Godot 4 - Unconventional optimized boids / flocks

gistfile1.txt

extends Node2D

@export var entities_count: int = 5000
@export var entities_container: Node2D

@export_category("Optimization")
@export var draw_grid: bool = true
@export var grid_color: Color = Color(0.3, 0.8, 1.0, 0.3)
@export var grid_cell_size: float = 100.0
@export var randomness_frame_update_interval: int = 30

@export_category("Behavior")
@export var direction_change_chance: float = 0.25
@export var max_random_direction_degrees: float = 25.0
@export var use_leader: bool = false
## Only applies when use leader is active
@export var trouble_following_leader: float = 3.8
## At which distance form the target boids will stop moving
@export var stop_distance_sq: float = 2.5

@export_category("Detection")
@export var area2d_lag_frames: int = 6

@onready var fps: Label = %Fps
@onready var other_spatial_grid: Node2D = $SpatialGrid
@onready var area2d: Area2D = $Area2D

var frame_counter: int = 0
var area2d_frame_counter: int = 0
var speed: float = 250
var target_position: Vector2 = Vector2.ZERO
var EntityScene = preload("res://test_scenes/optimized_swarm/swarm_enemy.tscn")

var spatial_grid: Dictionary = {}
var batch_start: int = 0

var entities: Array[Node2D] = []
var entities_positions: PackedVector2Array = []
var entities_velocities: PackedVector2Array = []
var entities_angle_offsets: PackedFloat32Array = []


func _ready() -> void:
	entities.resize(entities_count)
	entities_positions.resize(entities_count)
	entities_velocities.resize(entities_count)
	entities_angle_offsets.resize(entities_count)
	
	other_spatial_grid.entities_count = entities_count
	
	for i in entities_count:
		var entity = EntityScene.instantiate()
		entities_velocities[i] = Vector2.ZERO
		entities_positions[i] = Vector2(randf_range(-500,500), randf_range(-500,500))
		entities_container.add_child(entity)
		entities[i] = entity
		
		
func _input(event: InputEvent) -> void:
	if MouseUtils.is_left_click(event):
		target_position = get_global_mouse_position()


func _physics_process(delta: float) -> void:
	fps.text = "FPS: %d" % Engine.get_frames_per_second()
	if not is_node_ready():
		return
		
	frame_counter += 1
	if frame_counter >= randomness_frame_update_interval:
		_recalculate_randomness()
		frame_counter = 0
		
	area2d_frame_counter += 1
	if area2d_frame_counter >= area2d_lag_frames:
		area2d_frame_counter = 0
		area2d.position = entities_positions[0]
		
		
	_update_spatial_grid()
	other_spatial_grid.update(entities_positions)
	
	# pre-calculate stuff to be faster
	var max_speed = speed * delta
	
	for i in entities_count:
		var is_leader = i == 0
		var velocity = Vector2.ZERO
		var distance_sq_out = [0.0]
		
		if use_leader:
			if is_leader:
				velocity = _compute_velocity_to_target(i, max_speed, distance_sq_out)
			else:
				velocity = _compute_velocity_to_leader(i, max_speed)
		else:
			velocity = _compute_velocity_to_target(i, max_speed, distance_sq_out)
			
		if distance_sq_out[0] <= stop_distance_sq:
			velocity = Vector2.ZERO
			# use return to stop EVERYONE ^^ LOL
			continue
			
		#entities_velocities[i] = velocity
		#entities_positions[i] += entities_velocities[i]
		entities_positions[i] += velocity
		
		if velocity.length() > 0.1:
			entities[i].position = entities_positions[i]
			entities[i].rotation = velocity.limit_length(1.0).angle()
		
	if draw_grid:
		queue_redraw()
		
		
func _draw() -> void:
	if not draw_grid:
		return
	
	# Only draw occupied cells
	for cell in spatial_grid.keys():
		var cell_pos = Vector2(cell.x * grid_cell_size, cell.y * grid_cell_size)
		var rect = Rect2(cell_pos, Vector2(grid_cell_size, grid_cell_size))
		
		# Draw cell border
		draw_rect(rect, grid_color, false, 3.0)
		
		# Optional: draw boid count in cell
		var count = spatial_grid[cell].size()
		if count > 1:
			var text_pos = cell_pos + Vector2(5, 15)
			draw_string(ThemeDB.fallback_font, text_pos, str(count), HORIZONTAL_ALIGNMENT_LEFT, -1, 12, Color.WHITE)
		
		
func _compute_velocity_to_target(i: int, max_speed: float, out_distance_sq: Array) -> Vector2:
	var direction = target_position - entities_positions[i]
	direction = direction.rotated(entities_angle_offsets[i])
	
	  # Pass back this value via array
	out_distance_sq[0] = direction.length_squared()
	return direction.limit_length(max_speed)
	
	
func _compute_velocity_to_leader(i: int, max_speed: float) -> Vector2:
	var direction = entities_positions[0] - entities_positions[i]
	direction = direction.rotated(entities_angle_offsets[i] * trouble_following_leader)
	return direction.limit_length(max_speed) 
		
		
func _update_spatial_grid() -> void:
	spatial_grid.clear()
	for i in entities_count:
		var cell = _get_grid_cell(entities_positions[i])
		if not spatial_grid.has(cell):
			spatial_grid[cell] = []
		spatial_grid[cell].append(i)
	
	
func _get_grid_cell(pos: Vector2) -> Vector2i:
	return Vector2i(
		int(pos.x / grid_cell_size),
		int(pos.y / grid_cell_size)
	)
	
	
func _recalculate_randomness() -> void:
	var max_angle = deg_to_rad(max_random_direction_degrees)
	var angle_range = max_angle * 2.0
	
	# Update a rolling batch (better cache performance)
	# and randomize batch size each time (between 10% and direction_change_chance%)
	var min_batch = int(entities_count * 0.1)
	var max_batch = int(entities_count * direction_change_chance)
	var batch_size = randi_range(min_batch, max_batch)
	var batch_end = min(batch_start + batch_size, entities_count)
	
	for i in range(batch_start, batch_end):
		entities_angle_offsets[i] = (randf() * angle_range) - max_angle
	
	# Move to next batch
	batch_start = batch_end
	if batch_start >= entities_count:
		batch_start = 0


func _on_area_2d_area_entered(area: Area2D) -> void:
	print("Unit or structure detected !!!")

And the spatial grid isolated code, essentially the same as in the main scene. Both have no purpose right now, but there cosmetic, or can be used to further boids avoidance/alignemen/separations calculations

class_name SpatialGrid
extends Node2D

@export var draw_grid: bool = true
@export var grid_color: Color = Color(0.8, 0.1, 0.5, 0.4)
@export var grid_cell_size: float = 100.0

var spatial_grid: Dictionary = {}
var entities_count: int = 0 : set = _set_entities_count
var entities_positions: PackedVector2Array = []

func _set_entities_count(value: int) -> void:
entities_count = value
entities_positions.resize(entities_count)

func _physics_process(_delta: float) -> void:
_update_spatial_grid()
if draw_grid:
queue_redraw()

func _draw() -> void:
if not draw_grid:
return

# Only draw occupied cells
for cell in spatial_grid.keys():
	var cell_pos = Vector2(cell.x * grid_cell_size, cell.y * grid_cell_size)
	var rect = Rect2(cell_pos, Vector2(grid_cell_size, grid_cell_size))
	
	# Draw cell border
	draw_rect(rect, grid_color, false, 3.0)
	
	# Optional: draw boid count in cell
	var count = spatial_grid[cell].size()
	if count > 1:
		var text_pos = cell_pos + Vector2(5, 15)
		draw_string(ThemeDB.fallback_font, text_pos, str(count), HORIZONTAL_ALIGNMENT_LEFT, -1, 12, Color.WHITE)

func _update_spatial_grid() -> void:
spatial_grid.clear()
for i in entities_count:
var cell = _get_grid_cell(entities_positions[i])
if not spatial_grid.has(cell):
spatial_grid[cell] = []
spatial_grid[cell].append(i)

func _get_grid_cell(pos: Vector2) -> Vector2i:
return Vector2i(
int(pos.x / grid_cell_size),
int(pos.y / grid_cell_size)
)

func update(_positions: PackedVector2Array) -> void:
entities_positions = _positions