javascript - 使用具有特定移动规则的 DFS 生成迷宫

Question

我有特定需要生成具有一些移动限制的路线/迷宫。

给定 10x10 矩阵中随机选取的cell，其中 level 是需要生成的可移动字段的数量，生成通过矩阵的路线。

移动限制如下:

• 水平和垂直恰好 3 个单元格
• 对 Angular 线上恰好有 2 个单元格
• 你不能两次踏上同一个 field

我已经弄清楚了较低级别的情况，但目前不可能生成最大级别。

我似乎无法正确理解回溯。

interface Cell extends Cords {
  visited: boolean
  neibhoursAvailable: Cords[]
  pickedEdge: Cords | {}
}

interface Cords {
  x: number
  y: number
}

type Matrice = Cell[][]

const rand = (arr: Cords[]) => {
  return arr[~~(Math.random() * arr.length)]
}

const matrix = (width: number, height: number): Cell[][] => {
  return Array(width)
    .fill({
      x: 0,
      y: 0,
      visited: false,
      neibhoursAvailable: [],
      pickedEdge: {},
    })
    .map(() =>
      Array(height).fill({
        x: 0,
        y: 0,
        visited: false,
        neibhoursAvailable: [],
        pickedEdge: {},
      }),
    )
}

const createCell = (
  x: number,
  y: number,
  visited: boolean,
  neibhoursAvailable: [],
): Cell => {
  return { x, y, visited, neibhoursAvailable, pickedEdge: {} }
}

let matrice = matrix(10, 10).map(
  (i, idx): Cell[] => {
    return i.map((_, idy) => {
      return {
        x: idx,
        y: idy,
        visited: false,
        neibhoursAvailable: [],
        pickedEdge: {},
      }
    })
  },
)

const checkTraversability = (
  startCords: Cords,
  matrice: Matrice,
): Cell | undefined => {
  // Check left
  console.log(startCords)
  if (startCords.x === undefined) {
    return undefined
  }
  if (startCords.y === undefined) {
    return undefined
  }
  const { x, y } = startCords
  const cell: Cell = matrice[x][y]

  if (cell.x - 3 >= 0 && !matrice[cell.x - 3][cell.y].visited) {
    cell.neibhoursAvailable.push({ x: cell.x - 3, y: cell.y })
  }

  // Check right
  if (cell.x + 3 < 10 && !matrice[cell.x + 3][cell.y].visited) {
    cell.neibhoursAvailable.push({ x: cell.x + 3, y: cell.y })
  }

  if (cell.y - 3 >= 0 && !matrice[cell.x][cell.y - 3].visited) {
    cell.neibhoursAvailable.push({ x: cell.x, y: cell.y - 3 })
  }
  if (cell.y + 3 < 10 && !matrice[cell.x][cell.y + 3].visited) {
    cell.neibhoursAvailable.push({ x: cell.x, y: cell.y + 3 })
  }

  // Check Diagonals

  if (
    cell.x + 2 < 10 &&
    cell.y + 2 < 10 &&
    !matrice[cell.x + 2][cell.y + 2].visited
  ) {
    cell.neibhoursAvailable.push({ x: cell.x + 2, y: cell.y + 2 })
  }

  if (
    cell.x + 2 < 10 &&
    cell.y - 2 >= 0 &&
    !matrice[cell.x + 2][cell.y - 2].visited
  ) {
    cell.neibhoursAvailable.push({ x: cell.x + 2, y: cell.y - 2 })
  }

  if (
    cell.x - 2 >= 0 &&
    cell.y + 2 < 10 &&
    !matrice[cell.x - 2][cell.y + 2].visited
  ) {
    cell.neibhoursAvailable.push({ x: cell.x - 2, y: cell.y + 2 })
  }

  if (
    cell.x - 2 >= 0 &&
    cell.y - 2 >= 0 &&
    !matrice[cell.x - 2][cell.y - 2].visited
  ) {
    cell.neibhoursAvailable.push({ x: cell.x - 2, y: cell.y + 2 })
  }
  return cell
}

let stack: Cell[] = []

const generateMaze = (
  matrice: Cell[][],
  stack: Cell[],
  startCords: { x: number; y: number },
  level: number,
) => {
  const traversable = checkTraversability(startCords, matrice)
  if (level >= 0) {
    traversable.visited = true
    const randomEdge = rand(traversable.neibhoursAvailable)
    traversable.neibhoursAvailable = traversable.neibhoursAvailable.filter(
      i => !(i.x === randomEdge.x && i.y === randomEdge.y),
    )
    traversable.pickedEdge = randomEdge
    stack.push(traversable)
    generateMaze(matrice, stack, randomEdge, level - 1)
  }
  return matrice
}

const gen = generateMaze(matrice, stack, { x: 0, y: 0 }, 10)
console.log(gen)

如有任何建议或指导，我们将不胜感激。

Answer 1

确实，回溯会带来问题。

一些问题:

• checkTraversability 快结束时有一个错误:您使用 cell.y + 2 推送坐标而它应该是cell.y - 2
• matrix函数有一个无用的参数传递给第一个 fill()称呼。该值永远不会被使用，因为您将该数组映射为二维数组，因此第一个 fill可能只是 fill(null) .
• 当随机选择的边导致无解时，就会出现循环缺失，应选择另一个边并进行尝试。
• generateMaze返回matrice ，但您可以保留返回值以用于更有用的内容，因为调用者已经可以访问 matrice它首先传递给函数，并通过调用而改变。
• 无需全局 stack变量，并将其传递给函数。相反，您可以反向构建它，从达到级别 0 的那一刻开始。您可以返回然后仅包含最后一个单元格的路径，并且在回溯时您可以在该路径前面添加当前单元格。最后，您将获得您想要的路径作为初始调用的返回值。
• 我认为没有必要从单元格的邻居列表中删除选定的边缘，因为无论如何您都不打算再次访问该单元格。另一方面，一个单元不能被访问两次的条件足以避免遵循相同的边。
• 返回值需要区分以指示搜索是否成功。如果成功，您可以返回路径(如上所述)，如果失败，您可以返回 undefined .
• 该函数应返回 undefined当checkTraversability返回一个空数组，而且我们还没有达到级别 0。
• 只有在确定递归调用成功找到解决方案时，才应将边标记为“已选取”。
• 不要忘记删除 visited当没有边导致解决方案时进行标记
• 而不是使用 rand 随机选择一条边，创建一个对边缘进行洗牌的函数，然后迭代它们直到成功。如果没有成功，则返回 undefined .

以下是您可以使用的一些代码部分:

shuffle功能:

function shuffle(a) {
    for (let i = a.length - 1; i > 0; i--) {
        let j = Math.floor(Math.random() * (i + 1));
        let x = a[i];
        a[i] = a[j];
        a[j] = x;
    }
    return a;
}

generateMaze功能

const generateMaze = (
  matrice: Cell[][],
  startCords: { x: number; y: number },
  level: number,
) => {    
  const traversable = checkTraversability(startCords, matrice);
  traversable.visited = true;
  if (level <= 0) return [traversable]; // found a solution: just return the end of the path
  for (let randomEdge of shuffle([...traversable.neibhoursAvailable])) {
    // Not needed to remove edge.
    let path = generateMaze(matrice, randomEdge, level - 1);
    if (path) { // Success: Only now mark the edge as picked
      traversable.pickedEdge = randomEdge;
      return [traversable, ...path]; // and backtrack building the path
    }
  }
  // failure: unmark this node (!), and just return undefined
  traversable.visited = false;
}

const path = generateMaze(matrice, { x: 0, y: 0 }, 10);
console.log(path);

这实际上会返回一条包含 11 个单元和 10 条边的路径。我不确定 10 级是否意味着 10 个其他单元格或包含起始单元格。如果需要减一，则更改 if (level <= 0)至if (level <= 1) .