Using the Flood Fill Algorithm to Create a Navigation Graph

Using the Flood Fill Algorithm to Create a Navigation Graph

To use the flood fill algorithm to create a navigation graph a single "seed" node is first placed somewhere in the map. See Figure 8.7, top left. The algorithm then "grows" a graph by expanding nodes and edges outward from the seed in each available direction, and then from the nodes on the fringe of the graph, until all the navigable area is filled. The figure shows the first six iterations of such a process.
 
Figure 8.7: The first six iterations of the flood fill algorithm
This is a similar sort of technique paint programs use to fill an irregular shape, except instead of flooding a shape with a color the editor uses the algorithm to flood a map with graph nodes and edges. Individual nodes can then be moved, deleted, or added by the designer to give the desired result. To ensure that an agent’s movement is unrestricted, during the process the algorithm ensures that all nodes and edges are positioned a minimum distance equal to the agent’s bounding radius from any walls.
 

2 thoughts on “Using the Flood Fill Algorithm to Create a Navigation Graph

  1. 您好,感受民族风情,增添家居情趣,为您传情达意,您的满意——-我的追求。民族风情手工坊经营各种民族手工艺品、特色家居装饰品、民族包包、民族娃娃、一定有您喜欢的,来看看吧^_^,店址:http://shop33377978.taobao.com  

  2. 你的博客都好专业  你很喜欢现在的工作吧   羡慕
    我在考虑是否换工作   但现在仍未确定什么是自己真正的兴趣  而且也没把握能把兴趣作为职业而不厌倦   所以暂时维持现状吧

Leave a Reply

Your email address will not be published. Required fields are marked *