Будучи студентом Школы запуска , вы создаете множество небольших проектов, проверяющих свои знания по определенным темам курса. Они полезны и часто достаточно мотивируют, но они не вызывают радости от настоящего побочного проекта: того, который вам нравится и который вызывает слишком много энтузиазма. Итак, во время рождественских каникул у меня впереди несколько тихих дней - отличное время для такого побочного проекта!
Изначально я вдохновился конкурсом Пришествие кода, ежегодным мероприятием, на котором дается 24 кодовых головоломки, которые проверяют ваши навыки решения проблем и алгоритмическое мышление. В частности, мне понравились две головоломки: одна связана с клеточными автоматами, а другая - с моделированием пошаговых сражений между эльфами и гоблинами в пещере (да, у головоломок обычно есть бессмысленная предыстория).
Клеточные автоматы: простой, но умный алгоритм
Я прочитал о Cellular Automata после решения той конкретной головоломки Пришествие кода. Один из самых популярных вариантов Cellular Automaton - Игра жизни Конвея. Он имитирует сетку с живыми клетками, которые развиваются в соответствии с набором правил.
Прочитав страницу Википедии, я построил свою собственную реализацию на Ruby, и это оказалось проще, чем ожидалось, потому что на самом деле это не так уж сложно. Вы можете увидеть мою «Игру жизни» в действии:
Так что же такое Cellular Automaton? В общем, он описывает преобразование двумерной конструкции по набору правил. Звучит слишком абстрактно? Давайте посмотрим, что влечет за собой Game of Life.
Начнем с пустой сетки. В идеале он был бы бесконечно большим, но мы можем ограничить его, определив простой двумерный массив ячеек, например:
rows, cols = x, y
Array.new(rows) { Array.new(cols) }
Затем нам понадобится начальная конфигурация. То есть мы случайным образом назначаем каждой из ячеек в этой сетке одно из двух состояний, например мертв или жив в Game of Life. На следующем рисунке светло-серые клетки живы, а темные клетки мертвы.
В основе клеточного автомата лежат правила трансформации, которые определяют судьбу каждой клетки в сетке на следующем этапе эволюции. Эти правила смотрят на соседей каждой ячейки.
У каждой ячейки ровно восемь соседей. Количество соседей можно определить с помощью матрицы смежности:
adjacent = [ [-1,-1], [0, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [0, 1], [1, 1] ]
Глядя на эти относительные положения каждой клетки, мы можем просто подсчитать количество живых клеток. После этого мы применяем четыре простых правила, чтобы увидеть, выживет или умрет клетка в следующем поколении. Вот эти правила:
- живая клетка, у которой меньше двух соседей, умирает в следующем поколении. Это называется голоданием.
- живая клетка продолжает существовать в следующем поколении, когда у нее будет ровно два или три соседа.
- живая клетка умирает в следующем поколении, если у нее более трех соседей. Это называется перенаселением.
- если у мертвой клетки ровно три соседа, она рождается заново в следующем поколении.
В этой конфигурации, например, все живые клетки (окрашенные в серый цвет) будут жить в следующем поколении, потому что у каждой из них ровно два или три соседа. Такая конфигурация привела бы к стабильному клеточному организму, который не меняется в ходе моделирования, за исключением случаев, когда другой организм подходит слишком близко и нарушает равновесие.
Однако в этом случае вылупившиеся живые клетки умрут от перенаселения в следующем поколении, потому что у них более трех соседей.
Вот и все, перевод этих четырех правил в код - это все, что нужно для реализации Игры жизни Конвея.
От «Игры в жизнь» до создания подземелий
Я бы оставил все как есть, если бы через несколько дней не решалась другая головоломка Появление кода. Сама головоломка была связана с симуляцией группы гоблинов и эльфов, но в ней использовалась сложная среда, которая создавалась уникальным образом для каждого участника Advent of Code. Это напомнило мне определенный тип видеоигр, который мне нравился: так называемые Rogue-like.
Rogue-like назван в честь их самого старого предка: игры под названием Rogue. В нем вы управляете персонажем-героем, обычно представленным в игре символом @, и вы исследуете подземелья и пещеры, убивая монстров и находя по пути сокровища. Все Rogue-подобные игры разделяют один важный основной принцип (помимо того, что они чертовски сложны): большие части игры генерируются процедурно, что означает, например, что каждая карта уровня будет быть случайно созданным алгоритмом. Конечный результат обычно отображается с помощью простых символов ASCII. Эта эстетика напомнила мне реализацию Game of Life, и я начал задаваться вопросом: смогу ли я генерировать случайные подземелья и пещеры с несколькими модификациями моего алгоритма Game of Life? И если да, могу ли я сам написать небольшую Rogue-подобную игру?
Я хотел проверить свое предположение, прежде чем строить какие-либо большие планы, поэтому я изменил свой алгоритм Game of Life. Я удалил правило перенаселения, потому что хотел получить массивные структуры со стенками вместо крошечных плавающих клеточных организмов. Затем я создал набор параметров на основе оставшихся правил, которые я мог настроить и посмотреть, будет ли результат чем-то близким к тому, что я себе представлял:
WALL_CHANCE = 0.25 # chance for an initial wall ITERATIONS = 7 # no. of generations to simulate WALL_EVOLUTION = 5 # minimum neighbor walls to grow a new one WALL_STARVE = 2 # minimum neighbor walls to not vanish
Для большинства из этих параметров нашлось место оптимальным, и для получения потрясающих результатов не потребовалось много настроек:
Они действительно были похожи на наскальные пещеры! И разнообразие сгенерированных карт было потрясающим. Я был счастлив, и идея моего побочного проекта воплотилась в жизнь.
Позже я узнал, что Cellular Automata используются в разработке игр для очень похожих целей (хотя часто более изощренным и умным способом). Кроме того, они используются для моделирования естественного поведения в определенных биологических или химических моделях, поэтому они довольно универсальны.
Что ж, теперь у меня появилась классная карта, но не более того. Как я могу превратить это в полноценный игровой процесс?
Перейдите к части 2 или посмотрите репозиторий проекта на GitHub (мой алгоритм создания пещер можно найти в файле lib / cavegen.rb). Просто следуйте инструкциям в Readme, чтобы установить и воспроизвести.
