穿越迷宮的算法

Question

我們目前正在編寫一個遊戲（它的一個非常未知的語言：modula 2）， 而我們遇到的問題如下：我們有一個迷宮（不是完美的迷宮）在17 x 12格。計算機必須從起點（9,12）到終點（9,1）產生一條路。我發現了一些算法，但他們不工作時，機器人必須回去：

xxxxx 
    x 
=> x 
    x 
    xxx 

或：

xxxxx 
     x 
xxxxxx x 
    x x 
    x x 
xxxxxx x 
=>  x 
xxxxxxxxx 

我發現的第一個例子類型的解決方案，但隨後的第二類型不能解決了，我爲第二種類型所做的解決方案會導致機器人陷入第一種情況。

這是一個很大的代碼，所以我給的想法：

WHILE（最終目的地沒有達到）DO { 儘量向右走，如果沒有塊你：向右走 如果遇到塊，嘗試，直到你可以向右走，如果你不能再上去嘗試下去，直到你可以向右走，（從你第一次被阻止的地方開始），如果你不能再下去，試着走一步，填滿你的空間用塊測試。 }

這適用於第一類問題......不適用於第二類問題。 現在它可能是我開始錯了，所以我打開更好的算法或解決方案，特別是如何我可以改進我的算法。

非常感謝！

Answer 1

我想我記得你的算法只有當你通過一個入口進入迷宮，擁抱一堵牆，並嘗試出去時，你的算法才起作用。例如，如果你從迷宮中間的一個「島嶼」開始，它將無法工作。

看看Breadth-first search。這也會給你想要去的任何細胞的最短路徑。基本上這個想法是，你不希望從你分支的每個單元訪問同一個單元兩次（沒有理由）。

您的第一個例子。您可以識別該模式，數字是從箭頭開始到達每個單元格所需的步驟數。

xxxxx 
3212x 
2101x 
3212x 
43xxx 

你可以，當然，重建所採取的路徑，如果你喜歡，通過跟蹤，對每個小區，採取這種電池的最佳前一路徑的。

廣度優先搜索假定每個網格單元之間的距離是恆定的。如果相鄰單元格之間的距離有所不同，那麼可以看看這類問題：Shortest path problem。

Answer 2

你可能會需要實現搜索算法的路徑，因爲你不僅想找到什麼辦法，你也想找到最短可能的方式。最流行的路徑搜尋算法是Dijkstra和A*。如果你知道整個迷宮的佈局，它將爲你提供從一點到另一點的最短路徑。

Answer 3

您試圖解決的問題叫做尋路。有很多方法，從簡單的蠻力到驚人的A*。維基百科有一個非常好的概述here。

Answer 4

你正在考慮這個問題是否是一個穿過迷宮的角色。我不會那樣做。我會將迷宮想象成一系列隧道，水流經它們（意味着答案會流向各個方向）。因此，如果您要將迷宮表示爲2個空格字符串數組，其中包含null（或其他字符作爲牆），與未發現的地方（如'o'）不同的分隔符，其餘爲到達那個廣場的最短路徑（使用'n'，'e'，'s'和'w'）。然後，循環遍歷一個循環，每次，每個正方形都會查看它是否可以傳播到另一個正方形（如果正方形中有'o'），那麼它將添加一個連接版本的字符串，該正方形已經到了下一個廣場，char代表了它到達那裏的動作。當你找到結束方塊時，你就完成了。