When working on projects, you often face the decision between using existing libraries and assets (Option A) or building from scratch (Option B). Time constraints often lead to opting for Option A, but this choice comes with drawbacks. For instance, if the library doesn’t fully meet your needs, you may struggle to modify or extend it. This difficulty can arise either because the library wasn’t designed for easy extension or because it employs advanced techniques beyond your current understanding.
That’s why, given the opportunity, I lean towards Option B. Choosing this path offers numerous opportunities for learning and results in a product you fully comprehend. Consequently, extending its functionality becomes much easier.
Recently, while working on an internal project, I required flocking behavior to simulate various entities like fish, birds, or other groupings. After a quick google search that lands you on the ‘boids’ algorithm. In this devlog, I’ll delve into the process of how I achieved that by writing my own implementation.
The Boids algorithm
As mentioned earlier. A quick google search about how to achieve convincing flocking behaviour points you to the boids algorithm. After going over a couple of ready-made examples of the algorithm that were either too complicated, or too simple for my liking I decided that I wanted to make my own implementation. Before going over that journey, I’ll first explain the basics of the algorithm.
The boids algorithm, short for bird-oid object, is an algorithm that achieves realistic flocking behaviour by implementing three simple rules.
separation: steer away from boids that are close-by
cohesion: steer to move towards the average position (center of mass) of local flockmates
alignment: steer towards the average heading of neighbouring boids
Without these rules our bodies are aimless and blind. To implement these rules each boid needs to keep track of the other boids in it’s local area. On top of that each boids has an area around them that if other boids were to enter it they try to actively steer away from them to avoid collision, we call this the no-clump zone.
Separation
In order to successfully steer away from each other each boid needs to keep track of all the other boids within their no-clump zone. Based on that information we can calculate a new safe direction to move towards.
Cohesion
A bunch of boids avoiding each other doesn’t make a convincing simulation. Each boid keeps track of all the boids in their local area and calculates a local center that they try to move towards. This makes them effectively cluster together.
Alignment
Finally we add alignment to the mix. Again we take the local area, but this time we calculate an average of the forward heading of each of the boids.
Result
Besides these three simple rules there are many more variations on the algorithm possible by, for example, adding things like food sources or predator boids that want to eat the other boids. If you want to read more boids you can do so here and here.
The process
After deciding I wanted to write my own implementation I went looking for different tutorials and implementations and concocted the first version of my own boids algorithm. I based it mostly on Sebastian Lague’s tutorial and this tutorial. It worked, but it had a couple of big issues
- 🚨The performance police, came looking for me. It worked well with about a 100 boids, but after that performance started to decline rapidly. This is because each of the boids had to loop over the positions of all of the other boids to see if they fell within their local area range. For 100 boids that’s 100*100 checks. For 900 boids that’s 900*900 checks. That will quickly bring any modern computer to it’s knees.
- The boids could fly in an open space but they weren’t able to avoid obstacles like rocks and terrain.
Performance
To improve performance I decided to rewrite the entire thing and improve the performance using two key technologies: ECS and Octrees.
ECS
Around when I began our boids project, Unity launched Unity DOTS 1.0 (Data-Oriented Technology Stack). It’s like a special toolbox in Unity for making games run faster and handle more complex stuff. One of its key features is something called Entity-Component-System (ECS), which is a way of organizing game data. ECS makes it easier for the game to handle lots of characters or objects with a lot of different features without slowing down. It’s like having a super-efficient way of managing all the parts of your game behind the scenes.
In the old way of making games, most of the work happens on just one part of your computer’s brain (the CPU). But with Unity DOTS stack, I could spread out these tasks across different threads at the same time, kind of like having many workers doing different jobs all at once.
Octrees
Now that I had discovered a method to distribute my calculations more efficiently, I still faced the challenge of each boid having to check with every other boid if they were within range, leading to a significant bottleneck even with parallel processing. Enter the octree.
An octree is a way to divide 3D space into smaller chunks, like boxes inside boxes, to efficiently organize and search for objects or data in a 3D environment. Each box, or “node,” in the octree can be further divided into eight smaller boxes if it contains too many objects or if it’s too big, creating a hierarchical structure. This hierarchical organization allows for faster searches and spatial queries, as objects can be quickly located within their respective boxes without needing to check every single object in the space. Spatial partitioning, including techniques like octrees, helps optimize performance in 3D applications by reducing the number of calculations needed to determine object interactions and visibility.
As I was learning about how they functioned, I faced another decision point: should I create my own version or use one that’s already made? This time, I decided to go with an existing one because I was already trying to learn and understand a lot of new concepts. Fortunately, I stumbled upon something called “nativetrees,” which worked well with the DOTS stack.
Collision
Now that I had addressed our performance issues, the next step was to implement collision detection. While this task seemed straightforward at first, it turned out to be quite challenging. Thanks to ECS, which enables scalable and modular code, and the existing movement systems, I could integrate a collision handling system relatively easily. However, understanding the intricate calculations required for the boids to avoid obstacles was tough. My only indicators were the boids’ behavior on screen and the changing data in the inspector. Let me clarify: comprehending this kind of information isn’t easy for the human brain, at least not for mine. I struggled to see what was wrong with my avoidance calculations based solely on visual observation of the data.
Rather than persisting in a cycle of trial and error, adjusting calculations slightly each time, I opted to visualize what the boids perceived in their path and how they responded to it. I achieved this by drawing invisible “antennas,” representing their eyes, also known as raycasts. Once the boids would approach an object the lines would transition from white to red. This approach uncovered a significant error in my calculation of the raycast angles required to detect potential collisions (a silly oversight on my part). It underscored the importance of creating tools like debug visualizers for development, teaching me a valuable lesson in the process.
Conclusion
Creating my own boids algorithm taught me invaluable lessons:
- It sparked my fascination with data-oriented programming.
- I realized the significance of visualizing data for effective debugging.
- I honed my skills in writing efficient multithreaded code.
Now, we possess a versatile boids algorithm that integrates into any project and can be tailored to its requirements. Given the frequent need for wildlife simulations in MoMoLab 3D scenes, such as fish and birds, I think the extra time invested in learning new things and writing my own implementation was worth it. I’m confident I can adapt it for simulating space-ship battles as well. This drop-in package empowers us with flexibility and customization options that wouldn’t have been possible if I had opted for a preexisting library.
The main point I’m emphasizing here is the importance of maintaining an open mind when it comes to learning new things. By doing so, you might discover that you gain far more knowledge and insights than you initially anticipated.