Godot Version
4.2.2
Question
I’m currently trying to learn GDscript and have been developing a simulation of boids to cut my teeth a bit.
Long story short, after achieving OK results with each boid detecting nearby boids via the Godot Physics Engine (somewhat stable with up to 350~ boids), I’m wanting to try a different approach for increased performance.
I’m trying to implement a method where every boid’s position vector is stored in a two-dimensional array, as to create a ‘grid’ of Vector2s. Here’s an example of the unsorted grid with the positions 16 Boids (4 rows x 4 columns):
UNSORTED:
[(1199, 864), (1259, 73), (1773, 77), (791, 504)]
[(1259, 73), (1773, 77), (791, 504), (589, 236)]
[(1773, 77), (791, 504), (589, 236), (1144, 1016)]
[(791, 504), (589, 236), (1144, 1016), (1869, 412)]
For how I want my boids to see each other without looping through every single other boid, I need to perform a custom sort on this array so that positions that are closest to (0, 0) are furthest top-left, positions that are further to the right (i.e have a larger x) are placed further in the row, and positions that are further down (i. e have a larger y) are placed lower in the column.
For example, in a 4x4 grid, the boid in the most left and uppermost position
would be at grid[0][0], and the boid in the most right and lowest position would be at grid[3][3]
As to how to create the custom sorting algorithm, I’m a bit lost. Any recommendations and help would be greatly appreciated; as I’m trying to make a simulation with as many boids as possible, an algorithm with the lowest complexity possible is necessary.
Here are two of the research papers I’ve been referencing if anyone would like further context:
https://vanhunteradams.com/Pico/Animal_Movement/Boids-algorithm.html