PathEngine home previous: Representing Positions on the Groundnext: Additional Features Overview
Contents, Overview, Fundamental Concepts, Why Integer Coordinates?

Why Integer Coordinates?

PathEngine uses an integer representation for horizontal (x and y) coordinates.
(See PathEngine Coordinates.)
Here are some frequently asked questions about this issue, with explanations.

'Why does PathEngine use integers? Wouldn't floats give us a lot more precision when placing agents?'

It's important to realise that while floating point representation gives you extra precision for numbers near zero, this extra precision comes at the expense of precision for numbers further out.

The 'grid' of points that can be represented by floating point coordinates looks something like this.

Floating point representation can lead to nightmare scenarios where code works correctly when tested for points near the origin, but fails due to approximation of points further out.

Integer coordinates give you fixed precision over the range represented. The scale chosen for the coordinate system determines the precision of agent placement and maximum world size.
PathEngine will operate correctly independantly of the scale chosen for the coordinate system so you are free to choose the scale best suited for your requirements.

'PathEngine claims to provide pathfinding in continuous space. Isn't the use of integer coordinates contradictory to this claim?'

Any binary coordinate representation implies a grid of points that can be represented. (See the 'floating point grid' above.)
PathEngine uses integers, so agent placement is necessarily restricted to an integer grid. (With the precision of the grid dependent on the coordinate scale.) Movement through continuous space is then represented in terms of lines between points on the grid. Collision between an agent moving along a line and the obstructions in the environment is performed exactly. Paths are generated as a set of lines through continuous space that are guaranteed not to be obstructed according the collision model.
Queries are provided to help with the details of moving agents along paths through continuous space and choosing an appropriate approximate point when an agent is part way along a path section.

Agents must be placed on the integer grid but lines and paths through continuous space are checked exactly against the PathEngine collision model.

Why do 3D engines generally use floats to represent object position?

Floating point representation can make sense in a rendering engine, where absolutely exact results are not required.
A certain amount of approximation when rendering is normal and has no adverse effects. And the floating range offered by this representation is very convenient given the amount of vector maths involved.

In a continuous space pathfinding system, however, approximation is a very bad thing. Failure to find a path due to approximation is bad news, and can leave agents stuck, unable to find a way around geometry.
Code to deal with approximation is messy and complicated, and adds extra work for the processor.
PathEngine is built on a system for performing geometric calculations absolutely exactly. There are a number of optimisations that depend directly on this technology and would not be possible with a floating point representation.

When to convert between integer and floating point representation

A common concern relates to the overhead of converting coordinates between integer and floating point representations, given that PathEngine requires integer coordinates but a 3D engine will require floats.

The recommended approach is to maintain agent positions in PathEngine coordinates and then convert to floating point representation whenever this is required to render the agent.
This enables you to take full advantage of the robustness PathEngine offers for your agent movement, and limits conversion overhead to once per agent per frame. The actual cost of this conversion will be completely insignificant.

Maintaining additional precision for agent position separately

If a large scale is chosen for PathEngine coordinates then this can potentially cause problems with perceived quality of motion.
Motion captured animation is particularly sensitive to small jumps in agent position due to approximation.
To address this problem PathEngine supports the representation of additional precision as floating point values relative to an agents position on the integer grid.

Extra precision components for an agent's rendering position.

PathEngine provides methods that maintain additional precision as floating point values relative to the agent's integer position.
The blue arrows show offsets from the integer position for an agent midway along a path.
These are stored as floats and therefore provide extremely high precision for the agent's rendering position, shown by the purple cross.

Documentation for PathEngine release 5.34 - Copyright © 2002-2014 PathEnginenext: Additional Features Overview