How to fill scene by dots in all directions?

Question

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?

Comments

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?

Answer 1

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: