回溯迷宮算法似乎不會一直回退

基本上，我有這樣的觀點：首先，一堆代碼會生成一個不可穿越的迷宮。它根據幾個參數在二維數組的某些空間中隨機設置牆。然後我有一個回溯算法去穿透牆壁，直到整個事物都可以穿越。事情是，該程序似乎並沒有回到堆棧中。回溯迷宮算法似乎不會一直回退

這是非常標準的回溯代碼。該算法開始於一個隨機位置，然後在僞代碼進行這樣的：

移動（X，Y）{
如果你可以去了，還沒有去過那裏已經：
移動（X，Y - 1）
如果你可以去正確的，並沒有在那裏已經：
移動（X + 1，Y）
...
}

等了其他方向。每次移動時，都會在座標處設置兩個獨立的布爾二維數組（一個臨時的，一個永久性的），以表明您已處於某個元素中。一旦它不能進一步發展，它會檢查永久2D陣列，看看它是否到處都是。如果不是，它會隨機挑選一個在訪問和未訪問空間（根據臨時數組）之間的邊界並移除它的牆。整個事件在一個while循環中被調用，所以一旦它遍歷了迷宮的一部分，臨時2D數組就會被重置，而另一個被保留，並且它會在另一個隨機位置再次遍歷，直到永久2D數組顯示整個迷宮已經被遍歷。移動方法中的檢查與臨時二維數組進行比較，而不是永久性數組。

這幾乎可以工作，但我在最終生成的迷宮中不斷找到一些無法到達的區域。否則，它會以我想要的方式創造一個迷宮。事情是，我發現這樣做的原因是它不會一直回到堆棧中。

如果我將其更改爲檢查臨時二維數組以完成而不是永久性數組（因此使其在一次運行中執行一次完整遍歷以將其標記爲完整，而不是在多次迭代中執行完整運行），它將繼續前進。我必須設置一個櫃檯來打破它。結果是一座「迷宮」，牆壁被拆除的太多了。通過檢查算法所採用的路線，我發現它沒有正確地回溯，並且沒有返回到堆棧中幾乎足夠遠的堆棧中，並且在宣佈自己無緣無故完成之前經常被卡住在單個元素上進行數十次遞歸完全消除了需要拆除的零牆。

我已經嘗試了兩次運行較早的那個，但它不斷敲出不需要被淘汰並使得迷宮太稀疏的牆。我不知道爲什麼這會發生。

來源

2011-04-05 AndroidHopeful

我試圖創建一個創建迷宮的方法時遇到了類似的問題。製作迷宮時最重要的事情就是不要在迷宮中創建連通房間的孤立「島嶼」。這裏是我的僞代碼解決方案

Room r=randomRoom(); 

while(r!=null){ 
    recursivelyDigNewDoors(r); 
    r=null; 
    for(i=0;i<rooms.count;i++){ 
     if(rooms[i].doors.length == 0 && rooms[i].hasNeighborWithDoor()){ 
     //if there is a room with no doors and that has a neighbor with doors 
     Create a door between the doorless room and the one 
     connected to the rest of your maze 
     r=rooms[i]; 
     } 
    } 
}

其中recursivelyDigNewDoors是很多像你的舉動（）函數

在現實中，你可能想

描述了一個「門」作爲缺少的壁
和沒有門的房間作爲一個帶四個壁

乙UT斯達康總的原則是：當算法停止

啓動遞歸算法某處
：找到一個地方，那裏有1未訪問廣場和1走訪。
鏈接這兩個一起，從先前未訪問過的方形
繼續當沒有兩個正方形滿足（2）您已完成，所有的廣場連接

來源

2011-04-11 12:07:51

謝謝，但我想它了。傻我沒有考慮確保方法有返回值，並且返回值分配給每個遞歸。難怪它沒有工作。我沒有告訴它維持一個堆棧回去！幾個小小的變化，我現在有一個迷宮生成算法，令人驚訝的是，從1x1方格的純網格到人口稀少的任何配置都可以工作。我得到了一個非線性的迷宮，但仍然需要大量的遍歷來完成。雖然謝謝！ – AndroidHopeful 2011-04-15 16:10:25

回溯迷宮算法似乎不會一直回退

回答

相關問題