分类目录归档：编程

作者：杨超 地址：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) 若队列非空，让队头结点出队。从此结点出发，分别尝试向上下左右推动箱子一格。(如：看是否能向左推动，就是看人能否自由的移动到箱子右侧一格，且箱子左侧一格为空) … 继续阅读 →