Исходный код доступен в Google Code, так что вы можете прочитать его сами и узнать!Лабиринт генерируется функцией generate_maze в game.c, строки 78ff.
Обновление: попробуйте демонстрацию!
Netwalk генерирует лабиринт, выполняя рандомизированную версию Алгоритм Прима , чтобы найти минимальное остовное дерево .Алгоритм Прима итеративно выращивает дерево один раз за раз, начиная с исходного узла (или узлов: в данном случае «сервер», темно-синий прямоугольник двойной высоты).В любой момент выполнения алгоритма структура данных выглядит примерно так:
Ячейки, окрашенные в зеленый цвет, являются ячейками на кончиках растущих ветвей: ониеще есть хотя бы один пустой сосед, в которого они могли бы вырасти.На каждом шаге алгоритм выбирает одну из этих зеленых ячеек, а затем выбирает одного из своих пустых соседей (1) и добавляет ответвление к этому соседу.Эта новая ветвь блокирует соседние ветви от растущих в своем направлении.Когда у ветви больше нет пустых соседей (2) , тогда она удаляется из списка зеленых ячеек.
В конечном итоге зеленый список пуст: ни одна из ветвей сети не имеетникаких пустых соседей.Это означает, что плата заполнена, и каждая ячейка подключена к серверу по одному пути.
[Я идеализировал детали в нескольких местах: (1) на самом деле алгоритм Netwalk немного наивен и просто выбирает случайное направление, и если сосед в этом направлении не пуст, он ничего не делает и переходит к следующей итерации.(2) Ветви без пустых соседей своевременно не обнаруживаются: они удаляются из зеленого списка, только если они выбраны.Демонстрация исправляет эти незначительные ошибки.]