Алгоритм создания 2d лабиринта [закрыто]

Какой алгоритм вы использовали в прошлом для создания простого 2d лабиринта?

Существует много разных способов изготовления лабиринтов. Их огромный список и их описания здесь: http://www.astrolog.org/labyrnth/algrithm.htm

Я думаю, что использовал тот, который описан в разделе «Идеальный».

Я предпочитаю сильно намотанные лабиринты, которые создает алгоритм Крускала.

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

Я буду использовать следующие термины:

• график
  • сам лабиринт.
• Узел
  • место в лабиринте. На квадратном лабиринте это квадратная клетка.
• край
  • связь между двумя узлами. На квадратном лабиринте это бар длиной 1.
• Дерево Группа
  • набор узлов, которые могут быть пустыми, организованы в виде дерева

И из них мы получаем:

1. Создайте группу GTG для группы дерева графиков , содержащую группы деревьев
2. Заполните GTG одной группой деревьев, содержащей один узел, для каждого местоположения в вашем лабиринте
3. Создать набор ребер E
4. Заполните E каждым действительным краем в вашем лабиринте
5. Пока в GTG более одной группы , и пока E не пусто:
6. Выберите случайное ребро RE из E
7. Определить конечные точки p1 и p2 для rE
8. Удалить РЭ из Е
9. Проверьте, к каким группам p1 и p2 относятся ( p1g и p2g соответственно).
10. Если p1g и p2g различаются, соедините группы деревьев p1g и p2g в p1 -> p2 и переписайте все группы владения одним деревом в другое, таким образом соединяя деревья.
11. Вернитесь к шагу 5.
12. Если у вас не осталось ребер, но имеется более одного дерева, либо график не связан, либо есть ошибка.
13. Если у вас есть только одно дерево, у вас есть полный лабиринт без петель.

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

Вот пример википедии о работе на компьютере.

Один простой способ - составить список северных и западных стен, а затем их переставить. Дайте каждой комнате номер. Затем взорвать одну из стен в списке, пока две комнаты не имеют одинаковое число, а затем распространить одно из номеров на все другие комнаты с одинаковым номером. Продолжайте, пока не выбежите из стен. Это работает для прямоугольных лабиринтов или, на самом деле, для любого другого лабиринта, где вы можете дать список «потенциально связанных комнат». Плюс, это довольно просто программировать.

Я также хотел бы взглянуть на некоторые алгоритмы, используемые в разработке Roguelike. В Rogue Basin есть хороший стартовый ресурс

Хороший прогон есть здесь: https://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/

Основные шаги были:

• Место комнаты
• Заполните пустое пространство лабиринтом
• Соедините комнаты с лабиринтом
• Выкроить тупики

Код здесь: https://github.com/munificent/hauberk/blob/db360d9efa714efb6d937c31953ef849c7394a39/lib/src/content/dungeon.dart

Вы спросили, какой я использовал, поэтому я обязательно отвечу на это. Я использовал Рекурсивный алгоритм Backtracker в моей игре-лабиринте на Rootbeer Games .

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