An Overview of the Techniques Used to Describe Virtual Terrains – Part 1

My name is Juliana and I used to work on a project called ASTROS, that built a strategy simulation system for the Brazilian Army. One of the biggest challenges of this project was to calculate routes for the agents to navigate in a very large and realistic virtual terrain.

The description of the virtual terrain posed a major challenge, more than the creation of the search algorithm itself. There were requirements like fast response time and realism. Therefore, extensive research had to be done to discover a technique or a combination of techniques that would be able to provide the desired result.

When dealing with navigation, the algorithms that calculate the routes for the agents must follow and be able to access and interpret data about the virtual environment description, because this data needs to be stored inside a structure that allows simple and fast access.

Inadequate representation of the terrain can put at risk the performance of other applications’ components, what can result in good or bad user interaction, along with immersion of the agents navigating in the virtual terrain.

The topic I will present will be divided into three parts, where I’m going to share with you some of the terrain topologies that I researched and that can be used to describe a virtual environment: their pros and cons, how they are constructed, etc. The purpose is to provide an overview that can serve as a guide if one day you face a similar challenge of having to choose a terrain topology to represent a virtual terrain.

Therefore, in this first part, I introduce you to some terminology that will be used in the post and the regular representations.

Terminology

As a quick note, it’s important to define the terms used in the text:

• Terrain features are the components that characterize a certain terrain and they can have different levels of granularity. Fine grain features would be a tree or a big rock, while coarse grain features would be forests, rivers, mountains, etc. In addition, a terrain feature is not necessarily an obstacle in your application.
• Search space is the domain that a search algorithm uses to make its search. This space is represented by a data structure, like a graph or a decision tree.
• An agent is a unit that performs multiple actions continuously and autonomously in the virtual terrain on behalf of the user. A common action that the agent must perform is to navigate in the virtual terrain.
• A cell is a representation of a small piece of the virtual terrain. A cell can have different sizes and shapes, according to the project’s needs.

Regular Representations

In a regular representation, the cells used to describe the virtual terrain always have the same size and number of edges, independently of the number of terrain features they represent in the virtual scenario. Each of these cells can be marked as either traversable or blocked according to the presence of certain terrain features, other agents, accessibility, etc. As a result, this topology will divide the virtual terrain into cells in the form of regular polygons.

Examples of regular grids using squares are presented in The Legend of Zelda: A Link to the Past, Pokémon FireRed and LeafGreen and Oxygen Not Included. Moreover, in games like Sid Meier’s Civilization V and King’s Bounty: The Legend, it is possible to see the use of a regular grid of hexagons.

Source: Examples of regular grids to describe the virtual terrain in the games “The Legend of Zelda: A Link to the Past, Oxygen Not Included and Sid Meier’s Civilization V.

The advantage of a regular grid description of the terrain is that this representation is much less complex to implement and apply search algorithms than others since the size and shape of the cells do not change.

However, this implementation has some drawbacks. The first shows that the cells maintain a single size and shape the modeling of the terrain features will most likely to be less accurate and will not allow a realistic representation of the terrain features in the virtual terrain. For example, circular terrain features will not be accurately described using square cells. Another drawback is the memory consumption and associated time overhead for searches in this structure. This means that dividing a large terrain into cells with a fine granularity can generate a massive search space for search algorithms and a negative effect on the performance and memory consumption of the system.

In the next part, I’ll start presenting the irregular terrain representations. Hence, I will discuss two of the four irregular representations: Waypoint Graphs and Visibility Graphs.

Cheers!

About the author

Juliana Brondani is a Mobile Engineer at Poatek.