Вівденко Владислав Сергійович

Реферат за темою випускної роботи

Зміст

• Вступ
• 1. Актуальність теми
• 2. Мета і задачі дослідження та заплановані результати
• 3. Огляд актуальних методів процедурної генерації кімнат у відеоіграх
• Висновки
• Перелік посилань

Вступ

Процедурна генерація контенту - одне з актуальних і швидко напрямків в сфері розробки комп'ютерних ігор. Процедурна генерація має на увазі автоматичне створення наповнення ігрового світу, до якого можуть ставитися всілякі ігрові об'єкти, такі як рівні, кімнати, предмети, противники, інструменти гравця. За допомогою алгоритмів генерації можуть задаватися як зовнішній вигляд і властивості цих об'єктів, так і їх розташування і навіть поведінку. Крім того, процедурно-згенеровані можуть бути текстури, музичний супровід, ігрові події і навіть сюжетні лінії.

Навколо принципу процедурної генерації були сформовані цілі жанри комп'ютерних ігор, і з кожним роком їх популярність лише зростає. Це викликано тим, що ігри з таким підходом здатні надовго захопити гравця своєю різноманітністю й унікальністю, адже вони дозволяють з кожним разом створювати нові ігрові ситуації. Крім того, процедурна генерація дозволяє значно знизити витрати на виробництво ігор, оскільки здатна замінити собою роботу великого числа художників і дизайнерів.

1. Актуальність теми

На даний момент існує безліч підходів до процедурної генерації оточення в іграх. Вони включають в себе різні методи і алгоритми. Вибір певних з них залежить від завдань, які ставляться під час застосування процедурної генерації, але навіть для схожих завдань можуть виявитися оптимальними різні варіанти. Це визначається багатьма критеріями, які виставляє розробник - користувач алгоритму генерації.

З цього випливають актуальні завдання у сфері процедурної генерації контенту - створення універсальних методів, які здатні задовольняти широкому спектру критеріїв і мати гнучкі можливості налаштування параметрів під різні ситуації, а також пошук і застосування найбільш оптимальних методів для конкретних цілей розробника.

2. Мета і задачі дослідження та заплановані результати

Метою роботи є проектування і розробка системи процедурної генерації контенту для ігрових додатків, що забезпечує досягнення оптимальних результатів шляхом гнучкого налаштування вхідних параметрів.

Основні завдання роботи:

1. Дослідження доступних методів і алгоритмів процедурної генерації контенту, їх базових принципів і областей застосування.
2. Відбір найбільш універсальних і гнучких методів, які знаходять широке застосування і зручні у використанні
3. Удосконалення обраних методів, включення в їх роботу більшого числа параметрів для отримання більш точних результатів
4. Реалізація методів з урахуванням універсальних вхідних / вихідних даних
5. Розробка інтерфейсу для взаємодії з отриманої бібліотекою методів

3. Огляд актуальних методів процедурної генерації кімнат у відеоіграх

Процедурна генерація має на увазі автоматичне створення наповнення ігрового світу, до якого можуть ставитися всілякі ігрові об'єкти, такі як рівні, кімнати, предмети, противники, інструменти гравця. За допомогою алгоритмів генерації можуть задаватися як зовнішній вигляд і властивості цих об'єктів, так і їх розташування і навіть поведінку. Крім того, процедурно-згенерували можуть бути текстури, музичний супровід і сюжетні лінії.

Процедурна генерація контенту дозволяє значно знизити витрати на розробку комп'ютерних ігор, дозволяючи за допомогою однієї процедури створювати необмежену кількість різних об'єктів. Крім того, генерація може відбуватися динамічно під час ігрового процесу, створюючи для кожного гравця унікальні ситуації і неповторний досвід при кожній новій спробі, значно підвищуючи інтерес до гри.

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

Однією з перших завдань, з вирішенням яких відмінно справляються алгоритми процедурної генерації контенту, стала побудова ігрового рівня і розташування кімнат [ 1 ]. Поняття ігрового рівня і кімнат широко використовується в комп'ютерних іграх самих різних жанрів. Особливо актуальна задача процедурної генерації рівнів варто в іграх тих жанрів, в яких особливістю є те, що гравцеві належить безліч разів повторно починати гру спочатку, починаючи з першого рівня. Для того, щоб цей процес не став монотонним, було запропоновано кожен раз створювати новий тип рівня, змінюючи в ньому розташування кімнат, предметів і супротивників. Таким чином, гравець ніколи не міг бути впевненим в тому, що чекає його попереду, навіть після кількох спроб.

Перед алгоритмом процедурної генерації рівня ставляться такі завдання:

• створення унікальних наборів кімнат;
• отриманий рівень повинен бути збалансованим і прохідним;
• кімнати повинні розташовуватися природним, інтуїтивно-зрозумілим способом.

Кімнати в кожній окремій грі будуть володіти своїм набором властивостей, які визначать її унікальність. Серед них можуть бути її структура, зовнішній вигляд, наповнення. Однак серед всіх ігор у кімнат можна виділити такі узагальнені риси: форма, розмір, розташування на карті, зв'язок з іншими кімнатами.

Кожен алгоритм процедурної генерації буде включати в себе створення набору властивостей з цього списку, і далі варіюватися в залежності від особливостей гри [ 10 ]. Різні алгоритми дозволяють створювати кімнати, які більше або менше підходять під задані умови гри. Так, наприклад, структура рівня, дія якого відбувається в печерах під землею, повинна значно відрізнятися від рівня, розташованого в міському середовищі. Таким чином, для різних цілей будуть доречні різні алгоритми, які краще справляються з побудовою рівнів, структура яких ближче до певних ігрових реаліям.

Метод двійкового розбиття простору

Метод двійкового розбиття простору грунтується на структурі, званій BSP деревом.

Двійкове розбиття простору (binary space partitioning) - метод рекурсивного розбиття евклідового простору в опуклі безлічі і гиперплоскости. В результаті об'єкти отримують уявлення у вигляді структури даних, званої BSP-деревом [ 11 ].

Вхідними даними для алгоритму є загальний розмір рівня і мінімальний розмір очікуваних кімнат. Вся площа рівня приймається за один лист BSP-дерева, який випадковим чином ділиться на дві частини. Ці частини стають листям в наступному рівні дерева (див. Рис. 1). Алгоритм виконується рекурсивно для кожного нового листа до тих пір, поки його розмір не виявиться нижче заданого мінімального порога.

Метод двійкового розбиття кімнат є простим і зручним у реалізації. Він дозволяє швидко розбити задану спочатку фігуру на необхідне кількість рівномірно розподілених менших фігур, не залишаючи між ними порожніх просторів і створюючи геометрично строгі кімнати.

Рівень, отриманий за допомогою такого алгоритму, добре підійде там, де є необхідність зобразити штучно-створений ландшафт. Це може бути міське середовище або поверх окремого приміщення (див. рис. 2).

Базовий алгоритм не припускав створення коридорів - переходів між кімнатами. Це завдання можна виконати вручну, або доповнити алгоритм генерації.

Метод «хода п'яниці »

Метод «хода п'яниці »(Drunkard walk) - одна з варіацій методу «Випадкової ходи» (Random walk). він отримав свою назву за відповідний хаотичний візерунок, який утворюється в Внаслідок його роботи.

Метод грунтується на переміщенні курсора, який зафарбовує область кімнати, рухаючись у випадковому напрямку [ 12 ]. він описується наступними етапами:

1. кожна точка рівня оголошується «стіною» - непрохідною областю

2. На площі рівня вибирається випадкова точка - точка початку. Вона відзначається як «стать» - прохідна область

3. вибирається випадкове напрям руху.

4. курсор робить крок в обраному напрямку, його нова точка розташування відзначається як «стать»

5. кроки 3-4 повторюються до тих пір, поки не буде закрашено задану кількість точок.

Метод «хода п'яниці »гарантує відсутність ізольованих порожніх областей - з кожної точки кімнати можна буде дістатися в будь-яку іншу точку на карті.

Для створення більше природних структур кімнат, алгоритм передбачає кілька поліпшень. Так, на кожне можливе напрямок руху виставляються вагові коефіцієнт, таким чином, щоб курсор зміщувався до центру рівня, а не впирався в кордону. Крім того, на наступної ітерації можна задати більший коефіцієнт для попереднього направлення - таким чином між кімнатами з'являться більш виражені коридори.

Даний алгоритм добре передає освіту природних, природних структур. він добре підходить для створення рівнів в печерах або джунглях (див. рис. 3).

Клітинні автомати

Клітинний автомат - набір клітин, що утворюють деяку періодичну решітку з заданих правил переходу, визначальними стан клітини в наступний момент часу через стан клітин, що знаходяться від неї на відстані не більше деякого, в поточний момент часу. Як правило, розглядаються автомати, де стан визначається самою клітиною і найближчими сусідами [ 13 ].

Алгоритм, який ґрунтується на клітинному автоматі, починає свою роботу з того, що випадковим чином оголошує кожну точку рівня «стіною» або «підлогою». Таким чином виходить стартове стан клітинного автомата. сусідами кожної точки вважаються 8 суміжних з нею точок. Після цього починається його ітераційний процес, який визначається наступними правилами:

- точка залишається стіною, якщо вона була стіною і чотири її сусідні точки - стіни;

- точка стає стіною, якщо вона була підлогою, а п'ять її сусідів - стіни.

Таким чином, після кількох ітерацій, утворюються кімнати.

В результаті роботи алгоритму можуть утворюватися ізольовані області, їх обробку необхідно проводити вручну або окремим алгоритмом.

Кінцевий результат містить порожні області з пологими, природно виглядають стінами, без строгого поділу на «кімнати» і «коридори». Такого роду рівень добре відображає ландшафт природного середовища (Див. Рис. 4).

Висновки

Алгоритми процедурної генерації контенту дозволяють створювати необмежену кількість різноманітних і якісних структур рівнів і кімнат. гнучкі настройки генерації, після коригувань, дозволяють домогтися бажаного розробником зовнішнього вигляду рівня. Для різних типів оточення, яке передає ігровий світ, будуть доречні різні алгоритми і параметри генерації. поінформованість і розумне застосування різних методів генерації дозволяють створювати високоякісне наповнення відеоігор з мінімальними витратами ресурсів. Однак, узагальнених алгоритмів недостатньо для створення конкурентно-здатних продуктів, і кожен алгоритм потребує в доробках для досягнення кращих результатів. Інформація даної статті може бути використана для створення більш вузькоспеціалізованих алгоритмів процедурної генерації контенту.

Перелік посилань

1. Procedural Content Generation Wiki [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: http://www.pcg.wikidot.com. – Загл. с экрана
2. The Death of the Level Designer: Procedural Content Generation in Games [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: http://roguelikedeveloper.blogspot.com/2008/01/death-of-level-designer-procedural.html - Загл. с экрана
3. Procedural Content Generation in Games [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: http://pcgbook.com/ - Загл. с экрана
4. Procedural Generation of Villages on Arbitrary Terrain [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://link.springer.com/article/10.1007%2Fs00371-012-0699-7- Загл. с экрана
5. Меженин М.Г. Обзор систем процедурной генерации игр / М.Г. Меженин / Вестн. ЮУрГУ. Сер. Выч. матем. информ., 2015, том 4, выпуск 1, с. 5–20
6. Процедурная генерация уровней [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://habr.com/post/418685/- Загл. с экрана
7. Процедурная генерация в Distrust [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://habr.com/post/333692/- Загл. с экрана
8. 7 примеров использования процедурной генерации в играх [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://habr.com/company/ua-hosting/blog/275195/- Загл. с экрана
9. Средства разработки динамического игрового окружения для mmorpg игр [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: http://masters.donntu.ru/2015/fknt/luntovskaya/diss/index.htm- Загл. с экрана
10. Procedural Map Generation [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://www.gridsagegames.com/blog/2014/06/procedural-map-generation. - Загл. с экрана.
11. How to use BSP trees to generate game maps [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://gamedevelopment.tutsplus.com/tutorials/how-to-use-bsp-trees-to-generate-game-maps--gamedev-12268. - Загл. с экрана.
12. Drunken Master cave generation [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://forums.roguetemple.com//index.php?topic=4128.0. - Загл. с экрана.
13. Generate random cave levels using cellular automata [Electronic resource]/ Интернет-ресурс. – Режим доступа : www/ URL: https://gamedevelopment.tutsplus.com/tutorials/generate-random-cave-levels-using-cellular-automata--gamedev-9664. - Загл. с экрана.