Процедурная генерация в играх: что это такое и зачем она нужна

Генерация в трехмерном пространстве

Также мы не можем оставить без внимания статью о генерации 3D-лабиринтов: «Bake Your Own 3D Dungeons With Procedural Recipes» — основная сложность которого заключается в правильной ориентации элементарных частей лабиринта: коридоров, комнат и лестниц.

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

Линейный конгруэнтный ГПСЧ

Линейный конгруэнтный ГПСЧ(LCPRNG)?—?это распространённый метод для генерации псевдослучайных чисел. Он не обладает криптографической стойкостью. Этот метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой формулой. Получаемая последовательность зависит от выбора стартового числа?—?т.е. seed. При разных значениях seed получаются различные последовательности случайных чисел. Пример реализации такого алгоритма на JavaScript:

Многие языки программирования используют LСPRNG (но не именно такой алгоритм(!)).

Как говорилось выше, такую последовательность можно предсказать. Так зачем нам ГПСЧ? Если говорить про безопасность, то ГПСЧ?—?это проблема. Если говорить про другие задачи, то эти свойства?—?могут сыграть в плюс. Например для различных спец эффектов и анимаций графики может понадобиться частый вызов random. И вот тут важны распределение значений и перформанс! Секурные алгоритмы не могут похвастать скоростью работы.

Еще одно свойство?—?воспроизводимость. Некоторые реализации позволяют задать seed, и это очень полезно, если последовательность должна повторяться. Воспроизведение нужно в тестах, например. И еще много других вещей существует, для которых не нужен безопасный ГСЧ.

Триангуляция Делоне и построение графа

Теперь мы берём все центральные точки главных комнат и скармливаем их процедуре Делоне. Процедуру пишем самостоятельно или же пользуемся чьим-то готовым вариантом из Интернета. На моё счастье, такая процедура уже написана Yonaba. Как видно ниже, она берёт точки и выстраивает из них треугольники.

Когда у нас есть треугольники, можно строить граф. Это довольно простая процедура, при условии, что у вас на руках есть библиотека/структура данных графа. Если вы ещё этого не сделали, будет полезным присвоить объектам/структурам, отвечающим за комнаты, уникальные идентификаторы, чтобы эти идентификаторы можно было добавить в граф вместо утомительного копирования.

Встраиваемые заготовки

На выработку подходящего набора правил у меня ушло два часа.Шаги по встраиванию заготовки в стену пещеры.

1. Выбираем случайную заготовку для заданной встречи и поворачиваем её, чтобы она смотрела в случайную сторону света.
2. Выбираем случайную открытую ячейку в пещере, которая должна стать одним передним углом местоположения заготовки. Затем на основании длины передней грани заготовки определяем, где должен находиться противоположный угол. Если второй угол находится за пределами пещеры, то пробуем подобрать другие точки.
3. Измеряем расстояние вдоль воображаемых сторон заготовки, пока она не столкнётся со стеной.
4. У каждой заготовки есть задаваемое вручную значение «максимальной протяжённости» (maxProtrusion). Оно является ограничением глубины, на которую она может вдаваться в родительскую пещеру. Если расстояние, измеренное по любой из сторон, превышает значение maxProtrusion, то сдвигаем углы обратно к стене, пока оба значения не будут в пределах этого значения. (Если расстояния, при котором значение протяжённости можно соблюсти с обеих сторон, то возвращаемся к этапу 2.)
5. Проверяем правильность целевой области заготовки: «внешний прямоугольник» не может содержать лестниц (потому что он перезапишет их) а «внутренний прямоугольник» может быть только землёй — не допускаются даже открытые области той же пещеры, потому что они могут создавать неожиданные/нежелательные дополнительные входы в область заготовки.
6. Также проверяем, что существует стена хотя бы толщиной в одну ячейку вдоль сторон и задней части внутреннего прямоугольника (то есть он, например, не касается непосредственно другой открытой пещеры или области заготовки).
7. Располагаем заготовку на карте! Затем преобразуем в стену все ячейки земли вокруг внешней границы, которые соседствуют с открытым пространством заготовки.
8. Добавляем объекты в соответствии с описанием заготовки, например, терминал, позволяющий открыть дверь и подобрать кучу отличного оружия.

REXPaintПример встраиваемой заготовки в игре.

Часть 5. Заготовки подземелий

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

Применение

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

Ссылки [ править ]

1. ^ a b Делоне, Борис (1934). «Sur la sphère vide» . Bulletin de l’Académie des Sciences de l’URSS, Classe des Sciences Mathématiques et Naturelles . 6 : 793–800.
2. ↑ Фукуда, Комей. «Часто задаваемые вопросы в вычислениях многогранников» . www.cs.mcgill.ca . Проверено 29 октября 2018 года .
3. Перейти ↑ Seidel, Raimund (1995). «Теорема о верхней границе для многогранников: простое доказательство ее асимптотической версии». Вычислительная геометрия . 5 (2): 115–116. DOI10.1016 / 0925-7721 (95) 00013-Y .
4. ^ Мейеринг, JL (1953), «Площадь границы раздела, длина ребра и количество вершин в кристаллических агрегатах со случайным зарождением» , Philips Research Reports , 8 : 270–290, заархивировано из оригинала на 2017- 03-08. Как указано на Dwyer, Рекс А. (1991), «Многомерные диаграммы Вороного в линейной ожидаемого времени», дискретных и вычислительной геометрии , 6 (4): 343-367, DOI10.1007 / BF02574694 , МР 1098813.
5. ^ Эдельсбруннер, Герберт ; Тан, Тиоу Сенг; Ваупотич, Роман (1992), » Временной алгоритм O ( n 2  log  n ) для минимальной угловой триангуляции» , SIAM Journal on Scientific and Statistical Computing , 13 (4): 994–1008, CiteSeerX 10.1.1.66. 2895 , DOI10,1137 / 0913058 , MR 1166172 , архивируются с оригинала на 2017-02-09 , извлекаются 2017-10-24.
6. ^ Ся, Ge (2011), «перегон фактор триангуляционных меньше , чем 1,998″, Computing Research Repository — КОРР , 42 , DOI10,1137 / 110832458.
7. ^ а б Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010). Триангуляции, структуры для алгоритмов и приложений . Алгоритмы и вычисления в математике. 25 . Springer.
8. ^ Guibas Леонидас ; Столфи, Хорхе (1985). «Примитивы для манипулирования общими подразделениями и вычисления Вороного». Транзакции ACM на графике . 4 (2): 74–123. DOI10.1145 / 282918.282923 . S2CID 52852815 .
9. ^ Уртадо, Ф .; М. Ной; Дж. Уррутия (1999). «Перевернутые грани в триангуляции» . Дискретная и вычислительная геометрия . 22 (3): 333–346. DOI10.1007 / PL00009464 .
10. ^ Гибас, Леонидас Дж .; Кнут, Дональд Э .; Шарир, Миха (1992). «Рандомизированное пошаговое построение диаграмм Делоне и Вороного». Алгоритмика . 7 (1–6): 381–413. DOI10.1007 / BF01758770 . S2CID 3770886 .
11. ^ де Берг, Марк; Отфрид Чеонг ; Марк ван Кревельд; Марк Овермарс (2008). Вычислительная геометрия: алгоритмы и приложения . Springer-Verlag. ISBN  978-3-540-77973-5. Архивировано из оригинального 28 октября 2009 года . Проверено 23 февраля 2010 .
12. ^ Эдельсбруннер, Герберт ; Шах, Нимиш (1996). «Инкрементальные топологические перевернутые работы для регулярных триангуляций» . Алгоритмика . 15 (3): 223–241. DOI10.1007 / BF01975867 . S2CID 12976796 .[ мертвая ссылка ]
13. ^ Blelloch, Гай; Гу, Ян; Шун, Джулиан; и Сун, Ихан. Параллелизм в рандомизированных инкрементальных алгоритмах. Архивировано 25 апреля 2018 г. в Wayback Machine . SPAA 2016. DOI: 10.1145 / 2935764.2935766.
14. ^ Guibas Леонидас; Столфи, Хорхе (апрель 1985 г.). «Примитивы для манипулирования общими подразделениями и вычисления Вороного». Транзакции ACM на графике . 4 (2): 74–123. DOI10.1145 / 282918.282923 .
15. ^ «ВЫЧИСЛЕНИЕ ОГРАНИЧЕННЫХ ТРЕУГОЛЬНИКОВ ДЕЛОНЕ НА ПЛОСКОСТИ» . www.geom.uiuc.edu . Архивировано из оригинального 22 сентября 2017 года . Проверено 25 апреля 2018 года .
16. Перейти ↑ Dwyer, Rex A. (ноябрь 1987 г.). «Более быстрый алгоритм« разделяй и властвуй »для построения триангуляций Делоне». Алгоритмика . 2 (1–4): 137–151. DOI10.1007 / BF01840356 .
17. Перейти ↑ Leach, G. (июнь 1992 г.). Улучшение оптимальных алгоритмов триангуляции Делоне в наихудшем случае »: 15. CiteSeerX 10.1.1.56.2323 .
18. ^ Cignoni, P .; К. Монтани; Р. Скопиньо (1998). «ДеУолл: быстрый алгоритм триангуляции Делоне« разделяй и властвуй »в E dКомпьютерный дизайн . 30 (5): 333–341. DOI10.1016 / S0010-4485 (97) 00082-1 .
19. ^ Сравнение последовательных алгоритмов триангуляции Делоне «Архивная копия» . Архивировано из оригинального 08 марта 2012 года . Проверено 18 августа 2010 .
20. ^ «Алгоритмы триангуляции и структуры данных» . www.cs.cmu.edu . Архивировано 10 октября 2017 года . Проверено 25 апреля 2018 года .
21. ^ «S-корпус» . s-hull.org . Проверено 25 апреля 2018 года .
22. ^ Франц Ауренхаммер; Рольф Кляйн; Дер-цай Ли (26 июня 2013 г.). Диаграммы Вороного и триангуляции Делоне . Мировая научная издательская компания. С. 197–. ISBN 978-981-4447-65-2.
23. ^ Стерлинг Дж. Андерсон; Сисир Б. Каруманчи; Карл Ягнемма (5 июля 2012 г.). «Планирование и контроль на основе ограничений для безопасной, полуавтономной работы транспортных средств» . 2012 IEEE Интеллектуальные Транспортные средства Symposium . IEEE. DOI10.1109 / IVS.2012.6232153 .

Сравнение с итеративным алгоритмом построения триангуляции Делоне с использованием kD-дерева

Описание итеративного алгоритма

Коротко опишу вышеуказанный алгоритм. При поступлении очередной точки мы с помощью kD-дерева (советую почитать про него где-нибудь, если вы не знаете) находим довольно близкий к ней уже построенный треугольник. Затем обходом в глубину ищем треугольник, в который попадает сама точка. Достраиваем ребра в вершины найденного треугольника и фактически выполняем шаг (4) из нашего алгоритма для новых четырехугольников. Так как точка может быть вне триангуляции, то для упрощения предлагается накрыть все точки большим треугольником (построить его заранее), это решит проблему.

Сходство алгоритмов

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

Различия алгоритмов

В итеративном алгоритме локализация точки (поиск нужного треугольника) происходит в среднем за O( logN ), на вышеуказанных распределениях в среднем происходит 3 перестроения (как показано в ) при условии произвольного порядка подачи точек. Таким образом заметающая прямая выигрывает время у итеративного алгоритма в локализации, но проигрывает его в перестроениях (которые, напомню, довольно тяжелые). Ко всему прочему итеративный алгоритм работает в режиме онлайн, что также является его отличительной особенностью.

Ссылки [ править ]

1. ↑ Брайан Ино (8 июня 1996 г.). «Речь в Сан-Франциско, 8 июня 1996 г.» . журнал inmotion . Проверено 7 ноября 2008 .
2. ^ «Искусственный интеллект и интерактивные цифровые развлечения» . AIIDE.org . Проверено 12 июня +2016 .
3. ^ Кук, Майкл (10 августа 2016 г.). «Чужие языки: как мы говорим о процедурной генерации» . Гамасутра . Проверено 7 октября 2019 года .
4. ^ Браун, Джозеф Александр; Скирия, Марко (2018). «Процедурная генерация для настольных игр: подходы, ориентированные на пользователя, с ограничениями на вычислительные ресурсы». SEDA 2018: Материалы 6-й Международной конференции по разработке программного обеспечения для оборонных приложений . Международная конференция по разработке программного обеспечения для оборонных приложений. Рим, Италия. С. 44–54.
5. ^ Смит, Джиллиан (2015). Аналоговая история создания процедурного контента . Основы цифровых игр, 2015 г. Пасифик-Гроув, Калифорния . Проверено 7 октября 2019 года .
6. ^ Хэтфилд, Том (2013-01-29). «Восстание рогаликов: жанр развивается» . GameSpy . Проверено 24 апреля 2013 .
7. ^ «Безумный лабиринт» . Atari Mania .
8. ^ Франсис Спуффорд (18 октября 2003). «Мастера своей вселенной» . Хранитель.
9. Рианна Мосс, Ричард (1 января 2016 г.). «7 применений процедурной генерации, которые должны изучить все разработчики» . Гамасутра . Проверено 1 января 2016 года .
10. ↑ Бейкер, Крис (9 августа 2016 г.). „ Нет человека Sky“: Как игры Строительство Сами по себе» . Rolling Stone . Проверено 9 августа +2016 .
11. ^ Гизен, Fabian (8 апреля 2012). «Метапрограммирование для безумцев» . Блог ryg .
12. ↑ Куо, Райан (19 апреля 2012 г.). «Почему в Borderlands 2 самое стильное оружие в играх» . Wall Street Journal . Проверено 21 апреля 2016 года .
13. ^ Пекхэм, Мэтт (8 августа 2016 г.). «NO MAN’S SKY ЯВЛЯЕТСЯ ДИКОЙ АМБИЦИОЗНОЙ, ВНЕШНЕЙ ОБЪЕМОМ И ОГРОМНЫМ ВЫЗОВОМ ДЛЯ СТАТУСНОЙ ИНДУСТРИИ ВИДЕОИГРОВ» . Время . Проверено 9 августа +2016 .
14. ^ Хачатурян, Раффи (18 мая 2015). «Мир без конца: создание полномасштабного цифрового космоса» . Летопись игр. Житель Нью-Йорка . 91 (13). С. 48–57 . Дата обращения 5 августа 2015 .
15. ^ Уилсон (16 июля 2015 г.). «Как 4 дизайнера создали игру с 18,4 квинтиллионами уникальных планет» . Быстрая компания . Дата обращения 9 августа 2015 .
16. ^ «О массиве» . Огромное программное обеспечение . Проверено 12 июня +2016 .
17. ^ Вставка: Почему «Мандалорианец» использует виртуальные наборы на зеленом экране | Movies Insider, опубликовано 6 июня 2020 г.
18. ^ Gartenberg, Хаим (20 февраля 2020). «Как Mandalorian объединился с Epic Games, создателем Fortnite, чтобы создать свои цифровые наборы» . Грань . Архивировано 20 февраля 2020 года . Проверено 20 февраля 2020 года .

Имеют ли смысл наши случайные размещения?

Since we are using random locations and dimensions for our rooms, we are bound to overlap with previously created rooms as we fill our dungeon. Well, we already coded up a simple method in order to help us take care of the problem.

Each time we attempt to place a new room, we simply call on each pair of rooms within the entire list. This function returns a Boolean value: if the rooms are overlapping, and otherwise. We can use that value to decide what to do with the room we just attempted to place.

Check back at the function. You can see how the x and y values overlap and return .

The key here is the Boolean; it’s set to the return value of , and so is if (and only if) your rooms are overlapping. Once we break out of the loop, we check this variable and, if it’s false, we can carve out the new room. Otherwise, we just discard the room and try again until we’ve hit our maximum number of rooms.

Алгоритм Лемера

Самый простой приемлемый метод генерации случайных чисел — алгоритм Лемера. (Для простоты я использую термин «генерация случайных чисел» вместо более точного термина «генерация псевдослучайных чисел».) Выраженный в символьном виде, алгоритм Лемера представляет собой следующее:

На словах это звучит так: «новое случайное число является старым случайным числом, умножаемым на константу a, после чего над результатом выполняется операция по модулю константы m». Например, предположим, что в некий момент текущее случайное число равно 104, a = 3 и m = 100. Тогда новое случайное число будет равно 3 * 104 mod 100 = 312 mod 100 = 12. Вроде бы просто, но в реализации этого алгоритма много хитроумных деталей.

Чтобы создать демонстрационную программу, я запустил Visual Studio, выбрал шаблон C# Console Application и назвал проект RandomNumbers. В этой программе нет значимых зависимостей от .NET Framework, поэтому подойдет любая версия Visual Studio.

После загрузки кода шаблона в окно редактора я переименовал в окне Solution Explorer файл Program.cs в более описательный RandomNumbersProgram.cs, и Visual Studio автоматически переименовала класс Program за меня. В начале кода я удалил все лишние выражения using, оставив только ссылки на пространства имен верхнего уровня System и Collections.Generic.

Затем я добавил класс с именем LehmerRng для реализации RNG-алгоритма Лемера. Код показан на рис. 2. Версия алгоритма Лемера за 1988 год использует a = 16807 и m = 2147483647 (которое является int.MaxValue). Позднее, в 1993 году Лемер предложил другую версию, где a = 48271 как чуть более качественную альтернативу. Эти значения берутся из математической теории. Демонстрационный код основан на знаменитой статье С. К. Парка (S. K. Park) и К. У. Миллера (K. W. Miller) «Random Number Generators: Good Ones Are Hard to Find».

Рис. 2. Реализация алгоритма Лемера

Проблема реализации в том, чтобы предотвращать арифметическое переполнение. Алгоритм Лемера использует ловкий алгебраический трюк. Значение q является результатом m / a (целочисленное деление), а значение r равно m % a (m по модулю a).

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

RNG Лемера вызывается в методе Main демонстрационной программы:

Каждый вызов метода Next возвращает значение в диапазоне .

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

Завершаем игру

FpsMovementмоей книгиTriggerEventRouterFpsMovementLighting SettingsMazeConstructor

Generated

TriggerEventRouter

MazeConstructorGameController

1. Первое, что мы добавили — сериализованные поля для объектов в сцене.
2. Добавлено несколько частных переменных для отслеживания таймера и очков игры, а также того, найдена ли цель в лабиринте.
3. инициализируется так же, как и раньше, но теперь использует новые методы, которые не просто вызывают .
4. используется для запуска всей игры сначала, а не для переключения уровней внутри игры. Таймеру присваиваются исходные значения, очки сбрасываются, после чего создаётся лабиринт.
5. переходит к новому уровню, не перезапуская заново всю игру. Кроме создания нового лабиринта, этот метод располагает игрока в начальной точке, сбрасывает цель и снижает лимит времени.
6. проверяет, активен ли игрок, а затем обновляет время, оставшееся на прохождение уровня. После завершения времени игрок деактивируется и начинается новая игра.
7. и — это функции обработки событий, передаваемые TriggerEventRouter в MazeConstructor. записывает, что цель была найдена, а затем увеличивает количество очков. проверяет, найдена ли цель, и если это так, то деактивирует игрока и запускает новый лабиринт.

CanvasHierarchyPlayerTimeScoreShow Debug

Генерация лабиринтов с использованием клеточного автомата

Каждый программист хотя бы раз писал «Жизнь» — клеточный автомат, придуманный математиком Конвэем. Так почему бы не использовать схожую идею для генерации лабиринтов? Суть предложенного алгоритма состоит в реализации всего двух шагов: сначала все поле заполняется случайным образом стенами — т.е. для каждой клетки случайным образом определяется, будет ли она свободной или непроходимой — а затем несколько раз происходит обновление состояния карты в соответствии с условиями, похожими на условия рождения/смерти в «Жизни».

В источнике — на странице статьи «Generate Random Cave Levels Using Cellular Automata» — вы можете поэкспериментировать с интерактивной демкой, устанавливая различные значения для генерации: количество итераций обновления, граничные значения для жизни/смерти клетки и т.п. — и увидеть результат. Там же рассказывается о подводных камнях реализации.

Определения и постановка задачи

Триангуляция

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

Триангуляция Делоне

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

Замечание: для заданного множества точек, в котором никакие 4 точки не находятся на одной окружности, существует ровно одна триангуляция Делоне.

Условие Делоне

Пусть на множестве точек задана триангуляция. Будем говорить, что некоторое подмножество точек удовлетворяет условию Делоне, если триангуляция, ограниченная на это подмножество, является триангуляцией Делоне для него.

Критерий для триангуляции Делоне

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

Замечание: для невыпуклых четырехугольников условие Делоне всегда выполнено, а для выпуклых четырехугольников (вершины которого не лежат на одной окружности) существует ровно 2 возможные триангуляции (одна из которых является триангуляцией Делоне).

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

Генерирование данных лабиринта

GameController

MazeDataGeneratorMazeConstructor

MazeConstructor

1. будет использоваться алгоритмом генерирования данных для определения того, пусто ли пространство. В конструкторе класса этой переменной назначается значение по умолчанию, но она сделана , чтобы другой код мог управлять настройкой генерируемого лабиринта.
2. Один из методов (в этом случае ) снова пока пуст и оставлен заготовкой, которую мы заполним позже.

MazeConstructor

MazeDataGenerator

1. Для каждой ячейки сетки код сначала проверяет, выходит ли текущая ячейка за пределы сетки (то есть находится ли какой-то из индексов на границе массива). Если это так, то он ставит стену, присваивая 1.
2. Далее код проверяет, делятся ли координаты на 2 нацело, чтобы выполнять действия в каждой второй ячейке. Также здесь есть дополнительная проверка на описанное выше значение для пропуска случайным образом этой ячейки и продолжения обхода массива.
3. Наконец, код присваивает значение 1 текущей ячейке и случайно выбранной соседней ячейке. Код использует несколько тернарных операций для прибавления к индексу массива 0, 1 или -1, получая таким образом индекс соседней ячейки.

Построение триангуляции Делоне

КУРСОВОЙ ПРОЕКТ

ПОСТРОЕНИЕ ТРИАНГУЛЯЦИИ
ДЕЛОНЕ

по дисциплине «Структуры
и алгоритмы обработки данных»

Введение

1. Общее описание триангуляции делоне

1.1 Анализ литературы по теме

1.2 Основные определения и свойства

1.3 Метод пустого шара Делоне. Построение в общем случае

1.4 Применение триангуляции Делоне

2. Описание алгоритмов построения

2.1 Жадный алгоритм

2.2 Алгоритм «Удаляй и строй»

2.3 Алгоритм «Строй, разбивая»

2.4 Алгоритм с индексированием центров треугольников k-D — деревом

3. Оценка эффективности алгоритмов

3.1 Простой итеративный алгоритм

3.2 Итеративный алгоритм с индексированием треугольников

3.3 Итеративный алгоритм с индексированием центров треугольников
k-D-деревом

3.4 Веерный алгоритм

4. Программная часть

Заключение

Список использованной литературы

Введение

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

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

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

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

Цель работы и задачи: изучить один из
итеративных алгоритмов построения триангуляции Делоне.

)        Изучить основные определения и теоремы задачи
триангуляции Делоне;

2)      Рассмотреть основные виды итеративных алгоритмов
построения триангуляции;

)        Реализовать алгоритм «Удаляй и строй»
построения триангуляции Делоне.

1. Общее
описание триангуляции делоне

Задача построения триангуляции.

Делоне является одной из базовых в вычислительной геометрии.
К ней сводятся многие другие задачи, она широко используется в машинной графике
и геоинформационных системах для моделирования поверхностей и решения
пространственных задач. Впервые задача построения триангуляции Делоне была поставлена
в 1934 г. в работе советского математика Бориса Николаевича Делоне.

Триангуляцией Делоне для множества точек S на
плоскости называют триангуляцию DT (S), такую что никакая точка A из S не
содержится внутри окружности, описанной вокруг любого треугольника из DT (S),
такого, что ни одной из вершин его не является точка A.

Уход от клеточного поля

Тут есть несколько интересных вариантов.

Во-первых. Как скелеты животных подобны друг другу почти с точностью до геометрических преобразований (растяжение, сжатие, изгиб, etc), так и мы можем получать разные формы подземелий созданной нами топологии, применяя к ней различные геометрические преобразования. 

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

Примерно как на этих картинках с черепами и рыбами:

Подробнее об этом можно узнать, начав с чтения про гомологию и книгу On Growth and Form.

Во-вторых. Можно изменить форму самих клеток, например, на гексы или любой другой способ покрытия плоскости плитками.

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

Заключение

Структуры данных, полученные мной после всей процедуры: список комнат (каждая комната – это структура с уникальным идентификатором, координатами x и y, и шириной/высотой); граф, где каждый узел указывает на идентификатор комнаты, а у рёбер расстояние между комнатами выражено в тайлах; сама 2D-сетка, где каждая ячейка может быть ничем (то есть пустой), указывать на главную комнату, на коридорную комнату или быть ячейкой коридора. Думаю, с этими тремя структурами из сгенерированной схемы возможно получить любой желаемый тип данных, после чего уже определяться с расположением дверей, врагов, предметов, боссов и так далее.

Gamasutra, Procedural Dungeon Generation Algorithm.