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

Темы, связанные с проектированием и программированием roguelike-игр

Модераторы: Sanja, Максим Кич

Ответить
Siri0n
Сообщения: 31
Зарегистрирован: 19 авг 2013, 10:31

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

Сообщение Siri0n » 23 авг 2013, 06:17

Сначала дисклеймер:
Скрытый текст: ПОКАЗАТЬ
1. Я не считаю, что этот алгоритм - что-то супер-пуперское. Недавно я упомянул о нём с излишним пафосом. На самом деле - алгоритм как алгоритм.
2. Когда-то он был очень коряво написан на Delphi, сейчас я постепенно переписываю его на JS. Постепенно - в том смысле, что я начал с упрощённой версии и понемногу, по мере появления свободного времени, буду добавлять новые фичи. Каждая новая версия будет на своей веб-страничке, чтобы можно было проследить развитие.
3. С точки зрения вычислительной эффективности он, пожалуй, сосёт. В императивном стиле сгенерить карту можно значительно быстрее.
Теперь перейдём к делу. Наверное, все знают, что такое клеточный автомат. Если кто вдруг не знает, он может почитать мою дипломную работу Википедию. Эти штуки мне всегда нравились, и я хотел приспособить их для чего-нибудь полезного. Для вышеупомянутого диплома я сочинил алгоритм шифрования с помощью сабжа, а потом попробовал использовать КА в мирных целях, а именно - для генерации карты.

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

Далее на каждом шаге происходит примерно следующее: клетка, находящаяся в состоянии "chaos", у которой хотя бы одна из соседних клеток находится в состоянии "floor", с некоторыми вероятностями может перейти либо в "floor", либо в "wall". Если у клетки есть соседи в состоянии "wall", переход в состояние "wall" более вероятен. Процесс продолжается, пока нам не надоест на некотором шаге состояния всех клеток не окажутся теми же, что и на предыдущем.

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

Посмотреть, как это работает, можно здесь: http://sirion.ho.ua/cell_maze/230813.html

Аватара пользователя
Apromix
Мастер
Сообщения: 1236
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

Re: Генерация карты с помощью клеточного автомата

Сообщение Apromix » 23 авг 2013, 06:48

Всего через несколько перезагрузок я к своему удивлению получил вот это :D

Изображение

Siri0n
Сообщения: 31
Зарегистрирован: 19 авг 2013, 10:31

Re: Генерация карты с помощью клеточного автомата

Сообщение Siri0n » 23 авг 2013, 06:51

Батенька, вы часом не тестировщик? :D
Действительно, с интервалом рандома на единичку ошибся. Уже поправил.

Аватара пользователя
Oreyn
Сообщения: 297
Зарегистрирован: 07 авг 2013, 14:59

Re: Генерация карты с помощью клеточного автомата

Сообщение Oreyn » 23 авг 2013, 07:11

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

Следующий шаг, чтобы сделать генератор более настраиваемым - сделать шансы на превращение клетки в стену/пол/узкий коридор изменяемыми в зависимости от того, во что была превращена клетка родитель. (Я ведь правильно понимаю, что каждая обработанная клетка добавляет своих необработанных соседей в стек обработки?) Делаем N параметров аффинити - стена/пол/коридор, которые показывают структуру вероятности превращения. Превращение "родительской клетки" в каждый из указанных типов уменьшает/увеличивает соответствующее аффинити на дельту, которую задаем генератору. Хотим уровень с маленькими ветвистыми комнатами - задаем большую дельту и каждый сгенеренный пол будет сильнее увеличивать шансы появления стены в следующей клетке, и наоборот.
Плюс, идея как можно бороться с быстрым окончанием работы алгоритма. Храним 4 параметра min/max по x/y обработанных клеток лабиринта. Если алгоритм заканчивается и процентное отношение количества обработанных клеток меньше желаемого (например мы задали генератору покрыть 80% из доступных 5 000 клеток) Он находит сторону с которой осталось больше свободного места зная min/max x/y сгенеренного лабиринта и общие размеры поля генерации и насильно превращает крайнюю стенку в пол и запускает алгоритм генерации дальше от этой точки. Аналогично если нужное кол-во клеток обработано насильно закрываем оставшиеся в стеке обработки стенками и заканчиваем алгоритм. Вот и настройка генератора которая управляет размером уровня.

Аватара пользователя
Apromix
Мастер
Сообщения: 1236
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

Re: Генерация карты с помощью клеточного автомата

Сообщение Apromix » 23 авг 2013, 07:20

Siri0n писал(а):Батенька, вы часом не тестировщик? :D
Действительно, с интервалом рандома на единичку ошибся. Уже поправил.
Распиши алгоритм по детальней после того места, как на карту ставится первая ячейка с полом? Попробую реализовать как алгоритм №18 в BeaRLib.

Siri0n
Сообщения: 31
Зарегистрирован: 19 авг 2013, 10:31

Re: Генерация карты с помощью клеточного автомата

Сообщение Siri0n » 23 авг 2013, 07:41

Oreyn писал(а):Признаться думал что автор куда глобальней поработал с клеточными автоматами, а не просто реализовал первую приблизительную идею которая выходит из самой идеи применения клеточных автоматов.
Автор поработал куда глобальнее. См. дисклеймер, пункт 2. Версия на делфи умела много интересных вещей. К несчастью, она развалилась под тяжестью своих фич - быдлокод такой быдлокод...
Oreyn писал(а):Следующий шаг, чтобы сделать генератор более настраиваемым - сделать шансы на превращение клетки в стену/пол/узкий коридор изменяемыми в зависимости от того, во что была превращена клетка родитель. (Я ведь правильно понимаю, что каждая обработанная клетка добавляет своих необработанных соседей в стек обработки?) Делаем N параметров аффинити - стена/пол/коридор, которые показывают структуру вероятности превращения.
Стека обработки нет, каждый шаг мы тупо проходимся по всему полю. И для этого есть причина: в дальнейшем определённые изменения смогут происходить и с нехаотическими клетками, причём почти с каждой. А реализация со стеком для "плотного" КА ненамного эффективнее наивной реализации (для совсем "плотного" - вообще проигрывает).

Честно говоря, не хочется использовать какие-то "магические" (основанные на специально подобранных арифметических операциях) функции. В случае КА предпочитаю табличное задание. Однако в дальнейшем вероятности действительно будут более тонко меняться в зависимости от окружения, начальных настроек и прочих фаз Сатурна.
Oreyn писал(а):Плюс, идея как можно бороться с быстрым окончанием работы алгоритма. Храним 4 параметра min/max по x/y обработанных клеток лабиринта. Если алгоритм заканчивается и процентное отношение количества обработанных клеток меньше желаемого (например мы задали генератору покрыть 80% из доступных 5 000 клеток) Он находит сторону с которой осталось больше свободного места зная min/max x/y сгенеренного лабиринта и общие размеры поля генерации и насильно превращает крайнюю стенку в пол и запускает алгоритм генерации дальше от этой точки. Аналогично если нужное кол-во клеток обработано насильно закрываем оставшиеся в стеке обработки стенками и заканчиваем алгоритм. Вот и настройка генератора которая управляет размером уровня.
Идея рабочая, но не слишком соответствует духу КА, где всё построено на локальных взаимодействиях. Я пошёл другим путём - скоро увидите, каким.
Apromix писал(а):Распиши алгоритм по детальней после того места, как на карту ставится первая ячейка с полом? Попробую реализовать как алгоритм №18 в BeaRLib.
Вечером распишу. Но пока алгоритм ещё достаточно приблизительный.

Аватара пользователя
Maelstrom
Мастер
Сообщения: 2062
Зарегистрирован: 26 ноя 2006, 14:19
Откуда: г. Усть-Кирдык
Контактная информация:

Re: Генерация карты с помощью клеточного автомата

Сообщение Maelstrom » 23 авг 2013, 08:41

Плакался тут, понимаешь, плакался, что все бяки и ничего не покажешь #-o

Алгоритм выглядит хороши для локального заполнения небольших площадей, получается комнаты рваной формы, или вообще не комнаты. Но как единственный алгоритм на весь экран выглядит так себе.
Айв кнгенгах Йог-Сотот

Siri0n
Сообщения: 31
Зарегистрирован: 19 авг 2013, 10:31

Re: Генерация карты с помощью клеточного автомата

Сообщение Siri0n » 23 авг 2013, 08:50

Maelstrom писал(а):Алгоритм выглядит хороши для локального заполнения небольших площадей, получается комнаты рваной формы, или вообще не комнаты. Но как единственный алгоритм на весь экран выглядит так себе.
Зависит от типа местности же.

Siri0n
Сообщения: 31
Зарегистрирован: 19 авг 2013, 10:31

Re: Генерация карты с помощью клеточного автомата

Сообщение Siri0n » 23 авг 2013, 17:52

В общем, алгоритм следующий (псевдокод):

Код: Выделить всё

на каждом шаге{
    для каждой некрайней клетки{
        соседи = [соседСправа, соседСлева, соседСверху, соседСнизу]
        если(клетка.состояние == хаос){
            если(соседи.содержат(элемент.состояние == пол)){
                если(соседи.содержат(элемент.состояние == стена)){
                    клетка.новоеСостояние = рандом(стена: 60%, пол: 40%)
                }иначе{
                    клетка.новоеСостояние = рандом(стена: 40%, пол: 60%)
                }
            }
        }
    }
    торт = ложь
    для каждой некрайней клетки{
        если(клетка.состояние != клетка.новоеСостояние){
            клетка.состояние = клетка.новоеСостояние
            торт = истина
        }
    }
    если(не торт){
        любуемся результатом
    }
}

Аватара пользователя
Oreyn
Сообщения: 297
Зарегистрирован: 07 авг 2013, 14:59

Re: Генерация карты с помощью клеточного автомата

Сообщение Oreyn » 23 авг 2013, 21:17

Скрытый текст: ПОКАЗАТЬ
Siri0n писал(а):В общем, алгоритм следующий (псевдокод):

Код: Выделить всё

на каждом шаге{
    для каждой некрайней клетки{
        соседи = [соседСправа, соседСлева, соседСверху, соседСнизу]
        если(клетка.состояние == хаос){
            если(соседи.содержат(элемент.состояние == пол)){
                если(соседи.содержат(элемент.состояние == стена)){
                    клетка.новоеСостояние = рандом(стена: 60%, пол: 40%)
                }иначе{
                    клетка.новоеСостояние = рандом(стена: 40%, пол: 60%)
                }
            }
        }
    }
    торт = ложь
    для каждой некрайней клетки{
        если(клетка.состояние != клетка.новоеСостояние){
            клетка.состояние = клетка.новоеСостояние
            торт = истина
        }
    }
    если(не торт){
        любуемся результатом
    }
}
Пока что мало всего. И главное мало от использования самих автоматов. Все это пока что быстрее реализует алгоритм заливки через стек с тем же условием формирования стены или пола. Даешь применение итераций с изменением клеток с не начальным "хаотическим" состоянием, а также методы контроля за размерами уровня исходя из локальных операций между автоматами.

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 29 гостей