我正在嘗試爲iPhone創建一個Pacman AI，而不是Ghost AI，但是Pacman本人。我使用A *進行尋路，並且我有一個非常簡單的應用程序啓動並運行，它可以計算遊戲板上兩塊瓷磚之間的最短路徑，以避免牆壁。iPhone尋路實現
所以運行1函數來計算2點之間的路徑很容易。一旦函數到達goalNode，我就可以通過每個tile的parentNode屬性向後遍歷路徑，並創建所需的動畫。但在實際的遊戲中，國家正在不斷變化，因此路徑和動畫也將不得不如此。我是遊戲編程的新手，所以我不確定實現這一點的最佳方式。
我應該創建一個NSOperation，它在後臺運行，並且不斷計算goalNode以及給出當前遊戲狀態的最佳路徑？此線程還必須在某些點通知主線程並提供信息。問題是什麼？
我應該在什麼時候通知主線程？
我應該通過哪些數據通知主線程？
......還是我一起走了？
任何指導，非常感謝。
有點無關，但你見過ASIPathFinder framework？如果您有更高級的尋路需求，可以提供幫助。
我對pacman AI的建議是，您使用洪水填充算法來計算網格上每個瓦片的最短路徑和總距離。這是一個比A *更簡單的算法，實際上比A *有更好的最壞情況，這意味着如果你能負擔得起A *每一幀，你可以承受洪水填充。
爲了更詳細地解釋性能比較，可以想象A *中的最壞情況：由於死路一條，你最終必須在到達最終目的地之前探索網格上的每個瓦片。如果你在董事會中有很多死角，這個理論上的情況是可能的，但在大多數現實世界的pacman董事會中不太可能。洪水填充的最壞情況與最好的情況相同，您只需訪問一次地圖上的每個瓦片。不同之處在於迭代步驟對於填充填充比對於A *迭代更簡單（沒有啓發式，沒有節點堆等），所以訪問每個節點的填充填充比使用A *更快。
實現非常簡單。如果將網格想象爲一個圖形，每個圖塊都是一個節點，並且每個邊緣在相鄰圖塊之間沒有作爲圖形邊緣的邊框，那麼只需對圖形進行寬度優先遍歷，以便跟蹤您到達的節點從你探索過的節點到達那裏。您在訪問節點時將節點標記爲已訪問，並且永遠不會訪問節點兩次。
下面是一些僞代碼，讓你開始：
openlist = [ start_node ]
do
node = openlist.remove_first()
for each edge in node.edges
child = node.follow_edge(edge)
if not child.has_been_visited
child.has_been_visited = true
child.cost = node.cost + 1
child.previous = node
openlist.add(child)
while openlist is not empty
要弄清楚如何讓吃豆子移動到某處，你就開始你想要的節點，並按照既往指針一路回開始，然後顛倒列表。
這樣做的好處在於，您可以對地圖上的任何圖塊的費用進行常量時間查詢。例如，您可以遍歷每個功率顆粒並計算哪一個最接近，以及如何到達那裏。
你甚至可以用它來讓鬼魂知道當他們處於「攻擊」模式時回到pacman的最快方式！
你也可以考慮從每個鬼魂的洪水填充，在每個瓦片存儲最近的鬼魂是多遠。您可以限制探索的最大距離，而不是將節點添加到打開列表中，如果它們大於某些最大成本（8平方？）。然後，如果你以後做了A *，那麼你可以根據鬼魂的距離來估計每個瓷磚的成本。但是這超出了你在問題中提出的要求。
它應該是足夠快，你可以做到內聯每一幀，或多線程，如果你願意。爲了簡單起見，我建議你只是在你的主遊戲模擬線程（注意，不是UI線程）中執行它，因爲在完成所有工作時它確實應該非常快。
一個性能提示：不是每個幀都要通過並清除「has_been_visited」標誌，只需要一個搜索計數器即可增加每個幀。像這樣的東西：
openlist = [ start_node ]
do
node = openlist.remove_first()
for each edge in node.edges
child = node.follow_edge(edge)
if child.last_search_visit != FRAME_NUMBER
child.last_search_visit = FRAME_NUMBER
child.cost = node.cost + 1
child.previous = node
openlist.add(child)
while openlist is not empty
然後你只是增加FRAME_NUMBER每幀。
祝你好運！
我應該很快提到，如果您決定稍後添加某種成本偏差，其中每個邊的「成本」在所有方格中不均勻（例如偏離鬼），那麼您需要修改算法，使得如果以較低的成本重新訪問節點，則將其放回到打開的列表中。 – alvion 2012-05-15 03:48:14