从shapez.io衍生出的一个算法问题

shapez.io是一个自动建造类的游戏,在游戏过程中衍生出了一个比较难的问题,就是关于判断一个图案是否可合成,以及求得它的合成方式。

目前游戏群内已经暴力检举了所有图案的合成路径,但是现在还是期望能找到一个算法,可以直接求得一个任意图案的合成路径。

抽象后的算法要求如下,希望有兴趣的同学可以帮忙。最好是Julia实现啦,这样一举两得。

2赞

感觉可以用大概 O(k n^2) 的时间来完成搜索,这里 n2^{16}k 是最多的操作数,总计算量是几十亿,还是有些偏大。每一轮对已有的图形两两组合做加法等操作得到结果取最小值即可,一共做 k 轮。

是的没错,我已经用这样的方式尝试过了,最后是得出了一个特定评分准标下所有图案的最优的合成路径,程序写得比较烂,跑一趟下来要半小时。然后把数据保存出来当做数据库,就可以快速查看了。

现在更想要一种方式,可以针对单个图案来分析合成方法,这样就可以指导游戏内的电路制作了。另外所有图案一眼就可以看出合成方式,但是却不知道怎么让代码得出这个结论,也很不甘心。

备案号:京ICP备17009874号-2