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

In my last post, I wrote about regular terrain representations. In this post, I will write about the irregular representations and delve deeper into the topics of the Waypoint Graph and Visibility Graph representations.

Irregular Representations

Irregular terrain representations are the ones that use cells with different sizes and/or shapes to describe the virtual terrain. For example, this type of representation can use smaller cells to represent areas of the virtual terrain that contains many terrain features that act as obstacles. In contrast, it can use larger cells to represent empty areas without terrain features in the same terrain. In this example, search algorithms would require less memory to execute the search than in the regular representation, as the smaller number of cells in certain areas would speed up the exploration of the search space.

The authors Kapadia & Badler (2013) consider that irregular topologies may be divided into waypoint graphs, visibility graphs, and navigation meshes. In addition to these techniques, in this text, a quadtree will also be considered an irregular representation, although it may be often classified as a hierarchical representation.

Waypoint Graphs

In this type of terrain representation, waypoints are placed in the virtual terrain and then linked to create a graph. This construction can be done with a manual or autonomous placement of these waypoints. A waypoint graph representation example is demonstrated in Figure 2.

The benefits of this technique are compared to regular grids, the waypoint graphs create a much sparse and less complex search space. Therefore, they are much cheaper to store in memory and can generate fast response to the navigation algorithms. The drawbacks of the waypoint graphs don’t guarantee the full coverage of the virtual terrain. Besides, agents will always stay on the same possible paths in every execution, which makes their behavior constrained and unrealistically.

Source: Representation of a virtual terrain using a waypoint graph. (Anguelov, 2011)

Visibility Graphs:

The construction of a visibility graph is very similar to a waypoint graph. However, instead of connecting manually or autonomously placed waypoints, a visibility graph will connect the vertices of the obstacles in the virtual terrain between each other and with the initial and goal position of the agents. The construction of a visibility graph is illustrated in Figure 3.

The main advantage of this technique is that the path found by a search algorithm will be the actual shortest path between the initial and goal positions. The explanation for this is that the connections of the vertices of the graph are either a straight line or a tangential line to the terrain navigation obstacles. However, if the initial and/or goal positions are not inserted in the visibility graph, they must be inserted and connected before computing a path. The time for this insertion can generate a large overhead depending on the size of the graph. The overhead time can even become greater than the time used to compute the path. Besides, like a waypoint graph, a visibility graph does not allow flexibility for the agents’ movement.

Source: Representation of a virtual terrain using a visibility graph. (Anguelov, 2011)

In the next and last post about virtual terrain representation, I will present the Quadtree and the Navigation Mesh representation. These are more complex techniques, but they are frequently used or combined with other techniques in the industry to create a solution for virtual representations.

See you in the next part!

Cheers!

About the author

Juliana Brondani is a Mobile Engineer at Poatek.