Flock 'n' Roll: Boids and Quadtrees

19th June 2023

Simulations such as the boids algorithm provide fascinating insights into the astonishing complexity that can emerge from deceptively straightforward rules. 

The boids algorithm, developed by Craig Reynolds, simulates the collective behavior of a flock of boids and consists of three basic rules: 

1. Separation (avoiding collisions with nearby flockmates by maintaining a certain distance)

2. Alignment (matching the average direction of nearby flockmates)

3. Cohesion (moving towards the center of mass of nearby flockmates)

Despite these simple guidelines, the simulation demonstrates intricate patterns and behaviors reminiscent of real-life bird flocks. This phenomenon highlights the concept of emergence, where complex global behavior emerges from the interactions of individual agents following local rules. Such simulations serve as powerful tools for studying complex systems and understanding how simple interactions can give rise to sophisticated collective behavior in various domains, from nature to social dynamics. They offer valuable insights into the fundamental principles underlying the dynamics of complex systems and inspire researchers to explore new avenues of study and application.

One domain where the principles of distributed computing, mesmerizing patterns, and swarm intelligence converge is in the study of self-organizing systems. These systems, whether natural or artificial, exhibit fascinating emergent behaviors that arise from the interactions of numerous decentralized entities. Swarm intelligence, a collective behavior exhibited by social insect colonies, fish schools, and bird flocks, serves as a rich source of inspiration for designing efficient algorithms and optimizing complex tasks. 

This sparsity lends itself to distributed computing - allocating computing power unevenly for more efficient utilization. By dividing tasks into smaller subtasks and assigning resources based on computational requirements, distributed computing enables parallel processing and improved system performance. This approach is particularly beneficial when computational workloads are unevenly distributed, allowing for optimized resource allocation and faster execution. Additionally, dynamic load balancing techniques can further enhance efficiency by adapting resource allocation in real-time. Overall, distributed computing optimizes the allocation of computing power, resulting in faster and more effective processing of complex computational tasks.

A quadtree is a data structure used to efficiently store and retrieve spatial data in a two-dimensional space. It is particularly useful for problems involving spatial partitioning, collision detection, and range queries. The name "quadtree" comes from the fact that the structure recursively divides the space into quadrants.

At its core, a quadtree is a tree where each node represents a rectangular region in the space. The root node represents the entire space, and it is recursively subdivided into four child nodes as illu, each representing a quadrant of the parent region. This subdivision continues until a certain condition is met, such as a maximum number of elements allowed in a region or a minimum size of a region.

When inserting an element into a quadtree, the tree is traversed recursively starting from the root node. At each level, the appropriate child node is determined based on the element's position. If the child node does not exist, it is created. This process continues until a leaf node is reached, where the element is stored.

When performing a search or a query in a quadtree, the tree is traversed recursively as well. At each level, the current region is compared with the search criteria, and the appropriate child nodes are explored or pruned based on this comparison. This way, the search is focused on the regions of interest and skips irrelevant regions leveraging existing tree search algorithms. By dividing the space into quadrants, a quadtree provides a hierarchical representation of the spatial data, enabling efficient insertion, retrieval, and search operations.

This can be applied to the boids simulation to query the neighbouring boids in the visual range of any boid to efficiently search the dataset.

But this is a versatile idea in computer science and can be applied extensive. Broadening the same idea, we can consider how we could apply this idea in 3D. One popular approach is to consider voxels, a kind of primitive representation of volumetric data analogous to pixels for 2D. In this way we can construct an octree which subdivides a cube into 8 equal child voxel regions of space. This permits us to query the data structure in much a similar fashion and benefit from the spatial sparsity of the data similar to the quadtree. However the benefits to this approach is multifold in 3D as compared to 2D. Modern day applications in rendering save significant computation and allow for realtime representations, which is often far more demanding than 2D use cases and merits more optimisation tricks to squeeze as much performance as possible.

 One benefit of the hierarchical based structuring that this approach lends itself to is the idea of LoDs (Level of Details). This is a common technique employed in order to save computation by tricking the user by representing the data in an object at various resolutions based on their occlusion and distance from the viewport. One can notice LoDS being used in the modern graphics pipelines for simulations, video games, and other graphics intensive tasks that need to remain performant. The core premise of this technique is to render information with higher resolution and detail when larger and closer to the camera and vice versa. This way we can reserve high resolution computation and detail to large parts of the render target. The tree representation facilitates this approach by providing an easily accessible and compact data structure for such use cases.

Using this method we can also greatly increase the resolution of our 3D data representations of space by leveraging sparsity. This is particularly relevant in structured and ordered data which can make the most of the add-as-you-need mentality of the octree while adding the least memory cost. One fundamental paper from 2010, Efficient Sparse Voxel Octree, summarises how they were able to record a model at the staggering resolution of just 5mm and rendered only 2.7GB of ram. Keep in mind this is running on hardware from the 2010s where we have to consider the exponential growth of computing power and memory. This technique is becoming more and more relevant particularly as we explore the growing world of AI and the meta-verse which will need far more easy and efficient ways of capturing the real world - imagine what we are capable of storing now with current computers and technology! Such innovations bridge the gap between the real and virtual worlds. In 100 years technology will improve 100 fold, but with ingenuity technology can accelerate progress instantly

This approach has been used by game programmers to increase the efficiency of their games and squeeze the most out hardware. One such innovation was with the use of BSP trees (binary spatial partitioning tree) by legendary programmer John Carmack in his revolutionary title Quake III. A classic which has served as a masterclass for an entire genre with movement and parameters that are still used to this day. BSP trees function similarly to octrees and voxels but instead of seperating space into cubic regions, they instead split space in half using a plane. This approach allowed Quake III to support online multiplayer and blazingly fast and responsive player and bullet collision detection.