3

Description

"Based on the infamous [Craig Reynolds' Boids](https:\/\/www.red3d.com\/cwr\/boids\/) article, this piece of code is meant to be used for animating a 3D flock of mesh using `MultiMeshInstance3D`.\r\n\r\nAssuming you have a scene with such a `MultiMeshInstance3D` node, add a simple `Node` and attach the following script. It will require to specify at least the **output** node (being the multi mesh instance node).\r\n\r\n> [!IMPORTANT]\r\n> The code is very straightforward. There's no optimization (except for some quick approximations). It aims at demonstrating how easy it can be to add behavior script to an isolated node and take advantage of instanced meshes.\r\n> Be advised to not push the boids count too far. A modern CPU can manage 200 or so boids. Due to the quadratic nature of the algorithm and the heavy (for a script) use of multiplications and divisions (hello vector normalisation), the computation power usage can be reached pretty quickly.\r\n> In a further contribution, we will see how to use compute shader to speed things up.\r\n\r\n{#note_about_initial_state}\r\n> [!NOTE]\r\n> The function `_set_initial_flock_state` should be modified to set the initial state of the flock. For now, the boids are randomly scattered in a cube.\r\n\r\n## Behaviors\r\n\r\nThe steering behaviors of the flock boids are _cohesion_, _separation_, _alignment_ and _purpose_.\r\n\r\n* **Cohesion** : A boid will be attracted by other boids in its vicinity. The attraction vector is a mean (normalized) direction towards those boids.\r\n* **Separation** : A boid will be repelled by other boids that are too close. The repulsion vector is a (normalized) direction that is computed from weighted direction away from each _intruders_.\r\n* **Alignment** : A boid will align its direction to be the same as the flock in its vicinity.\r\n* **Purpose** : A boid will try to reach the target defined as a parameter. This definition of alignment is very different from the initial one as it is not a flock induced behavior. The alignment vector is the (normalized) direction toward the target.\r\n\r\n## Parameters\r\n\r\n* **output_mesh_instance** : `MultiMeshInstance3D` that will render the flock.\r\n* **structure_boid_count** : Number of boids in the flock.\r\n* **structure_starting_cube_size** : Size of the cube where the boids are initially scattered (see [note above](#note_about_initial_state)).\r\n* **capacity_max_velocity** : Maximal velocity of a boid.\r\n* **capacity_acceleration** : Acceleration of a boid. Note that a good ratio between speed and acceleration is 2 for 1 (eg. acceleration to 26 to a max speed of 13)\r\n* **capacity_obstacle_collision_decay** : Speed alteration ratio when a boid hits an obstacle.\r\n* **behavior_attraction_distance** : Distance below which boids attract together.\r\n* **behavior_repulsion_distance** : Distance boids will _try_ to keep between them.\r\n* **behavior_separation** : Weight of separation behavior.\r\n* **behavior_alignment** : Weight of alignment behavior.\r\n* **behavior_cohesion** : Weight of cohesion behavior.\r\n* **behavior_purpose** : Weight of the purpose behavior (following the target).\r\n* **interactor_attractor_node** : `Node3D` that will be used as a target for the alignment behavior.\r\n* **interator_repulsor_nodes** : A dictionary of `Node3D` mapped to a distance, serving as a list of obstacles.\r\n"

Main code

extends Node

@export_subgroup("Output", "output")

@export var output_mesh_instance : MultiMeshInstance3D

@export_subgroup("Structure", "structure")

@export var structure_boid_count : int = 76 :
	set(value) :
		structure_boid_count = value
		_allocate_flock()
		_update_flock(0.1)
		_update_instances()

@export var structure_starting_cube_size : float = 32.

@export_subgroup("Capacities", "capacity")

@export var capacity_max_velocity : float = 13.0

@export var capacity_obstacle_collision_decay : float = 0.8

@export var capacity_acceleration : float = 26.0

@export_subgroup("Behavior", "behavior")

@export var behavior_attraction_distance : float = 16.

@export var behavior_repulsion_distance : float = 1.

@export var behavior_separation : float = 4.2

@export var behavior_alignment : float = 1.6

@export var behavior_cohesion : float = 1.

@export var behavior_purpose : float = 1.6

@export_subgroup("Interactor", "interactor")

@export var interactor_attractor_node : Node3D

@export var interactor_repulsor_nodes : Dictionary[Node3D, float]

# -------------------------

@onready var flock_positions : PackedVector3Array = PackedVector3Array()

@onready var flock_new_positions : PackedVector3Array = PackedVector3Array()

@onready var flock_speeds : PackedVector3Array = PackedVector3Array()

# -------------------------

func _ready() -> void:
	_allocate_flock()
	_update_flock(0.1)
	_update_instances()
 
func _process(delta : float) -> void:
	_update_flock(delta)
	_update_instances()

func _allocate_flock() -> void:
	flock_positions.resize(structure_boid_count)
	flock_new_positions.resize(structure_boid_count)
	flock_speeds.resize(structure_boid_count)
	_set_initial_flock_state()
	if output_mesh_instance != null:
		var multimesh : MultiMesh = output_mesh_instance.multimesh
		if multimesh != null:
			multimesh.set_instance_count(structure_boid_count)
			multimesh.set_visible_instance_count(structure_boid_count)

func _set_initial_flock_state() -> void:
	var sz : float = structure_starting_cube_size / 2.
	for i in range(structure_boid_count):
		var v : Vector3 = Vector3(randf_range(-sz, sz), randf_range(-sz, sz), randf_range(-sz, sz))
		flock_positions[i] = v
		flock_new_positions[i] = v
	flock_speeds.fill(Vector3.ZERO)

func _update_flock(delta : float) -> void:
	var d_acc : float = capacity_acceleration * delta
	var target : Vector3 = Vector3.ZERO if interactor_attractor_node == null else interactor_attractor_node.position
	var ratio : float = behavior_alignment + behavior_cohesion + behavior_separation + behavior_purpose

	for i in range(structure_boid_count):
		var p : Vector3 = flock_positions[i]
		# Computing steering force ...
		var cohesion : Vector3 = Vector3.ZERO
		var alignment : Vector3 = Vector3.ZERO
		var cohesion_count : int = 0
		var separation : Vector3 = Vector3.ZERO
		var separation_count : int = 0
		for j in range(structure_boid_count):
			if i == j:
				continue
			var diff : Vector3 = flock_positions[j] - p
			var dist : float = diff.length()
			if dist < behavior_repulsion_distance:
				separation += flock_positions[j]
				separation_count += 1
			elif dist < behavior_attraction_distance:
				cohesion += flock_positions[j]
				alignment += flock_speeds[j]
				cohesion_count += 1
		cohesion = Vector3.ZERO if cohesion_count == 0 else ((cohesion / float(cohesion_count)) - p).normalized()
		alignment = Vector3.ZERO if cohesion_count == 0 else (alignment / float(cohesion_count)).normalized()
		separation = Vector3.ZERO if separation_count == 0 else (p - (separation / float(separation_count))).normalized()
		var direction : Vector3 = (target - p).normalized()
		# ... to determine new speed
		var acceleration : Vector3 = ((direction * behavior_purpose + cohesion * behavior_cohesion + separation * behavior_separation + alignment * behavior_alignment) / ratio).normalized() * d_acc
		flock_speeds[i] += acceleration
		var speed : float = flock_speeds[i].length()
		if speed > capacity_max_velocity:
			flock_speeds[i] *= capacity_max_velocity / speed
			speed = capacity_max_velocity
		# Interact with repulsors
		for j in interactor_repulsor_nodes:
			var repulsor : Node3D = j
			var distance : float = interactor_repulsor_nodes[repulsor]
			# Simple sphere collision
			var l : Vector3 = j.position - p
			var tca : float = l.dot(flock_speeds[i]) / speed
			if tca >= 0.:
				var d2 : float = l.dot(l) - tca * tca
				var sqd : float = distance * distance
				if d2 < sqd:
					var thc : float = sqrt(sqd - d2)
					var t0 : float = tca - thc
					var t1 : float = tca + thc
					var t : float = t0 if t0 < t1 else t1
					var colid : Vector3 = p + (flock_speeds[i] * t) / speed
					var sphere_normal : Vector3 = (colid - j.position).normalized()
					# For now, the speed is "reflected". It could be improved by using dot product
					# to determine if it is better to use tangent instead.
					var reflected : Vector3 = (flock_speeds[i] - (2. * sphere_normal.dot(flock_speeds[i])) * sphere_normal).normalized()
					flock_speeds[i] = reflected * capacity_obstacle_collision_decay * speed
		flock_new_positions[i] = flock_positions[i] + (flock_speeds[i] * delta)

	var tmp : PackedVector3Array = flock_positions
	flock_positions = flock_new_positions
	flock_new_positions = tmp

func _update_instances() -> void:
	if output_mesh_instance != null and output_mesh_instance.multimesh != null:
		var multimesh : MultiMesh = output_mesh_instance.multimesh
		if multimesh.get_instance_count() != structure_boid_count:
			print("Reset instance count to %d" % (structure_boid_count))
			multimesh.set_instance_count(structure_boid_count)
			multimesh.set_visible_instance_count(structure_boid_count)
		for i in range(structure_boid_count):
			var transformation : Transform3D = Transform3D.IDENTITY.looking_at(flock_speeds[i]).translated(flock_positions[i])
			multimesh.set_instance_transform(i, transformation)

Comments