程序员用Java实现推箱子算法网友:这绝对不是一

发布于:2019-05-29   编辑:admin 浏览:

  《推箱子游戏》是一款益智游戏,游戏目标是搬运工自己来找出到某个位置的最短路径,然后自己走过去。

  地图是这个游戏中非常重要的一部分,关于地图的存储,因为有一部分元素是可以重叠放置的,所以用了一个类似二进制的存储方式,就是4种物件分别有是否存在状态,使得用一个数字可以表示多个物件。

  一、在不移动箱子的情况下其实无论人在哪里对于map来说是没有影响的,所以填充可移动区域可以让需要存储地图的数量有一个大的下降。例如之前那副地图:

  这样就把存储量缩小了四分之三。至于怎样填充,相信对图论有一点了解的都可以随便想出方案,我这里用的是BFS。

  二、关于箱子的移动方式,直接用整幅地图的BFS搜索会比较靠谱。因为可以确定箱子的位置和在不移动箱子情况下人能到的位置,所以箱子可移动的位置也就能确定了,再加上之前存储的所有箱子的位置,这样就能计算出箱子每动作一次地图能更新的情况,一次BFS就是每个箱子往不同可移动位置进行一次移动。

  有箱子被推到角落并且不是在目的地--------说明不是正确的路线,搜索不再往下走。

  当前地图在以前已经被达成过--------说明是重复路线,搜索不再往下走。

  四、关于地图的存储,用的是hashSet,并重写了equals和hashCode的实现,用来自动判断地图是否重复。(以此保证不重复)

  最后完成地图显示问题,每个节点存储自己父亲节点的地址,当节点发现自己已经完成之后根据地址向上查找直到树顶。

  \u300a\u63a8\u7bb1\u5b50\u6e38\u620f\u300b\u662f\u4e00\u6b3e\u76ca\u667a\u6e38\u620f\uff0c\u6e38\u620f\u76ee\u6807\u662f\u642c\u8fd0\u5de5\u81ea\u5df1\u6765\u627e\u51fa\u5230\u67d0\u4e2a\u4f4d\u7f6e\u7684\u6700\u77ed\u8def\u5f84\uff0c\u7136\u540e\u81ea\u5df1\u8d70\u8fc7\u53bb\u3002

  \u8bdd\u4e0d\u591a\u8bf4\uff0c\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0b\uff1a

  \u4e8c\u3001\u5173\u4e8e\u7bb1\u5b50\u7684\u79fb\u52a8\u65b9\u5f0f\uff0c\u76f4\u63a5\u7528\u6574\u5e45\u5730\u56fe\u7684BFS\u641c\u7d22\u4f1a\u6bd4\u8f83\u9760\u8c31\u3002\u56e0\u4e3a\u53ef\u4ee5\u786e\u5b9a\u7bb1\u5b50\u7684\u4f4d\u7f6e\u548c\u5728\u4e0d\u79fb\u52a8\u7bb1\u5b50\u60c5\u51b5\u4e0b\u4eba\u80fd\u5230\u7684\u4f4d\u7f6e\uff0c\u6240\u4ee5\u7bb1\u5b50\u53ef\u79fb\u52a8\u7684\u4f4d\u7f6e\u4e5f\u5c31\u80fd\u786e\u5b9a\u4e86\uff0c\u518d\u52a0\u4e0a\u4e4b\u524d\u5b58\u50a8\u7684\u6240\u6709\u7bb1\u5b50\u7684\u4f4d\u7f6e\uff0c\u8fd9\u6837\u5c31\u80fd\u8ba1\u7b97\u51fa\u7bb1\u5b50\u6bcf\u52a8\u4f5c\u4e00\u6b21\u5730\u56fe\u80fd\u66f4\u65b0\u7684\u60c5\u51b5\uff0c\u4e00\u6b21BFS\u5c31\u662f\u6bcf\u4e2a\u7bb1\u5b50\u5f80\u4e0d\u540c\u53ef\u79fb\u52a8\u4f4d\u7f6e\u8fdb\u884c\u4e00\u6b21\u79fb\u52a8\u3002

  \u56db\u3001\u5173\u4e8e\u5730\u56fe\u7684\u5b58\u50a8\uff0c\u7528\u7684\u662fhashSet\uff0c\u5e76\u91cd\u5199\u4e86equals\u548chashCode\u7684\u5b9e\u73b0\uff0c\u7528\u6765\u81ea\u52a8\u5224\u65ad\u5730\u56fe\u662f\u5426\u91cd\u590d\u3002\uff08\u4ee5\u6b64\u4fdd\u8bc1\u4e0d\u91cd\u590d\uff09

  点击“提交”后,我们会向您的邮箱发送一封验证邮件,请按照邮件中的提示完成操作。