Ошибка переполнения стека при рекурсии

#c# #recursion #unity3d #stack-overflow

#c# #рекурсия #unity-игровой движок #переполнение стека

Вопрос:

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

Вот код:

 private void MazeDigger(int[,] maze, int r, int c){

    int[] directions = new int[] {1, 2, 3, 4};
    Shuffle(directions);

    for(int i = 0; i < directions.Length; i  ){

        switch(directions[i]){
        case 1:

            if(r-2 <= 0)
            {
                continue;
            }

            if(maze[r-2, c] != 0)
            {
                maze[r-2, c] = 2;
                maze[r-1, c] = 2;
                MazeDigger(maze, r-2, c);
            }
            break;

        case 2:

            if(c 2 >= MazeWidth - 1)
            {
                continue;
            }

            if(maze[r, c 2] != 0)
            {
                maze[r, c 2] = 2;
                maze[r, c 1] = 2;
                MazeDigger(maze, r, c 1);
            }
            break;

        case 3:

            if(r 2 >= MazeHeight - 1)
            {
                continue;
            }

            if(maze[r 2, c] != 0)
            {
                maze[r 2, c] = 2;
                maze[r 1, c] = 2;
                MazeDigger(maze, r 2, c);
            }
            break;

        case 4:

            if(c-2 <= 0)
            {
                continue;
            }

            if(maze[r, c-2] != 0)
            {
                maze[r, c-2] = 2;
                maze[r, c-1] = 2;
                MazeDigger(maze, r, c-2);
            }
            break;
        }
    }
}

На самом деле это довольно просто. Я создаю массив с четырьмя направлениями, случайным образом перебираю их, а затем использую цикл for для выполнения по массиву. Внутри есть оператор switch, который в основном будет помечать разные точки в лабиринте как = 2. Это потому, что другой раздел кода использует modulus для генерации кубов в этих местах. Буду признателен за любую помощь, и, пожалуйста, дайте мне знать, если я не предоставил достаточно информации, спасибо!

1. Изначально звучит так, как будто он выполняется так много раз, что у вас заканчивается память в стеке. Некоторые советы по отладке могут включать вывод количества итераций, выполняемых до сбоя. Возможно, условия выхода работают не так, как вы ожидаете, и на самом деле это бесконечный цикл? Я думаю, что подтверждение того, что условия выхода работают надлежащим образом, — это, по крайней мере, хорошее место для начала.

2. Хорошо, я предположил, что это бесконечный цикл, потому что я тестировал лабиринт размером 5×5, который довольно мал, и он его не генерировал. Я только что протестировал лабиринт 3×3, который работает. Максимум, что я могу сгенерировать, — это 4×4. Предполагается, что это должно работать с лабиринтами размером 100×100 и гораздо большими размерами. Обычно я не получаю никаких проблем со стеком на этой машине. Почему он так легко переполняется?

3. тема настолько мета! 🙂

Ответ №1:

Нет условия выхода, или вы перепутали проверку.

Вы отмечаете каждую посещенную ячейку знаком 2 , но вы посетите ее снова, если она не равна 0 . Бесконечная история 🙂

Лабиринт 3×3 работает, потому что каждая ячейка не проходит проверку границ и рекурсии не происходит. Лабиринт 4×4 уже должен завершиться сбоем, но он может работать при определенных начальных условиях.