===== Path Finding =====

==== Motivation ====

You have a map containing solid obstacles which block the movement of certain entities. You wish to find the shortest path to a destination, taking into account the fact that these obstacles must be avoided.

==== Description ====

There are many path finding algorithms available for use in [[grid]]-based games. Some take into account a "cost" value for each tile. This is useful if your game has varying terrain (such as mud, sand and water) which take different times to travel along.

==== A* Search Algorithm ====

This is probably the most common path finding algorithm used in games, as it is relatively fast. It makes use of a heuristic, which cuts down on computation time through estimation. See the [[A* algorithm]] for additional details.

==== Dijkstra's Algorithm ====

This is another popular path finding algorithm, but is slower than A* as it does not make use of heuristics. See [[Dijkstra's algorithm]] for more information.

==== See Also ====
  * [[Grid]]
  * [[A* algorithm]]
  * [[Dijkstra's algorithm]]

==== References ====

  * [[http://www.cokeandcode.com/pathfinding|Path Finding on Tile based Maps with A* - Coke And Code]]