Pacman的搜索算法

Question

我需要在由矩陣表示的圖中找到成本較低的路徑。我對Dijkstra的算法進行了一些研究，但我需要一個具有最短路徑節點序列的矢量，而不是距離本身。這個遊戲正在爲Assembly進行，但是如果有人知道C中的一個實現，至少它會有很大的幫助。我將使用它來計算鬼魂的路線，匹配啓發式算法來創建遊戲的非常困難模式。我也嘗試過使用A *，但是我發現使用了struct的實現，它們不適用於這種情況。從現在開始非常感謝。 ^^

Answer 1

此問題是edx AI course的基礎。我設法在這裏用C編寫的代碼爲breadth first search。從我能記得的廣度來看，第一次搜索是保證找到最短路徑，如果它存在的話。 我認爲在那裏添加一個啓發式算法也不算太難，edx鏈接上應該有一些註釋可以幫助解決這個問題。