алгоритм — создание лабиринта с возвратом (преобразование всего в 2d массив)
Здесь создание лабиринта путем обратного отслеживания работает правильно, но дело в том, что я пытаюсь реализовать это в пиксельной игре (Minecraft) … поэтому проблема заключается в рисовании лабиринта. В этой игре размер блоков стены должен быть точно таким же, как размер пустого блока / пространства, поэтому единственное решение, о котором я подумал, это бонусный 2d массив, называемый 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;
}
}
Решение
Я думаю, что трудно объяснить алгоритм рандомизированного Прима в комментариях. Поэтому я решил опубликовать новый ответ.
Ячейки стены в рандомизированном алгоритме Прима на самом деле имеют «направления». Рассмотрим лабиринт ниже, где # обозначает стену и. указывает на пустую ячейку (позиции начинаются с 0).
#####
#...#
###.#
#...#
#####
Стена, расположенная в (2, 1), соединяет две ячейки (1, 1) и (3, 1), но не (2, 0) и (2, 2) (так как они обе являются стенами). Как только мы выберем нашу самую первую пустую ячейку, направления всех стен будут определены. Это потому, что стены служат ребрами графа, и график определяется, когда мы выбираем первую пустую ячейку. Вы можете нарисовать несколько лабиринтов на бумаге и увидеть это сами.
Я также написал пример на языке 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))
Вы должны получить что-то вроде этого
#####################
#.#.....#.#.#.......#
#.###.###.#.###.#.###
#.#.....#...#.#.#.#.#
#.###.#.###.#.###.#.#
#...#.#...#...#.....#
#.#.###.#####.#.#####
#.#.#.........#...#.#
###.#########.###.#.#
#.#...........#...#.#
#.#########.#.###.#.#
#.........#.#...#...#
#####.###.###.#####.#
#...#.#.#...........#
###.###.#####.###.###
#.......#.....#.....#
#.#.###.#####.#####.#
#.#.#...#...#.#.....#
#####.#.###.#####.###
#.....#.............#
#####################
Другие решения
Для создания «блочного» лабиринта есть лучшие способы. Почему бы не попробовать какой-нибудь алгоритм связующего дерева, такой как Kruskal? Проверьте ссылку ниже.
https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Kruskal.27s_algorithm