php - 回溯迷宫生成(将所有内容转换为二维数组)

Question

这里通过回溯生成迷宫工作正常，但问题是我试图在像素游戏(Minecraft)中实现它......所以问题在于绘制迷宫。在这个游戏中，墙 block 的大小应该与空 block /空间的大小完全相同，所以我想到的唯一解决方案是一个名为 totalmaze 的奖励二维数组。它的目的是存储空白空间和墙 block ，所以我将其大小设置为 (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))

你应该得到这样的东西

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