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

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

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

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

Fruit Dating - правила і особливості

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

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

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

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

Раз і два.

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

Інструмент для розв'язання головоломок

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

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

б) з наступного положення можна знову продовжити в будь-якому напрямку;

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

Як бачите, це простий брутфорс-підхід. Отже, кількість можливих положень на полі була: 4, 4*4 = 4², 4*4*4 = 4³,… 4ⁿ. На 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.