推箱子的历史，理论研究和衍生游戏介绍-米儿火

本文会介绍推箱子类游戏的历史，相关研究，以及各种各样的变形都是怎样在基本规则上改进的，并会重点介绍几个比较新的有代表性的作品。把这一类的游戏放到一起介绍避免了介绍相似的游戏时很多基本内容要重复写一遍，而且也更容易比较不同游戏之间的相似和不同。不过由于这类游戏实在太多，保守估计已经有几千个，所以很难保证覆盖全面。目前为止只挑选了一些重点作品进行介绍，主要是比较有特色的。还有不少游戏没有介绍，部分游戏还没有发售的会在最后单独列出来，有些漏掉的作品会看情况增补。

历史介绍

推箱子是非常经典的解谜游戏，源自日本，到现在已经接近40年的历史了。日本其实逻辑谜题一直比较流行，Sudoku，Nonogram之类的经典的谜题大都是在日本发展起来的，这要归功于谜题出版商Nikoli。电脑解谜游戏方面，日本也比较领先，70年代末才出现了第一代个人电脑，而推箱子也是同一时代的作品。它是在在1981年由Hiroyuki Imabayashi（今林宏行）设计，英文名叫Sokoban（日文倉庫番，就是仓库工人），用BASIC语言编写，运行在PC-8801上，这是日本的第一代PC。据传他当时并没有打算商业化，做出来只是给朋友玩。后来在一名软件发行公司的推销员建议下才开始商业化制作。他成立了Thinking Rabbit，自己担任社长，并发行了这个游戏。最初版本只有20关，其中前10关是正常关卡，后面10关则是带有隐藏墙壁的变化关卡，因为后面不是纯逻辑谜题了，所以一般在讨论关卡数时认为初代只有10关。两年后，也就是1984年，他们推出了2代，有50关，这也就是到现在为止很多作者模仿的经典版。此后，Thinking Rabbit分别在1989年和1991年推出了Sokoban Perfect和Sokoban Revenge，各有306关，这些关卡合起来基本就是现在市面上各种推箱子游戏关卡的来源。这四款游戏都是发布在日本NES产的个人电脑，Spectrum HoloByte在1988年才把这款游戏引入欧美，移植到了比较流行的IBM-PC，Apple II之类的平台上，是经典版的50关。

在1990年，台湾大宇公司推出了仓库世家，正式将推箱子引入了中囯，此游戏一共250关。1995年，大宇又先后引进了Sokoban Perfect和Sokoban Revenge，游戏名分别叫仓库番：史上完整版和仓库番：玩家复仇版。

Thinking Rabbit也是很长时间没有出什么新作，只是不断的推出沿用之前关卡的作品和授权移植，推箱子被移植到了十几个平台，包括GB，MD，PS等。但新关卡其实不多，大部分关卡也都是来自于Perfect和Revenge两作。04年之后，推箱子归属Falcon公司，他们推出了各种手机平台的推箱子游戏，大多是运营商合作的，发行则大部分是SE发行，也有Konami发行的。15年后他们重新推出Windows版，这次是Perfect Plus，First Step Plus和Revenge的再版，都是Windows平台。此后又推出了苹果和安卓版本，不过两大应用商店早就有各种推箱子仿制品，官方版本基本被淹没了，不过相比较而言官方版本的画面和关卡都是很不错的。

复杂度和相关研究

推箱子属于滑块谜题（Sliding Piece Puzzle）的一种，有一本同名的书专门介绍这类谜题，是1986年牛津大学出版的，其中介绍了各种滑块谜题。其中大部分都是实体谜题，比如15谜题，华容道之类的（顺便说一下，华容道虽然是三国背景，但直到20世纪才有记载，是晚于欧洲的同类谜题的）。推箱子之所以能归入这一类是因为箱子和滑块没有本质区别，只不过只占一格，人可以看做唯一能自由移动的滑块。在这本书里，推箱子的原版10关在上面都有列举，同时作者还对各种谜题进行了难度评分，这10关的难度基本是逐步上升的。游戏的难度变化曲线，也就是游戏的节奏对于解谜游戏来说至关重要。人对于解谜游戏的要求实际上是比较苛刻的，解谜游戏既要难，但又不能太难。这里难指的是足够复杂，能够实现各种不同的解题方向，给玩家思考的空间；而简单则是指符合玩家的水平，不能超出太多，否则人们会乱试几下就失去兴趣，实际上游戏的节奏保持稍高与玩家的水平才更能吸引人们。难度需要一个量化标准，有不少理论研究了这方面的内容，因为推箱子是有实际意义的，比如机器人的控制和物品摆放这些实际问题可以简化为推箱子，这也是游戏的初始背景，而研究人的解谜方式则对人的认知和思维过程的理解都有所帮助。不过，理论上来讲，推箱子对于人和计算机的难度都很高。

对计算机来说难度的判断依据是复杂度理论，这里简单介绍一下，计算机专业或对理论不感兴趣的话可以跳过。复杂度理论主要用计算机的理论模型图灵机作为研究对象，主要研究的内容是时间和空间的复杂度。图灵机是一个无限长纸带，划分成小格，每格有一个符号，这是内存的抽象。还有一个读写头，可以左右移动，读写纸带上的符号，这是对总线的抽象。还有一个起始状态，终止状态，一个状态转移表根据读入的符号转到下一状态，这是对CPU的抽象。非确定图灵机就是每次能转移到多个状态，最终只要其中一个是终止状态就可以。

x论依据问题对时间和空间的要求分成不同的复杂性类，P是指多项式时间内确定性图灵机能判定的问题，NP指多项式时间内非确定图灵机能判定的问题。PSPACE是指确定图灵机多项式空间能判定的问题。多项式指的是所需的空间或时间能写成an^k+bn^(k-1)+…+cn+d这样的形式。n是问题的规模，在这里就是地图大小。判定指的是答案为真或假的问题，对于推箱子来说就是判定一个地图是否有解。

下面说结论：已经有人证明了推箱子问题是PSPACE-COMPLETE的，也就是说它可以用多项式空间解决，同时所有用多项式空间能解决的问题都可以在多项式时间内规约成为推箱子问题。证明的方法一般就是把一个已经证明为PSPACE-Complete的问题规约到推箱子问题。这里面包括的问题就很多了，其中一个是LBA（Linear Bounded Automata）问题，就是线性有界自动机能否接受一个输入，一般内存是有限的，LBA可以看成更接近于实际计算机的模型。另一个问题就是判断一个句子是否符合上下文相关语法。还有就是TQBF（True Quantified Boolean Formula）问题，就是判断一个只能取真和假，所有变量有全称和存在量词限定的逻辑表达式是否为真的问题。

Robert A.Hearn和Erik D.Demaine合著了一本书叫《Games,Puzzles,and Computation》，这本书里就把0人游戏也就是自动机，1人游戏也就是解谜游戏，2人的博弈比如围棋等放到了一个约束逻辑框架中，证明了各种情况下的复杂性，然后又用这个框架证明各种实际游戏的复杂性。对于解谜游戏就是采用将TQBF规约到约束逻辑的方法证明的。实际上Robert Hearn是MIT的博士，Erik Demaine是他的导师，这本书原来是他的博士论文。而Erik Demaine更是研究了很多关于游戏方面的理论，包括折纸和谜题等，还开设了好几门课程，对理论研究有兴趣的话可以去他的主页看看。

复杂度理论还是比较有意思的，在这方面上可以说解谜游戏，逻辑，语言和计算都是等价的。不过，对一般程序员来说，复杂性理论主要的作用是劝退，如果一个问题证明是NP-hard的话，除非想要把数学和计算机的奖得个大满贯，否则就不用费心找低复杂度的算法了。所以计算机解决推箱子问题的方法还是只能穷举，搜索所有可能的步骤寻找解，因此只能处理很小的地图，因为所需时间是随地图大小指数增长的，几百格的地图所需要的计算时间就远远大于宇宙的年龄了，而且计算机的速度提升几倍也就能处理的地图大小也就比原来+1而已，这也是区分多项式复杂度和指数复杂度的意义。

但人类和计算机的解决方法并不相同，人类不依靠搜索来解题，而是靠直觉（也就是heuristics），之前就有使用启发式算法进行搜索优化的，比如Hill-Climb Heuristic，就是把所有箱子离目标的距离之和作为优化的目标。但Petr Jarusek和Radek Pelanek认为这些方法并不能正确衡量谜题对人类的难度，他们建立了一个游戏网站记录每个人游戏时思考的时间，然后提出了一种人类模型，他们发现大多数人在初始位置附近花费的时间很多，但几乎不会在无效状态花费时间，一旦到达离最终点超过一半时就能很快完成谜题。因此他们提出了一个将随机走和有序走结合的模型，走到死路的概率为0，可以到达目标的状态权重高于其他状态，然后通过计算机多次模拟这个模型得到的平均步数来判断谜题对人的难度。他们认为人类适合抽象，问题分解和模式识别，因此还提出了另一个基于问题分解的方法，具体就是把箱子分成两组，每种分法计算在不同组之间交换最少的解法步数，最后得到所有分法的最小步数，第二种方法是每个箱子一组，计算不同箱子间交换最少的解法步数。以上两关是对人类难但对计算机容易的关卡，人类平均解决实际都超过了40分钟。

其实人是喜欢挑战的，大多数游戏复杂度都很高，很少有NP-hard以下的，毕竟难才有研究的意义，如果有固定解法的话很快就会变得无聊。有的游戏，比如Wayout和Zasa就都是P类问题，作为解谜游戏而言难度上限就差了一些，相比较而言也更容易无聊。关于推箱子的研究还有几方面，其中有关卡求解器，我们已经知道不存在有效算法来求解，但是可以对特定情况优化，用一些启发式搜索算法，同时尽早排除无效的情况可以提高能解决问题的大小。还有一方面的研究是随机关卡生成，纯随机生成的关卡大概率是无解的，而且不存在有效的判断方法，难度也很难界定。随机关卡生成和求解方法其实差不多，先生成一块地图和目标点最为最终结果，然后从最终结果开始，依据不同的判断规则寻找离目标最远的情况。不过生成的时间也比较长，近年人工智能比较热门，又有人提出神经网络进行关卡生成的方法，不过有趣的大型关卡还是需要有经验的人来设计。

推箱子的衍生游戏

推箱子作为一款经典游戏，风靡世界几十年，也启发了许多游戏制作人制作出各种各样的解谜游戏，下面就从不同方面介绍各种推箱子为基础游戏在创意和玩法上的变化和发展。

作为一款80年代的作品，原版的推箱子画面自然是十分落后的，随着技术的提升，也不断有人制作画面改进的关卡，加上了不同的风格和主题，还有各种各样的功能比如自定义关卡，换皮肤等。因为这类型太多了，也没有什么特别出色的，暂时不作过多介绍了。

这一部分主要介绍对基本规则进行简单变形的游戏，这些游戏的规则从始至终都是不变的，只有关卡难度增加。它们分别从地形，限制条件等角度对游戏进行了扩展。

强力推箱子原版的游戏一次只能推动一个箱子，这时的箱子既是障碍，又是目标，强力推箱子取消了这一限制实际上是减弱了箱子作为障碍的功能，代表作品有Sokostrong和杨超制作的QSokoban

拉箱子就是在推箱子上引入了拉箱子规则，这使得任意操作都是可以通过另一操作还原的，因此关卡只要有解就不会出现死局。Erik Demaine等人证明了这类谜题再3D情况下是PSPACE-Complete，2D且墙不占格子的情况下是NP-hard问题。代表作有Pullkoban和杨超制作的PSokoban

限制箱子的位置这类游戏通常将目标点和箱子进行编号或分组，典型的包括Sokomind Plus，引入了编号箱子。

这个网站引入了Modern Sokoban，加入了很多规则，其中就包括箱子分成4组。现代规则还包括格子各样的轨道，冰面，磁铁，洞等元素。完整内容在此：![]https:/www.sokobanonline.com/help/how-to-play))

改变关卡结构原版的规则是正方形关卡，有几个游戏或者游戏引擎可以处理六边形，三角形和八角形的关卡结构。不过关卡形状的改变其实只是改变了可选路径，对游戏本身的玩法其实没什么影响。代表作有各种推箱子引擎如The

MazezaM Engine

YHexoban

HexoSoko

YANKAI'S PEAK.

这个游戏是三角形的地图，用不同颜色区分不同的目标。

增加玩家普通推箱子是单可控角色的，这种规则就是允许有多个玩家，实际上这也更接近一般的滑块谜题。代表作Multiban

还有另一种游戏增加了非对称玩家，比如Olaf&Elmar in the Castles of Nabokos这个游戏结合了强力推箱子和非对称多玩家玩法，游戏中控制一只大象和一只老鼠，他们占的格子不同，力量也不同。

Ghost Sokoban这款游戏推入箱子后会变成地面，

这种玩法和把箱子推到洞里是一样的，还有Blocco

Gunther's Kistenschieben kesto这款则正好相反，会变成墙

Abyssal Zone

这款游戏中玩家只能顺时针移动。

Sokoban Coon

这款游戏对推拉以及最小和最大距离都没有限制，但限制了步数，所以游戏变成了寻找最佳策略的玩法。

加入滑动的冰箱子

推箱子其实是最小滑动的谜题，而有一类是最大滑动谜题，就是每次推动都会移动到没有障碍的最大距离。这类谜题种类也不少，值得单独讲，但有些游戏把这种箱子引入到了传统规则中。典型的游戏有日本的Ruta

和一款Java小游戏Sokobox

加入固定行为的怪物

这种类型的谜题虽然有怪物，但实际上怪物行为是确定的，没有随机成分，主要以逻辑为主，并不要求动作。

Eggerland/Adventure of Lolo系列

本系列有非常多的游戏，还有日版和欧版等混乱的版本号，不过游戏玩法几乎没有变化，每关需要收集心然后打开宝箱，不同的怪物有不同的行为，比如美杜莎会在四个方向没有障碍物的时候发射石化射线，但本身不会移动，还有的怪物会在收集齐心后才会攻击。

Zamby and the Mystical Crystals

这个游戏是和Adventure of Lolo差不多的一款游戏，2007年推出。也是有各种怪物，不同的是有大地图但不连续，仍然是关卡制，而且不需要移动到出口，但整体躲避怪物的玩法相当类似。

引入不同能力的人物

Parcel

这个游戏相对来讲是更讲究逻辑的，游戏一共有六种人物，最终目标是所有人物都达到指定地点。不同的人物设计非常有特色。Block可以推拉箱子，也可以拿起和放下箱子，箱子可以挡住机器人的激光。Magna相当于磁铁，可以远距离吸引箱子，距离足够远的话可以消灭机器人，Hackman可以改变某些方格的连通性，Porter可以与其他人物或箱子换位置三次。Shade可以穿墙三次，Clobber可以造路三次。

Berusky

这款游戏是开源的，加入了包括彩色门，炸药，锄头，单向门等多种元素。

Berusky II

2代进行了3D化，之前作为Bug's Escape 3D推出，但现在已经找不到了，作者开发了开源版本，只能在Linux下运行，而且关卡比之前少。

Kwirk

Amazing Tater

这两款都是GB上的游戏，主要目标是所有角色到达终点，游戏在推箱子上引入了旋转方块+不同大小的方块+多角色，关卡设计出色。

推箱子+消除=interLOGIC

这个游戏据说是根据1993年的同名Amiga游戏Balls制作的，此前是开源的，后来登陆了Steam，玩法是同色箱子消除，目标是消除所有箱子。

推箱子+多消+其他=Polyology

除了引入消除的玩法外还增加了滑动方块，固定方块，不规则方块，交换位置方块，定时方块等多种元素。

推箱子+Platformer=Toodee And Topdee

这是LD41的作品，这期内容是组合不相容的类型，而本作则巧妙地将俯视角的推箱子和平台跳跃关卡放到了一张地图上，创造了用箱子搭平台之类的玩法，很有新意。

推箱子+炸弹人=Tooki

这个游戏的解谜几乎都是建立在时间基础上的，其实逻辑性不是很强，游戏目标是把胡萝卜送到指定地点。

推箱子+贪吃蛇

Snokoban Dash

这款游戏结合了贪吃蛇和推箱子，还有Boulder Dash的玩法。

推箱子+音乐游戏=Resynth

这个游戏非常独特，游戏的逻辑部分不难，但是把箱子推到正确位置后是每个箱子发出一个音，同时不断有扫描线播放当前组合出的音效，关卡完成后就能组合出正确的音乐。

推箱子衍生的动作解谜

推箱子的单玩家特点让它可以很容易和其他类型游戏结合，包括塞尔达等游戏都加入了少许推箱子元素。下面介绍一些以解谜为主的推箱子游戏，这些游戏往往加入了非常多的元素，已经不再是纯逻辑解谜，有了对反应和时机掌握的要求。

Rescue Rover!

Rescue Rover II

这两款游戏是大名鼎鼎的Id Software作品，在它们推出一系列FPS代表作Wolfstain和Doom之前，它们出了两款推箱子主题的解谜小游戏，目标是从机器人手中救出狗。除了普通箱子外，其中还引入了激光，镜子，钥匙，门等各种元素，还有机器人作为敌人。

Chip’s Challenge

Chip's Challenge 2

这系列最初版本是1989年在Atari Lynx上推出的，后来移植到了Window 3.1上。最初版本主要设计者是Chuck Sommerville，此后他解决了版权问题，开发了续作，并将两部作品在15年登陆了Steam。玩法是收集芯片然后到达出口，其中有各种各样的机关，道具和敌人。

Chunk's Challenge 3D

这是Chip's Challenge的作者Chunk在14年的Kickstarter众筹作品，本作画面完全3D化，而且有非常多的部件可以组合，而且强调创意工坊，有编辑器让玩家自创关卡，比前作提升了很多。

Circuit Dude

可以算是Chip's Challenge的模仿者，玩法比较类似，同样支持创意工坊。

Wonderland

Wonderland Secret Worlds

Return To Wonderland

Wonderland Adventures

Wonderland Adventures:Mysteries of Fire Island

Wonderland Adventures

lanet of the Z-Bots

这系列也是一代经典，分为新三部曲（Adventure系列）和老三部曲，每关的目标是收集彩虹然后到达终点。游戏里箱子的作用主要是铺路，木箱可以浮在水上，铁箱会沉底，需要两个箱子才行，此外游戏有独特世界观和剧情，还有机器人等各种怪物和火焰发射器等。还结合了多种玩法，比如双人配合解谜，以及后续作品非对称的4人解谜，还支持关卡编辑器。本身谜题数目很多，到现在也不过时，是非常值得一玩的系列。

Push the Box