Автор на този материал за Unity е Мариан Клейнеберг (Marian Kleineberg), много популярен програмист и гейм дизайнер. Описва се практическото използване на алгоритъма WFC (Wave Function Collapse) – колапс на вълновата функция, в който са използвани някои принципи на квантовата механика. Алгоритъмът Wave Function Collapse генерира битови изображения, които са локално подобни на входящите битови иображения.
Нека да се спрем върху хипотетична компютърна игра, в която се разхождате в безкраен град, процедурно генериран едновременно с вашето придвижване. Градът се изгражда от определен брой модули с помощта на WFC алгоритъма (колапс на вълновата функция).
Готовата демо версия може да се изтегли от сайта itch.io. Сорс кодът е публикуван в съответното хранилище на GitHub. Има и видео, в което е показано придвижването в генерирания по този начин град.
Алгоритъмът
Ще наричам с думата „клетка“ всеки елемент на 3D вокселната мрежа, който може да съдържа блок или да бъде празен. Думата „модул“ означава блокът, който блокът, който може да заема тази клетка.
Алгоритъмът решава кои модули да се избират за всяка клетка на игровия свят, Масивът от клетки се счита за вълнова функция, която няма как да се наблюдава. По този начин, на всяка клетка съответстват редица модули, които могат да се окажат в нея. Ако използваме термините на квантовата механика можем да кажем, че „клетката е в суперпозиция по отношение на всичките модули“. Съществуването на този игрови свят започва в напълно ненаблюдаем виртуален вид, в който във всяка клетка би могъл да се намира който и да е от всичките модули. След това всички клетки една след друга колапсират. Това всъщност означава, че за всяка клетка по случаен начин се избира един от всичките възможно модули.
Следва етапа на разпространение на ограниченията (constraint propagation). За всеки модул се подбират такова подмножество от модули, на които е разрешено да бъдат в непосредствена близост до него. Етапът за разпространение на ограниченията изисква най-много ресурси от гледна точка на изчислителната мощност.
Важен аспект на алгоритъма е определянето на клетката, която трябва да колапсира. Алгоритъмът винаги намира клетката с най-малка ентропия. Това е клетката, допускаща минимален брой варианти на избора – тоест, клетката с най-малка хаотичност. Ако за всичко модули вероятността за колапс е еднаква, то най-малка ентропия ще има клетката, която съответства на минимален брой модули.
Вероятността за различните модули да попаднат в дадена клетка е различна. Така например, клетка с два възможни модула, които имат еднаква вероятност, предоставя по-голям избор (по-голяма ентропия) от тази, която може да има два модула, единият от които има много голяма вероятност да попадне в клетката в сравнение с другия, с много по-малка вероятност.
Ето няколко примера за работата на алгоритъма Колапс на вълновата функция. Той първоначално бе използван за генериране на 2D текстури на базата на единствен образец.
Блоковете, прототипите и модулите
Игровият свят се генерира с помощта на колекция, съдържаща около 100 блока. Създадох ги с помощта на Blender. Първоначално тези блокове бяха съвсем малко, но постепенно добавях нови и нови, когато считаха за нужно да разнообразя играта.
Алгоритъмът трябва да знае точно какви модули могат да бъдат разположени плътно един до друг. За всеки модул е направен списък с 6-те възможни съседи – по един за всяко направление. Но никак не мис се искаше да правя този списък ръчно. Освен това, исках и автоматично да се генерират и варианти, в които модулите са завъртени в една или друга посока.
Тези две задачи се решават с помощта на прототипи на модулите. На практика това са MonoBehaviour, с които е много удобно да се работи в редактора на Unity. Модулите заедно със списъка с допустимите съседни елементи и техните обърнати варианти автоматично се създават с помощта на тези прототипи.
Възникна доста сложен проблем с моделиране на информацията относно това, кои елементи могат да бъдат съседни. Ето какво направих:
Всеки един блок има по 6 контакта със съседните модули – по един на всяка страна. Всеки контакт си има номер. Осен това, хоризонталните контакти могат да бъдат обикновени, обърнати или симетрични. Вертикалните контакти имат индекс на на завъртането от 0 до 3 или се отбелязват като ротационно инвариантни.
Тази информация е достатъчна, за да може автоматично да се провери, кои модули могат да бъдат един до друг – модулите, които са един до друг, имат еднакви номера на контактите. Също така, трябва да съвпада и тяхната симетрия – еднакъв индекс на завъртането по вертикала или и двата модула трябва да бъдат или симетрични, или инвариантни.
Въведох и правила за изключенията, с помощта на които мога да забранявам съседствата, които по подразбиране са разрешени. Това е необходимо, понеже някои съседни блокове не изглеждат красиво един до друг. Ето един пример на карта (горното изображение), в която не са използвани правила за изключения.
Пътят към безкрайността
Оригиналният алгоритъм на колапса на вълновата функция генерира карти с ограничен размер. А аз исках да направя свят, който да се уголемява и разширява докато се движите в него.
Първоначално пробвах да генерирам фрагменти с краен размер и да използвам контактите на съседните фрагменти като ограничения. Ако фрагментът е генериран, а съседният му фрагмент също е генериран, то се допускат само модули, които според правилата могат да имат съседни модули от другия сегмент. Но при този подход възниква следния проблем: при всеки колапс на клетка, разпространението на ограниченията блокира всичко дори и на разстояние от няколко клетки. В изображението по-долу са показани последствията от колапса на само една клетка:
Ако на всяка стъпка на този алгоритъм се генерира само един фрагмент, то ограниченията не се разпространяват на съседните фрагменти. В този случай, вътре във фрагмента се подбират такива модули, които биха се оказали недопустими, ако се обърне внимание на другите фрагменти. В този случай, когато алгоритъмът се опитва да генерира следващия фрагмент, не може да намери нито едно решение.
Сега вече не използвам фрагменти, а записвам картата в масив, в който се записват клетките. Всяка клетка се запълва само когато е необходимо. Необходима е лека корекция на алгоритъма, за да се отчете този момент. При избор на клетка, която предстои да колапсира, няма как да се предвидят всички клетки, ако техният брой е безкраен. Вместо това генерираме само малък участък от картата, когато геймърът го достигне. Извън тази област ограниченията продължават да действат ограниченията.
Има случаи, при които този подход не работи. Ако се разгледаме необходимите модули за праволинеен участък на тунел, понякога се получава този тунел да няма вход. Ако алгоритъмът създаде подобен тунелен модул, то според правилата ще получим безкраен тунел. За подобни случаи подбрах специална колекция от модули, които не позволяват възникването на този проблем.
Граничните условия
Трябва да се съобразяваме с две важни гранични условия. Всички граници и ръбове в горния край на карата трябва да контактуват с въздуха. А всички граници и ръбове в долната част на картата, трябва да имат твърди контакти. Ако тези гранични условия не бъдат спазени, започват да се появяват кратери в земята, а някои сгради остават без покриви.
На една карта с краен размер този проблем се решава лесно. За всички клетки от най-високо и най-ниско ниво просто трябва да се премахнат всички модули с неподходящи контактувания. След това да се стартира разпространяването на ограниченията и да се махнат неподходящите модули.
Но в една карта с безкраен размер това няма как да се направи, понеже както в горното, така и в долното поле, има безкраен брой клетки. Най-наивното решение е премахването на всички неподходящи клетки още с тяхното възникване. Но при махането на модул от горното ниво се задействат ограниченията, засягащи близките до него клетки. Възниква лавинообразен ефект, който отново води до безкрайно заделяне на клетките.
Реших този проблем създавайки карта с размер 1×n×1, където n е височината. Тази карта използва пръстенообразни светове за разпространение на ограниченията. Механизмът на действията е като в играта Pacman – когато излезе извън десния край на картата, персонажът се появява в лявата страна на картата,
Статут на грешките и търсене с връщане назад
Понякога WFC алгоритъма достига такова състояние, в което клетката не съответства на нито един възможен модул. В приложенията и игрите, в които имаме работа със свят с краен размер, можем просто да отхвърлим резултата и да започнем отначало. В безкрайния свят това не работи, понеже част от виртуалния свят вече е показана на геймъра. В началото в местата, където възникваха грешки от подобен род, просто запълвах с бели блокове.
Но сега използвам търсене с връщане назад. Редът за колапса на клетките и част от информацията за разпространението на ограниченията се запазват в историята. Ако WFC алгоритъмът откаже, то част от историята се отменя. Този подход работи добре, но понякога грешките се улавят твърде късно и тяхното намиране с връщане назад изисква твърде много итерации.
Според мен, заради това ограничение, използването на WFC алгоритъма го прави неподходящ за комерсиални игри. Но има много места, където кодът може да бъде значително усъвършенстван.
Перспективите
Заех се с това, след като присъствах на лекцията на Оскар Стелбърг, който показа използването на съшия алгоритъм за генериране на нивата в играта Bad North.
Имам редица идеи за усъвършенстването на този алгоритъм, но не знам кога ще имам време да се заема и да добавя и геймплей. А ако все пак един ден се заема с това, едва ли ще създам епичната игра, която навярно си представяте. Но ако искате да проверите как работи с този алгоритъм вашата любима игрова механика – просто пробвайте и вие. В края на краищата това е отворен код, който е публично достъпен за всички и се разпространява чрез MIT лиценз.
Алгоритъмът Колапс на вълновата функция е реализиран на C++, Python, Kotlin, Rust, Julia, Haxe, JavaScript и е адаптиран за Unity. Алгоритъмът генерира нивата в Bad North, Caves of Qud, в някои по-малки игри, както и в редица прототипи на прототипи на игри. Неговото създаване доведе до нови алгоритмични изследвания. Предлагат се голям брой обяснения, интерактивни демонстрации, ръководства, учебни материали и много примери.
