My A* pages have some diagrams on them that look like this:
Colorful! Pretty! But what do the colors actually mean?
- In A*, the g value tells you how far you are from the start. In the diagram, this is blue.
- In A*, the h value is a guess of how far you are from the end. In the diagram, this is yellow.
- Areas that are in between are greenish.
- Areas that are bright are along the path.
- Areas that are both far from the start and far from the goal are darker. (None shown here)
Even though I know what the colors mean, I find it hard to interpret this diagram. It's hard to interpret two color channels together. It's hard to see the g and h values separately, and really hard to figure out the f value, which combines the two.
I've been thinking about how to reorganize and rewrite my pathfinding pages, and I want to make diagrams that better convey the key concepts. What variables from the algorithm could I show?
- The g value, the actual distance from the start to any other location.
- The h value, the estimated distance from any location to the end.
- The f value, the combination of g and h, used for deciding which order in which to process locations.
- The parent pointer, which tells you how you got somewhere.
- The open set, showing which locations need to be processed.
- The closed set, showing which locations have already been processed.
My existing diagrams show the state when the algorithm ends. For g, h, f, parent, this is fine. However, open and closed aren't particularly interesting at the end, so I hadn't bothered making a visualization for them. I focused on g and h. When I went back to make these diagrams interactive (see demos for square, hex, and triangle grids), I did the same thing. I now think that was a mistake. It's just not a good visualization.
The algorithm is a dynamic process. Locations change from “unvisited” to “open” to “closed” over time. State transitions aren't easily expressed in the static diagrams I had made. But the state transitions are the key to understanding how the algorithm works, and explain why you even want the f value. There's no backtracking in A*; it has a “frontier” that expands outwards until it hits the goal. That's one of the key concepts. And I hadn't shown that at all on my A* pages.
So here's an attempt at a diagram showing open and closed as well as the default state of unvisited, captured while the algorithm is still running, not at the end:
The blue is open; the shaded areas are closed; the lighter areas are unvisited. Is it as colorful as the first diagram? No. But I think it's much easier to interpret. It's still missing the key point: the blue frontier expands over time. To show that expansion, I need to animate this diagram. That's what I'll work on next.
In this case, the thing I want to visualize — the frontier — comes directly from the algorithm. In other projects, such as the article on probabilities, the key concept in the visualization didn't exist in the algorithm. I need to be open to the possibility that the concepts I should show aren't necessarily the ones that are directly encoded in the algorithm's variables.
When you learned graph search, what were the key concepts that helped you understand it? I've been focusing on the expanding frontier (open set) but I'd love to hear what else I should be looking at as I work to rewrite my pathfinding pages.
Labels: making-of , pathfinding
Post a Comment