关于程序对推箱子关卡的标准化处理

sokoban

推箱子关卡常常有很多纯装饰的墙体、箱子等等。

如61期的大力神杯关卡：



因此大部分推箱子程序的作者的原则似乎不对关卡做任何修改，也很少有提供对关卡标准化的相关功能（没有太充分调查研究，可能有程序有相应功能我不知道）。

一个最简单的处理就是处理内外的空位，外部空位（人无法移动到之处）变为透明色。



另外，对关卡进行进一步处理可以认为是一种辅助解关的手段，去掉无效元素可以避免注意力被分散。
为了这个目的，就可以进行把所有外部元素（人接触不到的元素）删去。于是得到下图：



从辅助解关的角度看，这个简化后，仍然有大量无效的格子。最简单的一种类型就是：人可以去到的，但是有三面是墙体的空位。
可以把这类空位全部变墙，一个空位变墙，就可能导致第二个空位变墙。可以递归的完成变墙的过程。结果是下图：



仅凭三面是墙这个条件，依然有无效空位没有删去。

其他的一些辅助简化的情况还有：四个箱子在目标位置，并且成田字形，等等。还有很多情况，要一一列举出来，都实现到程序中进行辅助性关卡简化、标准化，并不是太容易。

sokoban

海上晴天 发表于 2014-7-23 09:39
大力神杯简化成了兔子 好玩
为了2014几个字还多了不少不用推的箱子

先大象，后兔子

sokoban

shamy 发表于 2014-7-23 19:49
这个话题有意思。
我想的是这样，除了标准整理墙壁外，还有需要判断所有箱子的活动范围，而且是不能死锁的 ...

这个问题的确不简单，所以发个帖子向大家学习一下。

sokoban

anian 发表于 2014-7-25 08:04
>>> 除了标准整理墙壁外，还有需要判断所有箱子的活动范围，而且是不能死锁的活动范围，然后判断人的活动范 ...

判断箱子能被推到的地方，我想这个没有任何问题。

问题是如何确定哪些是为了推箱子而必须用到的地方（这些地方比箱子能推到的地方要多一些）？如何判断真正无用的格子（箱子推不到，人也不需进去）？我觉得这里面可能有些复杂情况。一时没有想出很好的例子。再琢磨琢磨。

sokoban

laizhufu 发表于 2015-4-17 17:34
很久没有来MF8，曾经热闹的MF8推箱子仅剩下比赛在更新。

前几天看到百度公告：百度空间迁入新家百度云

多少互联网大公司的服务说停就停。

我们这个自娱自乐的推箱子比赛也进入第七个年头了。这要感谢laizhufu兄做出了巨大的贡献 ！！