Внедрение случайно созданного лабиринта с использованием Prim Algorithm

Я пытаюсь реализовать случайно сгенерированный лабиринт с использованием алгоритма Prim.

Я хочу, чтобы мой лабиринт выглядел так:

однако лабиринты, которые я генерирую из моей программы, выглядят следующим образом:

Я сейчас зациклен на правильном выполнении шагов, выделенных жирным шрифтом:

  • Начните с сетки, полной стен.
  • Выберите ячейку, отметьте ее как часть лабиринта. Добавьте стены ячейки в список стен.
  • Пока в списке есть стены:
    • ** 1. Выберите случайную стену из списка. Если ячейка на противоположной стороне еще не находится в лабиринте:
        • Сделайте стену проходом и отметьте ячейку на противоположной стороне как часть лабиринта. **
        1. Добавьте соседние стены ячейки в список стен.
    1. Удалите стену из списка.

от в этой статье о генерации лабиринта.

Как определить, является ли ячейка допустимым кандидатом для списка на стене? Я хотел бы изменить свой алгоритм так, чтобы он создавал правильный лабиринт. Любые идеи, которые помогут мне решить мою проблему, будут оценены.

6 ответов

Описание в статье Википедии действительно заслуживает улучшения.

Первая запутанная часть статьи заключается в том, что описание рандомизированного алгоритма Prim не уточняет предполагаемую структуру данных, используемую алгоритмом. Таким образом, фразы типа "противоположная ячейка" запутываются.

В основном есть два основных подхода: "программисты-генераторы лабиринта" могут выбрать:

  • Клетки имеют стены или проходы к своим 4 соседям. Информация о стенах/проходах хранится и обрабатывается.
  • Ячейки могут быть заблокированы (стены) или проходы без сохранения дополнительной информации о подключении.

В зависимости от того, какая модель (1) или (2) читатель имеет в виду при чтении описания алгоритма, они либо понимают, либо не понимают.

Мне лично я предпочитаю использовать клетки как стены или проходы, а не возиться с выделенной информацией о проходе/стене.

Затем "пограничные" участки имеют расстояние 2 (а не 1) от прохода. Случайный пограничный патч из списка пограничных патчей выбирается и соединяется со случайным соседним проходом (на расстоянии 2), также делая ячейку между пограничным патчем и соседним проходом проходом.

Вот моя реализация F #, как это выглядит:

let rng = new System.Random()
type Cell = | Blocked | Passage
type Maze = 
 { 
 Grid : Cell[,]
 Width : int
 Height : int
 }
let initMaze dx dy = 
 let six,siy = (1,1)
 let eix,eiy = (dx-2,dy-2)
 { 
 Grid = Array2D.init dx dy 
 (fun _ _ -> Blocked
 ) 
 Width = dx
 Height = dy
 }
let generate (maze : Maze) : Maze =
 let isLegal (x,y) =
 x>0 && x < maze.Width-1 && y>0 && y<maze.height-1 let="" frontier="" (x,y)="[x-2,y;x+2,y;" x,y-2;="" x,="" y+2]="" |=""> List.filter (fun (x,y) -> isLegal (x,y) && maze.Grid.[x,y] = Blocked)
 let neighbor (x,y) =
 [x-2,y;x+2,y; x,y-2; x, y+2]
 |> List.filter (fun (x,y) -> isLegal (x,y) && maze.Grid.[x,y] = Passage)
 let randomCell () = rng.Next(maze.Width),rng.Next(maze.Height)
 let removeAt index (lst : (int * int) list) : (int * int) list =
 let x,y = lst.[index]
 lst |> List.filter (fun (a,b) -> not (a = x && b = y) )
 let between p1 p2 =
 let x = 
 match (fst p2 - fst p1) with
 | 0 -> fst p1
 | 2 -> 1 + fst p1
 | -2 -> -1 + fst p1
 | _ -> failwith "Invalid arguments for between()"
 let y = 
 match (snd p2 - snd p1) with
 | 0 -> snd p1
 | 2 -> 1 + snd p1
 | -2 -> -1 + snd p1
 | _ -> failwith "Invalid arguments for between()"
 (x,y)
 let connectRandomNeighbor (x,y) =
 let neighbors = neighbor (x,y)
 let pickedIndex = rng.Next(neighbors.Length)
 let xn,yn = neighbors.[pickedIndex]
 let xb,yb = between (x,y) (xn,yn)
 maze.Grid.[xb,yb] <- Passage
 ()
 let rec extend front =
 match front with
 | [] -> ()
 | _ ->
 let pickedIndex = rng.Next(front.Length)
 let xf,yf = front.[pickedIndex]
 maze.Grid.[xf,yf] <- Passage
 connectRandomNeighbor (xf,yf)
 extend ((front |> removeAt pickedIndex) @ frontier (xf,yf))
 let x,y = randomCell()
 maze.Grid.[x,y] <- Passage
 extend (frontier (x,y))
 maze
let show maze =
 printfn "%A" maze
 maze.Grid |> Array2D.iteri 
 (fun y x cell ->
 if x = 0 && y > 0 then 
 printfn "|"
 let c = 
 match cell with
 | Blocked -> "X"
 | Passage -> " "
 printf "%s" c
 )
 maze
let render maze =
 let cellWidth = 10;
 let cellHeight = 10;
 let pw = maze.Width * cellWidth
 let ph = maze.Height * cellHeight
 let passageBrush = System.Drawing.Brushes.White
 let wallBrush = System.Drawing.Brushes.Black
 let bmp = new System.Drawing.Bitmap(pw,ph)
 let g = System.Drawing.Graphics.FromImage(bmp);
 maze.Grid
 |> Array2D.iteri 
 (fun y x cell ->
 let brush = 
 match cell with
 | Passage -> passageBrush
 | Blocked -> wallBrush
 g.FillRectangle(brush,x*cellWidth,y*cellHeight,cellWidth,cellHeight)
 )
 g.Flush()
 bmp.Save("""E:\temp\maze.bmp""")
initMaze 50 50 |> generate |> show |> render
</maze.height-1>

Полученный лабиринт может выглядеть следующим образом:

Здесь попытка описать мое решение в стиле "алгоритм" википедии:

  • Сетка состоит из 2-мерного массива ячеек.
  • Ячейка имеет 2 состояния: заблокировано или прохождение.
  • Начните с сетки, полной ячеек в состоянии Заблокировано.
  • Выберите случайную ячейку, установите ее в состояние "Прохождение" и "Вычислите свои пограничные ячейки". Пограничная ячейка ячейки - это ячейка с расстоянием 2 в состоянии "Заблокировано" и внутри сетки.
  • Пока список пограничных ячеек не пуст:
    • Выберите случайную ячейку границы из списка пограничных ячеек.
    • Пусть соседние (frontierCell) = все ячейки на расстоянии 2 в состоянии Passage. Выберите случайного соседа и соедините пограничную ячейку с соседом, установив межсетевое соединение в состояние Passage. Вычислите пограничные ячейки выбранной пограничной ячейки и добавьте их в список границ. Удалите выбранную пограничную ячейку из списка пограничных ячеек.


Простая реализация Java алгоритма Prim:

import java.util.LinkedList;
import java.util.Random;
public class Maze {
 public static final char PASSAGE_CHAR = ' ';
 public static final char WALL_CHAR = '▓';
 public static final boolean WALL = false;
 public static final boolean PASSAGE = !WALL;
 private final boolean map[][];
 private final int width;
 private final int height;
 public Maze( final int width, final int height ){
 this.width = width;
 this.height = height;
 this.map = new boolean[width][height];
 final LinkedList<int[]> frontiers = new LinkedList<>();
 final Random random = new Random();
 int x = random.nextInt(width);
 int y = random.nextInt(height);
 frontiers.add(new int[]{x,y,x,y});
 while ( !frontiers.isEmpty() ){
 final int[] f = frontiers.remove( random.nextInt( frontiers.size() ) );
 x = f[2];
 y = f[3];
 if ( map[x][y] == WALL )
 {
 map[f[0]][f[1]] = map[x][y] = PASSAGE;
 if ( x >= 2 && map[x-2][y] == WALL )
 frontiers.add( new int[]{x-1,y,x-2,y} );
 if ( y >= 2 && map[x][y-2] == WALL )
 frontiers.add( new int[]{x,y-1,x,y-2} );
 if ( x < width-2 && map[x+2][y] == WALL )
 frontiers.add( new int[]{x+1,y,x+2,y} );
 if ( y < height-2 && map[x][y+2] == WALL )
 frontiers.add( new int[]{x,y+1,x,y+2} );
 }
 }
 }
 @Override
 public String toString(){
 final StringBuffer b = new StringBuffer();
 for ( int x = 0; x < width + 2; x++ )
 b.append( WALL_CHAR );
 b.append( '\n' );
 for ( int y = 0; y < height; y++ ){
 b.append( WALL_CHAR );
 for ( int x = 0; x < width; x++ )
 b.append( map[x][y] == WALL ? WALL_CHAR : PASSAGE_CHAR );
 b.append( WALL_CHAR );
 b.append( '\n' );
 }
 for ( int x = 0; x < width + 2; x++ )
 b.append( WALL_CHAR );
 b.append( '\n' );
 return b.toString();
 }
}
</int[]>

Образец вывода new Maze(20,20).toString():

▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓ ▓▓▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓ ▓ ▓ ▓▓▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓▓▓▓▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓ ▓ ▓▓▓ ▓ ▓ ▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓ ▓▓▓ ▓ ▓ ▓▓▓ ▓▓
▓ ▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓▓▓ ▓▓▓▓▓▓▓▓▓▓
▓ ▓ ▓ ▓ ▓ ▓▓
▓ ▓▓▓▓▓▓▓ ▓ ▓▓▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓▓▓▓ ▓▓
▓ ▓ ▓▓
▓▓▓ ▓ ▓▓▓ ▓▓▓ ▓▓▓ ▓ ▓▓
▓ ▓ ▓ ▓ ▓ ▓ ▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓


Ваше решение выглядит неправильно. В частности, это лабиринт, и (если вы не можете ходить по диагонали) есть уникальный путь от каждого (открытого) местоположения друг к другу (открытое) место. Единственная проблема с ним, кажется, в стиле.

Если вы рассмотрите "правильный" лабиринт, который вы разместили, без внешней границы, и возьмите тупиковую ячейку, чтобы она была (0,0), вы можете наблюдать, что проходы и стены, в некотором смысле, чередуются. Каждая ячейка, где обе координаты являются четными, должна быть проходом, и каждая ячейка, где обе координаты нечетны, должна быть стеной. Таким образом, единственные ячейки, в которых у вас есть выбор, - это те, где одна координата четная, а другая - странная.

Пусть ячейка (x,y) находится в середине поля, где обе координаты четные. Эта ячейка должна быть проходом. Клетки (x-1,y), (x+1,y), (x,y-1) и (x,y+1) - окружающие его потенциальные стенки, а ячейки (x-2,y), (x+2,y), (x,y-2) и (x,y+2) квадраты на противоположностях тех стены, соответственно.

С помощью этой информации вы можете просто реализовать алгоритм с дополнительным требованием, чтобы на шаге 2 вы должны были выбрать ячейку, в которой обе координаты четные.


Попробуйте учесть стены с уникальным случайным весом в самом начале процедуры. Этот список весов никогда не изменится. Когда вы выберете следующую стену из списка доступных стен, выберите стену с минимальным весом.


Простой ответ на ваш вопрос заключается в том, что при добавлении края вам нужно проверить, берет ли край удаление стены, которая является последним соседом любой из соседних частей стены.

Это предотвратит подключение любых стен только к углу.


Сам по себе я придумал что-то совсем другое, прежде чем исследовал проблему вообще. Посмотрите, считаете ли вы, что это полезный подход.

Давным-давно, когда я увидел графику персонажей IBM PC (глифы, которые являются частью кодовой страницы), я думал о создании лабиринтов таким образом. Мой подход состоит из двух этапов:

  • Создание лабиринта в массиве целых чисел с использованием бит-кодированных значений 1-15 для указания направлений, открытых в каждой ячейке лабиринта.
  • Оказание его видимой форме. Так что стены не рассматриваются, пока я не покажу лабиринт.

Каждая ячейка начинается с 0 (не выбрана), а затем может быть включен любой из 4 бит (1 = вправо, 2 = вниз, 4 = левый, 8 = вверх). Наивно, вы можете просто выбрать случайное число от 1 до 15 в каждой ячейке, за исключением пяти вещей:

  • Начните с рисования "стены" коридоров и углов вокруг всего массива и оставьте проход в двух точках. Это самый простой способ справиться с граничными условиями.
  • Весовой выбор, так что тупики встречаются редко, а прямые или угловые коридоры являются общими, полные пересечения - нечастыми.
  • Сопоставьте каждую ячейку с уже установленными вокруг нее: если соседняя ячейка имеет соответствующий бит On (1 бит в ячейке слева и т.д.), заставьте этот бит в этой ячейке, и если это Выключить, отключить его в этой ячейке.
  • Найдите способ убедиться, что начало и конец соединения (требуются дополнительные исследования).
  • Управлять заполнением всех ячеек и не создавать пустоты (требуется больше исследований).

Здесь отображается "сырой" массив в терминах графических символов:

┌│───────┐ 
 │└─┐┌┐│ │ 
 ││┌┴┤│├─┐│ 
 │├┴─┘│└┐││ 
 │└─┐──┐│││ 
 │┌┬┴─┌┘│││ 
 ││├┐│└┬┘││ 
 │└┤│└┬┴─┤│ 
 │─┴┴─┘──┤│ 
 └───────│┘

При рендеринге результата я показываю каждую ячейку, используя сетку символов 3x4. Вот пример:

╔═══╡ ╞═══════════════════════════════╗
║░░░│ │░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░║
║░░╔╡ ╞════════════════════════════╗░░║
║░░║│ └───────┐┌──────┐┌──┐ ║░░║
║░░║│ ││ ││ │ ║░░║
║░░║└───────┐ ││ ┌┐ ││ │ ║░░║
║░░║┌──┐┌───┘ └┘ ││ ││ └───────┐║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║│ ││ ┌────┐ ││ ││ ┌────┐ │║░░║
║░░║│ └┘ └────┘ ││ ││ └───┐│ │║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║│ ┌───────────┘└──┘└───┐ ││ │║░░║
║░░║│ └───────┐┌──────────┐│ ││ │║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║└───────┐ │└───────┐ │└──┘│ │║░░║
║░░║┌───────┘ └───┐┌───┘ │┌──┐│ │║░░║
║░░║│ ││ ││ ││ │║░░║
║░░║│ ┌┐ ┌───────┘│ ┌───┘│ ││ │║░░║
║░░║│ ││ └───┐┌──┐│ └────┘ ││ │║░░║
║░░║│ ││ ││ ││ ││ │║░░║
║░░║│ ││ ┌┐ ││ │└───┐ ┌───┘│ │║░░║
║░░║│ └┘ ││ ││ └────┘ └────┘ │║░░║
║░░║│ ││ ││ │║░░║
║░░║└───┐ ││ │└───┐ ┌────────┐ │║░░║
║░░║┌───┘ └┘ └────┘ │┌───────┘ │║░░║
║░░║│ ││ │║░░║
║░░║└──────────────────┘└───────┐ │║░░║
║░░╚════════════════════════════╡ ╞╝░░║
║░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░│ │░░░║
╚═══════════════════════════════╡ ╞═══╝

Посмотрите, что вы можете сделать с помощью этого метода. (Разный выбор шрифта делает его лучше, чем здесь, все линии соединяются легко - конечно, должны быть моноширинными).

licensed under cc by-sa 3.0 with attribution.