Блог

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

1. Программа также заранее генерирует лабиринт. Если цель (символ шляпы ( » ^ » )) сгенерирована в начальной точке лабиринта, я хочу, чтобы программа сгенерировала новый лабиринт. Но это почему-то не работает 🙁
2. Программа выполняет итерацию слева вверху справа внизу и проверяет окружающие позиции на наличие шляпы или символа поля. Проблема в том, что если лабиринт выглядит так, программа останавливается и не работает:

 [ [ '*', 'O', 'O', 'O', '^' ],
  [ '░', 'O', '░', 'O', '░' ],
  [ '░', '░', 'O', 'O', '░' ],
  [ '░', '░', 'O', 'O', '░' ],
  [ '░', '░', '░', '░', '░' ] ] 

Я хотел, чтобы он прошел весь лабиринт наоборот, но это тоже не работает…

Я действительно рад любым предложениям по этим вопросам! Кто-нибудь может дать мне какие-нибудь отзывы о коде? Я написал много комментариев, вопросы должны быть понятны!

Вот ссылка на мое репо: https://github.com/Dimianovic/maze_solver/blob/main/main.js

Спасибо!

Пара заметок о вашем коде…

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

 mazeTest =
[ [ 'X', 'X', 'X', 'X', 'X', 'X', 'X' ],
  [ 'X', '*', 'O', 'O', 'O', '^', 'X' ],
  [ 'X', '░', 'O', '░', 'O', '░', 'X' ],
  [ 'X', '░', '░', 'O', 'O', '░', 'X' ],
  [ 'X', '░', '░', 'O', 'O', '░', 'X' ],
  [ 'X', '░', '░', '░', '░', '░', 'X' ],
  [ 'X', 'X', 'X', 'X', 'X', 'X', 'X' ] ];
 

function printMaze( maze ) {
  let result = '';
  for ( let row = 0; row < maze.length; row   ) {
    for ( let col = 0; col < maze[ row ].length; col   ) {
      result  = maze[ row ][ col ]   ' ';
    }
    result  = 'n';
  }
  return resu<
}

console.log( printMaze( mazeTest ) ); 

• Кроме того, поскольку символ ребра теперь является частью лабиринта, проверка каждого квадрата вокруг текущего квадрата может состоять из массива параметров, которые код может перебирать без необходимости иметь четыре (4) набора if операторов, проверяющих границы массива. (Это также значительно облегчает настройку кода, если вы хотите разрешить диагональные перемещения или, скажем, переход на шестиугольную компоновку ступеней…) В следующем отрывке показана основная концепция…

     const moveOptions = [ { r: -1, c: 0 }, { r:  1, c: 0 }, { r: 0, c: -1 }, { r: 0, c:  1 } ]; 

        o
        o
        o

    // From the current position, let's look in the immediate vicinity for
    // available squares.
    for ( let mo of moveOptions ) {
      let option = { row: currentSquare.row   mo.r, col: currentSquare.col   mo.c };
      let square = maze[ option.row ][ option.col ];
      
      // Did we find our goal?  If so, set it as the currentSquare and exit
      // the while loop.
      if ( square === '^' ) {
        currentSquare = option;
        break;
      }
      
      // If the square is available, then let's push it on the stack as a
      // starting point for another search.  Also, let's mark the square
      // as being in the stack so we don't visit it again!      
      if ( square === '░' ) {
        nextSquares.push( option );
        maze[ option.row ][ option.col ] = 's';
      }
    }

        o
        o
        o

 

• Приведенный выше код является выдержкой из первого глубокого поиска. Поиск по глубине просто включает в себя…
  • Создайте пустой стек массива, удерживая nextSquares его для перемещения.
  • Определите currentPosition и установите его в начальный квадрат.
  • В то время как это правда
    • Пройдитесь по 4 возможным квадратам из currentPosition
      • Если квадрат цели найден, выйдите из цикла и верните результат.
      • Если найден пустой квадрат, поместите его в nextSquares стопку, отметив квадрат как находящийся в настоящее время в стопке. (Это делается для того, чтобы он больше не рассматривался как пустой квадрат для следующего поиска из 4 возможных квадратов.)
    • Если nextSquares стопка пуста, выход, указывающий на то, что квадрат цели не найден.
    • В противном случае установите currentPosition значение квадрат, выскочивший из nextSquares стека, возвращаясь к началу оператора While.

Обратите внимание на приведенные выше примечания при рефакторинге вашего кода…