关于程序对推箱子关卡的标准化处理
本帖最后由 sokoban 于 2014-7-23 08:38 编辑推箱子关卡常常有很多纯装饰的墙体、箱子等等。
如61期的大力神杯关卡：
因此大部分推箱子程序的作者的原则似乎不对关卡做任何修改，也很少有提供对关卡标准化的相关功能（没有太充分调查研究，可能有程序有相应功能我不知道）。
一个最简单的处理就是处理内外的空位，外部空位（人无法移动到之处）变为透明色。
另外，对关卡进行进一步处理可以认为是一种辅助解关的手段，去掉无效元素可以避免注意力被分散。
为了这个目的，就可以进行把所有外部元素（人接触不到的元素）删去。于是得到下图：
从辅助解关的角度看，这个简化后，仍然有大量无效的格子。最简单的一种类型就是：人可以去到的，但是有三面是墙体的空位。
可以把这类空位全部变墙，一个空位变墙，就可能导致第二个空位变墙。可以递归的完成变墙的过程。结果是下图：
仅凭三面是墙这个条件，依然有无效空位没有删去。
其他的一些辅助简化的情况还有：四个箱子在目标位置，并且成田字形，等等。还有很多情况，要一一列举出来，都实现到程序中进行辅助性关卡简化、标准化，并不是太容易。
大力神杯简化成了兔子 好玩
为了2014几个字还多了不少不用推的箱子 海上晴天 发表于 2014-7-23 09:39 static/image/common/back.gif
大力神杯简化成了兔子 好玩
为了2014几个字还多了不少不用推的箱子
先大象，后兔子 ;P 这个话题有意思。
我想的是这样，除了标准整理墙壁外，还有需要判断所有箱子的活动范围，而且是不能死锁的活动范围，然后判断人的活动范围，如果某个地方人能到达，但是四周不存在箱子的活动范围，就可以变成墙。计算量有点大。
箱子已经推死的话，可以变成墙，但是这个涉及到解关死锁判断了。
shamy 发表于 2014-7-23 19:49 static/image/common/back.gif
这个话题有意思。
我想的是这样，除了标准整理墙壁外，还有需要判断所有箱子的活动范围，而且是不能死锁的 ...
这个问题的确不简单，所以发个帖子向大家学习一下。 本帖最后由 anian 于 2015-7-28 09:19 编辑
将关卡尽量变小删除没有用的空间， 这个问题很早以前和歪推作者George讨论过。
因为已经是很久以前的事， 详细的讨论已经忘记了。
找EMAIL也是不容易。
记得的资料应该不齐全， 有以下这些...
每次一个关卡过关了， 歪推是保存这个关卡的答案。
它保存的关卡就是经过删除某些没有用的多余的空间才保存的。
除了正常的删除“人无法去的地方”， 它也是删除dead end tunnel (死胡同)。
这个就是版主说的三面是墙壁(而且空间不是目标点)。
还有的是， 如果开始人一定需要推动箱子， 没有其它选择的，
它也是删除这些空间 (当然， 箱子被推了后如果再也无法动的， 也是变了墙壁)。
如下面这个关卡：
----#####
---##.$@#
--##.$$##
-##.$$.#-
##.$$.##-
#.$$.##--
###.##---
--###----
____HHHHH
___HH.$aH
__HH.$$HH
_HH.$$.H_
HH.$$.HH_
H.$$.HH__
HHH.HH___
__HHH____
你放入歪推就看到它是自动认识关卡和答案。
这个答案其实是删除关卡的过程中得到的。
这个关卡经过“优化”后剩下的就只得人和四面是墙壁。
歪推对关卡的优化未必每个人都是接受。
除了无法推动的箱子(已经在目标点)， 作者也是曾经说过这个情况下， 通道里面
的多余空间(上面两个)可以删除：
本帖最后由 anian 于 2014-7-25 08:05 编辑
>>> 除了标准整理墙壁外，还有需要判断所有箱子的活动范围，而且是不能死锁的活动范围，然后判断人的活动范围，如果某个地方人能到达，但是四周不存在箱子的活动范围，就可以变成墙。计算量有点大。
这和我的想法类似。(或者完全相同)
昨天和版主说过类似的计算。
基本上就是:
(开始整个关卡没有做标记)
(1) 关卡里面选择一个没有做标记的箱子。 (暂时将关卡里面的其它箱子全部变成空)
(2) 计算这个箱子可以推到的全部地方(和人必须要走过的最短的路去推这个箱子)
(3) 这些空间全部记下来 (做标记)
(4) 重复 1， 2， 3 直到全部箱子已经做了标记。
完成后， 就标记了全部箱子可以推到的地方(和人必需要到的空间去推这些箱子)。
没有做标记的空间， 全部可以变成为墙壁。
计算箱子可以推到的全部地方有点复杂。
如果关卡大和没有好的计算方法， 会很慢。
幸好之前版主已经解决了这个计算问题， 现在计算箱子可以推到的地方可以很快的就计算好。
虽然是复杂了点， 但还是可以很快就做到。 anian 发表于 2014-7-25 08:04 static/image/common/back.gif
>>> 除了标准整理墙壁外，还有需要判断所有箱子的活动范围，而且是不能死锁的活动范围，然后判断人的活动范 ...
判断箱子能被推到的地方，我想这个没有任何问题。
问题是如何确定哪些是为了推箱子而必须用到的地方（这些地方比箱子能推到的地方要多一些）？如何判断真正无用的格子（箱子推不到，人也不需进去）？我觉得这里面可能有些复杂情况。一时没有想出很好的例子。再琢磨琢磨。 感觉上，需要找的就是“填个墙，与不填墙，不能影响箱子移动的路径”的地方，所以，如果要是填了一个墙以后，要从头找一下所有箱子，是否受到了影响。这个重复计算的太多了。除非分清每一个箱子人的活动范围与箱子的活动范围。然后如果填了个空地，找到对应的影响了几个箱子就行了。 本帖最后由 laizhufu 于 2015-4-17 12:04 编辑
谢谢sokoban兄用大力神杯做为标准化处理的关卡，其实早就看到此贴，只是不知如何回复。
关卡从大力神杯变成大象再变成兔子，还是挺有趣，但一想到可爱的兔子终将变成石头，实在高兴不起来。
直至昨天龟兔赛跑，想起了这只兔子。一动一静，一快一慢，非常地合适。
用anian兄的话来说：兔子懒洋洋，拒绝移动， 龟虽然慢， 还是移动了下。
--------------------------####-------
--------------------------#--#-------
------------------------###--#-------
------------------------#---##-------
----------------------###--##--------
----------------------#---##---------
----------------------#--##----------
---------------------###--#----------
--------------------##----#########--
--------------------#--*#---#--#--###
--------------------#-*-*--*--*-***-#
--------------------#---*-*-*-*-*---#
--------------------##-*--*-*-*-***-#
---------------------#-*-**-*-*---*-#
---------------------##-*-*-*-*-**-##
----------------------#----*----####-
----------------------###########----
----------####-----------------------
----------#--#-----------------------
----------#.$#-----------------------
-----######--####--------------------
-----#-.$.$.$####--------------------
-----#$------.$-#--------------------
######.-**-**--.#--------------------
##-$-$-*--*--*-$#--------------------
##.-.-*-**-*-*-.#--------------------
####$-*-*--*-*-$####-----------------
---#.-*-*-**-*-.-.##-----------------
---#$-*-.$--*-$-$@##-----------------
---#.--**-**-.######-----------------
---#-$.------$#----------------------
---####$.$.$.-#----------------------
---####--######----------------------
------#$.#---------------------------
------#--#---------------------------
------####---------------------------
Title: 龟兔赛跑
Author: laizhufu
__________________________HHHH_______
__________________________H__H_______
________________________HHH__H_______
________________________H___HH_______
______________________HHH__HH________
______________________H___HH_________
______________________H__HH__________
_____________________HHH__H__________
____________________HH____HHHHHHHHH__
____________________H__*H___H__H__HHH
____________________H_*_*__*__*_***_H
____________________H___*_*_*_*_*___H
____________________HH_*__*_*_*_***_H
_____________________H_*_**_*_*___*_H
_____________________HH_*_*_*_*_**_HH
______________________H____*____HHHH_
______________________HHHHHHHHHHH____
__________HHHH_______________________
__________H__H_______________________
__________H.$H_______________________
_____HHHHHH__HHHH____________________
_____H_.$.$.$HHHH____________________
_____H$______.$_H____________________
HHHHHH._**_**__.H____________________
HH_$_$_*__*__*_$H____________________
HH._._*_**_*_*_.H____________________
HHHH$_*_*__*_*_$HHHH_________________
___H._*_*_**_*_._.HH_________________
___H$_*_.$__*_$_$aHH_________________
___H.__**_**_.HHHHHH_________________
___H_$.______$H______________________
___HHHH$.$.$._H______________________
___HHHH__HHHHHH______________________
______H$.H___________________________
______H__H___________________________
______HHHH___________________________
--------------------------####-------
--------------------------#--#-------
------------------------###--#-------
------------------------#---##-------
----------------------###--##--------
----------------------#---##---------
----------------------#--##----------
---------------------###--#----------
--------------------##----#########--
--------------------#-.*#---#--#--###
--------------------#-*-*-$*--*-.**-#
--------------------#---*-*-*-*-*---#
--------------------##-*--*-*-*-**$-#
---------------------#-*-**-*-*---*@#
---------------------##-*-*-*-*-**-##
----------------------#----*----####-
----------------------###########----
----------####-----------------------
----------#--#-----------------------
----------#*-#-----------------------
-----######--####--------------------
-----#-*-*-*-####--------------------
-----#-------*--#--------------------
######*-**-**--*#--------------------
##-----*--*--*--#--------------------
##*-*-*-**-*-*-*#--------------------
####--*-*--*-*--####-----------------
---#*-*-*-**-*-*-*##-----------------
---#--*--*--*-----##-----------------
---#*--**-**-*######-----------------
---#--*-------#----------------------
---####-*-*-*-#----------------------
---####--######----------------------
------#-*#---------------------------
------#--#---------------------------
------####---------------------------
Title: 《龟兔赛跑》
Author: laizhufu
__________________________HHHH_______
__________________________H__H_______
________________________HHH__H_______
________________________H___HH_______
______________________HHH__HH________
______________________H___HH_________
______________________H__HH__________
_____________________HHH__H__________
____________________HH____HHHHHHHHH__
____________________H_.*H___H__H__HHH
____________________H_*_*_$*__*_.**_H
____________________H___*_*_*_*_*___H
____________________HH_*__*_*_*_**$_H
_____________________H_*_**_*_*___*aH
_____________________HH_*_*_*_*_**_HH
______________________H____*____HHHH_
______________________HHHHHHHHHHH____
__________HHHH_______________________
__________H__H_______________________
__________H*_H_______________________
_____HHHHHH__HHHH____________________
_____H_*_*_*_HHHH____________________
_____H_______*__H____________________
HHHHHH*_**_**__*H____________________
HH_____*__*__*__H____________________
HH*_*_*_**_*_*_*H____________________
HHHH__*_*__*_*__HHHH_________________
___H*_*_*_**_*_*_*HH_________________
___H__*__*__*_____HH_________________
___H*__**_**_*HHHHHH_________________
___H__*_______H______________________
___HHHH_*_*_*_H______________________
___HHHH__HHHHHH______________________
______H_*H___________________________
______H__H___________________________
______HHHH___________________________
（想想还是让兔子动起来，不过此时乌龟已到达终点。）
页:
[1]
2