分类目录归档:推箱子

魔方吧推箱子比赛五周年

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=1133 随着第57期MF8(魔方吧)推箱子比赛结束,我们这个在线的推箱子比赛足足举办了五周年。这是一件值得高兴的事情,借这个时机总结一下这五年中比赛的发展变化。比赛能够举办五年,主要原因我想是推箱子爱好者们在编关和解关中得到了乐趣。anian、stopheart、荆先生、20603、zhenying、西北天狼、laizhufu、zhouxh、风过了无痕、(捷克)Přemysl Zíka、shamying、tengxi、Many illusions等都为比赛贡献过关卡。参加比赛的朋友就更多无法一一列出了。每期一般少则十来人,多则近三十人提交答案。参赛者来自中国、德国、法国、西班牙、保加利亚、阿鲁巴、丹麦、巴西、比利时、美国、俄罗斯等十多个国家或地区。我对编关和解关参与得较少,主要负责比赛的后勤工作。关于编关解关中故事,有待其他朋友来讲述,在此我说说比赛是如何办起来的,以及这五年中比赛网站、形式和奖品等的变化。 一、比赛的由来 比赛是借助魔方吧论坛这个平台办起来的,所以叫MF8推箱子比赛。魔方这个上世纪80年代风靡一时的智力玩具在2006年后又开始变得越来越流行了。究其原因,很重要的一个是有个民间组织叫WCA(世界魔方协会World Cube Association)在全球各地举办了越来越多的魔方竞速比赛。在这股潮流下,我也弄到了以前比较少见的四阶五阶魔方,并且于2007年夏天在MF8论坛注册了账号,而我注册的账号是sokoban。到了2009年,也跟MF8论坛的站长cube_master混了个脸熟。 2009年4月初,可能是由于老封关掉了他的推箱子论坛,MF8站长cube_master在魔方吧论坛里开增设了一个推箱子版。我马上毛遂自荐担任了推箱子版版主。可能是看到魔方的各种竞速比赛举办得红红火火,我很自然地也想在新成立的推箱子版搞一个在线比赛。于是开版才几天,第一期的MF8推箱子比赛就仓促开始了。 最初提交答案的方式极为麻烦。参赛者把答案加密打包在论坛回复,并站内私信把密码发给我。我再人工验证答案。比赛以这种很原始的方式运行了一年多,才得到改进。 前几期的比赛关卡也是由我从现有关卡中选取或是由我随意编的,质量不高。幸运的是,anian很快就加入比赛关卡的编排组织工作中,之后stopheart、荆先生和更多的朋友都为比赛提供了精彩的关卡,保证了比赛关卡的质量。 二、比赛网站 比赛的第一年,提交答案的方式的确很繁琐,很不友好。到了2010年6月,我学习了一些简单的PHP网站编程后,便利用国外的免费虚拟主机 http://sokoutil.orgfree.com 建立一个简易的在线提交和验证答案系统,简化了答案提交的流程。 比赛网站建立不到半年,由于不可抗拒的原因,中国大陆无法直接访问。于是把比赛网站整体迁移到另一国外的免费虚拟主机 http://sokoban.zzl.org 。搬家才两个月,中国大陆又无法访问了。一气之下,我便从国内的互联网服务提供商租用了虚拟主机,把网站再次迁移,从国外搬到了国内的服务器。同时依照工信部的规定,于2011年初通过了备案,成为一个合法的网站。 为了使比赛网站看上去更像一个正式网站,2010年底,注册使用了域名 sokoban.ws。2012年5月后,中国互联网信息中心(CNNIC)重新开放个人注册.cn域名,同年11月,我们又成功注册了 sokoban.cn 域名。 下面贴几个不同时期的比赛网站截图: 2010年10月 2011年11月 2012年4月 2014年3月(手机版截图) 三、比赛形式 我们一直希望吸引到更多的朋友参加到比赛中来,为此比赛形式做过一些调整。 第三十一期设立的围观答案,参赛者可以提交n-1个箱子归位的答案。到了四十三期,取消了围观答案,取而代之的是每期设立一主一副两个关卡。副关较为容易,降低参赛的门槛。事实上我们的比赛一直是完全公开的,不设任何门槛,参赛者甚至不需要在比赛网站注册账号,就可以参赛。 四、比赛奖品 我们的比赛虽然开始得比较仓促,但从第一期起就提供了奖品。 头两期的奖品是我厚着脸皮向MF8论坛的一位版主“七夜”要的,七夜没好意思直接拒绝,便赞助了两期铭浩之魔方。后来鬼手魔方也有意赞助我们的比赛,从第三期起到第五十五期,期间除了第三十期庆祝魔方吧论坛开坛八周年由大烟头赞助了宝石魔方,鬼手连续赞助了四年多。 从第三十四期到第四十八期,荆先生非常慷慨地赞助了幸运话费奖一年半。 比较遗憾的是目前比赛暂时没有了赞助,若有企业有兴趣赞助,我们非常欢迎。

发表在 推箱子 | 留下评论

大宇推箱子

作者:杨超 本文地址:http://sokoban.ws/blog/?p=925 我在《推箱子软件简史》一文中提到,是台湾大宇于20多年前最早把推箱子从日本引进到中国的。大宇直到今天仍在发行其他各种游戏。大宇在1990年发行《仓库世家精彩篇》,1995年授权引进了《仓库番 – 史上完整版》和《仓库番 – 玩家复仇版》。三款游戏都是在DOS下运行的,本文简单地介绍一下,大多数资料来源于台湾的网页,文末一一列出。 一,《仓库世家精彩篇》 这款游戏共250关 [1],但有两关关卡数据错误,正常情况下无法过关,分别是第194关和第244关。第194关有一个箱子错误地摆放在死角,青衫研究了关卡保存格式后,对194关作了修改后可过关 [2] 。第244关也存在类似问题,但箱子不在死角,可以用游戏修改器修改人的位置过关。 《仓库世家》的操作比较原始,只能用键盘一步一步的移动。 二,《仓库番 – 史上完整版》和《仓库番 – 玩家复仇版》 这两个版本在日本的发行年份分别是1989年和1991年 [5],而大宇是在1995年引进发行中文版的。 两款游戏分别都有306关 [3,4],游戏操作也有了一些改进,支持鼠标移动人和箱子了。但只支持箱子的直线寻径,且操作方式游戏别扭。首先人必须走到箱子旁边,然后右击箱子按住不放拖到能被直线推到的某个地方,再按下鼠标左键。 由于是DOS游戏,如今的 Windows 系统对DOS的兼容已经不是太好了,有时候需要用 DOSBox等工具才能在其他系统运行。而 DOSBox 对这两款游戏的兼容行不好,无法运行。有些老玩家对游戏打了补丁,使得可以在 DOSBox 下完美运行 [6,7]。   参考资料 [1] 倉庫世家精彩篇(攻略) http://blog.xuite.net/laurated/game/43084318 [2] 青衫 (邱奕南), 倉庫世家 … 继续阅读

发表在 推箱子 | 留下评论

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

作者:杨超 本文地址: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)确定图的割点。

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

用 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 … 继续阅读

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

判断推箱子关卡是否有解的多项式空间的算法

作者:杨超 本文地址:http://sokoban.ws/blog/?p=630 之前写过一篇博文介绍了一系列具有递归关系和指数长度答案的推箱子关卡。本文给出判断推箱子关卡是否有解的多项式空间的算法。这两篇博文结合起来,可以对计算复杂性理论里面的PSPACE问题的概念有比较直观的理解。推箱子游戏是一个非常好的PSPACE问题的例子。 一、P, NP和PSPACE 先定义推箱子问题。本文中说的推箱子问题,是指如下的一个判断性的问题:给出一个推箱子关卡,这个关卡是否有解?注意这里只判断是否有解,也就是说只要回答“是“或“否“,如果回答“是“,也不需要给出一个具体可行的lurd答案。 判断一个推箱子关卡是否有解,是一个PSPACE完全(PSPACE-complete)问题。PSPACE-complete问题是计算复杂性理论里面的一个术语。PSPACE-complete 所讨论的是推箱子问题的空间复杂度。简单地说,空间就可以理解为计算机的内存。我们假设一个推箱子关卡宽度为w,高度为h,则我们称这个推箱子关卡的大小为n=w*h。显然,一个关卡越大,我们用程序去计算关卡是否可解时,需要的内存就越多。PSPACE-complete 有两层意思。第一层意思是推箱子问题存在多项式空间的算法,也就是说存在一个算法A,这个算法对大小为n的推箱子关卡,最多使用$ n^k $(k是某一个与关卡无关的常数)的大小的内存就能回答出这个关卡是否可解。当然,所用的时间没有限定。第二层意思是推箱子问题是所有多项式空间可解的问题里面最难的一类。PSPACE表示所有多项式空间可解问题的全体,PSPACE-complete是PSPACE 的一个子集,是里面最难的那些问题的全体。这里“最难“是有严格的数学定义的,在此我们直观地认为从空间复杂度考虑最难就可以了。 计算复杂性理论的完整的理论体系建立于20世纪的70年代(1970年代)。而推箱子最早被证明是PSPACE-complete问题是在上世纪90年代末。就像我们前面解释的那样,证明推箱子问题是PSPACE-complete问题有两个要点。一是要说明推箱子是多项式空间可解的。二就是说明推箱子问题是多项式可空间可解问题里面最难的。其中第一点比较容易,本文的目的是给出一个判断推箱子关卡是否有解的多项式空间的算法。注意,这个算法只是理论上有意义,不适宜用来实际求解。在实践中,大多推箱子求解程序使用大量的内存,往往是随推箱子关卡大小呈指数增长。 在具体讨论算法之前,先说些题外话。前些年,媒体曾热炒过“庞加莱猜想”,这是Clay数学研究所(Clay Mathematics Institute)于2000年悬赏100万美元的七个尚未解决的数学问题之一,每个100万美元。其中“庞加莱猜想”最近已经被解决了。2010年,这个百万大奖授予俄罗斯数学家佩雷尔曼(Grigoriy Perelman)。但佩雷尔曼拒绝接受这个奖项和奖金。 在其他六个尚未解决的价值百万美元的问题中,有一个是属于理论计算机科学里面的问题,更具体地说是关于计算复杂性理论的问题:即 P vs NP问题。 我们用P来表示所有能用多项式时间(注意是时间,不是空间,区别于PSPACE)算法解决的判断问题全体。用NP表示所有所有能用“非确定性(Non-deterministic)”多项式时间算法的判断问题全体。可以证明,任何一个P问题都一定是NP问题,也就是说P是NP的子集。但是现在尚未确定的是,究竟P是NP的真子集,还是P=NP?这就是所谓的P vs NP问题,七个百万问题之一。 P和 NP都是从时间复杂度上考虑的,而PSPACE是从空间复杂度上考虑的。大家很自然会问,有没有NPSPACE问题?也就是说是否有“非确定性“多项式空间算法问题的全体呢?有的。但是作为著名的Savitch定理的一个推论,可以证明PSPACE=NPSPACE。即两者实际上是同一个集合,因此一般只提PSPACE。 Savitch定理是由Walter Savitch 于1970年证明的。我搜索了一下他的主页,发现他主页(http://cseweb.ucsd.edu/users/savitch/) 上照片似乎是在中国照的,大家可以去看看。这里提到Savitch定理的一个重要原因是下面介绍的算法是基于Savitch定理(参看[1])的证明设计的。 (图片来自Walter Savitch的个人主页) 可以证明,凡NP问题都是PSPACE问题,NP是PSPACE的子集。那么究竟NP是PSPACE的真子集,还是NP=PSPACE?这也是一个悬而未决的问题。多数数学家和理论计算机学家都倾向于认为P,NP和PSPACE三者,前一个都是后一个的真子集,也就是可用下图示意: 二、判断推箱子关卡是否有解的多项式空间的算法 下面开始讨论算法。 我们知道一个大小为n的关卡,实际有效的格子实际上是小于n的,但我们不妨设就是n。每个格子要么是箱子,要么是人,要么什么也没有,所以所能形成的不同的局面不会超过$ 3^n $种(事实上$ 3^n $高估了所有可能的局面数,但从数量级上是基本一致的),其中有一个局面是初始局面,有一个是目标局面。所以,如果一个关卡是可解的,一定在$ … 继续阅读

发表在 推箱子, 数学 | 留下评论

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=430 一 推箱子的其中一个很重要的魅力来源于推箱子求解问题在计算复杂性理论里是一个 PSPACE 完全问题。在这里不对什么是 PSPACE 完全问题作出解释,但是推箱子的一部分美妙之处可以认为正是来源于它的计算复杂度达到了 PSPACE 完全问题的级别。具体表现就是可以设计出很多不同模式的关卡,而且我们目前所涉及到的模式只是一小部分,还有很广阔的空间等待我们去探索。另外一个表现就是存在一系列具有指数长度答案(相对与关卡的大小)的关卡,这一类关卡就是推箱子关卡众多模式里面非常有趣的一类,也是本文要讨论的对象。 二 2009年6月8日,我曾在魔方吧论坛发贴子介绍了一类指数长度答案的关卡。无独有偶,约一个月后的2009年7月5日,Matrix67的一片博客文章也介绍了这一关卡。我的贴子和 Matrix67 的博文介绍的关卡都是基于2000年国外的一个关于推箱子问题的解答。 对这个关卡的具体分析这里就不再重复了,简单的说它就是由一个个的“房间”构成,上图是三个房间的情况。要过关,最左侧一个房间要进入2次,但要进入左一房间1次,就要进入左二房间2次,所以左二房间一共要进入4次。同理,左三房间就要进入8次。一般的,若有n个房间的话,第n个要进入2^n次,于是答案长度便成指数增长了。 这个关卡设计巧妙,让人感受到推箱子的美。下面我们要介绍一个更美的更简洁紧凑,但同样也是具有指数长度的答案的系列关卡。 三 这个更漂亮的系列关卡也是在推箱子玩家里面流传了很长时间了,有很多变化形式,其中最经典的可能是如下图所示。 这是 Aymeric du Peloux 2001年设计的 Picokosmos 第17关。David Holland 在2002年曾分析过这个关卡。Dries De Clercq 在这个基础上作了名为 Fibo 系列的变形关卡。上图所示的经典形式不只是一个关卡,而是一系列关卡,关卡可以纵向任意伸长(同时箱子也增加),只要保持箱子总数是偶数个就行了(奇数的时候关卡无解)。若用n表示箱子的数目,随着n增大,答案步数以n的指数函数增长。 没有玩过这一关的朋友可以点击此链接在线玩。先提前警告,虽然只有8个箱子,要解出来不太容易。 我是2009年在魔方吧发了前面提到的贴子之后,才注意到这个关卡,当时没有看到 David Holland 的分析文章,独立地研究了这一系列关卡的步数。下一节将简要的介绍一下我的计算方法。 四 上一节提到,这一系列关卡只对偶数个箱子有解。为了便于建立递推关系,我对箱子位置作了以下微妙调整,使得对奇数也有效。主要有两处改动:一是最下方一个箱子连同目标移动了一格;二是最上方一侧的箱子移下一格(哪一侧由奇偶性确定)。如下面所示,分别是4到8个箱子的情形(注意本节的图和上一节的图左右反了)。 本关在线游戏链接 … 继续阅读

发表在 推箱子, 数学 | 留下评论