system
September 24, 2020, 2:56pm
1
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
September 24, 2020, 9:12pm
2
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: