How to fill scene by dots in all directions?

[system]

	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
var point_radius = 5

func _ready():
	add_point(Vector2(200, 200))
	
	print("a")
	
func add_point(position : Vector2, current_generation : int = 0) -> void:
	if point_already_exists(position):
		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_circle(point.position, point_radius, Color("#ffff0000"))
		
		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

[system]

	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 point_radius = 5
var max_cycles_per_update = 60

func _ready():
	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.clear()
	points_to_add.push_back({"position": start_position, "x": 0, "y": 0})
  
func fill_points():
	var space_state = get_world_2d().direct_space_state
	while not points_to_add.empty():
		cycle_once(space_state)

func cycle_once(space_state) -> void:
	var point = points_to_add.pop_front()

	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
  
	if point_already_exists(point.position):
		add_edge(point.from, point.position)
		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:
		add_edge(point.from, point.position)
		
	points[point_hash(point.position)] = {"position": point.position, "x": point.x, "y": point.y}
  
	var pos = point.position + Vector2(1, 0) * points_distance
	if not point_already_exists(pos):
		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
	if not point_already_exists(pos):
		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
	if not point_already_exists(pos):
		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
	if not point_already_exists(pos):
		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:
	if edge_already_exists(from, to) or edge_already_exists(to, from):
		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():
		draw_circle(points[key].position, point_radius, Color("#ffff0000"))
	
#    draw_string(font, points[key].position, String(points[key].x) + ":" + String(points[key].y), Color(1, 1, 1))
	
	for key in edges.keys():
		draw_line(edges[key].from, edges[key].to, Color("#ff00ff00"))

#  label.free()

Result: