半岛,半岛体育,半岛体育app,半岛官网,半岛电竞,半岛真人,半岛棋牌,半岛体育官网注册,半岛体育官方app下载,半岛体育app下载,半岛体育怎么样,半岛体育官网,半岛体育登录入口,半岛体育官方网站出于练习和探索的目的，我决定写一个简单的推箱子原型，然后写个算法来判定一个关卡是否可能通过。我将用 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。但是，如果系统中众多对象的状态没法完美地分离出来，成为一个低内存占用的对象，则不得不采用回滚来实现。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　上图是前置的用于表达坐标的二维整数矢量的 Hash，下图是 State 的 Hash

　　用了 3.0ms 左右，确实变得更快了。要进一步优化 C++ 版本，就交给那些算法竞赛高手吧，我已经很满意了。

　　这一次测试的主要是在单线程纯逻辑算法上的性能差异。以后我可能还会测试图形渲染、物理引擎（主要是碰撞检测）等方面的性能差异。但我应该也不会马上做这件事，而是打算先尝试制作游戏，实现一些自己的灵感，看看能不能搓点有意思的原型出来。毕竟我想做的不是算法，而是游戏，大概吧。

　　* 本文为用户投稿，不代表 indienova 观点。返回搜狐，查看更多