---

Translated from "training / 2000 pacs collision map". {.is-info}

In addition to player-controlled characters, the world contains characters controlled by artificial intelligence (NPCs, non-playable characters). These NPCs must be able to move as any human player would, and travel to any accessible location. The problem is therefore to find a way to map the 3D world into accessible zones, and to connect these zones so that movement from zone to zone is possible.

We chose to generate a graph of accessible positions (both on the ground and in the sky, for flying vehicles), recording in each node information about the size of the domain covered by the node. At this point, the problem remains whole because we must find a way to simply describe the geometry of the ground or space, in order to know which zones are accessible by which type of character.

As specified by the developers, the source code was written in ANSI C++, making extensive use of the STL, under Microsoft Visual Studio 6.0.

Before examining the considered solutions, the 3D world representation must be introduced. Given that the world must support more than 3,000 simultaneously connected players, the territory is sized accordingly (over a hundred km²). To allow sufficient detail and reduced memory footprint (since the entire world must be available on the player's computer), the 3D engine developers used Bezier surfaces for landscape description. Nevertheless, since accelerated rendering cards can only draw triangles, each Bezier surface is subdivided into triangles before display. Thus, the ground is modeled by rectangular Bezier surfaces called patches. The patches used average 16m × 16m.

An example with 4 edge-to-edge patches.

For greater modeling flexibility, patches can be rectangular and can have 1, 2, or 4 neighbors on each edge. We can therefore construct a surface:

We first studied the solution proposed by Joseph O'Rourke in Computational Geometry in C. Here we must examine the movement of a robot from point A to point B, on a plane cluttered with obstacles:

The algorithm proposed by O'Rourke is to compute the visibility graph (including points A and B), and to find the shortest path from A to B. In the previous case, we obtain the following result:

Applied to the 3D problem, we use the tessellation of patches — the discretization of patches into triangles. It suffices to subdivide the patches into triangles, then compute the visibility graph between all triangle vertices.

The tessellation of the previous example.

However, such a solution generates an enormous number of arcs (on the order of n² where n is the number of nodes), and it does not account for the width of the robot. There are ways to solve the robot width problem (based on Minkowski sums), but this is only adapted to a single type of robot, and risks causing other problems when considering multiple robot types.

Another simple approach consists of dividing the ground into a sheet of convex polygons, and performing a vertical extrusion such that the resulting prism is completely empty. The space has been discretized into prisms.

Here again, we had problems, on one hand due to surface folding (and thus overlapping prisms), and on the other hand due to prism positioning — the problem remains of knowing where to place prisms to reproduce the terrain configuration (surface meshing problem).

We therefore chose an intermediate method, making use of the terrain's patch structure. Each patch is subdivided according to a quadtree of sub-patches, each representing an accessible zone. If a zone is covered by an obstacle, then the patch subdivision follows the obstacle's contour (up to a certain precision).

Each terminal sub-patch is associated with a node in the graph, and it then suffices to connect this node with the nodes of neighboring terminal sub-patches.

This system has the advantage of being hierarchical (and thus easily analyzable), of generating detail only where necessary (cliff edges, rocks...), and of building upon the patch structure that is also used by the 3D engine. However, this method has the disadvantage of being less precise and of potentially blocking access to some accessible zones. Nevertheless, we judged this method interesting and sufficiently configurable (maximum depth of quadtrees) to be able to control the total number of nodes. This method also allows (as we will see later) taking into account terrain specificities such as ground inclination, maximum "ceiling" height, etc.

A terrain parcel in normal rendering (left) and the same parcel from the point of view of patch subdivision (right).

Each node, associated with a sub-patch, represents an accessible zone. This remains somewhat vague, as we have not yet specified what is meant by zone. We chose cylindrical zones, as this is the model best suited to a human morphology (we rejected the sphere, which induces too many degrees of freedom relative to walking on the ground). The nodes therefore carry cylinder height/width information. We added to this a surface inclination value (such that only creatures capable of climbing can scale vertical or even overhanging walls). Here, the cylinder width calculation is done directly by examining neighbors and "holes" in the surface. For storage reasons inherent to the AI part, these values are kept in a discretized form — the information is stored on 3 or 4 bits, rather than 32.

Nuances must nevertheless be added to the accessible zone/obstacle model, since we introduced sensitivity to inclination, ceiling height, etc. Initially, we kept the raw subdivision when these parameters varied. For example, considering the inclination parameter in the following situation:

Using the fact that "those who can do more can do less," it suffices to keep the nodes corresponding to the less inclined zone, and to keep a global node on the more inclined zone, like this:

Note that the node corresponding to the more inclined zone extends over the entirety of the sub-patch. We defined a notion of terminal nodes and non-terminal nodes (for zones that can encompass other nodes). Thus, the deeper one descends in the sub-patch hierarchy, the less restrictive the inclination or height characteristics, but the smaller (in width) these zones become.

This calculation is trivial; it suffices to compute the normal vector to the surface at the center of the sub-patch, and to keep the angle between the vertical and this normal vector.

The cylinder height is calculated by raising a prism whose base is the sub-patch itself, to the maximum height without collision with environment elements (patches, various objects...). The elevation is done in the direction of the surface normal, assuming that the surface deformation is negligible.

An example of cylinders generated on a patch.

The cylinder width is calculated by recursively traversing neighboring patches, and descending in the hierarchy to find the nearest sub-patch with more restrictive constraints — a smaller cylinder height or greater inclination. Patches are traversed by a flood fill mechanism (from each patch, neighbors that have not already been traversed are recursively visited).

Once the surface subdivision into sub-patches and node creation are complete, the algorithm links nodes to each other, taking advantage of the hierarchical structure of sub-patches. It would not be wise to link a node to all its neighbors (i.e. a node associated with a sub-patch p to all nodes associated with sub-patches neighboring p), as this would generate too many arcs, many of which would be redundant with an arc from a "parent" node. We therefore chose to link a node A to one of its neighbors B only if B is less restrictive (in terms of inclination and height) than A (still following the principle that "those who can do more can do less"). Note that arcs are always bidirectional to avoid sink zones, which one can enter but cannot exit.

It appeared that during modeling, Bezier surfaces can interpenetrate — environment elements modeled as patches embed directly into the ground. The corresponding nodes must nevertheless be linked, to allow agents to pass the obstacle as a simple terrain feature. Thus, each patch with "holes" is marked, and a reference to the patches generating these "holes" is kept. It then suffices to link each sub-patch missing a neighbor on an edge to the best sub-patch generating the hole.

The example below illustrates the results obtained. In the left figure, we observe that the sub-patch subdivision is interrupted due to the protrusion rising from the ground, and in the right figure, we can see that the links have been recomposed between the ground and the protrusion, at the level of the intersection:

A terrain parcel traversed by a scenery element. Green patches are horizontal, yellow are vertical, and red are inverted patches (left). The same parcel with the view of links between patches — some links may not appear as they are hidden by the scenery itself (right).

To allow flying agents to orient themselves in the world, we also implemented a system for computing spatial nodes, inspired by the quadtree model. Space is organized as an octree, recursively divided into rectangular parallelepipeds, up to a maximum depth or until the parallelepiped is empty. The height/width calculation is done by locating the nearest "hole" in the octree hierarchy.

Representation of the octree as boxes (left) and representation of the links in the octree (right).

Spatial nodes are then linked to ground nodes, so that flying agents can reach solid ground. This is done by scanning all spatial nodes missing neighbors on an edge, and electing, for each of these nodes, the best ground node (the most accessible, the most aligned with the parallelepiped axis, etc.).

Given the extent of the virtual world, it was decided that it would be divided into territories, themselves decomposed into zones (the entire world spans more than a hundred square kilometers, divided into 4,800 zones, each approximately 160m × 160m). It is obvious that generating the graph in a single piece is impossible — it would take more than a week of computation at once, and everything would have to be redone each time a zone is modified. The computation is therefore done zone by zone, with saving of the necessary parameters for each zone.

This implies a 2-pass computation for each zone:

1. The first pass computes the patch subdivision and the octree spatial decomposition, using the tessellation of the current zone and the 8 neighboring zones. The nodes of the zone are linked to each other.
2. The second pass links the current zone to the 8 neighboring zones.

For this purpose, we implemented a save system including the sub-patch hierarchy, octrees, the graph including arcs to nodes not belonging to the zone, and with pointer relocation on loading (using hash tables to accelerate relocation).

A portion of the test zone (left) and the same portion with visualization of patch tessellation (right).

An example of graph computation, the same parcel but seen from another angle. Green, yellow, and red arcs are ground arcs; violet arcs are spatial arcs; blue arcs link the ground to the airspace.