最佳路徑查找

Question

背景
有一個方形地圖上有一些障礙物。障礙由多邊形表示。我實現了以下路徑查找算法：
1）選擇精度（用k表示）
2）將圖分爲k×k個方塊。
3）根據以下規則從這些正方形制作圖表：
- 每個節點表示一個平方
- 當且僅當它們是相鄰的，其中沒有任何cosist障礙物兩個節點連接。
4）使用A *算法（或Dijkstra或其他一些...）尋找最短路徑

如果map不是動態的，這個算法效果很好。這意味着障礙不能移動。

問題
1）是否有效的方法？
2）如果障礙物可以移動怎麼辦？
3）如何處理其他代理？讓我們考慮房間裏有100個房客的情況。有兩個存在。所有代理都在一個組中，並且該組靠近其中一個出口。如果所有代理商都去了最近的出口，那麼它會造成瓶頸。其中一些應該去另一個出口，以儘量減少退出所需的時間。如何獲得這樣的結果？

Answer 1

使用A *路徑作爲靜態障礙物的一般指南，併爲動態（較小）障礙物執行本地Obstacle Avoidance。雷諾茲也有一個瓶頸問題的算法。他稱之爲Queueing。