Cruyun's Blog

Talk is cheap, show you my code

Maze-generation

• 标签: Algorithm

CS103 Lab-Maze Generation by JS

这是迷宫生成与求解lab之一：迷宫生成，知识点是回溯算法，参考地址,作者用的Ruby实现，评论区有用C语言的。我用的是JavaScript，参考了维基百科的提示，canvas的绘制用了p5.js,

维基百科提示的迷宫生成算法

Recursive backtracker[edit]
Recursive backtracker on a hexagonal grid
The depth-first search algorithm of maze generation is frequently implemented using backtracking:

  1. Make the initial cell the current cell and mark it as visited

  2. While there are unvisited cells

    1.If the current cell has any neighbours which have not been visited

    1.Choose randomly one of the unvisited neighbours

2.Push the current cell to the stack

3.Remove the wall between the current cell and the chosen cell

4.Make the chosen cell the current cell and mark it as visited

    2.Else if stack is not empty

    1.Pop a cell from the stack

2.Make it the current cell

下面介绍如何生成的迷宫

绘制网格

首先我们来绘制一个网格，定义网格的行、列、边长和每一格的边长。

1
2
3
4
5
6
7
8
var cols, rows;
var w = 40; //single width
function setup() {
    createCanvas(400, 400);
    cols = floor(width / w); //make sure get integers
    rows = floor(height / w);
}

现在我们得到了一个总边长为400的10×10网格。把网格定义成一个一维数组grid[]（二维也是可以的）。

创建一个函数，执行这个程序的主要步骤。

1
2
function draw() {
}

因为每个cell的四周是墙，我要做的就是去拆除部分墙形成迷宫，所以创建Cell函数，在里面拆墙。i和j分别代表网格的列和行。

1
2
3
4
5
function Cell(i, j) {
    //create a cell object
    this.i = i;
    this.j = j;
}

这样每个cell就都有了行和列的位置信息，在setup函数里面创建cell对象，cell的位置存放在grid[]中。

1
2
3
4
5
6
7
// create cell objects
    for (var j = 0; j < rows; j++) {
        for (var i = 0; i < cols; i++) {
            var cell = new Cell(i, j);
            grid.push(cell);
        }
    }

在draw函数里面要画出cell，所以在Cell函数里写一个函数show。

1
2
3
4
5
6
7
this.show = function() {
        var x = this.i * w;
        var y = this.j * w;
        background(51);
        for ( var i = 0; i < grid.length; i++) {
        grid[i].show();
     }

这样我绘制出了一个网格。但是我需要对单独的cell拆墙，所以应该单独的绘制每个cell的墙。把绘制网格写在draw函数里。

1
2
3
4
5
6
    function draw() {
    background(80);
    for (var i = 0; i < grid.length; i++) {
        grid[i].show();
    }
}

把wall定义为一个数组，四个元素依次是上 右 下 左的状态（如果为true则该墙存在）。

1
this.walls = [true, true, true, true];

每个cell的四个顶点的坐标是(x, y)、(x+w, y)、(x, y+w)、(x+w, y+w)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
  this.show = function() {
      var x = this.i * w;
      var y = this.j * w;
      // draw the walls
      // each cell:
      // (x, y)--------(x+w, y)
      //   |            |
      //   |            |
      //   |            |
      // (x, y+w)-----(x+w, y+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);
      }
}

回溯算法生成迷宫

每个cell都有neighbor cell，当有路可走的时候不能回头，所以要检查它的上下左右neighbor是否已经访问过，假如已经访问过就标记下来。
定义一个全局变量visited并设成false，再定义一个全局变量current,current是最近访问过的那一个邻居。先把current设定为起点grid[0]（这里你可以随意设置迷宫生成的起点）。