Procedural content generation in gaming via evolutionary algorithms

i Mas e Deg ee P og am in Da a Science and Ad anced Analy ics PROCEDURAL CONTENT GENERATION IN GAMING VIA EVOLUTIONARY ALGORITHMS Se da Ce ine Disse a ion p esen ed as pa ial equi emen o ob aining he Mas e Deg ee P og am in Da a Science and Ad anced Analy ics NOVA In o ma ion Managemen School Ins i u o Supe io de Es a ís ica e Ges ão de In o mação Uni e sidade No a de Lisboa MDSAA i NOVA In o ma ion Managemen School Ins i u o Supe io de Es a ís ica e Ges ão de In o mação Uni e sidade No a de Lisboa PROCEDURAL CONTENT GENERATION IN GAMING VIA EVOLUTIONARY ALGORITHMS by Se da Çe ine Disse a ion / P ojec Wo k / In e nship epo p esen ed as pa ial equi emen o ob aining he Mas e ’s deg ee in Ad anced Analy ics, wi h a Specializa ion in Da a Science Ad iso : P o esso Mau o Cas elli Feb ua y 2023 ii STATEMENT OF INTEGRITY I he eby decla e ha ing conduc ed his academic wo k wi h in eg i y. I con i m ha I ha e no used plagia ism o any o m o undue use o in o ma ion o alsi ica ion o esul s along he p ocess leading o i s elabo a ion. I u he decla e ha I ha e ully acknowledge he Rules o Conduc and Code o Hono om he NOVA In o ma ion Managemen School. Se da Çe ine Feb ua y 28, 2023 iii ACKNOWLEDGEMENTS This hesis has been an amazing oppo uni y whe e I was able o explo e bo h my a ec ion o gaming and my passion o Da a Science. The wo k done would no be possible wi hou P o esso Mau o Cas elli, who no only p o ided wi h me he guidance I needed bu also ga e me he au onomy o ollow he uncommon domains o conduc he esea ch. I would like o hank my iend and colleague Oguz Kokes, who has been wi h me om he beginning o his jou ney and whose help, especially on he concep ual design, has been ins umen al in he c ea ion o his wo k. Las ly, I exp ess my g a i ude o my amily; my pa en s İhsan and Me yem Çe ine o hei unwa e ing lo e and suppo in e e y endea ou I had in my li e, and especially my b o he Fa uk Çe ine , who has been a cons an ole model, a men o , and a good iend o me. This wo k would no be possible wi hou hem. i ABSTRACT The aim o his hesis is o in es iga e he possibili y o c ea ing con en using he Gene ic Algo i hms. To his end a simple sys em o in e connec ed algo i hms we e de eloped using concep s om Role Playing Games, speci ically Dungeons and D agons o c ea e game con en as cha ac e s, ques s, and encoun e s. To be able o p oduce con ex , subsys ems o map, cha ac e , ques , and encoun e gene a o s we e c ea ed. These sys ems o engines no only de ine he game space o be popula ed, bu hey also p o ide each o he inpu o c ea e maps, ques s, loca ions, animals, and e en s ha a e sensible and cohe en . Randomness o he gene a ion was essen ial as such a a ie y o noise maps and andom numbe gene a ion we e added o e e y engine in he sys em. Laye ed o singula noise maps allowed o logical assump ions o be made, like seeing camels in a loca ion wi h no ain and high empe a u es. Wi h he base u h coming om a andom noise map such as dange , ci ilisa ion, ac ion e c., each sys em buil on op o each o he can ge mo e complex. The e a e se e al Gene ic Algo i hms wi h cus om ope a o s wi hin he sys em. These algo i hms ake hei inpu s and indi iduals om he espec i e engines and ie hem all o each o he h ough hei physical coo dina es in he gaming space. The mos impac ul pa o hese algo i hms is he Fi ness Func ions de ined wi h concep s om li e a u e o CGI. The p oposed sys em can popula e a game space wi h elemen s o desi ed a ibu es gi en he cons ain s. The ou pu p oduced consis s o cohe en ly ied s o y bea s wi h some a ibu es al eady se . E en in his simple le el, his can allow no only game designe s bu anyone who wan s o build any kind o ic ional wo k. KEYWORDS Gene ic Ope a o s; Op imiza ion; Gene ic Algo i hms; P ocedu al Gene a ion; Map Gene a ion; Ques Gene a ion; Cha ac e Gene a ion; Noise Maps INDEX 1. In oduc ion ................................................................................................................ 1 1.1. Backg ound In o ma ion ...................................................................................... 1 1.2. P ocedu al Gene a ion ......................................................................................... 1 1.3. Gene ic Algo i hms .............................................................................................. 2 1.3.1. Fi ness unc ion ............................................................................................. 2 1.3.2. Gene ic ope a o s ......................................................................................... 2 1.3.2.1. Selec ion ................................................................................................................... 2 1.3.2.2. C osso e .................................................................................................................. 2 1.3.2.3. Mu a ion ................................................................................................................... 3 1.4. P e ious wo k ....................................................................................................... 3 1.4.1. Te ain gene a ion ........................................................................................ 3 1.4.2. Ques gene a ion .......................................................................................... 4 1.4.3. Le el gene a ion ............................................................................................ 4 1.4.4. NPC gene a ion ............................................................................................. 5 1.4.5. Tex u e & asse gene a ion ........................................................................... 5 1.5. Thesis objec i e .................................................................................................... 5 2. PROPOSED SYSTEM ..................................................................................................... 7 2.1. Map Gene a ion ................................................................................................... 7 2.1.1. C ea ing Regions ........................................................................................... 8 2.1.2. A ibu ing Regions ..................................................................................... 10 2.2. Encoun e Gene a ion ........................................................................................ 14 2.2.1. Gene ic Algo i hm ....................................................................................... 15 2.3. Ques Gene a ion ............................................................................................... 17 2.3.1. Ques Lib a y Gene a ion ............................................................................ 19 2.3.2. Ques Line Gene a ion ................................................................................ 20 2.4. Cha ac e Gene a ion ......................................................................................... 21 3. RESULTS & Conclusions ............................................................................................. 24 4. Limi a ions and ecommenda ions o u u e wo ks ................................................ 25 5. Bibliog aphy .............................................................................................................. 26 6. Appendix ................................................................................................................... 29 i LIST OF FIGURES Figu e 1: P oposed sys em o e iew wi h sub-class in e ac ions. ...................................................................................... 7 Figu e 2: 1024x1024 map g id ini ialised wi h 512 andomly gene a ed poin s. ................................................................. 8 Figu e 3: Vo onoi essella ions o andomly ini ialised map, a bi a ily colou ed. ............................................................. 9 Figu e 4: Loca ion poin s a e Llyod’s Relaxa ion algo i hm is applied. ............................................................................. 9 Figu e: 5 Vo onoi essella ions d awn om elaxed loca ion poin s be o e and a e bounda y dis o ion, a bi a ily colou ed. ............................................................................................................................................................... 10 Figu e 6: 2-Dimensional Pe lin Noise. .............................................................................................................................. 11 Figu e 7: Two noise maps on he same g id, depic ing wea he ela ed a ibu es. .......................................................... 11 Figu e 8: A ibu ed map egions on di e en iews. ....................................................................................................... 13 Figu e 9: A ibu ed map egions on di e en iews wi h sea masks. .............................................................................. 14 Figu e 10: The i ness unc ion o encoun e gene a ion. ................................................................................................ 15 Figu e 11: Encoun e placemen o “Cannibals” and “Snakes”. ....................................................................................... 17 Figu e 12: F ey ag’s Py amid ............................................................................................................................................ 17 Figu e 13: Example ques objec a ibu es. ..................................................................................................................... 18 Figu e 14: The i ness unc ion o he ques gene a ion. ................................................................................................. 19 Figu e 15: Fi ness unc ion o ques line gene a ion. ...................................................................................................... 21 Figu e 16: Example NPC a ibu es. .................................................................................................................................. 22 Figu e 17: Ques NPC gene a ion algo i hm low. ............................................................................................................ 23 Figu e 18: Ini ial plan o he sys em. ............................................................................................................................... 31 ii LIST OF TABLES Table 1: Noise le el b eakdown o each iew and noise map gene a ed o map c ea ion. ............................................. 12 Table 2: Sample o encoun e biomes. ............................................................................................................................. 15 Table 3: Cha ac e aces and a ibu e modi ie s. .............................................................................................................. 29 Table 4: Wo ld encoun e s and hei biomes. .................................................................................................................. 31 iii LIST OF ABBREVIATIONS AND ACRONYMS NPC Non-Playe Cha ac e RPG Role-Playing Game MMORPG Massi e Mul iplaye Online Role-Playing Game RTS Real-Time S a egy GA Gene ic Algo i hm DnD Dungeons and D agons PMX Pa ially Mapped C osso e 7 2. PROPOSED SYSTEM To be able o gene a e con en in a cohe en and a iable way, ou sub-sys ems we e c ea ed. Each o hese “engines” a e ocused on a di e en aspec o RPGs. In gene al, hese engines c ea e he en i onmen and andomly ini ialises di e en popula ions o indi iduals o ques s, encoun e s and cha ac e s. Figu e 1: P oposed sys em o e iew wi h sub-class in e ac ions. Engines use each o he as inpu and ou pu loca ions, especially o ques s and encoun e s whe e gene ic algo i hms we e implemen ed. This connec ion o sys ems p o ide cohe ency be ween di e en iews o he map, which no mally would equi e game, le el, o ques designe s’ ime. The ou pu o he sys em is di e en iews on a map gene a ed and popula ed p ocedu ally. In RPG e ms, his would be he game s a e on beginning. Engines: • Map Engine: c ea es and popula es he map wi h base a ibu es. • Ques Engine: c ea es a lib a y con aining iable ques s and ques lines. • Cha ac e Engine: c ea es andom NPCs, ied o he gene a ed ques s. • Encoun e Engine: andomly bu cohe en ly popula es he map wi h p e-de ined in e ac ions. Gene a ed popula ions in di e en sys ems ie o each o he ia coo dina es as exac and ela i e loca ions o any indi iduals a e used o de e mine whe he hey a e i . To be able o c ea e base o his e alua ion, a game space needs o be c ea ed. 2.1. MAP GENERATION The game-space o he map, is essen ially a g id o poin s. Each poin o loca ion in he map needs o ha e di e en iews p o iding in o ma ion on di e en game aspec s. The gene a ion p ocess has wo phases, ini ialising he egions and assigning a ibu es o hem. Map Engine C ea es and popula es he map wi h immo able a ibu es. -Random poin s in g id. -Vo on o i Te s se l l a i o ns -Pe lin Noise -Lloyd’s Relaxa ion Te ain Ci ilisa ion Th ea S o y Ac Cha ac e Engine C ea es NPC’s cohe en wi h ques s. - Race & Classes -DND 5e a ibu es -Random names -Random in en o y -Se loca ion NPC Ques Engine C ea es a lib a y con aining iable ques pa hs. -Random coo dina es -Logical i ness -F ey ag’s i ness -Gene ic ope a o s -Random a ibu es Ques Ques Line FREYTAG’S LOGICAL NPC Book Encoun e Engine Popula es he map wi h non- s o y in e ac ion poin s. -Random coo dina es -Logical i ness -Gene ic ope a o s -P e-de ined a ibu es Animal Special Na u al LOGICAL FITNESS 8 2.1.1. C ea ing Regions To gene a e new andom maps whene e needed, he basis o he map needs o be andom numbe s. Fo he pu poses o his hesis a 1024 x 1024 g id was ini ialised wi h 512 andom poin s o “loca ions”. These poin s will se e as he cen e o a egion. Figu e 2: 1024x1024 map g id ini ialised wi h 512 andomly gene a ed poin s. Each cen oid is ied o a egion and he a ea o hese egions a e calcula ed as consis s o any poin s close o ha cen oid, he a ea is also called Vo onoi Tessella ion as o e e y cen oid α ∈"Ω, Ω being he map space, he e is a ce ain poin in x ∈"Ω in he map ha is close o α han any o he cen oid. (Luca ini, 2009) Fo his implemen a ion, Vo onoi class in scipy.spa ial lib a y was u ilised as he class is able o s o e egion, idges and e ices o di e en essella ion calcula ions. 9 Figu e 3: Vo onoi essella ions o andomly ini ialised map, a bi a ily colou ed. Due o na u e o ini ialisa ion, some clus e ing be ween cen oids is isible on he map and i doesn’ look na u al. These poin s ideally would be uni o mly dis ibu ed o he map. Fo his issue, Llyod’s Relaxa ion algo i hm was u ilised. This i e a i e algo i hm akes he ini ial loca ions, mo es hem o he cen e o hei cell and e-calcula es he Vo onoi egion esul ing in mo e uni o m cells e e y i e a ion. - Figu e 4: Loca ion poin s a e Llyod’s Relaxa ion algo i hm is applied. To achie e mo e na u al look, he idges be ween egions we e dis o ed, he a ec is pa icula ly necessa y o he e ain iew o he map as one does no expec o see s aigh line on a ealis ic map. 10 Figu e: 5 Vo onoi essella ions d awn om elaxed loca ion poin s be o e and a e bounda y dis o ion, a bi a ily colou ed. 2.1.2. A ibu ing Regions Upon gene a ion o he egions, p o iding a ibu es o hese egions a e he nex s ep as hese a ibu es will p o ide con ex o any game elemen s esiding on ha speci ic egion. This ope a ion also needs o s em om andomness o ensu e di e en maps can be gene a ed. Ini ial app oach o gene a ing uni o m andom numbe s will no wo k as his andomness needs o ollow a s uc u e. To sol e his issue, Pe lin noise was used. C ea ed by Ken Pe lin and won him an Academy Awa d in he p ocess, Pe lin Noise is an implemen a ion o g adien noise in mul iple dimensions. The algo i hm can p oduce smoo h andomness in mul iple dimensions. (Pe lin, 1985) Pe lin noise de e mines noise a a poin in space by compu ing a pseudo- andom g adien a each o he eigh nea es e ices hen doing an in e pola ion. (Lagae e al., 2010) Fo his implemen a ion, he noise package in Py hon we e u ilised. The noise class in he package allows use s o une pa ame e s o he noise maps gene a ed, which has p o ed use ul o he ini ial de elopmen p ocess. Scale: de e mines a wha dis ance o iew, se as 32. Oc a es: le els o de ail o he noise map o ha e, se as 10. Lacuna i y: adjus s he equency o a ec how much de ail is added a each oc a e, se as 0.8. Pe sis ence: adjus s he equency o de e mine how much each oc a e con ibu es o he o e all shape, se as 2. 11 Figu e 6: 2-Dimensional Pe lin Noise. As each poin in he noise map has a alue be ween -1 o 1, he ela i e di e ences o “ iews” can be de e mined. These iews a e p e-de ined o gene a e he le els be ween hem and e en ually be used o label he egion. Figu e 7: Two noise maps on he same g id, depic ing wea he ela ed a ibu es. Because di e en poin s in he egions ha e di e en noise le els, o be able o de e mine he a ibu es on a egional le el, he a e age noise is calcula ed o all egions. Fo each iew, he a e age noise is spli in o bucke s, de e mining he label. While some iews like “Dange ” ha e one noise map de e mining i , mo e complex iews such as wea he uses wo noise maps, one o aind op and one o empe a u e. 12 MAP VIEW Rain noise Hea noise Popula ion noise Th ea noise Ac noise Th ea Th ea 1-10 Te ain Tund a 0 0 Rain o es 2 2 Dese 0 2 G assland 1-0 1-2 Moun ain 2-0 0 Fo es 2 1 Ci ilisa ion Wild 1-2-3-4-5-6 Coun yside 7-8-9 Ci y 10 S o y ac Ac 0 1 Ac 1 2 Ac 2 3 NOISE LEVEL BUCKETS 3 3 10 10 3 Table 1: Noise le el b eakdown o each iew and noise map gene a ed o map c ea ion. Wi h all he di e en iews ou lined in Table 1, each poin in he map now ha e con ex in se e al dimensions depending on wha bucke (low o high) he egion in on ha speci ic iew. This al eady c ea es a cohe en map s uc u e whe e dange le el, ci ilisa ion le el, biome ype and s o y-ac s o each loca ion is known. The numbe o egions is se di e en ly o each iew depending on he con ex . Lowe numbe o egions esul s in consolida ed a eas wi hin map like he S o y Ac iew, egions ha needs o ha e imbalanced dis ibu ions a e achie ed wi h high numbe o egions in ini ialisa ion. This way, places wi h highes a e o popula ion co e s only a small ac ion o he map while s o y a cs a e sepa a ed hus a oiding an issue whe e a playe on Ac 0 can be s uck be ween highe Ac egions. 13 Figu e 8: A ibu ed map egions on di e en iews. Pe lin noise can be u he u ilised o gene a e seas wi hin he map wi h a mask, as any noise alue is be ween -1 and 1, any h eshold can be se o he “sea le el” gi ing he use con ol on he kind o map o gene a e. Se e al applica ions also use he same logic o gene a e ele a ion and smalle bodies o wa e . This applica ion only u ilises sea iew. 14 Figu e 9: A ibu ed map egions on di e en iews wi h sea masks. Wi h map gene a ion is comple e he e is a map o popula e and a ibu es o popula e i by. 2.2. ENCOUNTER GENERATION One o he ea lie RPG concep s, he encoun e s co e a wide spec um o game e en s ha can possibly happen o he playe . In ea lie games, his mechanic would be igge ed wi h a dice oll. Mode n RPGs imp o ed he mechanic o ha e oaming NPCs a ound he map ha can igge wi h an ac ual encoun e in he game space. Encoun e s a e p e-se e en s wi h con olled condi ions, one example is ge ing “ambush” encoun e while on a dange ous place. This is done o inc ease he imme sion o he playe o he game space. 15 Encoun e s TERRAIN Tund a Rain o es Dese G assland Moun ain Fo es ige 0 1 0 0 0 0 o e g ow h 0 1 0 0 0 0 bison 0 0 0 1 0 0 wind_gus 1 0 0 0 0 0 quicksand 0 0 1 0 0 0 donkey 0 0 0 0 1 0 Table 2: Sample o encoun e biomes. Fou main ypes o encoun e s we e de ined, and each sub- ype o encoun e s we e labelled wi h a biome in a logical way. (i.e., camel encoun e in dese ). Di e en ia ion o Encoun e s a e la e used on he i ness unc ion calcula ion speci ically using Th ea and Ci ilisa ion iews. 2.2.1. Gene ic Algo i hm Encoun e s needs o be dis ibu ed h oughou he map howe e a simple cons ain -based algo i hm will no be su icien as each encoun e needs o be on he co ec loca ion and be na u ally dis ibu ed o inc ease imme sion. The p oposed gene ic algo i hm u ilises wencoun e objec s. Each wencoun e , i ness unc ions a e calcula ed on wencoun e le el bu mul iple wencoun e objec s o packs a e ea ed as indi iduals. pack_popula ion e ol es un il desi ed i ness is eached. Only one indi idual is selec ed om each pack a limi ed numbe o i indi iduals a e aken om each i e a ion o p omo e di e si y and s o e hem in pe manen loca ions wi h all o he in o ma ion gene a ed. The i ness unc ion is calcula ed as ollows: !!"#$%"&!' ( #$%&'(( ) = + ,#$$'( + .#$$'( + /#$$'()+ 0#$$'( + 1#!"&'$*( !!""#$ = ! −1000%%%%%&'% he%coo dina e%biome%is%no %equal% o%encoun e %biome% % %%%%%%0%%%%%%%%%o he wise%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% #!""#$ = ⎩ ⎪ ⎨ ⎪ ⎧ −1000%%%%%&'% he%coo dina e%in%ci y%%%%%% %%%%%% −500%%%%%%&'%coo dina e%in%coun yside% %% %0%%%%%%%%%%o he wise%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% $ !""#$ = ⎩ ⎪ ⎨ ⎪ ⎧ −1000%%%%%&'% he%encoun e %is%dange ous%and%coo dina e% h ea %is%below%3%%%% %%%%%% −1000%%%%%&'% he%encoun e %is%wi h%sa e%animals%bu % he% h ea %is%abo e%7%%%%% %% %0%%%%%%%%%%o he wise%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %!""#$ = ! −1000%%%%%&'% he%encoun e %coo dina e%is%in% he%sea%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % %%%%%%0%%%%%%%%%o he wise%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% &!%&'#"($ = Absolu e%dis ance% o% he%nea es %cen oid% Figu e 10: The i ness unc ion o encoun e gene a ion. 16 Fo each wencoun e he i ness alue is calcula ed by aking co ec biome, dis ance om he cen oid o cu en egion, ci ilisa ion le el and h ead le el. Pseudocode o e olu ion s eps: • Ini ialise he wo ld encoun e manage wi h map inpu and desi ed encoun e o be gene a ed. • Ini ialise a pack popula ion. • Fo each ype o encoun e : o While he numbe o desi ed encoun e s (Wo ld A las leng h) is no eached. § Rank Selec ion • Rank he indi idual packs depending on hei i ness. • Assign selec ion p obabili ies o each indi idual, depending on hei ank. • Selec a pai o indi iduals. • Reco d he selec ed indi iduals. § Pa ially Mapped C osso e • C ea e wo cu poin s in he coo dina e a ays o pa en indi iduals sepa a ely o x and y axes. • Replace he coo dina e alues be ween he cu poin s ac oss pa en s as o sp ing. § Comple e Mu a ion • C ea e andom numbe . • I he andom numbe < mu a ion p obabili y: o Fo all coo dina es in he pack gene a e new andom numbe s. • Else: o Pass § Check i ness o indi idual. § I desi ed i ness, append o he Wo ld A las. The i ness alues aside om he dis ance om cen oid cen e a e penal ies mul iplie s o -500, al hough se e al selec ion ope a o s as Fi ness P opo iona e Selec ion and Tou namen Selec ion, because o ease o implemen a ion wi h nega i e i ness alues, Rank selec ion was used o selec pa en s. Among es ed C osso e ope a o s, he as es o con e ge on op imum solu ions we e he di e en e sions o Pa ially Mapped C osso e . Ini ial design was o ha e he genome ans e ence on wencoun e le el, bu ans e ence p o ed p oblema ic as i immensely inc eased a ia ion and p e en ed he algo i hm om con e ging. To alle ia e he a ia ion missing om he c osso e o u ilising g oups o coo dina es is compensa ed wi h he mu a ion ope a o s wi h ei he uned o be obus o jus wi h high mu a ion p obabili y. The algo i hm is un o each combina ion o encoun e ypes. Th ough gene a ions and popula ions i indi iduals a e eco ded o he wo ld a las, un il he desi ed numbe o indi iduals a e placed. 23 Figu e 17: Ques NPC gene a ion algo i hm low. When a ques placed in he Ques Lib a y, Cha ac e Engine is called o c ea e a andom cha ac e whose highes a ibu e ma ches he challenge ype o he ques . Once his cha ac e is gene a ed, i is le elled up. Cha ac e s can gain a ibu e bonusses om +2 o +6 depending on he le el b acke hey a e in. This also ensu es a iabili y in he sense ha placed cha ac e will be p o icien in he challenge ype a ibu e bu can ha e o he a ibu es boos ed wi h dange . An example o his is an in elligence challenge in a high dange loca ion could ha e a wiza d cha ac e wi h high in elligence and boos ed cons i u ion. In a simple s o y his would be hin ing ha he wiza d has been li ing in hos ile condi ions and go accus omed o i . The algo i hm o cha ac e gene a ion is ela i ely simple ye i p o ides he main aspec o he ou pu o be used as a bluep in . All engines oge he ensu e cohe ency in e ms o he game and space, his alle ia es he bu den o wo ld building and ying all elemen s oge he o a s o y elle o a game designe . 24 3. RESULTS & CONCLUSIONS The main objec i e o his hesis was he e alua e he possibili y o gene a ing con en wi h Gene ic Algo i hms. In adi ional op imisa ion app oach, he op imum solu ion is always sough a e . The whole p ocess o e olu ion is ocused on ge ing desi able le els, in he p ocess coun less o sub- op imal solu ions wi h a majo di e si y is c ea ed. The aim o he gene a ed sys em was o ocus on all iable solu ions wi hin he sea ch space. The main app oach o using penalisa ion in i ness unc ions p o ed o be use ul o achie e his esul . As expec ed, he simple and exis ing Gene ic Ope a o s p o ed e y e ec i e, he simplici y o he ope a o s is desi ed as hey impac he pe o mance o he sys em subs an ially and i hey can con e ge on any solu ion, hey p oduced desi able esul s. One downside o se ing he unc ions wi h cons ain s we e ha ing s a ic penal ies ha could no con e ge on a solu ion as all inpu s in he algo i hm ca ied he same weigh and no penal ies could be o e looked, a dynamic way o measu ing hese i nesses was only possible h ough dis ances. Un iable dis ances we e s ill penalised bu ha ing he dis ance o cen oids, ci ies and each o he as measu e be ween iable indi iduals helped he algo i hm o be able o ind he bes indi iduals. The o he side o his coin was Gaming, speci ically he embedded s o y and mechanical aspec s on games was he ocus o his hesis. E e y addi ion o di e en gaming aspec o he sys em ha e imp o ed i mo e han he Gene ic Ope a o s. Fi ness unc ions gene a ed and e e y cons ain added o he unc ions inc eased he dimension o complexi y. Especially inpu s om di e en domains such as li e a u e made all he di e ence. Tying he Ques Gene a o and Cha ac e Gene a o in o he map would no be possible wi hou F ey ag’s na a i e heo ies. Simila inpu s om psychology, poli ical science, mac o-economic can also bene i his sys em immensely because he sys ems embedded wi hin games a e al eady based on eali y, ha ing he algo i hm c ea ed wi h he same inspi a ion no only iable bu i also allows o a mo e gene al use o he p ocedu al gene a ion sys ems c ea ed. A model capable o c ea ing an ou line o game economy will be a mo e e ec i e han a sys em ha ies o calcula e he in-game cu ency amp-up in Fallou . The gene al app oach also emo es limi a ions o gaming as he p oduced esul s om he de eloped sys em is a bluep in illed wi h s o y bea s and p og ession which heo e ically can be used o c ea e any kind o s o y o wo ld building. The bluep in can alle ia e some o he alen and ime equi emen s o c ea e a good cohe en wo ld wi hin a s o y as he sys em c ea es he wo ld i s and hen pain s ou he possible s o ies ha can be old wi hin i . Same bene i o iable di e si y can also be u ilised o game es ing. Due o he na u e o some games, especially AAA a ed eleases equi e a massi e amoun o es ing be o e elease. The games ha we e no es ed p ope ly o hei size aces backlash om he playe s o en, ecen examples o his would be he elease o Fallou 76 and Cybe punk. A e hese games we e eleased, exploi s and bugs ha we e no iden i ied by he de elopmen eam we e ound by he massi e playe bases, which esul ed in PR damage and los e enues. I designed acco dingly, Gene ic Algo i hms can simula e all he di e ence ways o achie ing a goal in a limi ed space by gi ing aluable hin s o game de elope s on how many ways people can in e ac wi h hei p oduc wi h a ac ion o cos s and ime. 25 4. LIMITATIONS AND RECOMMENDATIONS FOR FUTURE WORKS The ini ial plan o his hesis was a mo e ambi ious wi h c ea ing a playable game, ha has all i s elemen s p ocedu ally gene a ed wi h he added inpu om he playe p og essing h ough he game. Many o hese elemen s we e al e ed o emo ed om he inal sys em as he amoun o ime equi ed o s udy and de elop hose concep s would o e shadow he ac ual goal o he hesis. Comple ion o his wo k mos ly elied on concep s ou o da a science, by p o iding he pe spec i e o con ex hey p og essed and shaped he sys em o i s cu en s a e. I is highly ecommended o u u e wo ks o be conduc ed wi h a eam om di e en disciplines, as i is di e en pe spec i es ha allows o abs ac concep s o be ma hema ically and algo i hmically ep esen ed. The echnical challenges o his ype o wo k can be a oided by building a sys em on a unc ional game engine as his was done by se e al s udies in he ield. A e he de elopmen o he sys em, a p ope way o measu e he quali y o he con en posed a majo issue. In exis ing li e a u e, his was only done o wo k ha was embedded in he games ia play- es e s. The only iable es ing o his applica ion, was h ough he inne wo kings o he algo i hm. As he e is no op imisa ion algo i hm ha can sol e all op imisa ion p oblems, no all con en need can be sa is ied wi h one p ocedu al gene a ion algo i hm. The complexi y o he algo i hm ises exponen ially wi h e e y o he dynamic added o he mix. Gi en he complexi y o mode n ideo games, he amoun o ime necessa y o de elop an algo i hm o gene a e iable con en is no iable. This applica ion should be u he in es iga ed o mobile games, mini-games o mechanics wi hin ideo games and gene al s o y elling. 26 5. BIBLIOGRAPHY A.J., U., & P.D., S. (2015). CROSSOVER OPERATORS IN GENETIC ALGORITHMS: A REVIEW. ICTACT Jou nal on So Compu ing, 06(01), 1083–1092. h ps://doi.o g/10.21917/ijsc.2015.0150 Basic D&D Rules | Dungeons & D agons. (n.d.). D&D O icial | Dungeons & D agons. h ps://dnd.wiza ds.com/wha -is-dnd/basic- ules Cal in Ashmo e & Michael Ni sche. (2007). The Ques in a Gene a ed Wo ld. Digi al Games Resea ch Associa ion Con e ence, 4. h p://homes.lmc.ga ech.edu/%7Eni sche/download/Ashmo eNi sche_DiGRA_07.pd Ca e , R. R., & Les e , D. (1998). Pe sonali ies o Playe s o Dungeons and D agons. Psychological Repo s, 82(1), 182. h ps://doi.o g/10.2466/p 0.1998.82.1.182 Deep, K., & Thaku , M. (2007). A new mu a ion ope a o o eal coded gene ic algo i hms. Applied Ma hema ics and Compu a ion, 193(1), 211–230. h ps://doi.o g/10.1016/j.amc.2007.03.046 Ebe , D. S., Musg a e, K. F., Peachey, D., Pe lin, K., & Wo ley, S. (2002). Tex u ing and Modeling, Thi d Edi ion: A P ocedu al App oach (The Mo gan Kau mann Se ies in Compu e G aphics) (3 d ed.). Mo gan Kau mann. Goldbe g, D. E. (1986). The Gene ic Algo i hm App oach: Why, How, and Wha Nex ? Adap i e and Lea ning Sys ems, 247–253. h ps://doi.o g/10.1007/978-1-4757-1895-9_17 Goldbe g, D. E. (1989). Gene ic Algo i hms in Sea ch, Op imiza ion, and Machine Lea ning. Addison- Wesley P o essional. Gygax, G., Su he land, D. C., & T ampie , D. A. (1978). Ad anced Dungeons & D agons, Playe s Handbook: Special Re e ence Wo k : a Compiled Volume o In o ma ion o Playe s o Ad anced Dungeons & D agons, Including, Cha ac e Races, Classes, and Le el Abili ies; Spell Tables and Desc ip ions; Equipmen Cos s; Weapons Da a; and In o ma ion on Ad en u ing. TSR Hobbies. Himi e, B. (2022, Janua y 4). Replica ing Minec a Wo ld Gene a ion in Py hon - Towa ds Da a Science. Medium. Re ie ed Oc obe 22, 2022, om h ps:// owa dsda ascience.com/ eplica ing- minec a -wo ld-gene a ion-in-py hon-1b491bc9b9a4 Holland, J. H. (1992a). Adap a ion in Na u al and A i icial Sys ems: An In oduc o y Analysis wi h Applica ions o Biology, Con ol, and A i icial In elligence. Ams e dam Uni e si y P ess. Holland, J. H. (1992b). Adap a ion in Na u al and A i icial Sys ems: An In oduc o y Analysis wi h Applica ions o Biology, Con ol, and A i icial In elligence. Ams e dam Uni e si y P ess. Hong, T. P., Wang, H. S., Lin, W. Y., & Lee, W. Y. (2002). E olu ion o App op ia e C osso e and Mu a ion Ope a o s in a Gene ic P ocess. Applied In elligence, 16(1), 7–17. h ps://doi.o g/10.1023/a:1012815625611 27 Ka e Comp on & Michael Ma eas. (2006). P ocedu al le el design o pla o m games. Na ional Con e ence on A i icial In elligence, 109–111. h p://aaaip ess.o g/Pape s/AIIDE/2006/AIIDE06- 022.pd Kelka , A., Dahibha e, M., & Jag ap, S. (2022). P ocedu al Foliage Gene a ion. In e na ional Jou nal o Resea ch in Applied Science and Enginee ing Technology, 10(5), 1628–1632. h ps://doi.o g/10.22214/ij ase .2022.42410 Koe sie , J. (2020, Sep embe 26). Global Online Con en Consump ion Doubled In 2020. Fo bes. Re ie ed Oc obe 22, 2022, om h ps://www. o bes.com/si es/johnkoe sie /2020/09/26/global- online-con en -consump ion-doubled-in-2020/?sh=71 d527c2 de Ko a, P., & Yadlapalli, P. (2017). C osso e Ope a o s in Gene ic Algo i hms: A Re iew. In e na ional Jou nal o Compu e Applica ions, 162(10), 34–36. h ps://doi.o g/10.5120/ijca2017913370 Lagae, A., Le eb e, S., Cook, R. L., DeRose, T., D e akis, G., Ebe , D. S., Lewis, J. S., Pe lin, K., & Zwicke , M. (2010). A Su ey o P ocedu al Noise Func ions. Compu e G aphics Fo um, 29(8), 2579– 2600. h ps://doi.o g/10.1111/j.1467-8659.2010.01827.x Lambo a, A., Gup a, K., & Chop a, K. (2019). Gene ic Algo i hm- A Li e a u e Re iew. 2019 In e na ional Con e ence on Machine Lea ning, Big Da a, Cloud and Pa allel Compu ing (COMITCon). h ps://doi.o g/10.1109/comi con.2019.8862255 Lim, S., Sul an, A. B., Sulaiman, M. N., Mus apha, A., & Leong, K. Y. (2017). C osso e and Mu a ion Ope a o s o Gene ic Algo i hms. In e na ional Jou nal o Machine Lea ning and Compu ing, 7(1), 9– 12. h ps://doi.o g/10.18178/ijmlc.2017.7.1.611 Luca ini, V. (2009). Symme y-B eak in Vo onoi Tessella ions. Symme y, 1(1), 21–54. h ps://doi.o g/10.3390/sym1010021 Machado, A. S. F. (2017). A p ocedu al ques gene a o o Conan Exiles [M.Sc. Thesis]. Uni e si y o Lisbon. Mawho e , P., & Ma eas, M. (2010). P ocedu al le el gene a ion using occupancy- egula ed ex ension. P oceedings o he 2010 IEEE Con e ence on Compu a ional In elligence and Games. h ps://doi.o g/10.1109/i w.2010.5593333 Pe lin, K. (1985). An image syn hesize . Compu e G aphics, 19(3), 287–296. h ps://doi.o g/10.1145/325165.325247 Rol e, B., Jones, C. M., & Wallace, H. M. (2010). Designing D ama ic Play: S o y and Game S uc u e. Elec onic Wo kshops in Compu ing. h ps://doi.o g/10.14236/ewic/hci2010.54 Rose, T. J., & Bakaoukas, A. G. (2016). Algo i hms and App oaches o P ocedu al Te ain Gene a ion - A B ie Re iew o Cu en Techniques. 2016 8 h In e na ional Con e ence on Games and Vi ual Wo lds o Se ious Applica ions (VS-GAMES). h ps://doi.o g/10.1109/ s-games.2016.7590336 Sho , T., & Adams, T. (2017). P ocedu al Gene a ion in Game Design. Ams e dam Uni e si y P ess. 28 Singe , D., & D’Angelo, E. (2021, No embe 4). The Ne lix o gaming? Why subsc ip ion ideo-game se ices ace an uphill ba le. McKinsey & Company. h ps://www.mckinsey.com/indus ies/ echnology-media-and- elecommunica ions/ou -insigh s/ he- ne lix-o -gaming-why-subsc ip ion- ideo-game-se ices- ace-an-uphill-ba le Soa es De Lima, E., Feijo, B., & Fu ado, A. L. (2019). P ocedu al Gene a ion o Ques s o Games Using Gene ic Algo i hms and Au oma ed Planning. 2019 18 h B azilian Symposium on Compu e Games and Digi al En e ainmen (SBGames). h ps://doi.o g/10.1109/sbgames.2019.00028 The e olu ion o business models in he ideo-game indus y. (n.d.). EDHEC BUSINESS SCHOOL. Re ie ed Oc obe 22, 2022, om h ps://www.edhec.edu/en/news/e olu ion-business-models- ideo-game-indus y Togelius, J., P euss, M., & Yannakakis, G. N. (2010). Towa ds mul iobjec i e p ocedu al map gene a ion. P oceedings o he 2010 Wo kshop on P ocedu al Con en Gene a ion in Games - PCGames ’10. h ps://doi.o g/10.1145/1814256.1814259 Vadim Buli ko, Mac Wal e s, & Ma hew R. G. B own. (2018). E ol ing NPC Beha iou s in A-li e wi h Playe P oxies. AIIDE Wo kshops. h p://ceu -ws.o g/Vol-2282/EXAG_116.pd Van De Linden, R., Lopes, R., & Bida a, R. (2014). P ocedu al Gene a ion o Dungeons. IEEE T ansac ions on Compu a ional In elligence and AI in Games, 6(1), 78–89. h ps://doi.o g/10.1109/ ciaig.2013.2290371 Washbu n, M., & Khosmood, F. (2020). Dynamic P ocedu al Music Gene a ion om NPC A ibu es. In e na ional Con e ence on he Founda ions o Digi al Games. h ps://doi.o g/10.1145/3402942.3409785 Yao, X. (1993). An empi ical s udy o gene ic ope a o s in gene ic algo i hms. Mic op ocessing and Mic op og amming, 38(1–5), 707–714. h ps://doi.o g/10.1016/0165-6074(93)90215 29 6. APPENDIX Race STR DEX CON INT WIS CHA Found Size Speed D agonbo n 2 1 Uncommon Medium 30 Hill Dwa 2 1 Common Medium 25 Moun ain Dwa 2 2 Common Medium 25 High El 2 1 Common Medium 30 Wood El 2 1 Common Medium 30 D ow El 2 1 Uncommon Medium 30 Fo es Gnome 1 2 Uncommon Small 25 Rock Gnome 1 2 Uncommon Small 25 Hal -O c 2 1 Uncommon Medium 30 Ligh oo Hal ling 2 1 Common Medium 30 S ou Hal ling 2 1 Common Medium 30 Human 1 1 1 1 1 1 Common Medium 30 Tie ling 1 2 Uncommon Medium 30 Table 3: Cha ac e aces and a ibu e modi ie s. Encoun e s TERRAIN Tund a Rain o es Dese G assland Moun ain Fo es ige 0 1 0 0 0 0 snow 1 0 0 0 0 0 o e g ow h 0 1 0 0 0 0 bison 0 0 0 1 0 0 wind_gus 1 0 0 0 0 0 quicksand 0 0 1 0 0 0 donkey 0 0 0 0 1 0 macaw 0 1 0 0 0 0 mee ka 0 0 1 0 0 0 hun e s 0 0 0 1 0 0 lion 0 0 1 0 0 0 a ine 1 0 0 0 1 0 capyba a 0 1 0 0 0 0 sco pion 0 0 1 0 0 0 clima e_ac i is s 0 1 0 0 0 0 gazelle 0 0 0 0 1 0 slo h 0 1 0 0 0 0 jagua 0 1 0 0 0 0 monk 0 0 0 0 1 0 eagle 0 0 1 0 0 0 ou is s 0 0 0 0 1 0 squi el 0 0 0 0 0 1 ozen_ igu e 1 0 0 0 0 0 30 liza d 0 0 1 0 0 0 hea _wa e 0 0 1 0 0 0 wol 1 0 0 1 0 0 uskan_ aide s 0 0 1 0 0 0 lood 0 1 0 0 0 0 abbi 0 0 0 0 0 1 wol e ine 0 0 0 0 1 0 poison_da _ og 0 1 0 0 0 0 bobca 0 0 1 0 0 0 o oise 0 0 1 0 0 0 animal_mig a ion 0 0 0 1 0 0 sand_dune 0 0 1 0 0 0 goa 0 0 0 0 1 0 mosqui os 0 1 0 0 0 0 maze 0 1 0 0 0 0 coyo e 0 0 1 0 0 0 spiky_canopy 0 1 0 0 0 0 a lesnake 0 0 1 0 0 0 o angu an 0 0 0 0 0 1 leopa d 0 0 0 0 1 0 gecko 0 0 0 1 0 0 a alanche 0 0 0 0 1 0 moun ain_lion 0 0 0 0 1 0 ho se 0 0 0 1 0 0 cli 0 0 0 0 1 0 cannibals 1 0 0 0 0 0 wild_boa 0 0 0 0 0 1 cul _mee ing 0 0 0 0 0 1 wilds 0 1 0 0 0 0 wood_choppe s 0 1 0 0 0 0 a c ic_ha e 1 0 0 0 0 0 ha e 0 0 0 0 1 0 snake 0 1 0 0 0 0 bea 1 0 0 0 1 0 a c ic_ ox 1 0 0 0 0 0 ozen_lake 1 0 0 0 0 0 elephan 0 0 0 1 0 0 dog 0 0 0 1 0 0 camel 0 0 1 0 0 0 allen_ ee 0 0 0 0 0 1 wi ches_house 0 0 0 0 0 1 pa o 0 1 0 0 0 0 hunde s o m 0 0 0 0 1 0 api 0 1 0 0 0 0 spide _monkey 0 1 0 0 0 0 iguana 0 1 0 0 0 0 sand_s o m 0 0 1 0 0 0 gophe 0 0 0 1 0 0 u y_ oad 0 0 1 0 0 0 31 dee 0 0 0 1 0 1 i e_an 0 1 0 0 0 0 Table 4: Wo ld encoun e s and hei biomes. Figu e 18: Ini ial plan o he sys em.