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

Question

我有特定的需要生成 route/maze 并限制一些移动。

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

移动约束如下：

水平和垂直正好 3 个单元格
对角线上刚好有 2 个单元格
同一个场地不能踩两次

我已经为较低的级别找到了它，但目前不可能生成最大 lvl。

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

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 returns matrice，但您可以保留 return 值以用于更有用的东西，因为调用者已经可以访问 matrice 它首先传递给函数，并通过调用发生变异。
不需要全局stack变量，传给函数。相反，您可以反向构建它，从达到级别 0 的那一刻开始。您可以 return 然后是仅包含最后一个单元格的路径，并且在回溯时您可以预先添加当前单元格的路径。最后，您将拥有您想要的路径作为初始调用的 return 值。
我认为不需要从单元格的邻居列表中删除选定的边，因为无论如何您都不打算再次访问该单元格。另一方面，一个单元格不能被访问两次的条件足以避免遵循相同的边缘。
需要在return值中进行区分，表示搜索成功与否。如果成功，您可以 return 路径（如上所述），如果失败，您可以 return undefined.
函数应该 return undefined 当 checkTraversability return 是一个空数组并且我们还没有达到级别 0 时。
只有在确定递归调用成功找到解决方案时，才应将边标记为 "picked"。
当没有通向解的边时，不要忘记删除 visited 标记
不是使用 rand 随机选择一条边，而是创建一个函数来打乱边，然后迭代它们直到一条成功。如果none带来成功，那么returnundefined.

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

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);

这实际上是 return 一条有 11 个单元格和 10 条边的路径。我不确定第 10 级是指 10 个 other 个单元格还是包含起始单元格。如果这需要少一个，则将 if (level <= 0) 更改为 if (level <= 1)。

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

Maze Generation Using DFS with specific movement rules

javascript

maze

graph

graph-traversal

typescript