MMORPGs PART 3: Parallel flocking behaviour in large-scale simulations
In the first post in this series, we talked about using the octree data-structure to hierarchically divide space. Each cell in an octree represents a region of space containing state that the cell is responsible for. Cells can vary by several orders of magnitude, providing a way to vary spatial granularity and the size of state allocated to a cell as needed. An octree is an ideal structure for managing simulated worlds as it provides a way to partition physical space in a way that provides efficient indexing and load balancing. In our octree implementation, each cell is located on a separate Hadean process which can be located either on the local or on a remote machine.
In order to maintain complete transparency to a user interacting with an environment built on this data structure, it’s important that behaviour of a partitioned environment remain identical regardless of how it is partitioned. We chose to build a demo using our octree implementation having two main requirements:
- Entities should be able to observe other entities in physically proximate space.
- Entities should be able to transparently migrate between cells whether they are on the same machine or not.
To this end, we constructed a demo based on flocking, using behaviour similar to that proposed by Craig Reynolds in 1991. Reynolds called the generic simulation creatures “Boids” and their movement was governed by three simple behaviours:
- Separation. Boids move in such as way as to ensure that they are a minimum distance away from other creatures in the same flock.
- Alignment. Boids observe the direction other nearby boids are travelling and align themselves to the average heading.
- Cohesion. Boids attempt to move towards to central position of other boids they can see. This ensures that flocks tend to remain together.
Such a simulation is ideal for testing our octree. For Boids to exhibit correct behaviour, they need to be aware of entities in the authoritative region of another cell, otherwise the behaviour will break down at the boundaries between cells. As Boids constantly remain in motion, they will frequently cross boundaries between octree cells, requiring the handover of state. The simulation we built can be seen in the video:
We augmented Reynold’s rules with one that restricts the Boids to a rectangular region. We also created three “species” of Boid and only apply the alignment rule when two Boids are of the same species. Hence Boids of the same species will tend to flock together. We also varied the average weight of members of each species.
As a later development, we augmented the existing rules with a rule that causes Boids to move away from Boids of other species. With this fairly simple change, we were able to introduce significantly more interesting non-linear behaviour as groups of Boids now cause other groups to be split and form isolated regions.
A Boid-like a simulation is simple to implement in the single process case, but much harder to implement in the parallel case. The distributed octree data structure an ideal choice for managing how entities are allocated to cells and determining which cells need to communicate.
In our implementation cells, in the octree maintain connections to physically proximate cells. At each time-step, cells inform each other of other entities they should be aware of. Octree cells can be different sizes, but the code that manipulates entities can be written in a way that only considers physical space. The complexity of handling dynamically changing octree cell adjacency and the complexity of managing communications with all the octree cells in physical range is hidden from client code.
In this post we looked at building a flocking simulation on top of an octree data-structure which incorporates features necessary for dynamically adapting to the distribution of simulation entities. As discussed in the previous blog post, our octree implementation permits cells of varying sizes and cell sub-division. In the future, we will explore simulations where cells need to be fused or destroyed and other issues related to achieving dynamic load balancing.
Read Part 1: Rethinking game architecture
Read Part 2: Applying data-driven design to optimize computation
Download The Cloud-Native Game Design Handbook to discover what cloud-native computing could do for your game design.