标准化
在关卡设计中, 有时会为了美观在原关卡基础上添加一些装饰性元素, 但这些装饰性的元素本质上并不会影响关卡的解法.
标准化的目的是移除这些与求解无关或冗余的元素.
理想情况下, 任何具有相同步数最优解的关卡都可以标准化为同一个关卡. 理论上, 可以先对关卡进行自动求解, 获得最优解决方案后, 再从解决方案构造关卡来得到标准化后的关卡.
然而, 对于 PSPACE-complete 的推箱子问题来说, 通过自动求解获得最优解决方案通常是耗时且困难的, 因此还需要一种不依赖于关卡解决方案的高效(多项式时间内得出结果)标准化方法. 尽管该方法得到的标准化结果并不完美.
关卡的标准化可以分为以下几个步骤:
-
将不可移动的箱子变为墙.
箱子可能默认就处于死锁状态, 可以将其视为墙体.
-
将无需使用的地板变为墙.
如果一个地板被三面墙包围, 属于死胡同, 可以将其视为墙体.
-
移除无法到达的墙.
部分墙无法与玩家产生交互, 因此移除这部分墙不影响关卡的解决方案.
-
统一外墙形式.
外墙有不同的包围类型, 如:
### #@$.# ### ##### #@$.# #####应该统一为其中一种类型, 通常使用下面的类型.
-
移除无法到达的箱子.
部分箱子无法与玩家产生交互, 因此移除这部分箱子不影响关卡的解决方案.
-
收紧地图尺寸.
地图中的元素被删除可能导致地图尺寸缩小.
-
对旋转和翻转标准化.
将经过不同旋转和翻转的关卡标准化为同一个关卡. 一个简单的方法是计算不同旋转和翻转后地图的哈希值，选择哈希值最小的版本.
-
玩家初始位置标准化. (注意: 可能移动玩家位置, 进而改变关卡的解决方案)
需要对先对玩家的位置进行标准化. 因为即使玩家位置不一样, 但都在同一个区域也可以转变为同一个关卡. 一个简单的玩家位置标准化方法是将玩家的位置设为玩家可达区域的位置中 Y 坐标最小, 其次 X 坐标最小的位置.
激进的标准化
激进的标准化可能改变关卡的解. 以最简单的关卡为例:
#####
#@$.#
#####
因为玩家开始的位置三面有墙, 位于死胡同, 只能向右移动. 得到结果:
#####
# @*#
#####
玩家左侧死胡同属于无用的区域, 使用墙体填充. 玩家右侧位于目标上的箱子处于死锁状态, 属于无用的箱子和目标, 使用墙体填充. 最后移除多余的墙体得到激进的标准化结果:
###
#@#
###
这是一个最简单的非标准关卡, 因为其没有箱子和目标, 解为空.