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

sokoban

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

如61期的大力神杯关卡：



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

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



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



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



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

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

海上晴天

大力神杯简化成了兔子 好玩
为了2014几个字还多了不少不用推的箱子

sokoban

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

先大象，后兔子

shamy

这个话题有意思。
我想的是这样，除了标准整理墙壁外，还有需要判断所有箱子的活动范围，而且是不能死锁的活动范围，然后判断人的活动范围，如果某个地方人能到达，但是四周不存在箱子的活动范围，就可以变成墙。计算量有点大。
箱子已经推死的话，可以变成墙，但是这个涉及到解关死锁判断了。

sokoban

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

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

anian

将关卡尽量变小删除没有用的空间， 这个问题很早以前和歪推作者George讨论过。

因为已经是很久以前的事， 详细的讨论已经忘记了。
找EMAIL也是不容易。

记得的资料应该不齐全， 有以下这些...

每次一个关卡过关了， 歪推是保存这个关卡的答案。
它保存的关卡就是经过删除某些没有用的多余的空间才保存的。

除了正常的删除“人无法去的地方”， 它也是删除dead end tunnel (死胡同)。
这个就是版主说的三面是墙壁(而且空间不是目标点)。

还有的是， 如果开始人一定需要推动箱子， 没有其它选择的，
它也是删除这些空间 (当然， 箱子被推了后如果再也无法动的， 也是变了墙壁)。

如下面这个关卡：
----#####
---##.$@#
--##.$$##
-##.$$.#-
##.$$.##-
#.$$.##--
###.##---
--###----





你放入歪推就看到它是自动认识关卡和答案。
这个答案其实是删除关卡的过程中得到的。

这个关卡经过“优化”后剩下的就只得人和四面是墙壁。
歪推对关卡的优化未必每个人都是接受。

除了无法推动的箱子(已经在目标点)， 作者也是曾经说过这个情况下， 通道里面
的多余空间(上面两个)可以删除：

anian

>>> 除了标准整理墙壁外，还有需要判断所有箱子的活动范围，而且是不能死锁的活动范围，然后判断人的活动范围，如果某个地方人能到达，但是四周不存在箱子的活动范围，就可以变成墙。计算量有点大。

这和我的想法类似。(或者完全相同)
昨天和版主说过类似的计算。

基本上就是:

(开始整个关卡没有做标记)

(1) 关卡里面选择一个没有做标记的箱子。 (暂时将关卡里面的其它箱子全部变成空)
(2) 计算这个箱子可以推到的全部地方(和人必须要走过的最短的路去推这个箱子)
(3) 这些空间全部记下来 (做标记)
(4) 重复 1， 2， 3 直到全部箱子已经做了标记。

完成后， 就标记了全部箱子可以推到的地方(和人必需要到的空间去推这些箱子)。

没有做标记的空间， 全部可以变成为墙壁。

计算箱子可以推到的全部地方有点复杂。
如果关卡大和没有好的计算方法， 会很慢。

幸好之前版主已经解决了这个计算问题， 现在计算箱子可以推到的地方可以很快的就计算好。
虽然是复杂了点， 但还是可以很快就做到。

sokoban

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

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

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

shamy

感觉上，需要找的就是“填个墙，与不填墙，不能影响箱子移动的路径”的地方，所以，如果要是填了一个墙以后，要从头找一下所有箱子，是否受到了影响。这个重复计算的太多了。除非分清每一个箱子人的活动范围与箱子的活动范围。然后如果填了个空地，找到对应的影响了几个箱子就行了。

laizhufu

谢谢sokoban兄用大力神杯做为标准化处理的关卡，其实早就看到此贴，只是不知如何回复。
关卡从大力神杯变成大象再变成兔子，还是挺有趣，但一想到可爱的兔子终将变成石头，实在高兴不起来。
直至昨天龟兔赛跑，想起了这只兔子。一动一静，一快一慢，非常地合适。
用anian兄的话来说：兔子懒洋洋，拒绝移动， 龟虽然慢， 还是移动了下。

--------------------------####-------
--------------------------#--#-------
------------------------###--#-------
------------------------#---##-------
----------------------###--##--------
----------------------#---##---------
----------------------#--##----------
---------------------###--#----------
--------------------##----#########--
--------------------#--*#---#--#--###
--------------------#-*-*--*--*-***-#
--------------------#---*-*-*-*-*---#
--------------------##-*--*-*-*-***-#
---------------------#-*-**-*-*---*-#
---------------------##-*-*-*-*-**-##
----------------------#----*----####-
----------------------###########----
----------####-----------------------
----------#--#-----------------------
----------#.$#-----------------------
-----######--####--------------------
-----#-.$.$.$####--------------------
-----#$------.$-#--------------------
######.-**-**--.#--------------------
##-$-$-*--*--*-$#--------------------
##.-.-*-**-*-*-.#--------------------
####$-*-*--*-*-$####-----------------
---#.-*-*-**-*-.-.##-----------------
---#$-*-.$--*-$-$@##-----------------
---#.--**-**-.######-----------------
---#-$.------$#----------------------
---####$.$.$.-#----------------------
---####--######----------------------
------#$.#---------------------------
------#--#---------------------------
------####---------------------------

Title: 龟兔赛跑
Author: laizhufu




--------------------------####-------
--------------------------#--#-------
------------------------###--#-------
------------------------#---##-------
----------------------###--##--------
----------------------#---##---------
----------------------#--##----------
---------------------###--#----------
--------------------##----#########--
--------------------#-.*#---#--#--###
--------------------#-*-*-$*--*-.**-#
--------------------#---*-*-*-*-*---#
--------------------##-*--*-*-*-**$-#
---------------------#-*-**-*-*---*@#
---------------------##-*-*-*-*-**-##
----------------------#----*----####-
----------------------###########----
----------####-----------------------
----------#--#-----------------------
----------#*-#-----------------------
-----######--####--------------------
-----#-*-*-*-####--------------------
-----#-------*--#--------------------
######*-**-**--*#--------------------
##-----*--*--*--#--------------------
##*-*-*-**-*-*-*#--------------------
####--*-*--*-*--####-----------------
---#*-*-*-**-*-*-*##-----------------
---#--*--*--*-----##-----------------
---#*--**-**-*######-----------------
---#--*-------#----------------------
---####-*-*-*-#----------------------
---####--######----------------------
------#-*#---------------------------
------#--#---------------------------
------####---------------------------

Title: 《龟兔赛跑》
Author: laizhufu



（想想还是让兔子动起来，不过此时乌龟已到达终点。）