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.