最佳路径查找

Question

背景
有一个方形地图上有一些障碍物。障碍由多边形表示。我实现了以下路径查找算法：
1）选择精度（用k表示）
2）将图分为k×k个方块。
3）根据以下规则从这些正方形制作图表：
- 每个节点表示一个平方
- 当且仅当它们是相邻的，其中没有任何cosist障碍物两个节点连接。
4）使用A *算法（或Dijkstra或其他一些...）寻找最短路径

如果map不是动态的，这个算法效果很好。这意味着障碍不能移动。

问题
1）是否有效的方法？
2）如果障碍物可以移动怎么办？
3）如何处理其他代理？让我们考虑房间里有100个房客的情况。有两个存在。所有代理都在一个组中，并且该组靠近其中一个出口。如果所有代理商都去了最近的出口，那么它会造成瓶颈。其中一些应该去另一个出口，以尽量减少退出所需的时间。如何获得这样的结果？

Answer 1

使用A *路径作为静态障碍物的一般指南，并为动态（较小）障碍物执行本地Obstacle Avoidance。雷诺兹也有一个瓶颈问题的算法。他称之为Queueing。