Алгоритм Эллера для генерации лабиринтов

Это топик-перевод статьи Eller's Algorithm. В ней рассказывается о способе программной генерации лабиринтов. Дальнейшее повествование идет от лица автора.

 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  
|__   |__       __ __|__   |   __|  |  |  |  |
|__   |__   |__|   __ __|   __ __      |     |
|        |  |  |     |  |__      |__|  |  |  |
|__|__|  |  |   __|   __|__   |   __|__|  |__|
|   __|  |     |__ __ __|  |  |__|  |     |  |
|  |  |  |  |__|  |__   |  |   __|__ __|  |  |
|  |__    __    __ __    __|  |   __   |  |  |
|  |  |  |  |      __|  |   __|  |  |__|  |  |
|  |     |     |__   |  |  |  |  |  |__    __|
|  |  |__|__|__ __|  |     |  |  |      __|  |
|__ __|  |  |  |__   |__|   __|     |   __ __|
|   __|  |   __|__      |__   |__|  |__    __|
|  |  |     |  |     |__|  |   __    __|   __|
|   __|  |__ __|__|      __|  |  |     |  |  |
|   __ __   |      __|__|  |__   |  |  |__|  |
|__ __ __|__ __|__ __ __ __ __|__|__|__ __ __|

Алгоритм Эллера позволяет создавать лабиринты, имеющие только один путь между двумя точками. Сам по себе алгоритм очень быстр и использует память эффективнее, чем другие популярные алгоритмы (такие как Prim и Kruskal), требуя памяти пропорционально числу строк. Это позволяет создавать лабиринты большого размера при ограниченных размерах памяти.



В интернете очень мало информации об алгоритме Эллера. Лучший источник, который я смог найти (сайт Walter Pullen) имеет всего один параграф с описанием, которое полезно, но недостаточно для реализации алгоритма. Также, алгоритм описанный в книге Mathematics and Physics for Programmers, скорее всего, не работает. Я обдумал недостающие части и уверен, что алгоритм который я описал, в самом деле является алгоритмом Эллера. Кроме того, вы можете найти дополнительную информацию о нем в статье Maze Generation: Eller's Algorithm.

Описание алгоритма

Замечание: мы предполагаем, что самая левая ячейка имеет границу слева, а самая правая — справа.

1. Создайте первую строку. Ни одна ячейка не будет являться частью ни одного множества.
2. Присвойте ячейкам, не входящим в множество, свое уникальное множество.
3. Создайте правые границы, двигаясь слева направо:
   1. Случайно решите добавлять границу или нет
      1. Если текущая ячейка и ячейка справа принадлежат одному множеству, то создайте границу между ними (для предотвращения зацикливаний)
      2. Если вы решили не добавлять границу, то объедините два множества в которых находится текущая ячейка и ячейка справа.
4. Создайте границы снизу, двигаясь слева направо:
   • Случайно решите добавлять границу или нет. Убедитесь что каждое множество имеет хотя бы одну ячейку без нижней границы (для предотвращения изолирования областей)
     1. Если ячейка в своем множестве одна, то не создавайте границу снизу
     2. Если ячейка одна в своем множестве без нижней границы, то не создавайте нижнюю границу
5. Решите, будете ли вы дальше добавлять строки или хотите закончить лабиринт
   1. Если вы хотите добавить еще одну строку, то:
      1. Выведите текущую строку
      2. Удалите все правые границы
      3. Удалите ячейки с нижней границей из их множества
      4. Удалите все нижние границы
      5. Продолжайте с шага 2
   2. Если вы решите закончить лабиринт, то:
      1. Добавьте нижнюю границу к каждой ячейке
      2. Двигаясь слева направо:
         1. Если текущая ячейка и ячейка справа члены разных множеств, то:
            1. Удалите правую границу
            2. Объедините множества текущей ячейки и ячейки справа
            3. Выведите завершающую строку

Пример

В этом примере мы создадим простой лабиринт. Мы начнем создавать его построчно, двигаясь сверху вниз, слева направо. Каждая ячейка в строке будет принадлежать множеству. Мы визуализируем это проставляя номера множеств и записывая эти номера в ячейку, согласно их принадлежности. Каждая ячейка может иметь границу справа и/или снизу. Мы предполагаем, что границы есть слева от самой первой и справа от самой последней ячейки в строке.

Шаг 1: Создание первой строки

	 ___ ___ ___ ___ ___ ___ ___ ___
	|                               |

Шаг 2: Присоединим все ячейки не принадлежащие множествам к свои новым множествам

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1   2   3   4   5   6   7   8 |

Шаг 3: Создадим границы справа

	 ___ ___ ___ ___ ___ ___ ___ ___
	|(1   2)  3   4   5   6   7   8 |

Если мы решим не создавать границу, то объединим множества

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  (1   3)  4   5   6   7   8 |

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1   1  (1 | 4)  5   6   7   8 |

	...

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1   1   1 | 4   4 | 6   6   6 |

Шаг 4: Создание нижних границ

Убедимся, что каждое множество ячеек имеет хотя бы одну ячейку без нижней границы. Если это условие не будет выполнено, то мы создадим изолированные области.

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  _1_ _1_| 4  _4_| 6   6  _6_|

Шаг 5А: Создание новой строки

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  _1_ _1_| 4  _4_| 6   6  _6_| <-- Выведем эту строку
	| 1  _1_ _1_| 4  _4_| 6   6  _6_| <-- наша предыдущая строка стала текущей

Удалим правые границы

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  _1_ _1_| 4  _4_| 6   6  _6_|
	| 1  _1_ _1_  4  _4_  6   6  _6_|

Если ячейка имеет нижнюю границу, удалим ее из множества:

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  _1_ _1_| 4  _4_| 6   6  _6_|
	| 1  ___ ___  4  ___  6   6  ___|

Удалим нижние границы

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  _1_ _1_| 4  _4_| 6   6  _6_|
	| 1           4       6   6     |

Продолжая с шага 2:

Шаг 2: Присоединим ячейки, не принадлежащие множествам к своим уникальным множествам

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___| 
	| 1   2   3   4   5   6   6   7 |

Шаг 3: Добавим границы справа

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|(1 | 2)  3   4   5   6   6   7 | <-- добавлена граница

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 |(2   3)  4   5   6   6   7 | <-- граница не добавлена, объединим множества 2 и 3

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2  (2   4)  5   6   6   7 | <-- граница не добавлена, объединим множества 2 и 4

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2  (2 | 5)  6   6   7 | <-- добавлена граница

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2   2 |(5 | 6)  6   7 | <-- добавлена граница

Следующие две ячейки члены одного множества, поэтому мы ОБЯЗАНЫ добавить границу. Если не добавим, то это приведет к циклам в нашем лабиринте

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2   2 | 5 |(6 | 6)  7 | <-- должны добавить границу

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2   2 | 5 | 6 |(6   7)| <-- граница не добавлена, объединим множества 6 и 7

Шаг 4: нижние границы

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2   2 | 5 | 6 | 6   6 |

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

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2  _2_ _2_| 5 |_6_| 6  _6_|

Вы можете добавить столько строк, сколько захотите

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|_1_  1 | 3   3 | 7  _7_ _7_| 8 |

Шаг 5Б: Завершение лабирина

Последняя строка отличается от обычных тем, что 1) каждая ячейка имеет границу снизу 2) каждая ячейка должна принадлежать одному множеству.

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

Начнем с создания обычной строки и добавления нижней границы к каждой ячейке.

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|___    |       |    ___ ___|   |
	|_1_ _1_|_3_|_3_|_7_ _7_|_8_ _8_|

Закончим лабиринт, разрушая границы между ячейками, принадлежащими различным множествам и объединяя их в одно.

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|___    |       |    ___ ___|   |
	|_1_ (1_|_3)|_3_|_7_ _7_|_8_ _8_|

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|_ _    |       |    ___ ___|   |
	|_1_ _1_ _1_|(1_|_7) _7_|_8_ _8_|

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|___    |       |    ___ ___|   |
	|_1_ _1_ _1_|_1_ _1_ (1_|_8) _8_|

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|___    |       |    ___ ___|   |
	|_1_ _1_ _1_|_1_ _1_ _1_ _1_ _1_|

В конце должен получиться идеальный лабиринт, в котором нет циклов (между двумя ячейками есть только один путь) и изолированных частей (ячейки или групп ячеек, которые не связаны с другими частями лабиринта). Теперь вы можете назначить любые две ячейки соответственно «входом» и «выходом».