In my continued efforts to learn and experiment with Rust, I decided to create a 3d cellular automata emulator. This idea was heavily inspired by watching tantan's video on his version. It is a super fun video outlining his experience building one. If you haven't watched it, I would check it out!

This is the third project I have used bevy with (second on this blog). I've really enjoyed my time using it, and the crate and the various plugins user's have written for it have made this process much easier than it otherwise could have been.

Cellular automata, also known as cellular automation, or one of a million different names, is a model of computation that involves emulating cellular life. The idea was first made massively popular by Conway's Game of Life. When first exploring cellular automata, I was blown away by the massive community behind Conway's Game of Life, but even more so by the universal turning machines people have created inside of the game.

Conway's Game of Life is played in 2-dimensional grid. Each cell in the grid is a metaphor to a cell in real life and exists in two states, either alive or dead. Alive cells surrounded by 2 or 3 other live cells survive into the next step while any dead cell surrounded by three live cells comes to life. There are many variations that can be made to the game, mostly by tweaking the cells required to live or die.

Three-dimensional cellular automata follows the same principals as two-dimensional cellular automata except it is played in three dimensions (shocking).

There are different ways for evaluating the number of neighbors a cell has at any moment. In our case, we will consider any cells touching, even corners, to be neighbors. For example, if the cell in question is located at position (0, 0, 0), then the following cells are all considered neighbors.

let neighbors = [
    (-1, -1, -1),
    (0, -1, -1),
    (1, -1, -1),
    (-1, 0, -1),
    (0, 0, -1),
    (1, 0, -1),
    (-1, 1, -1),
    (0, 1, -1),
    (1, 1, -1),
    (-1, -1, 0),
    (0, -1, 0),
    (1, -1, 0),
    (-1, 0, 0),
    (1, 0, 0),
    (-1, 1, 0),
    (0, 1, 0),
    (1, 1, 0),
    (-1, -1, 1),
    (0, -1, 1),
    (1, -1, 1),
    (-1, 0, 1),
    (0, 0, 1),
    (1, 0, 1),
    (-1, 1, 1),
    (0, 1, 1),
    (1, 1, 1),
];

This means any cell can have a total of 26 different neighbors, or including the possibility of 0 neighbors, 27 different neighbor counts.

For the simple cellular automata we will be building, the neighbors count will be the basis for our rules.

The emulator is actually very simple. First, we have a 3d world we create with bevy.

fn main() {
    let cell_locations: CellLocations = [false; CELL_LOCATIONS_SIZE];
    let game_rule: GameRule = GameRule::default();
    let paused: Paused = true;
    App::new()
        .add_plugins(DefaultPlugins)
        .add_plugin(CustomMaterialPlugin)
        .add_plugin(NoCameraPlayerPlugin)
        .add_plugin(EguiPlugin)
        .add_startup_system(setup)
        .add_system(cell_location_updater.with_run_criteria(FixedTimestep::step(0.125)))
        .add_system(ui.after(cell_location_updater))
        .add_system(feed_cells)
        .insert_resource(cell_locations)
        .insert_resource(game_rule)
        .insert_resource(paused)
        .run();
}

You will notice we add the NoCameraPlayerPlugin from the bevy_flycam crate. This allows us to move the camera with keys. We also add the EguiPlugin this gives us an easy to use gui interface. It is an absolutely awesome project. Check it out here. The DefaultPlugins are standard for most bevy projects.

The CustomMaterialPlugin is a compute shader that runs on the gpu and "instances" our cell. The code is taken directly from Bevy's instancing example. I'll discuss why we use this plugin later.

We also add a number of resources and systems which we will cover below.

There are three different resources we add: cell_locations, game_rule, and paused. The paused resource is simply a boolean that stops the cell_location_updater from running (more on that later).

The game_rule and cell_locations are covered below.

const GAME_SIZE: f32 = 100.;
const CELL_LOCATIONS_SIZE: usize = (GAME_SIZE * GAME_SIZE * GAME_SIZE) as usize;
let cell_locations: CellLocations = [false; CELL_LOCATIONS_SIZE];

While we can easily add new entities and components in bevy, what we need is a way to check whether an entity (cell) exists at a specific location. Keeping an array of every possible cell location, and having the specific location be either true or false depending on whether a cell lives there is a very easy way to do this. You might notice, while the game exists in three dimensions, the array is only 1 dimensional. We will translate between the third and first dimension as this simplifies some of our calculations.

It should also be noted this method only makes sense for a fixed-size emulator space. If we were planning on allowing the cells to grow in any direction without limit, this method would not work.

In our case, you can see we have restricted the GAME_SIZE to 100. Meaning cells can grow in a three-dimensional grid 100x100x100 allowing a total of 1 million cells.

struct GameRule {
    neighbors_to_surive: [bool; 27],
    neighbors_to_spawn: [bool; 27],
    spawn_noise_count: i32,
    spawn_noise_radius: i32,
    color_from: Color,
    color_to: Color,
}

impl GameRule {
    pub fn default() -> Self {
        let neighbors_to_surive = Self::to_dense_array(&[5, 6, 7, 8]);
        let neighbors_to_spawn = Self::to_dense_array(&[6, 7, 9]);
        GameRule {
            neighbors_to_surive,
            neighbors_to_spawn,
            spawn_noise_count: 50000,
            spawn_noise_radius: 75,
            color_from: Color::YELLOW,
            color_to: Color::BLUE,
        }
    }

    pub fn to_dense_array(vc: &[u8]) -> [bool; 27] {
        let mut ar = [false; 27];
        for i in vc {
            ar[*i as usize] = true;
        }
        ar
    }
}
let game_rule: GameRule = GameRule::default();

The game_rule specifies the rules of our game and some variables we want to store when using the gui interface we create later.

The neighbors_to_surive and neighbors_to_spawn are boolean arrays of all possible neighbor counts a cell could have. A cell will spawn or die in accordance with the indices set in these arrays. More on the implimentation of this below.

There are four systems we specify: setup, cell_location_updater, ui, and feed_cells.

fn setup(
    mut commands: Commands,
    mut meshes: ResMut<Assets<Mesh>>,
    mut cell_locations: ResMut<CellLocations>,
) {
    commands.spawn().insert_bundle((
        meshes.add(Mesh::from(shape::Cube { size: CELL_SIZE })),
        Transform::from_xyz(0.0, 0.0, 0.0),
        GlobalTransform::default(),
        InstanceMaterialData(Vec::new()),
        Visibility::default(),
        ComputedVisibility::default(),
        NoFrustumCulling,
    ));

    commands
        .spawn_bundle(Camera3dBundle {
            transform: Transform::from_xyz(-70., 0., 195.).looking_at(Vec3::ZERO, Vec3::Y),
            camera_3d: Camera3d {
                clear_color: ClearColorConfig::Custom(Color::rgb(0., 0., 0.)),
                ..default()
            },
            ..default()
        })
        .insert(FlyCam);

    for t in create_random_spawn_points(1000, (0, 0, 0), 20) {
        let index = translate_location_to_index(t.0, t.1, t.2);
        cell_locations[index] = true;
    }
}

The setup is really simple system that runs once and spawns in the camera, and an entity that has the InstanceMaterialData component. More on this soon.

We also spawn in some default cells generated from our create_random_spawn_points function that takes in the number of cells to spawn, center point, and radius around the center in which to spawn cells.

fn cell_location_updater(
    mut cell_locations: ResMut<CellLocations>,
    game_rule: Res<GameRule>,
    paused: Res<Paused>,
) {
    if *paused {
        return;
    }
    let task_pool = TaskPool::new();
    let max_size = (GAME_SIZE * GAME_SIZE * GAME_SIZE) as i32;
    let chunck_size = ((GAME_SIZE * GAME_SIZE * GAME_SIZE) / 32.) as usize;
    let counts = (0..max_size).collect::<Vec<i32>>();
    let cell_changes = counts.par_chunk_map(&task_pool, chunck_size, |chunck| {
        let mut cells_to_add = Vec::new();
        let mut cells_to_remove = Vec::new();
        for i in chunck {
            let nc = get_neighbors(*i, &cell_locations) as usize;
            if game_rule.neighbors_to_spawn[nc] {
                cells_to_add.push(*i as usize);
            }
            if !game_rule.neighbors_to_surive[nc] {
                cells_to_remove.push(*i as usize);
            }
        }
        (cells_to_add, cells_to_remove)
    });

    for (cells_to_add, cells_to_remove) in cell_changes {
        for i in cells_to_add {
            cell_locations[i] = true;
        }
        for i in cells_to_remove {
            cell_locations[i] = false;
        }
    }
}

The cell_location_updater is the heart of our emulator. It maps over every cell alive and dead, and determines whether it will live or die. This uses the rules specified in the game_rule. We are using bevy's par_chunk_map to parallelize this process. I'm sure there are more efficient ways to do this, but this worked well enough for me.

We are making use of the get_neighbors function that returns values between 0 and 27. This function directly utilizes the neighbor mappings we discussed above, and is otherwise uninteresting and not worth showing.

Once we have updated our cell_locations it is time to utilize them.

fn feed_cells(
    cell_locations: Res<CellLocations>,
    game_rule: Res<GameRule>,
    mut q_instances: Query<&mut InstanceMaterialData>,
) {
    let mut instances = q_instances.get_single_mut().unwrap();
    let x: Vec<InstanceData> = cell_locations
        .iter()
        .enumerate()
        .filter_map(|(index, x)| match x {
            false => None,
            true => {
                let loc = translate_index_to_location(index);
                let distance = loc.0.abs().max(loc.1.abs()).max(loc.2.abs()) / (GAME_SIZE / 2.);
                let r =
                    (1. - distance) * game_rule.color_from.r() + distance * game_rule.color_to.r();
                let g =
                    (1. - distance) * game_rule.color_from.g() + distance * game_rule.color_to.g();
                let b =
                    (1. - distance) * game_rule.color_from.b() + distance * game_rule.color_to.b();
                Some(InstanceData {
                    position: Vec3::new(loc.0, loc.1, loc.2),
                    scale: 1.,
                    color: [r, g, b, 1.],
                })
            }
        })
        .collect();
    *instances = InstanceMaterialData(x);
}

The feed_cells system filter_maps over the cell_locations and creates a vector of InstanceData which we assign to the InstanceMaterialData component in the entity we created earlier.

We do this because the CustomMaterialPlugin that does the shader instancing queries for entites with InstanceMaterialData components, and renders an instance of the mesh on this entity for every InstanceData in the InstanceMaterialData. Sorry if that was confusing.

I'm not going to explain how the CustomMaterialPlugin does this as I'm sure I would get many of the details incorrect, what is important to know, is that we are taking advantage of Bevy's compute shaders to save ourselves from creating and destroying hundreds of thousands of different meshes. If you are curious about how it works, feel free to check out the code here as mentioned the code is taken directly from bevy's instancing example.

When I first wrote this project, I did not use a compute shader to instance the cells and instead spawned hundreds of thousands of entities with their own meshes. The frame rate was terrible and crashed as the cell count would approach 1 million. With only one entity and the instancing compute shader, we can easily emulate a million cells.

We are also lerping between the color_from and color_to in our game_rule dependent on the distance the cell is from location (0, 0, 0).

fn ui(
    mut egui_context: ResMut<EguiContext>,
    q_instances: Query<&InstanceMaterialData>,
    mut game_rule: ResMut<GameRule>,
    mut cell_locations: ResMut<CellLocations>,
    mut paused: ResMut<Paused>,
) {
    let instances = q_instances.get_single().unwrap();
    egui::Window::new("Celluar!").show(egui_context.ctx_mut(), |ui| {
        ui.label("Overview:");
        {
            let cell_count = instances.len();
            ui.label(format!("cells: {}", cell_count));
            ui.checkbox(&mut paused, "Paused");

            if ui.button("reset").clicked() {
                *cell_locations = [false; CELL_LOCATIONS_SIZE];
            }

            if ui.button("spawn noise").clicked() {
                for t in create_random_spawn_points(
                    game_rule.spawn_noise_count,
                    (0, 0, 0),
                    game_rule.spawn_noise_radius,
                ) {
                    let index = translate_location_to_index(t.0, t.1, t.2);
                    cell_locations[index] = true;
                }
            }
            let mut spawn_noise_count = game_rule.spawn_noise_count as f32;
            ui.add(
                egui::Slider::new(&mut spawn_noise_count, 1.0..=1000000.0).text("cells to spawn"),
            );
            game_rule.spawn_noise_count = spawn_noise_count as i32;

            let mut spawn_noise_radius = game_rule.spawn_noise_radius as f32;
            ui.add(
                egui::Slider::new(&mut spawn_noise_radius, 1.0..=100.0).text("raduis to spawn in"),
            );
            game_rule.spawn_noise_radius = spawn_noise_radius as i32;
        }

        ui.add_space(24.0);
        ui.label("Rules:");
        {
            color_picker(ui, &mut game_rule.color_from);
            color_picker(ui, &mut game_rule.color_to);

            ui.label("Survival Rule: ");
            ui.horizontal_wrapped(|ui| {
                for (index, mut i) in game_rule.neighbors_to_surive.iter_mut().enumerate() {
                    ui.checkbox(&mut i, format!("{}", index));
                }
            });

            ui.label("Spawn Rule: ");
            ui.horizontal_wrapped(|ui| {
                for (index, mut i) in game_rule.neighbors_to_spawn.iter_mut().enumerate() {
                    ui.checkbox(&mut i, format!("{}", index));
                }
            });
        }
    });
}

The ui is built using egui and lets us update the colors, spawn and die rules, the noise we spawn, and even pause the game.

It has made finding cool patterns and playing with the emulator very easy and enjoyable.

That is pretty much it! I apologize for the cryptic discussion around the compute shader that handles the instancing of our cells. There is currently very little documentation about it in bevy, and I'm not confident enough in my understanding to share more details.

The result is pretty awesome! There are nearly an infinite number of patters and structures that can be created inside of our simple emulator. I would encourage cloning the repo and exploring it yourself: github repo

Thanks for reading!

the repo

© 2024 Silas Marvin. No tracking, no cookies, just plain HTML and CSS.