Escola T`ecnica Supe io d’Enginye ia In o m`a ica
Uni e si a Poli `ecnica de Val`encia
Open Wo ld S eaming:
Au oma ic memo y managemen in
open wo ld games wi hou loading
sc eens.
T abajo Fin de G ado
G ado en Ingenie ´ıa In o m´a ica
Alejand o Juan P´e ez
uk[email p o ec ed]
Supe ised by
Ram´on Pascual Moll´a Vay´a
2015-2016
Con en s
1 In oduc ion 3
2 Open wo ld ideogames 4
2.1 Con en gene a ion ........................ 5
3 Requi emen s 6
3.1 Main equi emen s . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Seconda y Requi emen s . . . . . . . . . . . . . . . . . . . . . 7
4 Le el-based ideogames 8
5 Wo ld s eaming 9
5.1 Examples o games using wo ld s eaming . . . . . . . . . . . 10
5.2 Thes a egy............................ 18
5.3 Loading Resou ces is slow . . . . . . . . . . . . . . . . . . . . 19
6 The a chi ec u e o he engine 21
7 Implemen a ion 23
7.1 G aphicsSys em ......................... 23
7.1.1 A chi ec u e........................ 23
7.1.2 Fea u es.......................... 24
7.1.3 Why did I implemen my own g aphics engine? . . . . 25
7.1.4 Mode n OpenGL p og amming . . . . . . . . . . . . . 26
7.2 PhysicsSys em .......................... 29
7.2.1 The issue o he p ecission . . . . . . . . . . . . . . . . 30
7.2.2 Al e na i e app oaches . . . . . . . . . . . . . . . . . . 30
7.2.3 Ou app oach....................... 31
7.3 Resou ce Manage . . . . . . . . . . . . . . . . . . . . . . . . 31
7.4 Wo ldS eame .......................... 34
8 Resul and es ing 38
8.1 Demo ............................... 39
8.2 Pe o mance............................ 40
9 Conclusion 44
10 Upda e: anima ion sys em 45
11 Fu u e ex ensions 50
1
12 License 51
13 Tools and dependencies 51
13.1Used ools............................. 51
13.2Dependencies ........................... 51
2
1 In oduc ion
Open wo ld games a e among he mos app ecia ed games by playe s. They
p o ide use s he chance o explo e a big wo ld and hey a e e y imme si e.
Open wo ld games g an playe s he eedom o ake any decision and enjoy
hei high in e ac ion.
In open wo ld ideogames he playe , usually, con ols an a a a o e a
big i ual wo ld. So he playe ha con ols he a a a akes i s skin and,
ideally, ge s imme sed in he i ual wo ld.
The e is a good chance you know abou some o he mos amous open
wo ld games. Some o hem a e: G ad The Au o se ies 1,The Elde Sc olls
se ies 2o Minec a 3. These games, apa om being e y amous, hey
ha e all been in he op o he bes -selling ideogames[1].
•Minec a has sold 19 million copies o he PC pla o m and i is he
mos sold PC game e e .
•G and The Au o V has sold 19 millons copies o he PS3, making i
he mos sold PS3 game e e .
•The Ede Sc olls: Sky im has sold 20 millon copies o PC,XBOX and
PS3.
The e o e, open wo ld games a e no only abou un, eedom and high
in e ac ion bu also a p omising business. And as we will see hey a e ech-
nologically challenging.
Despi e open wo ld games a e well know, he echniques ha a e applied
in hei implemen a ion a e no . Game s udios ha a e expe ienced in he
implemen a ion o open wo ld games, like Rocks a , keep well hei sec e s.
The de elopmen o open wo ld game engines equi es a g ea in es men .
The pu pose o his p ojec is o de elop a game engine ha will suppo
making open wo ld ideogames. Ou engine should allow he c ea ion o
games wi h huge wo lds and a oid loading sc eens. The e is e y ew in o -
ma ion abou he opic (specially a he implemen a ion le el). My in en ion
is o ga he a ailable in o ma ion and ex end i wi h my own hough s and
ge hem o be implemen ed. Hope ully, his a icle, and he open sou ce
code ha comes along wi h i , will help o he people o unde s and he main
conce ns hey should ake when de eloping open wo ld games.
1G and The Au o is a se ies o games p oduced by Rocks a
2The Elde Sc olls is a se ies o games p oduced by Be hesda
3Minec a is a sandbox game p oduced by Mojang
3
2 Open wo ld ideogames
Open wo ld a e some kind o ideogames in which he playe can mo e eely
in a huge i ual wo ld. The s uc u e o he game is no linea in e ms o
gameplay. Tha means, he playe has he choice on wha o do nex . The e
a e some game gen es ha can bene i a lo om he open wo ld app oach.
Fo example, ole playing games (RPG)4, sandbox5and ehicle simula ion6
a e enhanced when con ined wi h a big open wo ld.
In some open wo ld RPGs, he playe can explo e he wo ld and comple e
missions. Some o hese missions a e no manda o y so he playe is allowed
o decide whe he o no o ake hem. These is an example o he non-
linea i y we ha e been alking abou .
Figu e 1: Fa C y 3 is a RPG ea u ing an open wo ld
In an open wo ld ehicle simula ion ideogame, he playe would be ee
o d i e a ound a big ci y o he long oads o he coun y side.
4h ps://en.wikipedia.o g/wiki/Role-playing_ ideo_game
5h ps://en.wikipedia.o g/wiki/Glossa y_o _ ideo_game_ e ms#Sandbox_
game
6h ps://en.wikipedia.o g/wiki/Vehicle_simula ion_game
4

Figu e 2: Eu o T uck Simula o is a d i ing simula o wi h a ealis ic open
wo ld
2.1 Con en gene a ion
Since open wo ld games ha e such a big uni e se, he e mus be a lo o
con en o ill up all ha space. I is equi ed o ha e a lo o people c ea ing
ha con en (p og amme s, designe s, a is s...). Some imes, when he e a e
no so many human esou ces a ailable, i is a good choice o gene a e he
wo ld p ocedu ally. The e o e, we can ge help om he compu e s in o de
o ill he wo ld wi h un con en . Mos o he imes, he e is a mix u e
o p ocedu ally gene a ed con en and a is s con en . Bu he e a e some
games whe e he con en gene a ed by algo i hms is p edominan . Ha ing he
compu e s o do such a cos ly ask is an ad an age o indie game s udios
because hey can no a o d hi ing so much people. No Man’s Sky7is an
example o a ideogame wi h a p ocedu ally gene a ed wo ld de eloped by a
small eam.
7No Man’s Sky is a game p oduced by Hello Games
5
Figu e 3: No Man’s Sky is a ideogame wi h a po en ially unending open
wo ld (p ocedu ally gene a ed)
Whe he o no he con en o open wo ld games has been gene a ed by
a compu e o a human, he e is a common end in he la es open wo ld
ideogames: he e a e less and less loading sc eens. The ideogame design-
e s a e ying o a oid loading sc eens when possible, so he playe doesn’
ha e o wai and has his imme sion eeling inc eased. This is accomplished
hanks o a echniche called wo ld s eaming. This is he main ocus o his
documen .
3 Requi emen s
So we a e willing o make a game engine ha suppo s he de elopmen o
open wo ld games and a oids loading sc eens. We a e going o ocus on he
equi emen s ha a e mo e speci ic o open wo ld games. And equi emen s
ha a e common o mos game engines will be le as seconda y equi e-
men s.
3.1 Main equi emen s
We conside hese equi emen s a e he main a ge o accomplish.
•Visualiza ion: We said ha equi emen s ha a e common o any
game engine will be ea ed as seconda y equi emen s. Bu his is an
excep ion. I is e y impo an o ha e some kind o isual eedback.
6
We need isualiza ion o es ou sys em. Also, i is impo an in o de
o p o e ha ou engine is wo king p ope ly. So we need o implemen
a g aphical in e ace e en i i is no e y ancy. The g aphics will be
2-dimensional.
•Memo y managemen : I he e is one hing ha cha ac e izes open
wo ld games is ha hey usually ha e e y big wo lds. These wo lds
ha e a huge amoun s o da a (en i ies, ex u es, meshes, sound, e c).
Some o his games equi e se e al ens o gigaby es o comp essed da a
in seconda y disk. Ob iously, we can no expec ou use s o ha e ha
much RAM capaci y. The main challenge will be o keep memo y con-
sump ion o a minimum while no comp omising playabili y o quali y.
The ick we a e going o use is o load in o main memo y only he
hings ha a e close o he playe . Ano he hing ha we will do
is o a oid duplica ed esou ces in RAM. Fo example, he e a e is a
o es ha has many ees ha sha e he same se o ex u es, we mus
accomplish ha each ex u e is in RAM a mos once.
•Accu a e physics simula ion: Again, his is a ea u e ha mos
game engines inco po a e. Bu i is impo an as a main equi emen
because accu acy in open wo ld games ca y challenges ha mus be
sol ed. We will alk abou his opic la e because i is complex and
equi es i s own space (7.2.1).
•Easy o use: I is impo an ha making games wi h ou game engine
is as easy as wi h any o he engines we a e used o. I ou engine was
oo di icul o use nobody would use i .
•Tes able: We wan o be able o see i ou engine is wo king as ex-
pec ed.
3.2 Seconda y Requi emen s
These equi emen s would be g ea o be implemen ed o a comme cial game
engine bu no he main a ge o his academic wo k.
•Sound: E e y game engine has sound and i is no an issue in open
wo ld games.
•Sc ip ing: We could embed some sc ip ing language as i is done in
mos game engines.
•Ad anced g aphics: They ha e no hing o do wi h wo ld s eaming.
7
•Pe sis ency: I would by g ea i changes made o he wo ld we e
pe sis en .
•E iciency: Sa ing compu a ional esou ces in wo ld s eaming will
make hem a ailable o o he asks like physics simula ion o a i icial
in elligence.
4 Le el-based ideogames
T adi ionally games ha e been s uc u ed in le els. In his kind o games
he playe mus comple e he cu en le el o ad ance o he nex one. Once
one le el is comple ed ha le el doesn’ need o emain in main memo y.
The e o e, esou ces can be dele ed. The mechanics o his ype o games
allows o manage he esou ces o he game in an easy and e icien way.
Le el 1 Le el 2
Le el 1 Le el 2
Loading...
Figu e 4: Le el loading mechanics
I is well know ha compu e s(and o he gaming de ices) usually ha e
wo ypes o memo y. The i s memo y is he one we usually call main mem-
o y. Main memo y is as and small. The second memo y is he seconda y
8
Figu e 11: Sc eensho o GTA: San And eas
San And eas is he mos sold PS2 game e e . Ve y success ul o he PC
and XBOX pla o ms oo. And no only ha , he game is s ill ha ing good
sales o PC and And oid.
Wo ld O Wa c a - Blizza d (2004) Wo ld o Wa c a (WoW ) is an
MMORPG (massi ely mul iplaye online ole-playing game). This game has
a di e en ype o wo ld s eaming om he one we ha e seen so a . In his
case he in o ma ion ha p o ides he s a us o he en i ies does no come
om he ha d disk bu om he ne wo k. Wo ld s eaming in he ne wo k is
e en mo e challenging bu , o ins ance, esou ce managemen is e y simila .
This game has a big wo ld and social in e ac ion be ween playe s. Cha ing,
ading and igh ing wi h o he playe s is possible in WoW.
15

Figu e 12: Sc eensho o Wo ld o Wa c a
WoW has been he mos played mul iplaye game o many yea s and i
is he game ha p o ided mos ea nings o all imes($10 billion)[5].
Fallou 3 -Be hesda So wo ks (2008) Wo ld s eaming is a ea u e
p esen in many o he new-gene a ion ideogames. Fallou 3 is jus one o
hem ha has an eno mous wo ld and imp essi e g aphics.
16
Figu e 13: Sc eensho o Fallou 3
Minec a -Mojang (2011) Minec a is he sandbox ha p o ed ha
games a e no all abou g aphics.
Figu e 14: Sc eensho o Minec a
Minec a is he mos sold PC game o all imes.
Conclusion We ha e seen many games suppo ed by he wo ld s eaming
echnology. The end shows ha open wo ld games a e becoming mo e
popula and i does no seem i is going o s op.
17
5.2 The s a egy
The mos aluable sou ce o in o ma ion I ha e ound abou wo ld s eaming
is an a icle called The Con inuous Wo ld o Dungeon Siege by Sco Bilas[2].
In his a icle, Sco Bilas explains how hey de eloped Dungeon Siege.Dun-
geon Siege is an open wo ld 3D game eleased in 2002. I was de eloped by
Gas Powe ed Games and dis ibu ed by Mic oso . In his a icle I ha e
ound many use ul ips o implemen ing an open wo ld s eaming engine.
Dungeon Siege is a 3D game bu you can only mo e in ou di ec ions ( he
wo ld is landscape shaped). So he app oach ollowed in Dungeon Siege is
simila o he one we would ollow in a 2D game.
In Dungeon Siege he wo ld is di ided in o pieces o land which a e aligned
o a g id. These ec angles o land a e called nodes. Any node can be
connec ed o e e y o he node. I wo nodes a e linked, ha means ha i
he playe is in one o hem, he could a el o he o he a any momen .
The e o e, when he playe is in one node we mus be loading a leas all he
di ec ly connec ed nodes. No mally he connec ions will ma ch he adjacen
pieces o land.
Figu e 15: Connec ions o adjacen pieces o land (we a e no aking in o
accoun he diagonals)
Bu he e a e cases in which wo adjacen nodes could no be connec ed
(e.g. he e is a wall sepa a ing hem). O he e could be nodes ha a e
18
connec ed and a e no adjacen (e.g. he e is a po al ha will elepo he
playe om one place o ano he ).
Figu e 16: Two nodes connec ed by a po al.
This node-based app oach is he one used in Dungeon siege. The design-
e s o he game used a cus om ool ha would allow hem o manage he
connec ions o he nodes.
Fo ou engine we a e going o ake a simple app oach and we will assume
each node is connec ed o all he su ounding nodes (i.e 8 nodes a mos ).
This will simpli y he job o he designe s o he game. Wi h ou app oach
aking po als will equi e a loading sc een (which is e y common cu en
games).
5.3 Loading Resou ces is slow
Imagine ha we ha e implemen ed ou s a egy and in a gi en momen he
playe has changed o node. We will ha e o load o main memo y all he
en i ies ha a e loca ed in he new adjacen cells (o nodes). Tha implies:
loading om disk he ile ha desc ibes ha cell, pa sing ha ile in o de
o ind he en i ies, loading all he esou ces ha a e equi ed by he en i ies
and inally c ea ing he en i ies. So when he node had been loaded you
would ealize ha you ha e spen 1 second (o much mo e) and in his ime
19
you ha en’ ende ed a single ame!. This would be pe cei ed by he use
as a eeze. The e o e, we ha e o sol e his in some way.
Figu e 17: Loading om disk in he main loop.
The bo leneck he e is he access o disk. Access o disk blocks he CPU
and equi es some ime. So mos o he ime, when loading a new cell, he
CPU would be idle while i could be doing impo an asks (e.g. physics
simula ion o ende ing). The solu ion ha is sugges ed in he a icle o
Sco Bilas (and he one we ha e ollowed) is o use a sepa a e h ead o
loading esou ces om disk. So i ou main h ead ( he one ha execu es
he main loop) needs o load a esou ce, ins ead o doing i i sel , i asks he
backg ound h ead o do i . This way, he main h ead is ne e idle when
he e is job o be done and he seconda y h ead will be loading om disk
a i s own pace.
20

I need his esou ce o be
loaded bu I can' do i mysel
because I mus a end o he asks.
Would you mind doing i o me?
Hi, backg ound h ead! Hello!
Su e!
MBG
Figu e 18: Two h eads alking.
Figu e 19: Loading om disk is pe o med by a seconda y h ead
6 The a chi ec u e o he engine
Ou game engine will be composed by some subsys ems. In o de o wo k
p ope ly he componen s o he engine mus in e ac wi h each o he in some
way.
21
Lis o
ac i e en i ies
Wo ld
S eame
G aphics
Sys em
Physics
Sys em
Resou ce
Manage
Figu e 20: Game engine a chi ec u e.
The pic u e abo e is a simpli ica ion o he a chi ec u e. No ice ha in
he diag am only wo subsys ems a e ep esen ed. The g aphics and physics
componen s a e he mos impo an subsys ems, bu he e could be o he s
like sound o a i icial in elligence (AI).
Resou ce Manage : The esou ce manage is he componen in cha ge o
accessing he ile sys em. I uns on a sepa a e h ead so i does no in e e e
in he p og ess o o he asks. Also, i mus assu e ha he e will no be
duplica ed esou ces in main memo y. The esou ce manage is used by all
he o he a chi ec u e componen s. So i akes he ole o a se an o he
o he s. In o he o ease he access o his u ili y sys em, i is e y con enien
o implemen i as a single on.
Wo ld S eame : I is he one. The b ain o he a chi ec u e. The wo ld
s eame is in cha ge o elling he subsys ems below (g aphics and physics
in ou diag am) wha o do. I mus decide whe he a gi en en i y mus be
loaded o no . An ine icien implemen a ion o he wo ld s eame would
decide ha all he en i ies o he wo ld mus be loaded. And a useless
implemen a ion would no load any en i y. So he wo ld s eame needs o
compu e he subse o en i ies ha mus be loaded a any ime. This subse
o loaded en i ies is wha we ind in he diag am as ”Lis o ac i e en i ies”.
22
G aphics Sys em: Migh be called g aphics engine oo. I will ge a lis
o en i ies ha mus be ende ed om he wo ld s eame . So i will be
jus old wha should be displayed on he sc een. The g aphics sys em is
independen om all he o he componen s and does no ca e who is using
i .
Physics Sys em Ve y simila o he g aphics sys em. In he diag am you
can app ecia e he di e ence be ween hese wo: an ex a a ow. This a ow
lows om he physics sys em o o he wo ld s eame . The meaning o his
a ow is he posi ion o he main cha ac e . A e each physics simula ion s ep
he posi ion o he main cha ac e migh ha e changed and he wo ld s eame
needs his in o ma ion in o de o ecompu e he se o ac i e en i ies.
7 Implemen a ion
In his sec ion I will explain b ie ly how I implemen ed he modules o he
game engine.
7.1 G aphics Sys em
The g aphics sys em is implemen ed om sc a ch ( he e is a eason ha will
be explained la e ). Since implemen ing a g aphics engine is no he pu pose
o his academic wo k, i does no ha e a big se o ea u es.
7.1.1 A chi ec u e
This g aphics module is spli in wo laye s. The i s laye is he low-le el
laye . The low-le el laye is he one ha uses he OpenGL API (applica ion
p og amming in e ace). The pu pose o he low-le el laye is o p o ide a
simple in e ace o he uppe laye . This way he high-le el laye does no
need o unde s and any o OpenGL. So i we needed o deploy he applica ion
o a pla o m we e Di ec X pe o ms be e , we would only need o eplace
he low-le el laye and he es o he whole sys em would emain he same.
23
Wo ld S eame
High-le el Rende e
Low-le el Rende e
OpenGL
G aphics
Sys em
Figu e 21: G aphics sys em a chi ec u e.
The low-le el ende e API is jus a educed se o unc ions ha allows
o d aw hings on he sc een. On he o he hand he high-le el ende e
p o ides a class-based mechanism o de ine he scene. Tha is, in he low-
le el ende e we would say: ”d aw ex u e A in posi ion X” and i will be
shown on he sc een o jus his ame. And in he high-le el ende e we
would say: ” he e exis s a sp i e in X and i has p io i y P” and i would be
d awn on he sc een un il i is emo ed.
7.1.2 Fea u es
The ende e I ha e implemen ed is no e y sophis ica ed bu wo ks ine o
ou pu pose. Anima ions a e no ye suppo ed(Upda e: I ha e implemen ed
a new anima ion sys em [10]). You can assign p io i ies o he sp i es in o de
o de ine wha is d awn on op. The e is an abs ac ion o he came a oo.
The low-le el ende e uses he subse o unc ions a ailable in OpenGL ES
(embedded sys ems), so i could be po ed o mobile pla o ms.
24
7.2.3 Ou app oach
The app oach we ha e chosen has many bene i s and he only d awback is
ha i is a bi di ucul o implemen .
Ha ing he o igin o coo dina es close o he en i ies allows us o use he
mos p ecise ange o loa ing poin numbe s. In ha ange, loa ing-poin is
e en mo e accu a e han ixed-poin .
Since we a e using he loa ing-poin numbe s ha mos g aphics ca ds a e
op imized o , we ge he bes possible pe o mance. And he compa ibili y
is also he bes .
We can use any exis ing so wa e because loa ing-poin is so ex ended.
When s o ing en i ies o pe sis ence, he posi ions will be ela i e o he
cell hey belong o. So any posi ion in he wo ld could be ep esen ed as a pai
o cell (in ege ec o ) and ela i e posi ion ( loa ec o ). So as long as he
cell size keeps small, he p ecision will be ine. And he in ege ep esen a ion
is b oad enough o mos cases. I 32-bi in ege s we e no enough, you
could always use 64-bi o e en lib a ies such as TTMa h[16]. Wi h ou
ep esen a ion we ha e good accu acy and unlimi ed ange scalabili y wi hou
d oping pe o mance.
The ep esen a ion ha we ha e used is he same ha Sco Bilas sugges s[2].
7.3 Resou ce Manage
The esou ce manage is he sys em ha akes ca e o accessing he seconda y
s o age memo y. I p o ides all he o he sys em componen s an in e ace o
ge esou ces when hey need hem wi hou ha ing o wai . So basically, he
esou ce mange e u ns a handle o he esou ce when i ge s a eques . E en
i he esou ce is no loaded, i should e u n a handle (ins an aneously).
The ollowing comic shows in a iendly way how he esou ce manage
wo ks.
31

I need ex u e "ki en.png".
I'm going o ask
Resou ceManage o i .
Hi, m . RM.
I need "ki en.png"
Ok, le me check.
So y, dude. Tha ex u e
is no in RAM.
I will ha e o load i om
disk. When loaded you
will find i a add ess 42. Ok
While he esou ce
is being loaded, I
can do o he hings.
Figu e 25: Comic o he esou ce manage .
32
As you can see, e en hough he esou ce manage says ha he eques ed
esou ce is no in RAM, he ells he eques e ha when i becomes loaded,
he will ind i a add ess 42 ( ha is he handle).
Take a look a ( his ime mo e se ious) ep esen a ion.
Wo ld
S eame
I need ex u e
"duck.png"
i is
loaded
yes
no
inc ease
e e ence
coun
inc ease
e e ence
coun
enqueue o
load
e u n handle e u n handle
RESOURCE MANAGER
INTERFACE
RESOURCE MANAGER
INDEPENDENT
THREAD
o
e
e
load
esou ce
Figu e 26: Diag am o he esou ce manage .
The esou ce handle is e u ned in all cases. The handle has an a ibu e
ha ells i he esou ce is loaded o no .
So o ins ance, he ende e needs o d aw a ex u e. The e o e, he
g aphics sys em eques s o he esou ce manage ha ex u e. E e y ame,
he g aphics sys em will check i he esou ce has been loaded. And i i is,
he ex u e is d awn.
The esou ce manage needs o keep ack o how many handles a e poin -
ing o each esou ce. When he numbe o handles o one esou ce becomes
ze o, he esou ce is eleased.
I one esou ce needs o be loaded, ha eques is enqueued in a special
queue. Wha is so special abou his queue is ha i is p epa ed o being
accessed by se e al h eads ( h ead sa e queue). This ype o queue is usually
called wo k queue.
In ou implemen a ion he e is he abs ac class Resou ce. These a e
some o he classes ha inhe i om Resou ce:
33
•Resou ceTex . I ep esen s a ex ile on disk. When loaded you
will be able o ead he ile using ”ge Tex ()”.
•Resou ceTex u e. This is he esou ce ha will be equi ed by he
sp i es. When loaded you can call ”ge Tex u eDa a()” and you will be
gi en a poin e o he aw ex u e da a.
•Resou ceCell. This esou ce is qui e special. When loaded, you will
be able o ge he da a also. Bu his ime you can modi y he da a.
You a e gi en a XML node and you can modi y i . When he e a e no
e e ences o a Resou ceCell i will be eleased and all changes made
will be s o ed. This esou ce is used o ep esen a cell whe e en i ies
can be placed. The e o e, you can add and emo e en i ies om he
cell and seamlessly all changes will be pe sis en .
The esou ce manage is a single on and needs o be ini ialized a he
beginning o he applica ion. In o de o do so, jus call ”launch()”. Tha
will s a he seconda y h ead.
In o de o implemen he wo k queue, I used p h eads and I go inspi ed
by his a icle[16].
7.4 Wo ld S eame
The wo ld s eame is in cha ge o elling which en i ies should be loaded and
which ones should be dele ed. The wo ld is di ided in equally sized squa es
and inside each o hese cells we will place he en i ies.
Figu e 27: When changing o cell some cells a e loaded and some o he s
become dele ed.
Each cell is ep esen ed in an XML ile and hey a e named as ”cell X Y.xml”.
Take a look a his example o XML ile:
34
<cell>
<en i y>
<posi ion>
<x>109.925</x>
<y>180.015</y>
</posi ion>
<g aphics>
< ex u e> uki oc.png</ ex u e>
<wid h>120</wid h>
<heigh >120</heigh >
</g aphics>
<physics>
<shape>box</shape>
<wid h>120</wid h>
<heigh >120</heigh >
<mass>60</mass>
</physics>
</en i y>
<en i y>
<posi ion>
<x>9.91001</x>
<y>112.793</y>
</posi ion>
<g aphics>
< ex u e>wood_box.png</ ex u e>
<wid h>80</wid h>
<heigh >80</heigh >
</g aphics>
<physics>
<shape>box</shape>
<wid h>80</wid h>
<heigh >80</heigh >
<mass>60</mass>
</physics>
</en i y>
</cell>
In his example you can see he e a e wo en i ies a ached o he oo
node (cell). Each en i y has posi ion, g aphics componen and physics com-
ponen . Inside he g aphics componen he e is he ex u e and he dimen-
sions. In some cases, you will ind ”p io i y” o he g aphics componen . I
35
he p io i y is no speci ied, ze o will be assumed.
A he beginning he wo ld s eame will sea ch in he ”wo ld olde ” di-
ec o y o all iles named like ”cell X Y.xml” (whe e X and Y a e in ege s).
The a e no es ic ions in he shape o he wo ld. All he ollowing shapes
a e alid.
Figu e 28: Examples o alid wo ld shapes.
I an en i y ge s ou o a cell and ge s in a space whe e he e is no cell
(wha is no g een in he p e ious pic u e), he en i y is s o ed in he las
alid cell i was. So i is he job o he designe o make su e no en i y will
ge ou side o he map.
Main cha ac e ,
whe e a e you?
I'm a
(251, 217)
You ha e changed
o cell!
The main cha ac e has changed o cell.
I mus dele e all he old en i ies, c ea e
he new ones and mo e he o igin o
coo dina es.
MC
WS
Figu e 29: Wo ld s eame ealizes ha he main cha ac e has changed o
cell.
The wo ld s eame implemen s he IWo ldS eame in e ace, so you
can ha e se e al implemen a ions o he wo ld s eame . In he ea ly be-
36

ginning, when he Wo ldS eame was no s ill implemen ed, we w o e Tes -
Wo ldS eame . This class jus s eams one en i y and i s implemen a ion
was p e y s igh o wa d. This way o p og amming allowed us o make
a as p o o ype and check ha all he sys em componen s we e in e ac -
ing p ope ly. The main unc ions o his in e ace a e: ini (),upda e() and
ge En i ies().
The implemen a ion o he upda e() unc ion is he co e o he sys em. I
de e mines he lis o ac i e en i ies. I s implemen a ion is one o he longes
bu i is no as di icul as i migh seem a i s . The ollowing diag am sums
up wha his unc ion does.
i ou
o bounds
yes change o cell
i main cha ac e
changed o cell
no
yes change o igin
o coo dina es
elease old
cells
load new cells
pa se loaded
cells (XML)
end
FOR EACH ENTITY
Figu e 30: Flow diag am o he upda e unc ion o he Wo ldS eame .
37
In each ame we check o cells (XML iles) ha ha e been loaded and
we pa se hem. A e pa sing, we c ea e he new en i ies.
Dele ing a cell in ol es c ea ing an XML ee, emo ing all en i ies and
inally eques ing he esou ce manage o elease he XML ile ( hus sa ing
i ).
Also, we mus handle when he use closes he applica ion. So when he
use closes he window o p esses Esc we mus sa e all he ac i e cells.
In o de o pa se XML and modi y he ees, we ha e used RapidXml.
This lib a y claims o be he as es ou he e. The e is also a high-le el
w appe o his lib a y in he amous Boos lib a y collec ion bu I ealized
la e . Anyhow, I ha e ound i o be pleasan o use. The only pi all I ha e
ound wi h his lib a y is a small compiling e o he e is when gene a ing
he ex o he ee. I seems o be a bug ha can be easily sol ed[17].
When I had o implemen he code ha looks cell iles in a ce ain di ec-
o y, I had o use a ex e nal lib a y: Boos Filesys em. I decided o use his
lib a y because o i s good po abili y. Also he Boos lib a ies a e gua an ee
o quali y.
8 Resul and es ing
The inal applica ion consis s o a s able game engine. Ye no ully- ea u ed.
No e: The e is sec ion 10, whe e we show a newe e sion o he engine.
Figu e 31: Demo sc eensho .
38
8.1 Demo
As you can see, we ha e de eloped a demo using ou game engine. A e
a lo o debugging, e e y hing seems o wo k e y well. G aphics a e ine,
physics a e accu a e and o e all pe o mance is pe y good.
In o de o es ou sys em in ensi ely, we ha e w i en an sc ip ha
gene a es a andom wo ld. We ha e made ou es s wi h a wo ld o 1 million
cells (which is abou 4GB o XML iles). The iles mus be loca ed in he
”wo ld olde ” di ec o y. In he same olde he e is he main cha ac e ile
(main cha ac e .xml). In his ile you can con igu e he appea ance, posi ion
and o he s u o he main cha ac e .
Ou applica ion allows o zoom in and zoom ou he came a using he
mouse wheel. When you open he applica ion you will see some hing like in
igu e 31.
I you zoom ou he came a you will be able o see he bounda ies o he
isualiza ion.
Figu e 32: Zooming ou .
So i you zoom in enough, he playe will no ealize ha he en i ies a e
being loaded a he walks.
39
You can wa ch his ideo o he demo h ps://you u.be/ymecWxF886U.
The p e ious ideo shows he demo a he ime he i s pe o mance es s
whe e made.
The e i is a ideo o he engine wi h he la es ea u es (much be e
looking) h ps:// imeo.com/159836286.
8.2 Pe o mance
The memo y consump ion is e y low. Running wi h one million o cells we
ge a RAM consump ion o ∼70MB.
The wo ld window is he space ha will de e mine he se o en i ies ha
a e loaded a any gi en ime. We can con igu e he size o he wo ld window
in ini ile.xml. The wo ld window is always squa e shaped and he side is
always odd. The numbe you ha e o pu in he con igu a ion ile is no he
side o he wo ld window, i is (side−1)/2. This way, he in oduced numbe
is always alid.
The ollowing pic u es show di e en wo ld window sizes.
Figu e 33: Window size = 1.
40
</ ec >
< ime>0.2</ ime>
</ ame>
</anim>
</anima ions>
</sp i e>
I is use ul o ha e an id o e e y anima ion, so i ’s s aigh o wa d o
se an anima ion p og amma ically. I we wish o make an sp i e which is no
anima ed, we can make an anima ion wi h only one ame, since anima ions
loop by de aul .
In he ollowing diag am we y o ep esen he mechanism we use in
o de o load and display sp i es.
47

Figu e 38: Flow cha o he sp i e’s loading p ocess
Now he e a e mo e s eps han when we had jus s a ic images. We need
o ead he XML o each sp i e and om ha ile ob ain he ex u es ha
mus be loaded.
In he same way we made su e ha no ex u e is wice in memo y, we
wan o make su e no sp i e is wice in memo y. The class Sp i e con ains he
da a which is common o all he en i ies using i . And he class Sp i eS a us
only keeps ack o he cu en s a us o he anima ion. Tha is, he cu en
ame and he ime spen in he cu en ame.
48
Figu e 39: UML ep esen a ion o he Sp i e and Sp i eS a us classes
In o de o es he anima ion sys em I ha e c ea ed a new au oma ic
wo ld gene a ion sc ip . You can ind i in ”bin/wo ld gens”. This new
gene a o makes be e looking wo lds. The wo ld is made up o a big se
o empla e cells (can be ound a bin/cell empla es). Ou gene a o akes
as inpu a ce ain numbe o ows and columns and ills he wo ld wi h
andomly chosen cell empla es. This is an example o wha we ha e seen
in 2.1. In his case we a e making a mix u e o manually gene a ed con en
and au oma ically gene a ed con en .
49
Figu e 40: Sc eensho o one gene a ed wo ld
In e ms o pe o mance we ha e pe o med he same es s we did and
i seems ha he anima ion sys em has no a ec ed a all. The bo leneck
keeps being he ende ing s age.
11 Fu u e ex ensions
I ha e aken he de elopmen o his game engine as a hobby. I p e end o
con inue he de elopmen in my spa e ime.
These a e some o he ea u es ha I would like o ge implemen ed.
•Sc ip ing: I ha e al eady s a ed wo king on his ea u e. Righ now,
implemen ing game logic is eally di icul . Since he beginning, he
game logic was in ended o be done by sc ip ing. When his ea u e
go implemen ed, I would conside he game engine usable o make
some eal games. I wan o embed he Lua p og amming language.
50
•Wo ld edi o ool: Righ now, e e y hing has o be done by edi ing
ex iles. I would be g ea o ha e a ool ha allows o edi he wo ld
and manage he asse s. Tha would make he engine iendlie o use.
•Sound: No game is comple e wi hou sound.
•Wo ld desc ip ion da a comp ession: I you gene a e a e y big
wo ld he wo ld olde ge s looded o small cell iles. Ge ing hese
iles packed in a single comp essed ile would sa e a lo o space and
would make he wo ld olde easie o manage.
12 License
The de eloped so wa e is open sou ce. I is licensed unde he MIT License.
The p ojec is hos ed in a public eposi o y:
h ps://gi hub.com/ uke /OWMAN.
13 Tools and dependencies
13.1 Used ools
•Code::Blocks. Used as he main IDE (in eg a ed de elopmen en i-
onmen ).
www.codeblocks.o g
•Doxygen. Au oma ic gene a ion o documen a ion om code co-
men s.
www.doxygen.o g
•Api ace. OpenGL debugge .
api ace.gi hub.io
13.2 Dependencies
•Boos FileSys em. Allows accessing he ile sys em.
www.boos .o g/libs/ ilesys em
•OpenGL. G aphics API.
www.opengl.o g
•SDL2. As window manage .
www.libsdl.o g
51
•RapidXML. Fo pa sing XML and modi iying he ee.
apidxml.sou ce o ge.ne
•Box2d. As he physics engine.
box2d.o g
•POSIX Th eads. Fo c ea ing h eads.
pubs.openg oup.o g/onlinepubs/7908799/xsh/p h ead.h.h ml
•SOIL. A small lib a y ha allows o load ex u es.
www.lonesock.ne /soil.h ml
•GLEW. A lib a y ha de ines he OpenGL ex ensions.
glew.sou ce o ge.ne
•GLM. A ma hema ics lib a y o OpenGL.
h p://glm.g- uc.ne
Re e ences
[1] Lis o he bes -selling ideogames.
h p://en.wikipedia.o g/wiki/Lis _o _bes -selling_ ideo_
games#All_pla o ms
[2] The Con inuous Wo ld o Dungeon Siege - Sco Bilas.
h p://sco bilas.com/ iles/2003/gdc_san_jose/con inuous_
wo ld_pape .pd
[3] Technical leads Adam Fowle and Phil Hooke ake us h ough he
echnology powe ing GTA V.
h p://www.de elop-online.ne /s udio-p o ile/
inside- ocks a -no h-pa -3- he- ech/0184140
[4] GTA a icle a Wikipedia.
h p://en.wikipedia.o g/wiki/G and_The _Au o_%28 ideo_
game%29
[5] Top 10 highes g ossing ideogames o all ime.
h p://www.businessinside .com/he e-a e- he- op-10-highes -g ossing- ideo-games-o -all- ime-2012-6?
op=1
[6] S ack O e low pos discou aging mul i h eaded ende ing wi h
OpenGL.
52

h p://s acko e low.com/ques ions/11097170/
mul i h eaded- ende ing-on-opengl
[7] Shade s on Wikipedia.
h p://en.wikipedia.o g/wiki/Shade
[8] GLSL on Wikipedia.
h p://en.wikipedia.o g/wiki/OpenGL_Shading_Language
[9] GLSL u o ial
h p://www.ligh house3d.com/ u o ials/glsl- u o ial
[10] Mode n OpenGL u o ial.
h ps://open.gl
[11] Lea n OpenGL.
h p://www.lea nopengl.com
[12] GLM o icial webpage.
h p://glm.g- uc.ne
[13] SDL o icial webpage.
h ps://www.libsdl.o g
[14] SOIL o icial webpage.
h p://www.lonesock.ne /soil.h ml
[15] Box2D o icial webpage.
h p://box2d.o g
[16] Mul i h eaded Wo k Queue in C++.
h p:// icha g a e.com/mul i h eaded-wo k-queue-in-c
[17] Solu ion o RapidXml bug a S ackO e low.
h p://s acko e low.com/ques ions/14113923/
apidxml-p in -heade -has-unde ined-me hods
[18] Game Coding Comple e - Mike McSha y and Da id G aham.
h p://www.mcsha y.com/GameCode
[19] Game Engine A chi ec u e - Jason G ego y
h p://www.gameenginebook.com
[20] TTMa h lib a y
h p://www. ma h.o g/
53
[21] Le el ( ideo gaming) - Wikipedia
h ps://en.wikipedia.o g/wiki/Le el_%28 ideo_gaming%29
[22] S eam discussion abou he small size o Re o Ci y Rampage
h p://s eamcommuni y.com/app/204630/discussions/0/
882962698536189638/
54