推箱子游戏的一个箱子推动路径搜索算法

作者:杨超

地址: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) 若队列非空,让队头结点出队。从此结点出发,分别尝试向上下左右推动箱子一格。(如:看是否能向左推动,就是看人能否自由的移动到箱子右侧一格,且箱子左侧一格为空) 若能推动,检查得到的结点是否新结点。

若是,加入搜索队列q的队尾。并在t中把这一新结点标记为1,同时把与之本质上一样的结点也标记为1。若同时还是目标结点,跳出循环,执行第(3)步。

若不是新结点,什么都不用做。

上下左右都尝试过后,回到第(2)继续。

(2.2)若队列为空,全部可能结点搜索完毕。到目标结点的路径不存在,返回。

(3) 路径找到。从目标结点出发,回溯 lurd 路径。为了回溯路径,在前面的搜索过程中,实际上还需要保存额外信息,如每个新结点的前继结点是哪个一个等等。

上面是需要返回目标结点的路径的算法流程。若不需要回溯路径,如只搜索哪些格子是能够推到的,算法只需作相应调整:不保存前继结点的信息,且第(2.1)步不跳出循环,直到队列为空算法停止,等等。

通过以上的算法分析,我们看到,箱子的路径搜索算法同时还要用到人自由移动的路径搜索的算法作为帮助函数来实现。

实践表明,因为问题本身的计算复杂度不高,即便是算法的具体实现不是特别好(如具体实现中,本可避免的大数组的复制操作太多),程序的表现也非常不错。比如,我用浏览器解释执行的 Javascript 语言编写的《SokoPlayer HTML5》,执行效率应该说比C之类的编译型语言差很多,但是对于80 x 50的超大型关卡,路径搜索也就是几秒的时间,绝大多数情况下是瞬间完成搜索。

此条目发表在 推箱子, 编程 分类目录。将固定链接加入收藏夹。