Процедурна генерація рівнів для ігор-головоломок



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

Здорово було б знайти спосіб змусити комп'ютер заощадити вам час і вирішити проблеми, про які я сказав вище… І саме тут на допомогу приходить процедурна генерація!

Необхідно сказати, що існує наприклад тільки один спосіб для додавання векторів, і будь-який програміст, якому воно потрібно, повинен слідувати однаковими правилами; однак у разі процедурної генерації ви абсолютно вільні. Не існує правильних і неправильних способів. Головне — це результат.

Fruit Dating — правила та особливості
Не так давно ми випустили гру Fruit Dating для пристроїв iOS (також вона доступна для Чоловічий і навіть для невыпущенного (на момент релізу гри) Tizen). Це гра-головоломка з простими правилами. Її мета — з'єднувати пари фруктів одного кольору, проводячи пальцем по екрану. Переміщення пальця відповідає нахилу ігрового поля в потрібному напрямку. Коли гравець намагається виконати свою задачу, на його шляху встають різні перешкоди, такі як камені, машини та інші фрукти. Всі рухомі об'єкти переміщаються в одному напрямку. На картинках нижче показаний перший рівень, в якому для з'єднання фруктів потрібно 3 ходу.





Згодом додаються нові особливості:

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


Ви напевно вже помітили, що рівень складається з плиток; це спрощує роботу, тому що кожен рівень може бути представлений як маленька сітка. Її максимальний розмір 8x8 плиток, але завжди є нерухома кордон, так що «корисна» область не більше 6x6 плиток. Цього може здатися мало, але доведено, що для такого поля можна створити досить складні завдання.

На підставі базових правил (так як додаткові можливості були додані пізніше) я почав створювати свій генератор. Спочатку я подумав, що хтось у світі вже вирішив схожу проблему, так що я почав шукати в інтернеті процедурну генерацію рівнів головоломок. Виявилося, що це питання розглядалося не дуже широко. Я знайшов лише декілька корисних для мене статей. В основному вони були присвячені генерування/рішенням рівнів для Сокобана. Наприклад:

Раз, два.

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

Інструмент для рішення головоломок
Очевидно, що кожен згенерований рівень повинен проходити тестування (щоб зрозуміти, чи можна його вирішити, і наскільки складно це зробити), тому спочатку я вирішив створити інструмент для вирішення рівнів. Оскільки на той момент я враховував тільки базові правила без додаткових можливостей, у мене виникли наступні ідеї для «розв'язувача»:

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

Як бачите, це простий брутфорс-підхід. Отже, кількість можливих положень на полі було: 4, 4*4 = 42, 4*4*4 = 43,… 4n. На 10 ходу виходило більше мільйона комбінацій поля, а на 25 ходу — 1125899906842624 комбінацій. Ну добре, тоді ми можемо обмежити максимальну кількість ходів, скажімо, до 10, і нас не будуть цікавити більш складні рівні, але тут ховається інша небезпека. Деякі з головоломок можуть бути створені або згенеруватися таким чином, що гравець, який зробив на початку кілька поганих ходів, не зможе завершити рівень. Або ж у деяких рівнях може виникнути зацикленість станів на полі. Якщо алгоритм розгалужується в такому напрямку занадто рано, рівень може бути позначений як невирішуване, навіть якщо є більш короткі гілки з більш простим рішенням. Також якщо алгоритм знайшов рішення, немає ніяких гарантій, що воно саме коротке — треба завершити всі гілки, щоб знайти найкоротший рішення. Крім того, на полі часто виникають такі стани, що один хід у певному напрямку нічого не змінює. Подивіться на третю картинку в частині «Fruit Dating — правила і особливості» — нічого не зміниться, якщо ми будемо рухатися вліво.

Тому правила змінилися:

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

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


З вихідного положення ходи розгалужуються на чотири можливі напрямки. Пометим їх як 1-1, 1-2, 1-3, 1-4. Алгоритм завжди прагне переміститися в наступному порядку: праворуч, вгору, ліворуч, вниз. Оскільки для подальшого вивчення збережених станів потрібно застосувати стек, перше продовжує стан передається в стек останнім (у нашому випадку 1-4). Знову першим ходом є зсув вправо (2-1) і оскільки це новий стан, воно записується в стек. Наступним стає зсув вгору, що призводить до стану 2-2. Ми вже були в цьому стані у першій ітерації. Тому ми застосовуємо правило г) і обриваємо цю гілку — в стек нічого не записується. Далі йде спроба ходу вліво. Він призводить до нового стану (2-3) і воно поміщається в стек. Останній хід — зсув вниз, але в ньому немає відмінності між 1-4 і 2-4, тому ми нічого не поміщаємо в стек (б)… немає нового стану = нічого не робимо). Тепер верхнє стан стека — це 2-3. З нього ми переміщаємося вправо і потрапляємо в стан 3-1, яка дорівнює станом 2-1. Але в 2-1 ми були на другій ітерації, так що обриваємо цю гілку. Потім ми рухаємося вгору, фрукти виявляються на сусідніх плитках, і оскільки це була єдина пара, гра завершується.

Алгоритм працює, хоча він може і не знайти найкоротший шлях. Він просто бере перше знайдене рішення. Щоб виправити це, я спочатку обмежив максимальну кількість ходів рівним 30. Якщо рішення не знаходиться, я вважаю рівень непрохідним. Якщо рішення, припустимо на 15 ходу, я знову запускаю «вирішувач» з максимальною глибиною рішення 14 (15 — 1). Якщо рішення не знаходиться, то 15 — це найкоротший шлях. Якщо рішення знайдено наприклад на 13 ходу, я запускаю інструмент з максимальною глибиною 12 (13 — 1). Я продовжую процес, поки повертається яке-небудь рішення. Останнім повернене рішення є найкоротшим рішенням.

Генератор
Ми створили «вирішувач», тепер можна переходити до генератора і перевіряти з його допомогою кожну згенеровану головоломку.

Фаза генерування складається з двох частин:

  • генерування стін
  • генерування об'єктів на полі
Генерування стін завжди починається з малювання нерухомої межі поля:


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


Кількість стін, їх довжина і напрям випадкові. Кожна стіна починається з випадкової точки на кордоні. Кожна стіна малюється за одну або декілька ітерацій. Після першої ітерації випадково вибирається число між 0 і (довжина стіни) — 1. Якщо воно дорівнює нулю, цикл ітерації припиняється. Якщо він більше нуля, то це число стає завдовжки наступній частині стіни. Вибирається випадкова точка поточної частини стіни, напрямок вибирається випадково, ортогонально до поточної частини стіни, потім малюється наступна частина стіни. Результат може виглядати наступним чином (цифрами позначені ітерації):


На картинці видно, що кожна наступна частина стіни коротше, так що можна бути впевненим, що в якійсь точці стіна закінчиться.

Оскільки всі стіни починаються від межі поля, то кожна окрема плитка була з'єднана з кордоном. Для мене це виглядало нудно, тому я додав ще один етап, на якому генеруються внутрішні стіни. Внутрішні стіни не сполучені ні з однією наявної плиткою. Етап починається з вибору випадкової плитки і перевірки того, чи вільна вона і плитки в межах 3x3 від неї. Якщо це так, то стіна поміщена в сітку, і наступна ділянка вибирається згідно випадковому напрямку (це напрям випадково вибирається перед тестуванням першої плитки). Цикл переривається, коли умова вільних на 3x3 плиток не виконується. Зверніть увагу на виділене вище слово «буде». Якщо ви помістіть стіну в сітку відразу ж і перейдете до обробки наступної плитки, область в межах 3x3 ніколи не буде вільною, тому що ви тільки що помістили туди стіну. Тому я зберігаю всі плитки стін під тимчасовий масив і одночасно розміщую їх в сітку після припинення циклу.

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

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

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


Після завершення генерування стін можна почати генерувати об'єкти. Нам потрібна хоча б одна пара фруктів і нуль або більше перешкод (представлених в грі камінням, машинами і бочками).

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

Для решт коридорів, оточених плитками з трьох сторін, я вибрав вага 6 + Random (3). Для плиток в горизонтальних або вертикальних коридорах я вибрав вага 2. Для кутів я вибрав вага 3 + Random (3), а для вільних областей — 1.

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

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

До речі, з допомогою терезів можна робити і інші хитрощі. Пізніше я додав сплячого їжачка і мурахоїда (їх описи наведені на початку статті). Не має сенсу поміщати їх в середині коридору, тому для коридорів їх вага = 0.

У цій анімації показано розташування на рівні фруктів і перешкод:


Остаточний згенерований рівень показаний на статичній картинці нижче. Для вирішення потрібно 6 ходів (праворуч, вгору, ліворуч, вниз, вправо, вгору). Відмінно, через 1-2 хвилини після натискання на кнопку Generate у нас вийшов цікаво виглядає рівень, проходження якого можливе через 6 ходів (ніхто не буде грати в рівні, для проходження яких потрібно 30 ходів!); до того ж, для його пошуку нам не довелося ні краплі мучитися. Але… завжди можна зробити трохи краще. І з цієї точки в нашій статті ми будемо намагатися зробити рівні красивіше.


Редактор
Генерування рівнів завершилося в попередній частині. Наш редактор підтримує drag&drop, так що можна легко перетягувати об'єкти, щоб отримати більш високий рівень симетрії. Наприклад, ось так:


Після внесення змін важливо повторно протестувати рівень з допомогою «розв'язувача». Іноді невеликі зміни можуть привести до вирішуваних рівня. У нашому прикладі зміни підвищили кількість ходів до рішення з шести до семи.

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

Остаточний результат
Процедурна генерація рівнів заощадила нам гігантська кількість часу. Незважаючи на те, що генератор може створювати і сміття — рівні, які занадто просто або занадто складно пройти, рівні, повні перешкод або потворні рівні — він все одно заощадив нам купу часу. Він також дозволив нам вибирати і відкидати частину невподобаних рівнів. Якщо б ми робили вручну, це зайняло б місяці роботи. Ось як рівні, згенеровані в цій статті, виглядають в остаточній грі:


Про автора: Томас Рыхновски (Tomas Rychnovsky) — інді-розробник невеликих мобільних ігор для Android, iOS і Tizen.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.