# Fractal Analysis of Stealthy Pathfinding Aesthetics

Authors: Ron Coleman
Journal: International Journal of Computer Games Technology
 (2009)

---

## Abstract

This paper uses a fractal model to analyze aesthetic values of a new class of obstacle-prone or “stealthy” pathfinding which seeks to avoid detection, exposure, openness, and so forth in videogames. This study is important since in general the artificial intelligence literature has given relatively little attention to aesthetic outcomes in pathfinding. The data we report, according to the fractal model, suggests that stealthy paths are statistically significantly unique in relative aesthetic value when compared to control paths. We show furthermore that paths generated with different stealth regimes are also statistically significantly unique. These conclusions are supported by statistical analysis of model results on experimental trials involving pathfinding in randomly generated, multiroom virtual worlds.


---

## Body

## 1. Introduction

Nonplayer character (NPC) agents in
videogames depend on pathfinding to navigate virtual worlds autonomously. The
literature on artificially intelligent pathfinding has generally focused on
machine efficiency and shortest paths. While these concerns cannot be
neglected, they may be of secondary or even doubtful benefit if, in videogames,
they lead to movement lacking in sensori-emotional or aesthetic qualities that
would otherwise appeal to player expectations of plausibility, intelligence, beauty,
and so forth. Indeed, pathfinding without aesthetic considerations tends to look
unrealistic and mechanical, detracting from a game’s immersive potential and
frustrating players [7].Aesthetics,
however, pose challenges. According to a modernist, Kantian view [10],
aesthetics in  general and notions of beauty and matters of taste in particular
are thought to be subjective,
relative, and  presumably beyond the pale of automation. Yet, game researchers and developers have
side-stepped these dilemmas, asking not what is beauty in pathfinding but rather what is
knowable about such beauty which can be captured by heuristics called
“aesthetic optimizations” [17] and “aesthetic corrections” [7].These efforts
have yielded encouraging results and drawn attention to basic issues of
incorporating aesthetics in pathfinding. Unfortunately, they have depended almost
entirely on anecdotal arguments rather than metrics that facilitate hypothesizing
about and testing aesthetic outcomes under more quantifiable, independently verifiable
regimes. These investigators have furthermore addressed only beautifying heuristics
that navigate by straight lines, smooth turns, and avoiding obstacles without
tracking them. Such movement, although appealing in some contexts, is not appropriate for all
forms of play and types of games.In this paper, we
use fractal analysis to examine a new pathfinding aesthetic which we call
“stealthy.” These paths, obstacle-prone by nature, are reminiscent of and
suitable for covert movement in first-person shooter, role playing, and other
types of games wherein the goal is to avoid detection, exposure, all-out
encounters—concepts we
define mathematically later. We use fractal analysis since, among other reasons
we discuss later, this approach has been shown to reliably predict and comport
with player expectations of aesthetic appeal in pathfinding [4]. What is interesting
is that stealthy pathfinding has a statistically significantly unique fractal
signature compared to controls which have not been treated with stealth
regimes.We develop a
simple cost heuristic to generatestealth
effects, that is, stealthy movement patterns. In a series of N=100 experimental
trials involving randomly generated, multiroom virtual worlds, we show that the
fractal model reliably discriminates between stealthy paths versus two  types of
control paths with p≈10−9 and
p≈10−13,
depending, respectively, on the stealth effect. We show furthermore that paths
with different stealth effects are unique compared to one another with p≈10−3. These
results confirm previous studies of fractals as a reliable metric for measuring
pathfinding aesthetic outcomes.


## 2. Background and Related Work

The fractal dimension, originally
developed by Mandelbrot in his seminal paper [11] as we describe below, has
been used by others to assess aesthetic values in artistic masterpieces like Jackson
Pollack’s “action paintings” [8, 18] and Bach’s
Brandenburg Concertos [20]. Investigators working in these areas
were not specifically interested in pathfinding or even for that matter,
artificial intelligence.The artificial
intelligence literature, however, is generally silent on pathfinding aesthetics.
For example, see texts like
those of Bourg and  Seemann [2], Millington
[13],
and Russell and  Norvig [19] that cover various forms of automated movement but do not
discuss aesthetics.Rabin [17],
Higgins [7], and
Stout [22] have noted the need for aesthetic considerations in
pathfinding and proposed arguments and heuristics to improve aesthetic outcomes
in ways likely to appeal to player expectations of “realism,” “beauty,” and so
forth. For Botea et al. [1], the main interest is machine performance. However,
they acknowledge, if only in passing, that navigation in games is incomplete
without aesthetic concerns. These efforts, in any case, have all focused on
how to achieve aesthetic outcomes but not
grading, scoring, or in any way, measuring them.For precisely
this reason, Coleman [3] put forth the beauty intensity, ℜ, as a relative,
nonlinear measure of aesthetic appeal in pathfinding. Thus, a path object, P1,
is said to have more “working beauty” than a control or reference path object,
P0, provided that  ℜ(P1|P0)>0.
While ℜ was shown to give commonsense results in
accordance with straight lines, smooth turns, and avoiding obstacles without
tracking them, values of ℜ are not readily intuitive except in a strictly
lattice sense. ℜ is furthermore mathematically undefined for
some path objects. The implication is that ℜ is parametric; it uses explicit, internal
assumptions about pathfinding and aesthetics.Coleman [4] subsequently
proposed a fractal model, G, which is similar to and mildly correlated with ℜ as a relative, nonlinear measure, that is, G(P1|P0)>0 implies that P1 has more “fractal beauty” than a reference path
object, P0.
However, G is a more reliable and intuitive estimator
according, respectively, to its variance-to-mean ratio and relationship to
textured sensory data. Most importantly for the present study, G is nonparametric.
It makes no assumptions about pathfinding or even aesthetics. Thus, G tends to
provide more reliable, conservative results.In this paper, we
useG to study a new pathfinding regime, the stealth effect, in relation to
controls. We examine paths treated with stealth regimes versus “standard” paths,
that is, with no beautifying treatments and “aesthetic” paths, that is, with
beautifying treatments. While Coleman [4] was completely analytical, the present
effort is both analytical and generative.


## 3. Fractal Dimension

Mandelbrot developed the fractional
(or fractal) dimension as a way to analyze irregularly shaped geometric objects
which are no-where differentiable (i.e., textured) and self-similar [11, 12, 14].
Mandelbrot observed furthermore that the fractal dimension, D, of a surface, S,
is greater than its topological dimension, n [11, 12], that is, n<D<n+1.
Mandelbrot suggested that fractals offered a better description of objects
found in nature (e.g., coastlines).The fractal
dimension has different interpretations that come under two general mathematical
categories: stochastic and geometric [21]. The stochastic interpretation
assumes Brownian fluctuations [20] and might be employed, for instance, in time
series analysis. In this paper, we use a geometric interpretation based on the
Hausdorff dimension [20]: (1)D(S)=limε→0logNε(S)logε,S is a surface, εis a
yardstick or ruler, and Nε(S) is the number of self-similar objects or
subcomponents covered by the ruler. For fractal objects, log Nε(S) will be greater than log(1/ε) by a fractional amount.One way of interpreting
the Hausdorff dimension is through the box counting dimension, that is,
reticular cell counting. In this case, if the ruler is a uniform grid of square
cells, then a smooth surface passes through twice as many cells if the cell
length is reduced by a factor of two. A fractal object passes through more than
twice as many cells if the cell length is reduced by a factor of two.For instance, the
coastline of Maine, USA
, is not straight or smooth but
highly textured with inlets, outcrops, and keys. Researchers using the box
counting dimension have estimated its fractal dimension to be between 1.11 and
1.37 depending on where and how measurements are taken [23].Reticular cell
counting is intuitive and straightforward computationally. We use it to estimate
the fractal dimension by computing the regression slope oflog(1/ε) versus log Nε(S).
We use a slightly modified version of FracTop [9], which reliably computes the
fractal dimension using reticular cell counting, where ε={2,3,4,6,8,12,16,32,64,128} in pixels are the default rulers. The input to
FracTop is a 2D image in Portable Network Graphics (PNG) [16] format which we
explain later how to generate given a virtual world.


## 4. Fractal Model:G

The fractal model we describe is from Coleman [4]. We review it here for
the sake of completeness.Let the surface,S,
consist  of W,{Bj}, and P. W  is a finite state-space in
Euclidean Rn. We assume n=2 or n=3. For analysis purposes, however, the perspective
is two dimensional. For example, if the game is a first person shooter, the
veiw is from above, looking down on walls, rooms, and hallways. Yet, the NPC
perceives the world as a set of rigid-body
obstacles, {Bj},
in two or three dimensions. See Figure 1 as an example.Figure 1
Example of virtual world,W, in
2D perspective with start and goal configurations.LetW:x,y→t for 0≤x<w,0≤y<h,
where w and h are width and length features, respectively, of W, and t is a
state, namely, t∈{0,1,2}.
W contains the set {Bj},
namely, Bj=W:Bj⋅x,Bj⋅y→2.W also contains A, a “free flying” rigid-body (i.e., the NPC), which has configurations
or steps such that Ai=W:Ai⋅x,Ai⋅y.
These steps define a path object, P, for i=0⋯L from Astart(start=0) to Agoal(goal=L), where Ai+1=W:Ai⋅x+Δx,Ai⋅y+Δy→1 and Δx,Δy∈{−1,0,1}.
All other states of W are “open” or unoccupied, namely, W:x,y→0.
For the worlds we generate, A “tracks” an obstacle if W:Ai⋅x±k,Ai⋅y±k→2,
where k=1.LetD(P) be shorthand
notation for the fractal dimension of P
for a particular world, W, which includes the open states of W,P, and {Bj}. Let G be the “fractal beauty” of a path, P1,
in relation to a reference path, P0,
as (2)G(P1|P0)=D(P1)−D(P0).G is constrained
in that W,Astart, and Agoal are
assumed to be the same for both P1 and P0. Thus, we say P1 has more “fractal beauty” than P0 only if(3)G(P1|P0)>0.P1 is said to have less fractal beauty than P0 if G<0.
If G=0,
then P1 and P0 are said to have the same fractal beauty.


## 5. Stealthy Pathfinding

G does not specify how to find a
path. That is the role of pathfinding. In principle, therefore, any suitable pathfinding
algorithm suffices. We start with the A* algorithm [2] as a base. Aside from being
generally regarded as the “work horse” of pathfinding for games, A* is
simple, flexible, and straightforward with well-known space and time
characteristics [19]. The “standard” A*,
for instance, the one given by Bourg and  Seemann [2], does not have an aesthetic
objective.Others have
sought to reduce or correct these aesthetic deficiencies through beautifying
heuristics [1, 7, 17, 22], that is, if the path score subject to minimization is (4)f(Astart,Agoal)=g(Astart)+h(Agoal),
where g is the known cost from the
start configuration and h is the heuristic estimate to the goal configuration. (For
h, we use Manhattan
metric, namely, h(Agoal)=|ΔX|+|ΔY| (see [9]) for further information.) By
adding a penalty or surcharge to h for turns or zigzags, A* tends to generate paths with straight lines
and smooth  turns. Coleman [3] goes further and also penalizes wall tracking
within some radius, k, that is, an NPC navigating a game world by following a
wall or  obstacle may appear to be using the
object and not A.I. Thus, it is best to avoid such objects.Yet in a
competitive game world setting, the NPC would not necessarily traverse the
middle of a hallway in a straight line or make “pleasant,” predictably smooth
turns. Indeed, wall tracking is precisely what an NPC might conceivably do if
it is seeking to avoid detection, dodge an opponent, or evade a trap.Whereas the
standardA* is wall-neutral and “aesthetic” A* is wall-adverse, we define a “stealthy” A* as one which is obstacle-prone, that is,
rather than ignoring obstacles or penalize the NPC for tracking them, the
stealthy A* rewards such paths according to the following schedule
if W:Ai⋅x±k,Ai⋅y±k→2,
where k=1:(5)H(Agoal,γ)=(1−γ)⋅h(Agoal),where γis
called stealth effect and (1−γ) is the discount.
(Note the discount may in fact behave like a surcharge for some values of γ.) Equation
(5) supersedes the heuristic component of the A* algorithm. The nonheuristic component does not
change.We state the following lemmas.Lemma 1.
Cor(h,γ)=0,
that is, there is no correlation between the stealth effect, γ,
and the heuristic cost, h.Proof.
By
inspection of (5), there is no dependency between the discount and h.Lemma 2.
Three
possible values ofγgive distinct characteristics per the
relations below:
γ=0 standard or obstacle-neutral
search,γ<0 aesthetic or obstacle-adverse
search,γ>0 stealthy or obstacle-prone
search.Proof.
Ifγ=0,
(5) degenerates to the standard search. If γ<0,
the discount becomes a surcharge for tracking an obstacle. If γ>0,
the heuristic cost is discounted.Lemma 3.
At the
limit, there is no stealth effect andH converges to h, that is, (6)H(γ)limγ→0=H(γ=0)=h.Proof.
See Lemma2.


## 6. Experimental Design

Under experimental conditions,G
may be regarded as “black box,” that is, we input two objects, P0 and P1,
and we get a result, a statistic called G subject to constraints we mentioned
above. The experiment, thus, does not ask whether internally the regression
lines for P0 and P1 are statistically different (they may or may
not be), what kind of regression we are using, how we measure the fractal
dimension, and so forth. The G is deliberately and completely blind to these questions.
The only concern for experimental purposes is whether there are systematic deviations
from expectation, that is, our null hypothesis, which cannot be explained by
chance. We use two controls for this purpose.Lemma1 suggests we can generate the stealthy
paths without modifying the A* cost heuristic directly. Indeed, per Lemma 2 we
use the standard A* from Bourg and Seemann [2] as one of our experimental
controls, in this case, pathfinding without beautifying treatment. The other
experimental control, the aesthetic A*, is from Coleman [3].Lemma3 states
that paths are distinguishable only for sufficiently large, nonzero γ. However,
Lemma 3 does not suggest how to
choose γ.
Thus, we selected γ=10% for one run and γ=15% for another run as these seemed to us a reasonable
basis for experimental and illustration purposes. Note that a “run” is a series
of “trials” which we explain below.These pathfinding algorithms, standard, aesthetic,
and stealthy, are embedded, respectively, in multiroom virtual worlds,W,
generated by the Wells [24] random level generator. The Wells level generator takes
as input a “level” which defines the width and height of the world. It also
takes as input a seed which randomizes the configuration of the world in terms
of rooms and interconnecting hallways as {Bj}.
The Wells level generator also creates Astart and Agoal,
respectively, in the first and last rooms. We use the three types of
pathfinding (i.e., aesthetic, standard, and stealthy) to find a path from Astart to Agoal in each world. Finally, for each world
we compute G(P1|P0), where P1 is a stealthy path and P0 a
reference or control path, either
aesthetic or standard.To computeG, we convert the virtual world to a PNG
[16] image. We generate level “10” worlds which are 50×50 tiles. Each tile is 10×10 pixels and each Ai and Bj occupies a single tile. Ai are
ovals 10 pixels in diameter and Bj are squares 10 pixels in length. This is the input
to FracTop which calculates the fractal dimension, D(P), using reticular cell
counting. Finally, we then compute G according to (2).Each random multiroom virtual world,Wm,
is an independent Bernoulli trial. A trial is successful provided that G(P1stealthy|P0aesthetic)<0⋀G(Pstealthy|P0standard)>0. The trial is a failure otherwise. If s is the number of successes in N
trials and f is the number of failures where N=s+f,
then the null hypothesis is H0:s≤f.
To conservatively estimate the P-value, we use the one-tailed Binomial test,
a nonparametric test [6] for N=100 trials in two runs, one for γ=10% and one for γ=15%.We also analyze stealthy paths compared to each
other, namely, less stealthy(γ=10%) versus more stealthy (γ=15%) pathfinding. In this case, a trial is successful if G(P1stealthy15%|P0stealthy10%)≠0 and a failure if G(P1stealthy15%|P0aesthetic10%)=0. Again, we have H0:s≤f.


## 7. an Example

To make these ideas clearer, we go through a randomly selected trial, number
18. Namely, the Wells random seed is 18. Readers can view the results of all 100
trials of 400 images online at the author’s website [5].
Figure 2 shows the
multiroom, virtual world and aesthetic pathfinding for this trial from Astart to Agoal. The • symbols represent “bread crumbs” which
constitute the path in the time domain.Figure 2
Aesthetic pathfinding
with beautifying treatment for trial 18.Figure3 shows the same random virtual world with stealthy (γ=15%) pathfinding.Figure 3
Stealthy pathfinding for
trial 18 andγ=15%.Figure4 shows
the stealthy path for γ=10%.
Notice that the difference between 10% and 15% is the little “jog” in the upper-left
quadrant. We discuss this further in the
conclusion section.Figure 4
Stealthy pathfinding for
trial 18 andγ=10%.In general, one
can easily see the difference between stealthy paths and the control paths. The
standard path swerves from wall to wall seeming almost to wander. In a sense,
the standard path is making random choices since the wall does not affect the cost
heuristic. Yet in the stealthy case, the wall is sought out where possible.
This movement gives a visual impression of avoiding opening spaces, that is,
middle of the room or hallway. In other words, the aesthetic path is less
covert compared to the standard one. The stealthy ones, however, appear more
covert than both aesthetic and standard paths.Table1 gives a
quantitative assessment, namely, the fractal dimension, D(P),
for each path, P,
according to the four objectives shown in Figures 2–5.Table 1
Fractal dimensions,D(P), for each path, P, of trial
18.
FigurePD(P)2Aesthetic1.5576383Stealthy (15%)1.5507864Stealthy (10%)1.5496075Standard1.547505Figure 5
Standard pathfinding (i.e.,
with no beautifying treatment) for trial 18.Table2 gives G(P1|P0) as the intersection of rows and columns
starting in the control or “D(P0)” column gives G for this trial.Table 2
G(P1|P0).
P0P1AestheticStealthy 15%Stealthy 10%StandardAesthetic0Stealthy
15%0.0068520Stealthy
10%0.0080310.0011790Standard0.0101320.0032810.0021010We
organized Table2 for readability; namely, the lower triangle is a positive
transpose of the upper triangle (not shown). The zeros along the diagonal
represent G(P1|P0)=0,
where P1=P0. For instance, the aesthetic path compared to the stealthy path as the
reference, G(P1aesthetic|P0stealth15%)=1.557638−1.550786=0.006852.From a purely
quantitative perspective, Table2 shows the objectives in order of decreasing
fractal beauty and one can readily see that the null hypothesis, H0,
is not supported by this single trial. Both stealthy paths’ fractal dimensions
are numerically between the aesthetic path and the standard path.In other words,
the numerical relationships are somewhat different from visual impressions. We
do not attempt to explain this phenomenon here. We only note that the movement
patterns are visually distinct and consistent, and as we observe below,
statistically significant from the model’s perspective.


## 8. Results

The raw data consists of 400
results: 100 standard paths, 100 aesthetic paths, 100 paths forγ=10%, and 100 paths for γ=15%. The full data sets may be found online at the
author’s website [5]. Figure 6 gives the histogram distribution of G(P1stealthy|P0standard) and G(P1aesthetic|P0stealthy) for the γ=15%. run. The proportions of mean G are 0.001675±0.001661 and 0.007203±0.002285,
respectively. (The notation “±” is the standard deviation.)Figure 6
G(P1stealthy|P0standard) and G(P1aesthetic|P0stealthy) for γ=15%.Figure7 gives
the statistical histogram distribution of G(P1stealthy|P0standard) and G(P1aesthetic|P0stealthy) for the γ=10% run. The proportions of mean G are 0.001275±0.001503 and 0.007603±0.002257,
respectively.Figure 7
G(P1stealthy|P0standard) and G(P1aesthetic|P0stealthy) for γ=10%.These two charts
are generally similar. They both show that stealthy paths tend to have more
fractal beauty than standard ones, while aesthetic paths have more fractal
beauty than stealthy ones. The distribution is somewhat more dispersed forγ=15% compared to γ=10% when the standard path is the control. Yet,
this is precisely what Lemma 3 predicts.Table3 gives the results
in terms of the number of successes (s) and failures (f) and the P-value
based on the one-tailed binomial test.Table 3
Number of successes and
failures andP-value.
γTrialssfP15%10084162.391E−1310%10078222.169E−09Thus, we can
reject the null hypothesis and accept its logical alternative. Namely, stealthy
paths are unique  in terms of
their  aesthetic value.Table4 addresses the question of how less stealth (γ=10%) versus more stealth (γ=15%) affects pathfinding. The P-value is
based on the one-tailed binomial test.Table 4
Number of successes and
failures andP-value.
γsfP15% versus 10%64361.759E−03The data in Table4 suggests
that stealth effects γ=15% versus γ=10% are unique among themselves. In other words,
there is a measurable, statistically significant difference.


## 9. Conclusions

We have shown that stealthy
pathfinding is a unique aesthetic objective in relation to controls which have
beautifying treatment and no such treatment. There is also a small but
nevertheless statistically significant difference between the two stealth
effects,γ=10% versus γ=15%.
In fact, a closer inspection of the data suggests that the “jog” in
Figure 3 is the difference. Future research might
seek to better understand this more clearly.We noted that the
quantitative pattern measured by the model is somewhat different from visual inspections
of the virtual worlds. This discrepancy is consistent but seemingly counterintuitive.
Future work might set up further experiments to explore the matter further.We choseγon the
basis of trial and error. In fact, after collecting the data for γ=10% versus γ=15%,
we subsequently tried other values, for instance, γ=5% versus γ=20%.
We found no differences compared to γ=10% versus γ=15%, respectively. We speculate that the range of γeffectiveness is constrained by the virtual
world size. Future efforts might study γmore systematically in relation to parameters
which generate the virtual world.



---

*Source: 670459-2008-11-25.xml*