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.