map - 最佳寻路

Question

背景
有一张方形 map ，上面有一些障碍物。障碍物由多边形表示。我实现了以下寻路算法:
1)选择精度(用k表示)
2) 将 map 分成k x k个方 block 。
3) 根据以下规则从这些正方形中绘制图形:
- 每个节点代表一个正方形
- 两个节点连接当且仅当它们相邻并且没有任何障碍。
4) 使用 A* 算法(或 Dijkstra 或其他...)找到最短路径

如果 map 不是动态的，这个算法会工作得很好。这意味着障碍物无法移动。

问题
1) 这种方法有效吗？
2)障碍物可以移动怎么办？
3) 如何治疗其他药物？让我们考虑房间里有 100 个代理的情况。有两个存在。所有特工都在一组中，并且该组靠近其中一个导出。如果所有代理都去最近的导出，那么它会造成瓶颈。他们中的一些人应该去另一个导出，以尽量减少离开所需的时间。如何得到这样的结果？

Answer 1

使用 A* 路径作为围绕静态障碍物的一般指南并执行本地 Obstacle Avoidance对于动态(较小)障碍。 Reynolds 也有一个解决瓶颈问题的算法。他称之为Queueing .