Press Play and watch the algorithm search: light blue is what it has already looked at (expanded), yellow is what it still has pending (the frontier) and, at the end, blue is the path. Paint walls, mud or traps by dragging over the grid, and move the start and the goal.
They all do the same thing: take a cell out of the frontier, expand it and add its neighbours. The only difference is WHICH one they take. Breadth-first, the oldest (fewest steps). Depth-first, the newest (finds something, rarely the best). Uniform cost, the cheapest so far (the cheapest path). Greedy, the one that looks closest to the goal (fast, but easily fooled). A*, the one that adds what was spent and what seems to be left: the cheapest path while looking at less.
With weight 1, A* always gives the cheapest path, because the straight-line (Manhattan) distance never overestimates what is really left. Raising it makes A* trust that estimate more: it looks at fewer cells, but may stop giving the best path. With a very high weight it behaves like greedy.
Takes the one with the lowest sum of what was spent and what seems to be left (g + weight·h). With weight 1, the cheapest path while looking at fewer cells.
Going over something already painted with the same brush erases it.
Press Play to watch the search, or «To the end» for the result at once.
| Algorithm | Expanded | Steps | Cost |
|---|---|---|---|
| 103 | 18 | 18 | |
| 21 | 20 | 20 | |
| 103 | 18 | 18 | |
| 31 | 20 | 20 | |
| 62 | 18 | 18 |