递归除法不保证路径

Question

我根据这里的答案实现了算法 Maze (recursive division) algorithm design。

但我运行遇到一个问题，即从开始 (+) 到结束 (-) 并不总有路径 like this image.

还有一个问题就是start(+)或者finish(-)节点会被墙包围see start node (+)

但我认为它很容易修复。

移除节点 [x-1][y]、[x][y+1]、[x+1][y] 和 [x][y-1] 周围的墙。

我不知道它是否正确。

那是我的迷宫class

class Maze {
  private G: INode[][];
  private rows: number;
  private cols: number;

  constructor(G: INode[][]) {
    this.G = G.map((row) =>
      row.map((node) => ({
        ...node,
        isWall: false,
      }))
    );
    this.rows = this.G.length;
    this.cols = this.G[0].length;

    // border walls
    for (let i = 0; i < this.rows; i++) {
      this.G[i][0].isWall = true;
      this.G[i][this.cols - 1].isWall = true;
    }
    for (let i = 0; i < this.cols; i++) {
      this.G[0][i].isWall = true;
      this.G[this.rows - 1][i].isWall = true;
    }
  }

  private rand(min: number, max: number) {
    return Math.floor(Math.random() * (max - min + 1) + min);
  }

  private isNodeStartOrFinish(row: number, col: number) {
    return this.G[row][col].isStart || this.G[row][col].isFinish;
  }

  // call perfectMaze to get the generate the maze 
  public perfectMaze() {
    this.divide(true, 1, this.cols - 2, 1, this.rows - 2);
  }

  private divide(
    h: boolean,
    minX: number,
    maxX: number,
    minY: number,
    maxY: number
  ) {
    if (h) {
      if (maxX - minX < 2) return;
      const y = Math.floor(this.rand(minY, maxY) / 2) * 2;
      this.addHWall(minX, maxX, y);
      this.divide(!h, minX, maxX, minY, y - 1);
      this.divide(!h, minX, maxX, y + 1, maxY);
    } else {
      if (maxY - minY < 2) return;
      const x = Math.floor(this.rand(minX, maxX) / 2) * 2;
      this.addVWall(minY, maxY, x);
      this.divide(!h, minX, x - 1, minY, maxY);
      this.divide(!h, x + 1, maxX, minY, maxY);
    }
  }

  private addHWall(minX: number, maxX: number, y: number) {
    const hole = Math.floor(this.rand(minX, maxX) / 2) * 2 + 1;
    for (let i = minX; i <= maxX; i++) {
      if (i !== hole && !this.isNodeStartOrFinish(y, i)) {
        this.G[y][i].isWall = true;
      }
    }
  }

  private addVWall(minY: number, maxY: number, x: number) {
    const hole = Math.floor(this.rand(minY, maxY) / 2) * 2 + 1;
    for (let i = minY; i <= maxY; i++) {
      if (i !== hole && !this.isNodeStartOrFinish(i, x)) {
        this.G[i][x].isWall = true;
      }
    }
  }

  public getMaze() {
    return this.G;
  }
}

Answer 1

好吧我是笨蛋

我===打洞的时候没有拆墙

在 addHWall 和 addVWall 方法中

如果 i === 洞，你必须删除墙，否则将再次添加墙

  private addHWall(minX: number, maxX: number, y: number) {
    const hole = Math.floor(this.rand(minX, maxX) / 2) * 2 + 1;
    for (let i = minX; i <= maxX; i++) {
      if (i === hole || this.isNodeStartOrFinish(y, i)) {
        this.G[y][i].isWall = false;
      } else {
        this.G[y][i].isWall = true;
      }
    }
  }

与addVWall相同

if (i === hole || this.isNodeStartOrFinish(i, x)) {
   this.G[y][i].isWall = false;
} else {
   this.G[i][x].isWall = true;
}

最后我删除了开始和结束节点周围的墙仍然不知道它是否是正确的解决方案

递归除法不保证路径

Recursive division does not guarantee a path

algorithm

recursion

graph-algorithm

maze