Simulating Boids with ECSx and liveview

You can view the live simulation here

You can check the code here

Entity Component Systems for Simulations

Entity Component Systems are a new concept I have come to learn as I am learning more about Video Game development. I was then presently surprised to find that a developer Andrew Berrien had built a library, ecsx for developing entity component systems in Elixir. Naturally I had to play around with it.

In this article, I will cover what entity component systems are, how we can use them to build a boid simulation(after all, what is a game but an interactive simulation) and how we can learn to optimize simulations. We also explore ECSx and ECSx Dashboard. All references used are at the end.

What are Entity component systems??

They are an architectural pattern often used in video game development. They allow for re-usability by separating data from behavior. It is a pattern that obeys the "composition over inheritance principle"

ECS is an architecture for building real-time games and simulations, wherein data about Entities is stored in small fragments called Components, which are then read and updated by Systems.
~Mike Binns, ecsx README.md

Entities

These represent a thing in a video game. A distinct object representing an actor in a simulated space. For instance, if we are playing flappy bird, the bird would be an entity.

Entities have no actual data or behaviors.

Components

They are data types consisting of unique behavior assigned to an entity. They are re-usable modules that are attached to entities, providing behavior, functionality and appearance forming an entity.

In our flappy bird example, some components would be a y_coordinate. When attached to a bird entity we know how high on the screen the bird is.

Systems

Systems provide the logic that operates on the components.

For instance, in our flappy bird example, a jump system would update the y_coordinate of the bird when a click occurs.

Putting it all together

• System : This listens to outside events and publishes updates to the components.
• Components : They listen to the system events and update their state
• Entities: They gain behavior through changes in their associated components.

ECSx

The best intro I could give you for ecsx would be for you to watch Andrew Berrien's talk at ElixirConfUS 2023.

The highlights are as follows:

1. Entities within ecsx are conceptual.

2. Components and Systems have generators you can use
   

   mix ecsx.gen.component component_name component_type
   mix ecsx.gen.system system_name
   

3. There is a manager that controls initialization components, and which components and systems are known to the program

4. Tags are a special type of component that do not have a type.

Boids and our simulation.

Craig Reynolds introduced the Boid algorithm in 1986. It is a computational model that simulates flocking behavior based on 3 rules; separation, alignment and cohesion. It have since been used widely in computer graphics and robotics to model flocking and swarming behavior.

To design a boids simulation with ecsx, we need to define our components and systems. We will have 4 systems, separation, cohesion, alignment and movement. With regards to components, we need to consider that we will require to do a lot of 2d vector manipulation. As such, most of our components will have an x component and a y component. For instance, Velocity will be split into 2 components XVelocity and YVelocity.

The reason for this split is that ecsx only allows a small subset of types for the components.

From the internal documentation of the library

The type of value which will be stored in this component type. Valid types are: :atom, :binary, :datetime, :float, :integer

But this is ok, because we can build helpers that make it easier to work with these separate components.

Further, we also define a small utility to assist with some common calculations. We will call this utility Vector, because it helps us with Vector calculations.

Designing the systems

We have 4 systems defined, movement, cohesion, separation and alignment. The systems cohesion, separation and alignment systems will update the x and y components associated with those systems. For instance x_cohesion and y_cohesion are updated by the cohesion systems and so forth.

The movement of a boid is defined by the sum of the result of these systems. The purpose of the movement system is to that sum these results and update the x and y position components.

Alignment System

Alignment force helps the boids coordinate their direction with nearby boids. It encourages the boids to match the average velocity of their closest neighbors ensuring the group moves in a unified manner.

1. First we check if there are any neighbors within the alignment radius, if not the force is zero
2. Sum all the neighbors' velocity vectors and average them to determine the group's general movement direction
3. Instead of directly setting the velocity to the average, we subtract the boid's current velocity from it, creating a smooth transition instead of an abrupt change.

Cohesion System

The cohesion force ensures that boids stay close to their group, preventing them from drifting apart. It calculates the center of mass of the nearby boids and applying a force that pulls the boids towards this center

1. We check if there are any neighboring boids. If not the force is set to a zero vector
2. Average the position of all nearby boids to find the center of mass of the local group
3. The boid then moves toward this center helping it stay within the flock.

Separation System

Prevents boids from colliding with each other by making them steer away from nearby neighbors. We calculate the this by tracking the closest boids within a certain radius and calculate a repulsion force based on their distances.

1. The closer a neighboring boid is, the stronger the repulsion force should be.
2. The separation_intensity is a parameter that follows a hyperbolic function of the form f(x) = a/x which means that as the distance decreases, the force increases.
3. The repulsion forces from all the neighbors are summed and averages ensuring smooth movement instead of abrupt changes in direction.

Movement System

We define weights to the 3 other forces, cohesion, separation and alignment. These allow us to provide greater control over their combined effect. After weighting, each force is added to the boid's velocity vector.

Once the velocity is updated, the boid's position is recalculated. It's heading is adjusted to align with the velocity vector. We compute the orientation angle using atan2.

The ECSx Manager.

Our manager is responsible for the startup state of the boids. According to the docs

This module holds three critical pieces of data - component setup, a list of every valid component type, and a list of each game system in the order they are to be run.

Our manager startup function will look like this

def startup do
    for _boid <- 1..@number_of_boids do
      entity = Base.encode16(:crypto.strong_rand_bytes(16), case: :lower)

      Boids.Components.BoidEntity.add(entity)
      Boids.Components.XCoord.add(entity, Enum.random(100..1400) * 1.0)
      Boids.Components.YCoord.add(entity, Enum.random(100..900) * 1.0)
      Boids.Components.Width.add(entity, 7.5)
      Boids.Components.Height.add(entity, 15.0)
      Boids.Components.Heading.add(entity, 360.0)
      Boids.Components.XVelocity.add(entity, Enum.random([-1, 1]) * 1.0)
      Boids.Components.YVelocity.add(entity, Enum.random([-1, 1]) * 1.0)
      Boids.Components.XCohesion.add(entity, 0.0)
      Boids.Components.YCohesion.add(entity, 0.0)
      Boids.Components.XAlignment.add(entity, 0.0)
      Boids.Components.YAlignment.add(entity, 0.0)
      Boids.Components.XSeparation.add(entity, 0.0)
      Boids.Components.YSeparation.add(entity, 0.0)
    end
  end

We randomize the starting position to be random within our screen viewport. We also randomize our velocities.

Showing the boids

To render our boids, we will use phoenix liveview with SVG graphics.

def render(assigns) do
    ~H"""
    <div class="w-full p-4 bg-gray-800 h-screen border rounded-md border-black">
      <div class="w-full flex items-center">
        <p class="w-full text-white text-center text-2xl">BOIDS</p>
      </div>

    <!-- Render the Boids ViewFrame -->
      <div class="flex items-center justify-around">
        <svg version="1.1" width="1500" height="900" xmlns="http://www.w3.org/2000/svg">
          <rect width="100%" height="100%" fill="black" />

          <%= for {height, l_position, r_position} <- @boids do %>
            <% [{h_1, h_2}, {l_1, l_2}, {r_1, r_2}] = [height, l_position, r_position] %>
            <polygon
              points={"#{h_1},#{h_2} #{l_1},#{l_2} #{r_1},#{r_2}"}
              fill={random_fill()}
            />
          <% end %>
        </svg>
      </div>
    </div>
    """
  end

Each component height, l_position and r_position all have an x,y component. These will be used to render the 3 vertices of a triangle. The boids will also have random colors for now.

Performance optimizations

As it stands, there are 2 optimizations I am considering.

1. Hash Partitioning
2. Using Nx to perform vector math.

Hash Partitioning

Instead of calculating the forces separation, cohesion and separation for the show system, we can divide the viewport into quadrants and calculates forces for the boids in those quadrants.

Using Nx

Numerical Elixir is optimized for faster mathematical computation in elixir. Right now I am doing Vector math with my own small vector module

Nx would do the math faster, however, in testing, I found that it actually increases system latency.

Benchmarking

For benchmarking, we will render 50 boids on a view-port of 1500x1000 px. We use ECSx-live-dashboard to check performance of the systems.

First we look at performance without hash partitioning and without using Nx.

Next we check how the boids perform with hash partitioning. We use 81 partitions

Finally we check performance with Nx and no hash partitioning. The Nx utility used can be found here

Discussion

Well, none of my optimizations performed better, which is OK. It just means there is room for improvement. The first implementation appears to be the best performing one.

I find that the hash partitioning makes the boids roughly align along the partition edges

Further, I think the reason for terrible performance when using Nx, is that I am not using the correct functions. Perhaps using broadcast capabilities of Nx might be a better fit.

Another optimization might be combining both Nx and hash partitioning.

Conclusion

There is a lot more work to be done to make the system performance manageable.

I think ECSx is very very neat for what it offers. It is simple to setup and understand. Further, Nx, while primarily for machine learning, is still an amazing library fr when you need high performance calculations.

Liveview is still a work of art every time I use it. It is simple and gets more intuitive with practice.

In the github repo, I have separate branches for hash_partitioning and nx optimisations.