Алгоритм обратного следования лабиринта, кажется, не возвращается - PullRequest
Новая
       39

Алгоритм обратного следования лабиринта, кажется, не возвращается

1 голос
/ 05 апреля 2011

В основном, у меня есть это: во-первых, куча кода генерирует лабиринт, который нельзя пройти. Он случайным образом устанавливает стены в определенных пространствах двумерного массива на основе нескольких параметров. Затем я использую алгоритм обратного отслеживания, чтобы выбить стены, пока все это не будет пройдено. Дело в том, что программа, похоже, не возвращается обратно в стек.

Это довольно стандартный код возврата. Алгоритм запускается в произвольном месте, а затем продолжается в псевдокоде:

move (x, y) {
если вы можете подняться и еще не были там:
двигаться (х, у - 1)
если вы можете идти прямо и еще не были там:
ход (х + 1, у)
...
}

И так далее для других направлений. Каждый раз, когда вы перемещаетесь, два отдельных двумерных массива логических значений (один временный, один постоянный) устанавливаются в координатах, чтобы показать, что вы были в определенном элементе. Как только он не может идти дальше, он проверяет постоянный 2D-массив, чтобы увидеть, был ли он везде. Если нет, он случайным образом выбирает стену, которая граничит между посещенным и не посещенным пространством (согласно временному массиву), и удаляет ее. Все это вызывается в цикле while, поэтому после прохождения части лабиринта временный 2D-массив сбрасывается, в то время как другой сохраняется, и он снова проходит в другом случайном месте, пока постоянный 2D-массив не покажет, что весь лабиринт были пройдены Проверка в методе перемещения сравнивается с временным 2D-массивом, а не с постоянным.

Это почти работает, но я продолжал находить несколько недоступных областей в конечном сгенерированном лабиринте. В противном случае он делает замечательную работу по созданию лабиринта именно так, как я этого хочу. Дело в том, что я нахожу, что причина этого в том, что он не возвращается в стек.

Если я изменю его, чтобы проверить наличие временного 2D-массива вместо постоянного, то есть сделать один полный обход за один прогон, чтобы отметить его как завершенный, вместо того, чтобы выполнять полный прогон через несколько итераций), он будет и так далее. Я должен установить счетчик, чтобы сломать его. В результате получается «лабиринт» с удалением слишком большого количества стен. Проверяя маршрут, по которому идет алгоритм, я обнаружил, что он не отслеживался должным образом и не вернулся в стек достаточно далеко в стеке и часто просто застревает в одном элементе для десятков рекурсий, прежде чем объявить себя законченным без причины. на всех, и удаление стены, которая имела ноль, необходимо удалить.

Я пытался запустить предыдущую дважды, но она выбивает стены, которые не нужно выбивать, и делает лабиринт слишком разреженным. Я понятия не имею, какого черта это происходит.

1 Ответ

1 голос
/ 11 апреля 2011

У меня была похожая проблема при попытке создать метод для создания лабиринта.При создании лабиринтов важно стараться НЕ создавать изолированные «островки» из связанных комнат в лабиринте.Вот мое решение в псевдокоде 

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 очень похожа на вашу функцию move ()

В действительности, вы можете

  • описатьдверь "как отсутствие стены
  • и комната без дверей, как комната с четырьмя стенами

Но общий принцип:

  1. Началогде-то ваш рекурсивный алгоритм
  2. Когда алгоритм останавливается: найдите место, где есть 1 не посещенный квадрат и 1 посещенный.
  3. Свяжите эти два вместе и продолжайте с ранее не посещенного квадрата
  4. Когда никакие два квадрата не удовлетворяют (2), все готово и все квадраты соединены
...