月归档:四月 2013

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

作者:杨超 本文地址:http://sokoban.ws/blog/?p=843 在博文《推箱子游戏的一个箱子推动路径搜索算法》中,我介绍了推箱子游戏如何用鼠标双击或拖放来进行推箱子操作。我知道的大概有十多个甚至二十多个推箱子软件都实现了这一功能。最近,anian告诉我,他通过用20603兄的《一箭十万》关卡测试了多个推箱子软件,发现《YSokoban》的速度最快,点击箱子,瞬间程序就给出了所有能被推到的格子的提示。而我编写的《SokoPlayer HTML5》则需要约2秒。经过和anian兄的讨论,我们改进了算法,大幅度提高的效率,使得《SokoPlayer HTML5》也能瞬间给出提示(约3毫秒)。下面简单介绍一下我们如何作出改进的。 在一个箱子推动路径搜索过程中,要反复判断人是否能从箱子的一侧自由移动(即不推动箱子情况下)到箱子的另一侧。这个不难判断,用简单的广度和深度优先搜索都能在线性时间内得到答案。但是箱子推动过程中,箱子位置在变化,要在不同的位置都作出判断。假设涉及到的格子有n个,每判断一次要O(n)时间,但箱子最多也可能出现在n个不同的格子,要做n次这样的判断,所以总的时间复杂度是O(n^2)。当关卡比较大时,如《一箭十万》是50×50的关卡,不算墙体,格子也上千,导致计算时间比较长。 后来,我们发现判断各种位置下人能否从箱子一侧自由移动到另一侧,可以用一个线性时间算法完成。这可以用图论里的割点(Cut Vertex)和块(Block)的理论和算法来帮助我们。举一个具体的例子来说明什么是割点和块。割点把关卡区域分割成不连通的小区域,称为块。下图关卡中,黄色格子为割点,共有10个块,分别用数字1到10标记。 我们若能把推箱子地图所对应的图中的割点和块全部标记出来,那么回答人能否从一侧移动到另一侧就很简单了。可以用这两步来判断:(1)先看箱子是否在一个 割点上。若不是割点,则人一定能从箱子一侧移动到任意的另一侧。若是割点,则还要进行第2步判断。(2)看该箱子这两侧的格子是否属于同一个块。若是,则 能移动。否则不行。 如上图中,若箱子在割点G6位置,人能从箱子左侧(F6)移动到上侧(G5),因为属于同一个块3号。但不能从左侧(F6)移动到右侧(H6)。又若箱子在H4位置,由于H4不是割点,人可以从一侧移动到任意的另一侧。 标记图的所有割点和块,有一个线性时间算法。这是一个基于深度优先搜索(Depth First Search)的算法。在深度优先搜索过程中,对每个结点记录两个参数。一个是结点的深度depth,另一个是结点的低位数(low point)。一个结点v的低位数是这样计算的,取下面三者的最小值:(a)v自身的深度,(b)v的所有邻点(DFS树中的父结点除外)的深度,(c)DFS树中v的所有子结点的低位数。 在实现中,通常用递归函数来进行深度优先搜索,于是计算低位数可以这样处理。每发现一个新结点v时,把低位数初始为该结点的深度(即a)。对v的每个邻点,若是父结点,不管;若是父结点以外的已访问结点,且若该结点的深度较当前的低位数小,重新赋值v的低位数为该结点的深度(即b);若是未访问结点,那么找到了一个子结点,于是递归调用搜索函数进行下一层搜索,返回时,若该子结点的低位数较小,则用它的更新v的低位数(即c)。 下面两幅图给出了一个例子,给出其DFS树(红色边),每个结点的深度和低位数。括号内为低位数,黄色结点为割点。 有了深度和低位数,如何判断割点和块呢? 对于割点,判断条件很简单,若结点v有某一个子结点的低位数大于等于v的深度,则v是割点。 搜索的根结点比较特殊,它是割点的条件是在DFS树中有至少两个子结点。 对于块的标记可以按如下方法实现。首先注意到割点同时属于多个块,其他点则恰属于一个块。在深度搜索过程中,每从一个子结点返回,并且由子结点判断出其父结点v是割点时,就意味着找到一个新的块了。此时,把v及其所有子孙都标记为同一个块。标记之后,在DFS树中,把v的所有子孙删掉,但保留v。这样v的子孙就不会被重复标记。而v是割点,还可能属于另外一个块。 以上文的图为例。2(2)是个割点,从子结点3(2)返回是能判断出来,同时能发现一个块。而从子结点3(3)返回时也发现2(2)是割点,于是2(2)在另外一个块中也被标记了。 [后两个图用LibreOffice Draw制作] 2013年12月22日补充:关于寻找割点算法,可参看用深度优先搜索(DFS)确定图的割点。

发表在 推箱子, 算法 | 一条评论

编译《Berusky2-0.9》

作者:杨超 本文地址:http://sokoban.ws/blog/?p=835 在Ubuntu下安装软件其实是非常容易。用了两年多Ubuntu 10.04,最近升级到12.04,发现软件安装更容易了。现在Ubuntu Software Center 还有大量的闭源和商业软件可供下载或购买,如《Steam》。 不过有时仍不得不自己编译软件。我之前编译运行过《XSokoban》。这个程序可能太老了,Ubuntu没有提供现成的安装包。要不是因为XSokoban是推箱子历史上比较有影响的一款自由软件,我也不会费功夫去编译它。 最近又遇到另外一个需要自己编译的软件《Berusky2》。我之前也在博文《Berusky 系列游戏》中介绍过。那时玩的是Windows下的demo版本。而这个游戏的完整Linux版是开源的,且还保持更新。但Ubuntu也没有提供现成的安装包,只好自己下载源代码编译了。 首先是要用 sudo apt-get install libsdl1.2-dev 等命令安装一些图形和声音库。这些库包括 SDL, SDL_image, OpenAL, ALUT 和 libvorbis 等。 然后用./configure脚本生成makefile,用make工具编译即可。必要时,还需要make clean之后重来。 经过这么一番折腾,终于编译成功,但是在任何一关过关时,程序都会崩溃(程序版本 berusky2-0.9 结合数据包 berusky2-data-0.7)。只好给开发者发邮件请求帮助。几天后,开发者解决了这个问题,是数据文件不完整导致,重新发布新数据包 berusky2-data-0.9。 补充(2013年6月16日):去年玩 Windows 捷克语demo版的《Berusky 2》对规则不求甚解。在Linux下编译了英文版后,这两天周末又玩了十多关,把 tutorial 和 training 两大部分关卡基本都通关了。越发觉得游戏元素机制和关卡设计极为出色,在我玩过的推箱子类益智游戏里面可以说是数一数二的。游戏的一个核心机制是bugs只能推动2个单位总重量的箱子(或箱子加臭虫)。而箱子有1个单位重的空箱子,2个单位重的装满的箱子和炸弹箱子,臭虫本身重1个单位。这一机制使得游戏关卡设计可以充分利用了空间特性,带来了很多2维推箱子所没有的体验。

发表在 游戏 | 留下评论