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

Введение

Алгоритм был написан как часть работы на получение степени бакалавра и основан на статье Ma et al (2014). Целью работы было ускорение алгоритма и дополнение его новыми функциями. Я вполне доволен результатом, потому что мы сделали алгоритм достаточно быстрым, чтобы использовать его во время выполнения игры. После завершения бакалаврской работы мы решили превратить её в статью и отправить на конференцию Game-ON 2018.

Алгоритм

Для создания уровня игры алгоритм получает в качестве входных данных набор полигональных строительных блоков и граф связности уровня (топологию уровня). Узлы графа обозначают комнаты, а рёбра определяют связи между ними. Цель алгоритма — назначить каждому узлу графа форму и расположение комнаты таким образом, чтобы никакие две формы комнат не пересекались, и каждая пара соседних комнат могла соединяться дверьми.

Что такое шум Перлина?

Шум Перлина придуман в 1983 году Кеном Перлином (получившим за это достижение премию Американской Академии кинематографических искусств и наук). Видите ли, в те времена все стремились к фотореализму, но его всегда не хватало. Кен Перлин придуман этот алгоритм шума, чтобы избавиться от жалкого «компьютерного» внешнего вида 3D-моделей. Шум — это генератор случайных чисел в компьютерной графике. Это случайный неструктурированный паттерн, он полезен в тех случаях, когда требуется источник подробных деталей, недостающих в очевидной структуре¹. Шум Перлина — это многомерный алгоритм, используемый в процедурной генерации, текстурах, генерации рельефа, генерации карт, генерации поверхностей, генерации вершин, и так далее, и тому подобное.

Одним из проектов, которые я долго мечтал реализовать, были модульные боты задач с памятью. Конечная цель проекта заключалась в создании мира с существами, способными действовать независимо и коллективно.

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

Я уже реализовал базовую систему конвейера задач на Javascript (потому что это упростило мою жизнь), но мне хотелось чего-то более надёжного и масштабируемого, поэтому этот проект я написал на C++. На это меня сподвиг конкурс по реализации процедурного сада в сабреддите /r/proceduralgeneration (отсюда и соответствующая тема).

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

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

Часть 1. Общий алгоритм поиска

Введение

Поиск пути — это одна из тех тем, которые обычно представляют самые большие сложности для разработчиков игр. Особенно плохо люди понимают алгоритм A*, и многим кажется, что это какая-то непостижимая магия.

Цель данной статьи — объяснить поиск пути в целом и A* в частности очень понятным и доступным образом, положив таким образом конец распространённому заблуждению о том, что эта тема сложна. При правильном объяснении всё достаточно просто.

Учтите, что в статье мы будем рассматривать поиск пути для игр; в отличие от более академических статей, мы опустим такие алгоритмы поиска, как поиск в глубину (Depth-First) или поиск в ширину (Breadth-First). Вместо этого мы постараемся как можно быстрее дойти от нуля до A*.

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

Классификация лабиринтов

Лабиринты в целом (а значит, и алгоритмы для их создания) можно разбить по семи различным классификациям: размерности, гиперразмерности, топологии, тесселяции, маршрутизации, текстуре и приоритету. Лабиринт может использовать по одному элементу из каждого класса в любом сочетании.

Искажения, бесшовный шум и как с ними работать.

Генерируем планету

Один из простейших способов генерации планеты — использование шума. Если мы решим выбрать его, то у нас есть пара возможных вариантов. Давайте рассмотрим каждый и определим лучший:

• Шум Перлина (Perlin Noise) — самый простой вариант. Шум Перлина был разработан Кеном Перлином в 1983 году, он имеет пару недостатков — визуальные артефакты и довольно низкая по сравнению с другими вариантами скорость при генерации больших изображений.
• Симплекс-шум (Simplex Noise) — разработан Кеном Перлином в 2001 году как попытка устранения недостатков шума Перлина; это вполне достойное и быстрое решение, однако обладающее серьёзным недостатком: использование трёхмерного симплекс-шума защищено патентом, что делает его довольно дорогостоящим.
• Открытый симплекс-шум (Open Simplex Noise) — был разработан KDotJPG с одной простой целью: создать современную и бесплатную версию симплекс-шума, относительно быструю и без искажений.

Из этих трёх лично я предпочитаю Open Simplex Noise, который использую в своих личных проектах. Стоит заметить, что в текущей реализации OpenSimplexNoise для получения простого доступа к масштабу, октавам и порождающим значениям потребуется дополнительная работа. В Интернете есть множество информации о том, что делает каждый из этих элементов, и я крайне рекомендую вам её изучить. Однако в своей статье я буду говорить не об этом.

Введение

---

«Что получится, если мы заменим числа с плавающей запятой на рациональные числа и попытаемся отрендерить изображение?»

Такой вопрос я задал себе после размышлений над твитом исследователя и преподавателя компьютерной графики Моргана Макгвайра. Он рассуждал о том, насколько сильно студенты компьютерных наук удивляются, когда впервые узнают, что для хранения привычных нам чисел с плавающей запятой в современных компьютерах нужно идти на компромиссы. И эти компромиссы делают сложными простые задачи, например, проверку принадлежности точки треугольнику. Проблема, разумеется, заключается в том, что проверка нахождения четырёх точек в одной плоскости (копланарности) с помощью определителя или какого-нибудь векторного умножения (а на самом деле это одно и то же) никогда не даст значение, точно равное нулю, чего требуют эти математические методы. Даже если бы настоящие вычисления нахождения на одной плоскости были бы точны, те же компромиссы с точностью почти с вероятностью в 1,0 дали бы ответ, что сами четыре точки не копланарны.

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


Простая сцена, трассировка пути в которой выполнена рациональной арифметикой. Здесь используется система чисел «с плавающей чертой дроби», а не числа с плавающей запятой.

Сегодня российская космическая отрасль немало работает по иностранным заказам и в международных проектах. Однако прежние заказчики — США и Европа — сокращают или собираются сокращать сотрудничество. Может ли «Роскосмос» удержать прежних и заинтересовать новых заказчиков?

Машинное обучение как оно есть сейчас

В популярных методах машинного обучения программа не выучивает алгоритм. Классификатор, нейронная сеть или, для большей очевидности, методы регрессии выучивают в лучшем случае функцию (в математическом, а не программистском смысле): имея входные данные, выдать выходные данные. Это может быть в лучшем случае единственным шагом алгоритма и не понятно, как масштабировать такое решение на целый алгоритм вместо одного шага. Без возможности выучивать алгоритмы, эти методы далеки от AGI (общего искусственного интеллекта — Artificial General Intelligence). На пути к AGI неплохо бы найти способ, чтобы программы выучивали алгоритмы с ветвлением, циклами и подпрограммами. Далее следует научить программы понимать другие программы. Далее понимать и улучшать саму себя. Не настаиваю что именно этим путём люди пройдут к AGI, но это моё скромное виденье.

Программа как прикладной искусственный интеллект

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

— Куды? – грозно спросила бабка, встав спиной к двери.

— Куды надо. – передразнил неопрятный парень, с красными глазами, взъерошенными волосами и в черной футболке с надписью «Король и Шут».

— Ну-ка, не пущай его! – встала со скамейки другая бабка. – Ишь, вумные, без очереди лезут! Мы тут с шости утра стоим!

— Не стоите, а сидите. – ответил парень. – Дайте пройти, я по делу.

— Знаем мы, по какому ты делу! – вступила симпатичная девушка лет тридцати. – Только спросить?

— Да что с вами такое, а? – возмутился парень. – Работаю я здесь! Я – программист!

Однажды настанет день, когда команды в программировании будут выглядеть вроде «эй, компьютер, сделай-ка мне вот эту хреновину».

Что там будет под капотом, ни одна живая душа уже не поймет. Команда «хреновина» интерпретируется в абзац с описанием, который интерпретируется в ключевые слова, который интерпретируется в набор векторных обозначений, который интерпретируется в какой-нибудь С, который скомпилируется в…

и где-то там внизу превратится в электрические импульсы на железяках.

Программистами станут лощеные гуманитарии с «высокими вербальными способностями, коммуникативными навыками и умением быть няшей в команде». Слава богу до этого дня, как до Аляски на упряжке, но каждый раз изобретая очередной Kotlin, мы этот день приближаем.

Просто я задумался — а не стали ли наши ЯПы уже чем-то таким? Чуть более умным эквивалентом фразы «компьютер, сделай хреновину». Кучей формализованных протоколов для электричества, про которое мы уже забыть забыли. Штукой, которая все сильнее рвет нашу связь с механической реальностью.

Я часто слышу фразу: «Фил, отступись, хватит думать обо всякой чепухе». Но блин, будь проклят тот день, когда на Хабре напишут «хватит думать».