How can I handle hundreds of calculation heavy nodes at the same time?

Question

I'm currently trying to implement a basic boids simulation with godot in c#.

Currently I managed to implement evasive behavior which works fine for a boid count of roughly 300. Everything beyond that is CPU limited and the simulation starts to lag.

I want to increase the amount of boids more into a number of thousands. What I tried for now is an offload of the evasive behavior into a thread per boid. But I soon realized that one thread for each boid is probably not the right way to achieve this.

So my question is: What is the proper way to handle such amounts of nodes?

I know my code is in c#. I don't need a proper solution in c# but rather a hint on where and how to offload the workload into a thread or something like this.

My world script does the following:

• Add n boids to the scene with randomized position and rotation (It's a wip so please ignore the messy rng stuff :D )
• Start a time for text update
• Pick one boid as the chosen one for visualization and speed read

using Godot;
using System;

public class World : Node2D
{
    [Export]
    private PackedScene boidScene = ResourceLoader.Load("Boid.tscn") as PackedScene;
    private Boid chosenOne;
    private int boidCount = 350;
    private string groupName = "boids";

    public override void _Ready() {
        base._Ready();
        AddBoids();
        StartTextUpdateTimer(CreateTimer());
        PickChosenOne();
    }

    private void AddBoids() {
        var random = new Random();
        var screensize = GetViewport().Size;
        var rng = new RandomNumberGenerator();
        for (int i = 0; i < boidCount; i++) {
            var boid = boidScene.Instance() as Boid;
            boid.GlobalPosition = new Vector2(rng.RandfRange(0f, screensize.x), rng.RandfRange(0, screensize.y));
            var direction = (random.NextDouble()* (Math.PI * 2))-Math.PI;
            boid.GlobalRotation = (float)direction;
            AddChild(boid);
        }
    }

    private void StartTextUpdateTimer(Timer timer) {
        timer.Connect("timeout", this, "_On_Timer_Timeout");
        timer.WaitTime = 1.0f;
        timer.OneShot = false;
        timer.Start();
    }

    private Timer CreateTimer() {
        var timer = new Timer();
        AddChild(timer);
        return timer;
    }

    private void _On_Timer_Timeout() {
        RichTextLabel richTextLabel = GetNode("Speed") as RichTextLabel;
        richTextLabel.Text = "Chosen speed: " + chosenOne.LinearVelocity.Length();
    }

    private void PickChosenOne() {
        var index = new RandomNumberGenerator().RandiRange(0, GetTree().GetNodesInGroup(groupName).Count);
        chosenOne = GetTree().GetNodesInGroup(groupName)[index] as Boid;
        chosenOne.Chosen = true;
    }
}

And my boid scene does the following:

• Adds itself to the boids group
• Add raycasts for collision scanning (I want to simulate the view with a viewing distance)
• On each tick: Get boids in perception and evade from closest one.

using Godot;
using System;
using System.Linq;
using System.Collections.Generic;

public class Boid : RigidBody2D
{
    [Export]
    private string groupName = "boids";

    [Export]
    public int MinSpeed { get; set;} = 80;

    [Export]
    public int MaxSpeed { get; set; } = 120;

    [Export]
    public int Torque { get; set; } = 25;

    [Export]
    public bool Chosen { get; set; } = false;

    private int perceptionRadius = 150;
    public int EvasionDistance { get; } = 80;

    private float radStep = 10 * Mathf.Pi / 180;

    private Color vis_color = new Color(.867f, .91f, .247f, 0.1f);
    public List<RayCast2D> RayCasts { get; } = new List<RayCast2D>();


    // Called when the node enters the scene tree for the first time.
    public override void _Ready()
    {
        AddToGroup(groupName);
        AddRayCasts();
        ApplyInitialImpluse();
    }

    private void AddRayCasts()
    {
        float i = 0;
        while (i < 2 * Mathf.Pi)
        {
            if (IsInVisibleArea(i))
            {
                var rayCast = new RayCast2D();
                AddChild(rayCast);
                rayCast.Enabled = true;
                rayCast.CastTo = new Vector2(0, -perceptionRadius).Rotated(i);
                RayCasts.Add(rayCast);
            }
            i += radStep;
        }
    }

    private bool IsInVisibleArea(float i)
    {
        // Note: Blindspot between 225° and 315°
        return (i < 5 * Mathf.Pi / 4 || i > 7 * Mathf.Pi / 4);
    }

    private void ApplyInitialImpluse()
    {
        var rng = new RandomNumberGenerator();
        var impulse = new Vector2(rng.RandiRange(MinSpeed, MaxSpeed), 0).Rotated(Rotation);
        ApplyImpulse(new Vector2(), impulse);
    }

    public override void _IntegrateForces(Physics2DDirectBodyState state)
    {
        base._IntegrateForces(state);
        TeleportOnScreenExit(state);
        MaintainSpeed();
        HashSet<Vector2> nodesInPerception = GetNodesInPerception();
        List<Vector2> closest = GetClosestPoints(nodesInPerception, 1);
        Evade(closest, state);
    }

    private void Evade(List<Vector2> closest, Physics2DDirectBodyState state)
    {
        closest.ForEach(node =>
        {
            var distanceToNode = Position.DistanceTo(node);
            if (distanceToNode < EvasionDistance)
            {
                var angle = GetAngleTo(node);
                state.AngularVelocity = (-angle) * (1 / (distanceToNode / 2)) * Torque;
            }
        });
        state.LinearVelocity = new Vector2(MinSpeed, 0).Rotated(Rotation);
    }

    private List<Vector2> GetClosestPoints(HashSet<Vector2> nodesInPerception, int amount)
    {
        List<Vector2> closest = new List<Vector2>();
        if (nodesInPerception.Count > 0)
            closest = nodesInPerception.OrderBy(node => Position.DistanceTo(node)).Take(amount).ToList();

        return closest;
    }

    private HashSet<Vector2> GetNodesInPerception()
    {
        var setOfColliders = new HashSet<Vector2>();
        RayCasts.ForEach(rayCast =>
        {
            if (rayCast.IsColliding())
                setOfColliders.Add(rayCast.GetCollisionPoint());
        });
        return setOfColliders;
    }

    public override void _Draw()
    {
        base._Draw();
        if (Chosen)
        {
            DrawCircle(new Vector2(), perceptionRadius, vis_color);
            float i = 0;
            while (i < 2 * Mathf.Pi)
            {
                if (IsInVisibleArea(i))
                {
                    DrawLine(new Vector2(0, 0), new Vector2(0, -perceptionRadius).Rotated(i), new Color("#ff8888"), 1);
                }
                i += radStep;
            }
        }
    }

    private void TeleportOnScreenExit(Physics2DDirectBodyState state)
    {
        var xform = state.Transform;
        var screensize = GetViewportRect().Size;
        if (xform.origin.x < 0)
            xform.origin.x = screensize.x;
        if (xform.origin.x > screensize.x)
            xform.origin.x = 0;
        if (xform.origin.y < 0)
            xform.origin.y = screensize.y;
        if (xform.origin.y > screensize.y)
            xform.origin.y = 0;

        state.Transform = xform;
    }

    private void MaintainSpeed()
    {
        if (LinearVelocity.Length() < MinSpeed)
            AppliedForce = new Vector2(MinSpeed, 0).Rotated(Rotation);
        else
            AppliedForce = new Vector2();
    }
}
```

Answer 1

1. Divide your boids and the objects they need to perceive into a spatial partition, so you only ever need to examine a small number of objects in a small number of cells.

2. Instead of sweeping a fan of rays, cheat. Use the spatial partition to find candidate closest objects, then fire a single ray at the best candidate to confirm whether it's visible.

   This both massively reduces your number of (potentially expensive) rays to check, and also helps ensure you don't miss objects that fit between two rays of your fan.

3. Think of the work of updating each boid (or every boid in each partition cell) as a job. You can then divide those jobs between any number of worker threads.

   You can do this by having a single queue that each worker thread pulls from once it's finished its previous job (easier for load-balancing so all threads are kept busy), or a queue for each worker where you have some centralized logic for divvying-up the work (easier for tuning data locality and minimizing cache conflicts)

   This lets you tune the number of threads to what the hardware handles well, separate from the number of boids/cells. More boids or more cells just means a longer queue. Having just a few threads minimizes the overhead of spinning them up / shutting them down, and switching between them. Many solutions will keep a "thread pool" of such workers around as long-lived, general-purpose resources so they're ready to go on demand. There's such a pool in the C# .Net runtime you can tap into with a parallel for, as one example.

4. Where you can, avoid creating new reference types like lists inside your hot inner loop. This involves allocating memory and garbage collection book-keeping, which slow down your code. And the garbage eventually piles up and forces the garbage collector to run, taking up more time. Instead, see of you can re-use one set of book-keeping data structures per thread.