0 votes

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?

in Engine by (254 points)

1 Answer

+1 vote

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)
by (82 points)

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

Welcome to Godot Engine Q&A, where you can ask questions and receive answers from other members of the community.

Please make sure to read How to use this Q&A? before posting your first questions.
Social login is currently unavailable. If you've previously logged in with a Facebook or GitHub account, use the I forgot my password link in the login box to set a password for your account. If you still can't access your account, send an email to webmaster@godotengine.org with your username.