分类目录归档:推箱子

推箱子软件简史

作者:杨超 本文地址:http://sokoban.ws/blog/?p=384 三年前我在魔方吧论坛发过《推箱子简史》的贴子。之后我又千方百计的尝试运行了更多的推箱子软件,涉及的平台包括 Linux 和 Mac 系统、功能手机、智能手机和数字电视机顶盒等等,所以我打算重新梳理一下推箱子的历史,主要着重在软件的发展。 一、源于日本 1981春,今林宏行编写出世界上第一个推箱子程序“仓库番”,并于1982年商业发行《仓库番》[1]。这个版本有20关,其中只有前10关是标准的推箱子关卡[2]。后来84年发行《仓库番2》,89和91年分别发行《仓库番Perfect》和《仓库番Revenge》。日本国内发行的各种版本很多,但是有国际影响的主要是这几款,因为被移植到其他国家了。 推箱子诞生在个人电脑迅猛发展的初期,最初的《仓库番》是运行在 NEC PC-8801系统。 二、传遍世界 推箱子最早是由 Spectrum Holobyte 公司获得授权把“仓库番”移植到 DOS 平台在欧美地区发行。Spectrum Holobyte 发行的名为《Soko-Ban》的软件主要基于日本的《仓库番2》,有50关。这款软件在美国的发行面市时间估计在1988年,因为有两本杂志,《Computer Gaming World》和《Dragon》,都是在这一年介绍了《Soko-Ban》[3,4]。 而最早把推箱子介绍到中国的,应该是台湾的大宇公司了。很多老推箱子迷都是最先接触到大宇1990年发行的 DOS 版《仓库世家精彩篇》。这是一款带颜色的游戏,就是过几关出一张照片那种。后来95年大宇又正式代理发行了《仓库番之史上完美篇》和《仓库番之玩家复仇篇》[5]。 三、自由时代 最初的推箱子游戏主要以游戏公司商业发行推广的形式出现。但最迟从1992年起,推箱子软件逐渐地由个人开发的自由软件、共享软件和免费软件等占主导地位。主要原因我想有这么几个:推箱子规则简单但又让人上瘾,个人程序员有能力又有强烈的愿望编写自己的推箱子程序;而游戏公司则更在乎开发和发行大型的更能赚钱游戏。 独立开发者们基本形成了一个跨越推箱子软件的较弱的标准:xsb 关卡格式和 lurd 答案格式,有利于推箱子的交流和发展。也是这些独立开发者们把推箱子软件的功能发展到极致。 这一时期比较有影响的推箱子软件有以下一些,这些程序大都可以追溯到2000年左右或更早。 Unix/Linux 平台 XSokoban: Andrew C. Myers 编写的 … 继续阅读

发表在 推箱子 | 留下评论

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

作者:杨超 地址: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: ” … 继续阅读

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

用 Haskell 编写 LURD2XSB 程序

作者:杨超 本文地址:http://sokoban.ws/blog/?p=263 (4月24日和4月28日分别更新了一次) 推箱子关卡的答案通常用LURD文本格式来保存,而关卡则用XSB格式保存。更详细的介绍可参看XSB格式和LURD格式简介。一个有趣的事情是,仅凭一个有效的LURD答案可以还原关卡的初始状态(当然,有些“多余”的箱子和空位会变成墙体)。很多推箱子爱好者都编写过小工具来做这个从答案到关卡的转换,实现这类功能的程序通常都命名为lurd2xsb。如金优编写过一个具有很友好的图形界面的lurd2xsb。银河(skyivben)也提供了一个在线的lurd2xsb工具,并写了一篇博文介绍算法。 本文的目的是用函数式编程语言(Functional Programming Language) 编写一个命令行的lurd2xsb程序。函数式编程和命令式编程(imperative programming)的主要区别是:前者更接近数学,后者更接近机器语言。因此两者编程的思路差异比较大。Haskell 是比较流行的一种函数式编程语言,最早于1990年发布,从2009年起以下图作为标识(Logo)。Learn You a Haskell for Great Good! 是一个比较好的在线教程。 下面是全部代码。可复制存为一个lurd2xsb.hs文件,然后用ghc –make lurd2xsb.hs命令编译,会生成一个lurd2xsb可执行文件。之后用 ./lurd2xsb 或 cat [lurd file] | ./lurd2xsb 命令来运行。也可以用 runhaskell lurd2xsb.hs 直接即时编译并运行。 module Main where import Data.List (transpose, intercalate) import System.IO … 继续阅读

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

一些推箱子网站的历史截图

作者:杨超 本文地址:http://sokoban.ws/blog/?p=241 http://archive.org 网站致力于建立一个永久收藏各个时期的互联网网站的档案馆,从1996年起,就开始以不同的频率对全球的网站进行备份。老推箱子迷十分熟悉并有着深厚感情的,但现在已经关闭的两个推箱子网站:老封和20603的网站,都能在 archive.org 找到部分历史备份。 http://www.supersoko.com 老封推箱子 http://www.20603.com

发表在 推箱子 | 留下评论

推箱子关卡文件和正则表达式

作者:杨超 本文地址:http://sokoban.ws/blog/?p=225 正则表达式(Regular Expressions)在编写计算机程序中有广泛和重要的作用。无论是编译器把源程序编译成可执行文件,还是浏览器把HTML文件渲染成可视化的页面,其中第一步都是在做类似一个的工作,那就是有一个通称为词法分析器(Lexer)的组成部分把源程序或是HTML文件分离成一个个最小的单位,称为单词(Token)。这一过程中,词法分析器所作的事情就是通过正则表达式的匹配,把单词逐一识别出来。 正则表达式的匹配有非常成熟的通用算法,很多时候并不需要手动编写。很多编译器或是浏览器(如 webkit )的词法分析器都用一个叫 flex 的程序自动生成的。使用 flex 程序,先把需要分析的词法用正则表达式写到一个.l文件中,然后 flex 程序根据.l文件的描述生成c文件。flex 程序也可以用来读取 XSB 格式的推箱子关卡文件。XSB 的基本格式可以参看这里的介绍。除了用 #@$*+. 等字符来表示推箱子关卡中的不同元素之外,很多关卡文件还在每个关卡后面用 Title, Author, Comment 等关键词来标识关卡的标题、作者和注释等信息。下面是一个例子: ######### # # # # #***# # ######### * * # ## # * * # ## … 继续阅读

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

XSokoban

作者:杨超 本文地址:http://sokoban.ws/blog/?p=217 今天成功编译并运行 XSokoban.  XSokoban的下载地址:http://www.cs.cornell.edu/andru/xsokoban.html XSokoban 是早期Unix/Linux下的一个开源的推箱子程序,93年发布3.0版,到97年3.3c版后停止更新,是比较有影响的推箱子程序之一,早在94年就实现了箱子的智能拖放。XSokoban的作者Andrew C. Myers现为康奈尔大学(Cornell University)计算机科学教授,这个程序是他在博士毕业之前的作品。XSokoban用X Window System (又称X11)来处理图像界面,故称XSokoban. 我是在Ubuntu 10.04下编译并运行XSokoban的。因为年代久远,README文件语焉不详,我还是颇费了一番功夫才把这14多年前的代码成功编译。现把其中一些细节记下来备忘。 1. 修改config.h文件并用命令 ./configure –with-CC=cc 生成 Makefile 。其中 config.h里面把WWW设为0,并设定路径(ROOTDIR),用户(OWNER)和密码(PASSWORD)等信息。可根据命令 ./configure –with-CC=cc的错误提示来修改。 (2013年3月23日补充:系统升级到Ubuntu 12.04后重新编译了一次XSokoban,这里直接运行./configure脚本生成 Makefile即可,默认用gcc编译。另config.h中的目录一定要正确设置,否则编译后也会因为路径不正确在运行中无法创建scores文件而退出) 2. 用命令make编译。编译前,我手动在Makefile里设定了头文件路径INCS = -I/usr/include/X11(头文件xpm.h的路径),并把score.c里的getline 函数重命名为 getline2(和系统函数有冲突)之后才编译成功。 3.运行时要用 ./xsokoban -u <user>来输入用户名,在输入密码正确后才能运行。第一次还要用./xsokoban -c来创建scores文件。用./xsokoban -<xx>选关。 … 继续阅读

发表在 推箱子 | 留下评论

电子辞典和电视机顶盒上的推箱子

作者:杨超 本文地址:http://sokoban.ws/blog/?p=201 我最早是从电子辞典文曲星上知道推箱子这个游戏的。那是98年左右,最初见到的型号比下图的pc533还要老一些。 下图是另外一款电子辞典。 广东部分地区的“银视数字电视”机顶盒也有推箱子游戏。 珠海市的有线电视机顶盒自带一个不同版本的推箱子程序。

发表在 推箱子, 游戏 | 留下评论

tksokoban

作者:杨超 地址:http://sokoban.ws/blog/?p=171 【说明:推箱子是被克隆最多的经典小游戏。所以准备不定期介绍一些我试过的有特色的推箱子程序。】 tksokoban 是一个用 tcl/tk语言编写的推箱子游戏。下载地址:http://wiki.tcl.tk/7847 准确地说tcl是编程语言,tk是为tcl设计的跨平台GUI框架。tcl在TIOBE的2011年11月份的编程语言流行度排名中排第42名。上图是tcl语言的标识。tksokoban是以一种称为starkit的格式打包提供下载的,扩展名为.kit。要运行.kit程序,需要下载一个名为tclkit的运行环境。tclkit可以在 http://code.google.com/p/tclkit/ 下载,支持Win32、Linux等多个系统。这个网站还提供一个名为sdx的工具可以把starkit包解压(unwrap)为源程序。所以tksokoban是开源的。 在Linux下,用./tclkit-8.5.9-linux-ix86 tksokoban.kit命令运行tksokoban,用./tclkit-8.5.9-linux-ix86 sdx-20110317.kit unwrap tksokoban.kit命令把tksokoban.kit解压到一个名为tksokoban.vfs的文件夹。在Windows下,在tclkit的命令行中输入source tksokoban.kit 运行tksokoban。 tksokoban支持移动和直线推动的智能路径搜索,写于十年前的2001年,是一个还算不错的克隆。

发表在 推箱子, 游戏 | 留下评论