Блог

Я создаю приложение с использованием JavaScript и пытаюсь сгенерировать лабиринт, используя метод рекурсивного деления. Лабиринт генерируется в матрице n x m, где m > n и n — высота, а m — ширина. В матрице стены занимают положение матрицы [y] [x] (они не являются тонкими барьерами между точками в матрице). Я использую это в качестве руководства: http://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-algorithm .

Мой код выглядит следующим образом:

 const HORIZONTAL = "HORIZONTAL";
const VERTICAL = "VERTICAL";

// this function gets called first
function GenerateRecursiveDivisionMaze(grid) {
  let height = grid.length;
  let width = grid[0].length;

  // all the positions of the walls in the matrix
  let wallNodes = [];

  divide(wallNodes, 0, 0, width, height, HORIZONTAL);

  return wallNodes;
}

function divide(wallNodes, row, col, width, height, direction) {
  if (width < 3 || height < 3) return;
  let horizontal = direction === HORIZONTAL;

  // start position of the wall, change col and row?
  let wallPositionX = x   (horizontal ? 0 : generateRandomNumber(0, width - 2));
  let wallPositionY =
    y   (horizontal ? generateRandomNumber(0, height - 2) : 0);

  // passage in the wall
  let passageX =
    wallPositionX   (horizontal ? generateRandomNumber(0, width) : 0);

  let passageY =
    wallPositionY   (horizontal ? 0 : generateRandomNumber(0, height));

  // direction of wall
  let directionX = horizontal ? 1 : 0;
  let directionY = horizontal ? 0 : 1;

  // how long will the wall be
  let length = horizontal ? width : height;

  // build the wall
  for (let i = 0; i < length; i  ) {
    wallPositionY  = directionY;
    wallPositionX  = directionX;
    let y = wallPositionY;
    let x = wallPositionX;

    // make everything a wall except the designated passage
    if (passageX !== x || passageY !== y) {
      let node = {
        row: y,
        col: x,
      };
      wallNodes.push(node);
    }
  }

  let nextHeight = horizontal ? wallPositionY - y   1 : height;
  let nextWidth = horizontal ? width : wallPositionX - x   1;
  let nextDirectionToSlice = getDirectionToSlice(nextWidth, nextHeight);
  let nextX = x;
  let nextY = y;

  // recurse for the left and top side of the wall:
  divide(wallNodes, nextX, nextY, nextWidth, nextHeight, nextDirectionToSlice);

  // recurse right or bottom
  let nextX2 = horizontal ? x : wallPositionX   1;
  let nextY2 = horizontal ? wallPositionY   1 : y;

  let nextHeight2 = horizontal ? y   height - wallPositionY - 1 : height;
  let nextWidth2 = horizontal ? width : x   width - wallPositionX - 1;
  let nextDirectionToSlice2 = getDirectionToSlice(nextWidth2, nextHeight2);

  // recurse for the right and bottom side of the wall:
  divide(
    wallNodes,
    nextX2,
    nextY2,
    nextWidth2,
    nextHeight2,
    nextDirectionToSlice2
  );
}

function getDirectionToSlice(width, height) {
  if (width > height) {
    return VERTICAL;
  } else if (height > width) {
    return HORIZONTAL;
  } else {
    return generateRandomNumber(0, 1) == 0 ? HORIZONTAL : VERTICAL;
  }
}

// Generate a random number between lowNum and highNum
function generateRandomNumber(lowNum, highNum) {
    return Math.floor(Math.random() * (highNum - lowNum   1))   lowNum;
}
  

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

Любая помощь была бы очень признательна!

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

Обновление: отредактирована функция разделения. Проблема с превышением максимального стека теперь устранена. Однако стены в лабиринте группируются вместе, так что иногда по вертикали рядом друг с другом находится более одной стены, образуя стену толщиной в два узла. Сейчас я пытаюсь решить эту проблему.

В javascript рекурсии используются с функциями async и await, чтобы мы могли дождаться завершения рекурсии и возврата результата.

Пожалуйста, проверьте скрипку:https://jsfiddle.net/cvpwLrtn /

 const HORIZONTAL = "HORIZONTAL";
const VERTICAL = "VERTICAL";

GenerateRecursiveDivisionMaze([5000,5000]).then(result => {
    console.log(result);
});

// this function gets called first
async function GenerateRecursiveDivisionMaze(grid) {
    let height = grid[0];
    let width = grid[1];

    // all the positions of the walls in the matrix
    let wallNodes = [];

    await divide(wallNodes, 0, 0, width, height, HORIZONTAL);

    return wallNodes;
}

async function divide(wallNodes, row, col, width, height, direction) {
    if (width <= 2 || height <= 2) return;

    let vertical = direction === VERTICAL;

    // start position of the wall
    let wallPositionCol = vertical ? generateRandomNumber(row   2, width - 2) : row;
    let wallPositionRow = vertical ? col : generateRandomNumber(col   2, height - 2);

    // passage in the wall
    let passageRow = vertical
        ? generateRandomNumber(col   1, height - 1)
        : wallPositionRow;

    let passageCol = vertical
        ? wallPositionCol
        : generateRandomNumber(row   1, width - 1);

    // direction of wall
    let directionCol = vertical ? 0 : 1;
    let directionRow = vertical ? 1 : 0;

    // how long will the wall be
    let length = vertical ? height : width;

    // build the wall
    for (let i = 0; i < length; i  ) {
        let row = wallPositionRow   directionRow * i;
        let col = wallPositionCol   directionCol * i;

        // make everything a wall except the designated passage
        if (passageRow !== row || passageCol !== col) {
            let node = {
                row: row,
                col: col,
            };
            wallNodes.push(node);
        }
    }

    let nextHeight = vertical ? height : wallPositionRow;
    let nextWidth = vertical ? wallPositionCol : width;
    let nextDirectionToSlice = getDirectionToSlice(nextWidth, nextHeight);
    let nextRow = row;
    let nextCol = col;

    // recurse for the left or top side of the wall:
    setTimeout( function () {
        divide(
            wallNodes,
            nextRow,
            nextCol,
            nextWidth,
            nextHeight,
            nextDirectionToSlice,
        );
    }, 1000);

    // recurse right or bottom
    let nextHeight2 = vertical ? height : Math.abs(height - wallPositionRow);
    let nextWidth2 = vertical ? Math.abs(width - wallPositionCol) : width;
    let nextDirectionToSlice2 = getDirectionToSlice(nextWidth2, nextHeight2);
    let nextCol2 = vertical ? wallPositionCol : col;
    let nextRow2 = vertical ? row : wallPositionRow;

    setTimeout(function () {
        divide(
            wallNodes,
            nextRow2,
            nextCol2,
            nextWidth2,
            nextHeight2,
            nextDirectionToSlice2,
        );
    }, 2000)

}

function getDirectionToSlice(width, height) {
    if (width > height) {
        return VERTICAL;
    } else if (height > width) {
        return HORIZONTAL;
    } else {
        return generateRandomNumber(0, 1) === 0 ? HORIZONTAL : VERTICAL;
    }
}

// Generate a random number between lowNum and highNum
function generateRandomNumber(lowNum, highNum) {
    return Math.floor(Math.random() * (highNum - lowNum   1))   lowNum;
}  

Редактировать: Здесь я добавил setTimeout внутреннюю функцию асинхронного разделения, чтобы у двух рекурсий было время очистить стек, 1000 означает 1 сек. вы можете уменьшить его или увеличить в зависимости от размера сетки, я тестировал это с размером сетки [200000,200000]