Алгоритми генерації лабіринтів
Лабіринти - це не тільки самостійний клас ігор, але і основа для створення локацій в іграх інших жанрів: наприклад, систем печер, які, в свою чергу, можуть бути використані в дуже широкому класі ігор-броділок і т.д. Однако если игроку придется постоянно «изучать» одни и те же локации, ему это может скоро надоесть, а потому перед разработчиками игр встает вопрос о процедурной генерации лабиринтов, т.е. щоб кожне чергове проходження гри проходило на заново згенерованої території.
Лабиринты мы будем строить на прямоугольном клеточном поле (+ одна из статей о генерации в трехмерном пространстве), поэтому все их можно разделить на две группы: лабиринты с «тонкими» стенками и с «толстыми». Перші - це ті, у яких стіни розташовані на кордонах клітин, другі - це ті, в яких деякі клітини самі є непрохідними, тобто стінами. Їх відрізняє, наприклад, спосіб зберігання даних про карту.
Також існують вже готові рішення для генерації лабіринтів: генератор Oblige. который используется в DOOM, DOOM II и Heretic, и др.
алгоритм Еллера
На тему генерації лабіринтів, де стінки розташовані на кордонах клітин, на Хабре є хороший переклад статті «Eller's Algorithm» (саме Еллера, а не Ейлера - «Eller's», а не «Euler's») про те, як створити ідеальний (perfect) лабіринт - такий, що між будь-якими двома його клітинами існує шлях, і до того ж єдиний.
Загальна ідея алгоритму полягає в порядкової генерації, де між кожними двома клітинами рядки при певних умовах (щоб не було циклів і недоступних клітин) випадковим чином виникає стінка. При цьому в кінці все клітини виявляться «в одному безлічі», що означатиме, що між кожними двома клітинами існує шлях.
Зберігати карту лабіринту можна, наприклад, в двох двовимірних масивах: для вертикальних стінок і горизонтальних, відповідно.
Як зберігати лабіринти з «товстими» стінками?
Відповідь на питання про зберігання карт таких лабіринтів очевидний: у вигляді двовимірного boolean масиву, де, наприклад, 1 - це непрохідна клітина (стіна), 0 - вільна.
наївний алгоритм
Природно, виникають два питання: чи не будуть кімнати перетинатися і як прокласти між ними переходи? Відповідь на перше питання залежить від ваших вимог до лабіринту: якщо ви не хочете, щоб кімнати перетиналися, напишіть функцію, яка перевіряє пару кімнат на перетин і при появі на карті черговий кімнати робіть перевірку.
Лабіринт на таблиці
У описаного вище алгоритму є один явний недолік: перевіряти, чи перетинаються кімнати, доводиться окремою функцією. Виникає питання, чи можна не робити це зайве дію. Виявляється, можна-і алгоритм описаний нижче.
Ідея полягає в тому, що поле спочатку розбивається на прямокутні «великі» клітини (тобто не елементарні клітини ігрового поля, а прямокутники, що складаються з декількох клітин), утворюючи таким чином таблицю. Далі в кожній такій клітинці випадковим чином з'являється кімната випадкового розміру, що не перевершує розмірів осередку - тим самим можливість появи пересічних приміщень пропадає. Затем комнаты объединяются коридорами, например, тем же способом, что описано в предыдущем пункте.
Детально цей алгоритм генерації описаний в статті «Grid Based Dungeon Generator».
BSP - це абревіатура від Binary Space Partitioning - бінарне поділ простору. Цей алгоритм також дозволяє уникнути перетинання кімнат ще в процесі розміщення їх на карту, тому що також попередньо ділить ігрове поле на частини - «листя», всередині яких потім генерує кімнати. Цей поділ площі ідейно складніше, тому що розділяє всі. ніж попередній алгоритм, але і дозволяє створити більш цікаві конфігурації розташування приміщень.
Генерація лабіринтів з використанням клітинного автомата
Кожен програміст хоча б раз писав «Життя» - клітинний автомат, придуманий математиком Конвей. Так чому б не використовувати схожу ідею для генерації лабіринтів? Суть запропонованого алгоритму полягає в реалізації всього двох кроків: спочатку все поле заповнюється випадковим чином стінами - тобто для кожної клітини випадковим чином визначається, чи буде вона вільної або непрохідною - а потім кілька разів відбувається оновлення стану карти відповідно до умов, схожими на умови народження / смерті в «Життя».
У джерелі - на сторінці статті «Generate Random Cave Levels Using Cellular Automata» - ви можете поекспериментувати з інтерактивною Демко, встановлюючи різні значення для генерації: кількість ітерацій поновлення, граничні значення для життя / смерті клітини і т.п. - і побачити результат. Там же розповідається про підводні камені реалізації.
Генерація в тривимірному просторі
Що далі?
На тему цієї статті існує величезна безліч матеріалів, які можуть бути знайдені в інтернеті, тому якщо ви хочете заглибитися у вивчення питання генерації лабіринтів, можете заглянути спочатку сюди. а потім вже, звичайно ж, ось сюди.
Дякую за увагу!