Рубрика «клеточные автоматы»

Использование алгоритма Прима для генерации соединённых друг с другом пещер - 1 Использование алгоритма Прима для генерации соединённых друг с другом пещер - 2 Использование алгоритма Прима для генерации соединённых друг с другом пещер - 3

Я решил объяснить один из алгоритмов генерации карты, используемых в моей игре In the House of Silence. Главное преимущество этого способа заключается в том, что в отличие от других алгоритмов, он никаким образом не может сгенерировать карту с разделёнными частями.

Генерация идеального лабиринта

Использование алгоритма Прима для генерации соединённых друг с другом пещер - 4

Как понятно из названия, я использую хорошо задокументированный рандомизированный алгоритм Прима. Описание этого алгоритма можно найти на Википедии, однако вы можете применить любой другой алгоритм генерации лабиринтов.

Для понятности я привёл псевдокод, описывающий алгоритм Прима. Будет довольно просто приспособить его под любой язык программирования.
Читать полностью »

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

Создание процедурной анимации смерти при помощи автоматов падающего песка - 1

Автоматы падающего песка

Автомат падающего песка — это клеточный автомат, симулирующий перемещение песчинок и создание куч песка под действием гравитации.

Правила просты:

  • Если ячейка под песчинкой пуста, то песчинка движется в пустую ячейку (см. (a)).
  • Если ячейка под песчинкой заполнена, но свободна ячейка внизу слева или внизу справа, то песчинка движется туда (см. (b)). Если свободны обе, то одна из них выбирается случайным образом.
  • В остальных случаях песчинка не движется.

Читать полностью »

image

Этот пост — о программе на Rust…

$ cargo install conway-nes

…выводящей двоичный файл NES…

$ conway-nes > life.nes

…в котором выполняется конвеевская игра «Жизнь»!

$ fceux life.nes    # fceux is a NES emulator

Запустив игру на эмуляторе, нажмите любую кнопку контроллера, чтобы начать заново с рандомизированного состояния.
Читать полностью »

Julia и клеточные автоматы - 1

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

Читать полностью »

image

Клеточный автомат — это система, состоящая из клеток с численными значениями в сетке, а также из правил, определяющих поведение этих клеток. Многократно применяя правило к каждой клетке сетки параллельно с визуализацией сетки, часто можно получить эффект некоего эволюционирующего организма со сложным и замысловатым поведением, даже если правила относительно просты.

Клеточные автоматы имеют различные формы, виды и размерности. Наверно, самым знаменитым клеточным автоматом является конвеевская игра «Жизнь» (Conway's Game of Life, GOL). Она состоит из двухмерной сетки, в которой каждая клетка содержит двоичное значение (живая или мёртвая). Сопутствующие правила на основании состояния соседних клеток определяют, должна ли клетка быть мёртвой или живой. Правила гласят, что живая клетка умирает от одиночества, если вокруг неё меньше 2 живых клеток. Если живы больше трёх соседних клеток, она погибает от перенаселённости. Другими словами, клетка «выживает», если вокруг неё ровно 2 или 3 живых соседних клеток. Чтобы мёртвая клетка ожила, у неё должно быть ровно 3 живых соседних клеток, в противном случае она остаётся мёртвой. Пример автомата GoL, итеративно проходящий несколько состояний, показан ниже.

Game of Life

Ещё один знаменитый вариант клеточного автомата одномерен; он называется элементарным клеточным автоматом (Elementary Cellular Automaton, ECA). Именно его мы реализуем в этом посте.
Читать полностью »

30.000$ за решение задач о Правиле 30 для клеточных автоматов — конкурс от Стивена Вольфрама - 1
Оригинал перевода в моём блоге

Прямая трансляция Стивена Вольфрама о конкурсе (на английском)

Поясним для читателей, что означает «Правило 30» — это элементарный клеточный автомат (см. Wiki), состояние которого (правило построения нового уровня ячеек на основе старого) в двоичной системе счисления задается как 0-0-0-1-1-1-1-0, что можно интерпретировать как 30 в десятичной системе счисления.

Итак, с чего все началось? — «Правило 30»

Как может быть так, что что-то невероятно простое производит на свет что-то невероятно сложное? Прошло уже почти 40 лет с того момента, как я впервые познакомился с Правилом 30, но оно до сих пор поражает меня и приводит в восторг. На долгое время оно стало моим личным любимым открытием в истории науки, за эти годы оно изменило все мое мировоззрение и привело меня к разнообразным новым типам понимания науки, технологий, философии и многому другому.

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

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

Правило 30 чрезвычайно просто:

Существует последовательность строк черных и белых клеток (ячеек) и, учитывая конкретную строку чёрно-белых ячеек, определяются цвета ячеек в строке ниже, рассматривая каждую ячейку в отдельности и ее смежных соседних ячеек, затем к ним применяется следующее простое правило подстановки, а именно:

30.000$ за решение задач о Правиле 30 для клеточных автоматов — конкурс от Стивена Вольфрама - 2

Код

RulePlot[CellularAutomaton[30]]

[Посмотрите ролик, в котором за пару минут рассказывается суть клеточных автоматов и Правила 30 — примечание переводчика]

Читать полностью »

Генерация подземелий и пещер для моей игры - 1

На этой неделе я начал работать над новой темой: генерацией подземелий и пещер. Я использовал разбиение пространства для генерации комнат, алгоритмы генерации лабиринтов для генерации коридоров и клеточные автоматы для придания пещерам более естествненного внешнего вида.

Разбиение пространства

Существует множество способов генерации комнат для подземелья (случайное размещение, генерация на основе агентов, с использованием separation steering behavior или физического движка, и т.д.). Но мой любимый метод — это разбиение пространства, потому что оно легко контролируется и расширяется.

Способов разбиения пространства тоже очень много: разделение на сетки, двоичное разбиение пространства, разбиение пространства деревом квадрантов, диаграммы Вороного и т.д. Я решил использовать двоичное разбиение пространства, потому что оно хорошо подходит для генерации прямоугольных комнат. Этот метод получил популярность благодаря статье на RogueBasin.

Единственная сложность этого алгоритма — выбор позиции разделения. Если мы не наложим ограничение на позицию разделения, то будем получать странные разбиения пространства:

Генерация подземелий и пещер для моей игры - 2

Такого поведения можно избежать несколькими способами. Один из них — ограничить позицию разделения двумя соотношениями длин сторон, например, в интервале от 30% до 70% или от 40% до 60%. Другой способ — использовать вместо равномерного распределения нормальное или биномиальное, благодаря этому повысится вероятность разделения по центру стороны, а не по краям. Эти способы устраняют проблему, но сложно понять, как конкретно параметры влияют на окончательный результат.
Читать полностью »

ПривеТ! Решил поделиться с читателями своими небольшими экспериментами с системами частиц в трехмерном пространстве. За основу взял публикацию на Хабре об экспериментах с частицами в 2D пространстве.
Жизнь на частицах 3D - 1

Читать полностью »

Всем привет! Сегодня я расскажу о своих экспериментах с системами частиц. Основной целью было нахождение простых правил, которые бы порождали интересное поведение.

Классический пример системы с простыми правилами и сложным поведением — клеточные автоматы, именно на них я и ориентировался, пытаясь подобрать правила. Конечно же, для клеточных автоматов правила будут в большинстве случаев проще. Но частицы могут быть красивее!

Под катом много мегабайт гифок.

Жизнь на частицах - 1

Читать полностью »

image

Процедурно генерируемые карты — базовая особенность roguelike. Для жанра, который почти является синонимом понятия «случайность» (и на то есть причины), рандомизированные карты стали простейшим способом демонстрации его ключевого элемента, потому что они влияют на многие аспекты геймплея — от стратегии исследования и тактического позиционирования до расположения предметов и врагов.

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

Поэтому рандомизированные карты обеспечивают нам бесконечную реиграбельность, каждый раз ставя перед нами разные задачи. Кроме того, удовольствие усиливается тем, что прогресс игрока зависит от его собственного навыка, а не от проб и ошибок. Схема каждой новой карты на 100% неизвестна, что тоже добавляет напряжённости процессу её изучения.

Конечно же, преимущества процедурных карт бессмысленны без большой вариативности механик и контента — однообразный hack-and-slash здесь не подойдёт. Поэтому все roguelike, выдержавшие испытание временем, имеют глубокий геймплей.

Этот пост является результатом моей работы над генерацией карт для Cogmind.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js