魔方吧·中文魔方俱乐部

标题: 关于程序对推箱子关卡的标准化处理 [打印本页]

---

作者: sokoban    时间: 2014-7-23 08:32:40     标题: 关于程序对推箱子关卡的标准化处理



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

如61期的大力神杯关卡：



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

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



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



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



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

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



附件: 屏幕快照 2014-07-23 上午8.28.28.png (2014-7-23 08:28:54, 6.15 KB) / 下载次数 129
http://www.mf8-china.com/forum.php?mod=attachment&aid=MjQwNDcyfDk0ZmU3OTc3fDE3NjI2MDIxNDB8MHww

附件: 屏幕快照 2014-07-23 上午8.25.26.png (2014-7-23 08:25:50, 7.06 KB) / 下载次数 136
http://www.mf8-china.com/forum.php?mod=attachment&aid=MjQwNDcxfDUxNDE3MGE0fDE3NjI2MDIxNDB8MHww

附件: 屏幕快照 2014-07-23 上午8.21.49.png (2014-7-23 08:22:16, 10.64 KB) / 下载次数 130
http://www.mf8-china.com/forum.php?mod=attachment&aid=MjQwNDcwfGU0NTY5NDQ1fDE3NjI2MDIxNDB8MHww

附件: 屏幕快照 2014-07-23 上午8.17.24.png (2014-7-23 08:17:54, 22.37 KB) / 下载次数 135
http://www.mf8-china.com/forum.php?mod=attachment&aid=MjQwNDY5fDdiODkxZDU0fDE3NjI2MDIxNDB8MHww

---

作者: 海上晴天    时间: 2014-7-23 09:39:28

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

---

作者: sokoban    时间: 2014-7-23 14:15:53

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

先大象，后兔子

---

作者: shamy    时间: 2014-7-23 19:49:07

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

---

作者: sokoban    时间: 2014-7-24 10:19:18

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

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

---

作者: anian    时间: 2014-7-25 07:48:49



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

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

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

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

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

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

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


[soko=9,8]
____HHHHH
___HH.$aH
__HH.$$HH
_HH.$$.H_
HH.$$.HH_
H.$$.HH__
HHH.HH___
__HHH____
[/soko]


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

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

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



附件: corridor.png (2014-7-25 07:48:15, 45.21 KB) / 下载次数 174
http://www.mf8-china.com/forum.php?mod=attachment&aid=MjQwNTE2fDljMmRkMzlhfDE3NjI2MDIxNDB8MHww

---

作者: anian    时间: 2014-7-25 08:04:36



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

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

基本上就是:

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

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

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

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

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

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

---

作者: sokoban    时间: 2014-7-25 20:32:05

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

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

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

---

作者: shamy    时间: 2014-7-29 09:11:53

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

---

作者: laizhufu    时间: 2015-4-17 11:51:51



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

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

Title: 龟兔赛跑
Author: laizhufu

[soko=37,36]
__________________________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___________________________
[/soko]


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

Title: 《龟兔赛跑》
Author: laizhufu

[soko=37,36]
__________________________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___________________________
[/soko]

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

---

作者: laizhufu    时间: 2015-4-17 17:34:43

很久没有来MF8，曾经热闹的MF8推箱子仅剩下比赛在更新。

前几天看到百度公告：百度空间迁入新家百度云
带着各种不舍，百度空间将于2015年5月7日正式迁移到百度云！此后，我们的记忆墙是这个样子的……

8年的百度空间说关闭就关闭了，曲散人终，忽然想来这里看看。有一天我们也会推不动箱子，那时我们的记忆墙又会是怎样？

附件: 百度空间迁入新家百度云.png (2015-4-17 17:35:15, 53.87 KB) / 下载次数 92
http://www.mf8-china.com/forum.php?mod=attachment&aid=MjUwMjQ1fDk0ZjhkMGM2fDE3NjI2MDIxNDB8MHww

---

作者: sokoban    时间: 2015-4-18 12:14:03

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

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

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

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

---

欢迎光临 魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/)

Powered by Discuz! X2