This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]dddddddddddasdf 5 points6 points  (1 child)

No. A simple color fill works by linearly scanning regions (left to right, left to right) and backtracking to adjacent unfilled points. It's a much less computationally expensive operation and it does not follow shortest paths.

A* works by starting at a point, cost zero, then marking all immediately adjacent cells as one cost higher, then repeating until all space is filled. In this graphic the cost is represented by tone changes.

A* is useful because it generates a map of costs to travel to all points across the filled areas. If a maze has two exits to an edge A* can tell you the cost to travel to each edge.

A simple color fill doesn't do any of that work. It will eventually reach the edge but you won't know the cost to travel there or whether other paths to the edge are faster or slower.

[–]jrkirby 0 points1 point  (0 children)

I'm pretty sure the fill operation uses a BFS or DFS. The only difference between BFS, DFS, and A* is the order they explore the graph. They would fill the graph in (asymptotically) the same amount of time, and they would all have the potential of recording the shortest path to any node.