-
最近文章
近期评论
- [坑]POI补完计划#1 | qiancl 在 推箱子游戏的一个箱子推动路径搜索算法 (二) 上的评论
- [坑]POI补完计划#1 – qiancl 在 推箱子游戏的一个箱子推动路径搜索算法 上的评论
- HZF 在 推箱子是PSPACE完全问题 上的评论
- sokoban 在 马拉松简史 上的评论
- 跑步世界 在 马拉松简史 上的评论
2024 十月 一 二 三 四 五 六 日 « 八 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 文章归档
分类目录
博客链接
功能
分类目录归档:编程
推箱子游戏的一个箱子推动路径搜索算法
作者:杨超 地址:http://sokoban.ws/blog/?p=298 推箱子自1981年诞生至今,已经超过30年了。推箱子软件的功能也有了很大的改进。从刚开始的只能用键盘一步一步的移动,到上世纪90年代后期起,用电脑辅助搜索一个箱子的推动路径,从而实现用鼠标两次点击(或是拖放)就能实现一个箱子的任意推动。可以说,电脑辅助路径搜索,已经成为推箱子软件的一个标准功能,使得人们从繁琐的逐步操作中解放出来,在更大一些的关卡中探寻更多的挑战和乐趣。 一个箱子的推动路径搜索并不是一个很难的算法,用最基本的广度优先搜索算法(Breadth-first search),就可以很快地找到一个推动数最少(但此时移动步数不一定最少)的路径。我2002年春写《Final Sokoban》第一次实现了这个算法,2004年写《M2 Sokoban》又实现了一次。这两次都是用C++或C在Windows平台下写的。2010年后写Java Applet《SokoPlayer》,用C写Linux下的《USokoban》和用Javascript写《SokoPlayer HTML5》,都实现过这个算法。下面简单说一下这个算法的要点。 首先,必须明确搜索的一个结点是什么。我们是考虑选中一个箱子后,不推其他箱子的前提下,把选中的箱子推到一个目的地。于是,在推动这个箱子的过程中,其他箱子可以视为墙体。又我们以推动一步为基本的单位来搜索,不以移动一步来搜索。所以搜索的一个结点由两个要素确定:一是箱子的位置,二是人相对于箱子的方向。这是因为箱子可以把人隔在关卡中不同的区域。 以下面这个简单的关卡为例: (图一) 可以点击下面链接玩这一关。 http://sokoban.ws/sokoplayer/?w=4&h=9&lvl=HHHH|H__H|H__H|H__H|H__H|HH$H|_HaH|_H.H|_HHH 这一关的按广度优先搜索得到的树如下: 在上述搜索树中我们看到,结点a 和结点 f 的箱子位置是一样的,但是由于人的位置不同,所以是两个不同的结点。一般地,当前要推动的箱子最多把关卡隔为四个不同区域(即上下左右,在程序中可以用0,1,2,3或其他常数表示)。所以若关卡大小不超过n*n,则搜索总的结点不超过 4n*n 个。 广度优先搜索通常要用到一个先入先出(First-in first-out)的队列(Queue)来保存搜索过程中的结点。根据前面的分析,每个结点只需保存箱子位置和人相对于箱子的位置。如,结点a可记为[(C, 6) 下],其中(C, 6)是图一中箱子标尺坐标,“下”表示人相对于箱子的位置。这样,一个结点在搜索队列中用2到3个字节便可以保存。 其次,搜索过程中,结点可能重复出现,我们必须记住哪些结点前面已经访问过了,只把新的结点添加到搜索队列中。比如上面例子中,结点 e 箱子有向上和向下推两种可能。向上推得到新结点g;向下推得到的本质上是结点c,这个在前面已经出现,所以忽略不要。 幸好,我们已经分析过了,总结点不超过4n*n个,我们可以用一个4n*n个单元的数组来记录结点是否已经访问过。初始时,数组全为0,每遇到一个新结点,它在数组上对应的位置改为1,表示访问过了。于是,搜索中,我们每推一步得到一个结点,只需查看该数组的相应位置是0还是1,快速判断这个结点是否新结点。 比如,结点c我们可以记为[(C,4)下]。我们确认它是一个新结点加入队尾时,把[(C,4)下]对应的位置标记为1。注意,同时我们把[(C,4)左]和[(C,4)上]也标记为1,因为这三者本质上是同一个结点。在具体的算法实现上,我们检查一下人能否从箱子下方在不推动任何箱子的前提下,自由地移动到箱子的其他方向。 有了以上的分析,我们可以把总的算法描述如下(假设关卡不超过80 x 80): (1)初始化准备:建立搜索队列q,把初始结点入队。用数组t[80][80][4] 来记录结点是否访问过,初始化为全为o,然后把数组t中与初始结点对应的位置和与之等价的位置标记为1。 (2) 主循环:根据队列是否为空,分别执行操作(2.1)或(2.2) (2.1) 若队列非空,让队头结点出队。从此结点出发,分别尝试向上下左右推动箱子一格。(如:看是否能向左推动,就是看人能否自由的移动到箱子右侧一格,且箱子左侧一格为空) … 继续阅读