TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.7, July 201
4, pp
. 5537 ~ 55
4
5
DOI: 10.115
9
1
/telkomni
ka.
v
12i7.429
2
5537
Re
cei
v
ed Au
gust 31, 20
13
; Revi
sed Fe
brua
ry 19, 20
14; Accepted
March 7, 201
4
Performance Analysis of Pathfinding Algorithms Based
on Map Distribution
Yan Li*, Zhenhua Zhou,
Wenju Zh
ao
Ke
y
Lab. of Ma
chin
e Le
arni
ng
and Com
putat
i
ona
l Intelli
ge
nc
eof Heb
e
i U
n
iv
ersit
y
Coll
eg
e of Mathematics a
nd
Comp
uter Scie
nce, Heb
e
i u
n
i
v
ersit
y
, Ba
odi
n
g
, 1873
02
72
72
5
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: l
y
@
h
b
u
.cn
A
b
st
r
a
ct
T
he distri
buti
o
n infor
m
atio
n
of ga
me
maps
is hi
gh
ly rel
e
v
ant to the
ex
e
c
ution
efficie
n
c
y
of path
search
ing and the
de
gree of
ga
me
d
i
ffi
culty. T
h
is pap
er an
aly
z
e
s
the r
e
lat
i
ons
hip
betw
e
e
n
the pathfi
n
d
i
n
g
perfor
m
a
n
ce
a
nd th
e o
b
stacl
e
s distri
buti
on
in
ma
ps
fro
m
t
w
o aspects, p
a
thfind
in
g al
go
rithm des
ig
n a
n
d
ga
me
’
s
ma
p d
e
sig
n
res
pecti
vely. A h
i
erar
chical
p
a
thfind
ing al
gorith
m
calle
d
C
DHPA
*
is prop
ose
d
b
y
incor
porati
ng t
he obstac
l
e d
i
s
t
ributio
n in trad
ition
a
l HPA*
al
gorith
m
. It is used to hier
arch
ical p
a
th searc
h
in
those
ma
ps w
here th
e obsta
cles are
dens
e
l
y distrib
u
ted.
On the other h
and, a
ma
p co
mp
lexity
metric
is
defin
ed b
a
se
d
on the accu
mu
lati
on of xo
r calcul
ati
ons
of given
maps
. T
h
is meas
ur
e descri
bes th
e
compl
e
xity of
a
map
a
nd
he
nce co
ul
d refl
ect the
p
e
rfor
ma
nce
of p
a
th
findi
ng
alg
o
rith
ms, w
h
ich
cou
l
d
provi
de refere
n
c
es for ga
me
ma
ps des
ign.
T
he ex
per
i
m
en
tal results hav
e
valid
ated the p
r
opos
ed a
nalys
is.
Ke
y
w
ords
:
pat
hfind
i
ng
alg
o
rit
h
m, p
e
rforman
c
e ana
l
ysis, map distri
butio
n, abstract map
Copy
right
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
In the map
s
of comp
uter
game
s
, the q
ualit
y and respon
se
spe
ed
of pathfindin
g
dire
ctly
affect the
exp
e
rien
ce
an
d
satisfactio
n
d
e
g
ree
of
g
a
me
players. M
o
st of the exi
s
ting p
a
thfindin
g
algorith
m
s su
ch as A*[1-2] and Dij
kst
ra [3], howev
er, do not con
s
id
er the distri
bu
tion informati
on
of ob
stacl
e
s,
whi
c
h
ca
use
s
u
nne
ce
ssary time
and
st
orag
e
co
st. Another exa
m
ple i
s
HPA*[4],
whi
c
h is
a typical fa
st alg
o
rithm u
s
ing
the con
c
e
p
t of hiera
r
chy and ab
stract
map to spee
d up
the traditio
n
a
l
A* an
d effe
ctively red
u
e
s
the
s
earch
sp
ace. It do
es
not
con
s
i
der th
e te
rrai
n
informatio
n when formin
g the abst
r
a
c
t map and p
r
o
duces some
unne
ce
ssary
extensio
n no
des
and
red
u
ces
the path
opti
m
ality, which
is e
s
p
e
ci
a
lly obviou
s
in
a
map
with a
l
a
rge
fre
e
a
r
e
a
.
Beside
s, M-A*[5] divides the map into uneq
ual
sub-regi
on
s b
y
multi-
scale
strategy bef
ore
forming its ab
stra
ct map. It only consi
d
e
r
s the
lo
catio
n
information
of start node
and goal no
de
in the partitio
n
pro
c
e
ss,
which d
e
crea
ses the
spee
d
of pathfindin
g
and
in
creases the exten
s
ion
node
s. Q
uadt
ree [6]
algo
rithm do
es con
s
ide
r
the
info
rmation
of m
ap di
strib
u
tio
n
when
dividi
ng
the map into clu
s
ters, but the co
ndition
of partition te
rmination is to
o strict to re
q
u
ire ea
ch
clu
s
ter
contai
ning
on
ly one type
of node
s. As a re
sul
t, bot
h the num
be
r of sub a
r
e
a
s a
nd a
b
stract
node
s a
r
e l
a
rge, whi
c
h l
e
a
d
s to
a lot of
memory
co
st. Furthe
r, the
s
e algo
rithm
s
only use lo
cal
A*
algorith
m
to
calcul
ate the
shorte
st pat
h i
n
ea
ch
pai
r a
b
stra
ct
node
s and
refine p
a
ths. T
hey d
o
n
’t
sele
ct suitabl
e algo
rithm a
c
cordi
ng to th
e dist
ri
bution
informatio
n of
sub
-
regio
n
s,
whi
c
h
redu
ces
the overall ex
ecutio
n efficie
n
cy of pathfin
ding alg
o
rith
m to some ex
tent.
In fact, the search
perfo
rmance
could
be ve
ry
different
even f
o
r o
ne give
n
algo
rithm
whe
n
the ma
ps have diffe
rent di
stributi
ons of ob
sta
c
les. We
ca
nn
ot find an alg
o
rithm which is
workin
g the best in all types of map
s
with re
sp
e
c
t to the densit
y of obstacle
s
. Therefore,
the
distrib
u
tion i
n
formation
in t
he ma
p
scen
e shoul
d
b
e
con
s
id
ere
d
when th
e p
a
thfinding
algo
rit
h
m
is de
sign
ed.
Different p
a
th
finding alg
o
rit
h
ms
sho
u
ld
b
e
sel
e
cted fo
r different sub-regio
n
s. O
n
the
other ha
nd, we attempt to prop
ose a
complexi
ty measure for maps
whi
c
h
coul
d refle
c
t the
difficulty for path se
archi
ng (whi
ch can be def
in
ed by sea
r
ching time).
Then p
a
thfin
d
ing
algorith
m
s
ca
n also be
an
alyzed th
rou
gh the
comp
ut
ation of the
compl
e
xity measure. In this
pape
r,
we
prese
n
t a
ne
w hie
r
archi
c
al
pathfi
ndin
g
a
l
gorithm
CDHPA* b
a
sed
on the
o
b
sta
c
le
distrib
u
tion a
nd a ne
w m
ap co
mplexit
y
metric call
ed ACX ba
sed on the a
c
cumul
a
tion of
xor
cal
c
ulatio
n, which
furthe
r
a
nalyze
s
th
e relation
ship
b
e
twee
n the
o
b
sta
c
le
s di
stribution
and t
he
executio
n efficien
cy of pathfinding.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 7, July 201
4: 5537 – 55
45
5538
2. Relate
d Resera
c
h
A*[1] is a kin
d
of pathfindin
g
algo
rithm b
a
se
d on a h
e
u
risti
c
fun
c
tio
n
whi
c
h e
s
tim
a
tes the
distan
ce
bet
wee
n
the
current no
de a
n
d
the go
al
no
de an
d the n
e
xt search
n
ode i
s
sele
cted. It
can
effectivel
y redu
ce the
sea
r
ching tim
e
by movi
ng t
o
the mo
st ho
peful directio
n, and so it ru
ns
faster th
an
Di
jkst
ra [3]. But as
we
have
mentione
d, th
e scale
and
o
b
sta
c
le
s di
stri
bution of m
a
p
s
influen
ce
s its perfo
rman
ce
greatly.
There a
r
e
ma
ny improvem
ent versio
ns
of A*.
HPA*[4
] algo
rithm i
s
a ki
nd
of hi
erarchical
pathfindin
g
al
gorithm
which is ba
se
d o
n
ab
stract
graph. Fi
rst, it
con
s
tru
c
t
s
a
n
ab
stra
ct g
r
a
p
h
throug
h dividi
ng o
r
iginal
m
ap into
som
e
uniform
cl
usters and
li
nks
the key no
des of
adj
acent
clu
s
ters. The
n
A* algo
rith
m is u
s
ed
o
n
the ab
stra
ct graph to fin
d
an ab
stract
path. Finally
, it
refine
s the
ab
stra
ct path to
get a lo
cal
n
ear-opt
imal
p
a
th between t
he sta
r
t no
de
and g
oal n
o
de.
Whe
n
the m
a
p is in l
a
rge-scale, HPA*
coul
d
divide
s the map i
n
to
a multi-laye
r abst
r
a
c
t ma
ps,
and fu
rthe
r
narro
ws the
ab
stra
ct
sp
ace.
Noti
ce
that HPA*
d
oes not
co
n
s
ide
r
the
terrain
information in the
process
of ab
straction and refinem
ent. Thi
s
w
ill
reduce the optimality of the
found p
a
th in
larg
e fre
e
re
gion
s in
give
n map
s
. Q
u
a
d
tree[6] i
s
al
so
a hie
r
a
r
ch
ical p
a
thfindi
ng
algorith
m
, bu
t it is different from HPA* in its
map division meth
od.
It
first divides the map int
o
four unifo
rm
clu
s
ters, and
che
c
ks th
e st
ate of all cell
s in ea
ch
su
b
-
clu
s
te
rs
re
sp
ectively. If all of
the cells are
obstacles/non-obstacl
es i
n
current
cluster, thi
s
cl
uster
will not
be divided furt
her.
Otherwise, the cu
rrent cl
uster will
contin
ue to be
divided into fou
r
u
n
iform
sub
-
cl
usters u
n
til e
a
ch
clu
s
ter only contain
s
one type of cells. Then t
he inte
rmedi
ate nod
e of each cl
u
s
ter an
d som
e
node
s
sele
ct
ed in th
e bo
unda
ry will
b
e
linked
and
thus fo
rming
the ab
stra
ct
grap
h. Qu
adt
ree
algorith
m
con
s
ide
r
s the m
a
p dist
ributio
n
in the p
r
o
c
e
s
s of divi
sion,
but it req
u
ires each
clu
s
ter
to
contai
n only
one type of cells, which i
n
cre
a
ses th
e
numbe
r of cl
usters a
nd th
en the nu
mb
er of
abstract
nod
es. M
-
A*[5] is a
pathfindi
ng alg
o
rith
m
usin
g
multi-scale environ
mental
info
rmation
and
co
nsi
ders the
influ
ence of
different
sea
r
ch ta
sk
s
in the
process of
divisi
on.
It tends to
ref
i
ne
the cl
uste
rs
near the
sta
r
t node
an
d d
e
stinatio
n n
o
de. First, M
-
A* divide
s th
e ma
p into
four
uniform
clu
s
ters li
ke Q
uad
trees
and jud
ges
wheth
e
r t
he sta
r
t/goal
node i
s
in the
current cl
ust
e
r
or not. It onl
y further divi
des th
e cl
ust
e
r that
c
ontai
ns the
sta
r
t or go
al no
de
until the cl
u
s
ter
contai
ns only
one
cell. Th
en M
-
A*
use
s
a
b
o
ttom-u
p
fusi
on
algo
rithm to
calculate the
sho
r
test
distan
ce
of al
l free
cell
s i
n
each p
a
rtition
bou
nda
ry, a
nd g
e
ts th
e a
b
stra
ct m
ap.
M-A* imp
r
ove
s
the com
putati
onal complex
i
ty of A* in th
e wors
t case. But,the process of division neglects the
obsta
cle di
stribution an
d its nee
ds to
re
peat t
he division process
whe
nev
er th
e
the start no
de
and the de
sti
nation no
de a
r
e ch
ang
ed.
In this pap
er,
we devel
op
a ne
w hie
r
archical
p
a
thfind
ing algo
rithm
based on th
e
idea of
abstract
grap
h, whi
c
h
rela
xes the
divisi
on
crite
r
ia
i
n
Quadtree
accordin
g to
the
obsta
cle
de
n
s
ity.
The pu
rp
ose
is to improve
the efficien
cy and the
opt
imality in maps that ob
sta
c
le
s are de
nsely
distrib
u
ted in
some
su
b-regio
n
s. To
furt
her a
n
a
l
yze the relationship bet
wee
n
the m
a
p
distrib
u
tion a
nd the pathfin
ding pe
rform
ance, we al
so
study the co
mplexity metrics of a ma
p.
Many schol
ars have p
u
t forwa
r
d a l
o
t of metr
ics from
the perspe
c
ti
ve of geog
ra
phy and
gene
rali
zed
d
i
agra
m
in dat
a stru
ctu
r
e fo
r re
al map
s
. [7] use
s
the
concept of ent
ropy to calcul
ate
the map
com
p
lexity, and [8] prop
oses
a com
p
lexity
metric of
the geog
rap
h
ical distrib
u
tion
a
nd
conto
u
r fig
u
re
. [9] mea
s
ure
s
the
comple
xity us
ing
bo
unda
ry ind
e
x, bou
nda
ry co
ntrast
index,
and
mitotic
res
p
ec
tively. However, thes
e methods
are n
o
t applicable
to game map
s
, so some ot
her
related meth
ods a
r
e put forward in the field
of AI.
[10] propo
se
s a method ba
sed on
Ham
m
ing
Dista
n
ce, whi
c
h
co
mpute
s
the
com
p
lex
i
ty by ca
l
c
ul
a
t
ing the
num
ber of diffe
re
nt bits bet
we
en
two bit strin
g
s
. [11] defines a ga
me
map co
mp
le
xity using rel
a
tive Hammi
ng Di
stan
ce,
and
introdu
ce
s th
e con
c
ept of regio
nal varia
n
ce. Both
of the two metri
c
s are defin
ed
by the differ
ent
numbe
r of
cells
with respect to
every neighb
ori
n
g ro
ws o
r
co
lums i
n
a
gi
ven map,
wit
hout
con
s
id
erin
g the sh
ape of o
b
sta
c
le
s or th
e geomet
rical
prope
rty.
3. Rese
arch
Metho
d
In this se
ction
,
two method
s pro
p
o
s
ed in
this pape
r wil
l
be elabo
rate
d.
3.1. Hierarch
ical pathfin
d
i
ng algorit
h
m
based on
map distribu
tion—
CDHP
A*
In large-scale
comme
rci
a
l comp
uter ga
mes,
many o
b
sta
c
le
s are
den
sely distri
buted in
the map
scen
e such a
s
bui
lding
s
, la
ke
s
and m
ountai
n
s
. Th
ere
a
r
e
often large f
r
ee a
r
ea
s
exist in
this type
of m
ap. If we
divi
de the
ma
p i
n
to unifo
rm
cl
usters sim
p
ly acco
rdin
g to
the p
o
sitio
n
s of
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Perform
a
n
c
e
Analysis of P
a
thfinding Alg
o
rithm
s
Base
d on Map Di
stribution (Ya
n
Li)
5539
start and go
al
nodes a
nd o
n
ly use A* algorithm to ca
l
c
ulate the sho
r
test distan
ce
s in all clusters,
the path opti
m
ality and se
arching
sp
ee
d will be
affe
cted in th
e free area
s. Thi
s
pa
per
pre
s
ents
CDHPA*, whi
c
h co
nsi
d
e
r
s
the distrib
u
tio
n
informat
ion
of obstacl
es i
n
the process of division and
refinem
ent. First, the give
n map is div
i
ded into un
equal
sub
-
re
gion
s ba
sed
on the ob
sta
c
le
distrib
u
tion, whe
r
e the nu
mber of
sub-region
s is det
ermin
ed by
adjusta
ble pre
defined threshold.
Secon
d
, the f
r
ee
bou
nda
ry node
s i
n
the
sub
-
regio
n
s
a
r
e
con
n
e
c
ted
as a
b
st
ra
ct n
ode
s to form
a
compl
e
te
a
b
stract
g
r
a
ph. The sho
r
te
st path
b
e
tw
e
e
n
ea
ch
pair of
ab
stra
ct no
d
e
s i
s
cal
c
ulat
ed
by Manh
attan di
stance o
r
bottom-up f
u
sio
n
al
g
o
rith
m dep
endi
ng
on the
de
nsity of obsta
cl
es.
Finally, we find an ab
stra
ct path on th
e gene
rat
ed
abstract g
r
ap
h and then
convert the ab
stra
ct
path to an lo
cal p
a
th. Both A* and Brese
nham[1
2-13] algo
rithm
are u
s
e
d
in
the pro
c
e
ss of
refinem
ent a
c
cordi
ng to
differnt ob
sta
c
le d
ens
ity. A* is used f
o
r region
s t
hat have ma
ny
obsta
cle
s
a
n
d
Bre
s
e
nha
m algo
rithm
for fre
e
a
r
ea
s. Bre
s
e
nha
m’s
spe
ed i
s
fa
ster
and
the
extended n
o
des a
r
e le
ss than A* in fre
e
are
a
s.
Next, we will intro
duce the det
ails of CDHP
A*,
and its pathfi
nding p
r
o
c
e
s
s ca
n be divid
ed into
two p
a
rts—preprocessing
a
nd o
n
line pathfin
d
i
ng.
3.1.1. Prepro
cessing
This p
a
rt m
a
inly contai
n
s
map divi
si
on,
key no
d
e
s sele
ction
and the formation of
abstract g
r
ap
h according t
o
the obsta
cl
e distrib
u
tion.
Step 1.
Tra
n
s
form a
real
map to a grid
map. Here we requi
re the
size of the map to be
n*n and n
=
2
j
,
j is an integer. This is because the map
will be divided into f
our equal sub-regions
in each divisi
on ba
sed o
n
the idea in
Quadtree
a
n
d
M-A*. Figu
re 1 is a m
a
p sele
cted from
Baldurs
Gate
II
[14] and
its
scale i
s
64*
64. Figu
re
2 i
s
a
gri
d
m
ap
that is th
e tra
n
sform result of
Figure 1. In Figure 2, the o
b
sta
c
le
s cell
s gather
toget
her, and the
white cells re
pre
s
ent walkable
area.
Step 2.
Build
a quadtree a
c
cordi
ng to the propo
rtio
n
of the obsta
cle
s
, in whi
c
h
all final
sub
-
regio
n
s
are the l
eaf
node
s. First, the grid
ma
p is divid
ed i
n
to four e
q
u
a
l are
a
s
and
the
obsta
cle p
r
o
portion
of each
sub
-
regi
on
is
cal
c
ul
ated usi
ng f
o
rmul
a(1
)
. Among them,
#
ob
stacl
e
i
s
the num
ber o
f
obsta
cle
s
in
cu
rre
nt re
gio
n
, #
total
is th
e total num
be
r of no
de
s in t
he
c
u
rr
en
t r
e
g
i
on
.
#
#
ob
st
a
c
l
e
tot
a
l
(
1
)
In Quadtree, the division
will continu
e
u
n
t
il each
sub
-
regio
n
co
ntai
ning only on
e
type
o
f
cell
s, i.e., free cell
or o
b
st
acle
cell. Thi
s
is too
stri
ct a
nd tend
s to g
enerate lots
o
f
sub
-
area
s a
nd
node
s in a
b
st
ract g
r
ap
h. Here, we set a
threshold
experimentally to relax this
stop
criterion.
The relation
betwe
en
and
will determi
n
e whether
the current
su
b-region i
s
further
divided
or
not. Acco
rdingly, the
st
ates
of the
le
af nod
es (su
b
-regio
n
s) in
the qu
adtree
is m
a
rked
by
.
There are three ki
nds
of situations: (1)
= 0, which
m
ean
s the current are
a
ha
s no ob
stacl
e
and ne
ed not
to be divided
any longe
r. In this ca
se, assign
=1 to cu
rrent sub-regi
on (leaf no
de
and ob
stacl
e
se
ction); (2
) 0<
<
mean
s t
hat the
ratio
of ob
stacl
e
cells
and f
r
ee
cell
s i
s
close
and thi
s
regio
n
sh
ould
cont
inue to
be div
i
ded; (3)
>
, mean
s the
cu
rrent re
gion
ha
s en
oug
h
obsta
cle
s
a
n
d
doe
s n
o
t n
eed furth
e
r
di
viding. The
st
ate marke
r
is set to 0
(leaf
node
and f
r
ee
se
ction).
Thi
s
metho
d
divid
e
s th
e o
r
igi
n
a
l
map
into
so
me n
on-unifo
rm
sub
-
regio
n
s, a
nd
a lot
of
them are fre
e
are
a
s. B
r
e
s
en
ham al
go
rithm can
b
e
use
d
to cal
c
ulate th
e shorte
st di
sta
n
ce
betwe
en ea
ch pair of ab
stract nod
es in t
h
is type of re
gion.
Figure 1. Rea
l
game
Map
Figure 2. Grid
Map
Figure 3. Partition
Re
sults
Figure 4. Shortest
Path
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 7, July 201
4: 5537 – 55
45
5540
We shoul
d mention that the value of thresh
old
is different in different maps. Its value
affects th
e n
u
mbe
r
of
su
b
-re
gion
s
dire
ctly, whi
c
h
fu
rther affect
s t
he n
u
mbe
r
of ab
stra
ct n
o
d
e
s,
extended
no
des,
and
the
sea
r
ching
tim
e
. The
r
efo
r
e,
the
suitabl
e
threshold
sho
u
ld b
e
fou
nd
to
balan
ce all
th
ese aspe
cts. For
Fi
gure
2, The
threshol
d
is
0.3 obtai
ned exp
e
rim
e
ntally. Figure
3 is the divisi
on re
sult of Figure 2, an
d it can
be see
n
that there a
r
e many free
area
s. The re
d
cell
s rep
r
e
s
e
n
t abstract no
des
whi
c
h are all free cell
s on regio
n
bo
unda
rie
s
.
Step 3.
From
an abstract
grap
h. After the pro
c
e
s
s o
f
division, CDHPA* com
put
es the
sho
r
t
e
st
dist
a
n
ce
f
o
r
ea
ch
pair
of
ab
st
ra
ct
no
de
s,
t
h
e
n
f
o
rm
s t
h
e a
b
st
ra
ct
g
r
a
p
h
ac
co
rdin
g t
o
value of e
a
ch
su
b-regio
n
.
Whe
n
is e
q
u
a
l to 1, it me
ans that the
curre
n
t re
gio
n
only
contai
ns
free
cell
s a
n
d
the Ma
nhatt
an di
stan
ce i
s
the
shorte
st
path.
Whe
n
is e
qual to
0,
it mean
s that
the curre
n
t re
gion ha
s a lot
of obstacl
e cells an
d A* is use
d
to cal
c
ul
ate the sho
r
te
st path.
To summ
ari
z
e, in the stage
of preprocessing, CDHPA* divides the map an
d cho
o
se
s
different m
e
thod
s to
cal
c
u
l
ate the
sh
ort
e
st di
st
an
ce
based
on th
e
dist
ribution
o
f
obsta
cle
s
. T
h
is
algorith
m
do
es n
o
t need t
he lo
cation in
formation
of start an
d go
a
l
node
s in di
vision like M-A*
doe
s. The
r
ef
ore, the p
r
ep
rocessin
g is
need
ed onl
y
once even fo
r multiple ta
sks. Althou
gh
the
threshold det
ermination
needs m
any experiments
i
n
advance, it
is
still acceptabl
e when we
taking the av
erag
e executing time
for many different task
s
.
3.1.2. Online Processing
Step 1
.
Insert the sta
r
t a
n
d
go
al n
ode
s into the
ab
st
ract
map. If t
he
start/goal
node
is
alrea
d
y an
ab
stra
ct n
ode, t
hen th
e in
se
rtion i
s
u
nne
ce
ssary a
nd
we
dire
ctly go
to
the n
e
xt step
.
Otherwise, we find the correspon
ding
sub-re
gion
based on th
e area in
dicator in the d
a
ta
stru
cture, an
d link eve
r
y boun
dary fre
e
cell
s in
the
corre
s
po
ndi
ng su
b-regi
o
n
, and finish
the
inse
rt
ion st
e
p
.
Step 2
. Find
an abstract
path betwee
n
the star
t a
nd goal no
de
in the abstract map.
First,
we ju
dg
e whethe
r th
e sta
r
t no
de
and
goal
nod
e lo
cate in
th
e same
regi
o
n
or not. If yes,
then CDHPA* dire
ctly cho
o
s
e
s
A* or B
r
e
s
en
ham al
go
rithm to find the sh
orte
st pat
h acco
rdin
g to
. Otherwi
se, this alg
o
rithm
use
s
A* to se
arch
ab
stra
ct
path and co
ntinue to exe
c
ute the next
step.
Step 3
. Refi
ne the ab
stra
ct path to a local o
ne. Co
nsid
erin
g eve
r
y sequ
ential
pair of
node
s
(on
e
node
an
d its next on
e) in
t
he
abst
r
a
c
t path, if th
e
state m
a
rke
r
of the
re
gio
n
contai
ning
ad
jace
nt nod
es of the curre
n
t pair
of
no
des i
s
e
qual
to 1, Bre
s
en
ham alg
o
rith
m is
use
d
to find the final path
betwe
en the
s
e two no
de
s. If that value of
equal
s to 0, A* is used to
find the fin
a
l
path
corre
s
p
ondin
g
ly. The
sp
eed
of p
a
thfinding
of Brese
nham
is faster than
A*
in
the free
are
a
s
. He
re
we h
a
ve co
nsi
dered the ma
p di
stributio
n an
d
sele
cts
different algo
rithm
s
to
path refine
m
ent. In Figure
4, the yellow line illu
strat
e
s the found
p
a
th betwe
en (5,5) an
d (60,
59)
in Figure 2, which i
s
also a sho
r
e
s
t path.
It can b
e
see
n
from th
e im
plementatio
n
pro
c
e
s
s of
CDHPA* th
at the ma
p di
stri
bution i
s
con
s
id
ere
d
in
both m
ap
division
and
pat
h refin
e
m
ent.
Acco
rdi
ng to t
he o
b
sta
c
le
s
distrib
u
tion,
we
cho
o
se the correspon
ding
method to abstra
c
t
and
refine path
s
, whi
c
h ca
n effectively improve
the executio
n
efficiency.
On the
othe
r
hand, th
e p
e
rforman
c
e
of
sea
r
ch
algo
rithms should
b
e
con
s
ide
r
ed
as th
e
importa
nt ref
e
ren
c
e
wh
en
map d
e
si
gn
ers ge
nerate
s
a g
a
me
ma
p scen
e. The
desi
gne
rs in
cline
to form maps in which pathfinding i
s
done qui
ckly
, so that red
u
cing the playe
r
s’ waiting time.
Furthe
r, they can al
so in
crea
se the g
a
m
e’s in
te
re
sting deg
ree th
roug
h control
ling the map’
s
compl
e
xity and then
control the pat
hfinding difficult
y. Therefore, this p
ape
r al
so puts forwa
r
d a
kind
of map
com
p
lexity metric
call
ed
ACX.
ACX
mea
s
ures
map
compl
e
xity by analyzing
obsta
cle
dist
ri
bution, a
nd p
r
ovides refe
re
nce
fo
r
map
d
e
sig
n
du
e to t
he hi
gh
co
rrel
a
tion b
e
twee
n
ACX and the
sea
r
ch efficie
n
cy of A* algorithm.
3.2. Metric Index of Ma
p Complexity
-
A
ccumula
tio
n
of Xor
The de
sign o
f
obstacl
e distribution de
ci
des t
he pe
rfo
r
man
c
e of pa
thfinding algo
rithm in
the game ma
p scene an
d
also the inte
restin
g deg
re
e of games.
Take
n the cl
assic 2
D
ga
me
<Pacman
>
f
o
r exa
m
ple.
This
gam
e’s role
s
ch
ase
ea
ch
other
in a m
a
ze-li
k
e map
an
d t
h
e
pro
c
e
ss
of ch
ase i
s
a
c
tural
l
y pathfinding
. Intuitiv
ely, w
hen the m
ap
compl
e
xity is low, the G
h
o
s
t
can
catch
up
with Pa
cma
n
easily
and
th
e ga
me
doe
s
not have
chal
lenge.
On
th
e
co
ntra
ry, if th
e
map co
mplex
i
ty is too high, the Ghost
will har
dly grasp Pa
cma
n
and the gam
e is too difficult.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Perform
a
n
c
e
Analysis of P
a
thfinding Alg
o
rithm
s
Base
d on Map Di
stribution (Ya
n
Li)
5541
This sho
w
s the
com
p
lexity of gam
e m
ap i
s
hi
ghly
correl
ated to
the sea
r
ch ef
ficien
cy an
d t
he
player’
s
experience. In this section, we w
ill define a formal measure to descri
be the map
c
o
mplexity.
3.2.1. The De
finition of ACX
There are
se
veral facto
r
s
related to the
m
ap com
p
le
xity, such a
s
the map scale, the
numbe
r an
d the den
sity of obsta
cle
s
. Different fr
o
m
what we coul
d imagin
e
intuitively,
the
compl
e
xity does
not ne
ce
ssarily in
crea
se
whe
n
t
he
map scal
e be
come
s la
rg
er
or the n
u
mb
e
r
of
obsta
cle
s
increases. Fo
r example, it is obvious t
hat the numbe
r of obsta
cle
s
in Figure 5 is m
o
re
than that in
Figure 6, but
it is mo
re dif
f
icult to
find
paths i
n
Fig
u
r
e 6. Thi
s
i
s
becau
se that
the
map di
stributi
on of Figu
re
5 is mo
re de
nse tha
n
that
of Figure 6,
and we ca
n
observe that
th
e
obstacle
regi
ons in
Figure 5 is
convex from the m
a
thematics poi
nt
of view. We
will incorporate
this inform
ation in the defi
n
tion of the complexity metric.
First, we
con
v
ert a map to
a matrix wh
ose el
ement
s represent the states of e
v
ery cell.
Let t (i, j) denote the stat
e of cell locat
ed at the
i-th row an
d the j-th colu
mn in
the map, and it
take
s value 0
(
free
) or 1
(
ob
stacl
e
). Before defin
ing ACX, we need to
introdu
ce se
veral functio
n
s
:
)
0
)
,
(
min(
arg
min
:
)
1
(
j
i
t
F
j
i
j
;
).
0
)
,
(
max(
arg
max
:
)
2
(
j
i
t
F
j
i
j
Here, F
(
1) is
defined
a
s
th
e minim
u
m
column
no. of
the
cell
with t(i
,
j)
=0 i
n
the
i
-
th row.
Similarly, F(2
)
is used to fi
nd the m
a
xim
u
m j-va
lu
e th
roug
h the
sa
me conditio
n
as F
(
1
)
. ACX
is
defined a
s
fol
l
ows:
m
i
j
n
j
i
i
j
i
j
j
i
j
i
j
i
t
j
i
t
j
i
t
j
i
t
M
ACX
1
max
1
min
1
max
1
min
)
2
/
))
,
1
(
)
,
(
((
)
2
/
))
1
,
(
)
,
(
((
)
(
AC
X calculat
es
map complexity thr
o
ugh ac
cu
mul
a
ting the
xor-v
a
lue
of a
d
jacent cells
line by line, and the com
p
l
e
xity can be get in time O
(n
2
). The valu
e contain
s
two parts: the first
item is obtai
ned by a
c
cu
mulating A
C
X-value ro
w
by row, a
n
d
anothe
r pa
rt is obtain
e
d
by
accumul
a
ting
xor-value
col
u
mn by colu
mn. For ea
ch
row (col
umn
)
, sea
r
ching t
he
i
j
min
(
j
i
min
)
cell
and
sta
r
ting to
sum
s
up the
xor-va
lue b
e
twe
en
every two
ad
jace
nt cells u
n
til the
i
j
max
(
j
i
max
) cell. Finally
the summ
atio
n of the xor-v
alue of
ea
ch
row
and
colu
mn is the co
mplexity o
f
map. The ACX measu
r
e wi
ll take its minimum value
of zero if the free cell
s in ro
ws an
d col
u
m
n
s
are n
o
t se
pe
rated by any
obsta
cle,
whi
c
h impli
e
s
the lowes
t
map c
o
mplexity. This
is
c
o
ns
istent
with our intuition.
If the ACX-va
lue of
a
ce
rtai
n row (colu
m
n) i
s
not e
q
u
a
l to 0,
then
this
ro
w
(colu
m
n)
ha
s
at lea
s
t on
e
obsta
cle
cell. As
can
be
see
n
fro
m
th
e definitio
n, the ACX
-
valu
e of ma
p i
s
not
dire
ctly relate
d to the map scale an
d the
numbe
r of
the obsta
cle
s
, it is only relate
d to the state of
every two
adj
ace
n
t cells. T
he hi
ghe
r the
retu
rn valu
e, the hi
ghe
r th
e complexity
of the ma
p. F
o
r
example, the
com
p
lexity from Fig
u
re
5 to Fig
u
re
8 a
r
e
sho
w
n
as foll
o
w
s: A
C
X(M
5
)=0;
ACX(M6)=160; ACX(M7
)=86; ACX(M8
)=13
0.
Figure 5. Example 1
Figure 6. Example 2
Figure 7. Example 3
Figure 8. Example 4
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 7, July 201
4: 5537 – 55
45
5542
Although the
numbe
r of obsta
cle
s
in Figure 5 i
s
the
large
s
t, this map ha
s the
lowe
st
ACX co
mple
xity value and re
sulting
b
e
st pathfin
di
n
g
efficien
cy.
We
can
se
e t
hat ACX valu
e is
not only dete
r
mine
d by th
e num
ber of
obsta
cle
s
a
nd the
si
ze
of map. To
summari
ze, if
the
obsta
cle
s
g
a
ther i
n
to a bl
ock o
r
lo
cate
at the
ed
ge
of the ma
p, the ACX
co
mplexity is lo
we
r
relatively eve
n
there
are m
any ob
stacl
e
s. In contrast,
whe
n
the
o
b
stacle
s are
scattered in
a m
ap
like a ma
ze, the com
p
lexity is relatively high.
3.2.2. The Correlation o
f
Acx Me
tric a
nd Search Efficienc
y
of A* Algorithm
Although the
r
e a
r
e m
any
improve
d
ve
rsio
n of A*, the tra
d
itional
A* is
still the mo
st
widely u
s
ed
path search
algorith
m
in
many appli
c
a
t
i
ons. In the
sea
r
ch p
r
oce
ss
of A*, it checks
all the neigh
b
o
ring
node
s repeatly for th
e cu
rre
nt
nod
e to predi
ct the mo
st pro
m
ising
dire
cti
on
and
extend t
he n
e
xt nod
e by the
h
e
u
risti
c
fu
nc
tio
n
. Wh
en
ob
stacle
s a
r
e
n
ear the
edg
e
or
gathered into
a block, the
node
s in the bloc
k will
not be exten
ded any mo
re. The se
arch
efficien
cy will
be relatively high. In
contrast, wh
en th
e
most
cell
s’
states a
r
e n
o
t
con
s
i
s
tent wit
h
their
adja
c
ent
cell
s, the
alg
o
rithm
will ta
ke
more time
to che
c
k nei
ghbo
ring
no
d
e
s
and
comp
ute
their h
euri
s
tic values.
The
numbe
r of
expand
ed n
ode
s i
s
al
so in
cre
a
sin
g
. As
a result, the
se
a
r
ch
efficien
cy will
be de
cre
a
se
d. That is co
nsi
s
tent
with
the prin
cipl
e of ACX metri
c
ba
sed
on x
o
r
accumul
a
tion
. The higher
the value of ACX is, the
lowe
r the exe
c
ution effici
e
n
cy of A* will be
.
Thus, th
e p
e
rforman
c
e
of
A* can
be
aju
s
ted by
co
ntrolling the
ACX com
p
lexity in the g
a
me
map
desi
gn.
In orde
r to
prove th
e co
rrel
a
tion b
e
twee
n ACX
metric and
A* algo
rithm,
nume
r
ou
s
experim
ents have
be
en condu
cted,
a
n
d
the results
are
sh
own in
Section
4. T
he a
c
tual
sea
r
ch
efficien
cy for
pathfindin
g
is the ratio
of the
total nu
m
ber
of expan
ding n
ode
s a
nd the le
ngth
of
the sho
r
test p
a
th for the sta
r
t to goal nod
e, as sh
own in formula 2.
PathLength
d
NodeSerche
othrim
A
E
)
lg
(
(
2
)
4. Experiments and
Res
u
lts
In orde
r to testify the impacts of the ma
p
distrib
u
tion informatio
n on the perform
ance of
pathfindin
g
al
gorithm, two
grou
ps
of exp
e
rime
nts hav
e been
con
d
u
c
ted.
4.1. Compari
s
ons of CDHPA*
w
i
th HPA* and M-A* algorithm.
In this gro
u
p
of experime
n
ts, the average pe
rforma
nce of a
bove
three alg
o
rit
h
ms i
s
comp
ared
ba
sed
on
the
same
se
arch t
a
sks to ve
rify
the effective
ness of con
s
i
derin
g
th
e
m
ap
distrib
u
tion i
n
formation
du
ring the
proce
s
s of
pa
th
find
in
g
.
10
maps
ar
e
s
e
le
c
t
ed
fr
o
m
Baldurs
Gate II
, among whi
c
h M
a
p1-M
ap5 a
r
e
64*64 in
si
ze
and the othe
r 5 map
s
a
r
e
128*1
28. At the
same tim
e
, 1
0
tasks
of pat
hfinding
are
randomly
g
e
n
e
rated to
ca
rry out the CDHPA*, HPA a
n
d
M-A* in ea
ch
map re
sp
ecti
vely,and different algo
rithm
s
have same
tasks in the same map.
Notice that t
he
sea
r
ching
time of M
-
A* start
s
co
mputing
after the ab
stract
map i
s
compl
e
tely fo
rmed. F
o
r th
e sake
of e
a
s
y compa
r
iso
n
, we
divide
d the
whol
e
runni
ng time
of
CHDPA* and
HPA* into three part
s
: pre
p
ro
ce
ssi
ng
time, the time
of insert the start and goal
and
on-lin
e pathfi
nding time. The followin
g
symbol
s are
use
d
to express all metrics of performa
n
ce
of pathfindin
g
re
sp
ectivel
y
.
t/
ms
is th
e total time
of se
archin
g
abstract
path
and
refinin
g
the
abstract
path.
Len
is the l
e
ngth of full
p
a
th bet
wee
n
start
node
an
d go
al n
ode.
Vec
is
the tot
a
l
numbe
r of no
des that a
r
e
expand
ed
in the process of
pathfinding.
The final com
pari
s
on
re
sult
s
are
sho
w
n
in
Table 1.
Note
that the data
are
th
e average valu
e of ten pathfin
din
g
tasks
and t
h
e
threshold
is
obtaine
d exp
e
rime
ntally. We
co
mpa
r
e
these
three
a
l
gorithm
s f
r
o
m
the foll
owi
ng
three a
s
pe
cts:
a)
On-line
se
arching
time
.
Table
1
sho
w
that
the
on
-line
searchi
n
g time
of
CDHPA* i
s
less than M
-
A* and
HPA*. The re
aso
n
is that
CDHPA* co
nsi
d
ers th
e ob
st
acle
s di
strib
u
t
ion
informatio
n in the proce
s
s of division an
d perfo
rms B
r
esenh
am straightline alg
o
r
ithm in the free
area
s a
s
mu
ch as po
ssible,
which is fast
er
than HPA*
and M-A* u
s
i
ng A* in refini
ng path.
b)
T
h
e num
ber
o
f
expa
nded node
s.
The
nu
mbe
r
of exp
ande
d
nod
es of
CDHPA*
is
less than
that
of M-A* b
u
t
more th
an
HPA*. CD
HPA* expan
ds
all
free n
ode
s o
n
the b
oun
da
ries
of all sub-reg
i
ons a
s
M-A*
does, whi
c
h
gurante
e
s th
e optimal pat
h will be fou
nd. HPA* uses
uniform p
a
rtition strate
gy and only ch
o
o
se
s a
few
key nod
es o
n
the regio
n
bound
ra
ries as
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Perform
a
n
c
e
Analysis of P
a
thfinding Alg
o
rithm
s
Base
d on Map Di
stribution (Ya
n
Li)
5543
abstract
nod
es to fo
rm th
e ab
stra
ct m
ap, so
it exp
and
s le
ss no
des.
Ho
weve
r, HPA*
can
not
gura
n
tee to find the optima
l
path for that rea
s
on.
c) Pr
eproc
e
ssing
time.
In additio
n
t
o
the
onli
ne-pathfindin
g
ti
me,
each
al
gorithm
inclu
d
e
s
prep
rocessin
g time and time for inse
rting no
des. M-A* ca
n perfom in
serting op
erati
on
only whe
n
th
e positio
n inf
o
rmatio
n of start and
go
al
nods
are
co
nfirmed. Ever when th
e task
changes, M
-
A* needs to
re-divide the map,
whi
c
h leads
to
a l
onger
waiting time. CDHPA
*
divides th
e
map
without
the lo
cation i
n
formatio
n of
start
and
go
al nod
es,
wh
ich
red
u
ces the
us
ers
’
waiting time for multiple tasks
. HP
A* does
not consi
der any
i
n
formaito
n
of distrib
u
tion
a
n
d
start/go
a
l lo
cations an
d al
ways eq
ually
divide
s a
ga
me ma
p, an
d the
r
efore it
s p
r
e
p
ro
ce
ssi
ng
time is
less
than CDHPA*.
d) The pa
th
optimalit
y
.
The path o
p
timality is an importa
nt index of measurin
g
algorith
m
performan
ce[1
5]. Since CDHPA* select
s all bound
ary
free cell
s a
s
nod
es in the
abstract ma
p
and use
s
A*
or Bre
s
en
ha
m to find
the
shorte
st pat
h according to the value of
.
That gua
rant
ees the fou
n
d
path is optim
al.
To con
c
lu
de,
without affecting the path optim
ality, CDHPA* imp
r
o
v
es the spe
e
d
of on
-
line pathfindi
ng and redu
ces the sto
r
a
g
e
co
st of M-A* by con
s
ide
r
ing the map
distrib
u
tion. It is
more
suitabl
e for pathfin
ding task th
at has hig
h
e
r
dema
nd fo
r path qualit
y and real
-time
respon
se.
Table 1. Co
m
pari
s
on
Re
sul
t
s of Different
Algorithms
MAP
β
Performance
CDHPA*
M-A*
HPA*
Map1
0.1
t/ms 0.63256
0.65958
2.96582
len 71.1
71.1
71.5
Vec 282.4
391.6
192.7
Map2
0.2
t/ms 0.58666
0.65810
2.48668
len 60.5
60.5
61.5
Vec 238.1
343.6
167.2
Map3
0.3
t/ms 0.78825
1.48901
2.80040
len 72.7
72.7
73.5
Vec 297.3
398.9
183
Map4
0.1
t/ms 0.81666
0.8691
2.70956
len 73.3
73.3
73.7
Vec 332.5
428.5
186.8
Map5
0.2
t/ms 0.46617
0.72967
2.63379
len 64.6
64.6
66.4
Vec 252.8
358.2
181.2
Map6
0.1
t/ms 3.30625
2.72534
5.44052
len 121.7
121.7
123.3
Vec 682.6
737.4
338.5
Map7
0.15
t/ms 2.59991
3.16892
5.56705
len 138.2
138.2
138.4
Vec 709.1
872
357.9
Map8
0.15
t/ms 1.6171
2.06603
4.26967
len 101.4
101.4
103
Vec 548.7
653.3
280.4
Map9
0.12
t/ms 2.74448
3.68443
4.84008
len 109.9
109.9
110.9
Vec 595.9
706.6
317.3
Map10
0.12
t/ms 3.55374
5.69287
5.63222
len 132.7
132.7
133.9
Vec 689.6
864.2
353.6
Average
t/ms 1.71118
2.17431
3.93458
len 94.61
94.61
95.61
Vec 462.9
575.43
255.86
4.2. Correla
tion of Ac
x M
e
tric
w
i
th
th
e Search Efficienc
y
of A* Algorithm
This g
r
ou
p of experime
n
t
s is cond
ucted
to validate the relatio
n
shi
p
betwe
en map
compl
e
xity and the sea
r
ch efficiency o
f
A*. 600 maps (5
0*50
size) are g
ene
rated by rand
om
map gen
erat
or and ACX
metric i
s
ca
rri
ed out on ea
ch map to ca
lculate the m
ap’s
compl
e
xity.
1500
pai
rs
of (sta
rt, goal
)
node
s a
r
e
g
enerated
ran
domly to find
path
s
in
ea
ch map
an
d the
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 7, July 201
4: 5537 – 55
45
5544
averag
e effici
ency of the 1
500
sea
r
che
s
is compute
d
. To ma
ke the
results b
e
m
o
re o
b
viou
s, we
only use th
ose pair of n
o
d
e
s
with its pa
th length
larg
er than
50 un
its. Figure 9
and 10
sh
ow
the
results, whe
r
e Figu
re 9 i
s
the cu
rve fig
u
re of
A
C
X complexity, and Figu
re 10 i
s
the effici
en
cy
curve
of A*. In Figu
re 9, th
e map
s
a
r
e n
u
mbe
r
ed fro
m
low to hi
gh
based on th
e value of A
C
X.
The x-axis i
s
the map num
ber an
d y-axi
s
is the
corre
s
po
ndin
g value of com
p
le
xity. In Figure
10,
the y-axis re
p
r
esents the
search efficie
n
c
y of A* in each map
co
rre
spo
n
din
g
to that in Figure 9.
From th
e two
figure
s
,
we
can
see th
at the tre
nd
of ACX curve i
s
consi
s
tent
with
that of
sea
r
ch
effici
e
n
cy curve
of A*
algo
rithm except of
some
small jitters in local
areas. T
hat may
be
cau
s
e
d
by th
e method
s of
maps’
gen
era
t
ion, the exist
e
nce of pa
rt
icularly lo
w efficien
cy path
a
n
d
no-p
a
th n
ode
s p
a
irs
and
so on. [1
0] me
ntioned
when
the m
ap’
s
co
mplexity based o
n
Hammi
n
g
distan
ce
met
r
ic is mo
re t
han
100, th
e
jitter of
th
e sea
r
ch efficie
n
cy cu
rve
i
s
more
o
b
vio
u
s.
Ho
wever, thi
s
doe
s
not o
c
cur in th
e m
e
thod of
A
C
X metric. he co
nsi
s
ten
c
y
of ACX
metri
c
a
n
d
the se
arch
efficien
cy do
es
not
disapp
ear with the in
crease of ma
p’
s compl
e
xity.
Therefore, A
C
X
can
be
u
s
e
d
to mea
s
u
r
e
the m
ap
co
m
p
lexity in d
e
signing
map
s
whi
c
h
uses
A
*
or
its
impro
v
ed
versio
ns to find sh
orte
st paths.
From th
e a
b
o
v
e two g
r
o
u
p
s
of exp
e
rim
e
nts,
we can
see that the
di
stributio
n info
rmation
in a map is highly relev
ant with the
perform
an
ce of search
algorith
m
s. By analyzing their
relation
shi
p
, we can de
si
gn low-cost
and efficie
n
t algorithm
with refere
nce to the
map
distrib
u
tion.
On the othe
r hand, the m
ap co
mple
xit
y
measu
r
e
can help i
n
m
a
p de
sign
which
coul
d determi
ne different o
b
sta
c
le di
strib
u
tions
, produ
cing different sea
r
ch difficul
t
ies.
Figure 9. Co
mplexity
Figure
10. A* Search Efficiency
5. Conclusio
n
In this pa
pe
r, the rel
a
tio
n
shi
p
bet
we
en
map
dist
ribution
and
the perf
orm
ance of
sea
r
ching
alg
o
rithm
s
is
discu
s
sed. A ne
w hie
r
a
r
chica
l
pathfindin
g
algorith
m
call
ed CDHPA* i
s
develop
ed to
red
u
ce
the
time and
st
orag
e cost
b
y
inco
rpo
r
ati
n
g the o
b
sta
c
le di
strib
u
tio
n
.
Beside
s, a m
ap complexit
y
metric b
a
se
d on the
accumulation
of xor is p
r
o
p
o
s
ed, whi
c
h
ca
n be
use
d
to describe ho
w ea
sy or difficult to sea
r
ch a path in a given map. This i
s
very helpful
fo
r
game ma
p d
e
sig
ners. The
y
could tun
e
the pathfi
ndi
n
g
efficien
cy (or the pathfin
ding difficulty
on
the co
ntra
ry) i
n
a map
by g
enerat
ing m
a
ps
with different com
p
lexities. Ove
r
all, the two
pro
p
o
s
ed
method
s de
monst
r
ate th
e effects of
obsta
cle
s
d
i
stributio
n on
the perform
ance of sea
r
ch
algorith
m
fro
m
two angle
s
– the desig
n
for pathfindi
n
g
algorith
ms i
n
a parti
cula
r distributio
n a
n
d
the desig
n for map
s
base
d
on compl
e
xity metric
. In future work, we will stu
d
y the methods
determi
ning threshold
intelligently an
d analyze th
e co
rrelation
of ACX an
d the se
arch
efficien
cy of other pathfindi
ng algo
rithm
s
.
Referen
ces
[1]
Rabi
n S. AI Ga
me Programmi
ng W
i
sdom. Be
ijin
g: T
s
inghua
Univers
i
t
y
Pr
es
s. 2005.
[2]
Luli
n
Ch
en, G
o
ufeng Q
i
n. K N
earest Ne
igh
b
o
r
Path Q
ueries
Based o
n
Ro
a
d
Net
w
orks.
TELKOMNIKA
Indon
esi
an Jou
r
nal of Electric
al Eng
i
ne
eri
ng.
2013; Vol.
11(1
1
):663
7-6
644,
[3]
Dijkstra E. A
N
o
te o
n
T
w
o
Pr
obl
ems i
n
C
o
n
n
e
x
i
o
in
w
i
th
G
r
aphs.
Nu
mer
i
s
c
he M
a
the
m
ati
k
.
195
9; 1(1)
:
269-
271.
[4]
Botea A, Muller M, Schaeffer J. N
ear-optim
al
Hierarc
h
ica
l
P
a
thfind
in
g.
Jou
r
nal of G
a
me
Devel
o
p
m
ent
.
200
4; 1(1): 7-2
8
.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Perform
a
n
c
e
Analysis of P
a
thfinding Alg
o
rithm
s
Base
d on Map Di
stribution (Ya
n
Li)
5545
[5]
Yibi
ao L
u
, Xi
a
o
min
g
Huo, P
T
s
iotras.
Bea
m
l
e
t-like D
a
ta
Processi
ng for
Accelerate
d
Path-pl
a
n
n
in
g
usin
g Mu
ltiscal
e
Infor
m
ati
on
of the E
n
viro
n
m
e
n
t.
Proce
e
d
i
ng
of 4
9
th IE
EE Conf
erenc
e o
n
Dec
i
si
o
n
Contro
l. Atlanta, GA. 2010; 3808-
381
3.
[6]
Han
an S
a
met.
T
he Quadtre
e
an
d R
e
l
a
ted
Hierarc
heric
al
Data Structur
e
s
.
ACM Computing Surveys.
198
4; 16(2): 18
7-26
0.
[7]
Mo
w
s
h
o
w
i
tz A
.
Entrop
y
and
the Compl
e
xit
y
of Graphs.
An Index of th
e Rel
a
tive C
o
mp
lexity of a
Graph Bul
l
etin
of Mathe
m
atic
al Bio
physics.
1
968;
30(
1): 175
-204.
[8]
MacEachr
en A
.
Map Compl
e
xit
y
.
T
he Americ
an Carto
g
ra
ph
er.
1982; 9(
1): 31-4
6
.
[9]
David F
.
Meas
urin
g Map Co
mple
xit
y
.
Carto
g
rap
h
ic Jour
na
l.
2006; 4
3
(3): 224-
238.
[10] Pan Su, Y
an
L
i
, W
enli
ang
Li.
A Game Map
Co
mpl
e
xity Me
asure B
a
se
d o
n
Ha
mmi
ng
Di
stance.
Proc.
of the 3rd Inter
natio
nal
Confe
r
ence
o
n
Com
putatio
na
l Intell
ige
n
ce a
nd Ind
u
strial Ap
plic
ati
on. W
uha
n
.
201
0; 38(7): 33
2-33
5.
[11]
Yan
Li, T
i
eson
g Li,
Cai
C
hen
. Map C
o
mpl
e
xit
y
M
easur
em
ent
Bas
ed on
Relativ
e
Ham
m
ing Dista
nce.
Co
mp
uter Engi
neer
ing.
2
012; 38(7):
10-
12.
[12]
Cha
o
Yu
an.
R
e
serac
h
of
the
Brese
n
h
a
m S
t
raight
Lin
e
G
ener
ation
Al
go
rithm.
Jour
nal
of
Sich
ua
n
univ
e
rsity of scienc
e & eng
ine
e
rin
g
.
200
6; 19
(2): 36-40.
[13]
Ying
lia
ng
Jia,
Hua
n
chu
n
Z
h
ang, Y
a
zh
i Ji
ng. A
Mod
i
fie
d
Bres
en
ham
Algorit
hm of
L
i
ne
Dra
w
i
n
g
.
Journ
a
l of Iamge an
d Graph
i
cs.
2008; 13(
1)
: 158-16
1.
[14]
Natha
n
Sturtev
ant'
s
Moving AI
Lab. Pathfin
d
i
ng Benc
hmark
s
,
http://
w
w
w
.
movin
gai.com/
benc
hmarks/
.
[15]
Yong
hu
a
Xu,
F
e
i Sha
o
. An Optimal
Routi
ng
Strat
e
g
y
Bas
ed
o
n
Spec
if
ying
Shortest Path
.
T
E
LKOMNIKA Indon
esi
an Jou
r
nal of Electric
al Eng
i
ne
eri
ng.
2013; 1
1
(10):
622
4-62
31.
Evaluation Warning : The document was created with Spire.PDF for Python.