Cellular Automata Using Rust: Part III

In the second post of this three-part series, we explored entity-component-system (ECS) architecture and built a static user interface with Bevy. In this post, the finale of the three-part series, we implement the numerous systems that together drive the evolution of our elementary cellular automaton and support user interaction via the keyboard and mouse. Throughout this post, we will work exclusively in src/ecs.rs.

The evolver

We have the user interface now, but it’s a tableau — a moment in time, locked on its initial presentation. Let’s unlock it by fulfilling its raison d’être: evolution of the cellular automaton!

fn evolve(
    time: Res<Time>,
    rule: Res<AutomatonRule>,
    mut timer: ResMut<EvolutionTimer>,
    mut history: ResMut<History>,
    mut cells: Query<(&CellPosition, &mut BackgroundColor)>
) {
    if timer.is_running()
    {
        timer.tick(time.delta(), || {
            history.evolve(*rule);
            for (position, mut color) in &mut cells
            {
                *color = liveness_color(history[*position]);
            }
        });
    }
}

We’ve seen Res already, so it’s not hard to guess what ResMut is: a mutable borrow of a resource, provided to our evolve system through dependency injection.

Time is a clock resource supplied by Bevy. It tracks how much time has elapsed since its creation or previous update, which is queryable via the delta method. Bevy updates this value every frame, before running any systems in the Update schedule.

Now for the magical part! Query is effectively an iterator over all entities that possess the specified combination of components. So Bevy will pass every entity that currently has both a CellPosition and a BackgroundColor. This just so happens, by construction, to be the cells of our visual history.

So let’s break the logic down into a narrative before we dive into the individual pieces:

1. Check whether the EvolutionTimer is running. This is one of our project’s resources. We saw its registration back in our plugin setup code, but we haven’t investigated yet. We’re going to kick that can a few more paragraphs down the post, but for the moment we note that the application starts paused and toggles between paused and running when the user presses the space bar.
2. Assume that the EvolutionTimer is running. Now manually tick it by the time elapsed since the last frame, which may cause the timer to expire.
3. Assume that the EvolutionTimer is expired. Now evolve the cellular automaton in accordance with the injected rule, then update the background color of every cell to agree with its new model state. Our Query iterator here just answers 2-tuples, so we destructure them to simplify the update process.

EvolutionTimer and manual ticking

You probably won’t be surprised to discover that EvolutionTimer is just another newtype around an existing Bevy struct:

#[derive(Resource)]
struct EvolutionTimer(Timer);

Bevy timers support a duration, a repeat mode (either Once or Repeating), and a run mode (either running or paused). Like our own wrapper, a Timer must be manually "ticked" via the tick method. This gives us total freedom about how we couple any particular timer to the engine loop or wall clock. We introduce a new method to configure an EvolutionTimer for our particular circumstances.

const HEARTBEAT: Duration = Duration::from_millis(250);

impl EvolutionTimer
{
    fn new() -> Self
    {
        Self({
            let mut timer = Timer::new(HEARTBEAT, TimerMode::Repeating);
            timer.pause();
            timer
        })
    }
}

We use an inline block here to create a Timer, pause it, and embed it inside an EvolutionTimer.

impl EvolutionTimer
{
    fn is_running(&self) -> bool
    {
        !self.0.paused()
    }

    #[inline]
    fn tick(&mut self, delta: Duration, on_expired: impl FnOnce())
    {
        self.0.tick(delta);
        if self.0.finished()
        {
            on_expired();
        }
    }
}

Now we see that is_running just tests whether the internal Bevy timer is paused. Calling tick just delegates to the eponymous method of the internal timer and conditions execution of the supplied closure on the internal timer having exhausted its allotted duration.

Toggling the EvolutionTimer

Toggling the EvolutionTimer is pretty straightforward, so there’s really nothing interesting to say about it:

impl EvolutionTimer
{
    fn toggle(&mut self)
    {
        match self.0.paused()
        {
            true => self.0.unpause(),
            false => self.0.pause()
        }
    }
}

Enabling the user to toggle the EvolutionTimer is much more interesting:

fn maybe_toggle_instructions(
    keys: Res<Input<KeyCode>>,
    mut instructions: Query<&mut Style, With<Instructions>>,
    mut timer: ResMut<EvolutionTimer>
) {
    if keys.just_pressed(KeyCode::Space)
    {
        timer.toggle();
        let style = &mut instructions.single_mut();
        style.display = match style.display
        {
            Display::Flex => Display::None,
            Display::None => Display::Flex,
            Display::Grid => unreachable!()
        };
    }
}

There are two new things in the signature:

1. Input is a system resource that provides access to "press-able" input, like a keyboard, mouse button, or gamepad. The type parameter, KeyCode, corresponds to cooked keyboard input. I say "cooked" because these are not the raw keycodes obtained from the operating system, but rather Bevy’s cross-platform abstractions of key events. We can ask an Input whether it is "just pressed" (since the last frame), "pressed" (over the course of multiple frames), or "just released" (since the last frame).
2. With acts a positive filter for a Query: we want every entity that has both a Style component and an Instructions component, but we don’t need access to the Instructions component itself. Recall that Instructions was an empty marker struct, so there wouldn’t be any point to binding it locally, because there’s nothing to read and nothing to write.

The code itself is simple. When the user presses the space bar, toggle the EvolutionTimer, extract the only Style from the singleton query, and toggle the display property between Flex and None. How do we know that there’s only one Style? Construction: we only branded one entity with the Instructions label. single_mut will panic if you get this wrong, so it has the side benefit of acting as an assertion. Speaking of assertions, we call unreachable! if the old display is Grid, because this should be impossible from the structure of our code.

Toggling cell state by mouse

When the simulation is paused, we let the user toggle the cells at the bottom of the grid — the ones that represent the newest generation — by clicking on them.

const PRESSED_COLOR: Color = Color::YELLOW;

fn maybe_toggle_cells(
    timer: ResMut<EvolutionTimer>,
    mut history: ResMut<History>,
    mut interaction: Query<
        (&Interaction, &CellPosition, &mut BackgroundColor),
        (Changed<Interaction>, With<Button>)
    >
) {
    if !timer.is_running()
    {
        for (interaction, position, mut color) in &mut interaction
        {
            match *interaction
            {
                Interaction::Pressed =>
                {
                    let cell = &mut history[*position];
                    *cell = !*cell;
                    *color = liveness_color(*cell);
                },
                Interaction::Hovered =>
                {
                    *color = BackgroundColor(PRESSED_COLOR);
                },
                Interaction::None =>
                {
                    *color = liveness_color(history[*position]);
                }
            }
        }
    }
}

We have a much more complex Query here, so let’s analyze it. There are two type parameters, each a tuple. The first aggregates the target components; the second aggregates additional filters. Interaction abstracts the kind of interaction that occurred on some UI node. Changed excludes entities for which the Interaction did not change since the last time that this system ran. With<Button> ensures that only entities with the Button component will appear during iteration.

Now for the logic. We ignore mouse input when the timer is running; when the timer is running, the simulation is running, and we don’t want to inflict upon the user the frustrating experience of racing against the evolver to click the cells. We loop over all the interactions, taking appropriate action when the UI element is pressed, hovered, or vacated (Interaction::None). Respectively, this amounts to: toggling the cell between "on" and "off"; showing the bright yellow interactivity indicator; and restoring the cell to its usual state indicator upon un-hovering.

Note that we never explicitly mention the specific device here, because Interaction is from the UI element’s point of view, not the user’s or the device’s. That technically makes this mechanism device-agnostic, even though the device will usually be a pointing device like a mouse or trackpad.

Buffering a new rule

In most mathematical exercises, a cellular automaton evolves according to a single fixed rule established at the onset. But it makes for a much more appealing visual simulation to allow the user to change the rule midstream.

Before we look at the systems involved, let’s look at the data structure that supports them. It’s called AutomatonRuleBuilder. We added it as a resource from our plugin, but glossed over it completely. It’s time to put it front and center.

#[derive(Default, Resource)]
struct AutomatonRuleBuilder
{
    builder: Option<String>,
    timer: Option<Timer>
}

builder is the compositional buffer for the textual version of a user-typed rule. It transitions from None to Some when the user types the first digit of the new rule, either through the number row or the number pad. It transitions back to None when either the paired timer expires or an invalid rule is detected.

timer controls the pacing of data entry. The timer also transitions from None to Some when the user types the first digit. The timer is one-shot, but resets whenever the user enters another digit. When the timer expires, the content of the buffer is treated as complete and parsed as an AutomatonRule.

Following the same pattern that we’ve seen several times now, we also manually tick the data entry timer:

impl AutomatonRuleBuilder
{
    /// Update the [timer](Self::timer) by the specified [duration](Duration).
    #[inline]
    fn tick(&mut self, delta: Duration)
    {
        if let Some(ref mut timer) = self.timer
        {
            timer.tick(delta);
        }
    }
}

We only allow digits to be accumulated into the buffer:

const RULE_ENTRY_GRACE: Duration = Duration::from_millis(600);

impl AutomatonRuleBuilder
{
    fn push_digit(&mut self, c: char)
    {
        assert!(c.is_digit(10));
        match self.builder
        {
            None =>
            {
                self.builder = Some(c.into());
                self.timer = Some(
                    Timer::new(RULE_ENTRY_GRACE, TimerMode::Once)
                );
            },
            Some(ref mut builder) if builder.len() < 3 =>
            {
                builder.push(c);
                self.timer.as_mut().unwrap().reset();
            },
            Some(_) =>
            {
                self.builder = None;
                self.timer = None;
            }
        }
    }
}

The caller is responsible for giving push_digit an actual digit, so we assert the precondition. We install a buffer and timer if they didn’t exist already, meaning that this is the first digit that we’ve seen ever or since the last proposed new rule was accepted or rejected. If the buffer could possibly be valid after the new digit is appended, then push it and reset the timer to give the user a full quantum (600ms) to type the next digit. If the buffer would be ostensibly invalid after the push, i.e., because every valid parse would exceed the upper bound for a Wolfram code, then destroy the buffer and the timer immediately.

impl AutomatonRuleBuilder
{
    fn buffered_input(&self) -> Option<&str> { self.builder.as_deref() }
}

To access the buffered input directly, we call buffered_input. We can chain is_some to turn this into a simple check for the existence of buffered data.

Finally, we need to extract the successor rule from an AutomatonRuleBuilder:

impl AutomatonRuleBuilder
{
    fn new_rule(&mut self) -> Option<AutomatonRule>
    {
        match self.timer
        {
            Some(ref timer) if timer.just_finished() =>
            {
                let rule = match self.builder.as_ref().unwrap().parse::<u8>()
                {
                    Ok(rule) => Some(AutomatonRule::from(rule)),
                    Err(_) => None
                };
                self.builder = None;
                self.timer = None;
                rule
            }
            _ => None
        }
    }
}

We only want to parse the buffered data if the timer has just expired. We return Some only if the parse succeeds, destroying the builder and timer on our way out.

Typing a new rule

With the supporting model in place, we can now confidently proceed to an examination of the systems involved. First is accept_digit, which translates keyboard presses into buffered digits:

fn accept_digit(
    keys: Res<Input<KeyCode>>,
    mut builder: ResMut<AutomatonRuleBuilder>,
    mut next_rule: Query<&mut Style, With<NextRule>>
) {
    for key in keys.get_just_pressed()
    {
        match key.to_digit()
        {
            Some(digit) => builder.push_digit(digit),
            None => {}
        }
    }
    let style = &mut next_rule.single_mut();
    style.display =
        if builder.buffered_input().is_some() { Display::Flex }
        else { Display::None };
}

Nothing new in the signature and nothing terribly novel in the body. In short, we append a digit to the buffer and toggle the visibility of the overlay. We turn our attention momentarily to to_digit, because it involves the only trait that we are introducing in the whole project:

const NUMBER_ROW_RANGE: RangeInclusive<u32> =
    KeyCode::Key1 as u32 ..= KeyCode::Key0 as u32;

const NUMPAD_RANGE: RangeInclusive<u32> =
    KeyCode::Numpad0 as u32 ..= KeyCode::Numpad9 as u32;

trait ToDigit: Copy
{
    fn to_digit(self) -> Option<char>;
}

impl ToDigit for KeyCode
{
    fn to_digit(self) -> Option<char>
    {
        if NUMBER_ROW_RANGE.contains(&(self as u32))
        {
            match self
            {
                KeyCode::Key0 => Some('0'),
                key => Some(char::from_digit(key as u32 + 1, 10).unwrap())
            }
        }
        else if NUMPAD_RANGE.contains(&(self as u32))
        {
            let delta = self as u32 - KeyCode::Numpad0 as u32;
            Some(char::from_digit(delta, 10).unwrap())
        }
        else
        {
            None
        }
    }
}

The translation code is slightly yucky, which is why we hide it in a utility trait outside the main narrative. Key0 comes after Key9, just as it appears on the number row of the keyboard, hence the slightly weird logic in the match. But Numpad0 comes before Numpad1, so that case is simpler. We leverage the fact that KeyCode is an enum with repr(u8) to allow us to perform arithmetic on the enum discriminants. Finally, we use char::from_digit to obtain the print character that corresponds with the key press.

We also need to change the label inside the new overlay if and only if it’s visible:

fn update_next_rule(
    builder: Res<AutomatonRuleBuilder>,
    mut next_rule: Query<&mut Text, With<NextRuleLabel>>
) {
    let buffered_input = builder.buffered_input();
    if buffered_input.is_some()
    {
        let text = &mut next_rule.single_mut();
        text.sections[1].value = match builder.buffered_input()
        {
            Some(rule) if rule.parse::<u8>().is_ok() => rule.to_string(),
            _ => "Error".to_string()
        };
    }
}

We receive the sectioned Text via the Query so that we can update the dynamic section at index 1. We only perform the update if some digits are buffered. If parsing the buffered data as a Wolfram code fails, then transiently update the label to "Error".

Finally, using a third system, we actually update the AutomatonRule resource:

fn maybe_change_rule(
    time: Res<Time>,
    mut rule: ResMut<AutomatonRule>,
    mut builder: ResMut<AutomatonRuleBuilder>,
    mut query: Query<&mut Window>
) {
    builder.tick(time.delta());
    match builder.new_rule()
    {
        Some(new_rule) =>
        {
            *rule = new_rule;
            let window = &mut query.single_mut();
            set_title(window.as_mut(), *rule);
        },
        None => {}
    }
}

We manually tick the AutomatonRuleBuilder‘s clock, then attempt to extract a new rule from the buffered input. We have access to the lone Window, so we can update the title to reflect a new rule; by using our cross-platform set_title, we ensure that this works both on native and the web.

Reporting FPS

Almost done! All that’s left is to display the instantaneous frames per second while the user holds down the right shift key:

fn maybe_show_fps(
    keys: Res<Input<KeyCode>>,
    mut fps: Query<&mut Style, With<Fps>>
) {
    let style = &mut fps.single_mut();
    style.display = match keys.pressed(KeyCode::ShiftRight)
    {
        true => Display::Flex,
        false => Display::None
    };
}

We’ve already talked briefly about the only otherwise new thing here. pressed continues to answer true for as long as the right shift key remains pressed, so the display will become Flex when the user presses the key and stay Flex until the user releases the key. This links the visibility of the overlay directly to the duration of that key press.

fn update_fps(
    diagnostics: Res<DiagnosticsStore>,
    mut fps: Query<&mut Text, With<FpsLabel>>
) {
    let text = &mut fps.single_mut();
    let fps = diagnostics.get(FrameTimeDiagnosticsPlugin::FPS).unwrap();
    if let Some(value) = fps.smoothed()
    {
        text.sections[1].value = format!("{:.2}", value);
    }
}

DiagnosticsStore is our gateway to the various diagnostics that Bevy maintains over the lifetime of our application. We added the FrameTimeDiagnosticsPlugin so that the frame rate would also be available through the DiagnosticsStore. We extract the desired Diagnostic by id, which in this case is the aptly named FPS. smoothed fetches the precomputed exponentially weighted moving average (EWMA) for the diagnostic. We restrict the result to two decimal places and update the dynamic section of the text at index 1.

Conclusion

Well, as they say these days, that was a lot. But I do believe that a demonstration is in order. We can hardly wrap up without seeing all of this in action, can we? Without further ado, let’s turn on a single cell and watch Rule #90 build a famous fractal: the Sierpiński triangle!

You can also experience this demonstration interactively if you prefer. You may need to click the grid to give the app focus before it will accept input from the keyboard or mouse.

We covered some math history, computer science, Rust programming, and elementary game development. Hopefully, this is the beginning of a journey, not the end; merely a whetting of your appetite to build awesomely with Rust. There are so many more topics and crates, and so much more to do with Bevy alone. Thanks for your time, and happy coding!