Выполнение алгоритма генерации лабиринта в Javascript

Question

Я понимаю алгоритм лазера лабиринта «Глубина-первый», но мне нужна небольшая помощь в его реализации с помощью Javascript.

Answer 1

Maze Generation в Rosetta Code содержит множество реализаций для создания и показать лабиринт, используя простой поиск в глубину алгоритм:

код в 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]); 
} 

Source, demo and some more explanations