我目前正在研究Pacman AI啓發式，並且遇到了一些麻煩，包括Pacman變成兩個鬼之間的「困境」。算法，看看pacman是否被困在鬼魂之間，也就是說遊戲是無法通過的
我需要一些方法，給出板狀態以及所提供的任何有用信息（座標+所有代理的方向，牆位置，食物位置等），以確定Pacman是否被困在兩個即將到來的鬼之間，並且保證在n次移動中死亡，即這個棋盤狀態是不能通過的。 （這是假設鬼只能打開90度 - 因此，如果北上，鬼的可能的行動要麼是北，東或西，提供無壁的方式）
一個例子形象：
一個可能的解決方案是將問題表示爲狀態圖，其中每個狀態都表示爲一個節點。更具體地說，當前狀態將是根節點，並且邊將它連接到可以在單個步驟內達到的每個其他狀態。根據運行時間和內存約束/偏好，可以使用BFS/DFS/A *或其他一些搜索算法創建圖（樹）。
如果圖pacman的每一片葉子都被殺死了，那麼這個遊戲是無法通過的。否則，有一些獲勝狀態的葉子（以及從當前狀態到它的特定路徑）。
因爲在某些情況下，這種方法可能會帶來大量的計算工作，所以我會考慮限制樹的深度。
指數解決方案，真的不太有用。尋找多項式時間的東西。 –
建議的解決方案是普遍的（不限於pacman被困在兩個鬼魂之間，但解決任何可能的無法獲得的狀態），並且完成。 一個多項式解決方案可以通過以下任一方式輕鬆實現： 1.使用不完整的方法，例如限制樹深度/其中的節點數量/每當pacman有超過2個可能的方向轉向時停止消耗。 2.只處理狀態 –
2.只處理pacman被困在2個重影之間的特定情況。在這種情況下，您可以使用以下算法： a。確定當前的pacman所在的「走廊」。即，保留pacmans當前位置前後所有位置的一些表示，只有一種可能的處理方式（例如列表）。 b。檢查packman是否有一個幽靈從「走廊」的兩邊走向它的方向。 –
你的pacman可能會被困在某個點，但他可以根據鬼魂的移動而逃脫。鬼是否最佳移動？ –
@VladTarniceru不，受困我的意思是這樣的情況下，遊戲是完全無法通過。幽靈使用哪種算法無關緊要，只要記住它們只能達到45度 - 這意味着在上述情況下，遊戲將會丟失 –
幽靈可以開始向相反方向移動，如果它們隨機移動，對吧？ – halfo