# How to fill scene by dots in all directions? Attention Topic was automatically imported from the old Question2Answer platform. Asked By Robotex

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?

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?

jgodfrey | 2020-09-24 16:36 Reply From: Robotex

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():