推箱子的通关判定算法

出于练习和探索的目的，我决定写一个简单的推箱子原型，然后写个算法来判定一个关卡是否可能通过。我将用 Python，Unity，C++ 分别跑一遍同一个算法，比对性能差异。

首先，我需要有一个关卡集。先使用最经典的推箱子规则：箱子和目标位置数量一致，玩家没有目标位置，不能推动两个箱子（之后可能会引入其他规则版本，所以规则这一块先模块化）。我从 Caribou Contests 上薅了五关，这几关的箱子数量在 2 至 4 不等，应该能满足性能测试的需求。

接下来，我需要写一个可玩原型，并写个算法来测试关卡能否通过（先声明，我并非 OIer ，甚至不是计算机相关专业背景，所以算法方面可能会有点唐。）

红色是玩家，绿色是箱子，蓝色是目标位置

推箱子是一个有限状态机，可以用玩家和箱子的坐标来表示全部状态。我使用固定大小的 Numpy 数组来表示状态，比如上面这个关卡中，玩家的坐标是 [4, 5] ，三个箱子的坐标是 [1, 3]、[1, 5]、[3, 4]，那么状态是 np.array([[4, 5], [1, 3], [1, 5], [3, 4]]) ，其中第一行为玩家，后几行顺序随意。

我希望把这个状态表达为一个在内存空间中较为紧凑的对象，因为这样可以很容易地实现无限次按 Z 撤销，而且不容易出 Bug 。另一种实现撤销功能的方式是记录所有变化，然后撤销时依次回滚这些变化。后者实现起来更复杂且鲁棒性更差，容易在加入新功能后出 Bug。但是，如果系统中众多对象的状态没法完美地分离出来，成为一个低内存占用的对象，则不得不采用回滚来实现。

在此基础上，用一个 BFS 寻找在一定步数内能达到的状态，直到这些状态中出现通关条件。我使用一个巨大的布尔型 Numpy 数组来记录状态是否被访问。如上面这关中，地图为 5*7 ，玩家和箱子一共 4 个坐标，所以数组大小为 (5*7)^4=1500625）。跑一下：

通过上面这个关卡最少需要 73 步，我的程序用了 2745 毫秒。

做一些优化，比如用 Numpy 的遍历代替 for 循环：

被注释掉的代码是优化前的

可以看到，比之前变快了一点。然后让 AI 帮我做一些优化，结果：

变得超快，把我的代码爆杀了！让我研究一下它为什么更好。

1. 采用 Python 原生的 tuple 和 frozenset 来表达状态。我的表达是 np.array([[4, 5], [1, 3], [1, 5], [3, 4]])，而它的表达是 ((4, 5), frozenset(((1, 3), (1, 5), (3, 4)))) 。

2. BFS 时，不再用一个巨大的数组来记录访问状态，而是直接将已经访问过的状态放入一个 Set 。我本来也想这么做，但 Numpy 数组不可 Hash，遂作罢。

这样做可能的好处：

1. frozenset 是无序的，所以箱子顺序不同的状态被看作同一种状态。这实际上是我的失误，本来就是同一种状态，而我没有在代码中体现这一点，导致需要遍历的节点数目（大致）变成了箱子数目的阶乘倍（然而，我尝试补充写了「每次访问前，查询等价的其它状态表达是否已访问」和「每次访问后，将等价的其它状态都更新为已访问」，结果发现，无论哪种写法都导致代码跑得更慢了）。

2. 我用于记录访问状态的数组太巨大了，在这个例子里，直接占用了 5.7MB 内存。假设一个内存分页是 4KB，这相当于横跨了一千多个内存分页，而访问是近乎随机的，于是缓存命中率直接消失了。虽说 Set 和数组的读写，理论上都是 O(1)，但这个数组的常数实在太差，而由于实际能走到的空间比存在的整个状态空间小很多，所以 Set 的空间并不大，从而常数小很多。

3. tuple 和 frozenset 是 Python 内置的，可能本身性能会更好？这个我不确定，不是特别懂 Python 。

如果只是要找到能否通关，而不考虑步数，我们还可以进一步优化。先设定玩家的移动不消耗步数，只有推箱操作消耗步数。从而，在某个状态下，我们进行一次小的搜索，计算玩家下一次推箱操作有哪些可能性，然后直接计算这些状态作为下一步状态，这样可以避免遍历那些玩家只是走来走去但不推箱子的垃圾状态。依此优化后（从现在开始，我只提思路，具体实现都让 AI 来写）：

可以看到，玩家至少需要推动箱子 15 次，才能通过这关。值得一提的是，算法没有保证这个 15 次推动的解和之前 73 次操作的解是同一种，尽管在这个例子里经我测试其实是同一种。

而如果我们做一些调整，就可以用这种新算法重新找到最小通关步数。我们在搜索玩家下一步推箱可能性时采用 BFS，即可得到到达每种推箱可能性需要移动的步数，从而把问题转化为一个最短路径问题，用 Dijkstra 算法解决即可。于是：

我们在 Python 上的优化就做到这里。这相比于最开始的方案已经优化了两个量级，还是得多做优化才行。

推箱子的状态数目随着箱子的数量指数提升（据维基百科，推箱子是 NP 困难的），所以我们再看下两个箱子和四个箱子的关卡用时。

两个箱子：

四个箱子：

至此，我们用 Python 跑通了推箱子的原型和算法，接下来，用 Unity 和 C++ 也实现同样的原型和算法，比较一下各个框架的性能差异。

由于我的设备上经常会同时跑一些不同的东西，所以留给程序的性能会有波动，首先重新测一下 Python 版本的性能：

73 步，用了 26ms 左右，和之前的测试结果差不多。

现在，我们分别用 Unity 和 C++ 实现。因为是平台搬迁的重复性工作，所以基本完全交给 AI 完成。

首先是 Unity 版本的实现：

用了 24ms 左右，比 Python 版本快一点点，如果再做一些写法优化可能还会更快。Unity 引擎本身只做了渲染工作，算法求解完全是由 C# 本身的逻辑完成的，考验的是 C# 的性能。C# 要是做不到比 Python 更快，也是丢光了编译语言的脸。

Unity 自带对 Vector2Int 的 GetHashCode 方法，但是不像 Python 可以将多个箱子矢量组合成 frozenset，再与玩家矢量合并为 tuple，并使用内置 Hash 作为系统状态的 Hash 值，而是必须自己写。我们看看 AI 是怎么写系统状态的 GetHashCode 的：

这个写法还不错，因为它保证了箱子交换顺序后，Hash 不变。但也有一个不那么好的地方，就是玩家和箱子交换位置后，Hash 也不变，但这其实是不同的状态，可能会导致碰撞。我们做一点修改：

这样处理，玩家和箱子交换后 Hash 就不同了。测试一下：

用了 20ms 左右，快了一点点。看来我还是能给 AI 打打下手的。

U nity 版本就优化到这里吧。现在我们来看 C++ 版本的实现：

用了 4.2ms 左右，C++ 的性能还是高出太多。

看看 AI 是怎么写的。它使用了 std::map 来记录节点访问状态，而不是像 Python 版本和 Unity 版本那样使用 Hash table。

由于箱子应当是无序的，所以给状态类加了一个正则化方法，在作为键插入 std::map 前对状态中的箱子做字典排序，保证 std::map 中不会插入等价的两个状态。

std::map 的实现是红黑树，插入和查询是 O(log n) 的，使用 Hash table 可能会更快。我们希望改为 std::unordered_map（它的实现是 Hash table），它要求对于键的类型 T 存在模板类 std::hash<T>，所以需要给 State 加上 Hash 模板特化：