Visibili y Pa h- inding in ela ion o Hyb id S a egy-based Models in Dis ibu ed
In e ac i e Applica ions
De mo Madden, Declan Delaney
Depa men o Compu e Science, Na ional
Uni e si y o I eland, Maynoo h, Co. Kilda e.
[email p o ec ed]
Séamus McLoone, Tomás Wa d
Depa men o Elec onic Enginee ing, Na ional
Uni e si y o I eland, Maynoo h, Co. Kilda e.
{ omas.wa d, seamus.mcloone}@eeng.may.ie
Abs ac
The hyb id s a egy-based modeling app oach is a
me hod o educing he numbe o ne wo k packe s ha
need o be ansmi ed o main ain global consis ency in
Dis ibu ed In e ac i e Applica ions. I combines a sho -
e m model such as dead eckoning wi h a long- e m
s a egy model. A key aspec o his app oach is o
de e mine s a egies ha use s adop in na iga ing he
simula ed en i onmen o sa is y some objec i e o goal.
Compu e -gene a ed a i icial en i ies called BOTS,
na iga e by employing an A i icial In elligence echnique
called pa h inding. This pape p oposes using he A*
pa h inding algo i hm o au oma ically compu e s a egies
ha human use s migh ake h ough he simula ed
en i onmen . Since he A* algo i hm ope a es on a g aph
ep esen a ion o he en i onmen and because o he eal-
ime cons ain s imposed on Dis ibu ed In e ac i e
Applica ions, he pape also ca ies ou a compa a i e
analysis o wo ex eme g aph ep esen a ions o he
en i onmen – a s anda d egula g id and a minimal g id
ep esen a ion. The compa ison shows ha he minimal
g id leads o an o de o magni ude educ ion in eal- ime
compu a ion compa ed o he egula g id. In addi ion he
pa hs compu ed using he minimal g id and he A*
algo i hm a e used o de e mine s a egy models as pa o
he hyb id s a egy-based modeling app oach. I is shown
ha his educes he ne wo k a ic equi ed o main ain
global consis ency o en i y dynamics in wo simula ed
en i onmen s.
1. In oduc ion
Ne wo ked compu e p og ams ha allow use s o
in e ac in eal- ime in a simula ed en i onmen a e known
as Dis ibu ed In e ac i e Applica ions (DIAs). One o he
majo challenges acing he de elopmen and deploymen
o DIAs is he main enance o a consis en wo ld iew o
all pa icipan s in he ace o ne wo k la ency. Se e al
echniques o comba ing la ency ha e been documen ed
and implemen ed. Among hese, he hyb id s a egy-based
modeling echnique has shown a educ ion in he numbe
o packe s ha needs o be ansmi ed ac oss he ne wo k
o main ain global consis ency [1]. This echnique
ope a es by iden i ying long- e m s a egies ha use s may
adop in he pu sui o goals and only communica ing he
cu en use s a egy o o he pa icipan s. I is a hyb id
app oach in ha i combines a sho - e m dead eckoning
model wi h one o se e al possible long- e m s a egy
models. One key di icul y wi h his app oach is he
au oma ic de e mina ion o possible s a egies use s may
adop o achie e a gi en goal. In exis ing DIAs such as
compu e games, compu e -gene a ed a i icial en i ies
called BOTS, ace he same di icul y – gi en an ini ial
loca ion and an objec i e, wha is he bes me hod o adop
o each he objec i e while minimizing some cos
unc ion? This p oblem is e e ed o as pa h inding [2].
Pa h inding is an essen ial componen o he a i icial
in elligence (AI) ha makes BOTs appea mo e like
human use s. In DIAs such as ne wo ked games, up o
30% o compu a ional ime is spen on AI compu a ions,
p edominan ly pa h inding [3]. Pa h- inding algo i hms
consis o wo pa s:
1. he gene a ion o a sea ch g aph ha ep esen s he
unde lining en i onmen and
2. an algo i hm ha sea ches he g aph ep esen a ion
o ind a pa h connec ing gi en ini ial and a ge
loca ions.
The g aph ep esen a ion o a simula ed en i onmen
ep esen s he en i onmen by a se ies o nodes, wi h pa hs
h ough he en i onmen being cons ained o pass om
one node o ano he . A minimal se o nodes can be
achie ed by using a poin s o isibili y g aph o minimal
g id. O he possible ep esen a ions o he en i onmen
exis . P obabilis ic oadmaps andomly place nodes on a
map, connec ing newly placed nodes o nea by nodes [4].
Na iga ional Meshes spli he simula ed en i onmen in o
egions ha a e ee om obs acles, only allowing
na iga ion be ween hese egions [5]. Po en ial Field
me hods gi e he a ge loca ion an a ac i e o ce and
obs acles epulsi e o ces; en i ies hen ollow he
po en ial ield o he a ge [6]. O en nodes a e manually
placed wi hin he en i onmen o he compu ed nodes a e
weaked manually o imp o e he pe o mance o BOTs,
as in Un eal Tou namen [7].
Pa h inding algo i hms compu e he pa h h ough he
en i onmen unde some cons ain using he node
ep esen a ion o he en i onmen . The mos widely used
and a guably he bes pa h inding algo i hm used in DIAs
is he A* (A s a ) heu is ic sea ch [8], al hough o he s
exis such as B ead h- i s sea ch, Dep h- i s sea ch and
Dijks a’s algo i hm [9].
The g aph ep esen a ion o he en i onmen used in
pa h inding can ake many o ms. Examples include a
egula g id, a isibili y g id o a na iga ional mesh.
Howe e he e is a dea h o compa a i e esul s be ween
a ious g id ep esen a ions and pa h inding algo i hms.
The i s pa o his pape p o ides an ini ial con ibu ion
o his a ea by compa ing an implemen a ion o he A*
pa h inding algo i hm on bo h a isibili y g aph and
egula g aph ep esen a ion o a simula ed en i onmen .
I is shown ha he isibili y g aph p o ides an o de o
magni ude sa ing in compu a ional ime compa ed o he
same en i onmen ep esen ed by a egula g id. The
pape also p oposes a no el echnique based on he
isibili y g aph and A* algo i hm o au oma ically
de e mine s a egies use s may adop in na iga ing a
simula ed en i onmen . Two sample en i onmen s a e
used o illus a e how s a egies can be au oma ically
compu ed and da a will be p esen ed o show ha hese
s a egies lead o a educ ion in ne wo k packe s compa ed
o pu e dead eckoning when used as pa o he hyb id
s a egy-based modeling echnique.
In he ollowing sec ion we desc ibe he egula -g id
and isibili y g aph ep esen a ions o he unde lying
en i onmen . Sec ion 3 p esen s a compa a i e analysis o
he A* algo i hm using a egula -g aph and a poin s o
isibili y o minimal g aph. The applica ion o he A*
algo i hm and he minimal g id o he p oblem o
compu ing s a egy models in a gi en simula ed
en i onmen is desc ibed in sec ion 4 and he esul s o
simula ing ne wo k a ic using such a s a egy model is
gi en in sec ion 5. The pape hen ends wi h some
concluding ema ks and an indica ion o u u e wo k in
sec ion 6.
2. G aph Rep esen a ions o he En i onmen
In his sec ion wo possible ep esen a ions o he
simula ed en i onmen will be desc ibed: a egula sea ch
g aph [10] and a minimal g id o isibili y g aph [11]. In
gene al hese ep esen a ions a e a opposi e ends o he
node spec um, in ha he minimal g id ep esen s he
en i onmen by associa ing nodes wi h each obs acle,
whe eas he egula g id co e s all a eas o he
en i onmen ha a e ee om obs acles wi h nodes.
The e o e, he ac ual numbe o nodes in each case is a
unc ion o he numbe and size o obs acles wi hin he
en i onmen .
2.1 Regula G aph
A he simples le el simula ed en i onmen s consis o
obs acles ha mus be a oided and obs acle- ee o g ound
a eas ha can be eely na iga ed. Figu e 1a shows an
en i onmen wi h a single ec angula obs acle. A egula
sea ch g aph is o med by o e laying a egula g id o
nodes on he g ound a ea. Each node is connec ed o
adjacen nodes and an en i y can mo e om he node i
cu en ly inds i sel o any node connec ed o ha node.
Such a egula g id is illus a ed in Figu e 1b. The
absolu e g id spacing o g id spa ial esolu ion is dic a ed
by he uni s o measu e wi hin he simula ed en i onmen ,
each node on he g id being one uni om o he nodes in
bo h a ho izon al and e ical di ec ion [10, 12]. Gi en
such a g id oge he wi h bo h s a and a ge loca ions,
we can hen sea ch o a se o possible pa hs connec ing
he s a and a ge nodes. Figu e 1c shows he connec ed
g id, while Figu e 1d shows he sho es pa h solu ion
linking he s a and a ge nodes.
(a) (b)
(c) (d)
S a
a ge
obs acle
(a) (b)
(c) (d)
S a
a ge
obs acle
Figu e 1: (a) G ound a ea wi h obs acle; (b) Regula
g id; (c) Connec ed egula g id wi h ini ial and a ge
nodes; (d) Connec ed g id wi h pa h solu ion.
2.2 Visibili y G aph In he nex sec ion he egula and isibili y g aph
ep esen a ion o he en i onmen will be used by he A*
pa h inding algo i hm o disco e he sho es pa h
h ough an en i onmen . This will p o ide a compa a i e
analysis and g ea e unde s anding o he wo
ep esen a ions.
In con as o a egula g aph, a isibili y g aph loca es
he nodes a he e ices o obs acles, o a loca ions ha
will accu a ely delimi he obs acle. Each node is hen
connec ed o all o he nodes ha a e isible o i . This
equi es checking whe he nodes a e in line o sigh o
each o he . Figu e 2a shows he en i onmen wi h a
squa e obs acle. In Figu e 2b nodes ep esen ing he
e ices o he obs acle oge he wi h bo h s a and a ge
nodes a e shown. Figu e 2c demons a es some o he
pa hs ha migh be aken by an en i y mo ing om he
s a o a ge node wi hou going h ough he obs acle.
The sho es pa h is indica ed in Figu e 2d.
3. An Analysis o A* using Two g id Types
A es pla o m was de eloped o compa e he
pe o mance o he A* algo i hm using wo g aph
ep esen a ions. This phase o he wo k aimed o
unde s and he A* algo i hm and he isibili y g aph
ep esen a ion o he en i onmen in mo e de ail and
p o ide expe imen al e idence o he cos sa ing achie ed
by using he isibili y g aph wi h he A* algo i hm. This
p o ided mo i a ion o conside ing pa h inding as a
means o au oma ically de e mining possible s a egies
wi hin a Dis ibu ed In e ac i e Applica ion.
(a) (b)
(c) (d)
S a
a ge
(a) (b)
(c) (d)
S a
a ge
The A* sea ch algo i hm e alua es each node using he
sum o wo cos unc ions. The i s one calcula es he
cos o he pa h om he ini ial loca ion o he loca ion
being e alua ed. The second unc ion p o ides a heu is ic
es ima e o he emaining cos o each he a ge loca ion.
The sum o hese p o ides an es ima e o he o al pa h
cos h ough he e alua ed node. Du ing each i e a ion o
he sea ch, A* e alua es he nodes connec ed o he node
wi h he lowes es ima ed pa h cos , expanding he bes
node i s [8].
In his example he ini ial and a ge nodes a e
connec ed o all o he isible nodes. O he connec ion
c i e ia can be used; he ini ial and a ge nodes may be
connec ed o he nea es isibili y g aph node, o o he k
nea es nodes, o o all isible nodes wi hin a se dis ance.
Ob iously he possibili y o a di ec connec ion be ween
he ini ial and a ge nodes should be es ed o . Visibili y
g aphs hemsel es a e gene a ed o line and i has been
shown ha isibili y g aphs can be gene a ed in O(nlogn +
E) ime [13], whe e n is he numbe o nodes and E is he
numbe o edges in he g aphs.
Figu e 2: (a) G ound a ea and obs acle; (b)
Visibili y g aph wi h s a and a ge nodes; (c)
Connec ed isibili y g aph; (d) Connec ed g aph
wi h pa h solu ion.
Figu e 3: A sample map wi h andomly gene a ed
obs acles and he pa h compu ed using A* o a
egula g aph (le ) and a isibili y g aph ( igh ).
The de eloped es pla o m gene a es a andom map
and c ea es a isibili y g aph and egula g id; he A*
algo i hm is applied o hese g id ep esen a ions and he
esul s a e displayed oge he o ease o compa ison. In
he expe imen s pe o med he e en i onmen s we e
andomly gene a ed using a ying numbe s o obs acles;
each obs acle measu ed 5 by 5 uni s. An example o such
an en i onmen is gi en in Figu e 3. A egula g id and
isibili y g aph we e hen c ea ed o each en i onmen
and he es s we e ca ied ou .
The pe o mance o he A* algo i hm using each g id
was compu ed by exploi ing he high esolu ion ha dwa e
coun e , which is suppo ed by Mic oso Visual C++
2003. This coun e had a equency o 3,579,545 coun s
pe second on he es pla o m employed (AMD A hlon
XP 2600+ wi h 512MB RAM). The ac ual coun s we e
no ans o med in o absolu e ime alues as again we a e
only in e es ed in a ela i e compa ison.
A se ies o expe imen s was pe o med o de e mine he
compu a ion ime using bo h g aphs as he numbe o
obs acles in he en i onmen was inc eased om 0 o 140
on a map size o 50 by 50 uni s. In each case, 1000
andom maps wi h andom obs acles and andom
s a / a ge posi ions we e gene a ed and he a e age ime
coun o A* o inish i s sea ch was measu ed.
Figu e 4 illus a es he compu a ion ime as a unc ion
o he numbe o obs acles. When he e a e 100 obs acles
in he en i onmen a sea ch using he isibili y g id is
calcula ed in 10% o he ime equi ed by he egula g id,
demons a ing ha he isibili y g aph is as e by 90%.
Howe e as he numbe o obs acles inc eases wo e ec s
a e no iced: (1) he e is an inc ease in he sea ch imes o
bo h ep esen a ions and (2) he isibili y g id ge s
p og essi ely slowe in compa ison o he egula g id.
These wo e ec s may be explained as ollows. Fo he
egula g id, an inc ease in he numbe o obs acles means
a educ ion in he numbe o nodes and connec ions as
mo e g ound space is aken up wi h obs acles. Howe e ,
he e is also mo e ime was ed in compu ing dead end
pa hs. Fo he isibili y g aph, an inc ease in obs acles
esul s in an inc ease in he numbe o nodes and
connec ions wi h he numbe o connec ions being O(m2),
whe e m is he numbe o nodes. Despi e his, e en wi h
140 obs acles, he isibili y g aph is 80% as e .
The expe imen s pe o med indica e ha he A* pa h
inding algo i hm pe o ms signi ican ly be e using a
isibili y g aph han a egula g aph. Cu en ly pa h
inding is only used by compu e -gene a ed cha ac e s
na iga ing in he en i onmen . We use pa h inding o
au oma ically gene a e s a egies ha human use s may
adop in na iga ing he en i onmen . These s a egies can
be used in he hyb id s a egy-based model echnique.
These issues a e de eloped in he ollowing sec ion.
4. S a egy Models using Visibili y g aphs
Mo i a ed by he e iciency o he pa h inding
algo i hm using a isibili y g aph ep esen a ion and he
ac ha pa h inding is used by compu e gene a ed
cha ac e s, i was decided o use pa h inding o compu e
possible s a egies ha human use s migh choose when
na iga ing an en i onmen .
Regula G id
Visibili y G aph
Regula G id
Visibili y G aph
The hyb id s a egy-based modeling app oach educes
he numbe o upda e packe s ha need o be
communica ed be ween pa icipan s o a DIA o main ain
global consis ency wi hin a easonable e o h eshold.
The hyb id model consis s o a sho - e m dead eckoning
model and a leas one long- e m s a egy model. To
educe he numbe o packe s ha need o be ansmi ed,
he local use ansmi s in o ma ion o in o m o he use s
o he model ha bes ep esen s hei cu en ac i i y.
Remo e use s main ain his model un il he local use
decides a change is needed based on some h eshold
c i e ia, in his case an e o ole ance alue. Because he
long- e m s a egy model may ep esen a pa h o any
o m, i can be communica ed using a single packe in
con as o a dead eckoning ep esen a ion o he same
pa h, which may equi e se e al packe s. In p e ious wo k
s a egies we e chosen by isually selec ing he mos
ep esen a i e use s eady-s a e ajec o y [1, 14]. He e he
s a egies a e compu ed au oma ically using he A*
algo i hm and isibili y g aphs. Two es en i onmen s
we e cons uc ed and s a egies o he goal o na iga ing
om a s a o an end loca ion in he sho es ime possible
we e compu ed using A* and isibili y g aphs;
en i onmen s 1 and 2 a e shown in Figu es 5 and 6
espec i ely.
Figu e 4: The ime spen by A* o ind a pa h using he
isibili y g aph and he egula g id, as he numbe o
obs acles was inc eased on 50 by 50 maps wi h
andom obs acle posi ions.
By smoo hing he pa hs he s a egies can be made o
ma ch ac ual use mo emen mo e ealis ically. Figu e 7
shows he smoo hed pa hs o bo h en i onmen s a e
applying a s anda d smoo hing algo i hm ha akes en i y
dynamics in o accoun [2]. These smoo hed pa hs became
he s a egies ha we e used o simula e he gene a ion o
ne wo k packe s as pa o he hyb id s a egy model. This
simula ion is desc ibed in he ollowing sec ion.
Figu e 5: (a) Use en i onmen 1 (b) pa h
gene a ed au oma ically by A* algo i hm.
s a
End
(a)
(b)
s a
End
s a
End
(a)
(b)
En i onmen 1
X coo dina e
Y coo dina e
En i onmen 2
X coo dina e
Y coo dina e
(a)
(b)
En i onmen 1
X coo dina e
Y coo dina e
En i onmen 1
X coo dina e
Y coo dina e
En i onmen 2
X coo dina e
Y coo dina e
En i onmen 2
X coo dina e
Y coo dina e
(a)
(b)
Figu e 6: (a) Use en i onmen 2 (b) pa h
gene a ed au oma ically by A* algo i hm.
s a
End
(a)
(b)
s a
End
s a
End
(a)
(b)
Figu e 7: A ealis ic u ns ou ine was added o
c ea e mo e ealis ic s a egies, indica ed by he solid
line. The dashed line shows he s a egy ound b
y
pa h inding o (a) en i onmen 1 and (b)
en i onmen 2.
5. Simula ion Resul s
Use da a was ga he ed om ou een dis inc use s.
Each o hese use s maneu e ed an en i y h ough a maze
om a gi en s a posi ion o a gi en a ge loca ion.
Use s had no p io knowledge o he maze and we e
es ic ed o iewing a ci cula a ea o he maze cen e ed
on hei cu en loca ion a any poin in ime. Use s
epea ed he ask o a eling om he s a o he a ge
node in he sho es ime possible. Wi h each a emp hei
knowledge o he maze inc eased un il hey con e ged on

a s eady-s a e ajec o y. To de e mine he numbe o
packe s ha would ha e o be sen o e he ne wo k o
ep esen a use ajec o y a simula ion was pe o med
which ook he ajec o y as inpu and hen simula ed he
numbe o packe s gene a ed in h ee cases:
1. using a pu e dead eckoning model only;
2. using a hyb id s a egy model wi h he s a egy
chosen by isual analysis o he use s eady-s a e
ajec o ies;
3. using a hyb id s a egy model wi h he s a egy
compu ed au oma ically using he A* pa h inding
algo i hm and he isibili y g aph as desc ibed
ea lie .
Use 1 Use 2
Hyb id Hyb id Seq DR
Visual Pa h inding
DR
Visual Pa h inding
1 31 32 33 16 13 17
2 26 27 27 22 16 19
3 18 15 11 28 28 29
4 8 3 4 15 1 5
5 10 7 5 18 9 17
6 14 4 7 13 8 8
7 13 13 9 13 5 12
8 8 4 7 10 4 1
Use 1 Use 2
Hyb id Hyb id Seq DR
Visual Pa h inding
DR
Visual Pa h inding
1 35 42 36 52 44 51
2 38 32 34 25 23 24
3 22 6 9 34 23 26
4 18 3 3 21 4 10
5 16 6 3 24 20 21
6 20 3 3 18 7 11
The esul s o he simula ions a e p esen ed in Tables 1
and 2 o en i onmen 1 and en i onmen 2 espec i ely.
Examina ion o hese esul s shows ha he e is a
educ ion in he numbe o packe s ha need o be
ansmi ed using he hyb id s a egy-based model
app oach. In addi ion, he e is e y li le disc epancy
be ween he numbe o packe s ansmi ed using a
s a egy cons uc ed om isual analysis o eco ded use
ajec o ies and a s a egy cons uc ed au oma ically using
pa h inding. Two sample ajec o ies a e illus a ed in
Figu e 8 o use 1 na iga ing h ough en i onmen 2. As
hei expe ience wi hin he maze inc eases hei ajec o y
con e ges o he s eady-s a e s a egy iden i ied using pa h
inding. I mus be no ed ha he esul s p esen ed a e o
a h eshold o 25 uni s. This choice was based on he
a iance o he eco ded use s eady-s a e ajec o ies.
Resul s o a lowe h eshold alue ha e been p esen ed
elsewhe e [1, 2].
(a)
(b)
(a)
(b)
Table 1: En i onmen 1: packe s ansmi ed o pu e
dead eckoning and he hyb id me hod; s a eg
y
model chosen by isual analysis and pa h inding.
T ial 1 is he ini ial ial. Th eshold alue: 25.
Table 2: En i onmen 2: packe s ansmi ed o bo h
pu e dead eckoning and he hyb id me hod; s a eg
y
model chosen by isual analysis and pa h inding.
T ial 1 is he ini ial ial. Th eshold alue: 25.
Figu e 8: Use 1 na iga ing in en i onmen 2 – (a)
i s ajec o y - explo a o y; (b) inal ajec o y -
s eady-s a e. The s a egy model (solid line), pa h
inding model (dashed) line and use ajec o y (wide
line o ci cles) a e shown.
I all ials o he wo use s in bo h en i onmen s a e
conside ed, dead eckoning gene a es 596 packe s. In
compa ison he hyb id echnique (employing a isual
model) gene a es 402 packe s and he hyb id model
(employing a pa h inding model) gene a es 438 packe s.
This co esponds o educ ions o 33% o he isual
heu is ic Hyb id model, and 25% o he pa h inding
Hyb id model. The esul s show ha he educ ion in he
numbe o gene a ed packe s compa ed o dead eckoning
is simila o s a egies cons uc ed ei he isually o using
pa h inding. The key di e ence be ween he wo is ha
he pa h inding s a egy is gene a ed au oma ically.
6. Conclusions and Fu u e Wo k
I has been shown ha isibili y g aphs educe pa h
inding compu a ion ime by be ween 80 and 90%,
depending on he numbe and he densi y o obs acles in
he simula ed en i onmen . The isibili y g aph is also
insensi i e o map size, unlike he egula g id, which
makes i sui able o la ge i ual en i onmen s wi h ew
obs acles.
The A* pa h inding algo i hm was implemen ed on a
isibili y g aph and used o au oma ically gene a e s a egy
models. These we e used in he hyb id s a egy-based
modeling app oach and showed a educ ion in he numbe
o packe s needed o main ain global DIA consis ency.
The educ ion was commensu a e wi h p e ious wo k
using heu is ic echniques o de ining s a egies. The
ad an age o au oma ic iden i ica ion o s a egies using
A* and isibili y g aphs is wo old:
1. by educing he numbe o packe s ha need o be
ansmi ed ne wo k la ency is educed, as
packe s only need o be sen when he s a egy
changes; i communica ion is los o a longe
pe iod o ime, emo e use s can be ende ed
locally as con inuing on he s a egy hey we e on
be o e ne wo k connec ion was los ;
2. in he case o dynamic goals, i is p oposed ha
s a egies o sa is y he goal can be ecompu ed in
eal ime.
Fu u e wo k will ocus on using pa h inding echniques
o de e mine s a egies on he ly o dynamic goals. This
will wo k by p e-compu ing he isibili y g id o all use s
and hen employing he A* algo i hm o sea ch in eal ime
o a pa h be ween a cu en posi ion and a dynamic a ge
posi ion. The pa h inding implemen a ion will be
modi ied o use He shbe ge and Su i's me hods, which
p o ides a sho es pa h in O(nlogn) ime [15].
Acknowledgemen
This ma e ial is based upon wo ks suppo ed by
En e p ise I eland unde g an no. SC/2002/129/.
Re e ences
[1] Delaney, D., T. Wa d, and S. Mc Loone. On
Reducing En i y S a e Upda e Packe s in
Dis ibu ed In e ac i e Simula ions using a
Hyb id Model. in P oceeding o he 21s IASTED
In e na ional Mul i-con e ence on Applied
In o ma ics, Feb ua y 10-13. 2003. Innsb uck,
Aus ia.
[2] Pin e , M., Towa d mo e ealis ic Pa h inding.
Game De elope , 2001: p. 54-64.
[3] Woodcock, S., Game AI: The S a e o he
Indus y 2000-2001: I ’s No Jus A , I ’s
Enginee ing. Game De elope , Augus 2001.
[4] Ka aki, L.E., e al., P obabilis ic Roadmaps o
Pa h inding in High-Dimensional Space. IEEE
T ansac ions on Robo ics and Au oma ion, 1996.
12(4): p. 556-580.
[5] Tzou , P., Building a Nea -Op imal Na iga ion
Mesh, in AI Game P og amming Wisdom. 2002,
Cha les Ri e Media. p. 171-185.
[6] Hwang, Y.K. and N. Ahuja, A Po en ial Field
App oach o Pa h inding. IEEE T ansac ions on
Robo ics and Au oma ion, 1992. 8(1): p. 23-32.
[7] Epic Games, Un eal Tou namen websi e:
h p://www.un eal ou namen .com/. 2004.
[8] Russell, S. and P. No ig, A i icial In elligence -
A mode n App oach. 1995: P en ice Hall.
[9] S ou , B., Sma Mo es: In elligen Pa h inding.
Game De elope , 1996: p. 28-35.
[10] Yap, P., G id-based Pa h inding - Lec u e no es
in A i icial In elligence. 2002. pp. 44-55.
[11] Lozano-Pe ez, T. and M.A. Wesley, An
Algo i hm o planning collision- ee pa hs
among polyhed al obs acles. Communica ions o
he ACM, 1979. 22(10).
[12] Ma hews, J., Basic A* Pa h inding Made
Simple, in AI Game P og amming Wisdom. 2002,
Cha les Ri e Media. p. 105-113.
[13] Ghosh, S.K. and D.M. Moun , An Ou pu -
sensi i e algo i hm o compu ing isibili y
g aphs. Socie y o Indus ial and Applied
Ma hema ics (SIAM) Jou nal o Compu ing,
1991. 20(5): p. 888-910.
[14] Delaney, D., T. Wa d, and S. Mc Loone.
Reducing Upda e Packe s in Dis ibu ed
In e ac i e Applica ions using a Hyb id Model. in
16 h In e na ional Con e ence on Pa allel and
Dis ibu ed Compu ing Sys ems, Augus 13-15.
2003. Reno, USA.
[15] He shbe ge , J. and S. Su i, An op imal algo i hm
o Euclidean sho es pa hs in he plane. Socie y
o Indus ial and Applied Ma hema ics (SIAM)
Jou nal o Compu ing, 1997. 28(6): p. 2215-2256.