Какой алгоритм генерации лабиринта в игре Netwalk?

исходный код доступен в Google Code, так что вы можете сами прочитать его и узнать! Лабиринт создается функцией generate_maze в game.c, строки 78 и далее.

Обновление: попробуйте демоверсию!

Netwalk создает лабиринт, запуская рандомизированную версию алгоритма Прима для поиска минимальное связующее дерево. Алгоритм Прима итеративно выращивает дерево по одной ветке за раз, начиная с исходного узла (или узлов: в данном случае «сервера», темно-синего прямоугольника двойной высоты). В любой момент выполнения алгоритма структура данных выглядит примерно так:

Клетки, окрашенные в зеленый цвет, — это клетки на концах растущих ветвей: у них все еще есть по крайней мере один пустой сосед, в который они могли бы врасти. На каждом шаге алгоритм выбирает одну из этих зеленых ячеек, а затем выбирает одного из его пустых соседей⁽¹⁾ и добавляет ветвь к этому соседу. Эта новая ветвь блокирует рост соседних ветвей в ее направлении. Когда у ветки больше нет пустых соседей⁽²⁾, она удаляется из списка зеленых ячеек.

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

[Я идеализировал детали в нескольких местах: (1) на самом деле алгоритм Netwalk немного наивен и просто выбирает случайное направление, и если сосед в этом направлении непуст, он ничего не делает и продолжает к следующей итерации. (2) Ветви без пустых соседей своевременно не обнаруживаются: они удаляются из зеленого списка только в том случае, если они случайно выбраны. Демонстрация исправляет эти незначительные недостатки.]