Categories
Programming

Game of Life implementation in Erlang

Background

The universe of the Game of Life is a two-dimensional grid of square cells, each of which is in one of two possible states, dead or alive. Each cell interacts with its eight neighbors, those cells that are horizontally, vertically, or diagonally adjacent. At each unit of time the following transitions occur:

  • Any living cell with fewer than two living neighbors dies, as if by under-population.
  • Any living cell with two or three living neighbors lives on to the next generation.
  • Any living cell with more than three living neighbors dies, as if by overcrowding.
  • Any dead cell with exactly three living neighbors becomes alive, as if by reproduction.

For an assignment at school, my classmate Jonatan and I were to implement this in Erlang.

Demonstration

This video demonstrates the finished game and two examples called a pulsar and a glider.

Source code

First off, here is the main program. If you would like some more information before seeing the code keep scrolling.

Data representation

The input to our program is represented as a list of {X,Y} tuples containing coordinates. Our internal data is represented as a single list using the indices of the list as a one-dimensional representation of the grid. This was chosen over representing the game and its input as multi-dimensional arrays for simplicity.

Note: the worst random access time of a list compared to an array is negligible as random access is only required once during the setup.

Each cell contains information about its coordinate, current state (dead or alive), list of its neighbors, and information about them such as number of living neighbors.

Synchronization

To keep our game in sync and avoid race conditions we use a “master” process to notify all cells when a new unit of time (tic) begins. Each cell responds by sending its current state to all of its neighbors then waits for its neighbors to send their current state. When all current states have been collected the new cell state is updated and drawn. This avoids synchronization issues by making sure all processes start at roughly the same time.

Source code for supporting files is available in this Gist.

To run the program:

c(ehtml). 
c(frame). 
c(gol).
gol:gol(40,40,[{5,4},{3,5},{5,5},{4,6},{5,6}]).

Open a browser and go to the URL http://localhost:8088/

Known bugs

The update rate for the browser is not in sync with the actual game update. This causes some irregular behaviour in the visualization of the game.

Summary

I would like to try to make a version of Game of Life in Node.js and see what advantages Node.js brings to the table in a GoL-implementation.