如何爲pacman創建路徑追蹤算法？

Question

我是一名正在製作Pacman風格的gridworld遊戲的高中生。正如你知道的那樣，pacman有幽靈跟隨pacman並且試着去找他。但是，我無法創建一個搜索Pacman對象的最快路徑的algortihm，然後採用該路線。我在網上閱讀過一些博客，但我沒有發現任何有用的東西。你們有什麼想法讓鬼魂跟蹤包裝工？

Answer 1

您可以嘗試A *算法，as described here。

最終你會注意到幽靈會採用大多數相同的路線。查看AI遊戲編程智慧叢書獲取大量有用的信息。

Answer 2

啊...... Gridworld，我記得就像昨天一樣。來想一想，這是......：|

無論如何，我能想到的唯一的事情就是創建一個Pacman所有移動的ArrayList，將其傳遞給鬼，計算出到達列表中某個空格的最快路徑，然後跟隨Pacman一起。

希望我能提供更多幫助，但這就是我現在能想到的。

Answer 3

這裏提供一個完整的答案有點複雜......但看看'反對象'。 Alexander Repenning（科羅拉多大學）有一篇論文。這種非OOP建模將pac-man的位置視爲通常被描述爲類似於氣味的東西。

Answer 4

要找到我會建議實施類似的Dijkstra算法或Floyd的算法最短成本路徑（它的好處是積極的成本邊緣！）

http://en.wikipedia.org/wiki/Dijkstra「s_algorithm http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm