SIMULATION OF AUTONOMOUS AGENTS USING TERRAIN REASONING

Vinı́cius J. Cassol, Fernando P. Marson, Mateus Vendramini, Marcelo Paravisi, and Soraia R. Musse
Graduate Programme in Computer Science - PUCRS Porto Alegre - RS - Brazil
contact email: vinicius.cassol@acad.pucrs.br
Alessandro L. Bicho Cláudio R. Jung
Center of Computational Sciences - FURG Institute of Informatics - UFRGS
Rio Grande - RS - Brazil Porto Alegre - RS - Brazil

ABSTRACT ulation and training tools. In this paper we describe a

The representation of a real scenario through a 3D virtual model to provide motion of autonomous characters (human
environment populated by autonomous agents has several and non-human) in 3D virtual worlds, using terrain reason-
applications, such as games or animation movies. Such ing. The proposed method describes an integrated model
representation can be a difficult and complex task, since that begins with the terrain generation process using height
natural scenarios are composed by forms with a lot of de- maps in a pseudo-infinite world, followed by the simulation
tails that should be reproduced realistically in the virtual of characters movement generated by an algorithm based
world. Moreover, virtual people should understand and on a biological approach [24].
consider the virtual world for navigation similarly to real Together with the simulation process, we adopt the
people. In this paper we describe a model to provide mo- terrain reasoning concept. In this work, we consider terrain
tion of groups of characters based on terrain reasoning in reasoning as more than path planning or path finding. Ter-
3D virtual worlds. The model starts with the terrain gener- rain reasoning can be associated with interactions between
ation process using height maps in a pseudo-infinite world, the agent or character and terrain features, e.g. geograph-
followed by the simulation of characters movement gener- ical factors like lakes and mountains or other obstacles in
ated through an space colonization algorithm. Finally, the the environment. In this sense, agents can plan their ac-
visualization of characters motion in the 3D terrain can be tions, being able to measure effort and comfort. Moreover,
produced. agents avoid collision during their motion along the terrain.
The main contribution of our method can be defined
KEY WORDS as the integration of the biological model for group simula-
agents simulation, terrain generation, terrain reasoning. tion with terrain reasoning in 3D environments. In our ap-
proach, virtual agents (human and non-human) are capable
of moving on a terrain, and during their motion they avoid
1 Introduction obstacles or regions where walking is not allowed. Also, it
is possible to consider a planning algorithm to provide to
Nowadays, the process of conception and development of the agents a better way to achieve the goal.
a virtual world is still an expensive activity that consumes
The paper is organized as follows: the next section
a lot of time and work in the production of games and an-
presents the related work identified in the literature con-
imation movies. Usually, a virtual world needs to repre-
sidering the processes of terrain generation and characters
sent efficiently the features that can be observed in the real
movement in the environment. Section 3 presents in details
world. We can observe the nature, present in the real world,
the proposed model, while Section 4 presents and discusses
as a complex space, composed by many different elements
some results of our method. Finally, Section 5 presents
which are rich in forms, colors, details and functionalities
some final considerations and possibilities for future work.
that need to be satisfactorily reproduced during a virtual
world generation.
Furthermore, some aspects can be considered during 2 Related Work
the production of a virtual world, e.g. the fact that vir-
tual worlds are often populated with characters and ob- In computer graphics we can use some techniques and re-
jects. Moreover, some simulated situations can require sources to simulate natural elements like terrains, oceans,
other agents, like virtual humans or animals, moving on trees and other plants. The use of fractals [5] provides the
the terrain. reproduction of objects with non-rigid forms. Such tech-
Simulations involving terrain generation and moving nique makes it possible to represent some natural elements
characters have been studied by several researchers, aim- like plants and snow flakes. Besides fractals, noise func-
ing to provide methods and techniques that can be applied tions as presented in the work of Perlin [20] can be used to
in different areas, such as robotics, virtual environments, include randomness, aiming to insert a textural component.
games and/or entertainment industries and as well as sim- The use of textures in a virtual object has the objective of
simulating the appearance of natural elements, e.g. wood focused on tactical decision and it was originally designed
and marble. to solve a problem in mathematical graph theory. Consid-
The terrain can be considered a very important ele- ering characters locomotion, there are start and goal points,
ment for the composition of a virtual world. Such impor- and the algorithm is designed to find the shortest routes to
tance is due to the fact that the terrain is the basis for a any position from a given initial point. The A* algorithm
representation of other elements, natural (lakes, trees and is designed for point-to-point pathfinding. It can be eas-
other geographical features) or not natural (streets, build- ily extended to tackle more complex cases, but it always
ings), in the virtual world. We can find in the literature returns a single path from source to goal. The problem is
many different techniques that can be used in terrain gen- identical to that solved by Dijkstra pathfinding algorithm.
eration. Smelik et al. [26] present a survey of procedural Given a graph and two nodes in that graph (called start and
methods for terrain modeling, where the authors discuss goal), the algorithm should generate a path whose cost is
procedural methods to generate water [9, 21, 1], vegeta- minimal, among all possible paths from start to goal.
tion [22, 13, 7], road networks [6, 19, 10, 2] and urban en- Another feature that needs to be considered in ter-
vironments [6, 30, 16]. rain reasoning methods is the motion of a single char-
A basic point considered in the terrain generation pro- acter as well as groups formed by hundreds of charac-
cess is the use of height maps. In such approach the terrain ters. Sud et al.[27, 28] presented an algorithm used for
is represented on a grid, where the value at each point (i, j) real-time path planning and navigation of multiple virtual
means height of that point. After a rendering process, the agents in complex dynamic scenes. The authors intro-
height maps can produce a similar relief as we can see in duced a new data structure called Multi Agent Navigation
natural scenarios. Different techniques can be considered Graph (MaNG) computed using GPU-accelerated discrete
in the height map production process as stochastic subdi- Voronoi diagrams.
vision [12], midpoint displacement methods [14], erosion Rodrigues and collaborators [24] presented a new
algorithms [17] and Perlin noise [20]. On the other hand, model for steering behavior called Tree Paths. Their model
Ong et al. [18] make use of genetic algorithms for ter- is based on the biologically-motivated space colonization
rain generation. According to the authors, such model is algorithm, which has been previously used to provide leaf
able to provide terrain generation considering a two-pass venation patterns [25]. Considering the space colonization,
genetic algorithm approach together with intuitive inputs their method can be used for generating steering behaviors
from user. of groups of characters. The main idea is to define the walk-
Some virtual environments (VEs) are created using able space, by the use of a set of markers represented by
procedural techniques, where all geometry is generated on points in the space. The markers can be distributed over the
the fly. The generated VE is required to be coherent and portions of the space that can be effectively occupied by the
persistent, i.e. as the agent goes back to a point previously agents, so that obstacles and not walkable regions are not
visited, it must be identical as at the first moment. One populated with markers. To walk in the space, the agent
example of this feature, which can be generally observed moves considering the presence of markers.This work (fur-
in models of virtual cities, is presented by Greuter [6] in a ther details in [24]) is used as the basis for our model, and
production of a pseudo infinite world. Such approach rep- it is detailed in the next section.
resents the terrain on a 2D grid composed by square cells.
The cells coordinates are used together with a global seed
to calculate a hash function that is used to generate pseudo
random numbers to identify the features of each cell. 3 The Proposed Model
Once the terrain is generated, it is possible to pro-
vide the motion of virtual characters on the terrain. With This section presents and discusses the proposed approach.
the main goal of simulating human locomotion in a virtual We propose an integrated model that consists of a pseudo-
space, Reich and collaborators developed some of the pi- infinite terrain generation and the simulation of 2D charac-
oneer works in this area [23, 11], making agents aware of ters motion on it. Moreover, by using data from the sim-
the environment and associating a set of actions to their ulation we can generate a visualization of virtual humans
perceived data. In their work, simulated sensors are used motion in 3D terrain. The pipeline of our model is pre-
to find environment features such as the terrain type, obsta- sented in Figure 1, where it is possible to identify the steps
cles and hostile locations that are used to provide the agent followed during the execution of our model. The terrain
locomotion. Moreover, a behavioral control, based on the generation phase has a supporting tool that allows the user
information received from the sensors, is used to define the to customize some terrain features. Moreover, in the sim-
next agent action in the environment. ulation and visualization, we make use of a file contain-
As presented before, one of the terrain reasoning re- ing information about the simulation, e.g. the number of
quirements is to provide the agent movement avoiding ob- groups and agents, the geometric models of virtual humans,
stacles in the environment. For this purpose, it is possible the goal of each group, among others.
to identify well know techniques such as the Dijkstra [4] The following sections explain individually each one
and the A* [8] algorithms. The Dijkstra algorithm is more of the main phases of our method.
 using the following function:

seedcell = hash(pxcell ⊕ hash(pycell ⊕ globalseed)).

(2)
Figure 2(A) illustrates the matrix containing the 5 ×
5 cells. Let us consider that in their center, a previously
computed hashed seed is defined. The obtained seeds are
then normalized into height map scale values, ranging from
0 to 255 for each cell.

Figure 1. The pipeline of the proposed model is composed

by two main modules: terrain generation and simulation
of characters motion. It is also possible to define some
semantic information in the terrain, using a specific tool
named TerrainTool. The terrain module produces markers
and special markers as input to simulation module and a
geometric model of terrain to be used in the visualization
(an auxiliar module in our model). A setup file for the sim- Figure 2. The height map generation process. Each cell
ulation step is defined by the user. This information file can of the 5 matrix is populated with integer seeds, which are
also to be used in visualization process. normalized into height map scale values (0-255) and repre-
sented as small squares (A). The small circles represent the
computed interpolated values of neighbors seeds (B). The
computation describes horizontal and vertical interpolation
3.1 Terrain Generation among all the cells to generate the final height map (C).

We developed a tool responsible for terrain generation

named TerrainTool, which basically has the following fea- The next step aims to generate the height map of the
tures: i) generation of height maps, ii) generation of terrain terrain. Once each cell has received one height map value,
geometry, iii) definition of terrain semantics, e.g. walka- we simply interpolate values for neighboring cells in the
ble and semi-walkable spaces, iv) graph generation to pro- 5 × 5 matrix, in order to find values for each vertex in
vide navigation data for characters, and finally v) creation the grid. This process used two simple linear interpolation
of markers for space colonization (detailed in Section 3.2). functions and results in a 3 × 3 matrix in which all ver-
tices have height map values. Figure 2 (B) illustrates this
The virtual world is subdivided into cells, whose size
process, using the values shown in Figure 2 (A).
(granularity) is defined by the user, as well as the global
By default, all regions of the generated terrain are
seeds. The user defines the region of interest in the world
walkable. The user can define non-walkable or semi-
to be represented by informing world coordinates. Then,
walkable places using TerrainTool. A region defined as
the mapping from the given coordinates to cells addresses
non-walkable will represent a space where the agents must
should be computed, i.e. the simple division of coordinates,
not walk during the simulation. In addition, semi-walkable
as shown in Equation 1:
places mean regions where the agents will be able to
walk in some specific situations. Furthermore, through the
pcell = mod (pworld , granularity). (1) graphical interface, the user can define an intensity level for
the semi-walkable regions, which relate to “how walkable”
In order to generate the height map, we considered the terrain is. Such value will be considered to define the
a matrix with 5 × 5 cells. The position of the cell in the agents motion in the simulation phase (Section 3.2).
center of the matrix is computed according to Equation 1. To provide information to the planning algorithm,
Afterwards, the other cells in the 5 × 5 matrix can be ad- TerrainTool generates a graph considering the information
dressed directly, in grid coordinates. For example, let us about specific regions on the terrain (composed by semi-
consider that an region of interest in world coordinates is walkable or non-walkable markers). The graph creation
located at position (58, 77). Given a granularity of 6, the process is define as follows:
position of the central cell in the matrix should be at posi-
• Firstly, we use ray casting against the terrain to create
tion (9, 12). In addition, other cell coordinates can be found
a grid of nodes. Whenever a ray intersects a terrain
directly considering the matrix structure, e.g. the cell into
region defined as non-walkable, then that particular
the right of the central cell should be (10, 12).
region is not considered for graph node creation.
After each cell coordinate is defined, we populate the
matrix with an integer hashed seed method, as proposed by • After that, we generate edges connecting every pair
Wang [29]. Each cell will receive a hashed seed, computed of created nodes. In this step, we also consider the
 terrain regions where the edges should be created. If contribution of this paper, i.e. to provide terrain reasoning
a given edge intersects any non-walkable area, it is based on space colonization algorithm. Special markers are
deleted from the graph (since this path is not possible). illustrated in Figure 3, where A presents the terrain gen-
For the remaining edges, the distance between the cor- erated and B shows the terrain representation through the
responding nodes are used to define the edge weight markers viewed in the simulation environment.
(edge cost). For semi-walkable areas, the edge weight
is further modified by considering the level of “walka-
bility” defined in the terrain tool. Consequently, edges
going through semi-walkable regions with low inten-
sity level will have lower weight, providing greater
priority to be used.

After setting the walkability levels of the entire ter-

rain, we create a set of markers and special markers (repre-
senting semi-walkable and non-walkable regions) that will
Figure 3. Representation of the terrain generated by our
be used in the simulation phase. These markers are gen-
method (A) through markers positioning in the simulation
erated using the information of the terrain geometry which
environment (B).
was created based on the height map. It starts by analyzing
the list of triangles included in the terrain and finding out
the triangle with the smallest area, to be used as reference.
To compute agents motion, initial and goal positions
For each triangle, we test if its area is greater than a given
are considered for each agent, according to what is speci-
threshold. In such situation we subdivided the triangle and
fied in the configuration file (see Figure 1 - setup informa-
test again. Empirically we define such threshold as 35%
tion). To provide the next positions of the agent at each
bigger than the smallest triangle area. The division process
time step, we select the set S of N markers that are closer
is done when all triangles have similar areas. With the new
to agent i than any other agent. This set, that defines the
triangle list, we calculate their centroids which are consid-
personal space of each agent in the environment, is denoted
ered as the markers in the simulation step. If the triangle
by:
that generated the marker is included in a non-walkable or
semi-walkable region, then such marker is considered as a
special marker. S(i) = {m1 , m2 , ..., mN }. (3)
Markers are used to provide terrain reasoning for For each marker k, the following attributes are asso-
agents, as detailed in the next section. ciated: the 3D position in the environment mk , type mtk
and weight wk . The type defines the usability of the marker,
3.2 Simulating Groups of Characters in the Gener- i.e. if the terrain region discretized through the marker rep-
ated Terrain resents a walkable, semi-walkable or non-walkable space.
For instance, lakes and grass can be considered as semi-
To provide the simulation of characters in the generated ter- walkable space, i.e. regions where motions are allowed but
rain, we use the model proposed by Rodrigues [24] where are not preferential. Non-walkable spaces describe regions
the main idea is to represent the walkable spaces in a virtual where motions are forbidden, e.g. walls, while walkable
world considering a set of points called markers (dots in spaces are possible and preferential regions to walk. Fig-
the space). This concept was initially proposed by Bicho’s ure 4 shows an example where non-walkable markers are
PhD Thesis [3], where it is defined that markers available in applied in the terrain to define a lake.
the space are considered as a resource for which characters Markers weights are inspired on the original model [3,
compete in the simulation. Such approach makes uses of 24], in order to prioritize markers that lead each agent i
a space colonization algorithm proposed by Runions [25] to its goal, depending on the agent position pi . In Equa-
that was previously used to simulate the development of tion 4, we simply included the last term in order to take
leaf venation patterns, where the venation development oc- into account a factor that represent the type of the consid-
curs considering the existence of a hormone called auxin. ered marker. It impacts the weight of marker k and can
In Rodrigues’ method, the venation model was adapted to impact in computed direction vector which generates the
animate groups, and the markers are randomly distributed new position of agents.
in the space and are used to compute the agents paths.
In this work, we distribute the markers considering f (g − pi , mk − pi )
wk = N
f tk , (4)
the triangular mesh that describes the terrain, as presented X
before in Section 3.1, allowing us to reproduce the terrain f (g − pi , ml − pi )
l=1
shape in the simulation environment. However, there are
different types of markers that should impact how the vir- where f t denotes a factor which multiplies original weight
tual characters move in the environment. This is the main wk of marker k, according to the type of considered marker
 the definition of special markers and edge weights (as de-
scribed in Section 3.1). In this case, we inform for each
agent i, the initial and goal positions and compute a se-
quence of nodes that should be reached until the final goal.
During the simulation, agents move according to the
positions of graph nodes and the weight of edges. Sec-
tion 4 presents results obtained using our terrain reasoning
method. Visualization can be performed considering 2D
agents or animated virtual humans. In the last case, we
use Irrlicht 1 engine to provide terrain rendering and char-
Figure 4. The non-walkable markers are used in the terrain acters animation. A visualization example is illustrated in
to define a lake. In (A) is presented the simulation envi- Figure 5.
ronment where it is possible to observe the markers and
special markers; and in (B) this situation is rendered during
the visualization.

(mtk ). If the marker represents a semi-walkable space,

the value for f t should come from TerrainTool (see Sec-
tion 3.1). Equation 5 presents the formal definition of f t:



 1, if mt is walkable

0, if mt is non-walkable
ft =

 varied, if mt is semi-walkable,

coming from TerrainTool specification.
Figure 5. Visualization of animated virtual humans moving
(5)
in the terrain.
Since the weights are computed for markers closer to
agent i than any other agent, the direction vector describing
the agent motion is computed similarly to [24], as shown in
Equation 6:
4 Results Presentation
N
X
d(i) = wk (mk − pi ). (6) This section presents some results obtained with our ap-
k=1 proach. To support the terrain generation process, we
present TerrainTool (see Section 3.1), which is able to spec-
The motion generation process, previously described,
ify different kinds of markers, called special markers in
was initially developed to represent human motion across
the generated terrain according what the user desires. In-
the terrain. Considering this, we show that our model can
deed, this feature allows for the user to specify semantic
be easily adapted to provide non-human motion, e.g. fish in
information about the environment. Therefore, it is pos-
a lake, since it is possible to represent a lake by the use of
sible to specify walkable, semi-walkable and non-walkable
non-walkable markers. To make it possible we can define
regions in the terrain, defining special markers in the space.
f t for each agent, so, it will distinguish regions according
Considering a natural environment, for example, it is pos-
to motion information. For example, to provide the charac-
sible to delimit a space representing a water region by the
ters motion in water places, we consider ft in the opposite
use of non-walkable markers. During the simulation phase,
way to what is defined in Equation 5. In this way, the mark-
the characters motion in this specific region is not allowed.
ers defined as non-walkable can be used in the characters
In Figure 6 the different markers defined to be used in the
motion, and the opposite with the walkable markers.
simulation environment are illustrated: In A we show the
The paths considered by the agents are dynamically markers definition in terrain through the TerrainTool where
generated as presented. The use of special markers creates 1 means semi-walkable regions and 2 means non-walkable
the terrain reasoning as an emergent feature. regions and in B we show the representation of markers and
Another possibility that can be used in the agents special markers in the simulation space.
movement is a path planning algorithm, e.g. A*. Such al- Considering the special markers, the agents move in
gorithm allows for the generation of a path with sub-goals, the space through different trajectories generated as a func-
which can be followed by the agents to achieve their main tion of our terrain reasoning model. Figure 7 shows a tra-
goal. In our method, we use the approach presented by jectory of a group of agents that needs to move from the
Millington [15]. The graph requested in the algorithm exe-
cution is defined on the terrain, considering its features and 1 http://irrlicht.sourceforge.net/
 to be used in a path. Finally, we can observe in the graph, a
region without edges (2) because such region was defined
as a non-walkable place.

Figure 6. The special markers defined by an user through

the TerrainTool (A), where 1 means semi-walkable regions
and 2 means non-walkable regions and B shows the visu-
alization of markers and special markers in the simulation
environment.

source (S) to target (T) point considering special markers Figure 8. The graph used in the A*. It is possible to observe
in the terrain (Fig 7 - A). It is possible to observe that the vertices (nodes) and edges used in the path planning
the agents do not make use of non-walkable markers in algorithm. In (1) we can see a region with semi-walkable
their motion (Fig 7 - C) and, on the other hand, the semi- places and the region without edges (2) means a space with
walkable markers are considered (Fig 7 - B, D) in the mo- non-walkable markers.
tion just in cases where it is not possible for agents to walk
across original markers (without special definition).
In the simulation environment, we can observe in Fig-
ure 9 the generated path for agents to achieve their goal.
In A, we show four generated paths that will be used by
groups of agents during the simulation phase. In B, C and
D, we present different moments of the simulation. Each
group is composed by 12 agents and initial and goal posi-
tions are determined as follows: for group 1, path is formed
from node 1 to node 4, while group 4 applies the opposite
way. Group 2 follows a path formed from node 2 to node
3, and group 3 applies the path from node 3 to 2.

Figure 7. Evolution of the trajectory of a group of agents

considering a terrain with special markers where the agents
need to go from a source point (S) to a target point (T). The
agents consider such different regions during the simula-
tion.

Integration of path planning algorithm in our model

was possible with A* implementation [15]. In this case, Figure 9. Four different paths Generated by the A* algo-
TerrainTool provides a graph according to terrain charac- rithm (A) for the groups characters motion in the terrain (B,
teristics and afterward it is used by agents in order to move C, D).
coherently using terrain reasoning. Figure 8 illustrates the
generated graph where we can see the nodes and the edges
considered in this path planning algorithm. Region (1) con- On the other hand, another possibility is to run the
tains the edges generated in a region defined with semi- A* path planning algorithm by considering the edge cost to
walkable markers and will be considered with more effort compute the best way, consequently agents avoid passing
through big depressions in the terrain. It is possible to ob- In GRAPHITE ’05: Proceedings of the 3rd interna-
serve it in Figure 10. This feature simulates a very common tional conference on Computer graphics and inter-
situation in the real world where pedestrians apply paths active techniques in Australasia and South East Asia
which require less effort from them. (New York, NY, USA, 2005), ACM, pp. 447–450.

[2] C HEN , G., E SCH , G., W ONKA , P., M ÜLLER , P.,

AND Z HANG , E. Interactive procedural street model-
ing. ACM Trans. Graph. 27, 3 (2008), 1–10.

[3] DE L IMA B ICHO , A. From Plants to Crowd Dynam-

ics: A bio-inspired model(in portuguese). PhD the-
sis, State University of Campinas, Campinas, Brazil,
2009.

[4] D IJKSTRA , E. W. A note on two problems in connex-

Figure 10. Considering the edge cost in the graph, A* can ion with graphs. Numerische Mathematik 1, 1 (De-
generate more natural paths, avoiding terrain depressions. cember 1959), 269–271.

[5] F OURNIER , A., F USSELL , D., AND C ARPENTER , L.

Computer rendering of stochastic models. Commun.
ACM 25, 6 (1982), 371–384.
5 Final Considerations and Future Work
[6] G REUTER , S., PARKER , J., S TEWART, N., AND
This paper presents a method to simulate the motion of L EACH , G. Real-time procedural generation of
groups of characters in 3D environments using terrain rea- ‘pseudo infinite’ cities. In GRAPHITE ’03: Pro-
soning. We firstly describe the concept adopted for ter- ceedings of the 1st international conference on Com-
rain reasoning, followed by descriptions of environment puter graphics and interactive techniques in Australa-
modeling and semantic information. This latter concept sia and South East Asia (New York, NY, USA, 2003),
is presented through the use of markers, which define the ACM, pp. 87–ff.
features of the space for the agents. The main contribu-
[7] H AMMES , J. Modeling of ecosystems as a data
tion is the integration between the geometric space and the
source for real-time terrain rendering. In DEM ’01:
simulation of characters using the space colonization al-
Proceedings of the First International Symposium on
gorithm [25], by creating a semantic layer that allows the
Digital Earth Moving (London, UK, 2001), Springer-
agents to behave in a realistic way.
Verlag, pp. 98–111.
Obtained results indicate that agents can be easily an-
imated in the 3D terrain, considering the space features, by [8] H ART, P. E., N ILSSON , N. J., AND R APHAEL , B. A
using our model for terrain reasoning. Moreover, accept- formal basis for the heuristic determination of mini-
able visual results were achieved, in real time. mum cost paths. SIGART Bull., 37 (1972), 28–29.
Future work should be focused on group behaviors,
mainly improving their ability to evolve in the environ- [9] K ELLEY, A. D., M ALIN , M. C., AND N IELSON ,
ment. For instance, agents should consider the presence of G. M. Terrain simulation using a model of stream
others in order to compute their best paths to reach the goal. erosion. In SIGGRAPH ’88: Proceedings of the 15th
At the moment, agents do not interact with one another. annual conference on Computer graphics and inter-
active techniques (New York, NY, USA, 1988), ACM,
pp. 263–268.
Acknowledgments
[10] K ELLY, G., AND M C C ABE , H. Citygen: An in-
This work was supported by Brazilian research agencies teractive system for procedural city generation. In
CNPQ and FINEP using incentives of Brazilian Informat- Proceedings of GDTW 2007: The Fifth Annual Inter-
ics Law (Law n 8.2.48 of 1991). The authors acknowledge national Conference in Computer Game Design and
the support granted by CNPQ and FAPESP to the INCT- Technology (Liverpool, UK, 2007), pp. 8–16.
SEC (National Institute of Science and Technology Em-
bedded Critical Systems Brazil), processes 573963/2008-8 [11] KO , H., R EICH , B. D., B ECKET, W., AND BADLER ,
and 08/57870-9. N. I. Terrain navigation skills and reasoning. In
In Proceedings of the Fourth Conference on Com-
puter Generated Forces and Behavioral Representa-
References tion (1994), pp. 219–227.

[1] B ELHADJ , F., AND AUDIBERT, P. Modeling land- [12] L EWIS , J. P. Generalized stochastic subdivision.
scapes with ridges and rivers: bottom up approach. ACM Trans. Graph. 6, 3 (1987), 167–190.
[13] L INTERMANN , B., AND D EUSSEN , O. Interactive [25] RUNIONS , A., F UHRER , M., L ANE , B., F ED -
modeling of plants. IEEE Comput. Graph. Appl. 19, ERL , P., ROLLAND -L AGAN , A.-G., AND
1 (1999), 56–65. P RUSINKIEWICZ , P. Modeling and visualiza-
tion of leaf venation patterns. In SIGGRAPH ’05:
[14] M ILLER , G. S. P. The definition and rendering of
ACM SIGGRAPH 2005 Papers (New York, NY,
terrain maps. In SIGGRAPH ’86: Proceedings of the
USA, 2005), ACM, pp. 702–711.
13th annual conference on Computer graphics and
interactive techniques (New York, NY, USA, 1986), [26] S MELIK , R. M., DE K RAKER , K. J., G ROENEWE -
ACM, pp. 39–48. GEN , S. A., T UTENEL , T., AND B IDARRA , R. A sur-
vey of procedural methods for terrain modelling. In
[15] M ILLINGTON , I. Artificial Intelligence for Games
Proceedings of the CASA workshop on 3D advanced
(The Morgan Kaufmann Series in Interactive 3D
media in gaming and simulation (3AMIGAS) (Ams-
Technology). Morgan Kaufmann Publishers Inc., San
terdam, The Netherlands, 2009).
Francisco, CA, USA, 2006.
[16] M ÜLLER , P., W ONKA , P., H AEGLER , S., U LMER , [27] S UD , A., A NDERSEN , E., C URTIS , S., L IN , M.,
AND M ANOCHA , D. Real-time path planning for vir-
A., AND VAN G OOL , L. Procedural modeling of
buildings. In SIGGRAPH ’06: ACM SIGGRAPH tual agents in dynamic environments. In SIGGRAPH
2006 Papers (New York, NY, USA, 2006), ACM, ’08: ACM SIGGRAPH 2008 classes (New York, NY,
pp. 614–623. USA, 2008), ACM, pp. 1–9.

[17] M USGRAVE , F. K., KOLB , C. E., AND M ACE , R. S. [28] S UD , A., A NDERSEN , E., C URTIS , S., L IN , M. C.,
The synthesis and rendering of eroded fractal ter- AND M ANOCHA , D. Real-time path planning in dy-
rains. In SIGGRAPH ’89: Proceedings of the 16th namic virtual environments using multiagent naviga-
annual conference on Computer graphics and inter- tion graphs. IEEE Transactions on Visualization and
active techniques (New York, NY, USA, 1989), ACM, Computer Graphics 14, 3 (2008), 526–538.
pp. 41–50. [29] WANG , T. Integer hash function. Tech. rep., HP En-
[18] O NG , T. J., S AUNDERS , R., K EYSER , J., AND terprise Java Lab., 2000.
L EGGETT, J. J. Terrain generation using genetic al-
[30] W ONKA , P., W IMMER , M., S ILLION , F., AND R IB -
gorithms. In GECCO ’05: Proceedings of the 2005
ARSKY, W. Instant architecture. In SIGGRAPH ’03:
conference on Genetic and evolutionary computation
ACM SIGGRAPH 2003 Papers (New York, NY, USA,
(New York, NY, USA, 2005), ACM, pp. 1463–1470.
2003), ACM, pp. 669–677.
[19] PARISH , Y. I. H., AND M ÜLLER , P. Procedural mod-
eling of cities. In SIGGRAPH ’01: Proceedings of the
28th annual conference on Computer graphics and
interactive techniques (New York, NY, USA, 2001),
ACM, pp. 301–308.
[20] P ERLIN , K. An image synthesizer. SIGGRAPH Com-
put. Graph. 19, 3 (1985), 287–296.
[21] P RUSINKIEWICZ , P., AND H AMMEL , M. A fractal
model of mountains and rivers. In Graphics Interface
’93 (May 1993), pp. 174–180.
[22] P RUSINKIEWICZ , P., AND L INDENMAYER , A. The
algorithmic beauty of plants. Springer-Verlag New
York, Inc., New York, NY, USA, 1996.
[23] R EICH , B., KO , H., B ECKET, W., AND BADLER ,
N. I. Terrain reasoning for human locomotion. In
In Proceedings of Computer Animation ’94 (1994),
IEEE Computer Society Press, pp. 996–1005.
[24] RODRIGUES , R. A., L IMA B ICHO , A., PARAVISI ,
M., J UNG , C. R., M AGALHAES , L. P., AND M USSE ,
S. R. Tree paths: A new model for steering behav-
iors. In IVA ’09: Proceedings of the 9th International
Conference on Intelligent Virtual Agents (Berlin, Hei-
delberg, 2009), Springer-Verlag, pp. 358–371.