How to flood-fill 2D game map by dots flowing around obstacles filling just areas when player and bots can walk?

Question

I need to flood-fill walking area of map by dots. How can I do it?

I'm thinking about next algorithm:
1. choose random point on map that is not inside obstacle
2. put this point to map and then recursively check is the next four coordinates not inside obstacle
3. For point's inside obstacle - abort recursion
4. For point in walkable area - go to step 2

Will it work? How to check that point inside obstacle (but bots, items and spawn areas are not obstacles and we should to put points here)?

Is there exists more effective algorithm?

Answer 1

If you're using a tilemap, it's easy. This is the flood fill I use to check for closed-off areas in a procedural dungeon. I wouldn't use recursion, as it's a pretty simple algorithm anyway:

var looked = {}
var q = []
var curr = Vector2(0, 0)

# Pick a random, walkable point.
while not G.WALK[G.map_tiles.get_cellv(curr)]:
    curr = Vector2(randi() % MAP_SIZE_X, randi() % MAP_SIZE_Y)

q.push_back(curr)
while not q.empty():
    curr = q.pop_front()
    looked[curr] = true
    for dy in 3:
        for dx in 3:
            var l = Vector2(curr.x + dx - 1, curr.y + dy - 1)
            if (not looked.has(l)) and G.WALK[G.map_tiles.get_cellv(l)]:
                looked[l] = true
                q.push_back(l)

Comments

Not tilemap. I want use it for 3d too in future.

---

I guess you could divide up the volume into a grid, about as large as an obstacle, and cache all the locations in an array -- then use the same algorithm. Or you could make a node with an area node attached and move it through the volume in basically the same way, using the area to detect collisions with the obstacles -- but that might be slower.

---

How to detect collisions of point with obstacles?

---

Looks like, Physics2DDirectSpaceState.intersect_point may help

Just get the state from the world and do the queries.

http://docs.godotengine.org/en/stable/classes/class_physics2ddirectspacestate.html#class-physics2ddirectspacestate-intersect-point