algorithm - 在Javascript中实现迷宫生成算法

Question

我了解“深度优先”迷宫生成算法，但我需要一些帮助来使用 Javascript 实现它。

Answer 1

Rosetta Code的Maze Generation包含许多使用简单的深度优先搜索算法生成和显示迷宫的实现：

JavaScript 中的代码：

function maze(x,y) {
    var n=x*y-1;
    if (n<0) {alert("illegal maze dimensions");return;}
    var horiz=[]; for (var j= 0; j<x+1; j++) horiz[j]= [];
    var verti=[]; for (var j= 0; j<y+1; j++) verti[j]= [];
    var here= [Math.floor(Math.random()*x), Math.floor(Math.random()*y)];
    var path= [here];
    var unvisited= [];
    for (var j= 0; j<x+2; j++) {
        unvisited[j]= [];
        for (var k= 0; k<y+1; k++)
            unvisited[j].push(j>0 && j<x+1 && k>0 && (j != here[0]+1 || k != here[1]+1));
    }
    while (0<n) {
        var potential= [[here[0]+1, here[1]], [here[0],here[1]+1],
            [here[0]-1, here[1]], [here[0],here[1]-1]];
        var neighbors= [];
        for (var j= 0; j < 4; j++)
            if (unvisited[potential[j][0]+1][potential[j][1]+1])
                neighbors.push(potential[j]);
        if (neighbors.length) {
            n= n-1;
            next= neighbors[Math.floor(Math.random()*neighbors.length)];
            unvisited[next[0]+1][next[1]+1]= false;
            if (next[0] == here[0])
                horiz[next[0]][(next[1]+here[1]-1)/2]= true;
            else 
                verti[(next[0]+here[0]-1)/2][next[1]]= true;
            path.push(here= next);
        } else 
            here= path.pop();
    }
    return ({x: x, y: y, horiz: horiz, verti: verti});
}

function display(m) {
    var text= [];
    for (var j= 0; j<m.x*2+1; j++) {
        var line= [];
        if (0 == j%2)
            for (var k=0; k<m.y*4+1; k++)
                if (0 == k%4) 
                    line[k]= '+';
                else
                    if (j>0 && m.verti[j/2-1][Math.floor(k/4)])
                        line[k]= ' ';
                    else
                        line[k]= '-';
        else
            for (var k=0; k<m.y*4+1; k++)
                if (0 == k%4)
                    if (k>0 && m.horiz[(j-1)/2][k/4-1])
                        line[k]= ' ';
                    else
                        line[k]= '|';
                else
                    line[k]= ' ';
        if (0 == j) line[1]= line[2]= line[3]= ' ';
        if (m.x*2-1 == j) line[4*m.y]= ' ';
        text.push(line.join('')+'\r\n');
    }
    return text.join('');
}

Java中的代码：

public int[][] generateMaze() {
    int[][] maze = new int[height][width];
    // Initialize
    for (int i = 0; i < height; i++)
        for (int j = 0; j < width; j++)
            maze[i][j] = 1;

     Random rand = new Random();
     // r for row、c for column
     // Generate random r
     int r = rand.nextInt(height);
     while (r % 2 == 0) {
         r = rand.nextInt(height);
     }
     // Generate random c
     int c = rand.nextInt(width);
     while (c % 2 == 0) {
         c = rand.nextInt(width);
     }
     // Starting cell
     maze[r][c] = 0;

     //　Allocate the maze with recursive method
     recursion(r, c);

     return maze;
 }

 public void recursion(int r, int c) {
     // 4 random directions
     int[] randDirs = generateRandomDirections();
     // Examine each direction
     for (int i = 0; i < randDirs.length; i++) {

         switch(randDirs[i]){
         case 1: // Up
             //　Whether 2 cells up is out or not
             if (r - 2 <= 0)
                 continue;
             if (maze[r - 2][c] != 0) {
                 maze[r-2][c] = 0;
                 maze[r-1][c] = 0;
                 recursion(r - 2, c);
             }
             break;
         case 2: // Right
             // Whether 2 cells to the right is out or not
             if (c + 2 >= width - 1)
                 continue;
             if (maze[r][c + 2] != 0) {
                 maze[r][c + 2] = 0;
                 maze[r][c + 1] = 0;
                 recursion(r, c + 2);
             }
             break;
         case 3: // Down
             // Whether 2 cells down is out or not
             if (r + 2 >= height - 1)
                 continue;
             if (maze[r + 2][c] != 0) {
                 maze[r+2][c] = 0;
                 maze[r+1][c] = 0;
                 recursion(r + 2, c);
             }
             break;
         case 4: // Left
             // Whether 2 cells to the left is out or not
             if (c - 2 <= 0)
                 continue;
             if (maze[r][c - 2] != 0) {
                 maze[r][c - 2] = 0;
                 maze[r][c - 1] = 0;
                 recursion(r, c - 2);
             }
             break;
         }
     }

 }

 /**
 * Generate an array with random directions 1-4
 * @return Array containing 4 directions in random order
 */
 public Integer[] generateRandomDirections() {
      ArrayList<Integer> randoms = new ArrayList<Integer>();
      for (int i = 0; i < 4; i++)
           randoms.add(i + 1);
      Collections.shuffle(randoms);

     return randoms.toArray(new Integer[4]);
 }

源代码、演示和更多解释