死锁
什么是死锁
推箱子的通关条件是箱子和目标位置一一对应. 但在一些情况下, 箱子永远不能被推到目标上, 推箱子通关条件永远无法达成.
为什么要检测死锁
死锁产生后, 该状态及其衍生状态一定无解, 但依然可以控制玩家继续推动其他可推动的箱子, 因此求解器将继续浪费大量的资源去搜索一定无解的状态. 因此需要有检测死锁产生的方法, 来跳过不必要的搜索.
何时检测死锁
死锁按照箱子和玩家位置的关系可以分为三类:
- 与箱子和玩家位置无关的.
- 与箱子位置有关和玩家位置无关的.
- 与箱子和玩家位置有关的.
第 1 类为静态死锁, 因为其与箱子和玩家的位置均无关, 可以在只知道关卡地形和目标位置的情况下进行计算, 而目标位置是静态的.
这类死锁可以在关卡地形变化时计算.
当箱子被推到目标后死锁了, 此时可以将死锁的箱子视为不可移动的墙, 关卡地形发生变化, 需要重新计算.
第 2 类为冻结死锁(freeze deadlocks), 这类死锁产生的原因是箱子之间的相互阻碍导致多个箱子同时死锁.
这类死锁的检测时机是箱子推动后.
第 3 类包括畜栏死锁(corral deadlocks)/闭对角死锁(closed diagonal deadlocks). 这类死锁和冻结死锁的区别是前者只要在箱子推动后变成了一定的模式就会产生, 而后者是否产生死锁还需要看玩家在箱子推动后的位置, 即箱子推动方向.
畜栏死锁是一种更为高级的冻结死锁, 因为即使在畜栏死锁后, 箱子仍然可以被推动, 但最终一定会形成冻结死锁.
畜栏死锁的检测时机是箱子推动后, 有玩家不可达的区域面积减小. 这意味着玩家可能无法再回到该不可达区域, 导致区域周边的箱子的移动自由度减少.