A Pathfinding Optimization Using Flood Fill

It's a useful technique. It's already a fairly well-known technique, generally called "connected component labeling" or similar, but congrats for rediscovering it. BTW, when doing pathfinding or similar operations, you'll generally refer to the "flood fill" algorithm as a "breadth first" traversal. The term "flood fill" is generally used (to refer to the same algorithm) when you're discussing computer graphics or computer vision.

It was taught to me, I didn't come up with it myself. But apparently not with the correct terminology. Thanks.

The actual application of this technique to pathfinding is known as the "Distance Transform Algorithm".

Are you sure? The top two google hits for "Distance Transform Algorithm" are not the same...

Did you guys at least like the demo?

Quote:

Original post by sled Are you sure? The top two google hits for "Distance Transform Algorithm" are not the same...

Don't worry, what you described in your blog post is 100% accurate, including the use of the "flood fill" terminology. They're talking about something entirely different.

More specifically, you're talking about using flood fill to identify connected regions of a map, coloring them uniquely. Your colored map would be used to determine in O(1) time whether a path exist from A to B. They are talking about another application of "flood-filling" (really breadth-first search) to actually _computing_ the path from A to B.

Yours is a good post. Keep it up.