I'm trying to autobuild navgraph for scene. As first stage, I'm trying to fill scene by dots.

I created this algorithm:

``````extends Node2D

var points : Array = []
var max_generation = 100
var points_distance = 30

print("a")

func add_point(position : Vector2, current_generation : int = 0) -> void:
return

if current_generation >= max_generation:
return

points.push_back({"position": position, "generation": current_generation})

current_generation += 1

add_point(position + Vector2(1, 0) * points_distance, current_generation)
add_point(position + Vector2(-1, 0) * points_distance, current_generation)
add_point(position + Vector2(0, 1) * points_distance, current_generation)
add_point(position + Vector2(0, -1) * points_distance, current_generation)

func point_already_exists(position : Vector2) -> bool:
for point in points:
if point.position == position:
return true

return false

func _draw():
var label = Label.new()
var font = label.get_font("")

for point in points:

draw_string(font, point.position, String(point.generation), Color(1, 1, 1))

label.free()
``````

But it doesn't fill scene to all directions smothely:

How can I rewrite this algorithm to fill field in all directions?

in Engine

Is the intent to always fill a scene with a rectangular grid? The current implementation looks like an attempt at a basic recursive flood fill algorithm. If you are indeed after a rectangular fill, I'd suggest just using a typical row/column based, inner-loop, outer-loop mechanism to step through a grid.

Otherwise, maybe you could provide some additional details about the ultimate goal, and why you're using a recursive flood-fill algorithm?

I solved it:

``````extends Node2D

var points : Dictionary = {}
var points_to_add : Array = []

var edges : Dictionary = {}

var max_generation = 10
var points_distance = 30
var max_cycles_per_update = 60

init_filling(Vector2(300, 300))

func _physics_process(delta):
var space_state = get_world_2d().direct_space_state

var counter = 0
while not points_to_add.empty() and counter < max_cycles_per_update:
cycle_once(space_state)
counter += 1

update()

func init_filling(start_position : Vector2):
points_to_add.push_back({"position": start_position, "x": 0, "y": 0})

func fill_points():
var space_state = get_world_2d().direct_space_state
cycle_once(space_state)

func cycle_once(space_state) -> void:

if "from" in point:
var result = space_state.intersect_ray(point.from, point.position)

if not result.empty() and result.collider.is_in_group("Obstacles"):
return

return

if point.x >= max_generation or point.y >= max_generation or point.x <= -max_generation or point.y <= -max_generation:
return

if "from" in point:

points[point_hash(point.position)] = {"position": point.position, "x": point.x, "y": point.y}

var pos = point.position + Vector2(1, 0) * points_distance
points_to_add.push_back({"position": pos, "x": point.x + 1, "y": point.y, "from": point.position})
pos = point.position + Vector2(-1, 0) * points_distance
points_to_add.push_back({"position": pos, "x": point.x - 1, "y": point.y, "from": point.position})
pos = point.position + Vector2(0, 1) * points_distance
points_to_add.push_back({"position": pos, "x": point.x, "y": point.y + 1, "from": point.position})
pos = point.position + Vector2(0, -1) * points_distance
points_to_add.push_back({"position": pos, "x": point.x, "y": point.y - 1, "from": point.position})

func point_already_exists(position : Vector2) -> bool:
return points.has(point_hash(position))

func point_hash(position : Vector2) -> String:
return "x" + String(position.x) + "y" + String(position.y)

func add_edge(from : Vector2, to : Vector2) -> void:
return

edges[edge_hash(from, to)] = {"from": from, "to": to}

func edge_already_exists(from : Vector2, to : Vector2) -> bool:
return edges.has(edge_hash(from, to))

func edge_hash(from : Vector2, to : Vector2) -> String:
return point_hash(from) + "-" + point_hash(to)

func _draw():
#  var label = Label.new()
#  var font = label.get_font("")

for key in points.keys():