php - 回溯迷宮一代（將所有東西都轉換爲二維數組）

Question

這裏通過回溯生成一個迷宮工作正常，但事情是，我試圖在一個像素遊戲（我的世界）中實現...所以問題是在繪圖迷宮。在這個遊戲中，牆塊的尺寸應該與空塊/空間的尺寸完全相同，所以我唯一想到的解決方案是名爲totalmaze的額外二維數組。它的目的是存儲空的空間和牆塊，所以我做了它的大小（x * 3，y * 3）並嘗試輸出牆壁，但不幸的是這會導致很多問題，例如空間太多/路徑被阻塞。注意：X，Z是因爲它是一個3d迷宮。

如果這是一個JavaScript和一個簡單的應用程序，我只是畫牆，但在Minecraft中，尺寸應該是相同的，因此即使算法是正確的，事情也會變得麻煩。請幫忙。

這是我正在試圖修復它，但也許是沒有辦法的辦法：https://prnt.sc/fbp88o

public function generateMaze($dim_x, $walls_height, $dim_z){ 

     $maze = array(); 
     $moves = array(); 

     $cell_count = $dim_x*$dim_z; 

     for($position=0; $position<$cell_count; $position++){ 
      $maze[$position] = "01111"; // visited, NSEW 
     } 
     $pos=0; 
     $maze[0]{0} = 1; /// initial 
     $visited = 1; 

     // determine possible directions 
     while($visited<$cell_count){ 
      $possible = ""; 
      if((floor($pos/$dim_x)==floor(($pos-1)/$dim_x)) and ($maze[$pos-1]{0}==0)){ 
       $possible .= "W"; 
      } 
      if((floor($pos/$dim_x)==floor(($pos+1)/$dim_x)) and ($maze[$pos+1]{0}==0)){ 
       $possible .= "E"; 
      } 
      if((($pos+$dim_x)<$cell_count) and ($maze[$pos+$dim_x]{0}==0)){ 
       $possible .= "S"; 
      } 
      if((($pos-$dim_x)>=0) and ($maze[$pos-$dim_x]{0}==0)){ 
       $possible .= "N"; 
      } 
      if($possible){ 
       $visited ++; 
       array_push($moves,$pos); 
       $direction = $possible{rand(0,strlen($possible)-1)}; 
       switch($direction){ 
        case "N": 
         $maze[$pos]{1} = 0; 
         $maze[$pos-$dim_x]{2} = 0; 
         $pos -= $dim_x; 
         break; 
        case "S": 
         $maze[$pos]{2} = 0; 
         $maze[$pos+$dim_x]{1} = 0; 
         $pos += $dim_x; 
         break; 
        case "E": 
         $maze[$pos]{3} = 0; 
         $maze[$pos+1]{4} = 0; 
         $pos ++; 
         break; 
        case "W": 
         $maze[$pos]{4} = 0; 
         $maze[$pos-1]{3} = 0; 
         $pos --; 
         break; 
       } 
       $maze[$pos]{0} = 1; 
      } 
      else{ 
       $pos = array_pop($moves); 
      } 
     } 
     $totalmaze = array(); 
     for($i=0; $i<$dim_x*3+1; $i++){ 
      $totalmaze[$i][0] = 1; 
      $totalmaze[$i][$dim_z*3-1]=1; 
     } 
     for($i=0; $i<$dim_z*3+1; $i++){ 
      $totalmaze[0][$i] = 1; 
      $totalmaze[$dim_x*3-1][$i]=1; 
     } 
     for($position=0; $position<$cell_count; $position++){ 
      $x = $position % $dim_x; 
      $z = floor($position/$dim_x); 
      if($maze[$position]{1} == 1){ 
       $totalmaze[$x*3+1][$z*3]=1; 
      } 
      if($maze[$position]{2} == 1){ 
       $totalmaze[$x*3+1][$z*3+2]=1; 
      } 
      if($maze[$position]{3} == 1){ 
       $totalmaze[$x*3+2][$z*3+1]=1; 

      } 
      if($maze[$position]{4} == 1){ 
       $totalmaze[$x*3][$z*3+1]=1; 
      } 

     } 

Answer 1

我認爲這是很難解釋的隨機Prim算法中的註釋。所以我決定發佈一個新的答案。

隨機Prim算法中的細胞壁實際上有「方向」。考慮以下迷宮，其中＃表示牆和。表示一個空單元（位置從0開始）。

##### 
#...# 
###.# 
#...# 
##### 

定位在所述壁（2,1）連接兩個單元（1,1）和（3，1），但不是（2,0）和（2,2）（作爲兩個都是牆）。只要我們選擇我們第一個空單元格，所有牆的方向就確定了。這是因爲牆壁在圖形中充當邊緣，並且當我們選擇第一個空單元時，圖形被確定。你可以在紙上畫一些迷宮，然後自己看。

我也寫過一個隨機Prim算法的python例子。嘗試運行它。

import random 

SIZE = 21 

# Fill the maze with walls 
maze = [['#' for j in range(0, SIZE)] for i in range(0, SIZE)] 

# Create an empty wall list 
wall_list = [] 

# Check if the given position is in the maze and not on the boundary 
def in_maze(row, col): 
    return row > 0 and row < SIZE-1 and col > 0 and col < SIZE-1 

# Add the neighboring walls of the cell (row, col) to the wall list 
def add_walls(row, col): 
    global maze, wall_list 

    # It's a 4-connected grid maze 
    dir = ((0, 1), (1, 0), (0, -1), (-1, 0)) 

    for k in range(0, len(dir)): 
     # Calculate the neighboring wall position and the cell position 
     wall_row = row + dir[k][0] 
     wall_col = col + dir[k][1] 
     cell_row = wall_row + dir[k][0] 
     cell_col = wall_col + dir[k][1] 

     # Make sure the wall grid is in the range of the maze 
     if not in_maze(wall_row, wall_col) or not in_maze(cell_row, cell_col): 
      continue 

     # Add the wall and the neighboring cell to the list 
     wall_list.append(((wall_row, wall_col), (cell_row, cell_col))) 

# Pick a random grid first 
cell_row = random.randint(1, SIZE-2) 
cell_col = random.randint(1, SIZE-2) 
maze[cell_row][cell_col] = '.' 
add_walls(cell_row, cell_col) 

while len(wall_list) > 0: 
    # Pick a random wall 
    id = random.randint(0, len(wall_list)-1) 
    wall_row, wall_col = wall_list[id][0] 
    cell_row, cell_col = wall_list[id][1] 
    wall_list.pop(id) 

    # Skip if it is no longer a wall 
    if maze[wall_row][wall_col] != '#': 
     continue 
    # Skip if the two cells that the wall divides are visited 
    if maze[cell_row][cell_col] == '.': 
     continue 

    # Make the two grid as passages 
    maze[wall_row][wall_col] = '.' 
    maze[cell_row][cell_col] = '.' 

    # Add the neighboring walls 
    add_walls(cell_row, cell_col) 

# Print the maze 
for row in maze: 
    print(''.join(row)) 

你應該得到這樣的事情

##################### 
#.#.....#.#.#.......# 
#.###.###.#.###.#.### 
#.#.....#...#.#.#.#.# 
#.###.#.###.#.###.#.# 
#...#.#...#...#.....# 
#.#.###.#####.#.##### 
#.#.#.........#...#.# 
###.#########.###.#.# 
#.#...........#...#.# 
#.#########.#.###.#.# 
#.........#.#...#...# 
#####.###.###.#####.# 
#...#.#.#...........# 
###.###.#####.###.### 
#.......#.....#.....# 
#.#.###.#####.#####.# 
#.#.#...#...#.#.....# 
#####.#.###.#####.### 
#.....#.............# 
##################### 

Answer 2

生成一個「塊」迷宮有更好的方法。爲什麼不嘗試像Kruskal這樣的生成樹算法？檢查下面的鏈接。

https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal.27s_algorithm