TABLE OF CONTENTS I may not have gone where I intended to go, but I think I have ended up where I intended to be. Douglas Adams (1952 - 2001), The Hitchhiker s Guide to the Galaxy
Pathfinding, in general terms, refers to the logic by which agents render a path from one point on the battlefield to another. For a human, of course, pathfinding is not usually a difficult problem, at least when the terrain is not overly complicated. In contrast, the problem of endowing agents with robust, intelligent, autonomous pathfinding and navigating abilities is highly nontrivial [Murphy00] .
If there are no obstacles, and the battlefield consists only of open terrain, a simple self-initiated vectoring from a starting point to a desired end point (via a single weight component directed toward that end point) suffices to move an agent toward its goal.
But what is an agent to do if a terrain element blocks its view, and/or the straight-line-path, to its desired goal? In principle, if terrain elements were all simply convex, a trivial rule of the form back up, turn 45/90 deg, then move forward again command may suffice for most cases. However, rigid rules of this form are generally not very robust and give rise to unrealistic motion. Moreover, if a scenario includes nonconvex terrain elements (as even semirealistic scenarios are likely to do), more complex algorithms must be used to ensure that agents are able to traverse the terrain.
In addition to basic...
