Last updated on

Game of Life

Points
40 points
Topics
State machines, Modularity
Files to submit
src/main/scala/scalashop/image/GameOfLife.scala

This question involves designing a state machine within the ScalaShop framework. Only the resulting output is tested.

Cellular Automata and the Game of Life

A cellular automaton is a type of state machine based on a grid of cells that take one of a possible set of states. Cellular automata are often used to model physical and biological systems, such as the spread of a virus or simulating fluids. Different cellular automata can be created by specifying how the state of a cell changes based on the state of its neighbors.

One of the most famous cellular automata is the Game of Life, devised and studied by mathematician John Horton Conway. The Game of Life is played on a 2D grid, and as the name suggests, is a simple model of life and death. Each cell represents an entity that can be either alive or dead.

The state machine is described by the following rules:

Here, a black pixel represents a live cell, and a white cell represents a dead one.

Sustenance: sustenance

Loneliness: loneliness

Overcrowding: overcrowding

Reproduction: reproduction

It is also possible to obtain an oscillating system. Here is an example called a blinker, with a period of two cycles: blinker

State Machines are Filters?

From extensive experience developing ScalaShop, you may note that a 2D grid is nothing but an image. In this vein, computing the next state of a system can be seen as simply applying a filter: the state of each pixel is decided based on the state of its neighbors.

In this exercise, you will implement the Game of Life as a ScalaShop filter.

Implement State

First, we need to represent and specify the cellular automaton as a state machine. The states Alive and Dead have been defined in GameOfLife.State. Implement the method GameOfLife.State.step to compute the next state of a cell, given the state of its 8 neighbours, based on the rules above.

def step(neighbours: Seq[State]): State =
  ???

src/main/scala/scalashop/image/GameOfLife.scala

Finally, having implemented states and transitions, we have a state machine in hand. All that remains is to tie this to an image. Implement the method GameOfLife.Step.apply, which, behaving as an image filter, computes the new state of a grid.

def apply(x: Int, y: Int): Pixel =
  ???

src/main/scala/scalashop/image/GameOfLife.scala

You can assume that the input grid is a valid Game of Life grid. The function to compute the neighbours of a pixel, assuming the grid wraps around, is provided to you as Step.neighbours.

The function Step.apply should map the input pixels to States, compute the next state, and map the result back to pixels.

Running

As before, ScalaShop can be run from sbt with the command run. This loads the ScalaShop GUI. Some additional controls have been added to facilitate viewing Game of Life states.

For now, you can use the default configurations on the top-right, pressing the “Load Configuration” button to load any of the existing Game of Life configurations to see the results of your filter.

scalashopgui

This loads the right image, sets the image scale, and changes the filter to game-of-life-step. You can press Apply to see the result of a single step, or Auto-step to run multiple steps in succession.

Testing

You can test your code in its entirety by running test within sbt in the project folder. The tests total up to 40 pts.

The tests are split into three major sets:

© 2023, 2024 EPFL. All rights reserved.