Генериране на процедурна карта (част 1)
В тази кратка статия ще споделя прост алгоритъм за процедурно генериране на геометрия на карта, който съставих като прототип за моята малка игра, подобна на roguelike.
За да стане ясно какво ще се обсъжда, на изхода се получават следните карти (щракнете за уголемяване):
Веднага ще направя резервация, че ще говорим за генериране само на геометрията на картата, ако такъв материал върви добре, тогава ще продължим да говорим за процедурното генериране на останалите елементи на играта - неща, чудовища, събития.
Взех чудесната статия Procedural Generation - The Dungeons от независимия разработчик на игри Noel Berry като основа за алгоритъма. Не пропускайте да посетите сайта му, той има страхотни игри!
Предложеният подход е доста прост, той може да бъде разделен на три етапа: 1. Генериране и разполагане на стаи. 2. Свързващи стаи с коридори. 3. Изграждане на стени и окончателно почистване.
Първото нещо, което ще направим, е да създадем игрално поле и да поставим няколко произволни стаи върху него, които ще станат основата на нашата карта.
Като начало ще създадем структури за картата и стаите в нея (веднага задаваме размерите на картата):
Едно от изискванията за новата стая е тя да не се припокрива със съществуващите, но също така исках стаите да са близо една до друга, затова добавих тази функция към стаята, за да проверя за пресичане:
Сега можем да генерираме няколко стаи с произволно местоположение и размери, за това ще добавим нов метод:
Сега имаме набор от произволни стаи, които могат да бъдат преобразувани в масив от 2D карти доста лесно:
В резултат на това трябва да получим нещо подобно (няма да засягам процеса на визуализация):
Свързани стаикоридори
Сега всички тези стаи трябва да бъдат свързани с коридори, в противен случай как нашият герой ще се движи по картата? И отново, идеята е съвсем проста - нека последователно да преминем през стаите на картата и да потърсим път от средата на една стая до средата на следващата в списъка, като по този начин получим гарантирано преминаване от първата до последната стая.
За да намерим пътя, използваме основния алгоритъм A * (A star), който е описан подробно в много източници, например тук. Използвах код като този (версия без оптимизации):
Функцията calcCost() връща "цената" на клетката, изчислена по такъв начин, че за нас е по-изгодно да се движим през съществуващи стаи и коридори, отколкото да създаваме нови. Плюс малка евристика, която ни позволява целенасочено да стигнем до крайната точка. Можете сами да си поиграете с тези настройки.
След изграждането на коридорите ще имаме в ръцете си карта от този тип:
Изграждане на стени и окончателно почистване
За пълнота липсва още един малък детайл - стените. Разбира се, можете да правите без тях, но по правило стените могат да бъдат красиво нарисувани, визуално ограничавайки пространството на картата.
Затова нека добавим нов метод, който ще премине през цялата карта и ще добави стени навсякъде, където „празните“ клетки граничат с клетките на стаи и коридори:
След това ще получим пълноценна карта:
Но това не ми се стори достатъчно, затова реших да добавя окончателно „почистване“, където премахвам ненужни (по мое мнение) стени и различни малки артефакти, кодът на този метод е доста „мръсен“, така че няма да го дам, мога само да кажа, че получавам следния резултат:
Заключение
Програма, която генерира карта по следния начин:ниво1