Skip to main content

推箱子死锁检测问题随想

· 8 min read
Life_Checkpoint
Life_Checkpoint
SUSTech

推箱子的死锁检测是一个复杂的问题，有专门的研究对该问题进行优化。

现代推箱子教程 - 死锁 DeadLock 给出了死锁的一般定义

Tristan Cazenave 与 Nicolas Jouandeau 的 Towards deadlock free Sokoban 给出了检测死锁的高效树算法（然而实现算法很困难）

死锁的类型非常多，增加了死锁的复杂性

死锁检测的目的？​

死锁检测可以用于早停，例如

  1. 玩家的失败提示
  2. Sokoban AI 搜索算法迭代的剪枝，减小搜索空间与分支常数

但是死锁不一定代表失败，在某些创新玩法中，某些死锁反而可能是胜利的必要条件

由于时间原因，这里仅采取一些常见情况的检测，能够做到初步的死锁检查

本质上是匹配人工建立的模式数据库

初步死锁检测​

初步的死锁有以下几种：

  1. 角落死锁
  2. 胡同死锁
  3. 单侧死锁

每种死锁都有不一样的适用条件

角落死锁​

角落死锁指的是一个箱子被推到了两、三或四面垂直墙壁的夹角处，且所在位置没有目标点

######        ###    ###
#   $#    #####$#    #$#
#.   #    #     #    ###
######    #######

这是一种绝对死锁，判断较为简单，直接判定箱子是否存在任意相邻两侧墙壁即可

胡同死锁​

胡同死锁指的是一个箱子被推到了死胡同中，胡同中没有目标点，并且绝对不存在走出胡同的方法

最简单的死胡同如下：

   ###
   # #
   # #
   # #
####$####
# @    .#
#########

这个死胡同的特点是：玩家与死胡同的另一部分不连通，从玩家连通块开始，箱子只有一个方向可以行进，且这个方向最后会进入角落死锁

注意，有一些胡同并不是死胡同，例如

######
#    #
#    #
#    #
#### #
   # #
####$####
# @   . #
#########

为什么不会产生死锁呢？因为在箱子移动到角落产生绝对死锁之前，玩家与胡同的另一部分发生了连通，由此破坏了胡同死锁的产生条件

因此在进行胡同死锁的检测的时候，应该遵循以下方法

  1. 如果判定到箱子被两侧平行墙壁夹住
  2. 对箱子进行当前玩家连通方向的虚拟推动
  3. 检测是否产生...
    1. 角落死锁: 判定为绝对死锁
    2. 玩家块与胡同块发生连通: 不可判定为死锁
    3. 以上条件均不满足：继续进行虚拟推动

后面发现这个逻辑有一些 cases 无法通过，例如

   #####
####   #
#  # # #
#    $ #
#.#### #
######$##
# @   . #
#########

确实不是连通块，但胡同口的箱子也不是死锁状态

解决方法是，判断连通块时，将箱子视为空气，这样至多会漏判，但绝不会错判

单侧死锁​

单侧死锁指的是一个箱子被推到了单侧墙壁，但是墙壁一侧没有任何目标点且箱子无法逃出单侧墙壁

例如

#####
#   #
#  $#
#.  #
#####

同样需要指出的是，箱子移动到了单侧墙壁并不代表箱子发生了单侧死锁，因为箱子是有机会逃出单侧墙壁的

####
#  #
# $#
#  #######
#@      .#
##########

然而我们也不能简单的认为箱子能移动到空地就是死锁不成立，比如

####
#  ###
#    #
#  ###
# $#
#  #######
#@      .#
##########

如果向上移动，虽然会出现四周无墙壁的情况，但如果内部是一个死胡同，情况就会转化为胡同死锁

因此，可以用如下算法检测单侧死锁：

  1. 如果箱子被移动到单侧墙壁
  2. 沿箱子两侧对箱子分别进行虚拟移动
  3. 如果箱子进入角落死锁，判定为单侧死锁
  4. 如果箱子进入四周空地的格子...
    1. 检查当前玩家块是否与能够将箱子垂直推离墙壁的块连通，如果连通，单侧死锁不成立
    2. 如果不连通...
      1. 将箱子沿墙壁方向继续移动，重复 2 3 4 步
      2. 将箱子向胡同内推入，检测胡同死锁
      3. 如果以上两个结果中有任意一个使死锁不成立，则认为单侧死锁不成立

其它说明​

以上死锁算法都通过递归或循环实现，需要指出的是，这些算法编写简单，但效率不高，所以出现了如下优化算法：

  1. 静态优化: 将进入某些特定死锁状态的箱子视为墙，懒惰更新一定会发生死锁的位置
  2. 树优化：将箱子首次进入死锁的状态作为死锁树的根节点，通过拓展树节点高效获取死锁位置

当然，也有暴力出奇迹的通用算法：

  1. BFS & DFS & Beam Search 等传统搜索
  2. A* IDA* 双向搜索 等启发式搜索

在不循环的前提下，暴力寻找所有可能的箱子移动空间，如果检测到箱子不可能移动到任何目标点，则认为死锁成立

缺点：

  1. 传统搜索：巨慢，地图很大，情况复杂，跑完一个算法的时间可能要用亿年来计
  2. 启发式搜索：相对快，但是对于大的地图依然需要一些时间，大地图的实时判断需掂量

优化算法一般是是针对传统玩法开发的，如果需要通用性，可以做出针对性修改

如果感兴趣可以参阅更多资料