Game logic

The first module we will build is the game logic. You are probably familiar with snake games, but if not, the basic idea is that the player guides a snake around a 2D grid. At any given time, there is some "food" at a random location on the grid and the goal of the game is to get the snake to "eat" as much food as possible. Each time the snake eats food it grows in length. The player loses if the snake crashes into its own tail.

In some variants of the game, the player also loses if the snake crashes into the edge of the grid, but given the small size of our grid we are going to implement a "wraparound" rule: if the snake goes off one edge of the grid, it will continue from the opposite edge.

The game module

We will build up the game mechanics in the game module.

Coordinates

We start by defining a coordinate system for our game (src/game/coords.rs).

#![allow(unused)]
fn main() {
use super::Prng;

use heapless::FnvIndexSet;

/// A single point on the grid.
#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
pub struct Coords {
    // Signed ints to allow negative values (handy when checking if we have gone
    // off the top or left of the grid)
    pub row: i8,
    pub col: i8,
}

impl Coords {
    /// Get random coordinates within a grid. `exclude` is an optional set of
    /// coordinates which should be excluded from the output.
    pub fn random(rng: &mut Prng, exclude: Option<&FnvIndexSet<Coords, 32>>) -> Self {
        let mut coords = Coords {
            row: ((rng.random_u32() as usize) % 5) as i8,
            col: ((rng.random_u32() as usize) % 5) as i8,
        };
        while exclude.is_some_and(|exc| exc.contains(&coords)) {
            coords = Coords {
                row: ((rng.random_u32() as usize) % 5) as i8,
                col: ((rng.random_u32() as usize) % 5) as i8,
            }
        }
        coords
    }

    /// Whether the point is outside the bounds of the grid.
    pub fn is_out_of_bounds(&self) -> bool {
        self.row < 0 || self.row >= 5 || self.col < 0 || self.col >= 5
    }
}
}

We use a Coords struct to refer to a position on the grid. Because Coords only contains two integers, we tell the compiler to derive an implementation of the Copy trait for it, so we can pass around Coords structs without having to worry about ownership.

Random Number Generation

We define an associated function, Coords::random, which will give us a random position on the grid. We will use this later to determine where to place the snake's food.

To generate random coordinates, we need a source of random numbers. The nRF52833 has a hardware random number generator (HWRNG) peripheral, documented at section 6.19 of the nRF52833 spec. The HAL gives us a simple interface to the HWRNG via the microbit::hal::rng::Rng struct. The HWRNG may not be fast enough for a game; it is also convenient for testing to be able to replicate the sequence of random numbers produced by the generator between runs, which is impossible for the HWRNG by design. We thus also define a pseudo-random number generator (PRNG). The PRNG uses an xorshift algorithm to generate pseudo-random u32 values. The algorithm is basic and not cryptographically secure, but it is efficient, easy to implement and good enough for our humble snake game. Our Prng struct requires an initial seed value, which we do get from the RNG peripheral.

All of this makes up src/game/rng.rs.

#![allow(unused)]
fn main() {
use crate::Rng;

/// A basic pseudo-random number generator.
pub struct Prng {
    value: u32,
}

impl Prng {
    pub fn seeded(rng: &mut Rng) -> Self {
        Self::new(rng.random_u32())
    }

    pub fn new(seed: u32) -> Self {
        Self { value: seed }
    }

    /// Basic xorshift PRNG function: see <https://en.wikipedia.org/wiki/Xorshift>
    fn xorshift32(mut input: u32) -> u32 {
        input ^= input << 13;
        input ^= input >> 17;
        input ^= input << 5;
        input
    }

    /// Return a pseudo-random u32.
    pub fn random_u32(&mut self) -> u32 {
        self.value = Self::xorshift32(self.value);
        self.value
    }
}
}

Movement

We also need to define a few enums that help us manage the game's state: direction of movement, direction to turn, the current game status and the outcome of a particular "step" in the game (ie, a single movement of the snake). src/game/movement.rs contains these.

#![allow(unused)]
fn main() {
use super::Coords;

/// Define the directions the snake can move.
pub enum Direction {
    Up,
    Down,
    Left,
    Right,
}

/// What direction the snake should turn.
#[derive(Debug, Copy, Clone)]
pub enum Turn {
    Left,
    Right,
    None,
}

/// The current status of the game.
pub enum GameStatus {
    Won,
    Lost,
    Ongoing,
}

/// The outcome of a single move/step.
pub enum StepOutcome {
    /// Grid full (player wins)
    Full,
    /// Snake has collided with itself (player loses)
    Collision,
    /// Snake has eaten some food
    Eat(Coords),
    /// Snake has moved (and nothing else has happened)
    Move(Coords),
}
}

A Snake (A Snaaake!)

Next up we define a Snake struct, which keeps track of the coordinates occupied by the snake and its direction of travel. We use a queue (heapless::spsc::Queue) to keep track of the order of coordinates and a hash set (heapless::FnvIndexSet) to allow for quick collision detection. The Snake has methods to allow it to move. src/game/snake.rs gets this.

#![allow(unused)]
fn main() {
use super::{Coords, Direction, FnvIndexSet, Turn};

use heapless::spsc::Queue;

pub struct Snake {
    /// Coordinates of the snake's head.
    pub head: Coords,
    /// Queue of coordinates of the rest of the snake's body. The end of the tail is
    /// at the front.
    pub tail: Queue<Coords, 32>,
    /// A set containing all coordinates currently occupied by the snake (for fast
    /// collision checking).
    pub coord_set: FnvIndexSet<Coords, 32>,
    /// The direction the snake is currently moving in.
    pub direction: Direction,
}

impl Snake {
    pub fn make_snake() -> Self {
        let head = Coords { row: 2, col: 2 };
        let initial_tail = Coords { row: 2, col: 1 };
        let mut tail = Queue::new();
        tail.enqueue(initial_tail).unwrap();
        let mut coord_set: FnvIndexSet<Coords, 32> = FnvIndexSet::new();
        coord_set.insert(head).unwrap();
        coord_set.insert(initial_tail).unwrap();
        Self {
            head,
            tail,
            coord_set,
            direction: Direction::Right,
        }
    }

    /// Move the snake onto the tile at the given coordinates. If `extend` is false,
    /// the snake's tail vacates the rearmost tile.
    pub fn move_snake(&mut self, coords: Coords, extend: bool) {
        // Location of head becomes front of tail
        self.tail.enqueue(self.head).unwrap();
        // Head moves to new coords
        self.head = coords;
        self.coord_set.insert(coords).unwrap();
        if !extend {
            let back = self.tail.dequeue().unwrap();
            self.coord_set.remove(&back);
        }
    }

    fn turn_right(&mut self) {
        self.direction = match self.direction {
            Direction::Up => Direction::Right,
            Direction::Down => Direction::Left,
            Direction::Left => Direction::Up,
            Direction::Right => Direction::Down,
        }
    }

    fn turn_left(&mut self) {
        self.direction = match self.direction {
            Direction::Up => Direction::Left,
            Direction::Down => Direction::Right,
            Direction::Left => Direction::Down,
            Direction::Right => Direction::Up,
        }
    }

    pub fn turn(&mut self, direction: Turn) {
        match direction {
            Turn::Left => self.turn_left(),
            Turn::Right => self.turn_right(),
            Turn::None => (),
        }
    }
}
}

Game Module Top-Level

The Game struct keeps track of the game state. It holds a Snake object, the current coordinates of the food, the speed of the game (which is used to determine the time that elapses between each movement of the snake), the status of the game (whether the game is ongoing or the player has won or lost) and the player's score.

This struct contains methods to handle each step of the game, determining the snake's next move and updating the game state accordingly. It also contains two methods--game_matrix and score_matrix--that output 2D arrays of values which can be used to display the game state or the player score on the LED matrix (as we will see later).

We put the Game struct at the top of the game module, in src/game.rs.

#![allow(unused)]
fn main() {
mod coords;
mod movement;
mod rng;
mod snake;

use crate::Rng;

pub use coords::Coords;
pub use movement::{Direction, GameStatus, StepOutcome, Turn};
pub use rng::Prng;
pub use snake::Snake;

use heapless::FnvIndexSet;

/// Struct to hold game state and associated behaviour
pub struct Game {
    pub status: GameStatus,
    rng: Prng,
    snake: Snake,
    food_coords: Coords,
    speed: u8,
    score: u8,
}

impl Game {
    pub fn new(rng: &mut Rng) -> Self {
        let mut rng = Prng::seeded(rng);
        let mut tail: FnvIndexSet<Coords, 32> = FnvIndexSet::new();
        tail.insert(Coords { row: 2, col: 1 }).unwrap();
        let snake = Snake::make_snake();
        let food_coords = Coords::random(&mut rng, Some(&snake.coord_set));
        Self {
            rng,
            snake,
            food_coords,
            speed: 1,
            status: GameStatus::Ongoing,
            score: 0,
        }
    }

    /// Reset the game state to start a new game.
    pub fn reset(&mut self) {
        self.snake = Snake::make_snake();
        self.place_food();
        self.speed = 1;
        self.status = GameStatus::Ongoing;
        self.score = 0;
    }

    /// Randomly place food on the grid.
    fn place_food(&mut self) -> Coords {
        let coords = Coords::random(&mut self.rng, Some(&self.snake.coord_set));
        self.food_coords = coords;
        coords
    }

    /// "Wrap around" out of bounds coordinates (eg, coordinates that are off to the
    /// left of the grid will appear in the rightmost column). Assumes that
    /// coordinates are out of bounds in one dimension only.
    fn wraparound(&self, coords: Coords) -> Coords {
        if coords.row < 0 {
            Coords { row: 4, ..coords }
        } else if coords.row >= 5 {
            Coords { row: 0, ..coords }
        } else if coords.col < 0 {
            Coords { col: 4, ..coords }
        } else {
            Coords { col: 0, ..coords }
        }
    }

    /// Determine the next tile that the snake will move on to (without actually
    /// moving the snake).
    fn get_next_move(&self) -> Coords {
        let head = &self.snake.head;
        let next_move = match self.snake.direction {
            Direction::Up => Coords {
                row: head.row - 1,
                col: head.col,
            },
            Direction::Down => Coords {
                row: head.row + 1,
                col: head.col,
            },
            Direction::Left => Coords {
                row: head.row,
                col: head.col - 1,
            },
            Direction::Right => Coords {
                row: head.row,
                col: head.col + 1,
            },
        };
        if next_move.is_out_of_bounds() {
            self.wraparound(next_move)
        } else {
            next_move
        }
    }

    /// Assess the snake's next move and return the outcome. Doesn't actually update
    /// the game state.
    fn get_step_outcome(&self) -> StepOutcome {
        let next_move = self.get_next_move();
        if self.snake.coord_set.contains(&next_move) {
            // We haven't moved the snake yet, so if the next move is at the end of
            // the tail, there won't actually be any collision (as the tail will have
            // moved by the time the head moves onto the tile)
            if next_move != *self.snake.tail.peek().unwrap() {
                StepOutcome::Collision
            } else {
                StepOutcome::Move(next_move)
            }
        } else if next_move == self.food_coords {
            if self.snake.tail.len() == 23 {
                StepOutcome::Full
            } else {
                StepOutcome::Eat(next_move)
            }
        } else {
            StepOutcome::Move(next_move)
        }
    }

    /// Handle the outcome of a step, updating the game's internal state.
    fn handle_step_outcome(&mut self, outcome: StepOutcome) {
        self.status = match outcome {
            StepOutcome::Collision => GameStatus::Lost,
            StepOutcome::Full => GameStatus::Won,
            StepOutcome::Eat(c) => {
                self.snake.move_snake(c, true);
                self.place_food();
                self.score += 1;
                if self.score % 5 == 0 {
                    self.speed += 1
                }
                GameStatus::Ongoing
            }
            StepOutcome::Move(c) => {
                self.snake.move_snake(c, false);
                GameStatus::Ongoing
            }
        }
    }

    pub fn step(&mut self, turn: Turn) {
        self.snake.turn(turn);
        let outcome = self.get_step_outcome();
        self.handle_step_outcome(outcome);
    }

    /// Calculate the length of time to wait between game steps, in milliseconds.
    /// Generally this will get lower as the player's score increases, but need to
    /// be careful it cannot result in a value below zero.
    pub fn step_len_ms(&self) -> u32 {
        let result = 1000 - (200 * ((self.speed as i32) - 1));
        if result < 200 {
            200u32
        } else {
            result as u32
        }
    }

    /// Return an array representing the game state, which can be used to display the
    /// state on the microbit's LED matrix. Each `_brightness` parameter should be a
    /// value between 0 and 9.
    pub fn game_matrix(
        &self,
        head_brightness: u8,
        tail_brightness: u8,
        food_brightness: u8,
    ) -> [[u8; 5]; 5] {
        let mut values = [[0u8; 5]; 5];
        values[self.snake.head.row as usize][self.snake.head.col as usize] = head_brightness;
        for t in &self.snake.tail {
            values[t.row as usize][t.col as usize] = tail_brightness
        }
        values[self.food_coords.row as usize][self.food_coords.col as usize] = food_brightness;
        values
    }

    /// Return an array representing the game score, which can be used to display the
    /// score on the microbit's LED matrix (by illuminating the equivalent number of
    /// LEDs, going left->right and top->bottom).
    pub fn score_matrix(&self) -> [[u8; 5]; 5] {
        let mut values = [[0u8; 5]; 5];
        let full_rows = (self.score as usize) / 5;
        #[allow(clippy::needless_range_loop)]
        for r in 0..full_rows {
            values[r] = [1; 5];
        }
        for c in 0..(self.score as usize) % 5 {
            values[full_rows][c] = 1;
        }
        values
    }
}
}

Next we will add the ability to control the snake's movements.