---

This document was written by Benjamin Legros at Nevrax in 2001, as part of his internship project on the PACS (Pathfinding And Collision detection System) library. It describes the design, algorithms, and implementation of the surface-based pathfinding system used in the NeL engine. {.is-info}

We recall here the principle of massively multiplayer online games, introduced earlier. These games no longer rely on a simple linear story, but seek above all to develop the community and social bond between players.

Games generally never end, and one can leave the game at any time to return later. These games are always hosted on the servers of the companies that develop them. A player who wishes to evolve in the virtual world must first connect, be identified and recognized before being able to actually play. The novice player must then go through a character creation phase, where they define their avatar by choosing their appearance, functions and particularities, adjusting their physical abilities, etc. Many of these games are drawn from the Heroic Fantasy universe, such as Ultima, Everquest, Asheron's Call. However, new types of universes are appearing, designed to attract a wider audience, such as Anarchy Online, Star Wars Galaxies, etc.

The essence of these games lies in interactivity with other players through combat and commercial exchanges. However, to add diversity and animation to the game, autonomous characters controlled by artificial intelligence are also used. This implies being able to control the movements of different entities in the game, whether they are manipulated by human players (preventing forbidden movements) or by the server (planning a valid movement without encountering obstacles).

Like most other online video games, the project is organized on a server/client architecture. The server application maintains the ongoing game, manages the different players and artificial intelligences, while the client application is the direct interface between the player and the game, performing real-time 3D rendering, sound, and input processing (keyboard, mouse, gamepad).

These applications use a common library, NeL (for Nevrax Library), broken down into different modules:

• Misc: general utility classes, basic mathematics and geometry, file and stream management, portable object serialization
• Network: network management classes (mainly based on TCP/IP)
• 3D: the real-time 3D rendering engine, based on the OpenGL API
• AI: the artificial intelligence engine
• PACS (Pathfinding And Collision detection System): the system for managing static and dynamic collisions, and pathfinding

The first point to note is that this library is portable, meaning compilable and usable on any platform. In practice, portability is ensured for Microsoft Windows systems and Linux.

The second point is its open-source distribution, under the GNU-GPL (GNU General Public License), allowing the development of a community of programmers beyond the game itself and the evolution of technology for the benefit of all.

Another particularity is the 3D landscape modeling using warped surfaces, with Bezier patches. This is innovative in the video game industry (currently, no game on sale integrates real-time warped surfaces), and this is possible thanks to the arrival of high-performance graphics cards in the consumer market. Thanks to this modeling, the precision of the patch discretization (also called tessellation) adapts to the desired refresh rate and the distance of the object being rendered. Finally, the memory space used is smaller than with static facet modeling at the same precision.

This particularity poses new problems that did not classically appear in the video game world, as we will see later.

For editing convenience, the universe is divided into 160m x 160m zones, assembled on a grid, and reused to accelerate modeling time. With this system, it is planned to generate more than a hundred square kilometers of terrain.

Finally, classic objects (characters, buildings, scenery elements) are modeled traditionally with facets, coupled with progressive degradation techniques (Level Of Detail and Geomorph).

As previously stated, the universe must include, in addition to players, intelligent entities capable of moving as naturally as a human would. The first concern is being able to locate oneself in the universe, other than by simple coordinates -- that is, to identify the surface and materials on which the entity rests in order to anticipate possible collisions with scenery elements, or simply to know the accessible positions from a specific point.

We chose to associate the pathfinding problem with the problems of locating in the universe and preventing/detecting collisions with static elements (walls, cliffs, impassable material, etc.) for the sake of coherence: pathfinding must not propose a path that the collision system rejects, for example. The data preparation will therefore be the same for the pathfinding system and the collision system.

We identified 3 possible types of movement, depending on the entity's behavior and the distance of movement.

1. Random, wandering movements, where the path is not imposed. For example, a cow grazing in a meadow, or an animal fleeing. This type of movement does not directly involve pathfinding, but rather collision detection and prevention, to know if it is possible to advance in a certain direction.

2. Short-distance planned movements, not involving routes. For example, an animal trying to reach food it can see. It knows precisely where to go and looks for a path.

3. Long-distance planned movements, involving routes. To complete the previous examples, one could imagine a predator that knows in which region prey can be found, without precisely knowing the exact location. It follows a rough itinerary to get there.

We can illustrate the three behaviors with the predator example, which after planning its global itinerary (3), reaches key points (called waypoints) by refining the path through a precise search (2), then wanders in ambush for prey (1). Once prey is located, it finds a precise route (2), then pursues its prey by following it (1).

The concept of a route is, in the context of video games, more subjective because it corresponds for example to material elements (paved roads, intended for that purpose), or gameplay elements (migration routes, streets busier than others, etc.) These routes are therefore generally "placed by hand", as their generation cannot be automated.

The object of this project is the creation of a system allowing pathfinding of the second type, that is, planned from one given point to another, on the surface, and respecting terrain constraints (inclination, materials, ...).

To move an entity in a simple way, a series of control points (waypoints) is needed. However, to avoid potential problems due to encounters between entities, a "safety corridor" must be provided in which we are assured of not colliding with the scenery.

Trajectories with collision	Trajectories without collision

The path will therefore include, in addition to waypoints, a safety corridor definition, as illustrated in the following figure:

The constraints set by the development team are due to the fact that the game must run in real time on the servers. On one hand, the memory space required by the application must fit on the servers, at most a hundred megabytes (given that the servers will host many other services), and on the other hand, the computation time for a path must allow several tens of thousands of requests per second (or even a hundred thousand or a million).

We set ourselves the following objectives:

• 100KB of data per km² of terrain, or approximately 12MB for the entire terrain
• 1000 pathfinding and waypoint calculation requests per 10ms
• At most one week of computation for preparing data for the entire world, representing approximately one hour of computation per square kilometer

We will try to respect these constraints as best as possible in developing a solution. We will evaluate results on the extrapolation of a portion of the world, not having the complete game data before the end of the game's development.

We studied several solutions, drawn from the video game world or from previous work. All these solutions are based on representing the accessible space as a graph, with subsequent pathfinding in this graph, such as Dijkstra's algorithm (or its variant, A*).

In the presentation of the solutions considered, we will keep in mind the size of the explorable world in the game, which represents more than 100 km², as well as the strong hardware constraints that have been imposed on us, mainly available memory space on the servers.

This method is presented in Joseph O'Rourke's book, Computational Geometry in C, and is based on a visibility graph of the world.

Obstacles are assumed to be polygonal. The vertices of these polygons constitute the nodes of the graph, to which we add the start and end points of the path. We connect nodes pairwise if the associated points can see each other directly, without crossing an obstacle, as illustrated in the following figures:

The initial figure, with 2 polygonal obstacles (gray), and the start and end points A and B.

Each vertex is represented by a node in the graph, and the arcs connect nodes "that see each other mutually". The weight of each arc is the direct distance between the associated points.

By applying Dijkstra's algorithm, we obtain the following solution:

Here, we must consider that the object to be moved is reduced to a point. To move objects of non-zero size in this way, we must additionally consider the Minkowski sum, that is, the enlargement of obstacles by the size of the object to be moved. The resolution is otherwise unchanged.

The Dijkstra search can be accelerated using a distance heuristic (this is the A* algorithm, which we will use later).

The advantage of this method lies mainly in its simplicity. It is easy to associate other information with the nodes, such as the type of ground material, etc.

However, this resolution only works well for small 2D problems. Indeed, the graph size is O(n²), where n is the number of nodes in the graph, and it quickly becomes difficult to identify 3D obstacles modeled by Bezier patches. Finally, the graph is only adapted to one type of entity, and as many graphs as there are entity types must be generated.

This is the simplest and most widely used solution in older video games. It consists of applying a 2D grid whose cells are the graph nodes, and the arcs are the neighborhood links between cells.

On each cell, information such as accessibility, the type of entity it can support, etc. is associated.

To use multiple levels, multiple surfaces are referenced on the same cell, or multiple grid levels are used.

Again, the advantage is the extreme simplicity of the system. But in the same way, this solution is mainly suited to geometrically simple problems (i.e., relatively flat ground, obstacles aligned with the grid axes), and proves too resource-intensive on large surfaces.

A variant of this method consists of directly using the facet terrain modeling and generating a connection graph between the facets. This gives us a graph perfectly adapted to the topography. Again, the graph proves to be too large for server capabilities (we estimated that the tessellation of the entire terrain weighs around 17GB, and the graph itself over 400MB).

During my previous internship, I studied a particular solution based on patches. Each patch delimits a portion of surface. We then determine which zones of the patch are accessible (by ray casting and intersection with bounding boxes), then the patch is subdivided according to a quadtree (up to an imposed maximum depth).

Left: The original patch, divided by accessibility. The contour of the inaccessible zone is not easily representable algorithmically. Right: The patch subdivided into children, sub-children, etc. The contour is not perfectly preserved, and the error is clearly visible. However, we can always reduce the precision to obtain a compromise between graph size and acceptable error.

Once the patch is subdivided, each node is connected to its neighbors, as illustrated below:

The idea of this method is to limit the amount of information in empty areas, and to generate detail only where necessary. Moreover, the delimited zones, typically rectangles, are nearly convex and ensure that we can traverse the zone from end to end without encountering obstacles.

The results obtained, although better than the other methods, are not satisfactory given the imposed constraints: the entire pathfinding system represents slightly more than 500MB of data for acceptable precision, and the error becomes too large for the required size.

Nevertheless, the pathfinding system for flying entities (not discussed here) will be retained. It is based on the same principle, that is, dividing the space into hierarchical octrees.

The octree, represented by boxes	The links between the octree nodes

These images are from the report of the previous (2nd year) internship.

As we specified previously, we approached the pathfinding problem with the perspective of locating and collision problems. We therefore looked for a simple and economical way to locate oneself in the world.

In studying the problem, it appeared that in addition to position, it is necessary to have surface information, that is, a set of positions sharing the same characteristics (inclination, orientation, type of material), and the boundaries of these surfaces. We also sought to approach a 2D study, seen "from above", leaving aside for the moment problems of overlap, vertical walls, etc.

We therefore defined surfaces as sets of terrain points satisfying the same properties. These surfaces resemble sheets in 3D. Thus, we can deduce, by establishing beforehand that these sets will be connected, that it is possible for an entity to reach any other point of that surface from any point on the same surface. This point lays the first foundations for pathfinding.

For the collision problem, surface borders directly form a support for their detection. Testing an entity, probably modeled by a cylinder or bounding box, against a surface border is relatively simple if we represent a border as a sequence of points.

As we will see later, locating a point on a surface is relatively simple if the borders are judiciously organized.

Finally, since each surface is directly linked to its neighbors by its borders, we can establish a neighborhood graph between surfaces.

The pathfinding algorithm from point A to point B in the world roughly proceeds as follows:

1. Locate the surfaces on which A and B are found.
2. Search for a surface-to-surface path (A* algorithm).
3. Determine the crossing points between surfaces, then determine a path within a surface itself, seeking collisions with the borders.

Left: The original surfaces (gray ones are impassable). Right: The surface-to-surface path given by the A* algorithm.

Left: The optimal path, within surfaces, with optimal crossing points between surfaces. Right: A wider, non-optimal path, but with a safety margin on the left and right.

This approach does not guarantee that the path is optimal. It is possible to find examples where A* gives poor results, due to the overly approximate heuristic. Likewise, choosing good crossing points between surfaces assumes being able to predict the optimal path in the next surface.

Left: The original configuration, with the path given by A*. Right: There are infinitely many crossing points between surfaces. One would need to set up an optimization problem, which is beyond the scope of this project and probably does not lend itself to a real-time application.

The project was divided into 3 parts. The first phase consisted of researching the method, then evaluating the memory cost and developing the surface computation. The second phase corresponds to adapting the data for pathfinding (taking into account the zone division of the world). Then the third phase involved coding the pathfinding solution.

The planned schedules were superimposed on Nevrax's internal schedules. We planned the project in its broad outlines, before developing each part independently. Through a system of weekly objective forecasting/validation, we kept the schedules up to date throughout the project's duration.

Changes in the definition of system features caused delays at the end of the project, which consequently prevented us from delivering a completely functional application. Nevertheless, the shortcomings of the application were identified and planned for in the company's future schedules.

Milestone	Date	Duration	Deliverable
Milestone 1	March 30, 2001	3.5 weeks	Problem stated. In-depth study and research of different solutions.
Milestone 2	May 11, 2001	6 weeks	First software version running on the server, with non-optimal or incoherent data.
Milestone 3	June 2001	6 weeks	Integrated and functional pathfinding system. Data generator meeting the set constraints.

Week	Planned	Actual
5/3 -- 9/3		Installation of work environment. Writing of the document stating the pathfinding problem.
12/3 -- 16/3	Evaluation of the surface solution cost	Coding and evaluation: tessellation generation, element links, surface computation, surface border generation.
19/3 -- 23/3	Discussion on the API to deliver to AI, implementing a trivial solution. Evaluation of the solution.	API fixed in a first version. Evaluation on a portion of terrain and validation of estimates.
26/3 -- 30/3		Implementation of entity models. Re-evaluation of the terrain.
2/4 -- 6/4	Level computation per surface	Implemented. Assembly of surfaces between zones.
9/4 -- 13/4	Definition of the border data structure and construction. Assembly of surfaces across an entire territory.	Border structure and computation started. Surface assembly completed. Problem reassessed from the perspective of brick-based terrain construction.
16/4 -- 20/4	Graph computation per model	Not done, due to system reassessment. Adaptation of zone computation by brick.
23/4 -- 27/4	Switch to oriented borders. Start of A* graph creation.	Oriented borders completed. A* graph started. Quadtree computation per surface.
30/4 -- 4/5	Finish A* graph. Inter-zone connection. A* search started.	A* graph completed. Connection realized. A* search not done (delay on the connection).
7/5 -- 11/5	A* search	A* search started. CGlobalRetriever creation. Local/global position retrieving completed. Report writing.
14/5 -- 18/5	Surface bypass	Not done (delay from previous weeks). A* completed, tested on simple examples. Project documentation. Report.
21/5 -- 25/5	Surface bypass	Problem decomposed into 2 sub-problems. Start of movement within a surface. Report.
28/5 -- 1/6	Pathfinding improvement. Movement within surfaces.	Surface data improved (coherence). Movement implementation in progress.
4/6 -- 8/6	Movement within surfaces. Links between surfaces.	Trajectory computation within surfaces finished. Links between surfaces addressed. Report.
11/6 -- 15/6	Links between surfaces. Functional pathfinding.	Links completed. Pathfinding functional, to be tested. Report completed.

We based ourselves on the discretization of the terrain into triangular facets (tessellation) as the support for surfaces. Each Bezier patch is subdivided so that the tessellation points are approximately 50cm apart from each other.

The generated triangles are then linked to neighbors (within the patch and between neighboring patches), then the properties of each triangle are updated.

An example scene in the world (surfaces are shown in different colors).	The tessellation of the previous scene. Each element is approximately a right triangle with ~50cm sides.

The capabilities of entities directly determine the properties of surfaces, that is, their ability to walk, crawl on walls, or even climb overhangs, or the type of terrain on which they can move, etc. We first distinguished characteristics such as inclination, orientation, materials, and the size of the largest entity that can move on the surface. These values are represented by intervals. We defined 4 possible types of inclination: flat (between 0 and 45°), steep (between 45 and 60°), vertical slope (between 60 and 120°) and ceiling (between 120 and 180°), and 4 orientations (north, south, east and west). Each triangle is characterized by its normal, and it suffices to quantify the inclination and orientation values.

We added another piece of information, the level, which is the number of surfaces below the current triangle. This will prevent surfaces from overlapping later, as illustrated below:

The surface overlaps itself. There exists a 2D point for which we cannot decide which elevation to associate.	The surface has been split into 2. There is no more overlap, and knowing which surface we are on, we can decide the elevation of the point.

The level of a triangle is calculated by casting a ray vertically from the center of the triangle and counting the number of intersections with other triangles. To accelerate the search for intersections, we use a selection grid. In practice, the calculation is more complicated due to rounding errors that lead to counting neighboring triangles and thus finding the same surface twice.

Finally, we calculated, per triangle, what is the largest entity that this triangle can support. The templates are also discretized and ordered by height and width. For the tests, we chose 4 typical values:

Model	Diameter	Height
0	1m	0.5m
1	2m	1m
2	4m	2m
3	8m	4m

To calculate the template, we raise a prism above the triangle and test intersections with other elements of the zone. Elements are pre-selected to accelerate the calculation (as for the level calculation). The largest prism without intersection directly gives the largest supported template.

The original triangle	After expansion by the given radius	The final prism, after elevation.

Once the triangle properties have been calculated, these surface elements must be grouped together according to their neighborhood. Here, we applied a "flood-fill" style filling algorithm. Starting from an element that has not been assigned to a surface, a new surface is created to which the current element is added, and we recursively traverse the neighbors that have the same properties and have not been assigned.

Above, an example of the flood-fill algorithm in operation.

It happens, particularly on surface borders, that there are isolated triangles that do not provide additional information. Indeed, these triangles are often "wedged" inside a surface whose properties are more restrictive, thus isolating the triangle and making it inaccessible. We choose to simplify these cases by readjusting the properties of the isolated triangle:

Before surface simplification.	After simplification. Isolated triangles have been "absorbed".

After the filling pass, we must determine the surface borders. What we call borders are the boundaries between two surfaces, meaning a border is associated with two surfaces only.

The algorithm that determines the borders first searches for a surface element on the border, neighboring another element in a different surface, then follows the border by circulating from triangle to triangle.

To explain the example, the black segments are the identified edges, while the red segments are the edges being evaluated. The black dot is the node around which the algorithm "turns" to find the next part of the border. For this purpose, we use a property of the generated triangles, which is that they all see their edges "turn" in the same direction, meaning they all have their normal oriented outward (or all inward).

At the end of the border generation pass, we observed that the algorithm generates many small aligned edges or small teeth that provide little information about the surface border (while occupying a lot of memory space). They need to be simplified. The reduction is lossy, eliminating points estimated to be superfluous.

The simplification algorithm eliminates points such that the surface covered by the triangle formed by the point and its neighbors is less than a threshold value, the smoothing-threshold, starting with the smallest triangles. This gives, on an example:

We did not, due to time constraints, evaluate the error as a function of the smoothing-threshold. Nevertheless, the results in practice prove satisfactory, and the reduction rate sometimes reaches 85% without obvious degradation of the borders.

A view of the landscape in the real-time 3D engine.	The computed surfaces. In red, the zones on which it is possible to walk (other colors are not representative).

Surfaces before reduction.	Surfaces after reduction (86.9%!)

Surface generation requires much more information to store than is needed for pathfinding itself. Since consumed memory space is critical data and we cannot afford to keep useless data on the server, we translated the dataset into another form, better adapted to pathfinding.

This organization takes up the principle of surfaces and borders, adding new information such as the loops generated by borders, connections between borders, etc. For memory savings, we converted point coordinates to two dimensions, and added in return a quadtree per surface that locally stores the average elevation.

The study of collision, location, and pathfinding problems led us to reorganize our data differently to optimize searches and access.

Associating a 2D position to a surface led us to determine the membership of a point in a non-crossing polygon. It suffices to cut the polygon at the abscissa of the given point, and test the ordinate with the result of the cut.

In practice, the implemented algorithm is slightly different but equivalent (it avoids actually cutting the polygon). We are therefore led to test the intersection of borders with the line x = a, a calculation we can optimize by storing the borders sorted by increasing abscissa: testing whether the chain is cut by the line is trivial, in constant time, and determining its unique intersection is O(log n), where n is the number of points in the chain.

We therefore store borders as sequences of sub-borders sorted by x. A forward marker is associated with each sub-border to indicate whether it should be traversed from beginning to end or in reverse to describe the parent chain from beginning to end.

A chain before splitting.	After splitting into sub-chains.

Once the surfaces likely to contain the given point are found (these surfaces overlap), the choice of the correct surface is made by the average value contained in the quadtree associated with each of the surfaces (the smallest distance designates the best surface).

This again involves accelerating collision detection between an entity and a border. Since this procedure is obviously local, that is, in the neighborhood of the entity, it is imperative to limit the number of tests by pre-selecting the borders to test. We put in place, for this purpose, a grid that contains in each cell the references to the borders.

As we will see later, it happens that the entity has to go around an obstacle. To do this, it must be able to follow the border of the obstacle. We must therefore, at the end of a surface border, know the next border, as suggested by the following figure:

The entity starts from A, follows border b₀, then upon reaching the junction between b₀ and b₁, must follow b₁, until it can directly reach B. This requires being able to easily find the successor of b₀.

We therefore group borders into loops, specific to each surface. In the example, surface S₀ has the loop (b₀, b₁, b₂), surface S₁ has the loop (b₀, b₅, b₃), and surface S₂ has the loop (b₁, b₃, b₄).

In the implementation, the loops are oriented so that when traversing them, the surface they relate to is always on the left (the loop traversal is thus homogenized).

The game, planned for early 2002, will have to run, for the client application, on personal computers equipped with 3D accelerator cards. The real-time rendering imperative makes it impossible, given the capabilities of this hardware, to visualize the entire world at once. Similarly, it is not possible to model the terrain as a single piece. The universe is therefore divided into 160x160 parcels, then assembled on a grid and connected to each other to reconstitute the continuity of the game space.

We chose to keep this modularity to allow each zone to be calculated separately. This additionally offers the possibility of assembling these parcels independently, like bricks, and generating terrain much more quickly, and even automatically.

Under these conditions, it is necessary to provide a link system between zones, allowing the connection of surfaces on the borders.

Surface borders at the edge of a zone are first identified, according to the side of that zone. During assembly, it is then necessary to identify the chains facing each other and reconstruct the links between surfaces. We introduced various objects for this purpose to instantiate zone models and connect them together. These objects are:

• CLocalRetriever: this is directly the template of a zone. It contains the surfaces and internal chains of the zone. It is a local object, always centered at (0,0). All coordinates internal to this object are expressed in the local frame. The surface graph is also stored in this object. The name "retriever" comes from the fact that its primary functionality is to retrieve a position on a surface (this is the location, explained above).

• CRetrieverInstance: this class realizes the instantiation of the CLocalRetriever, at a given location and orientation. The surfaces, chains, and graphs become global data, expressed in the world frame. The junctions between neighboring surfaces are effective in this object.

• CGlobalRetriever: it contains the local retrievers and the different instances that constitute the world. Everything in it, like the CRetrieverInstances, is expressed in the global frame of the universe. Note that the CLocalRetrievers are not directly stored in the CGlobalRetriever, but in a separate object, to be able to reuse them in other CGlobalRetrievers without having to duplicate them unnecessarily.

Here is the set of other defined classes, with a few words to explain their contents and functionalities:

• CRetrievableSurface: defined by the characteristics of inclination, level, material, and supported entity template. A surface contains references to the borders and neighboring surfaces that define its contour, and also the border loops defined previously.
• COrderedChain: contains the points that constitute it, sorted by increasing abscissa order. It also references the parent chain and its position in the parent chain.
• CChain: this is the boundary between two surfaces. It contains the COrderedChains, and references the surfaces located to its left and right (following its traversal direction) and the loop indices in the left and right surfaces. The two endpoints, denoted start and stop, are references to CTip objects.
• CTip: these objects unify the endpoints of chains with each other, and allow establishing a graph between chains.
• CRetrieverBank: this is a container of CLocalRetrievers, shared by several CGlobalRetrievers.

As we stated above, we restricted ourselves to pathfinding on horizontal, "walkable" surfaces, from any point A to any point B.

We decomposed the problem into three independent parts, which allows solving and testing them separately, and assembling them easily. The first part consists of finding a rough surface-to-surface path using the modified Dijkstra algorithm (A*). The second part handles finding the crossing points between surfaces, on the borders. Then finally, the last part finds a path within a single surface.

Due to lack of time, we were unable to develop solutions as performant as we had envisioned. Nevertheless, we laid the foundations of the method and will endeavor to propose better solutions in the remainder of this document.

A* is a shortest path search algorithm in a directed graph. It is based on Dijkstra's algorithm, with the addition of a heuristic that in most cases greatly improves performance.

The fundamental idea is to evaluate in priority the graph nodes that come closest to the solution to be found. In the case of physical pathfinding, a good indication is generally the straight-line distance to the solution. The node evaluation will naturally tend to approach geographically the destination point. This is indeed what we humans intuitively do when going to a given place.

The cost calculation at each node is the same as for classic Dijkstra (that is, the sum of arc costs to reach this node). The heuristic value is, however, the sum of the current node cost and the estimated cost to reach the destination. For pathfinding, we generally use the straight-line distance, which gives good results. It has been demonstrated that an optimistic heuristic, that is, one that systematically underestimates the distance to travel, allows obtaining the shortest path in all cases (the most optimistic heuristic, which equals the current node cost, corresponds to basic Dijkstra).

To illustrate the A* principle, here is an example from a program distributed on the Internet. It is a 2D grid where each cell has a variable access cost (represented by different colors).

The initial grid, before computing the solution. The green cell is the start point, and the red one the end point. Gray cells are harder to access. Black cells are impassable.	Pathfinding in progress. We can observe that the solution tends to move geographically toward the end point. The number in each cell is the cost to move to that cell.

The solution has been found. Not all nodes were evaluated, only those likely in the heuristic sense to yield a better solution. This application is from the website http://www.ccg.leeds.ac.uk/james/aStar.

In the context of this project, the graph is constituted by the surfaces and their links between them. We therefore chose to associate the barycenters (centroids) of the surfaces with the nodes, and to calculate the cost from one node to another as the distance between the associated barycenters. This approach is clearly not optimal, since it assumes moving from one surface center to another in a straight line (while we are not even assured that the center is effectively inside the surface). The cost and heuristic evaluation can be refined by taking into account the possible entry and exit points of the surfaces.

An illustration of the cost evaluation in A*. In solid lines, the current calculation method, based on surface centers. In dotted lines, a refinement of the method based on surface entry and exit points. This improvement could also link to the next part of the algorithm, the calculation of crossing points between surfaces.

The main difficulty in implementing the algorithm lies in the block division of the graph. Since the nodes are stored in the CLocalRetrievers, their position is expressed in the local frame of the zone, and one must always take care to convert it to the global frame.

The second part consists of determining the best crossing points between two surfaces. Initially, we conducted our tests by simply taking the midpoint of the border. A more satisfactory solution would be to look for the point closest to the start point in the first surface, or to minimize the distance to the end point:

In solid line, the currently implemented solution, not very efficient. In dotted lines, better approaches. Due to lack of time, we were unable to implement these solutions and test them.

This last part is, along with the graph search, the most interesting step of pathfinding. The first solution we considered is based directly on collision detection, and avoidance of found obstacles (that is, the surface borders).

First, we perform a ray cast through the surface between the start and end points, to find all intersections with borders. Here again, we pre-select the chains to test to accelerate computation time. The found intersections are then sorted by their distance from the start point. Since we assumed that the start and end points are both in the surface and that this surface is connected and closed, we can deduce that the found intersections group in pairs, the first corresponding to the exit from the surface, and the second to the re-entry into the surface. We can furthermore assert that this exit and re-entry occur on the same loop (otherwise, it would imply that the surface border crosses itself, which we excluded). Thus, we simply need to follow the border from the exit to fall back on the re-entry. In doing so, we have intuitively avoided the obstacle.

This method is entirely naive but provides a starting point for an optimal bypass method. Indeed, the algorithm gives us the set of points that deviate us from the straight-line route. Let us consider here the first block of points to bypass. It forms a polygon. If we construct the convex hull of this polygon and the start and end points, we thereby construct the shortest path avoiding this obstacle:

It suffices to repeat the process on the newly created free segments, as illustrated in the following figure:

The problem thus reduces to generating a convex hull. Convex hull construction algorithms are in the best case O(n log n) (the QuickHull algorithm, or Graham's algorithm). However, we can take advantage of the fact that we directly have to calculate, roughly speaking, the convex hull of a closed non-crossing polygon. We can use Graham's algorithm, which in this case is O(n), as illustrated further on.

The idea of Graham's algorithm is to construct the envelope polygon segment by segment, starting from a known point of the convex hull (for example, the leftmost point). We proceed as follows:

We push (onto a stack) the first three points and as long as there are polygon points to test, we test if the angle formed by the last two segments is positive. If yes, we push the next point. If no, we pop the second-to-last point. If only two points remain in the stack, we push the next point. Then we return to the beginning of the loop.

The algorithm is indeed O(n), where n is the number of points in the polygon. In its original version, the points are not ordered according to a polygon, and it is necessary to sort them beforehand (which justifies the O(n log n) cost).

Although we did not implement the desired optimal functionalities, we were able to test the search on relatively simple cases. Below, screenshots illustrate the results we obtain, observing the three phases of pathfinding separately:

The original terrain. Obstacles may block passage at the top of the image.

The path determined by A* passes through three surfaces whose contours are visible. The path is refined within the three surfaces. The path correctly passes through the midpoints of borders between surfaces.

An example of surface bypass. The start and end points are both in the same surface. It is just necessary to avoid the central surface that prevents directly reaching the destination.

When it has detected the collision, the algorithm follows the border to the collision on the other side.

The same scene seen from a different angle. The found path does not "stick" to the ground, because it is a 2D path. The height information is missing, as it is not provided since it is not directly used during object movement.

At present, the speed constraints have not yet been evaluated. It seems nevertheless that the execution speed is satisfactory (which is not surprising if one considers that we only perform simple list traversals, without nested loops).

The memory space constraint is exceeded (we approach 500KB per km²). It remains possible to reduce the size of certain objects (notably the quadtrees, which occupy almost half, on their own, of the allocated memory space).

Finally, data generation times are met; the entirety of the zones is compiled in slightly more than 3 days, after extrapolation.

• O'Rourke J., Computational Geometry In C, second edition, Cambridge.
• Robson R., Using the STL, second edition, Springer.
• Stroustrup B., The C++ Programming Language, third edition, Cambridge Press.
• Muller P.-A., Gaertner N., Modélisation objet avec UML, second edition, Eyrolles.
• Heyes-Jones J., A* algorithm for programmers, https://web.archive.org/web/20030620160704/http://www.geocities.com/SiliconValley/Lakes/4929/astar.html
• Patel A., Game programming information, http://www-cs-students.stanford.edu/~amitp/gameprog.html

This document was written by Benjamin Legros during his internship at Nevrax in 2001. It describes the design and implementation of the PACS pathfinding subsystem of the NeL engine. Translated from the original French by the Ryzom Core wiki team. {.is-info}