Index

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.

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.

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.

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.

• Grid
• A* algorithm
• Dijkstra's algorithm

• Path Finding on Tile based Maps with A* - Coke And Code