月归档:五月 2012

两款无主角的益智游戏

作者:杨超 本文地址:http://sokoban.ws/blog/?p=346 我在博文《介绍十款优秀的益智游戏》中曾尝试对推箱子类益智游戏作一个定义: 游戏由一个个关卡组成,每个关卡是一个2维或3维的迷宫,游戏者通过控制游戏中的1个或多个角色完成特定任务而过关。任务通常有两种类型,一类是走到迷宫中的某“出口”处,另一类是收集全迷宫中的某些物品。当然,关卡设计了各种各样的障碍,需要游戏者运用逻辑思考和试错等各种手段去找到正确的过关路径。一般没有动作因素,即不太需要迅速的反应和敏捷的操作。 这个定义中,游戏是有一个或多个可被控制的角色,而游戏中的其他元素是不能自主运动的,必须由游戏的主角对其间接控制。但也有一些益智类游戏是“无主角”的,或者也可以说游戏中的基本元素可以自主运动。历史比电子游戏还要悠久的滑块类游戏就是一个例子,滑块类游戏电子化之后也产生了不少新的花样。除了比较经典的滑块类游戏之外,人们也创造出很多新的“无主角”类的益智游戏。下面介绍两款过去一年中我见到的非常有特色的这类游戏。 第一款是由一个日本人写的Windows小游戏 Hanano Puzzle,大概可以翻译成《花之难题》。游戏可在其个人主页下载:http://qrostar.skr.jp/ 游戏的规则是这样的,十分独特而有趣的设计:有三种不同颜色的石头。石头若和颜色相同的花接触,便能在石头上面长出花来。游戏的目的是让所有石头开花。游戏通过鼠标操作,有两类允许的操作:一个石头可以单独左右移动,两个相邻的宽度为1的石头可以交换位置。石头没有东西支撑时会自由下落。 游戏共有50关,都设计得十分巧妙。一个好的益智类游戏关键在于关卡的设计,太容易或过关方式太单调的关卡显得无趣。但很多益智类游戏是靠增加游戏的元素种类来增加趣味性或难度,如《Laser Tank》可以认为是这类游戏的一个代表。而《花之难题》在如此简单的规则和不太大的一个迷宫里,能设计出不少难度很高且不雷同的关卡,给游戏者带来很愉悦的游戏体验。 另外游戏的程序设计也很优秀。特别是鼠标操作的方式,程序能直接识别鼠标指向的地方能进行何种操作。这个判别我觉得还是要费点劲才能写得好,因为情况很多(石头大小不同,水平高度不 同,等等)。如果程序作者偷点懒的话,他完全可以采取另外一种更容易实现(从编程角度)的人机互动模式:就是游戏者先用鼠标点中一个石块,再用键盘来左右 移动选择的石块。如果是先告诉我游戏规则,让我去写一个程序,那么结果就很有可能是后面这种鼠标加键盘的混合操作模式。所以说我觉得作者在人机交互的设计 上还是下了很大的功夫。 这个游戏很受欢迎,出来后不久就有玩家为它写了一个关卡编辑器。 第二款的规则也十分简单。在一个有重力的2维迷宫中,各种颜色的石头可以自主地左右移动,或自由下落。另外还有一个操作就是“固化”,可以把石头永久固定在当前位置,也就是相当于变成墙体了。有色石头可以互相“穿越”,这一点比较奇怪;但黑色石头不可以。游戏的目的是把所有的有色石头固定在目标位置。 游戏中还有两类元素帮助实现比较有趣的关卡:第一类是一次性的“染色”单元;第二类也是只能使用一次的“传送”单元。“传送”单元也是益智类游戏比较喜欢使用的一种元素,我在《介绍十款优秀的益智游戏》中提到的《火炬手》游戏也用了这一元素。特别是对以有重力的2维世界为舞台的游戏,没有这一要素,游戏的变化就有较大的局限。 我最早是在一个叫《Blockage》的Flash游戏中见到这种游戏规则。大概比较受欢迎,从而有了续作《Blockage 2》。这两个游戏的地址是: http://www.kongregate.com/games/guilovsh/blockage http://www.kongregate.com/games/guilovsh/blockage-2 后来,我又发现一个叫《Mr. Block》的Android游戏和《Blockage》的规则是一模一样的,甚至有些关卡都是一样的。看来优秀的游戏都避免不了被复制的命运。《Mr. Block》在Google Play 上的地址是: https://play.google.com/store/apps/details?id=com.Wuzla.game.Block_AD

发表在 游戏 | 留下评论

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

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

发表在 推箱子, 编程 | 一条评论

用 Python 写 lurd2xsb 程序

作者:杨超 本文地址:http://sokoban.ws/blog/?p=288 上一篇博文用Haskell写了lurd2xsb程序。请参阅上篇博文了解推箱子的lurd2xsb程序是什么。这回用Python语言来再写一次。Python诞生于1991年,支持包括函数式编程在内的多种编程范式,但偏重于命令式和面向对象的编程。 以下是程序的全部代码。存为lurd2xsb.py文件后,用python lurd2xsb.py命令运行。或者用cat [lurd file] | python lurd2xsb.py命令直接从文件中读入lurd答案。 class Sokoban: def __init__(self): self.level = “####@####” self.w=3 self.h=3 self.man=4 def __str__(self): temp = “”; for i in range(0,self.h): temp += self.level[i*self.w : (i+1)*self.w] + “\n” temp += “size: ” … 继续阅读

发表在 推箱子, 编程 | 留下评论