Amit's Game Programming Information

Amit’s Game Programming Information

# Shortest Paths Determining how to move around on a map is an interesting problem. There are many different approaches, ranging from simple (walk forward until you hit something) to the complex (path finding algorithms with heuristics). These are pages about pathfinding in general, with some bias towards A*: Amit’s Introduction to A* , Breadth-First Search, Dijkstra’s Algorithm, and Greedy Best-First Search — with interactive diagrams and sample code Pathfinding: the basics covers different types of graphs (grids, waypoints, navmeshes) used for graph search algorithms like A* Fringe Search [PDF] - possibly faster than A* for games (download the code here ) Cooperative Pathfinding [PDF] - useful when you have many units moving in narrow spaces, and need the units to be aware of each other A* My current favorite algorithm is A*, because it can handle varying terrain costs well, and it seems to be faster than most graph searching algorithms. However,

Read full article from Amit’s Game Programming Information