Weighted A* maze algorithm
Weighted A* trusts its distance estimate three times more than A* does, so it rushes toward the exit and explores less, but its path isn't always the shortest.
How it works
It's A* with the heuristic multiplied: it expands the cell with the lowest cost-so-far plus three times the estimated distance left. That pulls the search hard toward the goal, like Greedy Best-First, while still counting the steps already taken.
The result sits between A* and Greedy: usually far fewer cells explored than A*, and a path that can be longer than the shortest one, but never more than three times as long.
What to watch for
Watch it lunge toward the exit almost like Greedy, then back off and try another way when a wall gets in the way.
Properties
- Shortest path
- Not always (at most 3× longer)
- Explores
- Between A* and Greedy
- Memory
- A priority queue
Race it
Pick it in the race and see who reaches the exit first, or run it in the studio.
FAQ
Why would you want a path that might not be shortest?
Speed. In games and robotics a good-enough path found quickly often beats a perfect one found late.