Semeion

Sep 26, 2020 • edited Oct 09, 2022 • 9 minutes to read

This is an overview of a project I enjoyed working on over the past few months, which is now in a state that I consider good enough to be used for a toy kind of project.

semeion is a small Rust library that allows you to write simulations that run in a 2D (torus ) environment, well suited for cellular automata simulations or zero-player games .

The purpose of this library is to try to generalize many of the common concepts and components that you may find yourself writing when working on these type of projects, allowing you to focus especially on the logic of your program.

As such, semeion defines two mayor components: the Environment data structure (the engine) and the Entity trait.

The Environment

The Environment is a data structure that models a 2D unbounded plane of any user-specified integer dimension (where its rectangle bounds wrap onto themselves).

The geometry is then divided into a set of square tiles, each of the same size, that represents the possible discrete locations where all the entities are located (some entities may transcend the concept of location and not be bound to a specific tile).

Besides representing the world where all the entities exist, the Environment is also the engine that gives them life. Your simulation will proceed from generation zero until your logic determines when the simulation can be considered over. At each iteration, all the entities will be called automatically to perform the task you assigned them and will be automatically removed from the environment according to their lifetime. Only after all the entities finish their task (or an error is raised), the Environment can proceed to the next generation†.

The idea is to initialize the Environment with a set of entities that represent the initial population, to then let the engine move forward to the next generation until the simulation is over:

use semeion::{Environment, Error, Size};

/// The width the environment.
const WIDTH: f32 = 800.0;

/// The height of the environment.
const HEIGHT: f32 = 800.0;

/// The length of each environment grid tile.
const SIDE: f32 = 10.0;

/// The maximum number of generations before terminating the simulation
/// due to timeout.
const MAX_GENERATIONS_COUNT: u64 = 10_000;

fn main() -> Result<(), Error> {
    let dimension = env_size().to_dimension(SIDE);
    let mut env = Environment::new(dimension);
    env.insert(Box::new(Ant::new(rand::random(), dimension.center())));

    while !is_simulation_over() {
        if env.nextgen()? > MAX_GENERATIONS_COUNT {
            panic!("Timeout!");
        }
    }

    println!("Simulation over after {} generations", env.generation());
    Ok(())
}

/// Gets the size of the environment.
fn env_size() -> Size {
    Size {
        width: WIDTH,
        height: HEIGHT,
    }
}

/// Returns true only if the simulation is over.
fn is_simulation_over() -> bool {
    false
}

However, the above code cannot compile until we introduce the second main component of the semeion library: the Entity trait.

† This concept is not unique to semeion, in fact you can find it in a lot in optimization problems solved with genetic algorithms .

The Entity trait

The Entity is a trait that can be implemented by the user of this library to define the behavior (and optionally the shape) of each entity kind.

Each entity must in fact have an unique ID (unique for all the entities that currently exist in the environment) and a kind, which is user defined and allows to group entities into different sets.

Besides these mandatory fields, a user Entity can define several optional attributes by simply implementing the Entity methods. In particular, any single entity may or may not have the following:

  • Location: the location within the environment that identifies the tile where the entity is positioned.
  • Scope: the radius of influence, i.e. the portion of the environment that an entity can see and interact with. The bigger the scope, the bigger this portion of the environment (Neighborhood) is.
  • Lifespan: the remaining lifespan of the entity.
  • State: a user defined state that can represent additional metadata.

Moreover, any entity can define its behavior by implementing the following methods:

  • observe(Neighborhood): allows the entity to observe and record its surrounding environment (according to its scope of influence).
  • react(Neighborhood): allows the entity to take an action according to its surrounding environment.
  • offspring() -> Offspring: allows the entity to release its offspring into the environment at each generation.
  • draw(Context): allows drawing the entity using the user-provided graphics context type.

Now that we have most of the Entity information, we can start by defining a new entity:

use semeion::{entity, Entity};

/// The simulation will not draw any graphics for now.
type GraphicsContext = ();

#[derive(PartialEq, PartialOrd, Eq, Ord)]
enum EntityKind {
    Ant,
}

struct Ant {
    id: entity::Id,
    location: Location,
}

impl Ant {
    fn new(id: entity::Id, location: impl Into<Location>) -> Self {
        Self {
            id,
            location: location.into(),
        }
    }
}

impl<'a> Entity<'a> for Ant {
    type Kind = EntityKind;
    type Context = GraphicsContext;

    fn id(&self) -> entity::Id {
        self.id
    }

    fn kind(&self) -> Self::Kind {
        EntityKind::Ant
    }

    fn location(&self) -> Option<Location> {
        Some(self.location)
    }
}

And now we can initialize the environment with our entity:

let mut env = Environment::new(dimensions);
env.insert(Box::new(Ant::new(rand::random(), dimension.center())));

The only thing to point out for now is the presence of that lifetime 'a, which needs to be specified when implementing the Entity trait, since it will allow the propagation of the lifetime bound to the Offspring of the Entity without requiring a 'static lifetime. Please note that this lifetime bound does not apply to mutable references, since they cannot be copied without violating uniqueness (aliasing).

Defining the behavior of entities

At this point, we are finally able to focus on our entities logic and to do so we can define their behavior by implementing some of the remaining Entity methods according to our needs.

As an example, Langton’s ant lends itself very well, because the number of entities involved is low and the rules that define their behaviors are simple. If you want to have a look at a complete example that uses semeion to implement Langton’s ant, please have a look at the semeion repository examples .

As a reminder for this example, Langton’s ant moves according to the rules below:

  • At a white square, turn 90° clockwise, flip the color of the square, move forward one unit.
  • At a black square, turn 90° counter-clockwise, flip the color of the square, move forward one unit.

We then need two different entities: the Ant (which we already partially defined), and the Cell, which can be defined similarly to the Ant, and in our case will encode the black square as the presence of a Cell in the tile, and the white square will be instead encoded by its absence (where Cells are created by the Ant by releasing its Offspring into the environment, and can be removed by the Ant according to the simulation rules):

use semeion::{entity, Entity, Lifespan, Location};

#[derive(PartialEq, PartialOrd, Eq, Ord)]
enum EntityKind {
    Ant,
    Cell,
}

struct Cell {
    id: entity::Id,
    location: Location,
    lifespan: Lifespan,
}

impl Cell {
    fn new(id: entity::Id, location: impl Into<Location>) -> Self {
        Self {
            id,
            location: location.into(),
            // the lifespan of a cell is immortal (black square), until
            // killed by the Ant (white square)
            lifespan: Lifespan::Immortal,
        }
    }
}

impl<'a> Entity<'a> for Cell {
    type Kind = EntityKind;
    type Context = GraphicsContext;

    fn id(&self) -> entity::Id {
        self.id
    }

    fn kind(&self) -> Self::Kind {
        EntityKind::Cell
    }

    fn location(&self) -> Option<Location> {
        Some(self.location)
    }

    fn lifespan(&self) -> Option<Lifespan> {
        Some(self.lifespan)
    }

    fn lifespan_mut(&mut self) -> Option<&mut Lifespan> {
        // the lifespan of the Cell can be affected by the Ant behavior
        Some(&mut self.lifespan)
    }
}

Now that we have defined the Cell entity, we can proceed by implementing the Ant behavior:

use semeion::{entity, Entity, Lifespan, Location, Neighborhood, Offspring, Scope};

struct Ant<'a> {
    id: entity::Id,
    location: Location,
    // the Ant offspring can contain a new Black cell
    offspring: Offspring<'a, EntityKind, GraphicsContext>,
}

impl<'a> Ant<'a> {
    fn new(id: entity::Id, location: impl Into<Location>) -> Self {
        Self {
            id,
            location: location.into(),
            offspring: Offspring::default(),
        }
    }
}

impl<'a> Entity<'a> for Ant<'a> {
    fn lifespan(&self) -> Option<Lifespan> {
        // The lifespan of the Ant is infinite.
        Some(Lifespan::Immortal)
    }

    fn scope(&self) -> Option<Scope> {
        // The Ant can only see the tile it's currently in, it has no
        // scope beyond it.
        Some(Scope::empty())
    }

    fn react(
        &mut self,
        neighborhood: Option<Neighborhood<Self::Kind, Self::Context>>,
    ) -> Result<(), Error> {
        // given the scope of the Ant, we expect the seeable portion of the
        // environment to be just the tile where the Ant is currently
        // located
        let mut neighborhood = neighborhood.unwrap();
        let tile = neighborhood.center_mut();
        // the tile in question can either be BLACK or WHITE, we encode this
        // information with a Cell entity or no entity respectively
        let mut entities = tile.entities_mut();
        let cell = entities.find(|e| e.kind() == EntityKind::Cell);

        if let Some(black_cell) = cell {
            // if the cell is BLACK, we flip its color by "killing" the
            // entity reducing its lifespan to 0 and move left
            debug_assert_eq!(black_cell.location(), self.location());
            let lifespan = black_cell.lifespan_mut().unwrap();
            lifespan.clear();

            // update ant location
            self.turn_left_and_move_forward();
        } else {
            // if the cell is WHITE, we flip its color by creating a new
            // entity as offspring for the next generation, and move right
            let black_cell = Cell::new(rand::random(), self.location);
            self.offspring.insert(Box::new(black_cell));

            // update ant location
            self.turn_right_and_move_forward();
        }

        Ok(())
    }

    fn offspring(&mut self) -> Option<Offspring<'a, Self::Kind, Self::Context>> {
        // release the offspring (if any) into the environment
        Some(self.offspring.drain())
    }
}

Final thoughts

At the time of writing, semeion is, as stated above, in a good enough state to be introduced to the world, but not in a final state and never will be in a perfect one. The whole point of this library is to let you enjoy writing your own logic, without having to rewrite “the wheel of cellular automata” and trying to do so by providing “high level” and generic enough interfaces that are relatively simple to use in Rust.

Performance wise, I’ve never had issues with the library, which also provides an optional parallel feature to run your simulations while exploiting multi-threading. Nevertheless, there are definitely more performant architectural patterns such as the Entity Component System , and if you find yourself in need of such performance, please have a look at other more mature libraries, like Bevy or Amethyst .

If you want to leave some feedback, or contribute to the project, please do so by opening an issue or a MR in the semeion repository , I’ll be glad to help or discuss it as the time allows it.

 gliderkite @gliderkite gliderkite@gmail.com

Formicarium