分类目录归档:编程

写在推箱子比赛第一百期之际

  本文地址:http://sokoban.ws/blog/?p=3627 作者:杨超 接触推箱子这个游戏已经近20年,发起在线推箱子比赛至今已8年有余。比赛每月一期,现在正进行第100期。由于这个比赛,使得我业余持续地关注推箱子游戏,并且推箱子游戏也持续地给我带来很大的乐趣。趁着第一百期之际,谈谈推箱子是什么,以及推箱子给我所带来的精神上的快乐。 一、推箱子是什么? 推箱子是一种成本极其低的智力消遣活动。早在推箱子出现之前,姜长英在1949年《论消遣》一文就分析过平民化的科学消遣的好处。最近看到《三联生活周刊》特约作者“土摩托”袁越在新浪微博问答中也表达了类似的观点:“……精神追求的成本越来越低了……我觉得这才是人类的未来,因为这是一种低成本满足所有人的唯一方式……”。 所以,以推箱子为爱好的朋友是非常幸福的,这玩意几乎不需要花钱。因为推箱子是一款纯软件产品。只要一个计算机系统足够开放和普遍,它上面一定会出现优秀且免费的推箱子软件,如Windows系统,如安卓系统。即便比较封闭的系统,如掌上游戏机、电子词典、电视机、机顶盒等等,都会出现推箱子。 我们举办网上的推箱子比赛的服务器成本也相当低。两个域名(sokoban.cn 和 sokoban.ws)加上租用服务器虚拟空间,平均每个月只要约28元,只相当吃一顿快餐。这么低的成本就可以把分散在全国乃至全世界各地的顶尖推箱子爱好者聚在一起,举办全世界水平最高的推箱子比赛,可算奇迹了。 这主要还是得益于电子计算机和互联网的快速发展。就最近来说,触屏式的智能手机只用了不到十年,就发展得非常成熟了,几乎取代了台式电脑,成为人们上网的主要设备。就我自己而言,微信等APP已经成为我获取信息的最重要渠道之一。很多跑步活动的信息我都是最先从微信获得,甚至就在微信中完成报名的。 因此,2014年7月,比赛网站也开通了微信订阅号,主要推送比赛开始等相关信息。继《推箱子加加》之后,愉翁又为安卓平台发布了《推箱快手》这款功能强大的APP。而苹果手机因系统较为封闭,虽是智能手机的引领者,却一直未见优秀的推箱子软件出现在该平台。 二、推箱子给我带来的快乐 下面罗列一些在推箱子中得到的快乐,其中很多事情做成了之后当时能高兴好几天。 为了测试各种平台下的推箱子,尝试了不同的操作系统。特别是编译运行了早期Linux平台下的XSokoban。为此至少连续使用了三年Linux的一个发行版Ubuntu作为平时工作生活的主要桌面系统。近三四年又以苹果的macOS X为主要的工作系统,因此对三大桌面系统Windows, macOS, Linux都算是比较熟悉了。甚至连PC-BSD, Solaris等非主流系统都安装试运行过几次。有了在不同的操作系统下的使用经验,对什么是操作系统的理解,比以前只会使用Windows时有了更深的认识。最近anian又告知有一款相当不错的Linux下KDE桌面的推箱子Sokoban SG,尚没有时间和精力测试。 学习并使用了多种编程语言。使用得比较多的语言是C、JavaScript、PHP。比较满意且花的功夫比较多的是用C编写的USokoban,用JavaScript编写的HTML5浏览器平台下的SokoPlayer HTML5,以及用服务器端编程语言PHP编写的比赛网站sokoban.cn以及关卡分享平台sokoban.org等。其它还尝试过写Firefox浏览器插件,用Python也写了一个简单的推箱子等等。后来因跑步和小孩出生,没有太多业余时间写程序了,但有些程序至今还时不时需要维护,如在第99期比赛时,还修正了比赛网站的一个bug:对副关的答案没有做“至少一推”的检验。 学习使用LAMP技术建设网站。LAMP是比较成熟的开源建站技术,租用服务器建站成本和技术难度都不算高。但是工信部对个人建立网站的管理时紧时松,为了比赛顺利进行,我还是在2011年初按工信部规定为比赛网站备了案。一开始只注册了sokoban.ws这个差强人意的域名,后来又注册到sokoban.cn和sokoban.org两个域名真是喜出望外。对整个互联网是如何运转的也有了些更深的认识。 琢磨了一些推箱子相关的算法。写USokoban时,实现了一个简单的解关器,掌握了解关器的一些基本算法。后来为了优化SokoPlayer HTML5推一个箱子的提示和寻径,想到了运用图论中找割点的算法,大大提高了计算的速度。 研究了推箱子及其变种的计算复杂度。计算了一系列具有指数长度答案的关卡所需要的精确步数。搞明白了推箱子问题的计算复杂度为什么是PSPACE完全的,还证明了推箱子的一个新变种也是PSPACE完全的,发表在学术期刊Theoretical Computer Science上面。 此外,关于推箱子的编关和解关,我几乎没有太多研究,还有许多宝藏有待今后挖掘。可见,推箱子是可以作为一生的爱好,不断地给人带来欢乐。  

发表在 推箱子, 数学, 算法, 编程, 计算机 | 留下评论

推箱子解关器算法(一):PI密室的故事
[ Sokoban Solver Algorithm (1) - A Story of PI-Corral ]

  本文链接:http://sokoban.ws/blog/?p=2570   作者:杨超  (by Yang Chao) 我曾在开源软件USokoban上实现一个简单的推箱子解关器,对其算法有一定了解,但不是太深入。最近发生了一件关于推箱子解关算法的论文剽窃事件,所以我也借此机会写写推箱子解关器算法。 I have implemented a simple solver in my open-source project USokoban,  so I have some basic understanding of Sokoban solver algorithm, but I am no expert on this topic. Recently, an idea … 继续阅读

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

用 Python 写 lurd2xsb 程序 (二)

作者:杨超 本文地址:http://sokoban.ws/blog/?p=729 半年前用Python写了一个推箱子的lurd2xsb小程序。昨晚好奇为了了解Python建站技术,在https://www.pythonanywhere.com申请了一个帐号。 然后今天研究了大半天,终于成功把之前的lurd2xsb通过web.py框架,稍作修改,成功地作为一个web程序运行。本来技术上没有什么困难,但是排除缩进引起的错误花了我很长时间。程序原有的Sokoban类的代码一个字符未动,只是输入输出方式有所改变。 通过web.py框架用Python写web程序,和php很不大一样。 最后这个lurd2xsb网页程序地址是:http://sokoban.pythonanywhere.com/。在这个地址斜杆后接lurd串访问,便在返回页面中显示还原的xsb格式关卡。比如这个链接。 全部代码如下: import web 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: ” + … 继续阅读

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

谈谈 C 和 Win32 编程

作者:杨超 本文地址:http://sokoban.ws/blog/?p=214 我是一个业余的编程爱好者,绝大部分编程的经历来自于编写推箱子游戏。说来断断续续也有十年的 Win32 编程经验了,在Windows平台上先后写过两个推箱子程序(2002, 2004-2005),一个 Color Lines 的克隆(2003),一个结合了滑块和跳棋因素的 Toads and Frogs 游戏 (2007),还有几个推箱子的变种(2010)。这些基本上都是2D的逻辑类游戏。不过我最满意的还要算是和 anian 合作的 SokoFind (2009, 2011)了,一个推箱子关卡的搜索工具,虽然我只编写了其中的图形界面部分。 最近两年,我主要使用 Ubuntu 平台的时间比较多,也接触了非 Win32 平台的编程,包括编写了三个不同平台的推箱子程序: JavaApplet 《SokoPlayer》,基于JavaScript 和 HTML5 的画布(canvas)特性的网页程序《SokoPlayer HTML5》,和在 Linux 下基于 GTK+ 的自由软件《USokoban》。 再加上早前的一个GBA上的推箱子程序,我一共写过5个平台(Windows, GBA, Java, Linux 和 Web)上的6个推箱子程序。 … 继续阅读

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

GBA上的推箱子程序

作者:杨超 本文地址:http://sokoban.ws/blog/?p=678 GBA是日本的任天堂公司于2001年3月发行的一款掌上游戏机。国庆在老家翻出了我十年前手抄的GBA硬件技术文档和GBA使用的ARM7tdmi微处理器的指令和汇编语言技术文档。那是我在2002年大三暑假的时候对着电脑上的PDF文件抄的,抄这玩意大概花了我一个月的时间。当时抄的目的只有一个,就是为了写一个在GBA上运行的推箱子程序。 之所以有写一个GBA上的推箱子程序的想法,主要有那么几个原因。一是当时我有一部GBA,二是从同学JimmyZ那里弄到一个基于gcc的GBA开发包DevKitAdv,三是我对推箱子莫名的喜爱,在那之前已经写过一个Windows下的推箱子程序了。 虽然我费了很大力气抄写了技术文档,但最终用到的却不多。因为GBA是没有操作系统的,程序直接运行在硬件上,所以对我来说还是有比较多新奇的东西。如检查按键可以直接读取某固定地址的内存。下面代码判断A和L键是否同时按下。 #define REG_P1         *(u16*)0×4000130 #define KEY_A 1 #define KEY_L 512 short int key=REG_P1; if( (key & KEY_L)==0 && (key & KEY_A)==0 ) {…} 对显存的操作要复杂一些,十年之后我扫了几眼源代码还是不能明白个大概。显存主要支持背景和小精灵(sprite)等面向2D游戏的功能。 经过一番努力,先是在当年的8月底成功编写出一个可以在模拟器上运行的推箱子程序,用的时间似乎比抄技术文档的时间还少。我主要用VisualBoyAdvance来测试。 再过了几个月,有了烧录卡之后,在GBA真机上也成功运行了。GBA在运行一个卡带之前,要先CRC验证,若验证不对则终止运行,而模拟器往往忽略这个验证。所以要在真机上运行,还要用一个工具把正确的CRC写到二进制文件的恰当位置。我当时编译使用的批处理文件如下,其中GBARM就是用来计算并写入CRC的。 path=C:\devkitadv\bin gcc  -o skb.elf skb.cpp  -lm objcopy -O binary skb.elf … 继续阅读

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

Chrome 扩展: Sokoban.WS Tools

作者:杨超 本文地址:http://sokoban.ws/blog/?p=618 昨天的博文写了我是如何编写Firefox的扩展Sokoban.WS Tools的。在写的过程中,我注意到相似图片搜索TinEye网站不光是有Firefox的扩展,还同时有Chrome、Opera等其他浏览器的扩展。我就装了TinEye的Chrome扩展,和它的Firefox扩展一样,实现同样的功能:在图片上方点击右键,通过右键菜单快捷搜索。于是我就琢磨着如何把Firefox上的推箱子扩展也移植到Chrome浏览器上。 为了实现这个目的,还是浏览官方的技术文档和通过著名的编程技术问答社区StackOverflow来学习Chrome扩展的编写方法。经过一番了解,发现Chrome的扩展也是用JavaScript来编写的,但是具体实现方案又和Firefox的扩展不一样。首先,Firefox是用特有的XUL格式来描述扩展的界面的。但是Chrome没有专用的界面描述语言,而是和网页一样,用HTML5来描述。比如,选项对话框在Chrome的扩展里面就是一个本地的网页在新标签中打开,而不像Firefox那样是一个弹出的对话框,和网页有明显区别。而右键菜单项的更改则是在JavaScript代码中调用Chrome提供的API函数来实现。其次,Firefox扩展的JavaScript代码可以同时和扩展的界面控件以及当前浏览的网页中的各种要素对话。而Chrome扩展的JavaScript代码分成background和content两类。Background代码只和扩展自身的对象打交道,如右键菜单、本地选项页面、扩展在地址栏上的图标等等。要获取当前浏览的页面的内容,只能由Content类代码完成。Background和Content两类代码是相对独立的,要完成有用的扩展功能,两者必须交流。于是Chrome就设计了一种Message机制,通过在Backgournd 和Content代码之间请求和回应Message来让Background代码间接地获取当前浏览的页面的信息。主要就是这两点不同。这导致的结果就是Firefox扩展的表现力更强,而Chrome扩展被有些人戏称为就是本地的HTML+JavaScript应用,和浏览器的结合度相对较弱。 不管如何,要实现我想要的推箱子扩展功能,Chrome的扩展技术还是可以办到的。于是又用了大半天时间,完成了Chrome上的扩展Sokoban.WS Tools。因为和Firefox上的扩展是完成一样的功能,核心的逻辑(即把XSB格式关卡转换成SokoPlayer HTML5能识别的URL参数的几十行JavaScript代码)是一样的,这部分代码可以直接重用,所以我给扩展起了同样的名字:Sokoban.WS Tools。下面是Chrome上该扩展的截图: 做完了Chrome的扩展之后,很自然的就想能否再移植到其他浏览器上。所以我就继续考察了另外一个浏览器Opera的扩展。考察方法还是先安装相似图片搜索工具TinEye的Opera扩展。令我颇感意外的是,TinEye的Opera扩展用了一种不太好的方法来实现。右键菜单不再使用了。取而代之的是在Opera地址栏最右方出现一个TinEye的图标,点击该图标,会弹出一个悬浮框显示当前页面的所有图片,再点击想要搜索的图片进行搜索。这种方法相对右键菜单来说,明显是一种较差的方案。所以我有理由相信,Opera扩展所能提供的功能较弱,扩展是无法修改浏览器的右键菜单的。于是我就没有继续研究了,浏览器扩展的探索大概到此也告一段落了。

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

Firefox 扩展 Sokoban.WS Tools

作者:杨超 本文地址:http://sokoban.ws/blog/?p=609 我大概是从2010年春起使用 Firefox 作为我的常用浏览器。Firefox有很多性能都比IE强。比如地址栏所支持的URL长度至少8000字符以上,远远大于IE的大概2000字符的限制。Firefox 对HTML5的支持较好,我编写的网页程序SokoPlayer HTML5有些功能就只能在Firefox下使用。后来又发现Firefox有很多好用的扩展(extensions/add-ons)。我必装的扩展主要有:显示网站服务器所在国家等信息的Flagfox,显示网站全球排名的Alexa Sparky,网页截图工具Abduction!,等等。 前些天,我使用TinEye的相似图片搜索工具时,发现他们也提供一个Firefox扩展。安装该扩展后可以在任何一个网站图片直接点击右键,选择Search Image on TinEye直接搜索,十分方便。于是,我产生了给推箱子写一个插件的想法。推箱子迷们常常在论坛(如魔方吧推箱子版)和邮件中交流和分享新的关卡。大家交流时都是用标准的XSB文本关卡格式,这种格式被所有主要的推箱子软件支持,只要复制粘贴就可以了。我编写的在线推箱子程序SokoPlayer HTML5 也支持读入这种格式。即便如此,还是需要点击好几下鼠标才能把网页中的XSB格式关卡读入程序。如果能在选中XSB文本后直接用右键菜单把关卡载入在线的SokoPlayer HTML5程序,就可以节省好几步操作。而且SokoPlayer HTML5已经具备了从URL中读入关卡信息的功能,剩下的就看Firefox扩展如何编写了。 于是我花了些时间查阅了网上的Firefox扩展的技术文档和快速入门。我发现Firefox的扩展从技术上并不复杂,原来也是用 JavaScript编写的。简单地说,Firefox扩展主要由两部分构成。第一部分是扩展的界面。Firefox的扩展可以以右键菜单,地址栏,状态栏(扩展栏)或者选项对话框等标准形式出现。扩展可以采取其中的一个或者多个作为界面,而界面是用基于XML语言的XUL格式来描述的。第二部分就是扩展的代码。用户在通过上述各种形式的界面调用扩展时,扩展如何处理。这一部分就是用 JavaScript 语言来编写了。这和HTML+JavaScript的工作原理类似。最后,把这两部分加上一些额外的描述文件一起压缩成一个ZIP文件,把文件后缀由.zip改为.xpi,一个扩展就制作完成了。这就是Firefox扩展的原理。 知道了Firefox扩展的基本框架,我再查阅了Copy As Plain Text, JiaThis, TinEye等扩展的代码。在这基础上,我用了大概一天多的时间,完成了一个简单的Firefox插件,实现了我前面提到的想法:在页面中选中XSB关卡,然后调用右键菜单在新标签中打开SokoPlayer HTML5在线程序,并直接载入XSB关卡到程序中去。我把扩展命名为 Sokoban.WS Tools,虽然目前只有一个功能,但以后有新功能的想法还可以继续添加。 这个扩展我已经提交到Mozilla Add-on for Firefox了,可以从以下地址安装:https://addons.mozilla.org/en-US/firefox/addon/sokobanws-tools/ 下面分别是扩展使用时和选项对话框的截图。 右键菜单: 选项对话框:

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

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

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

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