# A Pathfinding Optimization Using Flood Fill

This topic is 3735 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

A Pathfinding Optimization Using Flood Fill I wrote up a short post describing a technique that can be used to optimize pathfinding. You might find it useful or interesting if you're new to pathfinding. And there's a small, browser based demo.

##### Share on other sites
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.

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

##### Share on other sites
The actual application of this technique to pathfinding is known as the "Distance Transform Algorithm".

##### Share on other sites
Are you sure? The top two google hits for "Distance Transform Algorithm" are not the same...

Did you guys at least like the demo?

##### Share on other sites
Quote:
 Original post by sledAre 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.

1. 1
Rutin
46
2. 2
3. 3
4. 4
5. 5

• 13
• 10
• 12
• 10
• 13
• ### Forum Statistics

• Total Topics
632995
• Total Posts
3009774
• ### Who's Online (See full list)

There are no registered users currently online

×