Qualitative Improvements of Biasing a Routes Starting Position

In this note I'll be discussing how biasing an entities starting position before providing it to the pathfinder, can improve the qualitative behavior of your game's characters. This technique was used on a multi-platform game [Ramsey 2009a].

Generating a route to destination can be parametrized in many ways, but one of the most fundamental parameters has a trickle down effect attune to an avalanche with observable repercussions on an entities motion - if selected incorrectly.

What I'm suggesting is that the start position provided to the path finder is one of the most important parameters to get correct. It almost seems intuitive to suggest that the starting point is "where your at." Well, maybe not so - we need to think temporally. Consider not only our thoughts, but our movement - it's always changing, adapting and what's appropriate at this moment in time is not necessarily appropriate 5 seconds from now, probably not even one second in the future. This applies to selecting a starting position for our animating penguin. We are more interested where it'll be rather then where it's at currently.

The picture below illustrates a simple environment where we have a penguin that wants to move from position A to position B. A typical pathfinder would be supplied with the penguins current position as the start position, and position B as the end point. The problem with this seemingly correct solution is that it fails to factor in any forward momentum of the penguin. Whether the forward momentum is implicit in the animation driving the penguin or an associated movement rate of a simple sprite where the penguin is at (t) is not where it'll be at (t+1).

The penguins directional vector is represented by the light blue line, the pink segments is the path returned if the penguins current position is used as the starting point, and the green segments is the route when we factor in not only the penguins directional vector, but also it's velocity. The yellow bidirectional connections is the graph representation of the navigation mesh.

Depending on how fast the penguin is moving, we bias the start position of the penguin farther and farther away. A simple technique is to attain the penguins heading and magnitude of translation over one frame (t). And then using a standard unit of measurement (r) - I used the diameter of the penguin, you multiply (r*t) = (s). I also experimented with the radius and this worked as well for animals that didn't translate too fast. (s) then becomes a scale that we can apply to the penguins directional vector, with a resulting point in the environment that serves as the starting point for your path finding algorithm. Straightforward and it allows for the continuation of the penguins motion with out any jarring hitches caused by the pathfinder (I had coded up a modified version of A-Star that supported our modeling methods) .

This technique is not only useful in this directed graph representation, but also on typical grids and navigation meshes. I hope you find it useful as using this technique had a qualitatively positive impact on the movement of the animals in World of Zoo.

References

[Gibson 1986] James J. Gibson. The Ecological Approach to Visual Perception. Hillsdale,

NJ: Lawrence Erlbaum Associates, 1986.

[Ramsey 2009a] Michael Ramsey. “A Unified Spatial Representation for Navigation

Systems.” Proceedings of The Fifth AAAI Artificial Intelligence and Interactive

Digital Entertainment Conference, 2009, pp. 119–122.

[Ramsey 2009b] Michael Ramsey. “A Practical Spatial Architecture for Animal and

Agent Navigation.” Game Programming Gems 8, edited by Adam Lake. Boston:

Charles River Media, 2010.

[Ramsey 2009c] Michael Ramsey. “An Egocentric Motion Management System.” Game Engine

Gems 2, edited by Eric Lengyel. Natick: A.K. Peters, 2011.

Further Reading

1. “On the Nature of Things” Lucretius, translated by Ronald Melville is wonderful book expounding the atomic theory first presented by Epicurus. Book I covers the two principles of beingness: that nothing ever came from nothing and that nothing ever returns to nothing. Book 2 discusses the principles of continual motion and how collisions shape the free will. Book 3 covers the nature of the mind, while Book 4 explains the nature of vision, hearing, taste, smell and how aspects of the environment enter the mind. Book 5 and 6 wrap covering mortality and environmental effects.