使用 p5.js 的迷宫求解算法

Question

我使用深度优先搜索 - 递归回溯算法生成了一个迷宫。我也想解决，但不知道如何开始解决我的迷宫。

我正在使用 p5.js 创建我的迷宫，并想解决我已经生成的迷宫。

这是我的 javascript 生成迷宫的代码。如果您想运行此代码，您可能需要在 html 文件中添加 p5.js cdn。

var cols, rows;
var w = 40;
var grid = [];
var current;
var stack = [];
function setup() {
    createCanvas(400,400);
    cols = floor(width/w);
    rows = floor(height/w);
    frameRate(5);
    for (var j = 0; j<rows; j++){
        for (var i = 0; i < cols; i++) {
            var cell = new Cell(i,j);
            grid.push(cell);
        }
    }
    current = grid[0];
}
function draw(){
    background(51);
    for (var i = 0; i<grid.length; i++){
        grid[i].show();
    }
    current.visited = true;
    current.highlight();
    var next = current.checkNeighbours();
    if (next) {
        next.visited = true;
        stack.push(current);
        removeWalls(current,next);
        current = next;
    }
    else if(stack.length > 0){
        current = stack.pop();
    }
}
function index(i,j){
    if (i < 0 || j < 0 || i > cols-1 || j > rows-1) {
        return -1;
    }
    return i + j * cols;
}
function Cell(i,j){
    this.i = i;
    this.j = j;
    this.walls = [true,true,true,true];
    this.visited = false;
    this.checkNeighbours = function(){
        var neighbours = [];
        var top =       grid[index(i, j-1)];
        var right =     grid[index(i+1, j)];
        var bottom =    grid[index(i, j+1)];
        var left =      grid[index(i-1, j)];
        if (top && !top.visited){
            neighbours.push(top);
        }
        if (right && !right.visited){
            neighbours.push(right);
        }
        if (bottom && !bottom.visited){
            neighbours.push(bottom);
        }
        if (left && !left.visited){
            neighbours.push(left);
        }
        if (neighbours.length > 0){
            var r = floor(random(0, neighbours.length));
            return neighbours[r];
        }
        else{
            return undefined;
        }
    }
    this.highlight = function(){
        x = this.i*w;
        y = this.j*w;
        noStroke();
        fill(0,0,255,200);
        rect(x,y,w,w);
    }
    this.show = function(){
        x = this.i*w;
        y = this.j*w;
        stroke(255);
        if (this.walls[0]){
            line(x   ,y    ,x+w ,y);
        }   
        if (this.walls[1]){
            line(x+w ,y    ,x+w ,y+w);
        }
        if (this.walls[2]){
            line(x+w ,y+w  ,x   ,y+w);
        }
        if (this.walls[3]){
            line(x   ,y+w  ,x   ,y)
        }   
        if (this.visited) {
            noStroke();
            fill(255,0,255,100);
            rect(x,y,w,w);
        }
    }
}
function removeWalls(a,b){
    var x = a.i - b.i;
    if (x === 1){
        a.walls[3] = false;
        b.walls[1] = false;
    }
    else if (x === -1){
        a.walls[1] = false;
        b.walls[3] = false; 
    }
    var y = a.j - b.j;
    if (y === 1){
        a.walls[0] = false;
        b.walls[2] = false;
    }
    else if (y === -1){
        a.walls[2] = false;
        b.walls[0] = false; 
    }   
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.7.3/p5.js"></script>

Answer 1

有many algorithmsfor solving mazes. One simple way to solve mazes created with the recursive backtracker算法在生成迷宫时跟踪解决方案。

将第一个单元格设为起始单元格并将其推入解决方案堆栈
将最后一个单元格设为目标单元格
虽然解决方案堆栈不包含目标单元格
1. 如果未访问下一个邻居，则将其推入解决方案堆栈
2. 如果一个单元格没有下一个邻居，则在我们回溯时弹出解决方案堆栈
当目标单元格被推送到解决方案堆栈时，将解决方案标记为完成

调整问题代码，使其也实现我们的解决算法：

var cols, rows;
var w = 40;
var grid = [];
var current;
var stack = [];
var solution = [];
var goal;
var solutionComplete;
function setup() {
    createCanvas(400,400);
    cols = floor(width/w);
    rows = floor(height/w);
    frameRate(5);
    for (var j = 0; j<rows; j++){
        for (var i = 0; i < cols; i++) {
            var cell = new Cell(i,j);
            grid.push(cell);
        }
    }
    current = grid[0];
    grid[grid.length - 1].goal = true;
    solution.push(grid[0]);
}
function draw(){
    background(51);
    for (var i = 0; i<grid.length; i++){
        grid[i].show();
    }
    current.visited = true;
    current.highlight();
    var next = current.checkNeighbours();
    if (next) {
        if (!next.visited){
          if (!solutionComplete){
            solution.push(next);
            if (next.goal){
              solutionComplete = true;
            }
          }
        }
        next.visited = true;
        stack.push(current);
        removeWalls(current,next);
        current = next;
    }
    else if(stack.length > 0){
        current = stack.pop();
        if (!solutionComplete){
          solution.pop();
        }
    }
    if (solutionComplete){
      for (let i = 0; i < solution.length; i++){
        solution[i].solutionCell = true;
      }
    }
}
function index(i,j){
    if (i < 0 || j < 0 || i > cols-1 || j > rows-1) {
        return -1;
    }
    return i + j * cols;
}
function Cell(i,j){
    this.i = i;
    this.j = j;
    this.walls = [true,true,true,true];
    this.visited = false;
    this.goal = false;
    this.solutionCell = false;
    this.checkNeighbours = function(){
        var neighbours = [];
        var top =       grid[index(i, j-1)];
        var right =     grid[index(i+1, j)];
        var bottom =    grid[index(i, j+1)];
        var left =      grid[index(i-1, j)];
        if (top && !top.visited){
            neighbours.push(top);
        }
        if (right && !right.visited){
            neighbours.push(right);
        }
        if (bottom && !bottom.visited){
            neighbours.push(bottom);
        }
        if (left && !left.visited){
            neighbours.push(left);
        }
        if (neighbours.length > 0){
            var r = floor(random(0, neighbours.length));
            return neighbours[r];
        }
        else{
            return undefined;
        }
    }
    this.highlight = function(){
        x = this.i*w;
        y = this.j*w;
        noStroke();
        fill(0,0,255,200);
        rect(x,y,w,w);
    }
    this.show = function(){
        x = this.i*w;
        y = this.j*w;
        stroke(255);
        if (this.walls[0]){
            line(x   ,y    ,x+w ,y);
        }   
        if (this.walls[1]){
            line(x+w ,y ,x+w ,y+w);
        }
        if (this.walls[2]){
            line(x+w ,y+w  ,x ,y+w);
        }
        if (this.walls[3]){
            line(x ,y+w ,x ,y)
        }
        if (this.goal){
            noStroke();
            fill(0,255,0,100);
            rect(x,y,w,w);
        }        
        else if (this.solutionCell){
            noStroke();
            fill(255,0,0,100);
            rect(x,y,w,w);
        }else if(this.visited) {
            noStroke();
            fill(255,0,255,100);
            rect(x,y,w,w);
        }
    }
}
function removeWalls(a,b){
    var x = a.i - b.i;
    if (x === 1){
        a.walls[3] = false;
        b.walls[1] = false;
    }
    else if (x === -1){
        a.walls[1] = false;
        b.walls[3] = false; 
    }
    var y = a.j - b.j;
    if (y === 1){
        a.walls[0] = false;
        b.walls[2] = false;
    }
    else if (y === -1){
        a.walls[2] = false;
        b.walls[0] = false; 
    }   
}

   <script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.7.2/p5.min.js"></script>

将迷宫生成和解决方案实现分开并不难，以便在确定解决方案之前完全生成迷宫，但除非存在强制我们解决完整迷宫的限制，否则构建是有意义的解决方案和迷宫。

Answer 2

很抱歉，这是非常相关的，但是编码训练一个编码 youtuber 制作了一个迷宫生成算法，但我不知道它是否使用深度优先搜索

使用 p5.js 的迷宫求解算法

Maze solving algorithm using p5.js

html

p5.js