Path Finding
1. What is pathfinding?
Pathfinding is the process of finding a route from a starting position to a destination while avoiding obstacles or choosing the best available route.
2. Open Vs Closed List
In pathfinding, the open list and closed list keep track of which locations the algorithm has discovered and explored. A* uses both to find a path from a starting point to a destination.
Open List
Locations waiting to be explored.
These locations have been discovered, but the algorithm has not finished checking them.
Example: The algorithm finds three possible neighboring tiles. All three are added to the open list.
Closed List
Locations that have already been explored.
The algorithm has processed these locations and checked their neighbors.
Example: After checking a tile's possible movements, A* moves it to the closed list.
3. How the A* Algorithm Works
A* (A-star) is a pathfinding algorithm that finds a low-cost route from a start to finish.
The main idea: A* uses the open list to choose where to explore next, the closed list to track explored nodes, and \(f=g+h\) to prioritize promising routes.
f(n)=g(n)+h(n)
Term | Definition | Example |
|---|---|---|
(g(n) | Cost of traveling from the start to the current node | 4 |
(h(n) | Estimated cost from the current node to the goal | 6 |
(f(n) | Estimated total cost of the path through this node | 4+6=10 |
What is a heuristic?
A heuristic is an estimate of how far a node is from the goal. It helps A* decide which direction is promising.
Common grid-based heuristics:
Manhattan distance: Estimates movement along horizontal and vertical grid cells. Useful when diagonal movement is not allowed.
Euclidean distance: Uses straight-line distance. Useful when movement can happen in any direction.
Diagonal distance: Accounts for horizontal, vertical, and diagonal movement on a grid.
For A* to guarantee a shortest path, its heuristic must not overestimate the remaining cost, and the algorithm must handle movement costs correctly.
Vocab
Term | Meaning |
|---|---|
Node | A location that can be visited in the pathfinding graph |
Neighbor | A node directly reachable from the current node |
Open list | Discovered nodes waiting to be explored |
Closed list | Nodes that have already been explored |
G-cost | Cost from start to current node |
H-cost | Estimated cost from current node to goal |
F-cost | G-cost + H-cost |
Heuristic | Method used to estimate remaining travel cost |
Parent node | Previous node used to reconstruct the path |
Pathfinding | Finding a route through connected locations |
Diagnal Shortcut Method
The Diagonal Shortcut Method is a heuristic used in A* pathfinding. It estimates the distance to the goal by assuming the character can move diagonally as much as possible, then move straight for whatever distance remains. Instead of counting every horizontal and vertical tile separately, the method uses diagonal steps wherever possible because they move toward the goal in both directions at once.
Unity Pathfinding: NavMesh and Height Mesh
In Unity, a NavMesh helps AI characters navigate through an environment. A Height Mesh adds more accurate height information to that navigation data, helping characters be positioned correctly on uneven terrain.
Doing The Baking !!
on the game object, make sure to add a NavMesh Surface
any objects that dont move are set to static !