Опыт генерирования пещерной игровой карты с помощью клеточного автомата

Существует множество алгоритмов генерации карты. В данной статье я опишу, как мне приходилось реализовывать один из таких алгоритмов.

О чем речь?

Клеточный автомат - решетка ячеек, состояние которых меняется по заданным правилам. В нашем случае ячейки будут иметь только два состояния: "стена" и "пустота" и изначально заполнены случайно. В качестве правил при генерации пещер обычно задаются следующие утверждения:

1. Клетка "стены" становится "пустой", если вокруг нее меньше Х стен.
2. Клетка "пустоты" становится "стеной", если вокруг нее больше Y стен.

От подобранных Х и Y зависит вся работоспособность генератора. При неправильно подобранных X и Y вся карта может стать "пустой" или полностью заполниться "стенками". Более того, при определенных Х и Y мы получим игру "Жизнь".

Особенности реализации

Однако, мы здесь не за тем, чтобы залипать на метаморфозы ячеек. Нам нельзя допустить, чтобы карта стала слишком пустой или заполненной. Дабы избежать этого, мы ограничим длительность работы клеточного автомата. Другими словами:

Вместо

while (true) { Применить правила ко всем клеткам; }

Мы напишем

for (int i = 0; i < T; i++) { Применить правила ко всем клеткам; }

Осталось только подобрать переменные X, Y, T (можно еще поиграться с изначальным заполнением клеток, но я просто сделал появление клетки "стенки" и "пустой" клетки равновероятными). Вы можете поэкспериментировать сами, я для себя выбрал значения: X = 4, Y = 4, T = 5.

Казалось бы, вот и все?

Но как бы не так. В некоторых случаях мы можем получать несвязные пещеры. Как это разрешить? Для начала получим список всех несвязанных пещер. Сделать это можно при помощи алгоритма Floodfill (вообще - с помощью любого обхода графа, который мы получим, если возьмем все пустые ячейки в качестве вершин и свяжем ребрами только соседние).

Теперь нужно придумать, как их связать. Самый простой и очевидный вариант - связать каждую из пещер с каждой (и получить полносвязный граф). Все пещеры связаны, все хорошо, да? Нет.

Пещера 1 и пещера 3 не просто связаны "через" пещеру 2, так еще и "сквозь" нее

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

Чтобы избежать этой проблемы, мы можем использовать один из следующих алгоритмов:

1. Измерить кратчайшие расстояния между всеми пещерами, отсортировать их по возрастанию и связывать пещеры с минимальным расстояниямим между ними (проверяя, чтобы они не были связаны через уже связанные пещеры), пока не получим связную пещеру (граф). Данный алгоритм называется алгоритмом Краскала
2. Взять одну из пещер. Соединить с самой близкой к ней пещерой. Затем соединить с самой близкой пещерой к ним, из оставшихся и т.д., пока не получим связную пещеру. Это алгоритм Прима

Отлично, теперь мы имеем связный граф. В принципе, на этом можно и остановиться. Однако я посчитал сгенерированные пещеры довольно скучными: ведь в ней нельзя ходить кругами!. В нашем графе пещер нет циклов. Исправить это можно, выби рая на каждом этапе любого из вышеприведенных алгоритмов не одну связь с минимальным расстоянием между пещерами, а сразу несколько (к примеру 5). Таким образом, при связывании пещер будет шанс соединения уже косвенно соединенных пещер (т.е. получения цикла в нашем графе).

Вот что генерируется у меня с реализацией всех шагов ():

Некоторые проходы заблокированы "завалами", но, не учитывая их, видно, что граф пещер связный и с циклами

Заключение

Возможно из статьи вы узнали о многих алгоритмах и не знаете как их реализовывать? Поискать более подробное объяснение с реализацией можно в следующих источниках:

• Emaxx
• Конспекты ИТМО
• Книга Th. Cormen "Introduction to algorithms"

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