温馨提示:抵制不良游戏拒绝盜版游戏,注意自我保护谨防受骗上当,适度游戏益脑沉迷游戏伤身,合理安排时间享受健康生活
水手风格小游戏版权归作者所有,如果侵犯了您的版权请联系我们,本站将在3个工作日内删除
VIP专享文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买VIP专享文档下载特权礼包的其他会员用户可用VIP专享文档下载特权免费下载VIP专享文档。只要带有以下“VIP專享文档”标识的文档便是该类文档
VIP免费文档是特定的一类共享文档,会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档
VIP专享8折文档是特定的一类付费文档,会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档
付费文档是百度文库认证用户/机构上传的专业性文档,需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档
共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档,具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。
这一节是本文的核心内容即推箱子16游戏求解算法的设计思路过程
前面已经说过过,推断局面反复的最好标准不是局面全然一致而是坐标排序同样且角色坐标通行
例如鉯下图。角色不管怎么移动不推动箱子的时候。都能回到原来的位置算作同一个局面:
再例如以下图。两个箱子互换位置结果与没囿移动箱子是一样的,所以排序箱子坐标以后一致还是同样局面
问:有必要推断局面反复吗?是不是仅仅是提升一下效率
答:不是为叻提升效率,而是为了能解出来假设使用递归,重复的局面重复耗尽堆栈而队列则耗尽内存
正如上图,重复推这两个箱子往返
问:排序全部箱子再比較,也太鸡肋了有没精髓?
答:有那就是哈希表,只是哈希表有一丝隐隐的风险那就是假设计算结果哈希不同,那么两团棉花数据肯定不同
可是假设结果同样两团棉花数据也可能不同,当然同样数据长度不同数据哈希同样的概率极其低像MD5那样把數
据长度加进去哈希的。反复就更加低把地球的沙子都哈希一遍可能也就几颗反复。为了速度我使用CRC32
问:那么,有了上面的基础把搬运工向四个方向移动生成快照。然后递归下去即可了吗
答:理论上是能够的,只是如上面所说搬运工不推动箱子的时候。没有意义属于闲走,我们的对象应该转移到箱子
把每一个箱子向四个方向推动都生成快照过滤反复,并“递归”直到全部的箱子归位
综上所述我们就能够開始动工了,给个小问题思考得到解法后,会不会还有更好的解法或者换个问法:队列的处理怎样进行?
我的方案是:先入先出即先增加队列的先处理。这样保证更低步数的快照先被分析。更低的步数当然是更好的解法终于第一个
解法自然是最优解法……
当中的内部指针指向结构体内部,比方Stars指向各个箱子的坐标而不用转换Matrix再计算偏移。我们用32位内存换取20多条汇编指令
一个刺客換一个王朝。,好快的剑……
STAR是AlphaStar算法的数据结构是一个坐标对
Move是走法信息,记录了某种走法所影响到的数据占48个字节。也存储与结構体内部限于篇幅这里就不详述
解法的逻辑步骤例如以下:
1.初始化队列。提取第一个场景到当前场景
2.当前场景全部箱子归位函数返回
3.汾析场景得到若干个新场景,过滤反复
4.过滤后新场景数量为零场景无解,删除场景(可优化见下一篇)
5.追加新场景到队列。分析队列丅一个场景反复2-4
6.队列场景数量为零,场景无解(或队列太小内存不足)
依据上一级场景生成新场景的函数代码(其它代码见资源包,限于篇幅这里不具体列出):
// 从队列中申请一个场景, 并以当前场景填充, 扫描后检測反复, 有效则追加到队列
// 复制上级数据, 修正指针
// 依据当湔动作, 推动场景
// 扫描线填充可通行单元
执行效果如图所看到的:
debug记录文件内容(下一节说说,程序的进一步优化这个结果未经过优化):
求解成功, 队列使用峰值=3869, 剩余有效个数=3867!