Open Tutorial
PE_IntegerSpace.icon

Robust Navigation and Fixed Point Math in PathEngine

Alex J. Champandard on January 3, 2011

Whether you're just getting started with the implementation of your own navigation system, or you're beginning pre-production of a pathfinding heavy title for the first time, you're no doubt blissfully unaware of the precision monsters lucking under your bed obstacle. You may try to convince yourself that floating point (or double) precision will help address the bugs that result from processing your navigation geometry, but chances are those problems will come back to bite you at the worst possible time — unless you have a team of developers that eat floating point precision bugs for breakfast.

The other solution is to use fixed point math! It may seem old school, but when you hear advice from veteran developers still using it regularly in practice should make you think twice at least. At the Paris Game/AI Conference 2010, Thomas Young gave a micro-talk entitled "Detail Issues in Robust Pathfinding" where he digged into the solutions and tricks that PathEngine uses in practice.

NOTE: This in-depth article was made possible thanks to Thomas Young and PathEngine's sponsorship of AiGameDev.com and the Paris Game/AI Conference 2010. Thomas is an active participant in the forums too, so if you have any tricky questions don't hesitate to ask, or consider digging into the PathEngine demo available on the official site.

Avoiding Floating Point...

In practice when implementing a navigation system, Thomas suggests avoiding floating point numbers because:

  1. Results vary based on the execution context. For example different builds, platforms and CPU states will yield different result, and different bugs.

  2. Floats actually don't provide extra precision, in the general case. (See the figure below for how the precision is distributed.)

  3. Geometric error is hard to predict and control. It makes problems very hard to reproduce and isolate.

What does this mean? Thomas suggests that a precise treatment of contained space is very difficult — or even impossible — with floating point numbers!

Figure 1: Here you can see the impact of picking either fixed point (left) or floating point (right) representation for your coordinate system.

Thomas' experience matches well with many other veteran developers in the field, including Tom Forsight, who wrote this blog post on the subject. In particular, Tom dispells the myth that switching to double precision would help alleviate the problem:

“One 'solution' is to turn on double precision, because then you get more bits. Yeah, but you've just shuffled the problem around. Doubles have exactly the same weaknesses — all you've done is shuffle the problems into a corner, stuck your fingers in your ears and yelled 'lalalalalala.' They'll still come back to bite you, and because it's double precision, it'll be even rarer and even harder to track down.”

What's worse, as Tom points out, is that double precision will impact your performance significantly, as well as double your memory requirements.

Integer Space

The solution that Thomas Young describes involves using integer coordinates for everything from mesh vertices to obstruction shape corners. The key to make this work, as with fixed point in general, is to let the user decide on the precision. There is no scale factor. However, Thomas mentions 1cm as a commonly used 'pathfinding unit' — the precision at which all navigation is done.

Screenshot 2: Zoomed out view of a warehouse-like environment in the PathEngine demo.

Screenshot 3: Zoomed in version of the warehouse demo with a dynamic obstacle moving in a static navigation mesh. The red grid represents the precision of the pathfinding calculations.

In practice, PathEngine's world range is ±1,500,000 which corresponds to 30km by 30km with 1cm units. For reference, the world in JUST CAUSE 2, which uses PathEngine, is 20 miles by 20 miles. When streaming, Thomas mentioned that the coordinate origin is local to each streaming unit.

Screenshot 4: Pathfinding in the large world of JUST CAUSE 2 is handled by PathEngine.

Intersections and Interpolation

In his talk, Thomas pointed out that boundary intersections are a common source of errors in pathfinding. This happens for instance around dynamic obstacles, as shown in the figure below. In these cases, approximating the intersection calculations can change the boundary entirely.

Diagram 5: A dynamic obstacle intersecting with a static boundary. Recalculating the intersection causes the boundary to move.

Thomas mentioned that creating robust approximations is a very difficult problem, so the best solution involves representing such intersections exactly to avoid the issue entirely. Then, with the exact representation in place, you can adapt the rest of the code to approximate only if necessary. In fact, having the exact intersections can also help creating more robust approximations too.

Also, Thomas points out that interpolation suffers from similar problems in practice. Unfortunately, approximation can't be avoided in this case, and it can cause agents to be pushed inside obstructed space or snapping path segments against obstructions — as shown in the figure below.

Diagram 6: When interpolating on a path, the calculations can cause the agent's position to end up in trouble.

Note that these problems don't disappear if you switch to a floating point representation. They are just harder to understand and reason about objectively with intuitive diagrams!

Fixed Point Tips and Tricks

So how can you represent the world using fixed point math? Generally, Thomas' advice is to avoid division and irrational numbers altogether. Setting up an integer space does that very well, and in practice you can:

  • Stick to just addition, subtraction, and multiplication.

  • Don't work with anything smaller than one 'pathfinding unit.'

  • In fact, avoid fixed point fractions altogether.

As Thomas mentions, there are similarities with traditional fixed point representations, but this approach is well suited to pathfinding:

“This works out a lot clearer than other possible approaches based on fixed point fractions. Perhaps approaches based on fixed point fractions actually have to work out as the same thing, in order to address the approximation issue properly, but just with a smaller fundamental unit.”

Otherwise, for representing things like the intersection of obstacle boundaries dynamically, Thomas suggests using 'vector fractions' to replace division with multiplication. You can then simply multiply out the denominators to compare vectors. His article in Game Programming Gems 3 entitled "Using Vector Fractions for Exact Geometry" covers this topic in more details.

Diagram 7: Representing vector fractions in space.

Thomas mentions that some operations are naturally implemented this way (e.g. side of line test), but others need to be re-implemented with this representation in mind.

Boundary Invariants

One last trick from PathEngine that Thomas mentioned was boundary invariants. If you split up your world into streaming units, and keep your coordinates relative to that, then having an area of overlap between each streaming unit helps significantly. Thanks to the exact representation of boundaries, there are bits of geometry that don't change from one streaming unit to the other, and there's a buffer zone where all changes in the geometry are replicated.

Not only does this simplify the high-level code, but it also opens up seamless pathfinding across streaming boundaries. So even though the coordinate system of each streaming unit is a different integer space (as described above), they can all be combined together to form long paths.

Screenshot 8: Top left streaming unit, with the boundary zone between the yellow and red lines.

Screenshot 9: Bottom right streaming unit that lines up diagonally with the other boundary.

Summary

For reference, you can download the slides from this presentation at the Paris Game/AI Conference 2010 here:

Detail Issues in Robust Pathfinding
Thomas Young, 2010.
Download PPT or PDF

Creating a production quality navigation system is no easy task, regardless of what representation you chose for your coordinate system. However, with fixed point math you have a better chance of identifying and resolving these problems, using the tricks mentioned in this article.

Photo 9: Thomas Young at the Paris Game AI/Conference on June 23rd 2010.

Discussion 3 Comments

soupcan on January 4th, 2011

I read the article. So, as I understand it, the basic idea is,"just stick to integers (even if it means scaling the coordinate system to something like cm) because you can't get infinite precision. By doing this, (or at least using a fixed number of decimals) the error is consistant, understandable, and easier to recognize." Do I understand the article correctly? It sounds like good reasoning to me. If you can't truely solve the problem, then make is easier to understand and thus easier to work around when it shows up.

dayoung on January 5th, 2011

It looks like the links to the PPT/PDF are broken.

sua_khb on January 6th, 2011

Floating-point operations are equal to integers, in the "good" precision (like cm), where you need not get really undefined precision (Fig. 1) - so we can use this simplification for all the "practice" tasks. This is not a universal solve of the all probably problems (Diag. 5,6) but you can easily understand whats happen

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!