基本上，“规则 + 限制”就有可能陷入锁死，寻路是一种规则，碰撞则是是一种限制。有时候，特殊的场景和恰好的时序会导致系统到达一个稳定的状态而无法继续。看上去可能比较难这么巧合，但是实际上这几乎是必然的，因为稳定状态随着限制增多（比如地方狭小之处，又或是存在大量人物），而系统一旦到了稳定状态就会停滞不前。所以规则中必须有一种可靠的打破平衡的方法。
一个比较简单的思路正如论坛上有人提到的，参考 ethernet 的数据发送碰撞检测退让算法 CDMA/CD（每次冲突退让 random(min(2^n, LIMIT)) 个时间片，n 为冲突次数，LIMIT 为最大退让时间，如果 n 到达最大值则丢弃数据）。这个方法容易想到，但是实际上并不是那么有效，因为：
1. 以太网在发送数据节点较多、通讯负载高的网络下效率会下降，而且随着负载高下降得很快。根据经验，
传统的以太网带宽利用率是 1/e，大概是 30% 左右，也就是说 10M 的以太网在在负荷较高时只能维持 3M 左右的通讯数据带宽。（现代普遍采用的是交换式的网络了，可以大量减少冲突，才能保证 1G 以上的应用）
2. 以太网的表现是机器越少，通讯越少越实用反之则不实用。而我们的目标是在高负载的时候还能够继续的工作而不陷入一种稳定状态，随机退让的思路刚好不符合我们的要求。
举一个具体的例子：
------------------
XXXYYY
XXXYYY
------------------
如果 X 往右，Y 往左，那么显然的，不论 X、Y 怎么退让（等待一段时间寻路），那么这个系统都是不会脱离稳定状态的。
关于打破平衡的方法很多，这些都和具体的情况有关，如果我们考虑的是游戏中的自动寻路，那么我们可以借鉴一下真实世界的方法：
如果很多人在一个拥挤的空间朝各个方向前进，那么可以想象的是，这些人会陷入混乱，甚至会导致悲剧发生（比如球场骚乱导致践踏事件，实际上，大家争先恐后的脱离危险地区的方法效率是不高的，所以才导致了更多的人遭到不幸）。真实世界真正能够有效的维持交通秩序，是因为大家有一套限制比较严格的规则，避免出现这种情况发生。比如，靠右行走；排成纵队而非横列。如果你试图建立一个这样的系统，大家随意行走，只遵守物理规则（不能飞，不能穿透），遇到瓶颈自动恢复，基本上这是无解的。
所以，综合上面分析的结果，如果你期望游戏中 AI 看起来不那么傻，那么就需要从以下几个方面完善你的寻路算法：
1. 一个区域内，如果寻路人员的空间密度小于一定数值，自由寻路。
2. 如果密度较高，则靠右行走，限制队列宽度。
那么这时，问题的关键就在于第二点如何实现，如果采用的是 A* 类的算法，那么我们可以简单的在地图上做一些标记来辅助我们解决这些问题，例如：
---------------------
RRRRRRRRRRRRRRRRRRRRR
SSSSSSSSSSSSSSSSSSSSS
TTTTTTTTTTTTTTTTTTTTT
UUUUUUUUUUUUUUUUUUUUU
---------------------
R、S、T、U 表示不同的四元组：
R - (1, 10, -, 3)
S - (1, 10, 3, 12)
T - (10, 1, 12, 3)
U - (10, 1, 3, -)
四元组的含义是，（向左走开销，向右走开销，向上走开销，向下走开销，-表示不可能），这样，我们寻路时，根据寻路的下一步方向，可以估算一个符合我们期望的开销成本，促使选择一条靠右走，宽度为 2 的道路。在较为拥堵的时候，禁止选择走 > 10 的节点，如果寻路失败，则原地等待一段时间。这样，发生完全堵死的情况就很不容易了（实际设计算法中，还需要考虑一些更复杂的具体情况）。
最后，我们是否需要在所有场景一点一点的去描述这个四元组？这是不必要的，除非非常特殊的地图，可能需要人为的设置（好像划分单行线一样），一般来说，这些数据可以由程序根据我们的规则自动预先生成。
没有评论:
发表评论