用傳送器尋找路徑

Question

我正在與一個虛擬機器人（海龜在Computercraft模組爲我的世界），其中的機器人將在迷宮的隧道，並必須在其中導航。這個世界已經很方便地被分成了幾個瓦片（它們的二維笛卡爾圖形，每個瓦片都有一個布爾可通過/不可通過的值），並且建造隧道的機器人將會隨着他的走向而映射它們。

此外，還有傳送器「快捷鍵」散佈在機器人需要快速切換的區域。

問題是：有什麼方法讓機器人路徑到達目的地？系統如何識別需要傳送器的區域？ A *是最着名的算法，但有其他可能更適合應用程序的算法嗎？請記住，我在尋路算法方面的經驗很少，因此您可能必須將其分解爲基本術語以供我理解。有什麼建議麼？

Answer 1

使用A *的唯一問題是爲您的問題找到admissible heuristic。幸運的是，這已經回答了here。

系統將如何識別需要傳送器的區域？

這取決於烏龜實際在哪裏移動/從哪裏移動。如果他總是往/從相同的起點/終點移動，則答案很簡單：在開始和結束時添加傳送。對於更復雜的設置，我的猜測是這是NP難度;如果屬實，你必須考慮global-optimization strategies（或者只是嘗試一堆隨機位置，並採取最好的一個）。