22 September 2020

Life on Screen

Welcome back to Exploring FPGA Graphics. In this post we’re going to use the designs we created in Framebuffers to experiment with Conway’s Game of Life.

In this series, we explore graphics at the hardware level and get a feel for the power of FPGAs. We’ll learn how displays work, race the beam with Pong, animate starfields and sprites, paint Michelangelo’s David, simulate life with bitmaps, draw lines and shapes, and finally render simple 3D models. New to the series? Start with FPGA Graphics.

You can watch an FPGA Graphics demo reel with designs from across this series.

Updated 2021-05-26. Get in touch with @WillFlux or open an issue on GitHub.

He is Archimedes, Mick Jagger, Salvador Dalí, and Richard Feynman, all rolled into one.
The Guardian, John Horton Conway: the world’s most charismatic mathematician (2015)

Series Outline

  • FPGA Graphics - learn how displays work and animate simple shapes
  • Pong - race the beam to create the arcade classic
  • Hardware Sprites - fast, colourful, graphics with minimal resources
  • Ad Astra - demo with hardware sprites and animated starfields
  • Framebuffers - driving the display from a bitmap in memory
  • Life on Screen (this post) - the screen comes alive with Conway’s Game of Life
  • Lines and Triangles - drawing lines and triangles with a framebuffer
  • 2D Shapes - filling and animating shapes
  • Simple 3D - models and wireframe rendering (draft coming soon)

Requirements

For this series, you need an FPGA board with video output. We’ll be working at 640x480, so pretty much any video output will do. It helps to be comfortable with programming your FPGA board and reasonably familiar with Verilog.

We’ll be demoing with these boards (FPGA type):

Source

The SystemVerilog designs featured in this series are available from the projf-explore git repo under the open-source MIT licence: build on them to your heart’s content. The rest of the blog content is subject to standard copyright restrictions: don’t republish it without permission.

Conway’s Life

John Conway was a remarkable mathematician, active in many fields, who sadly died in 2020. Conway is best known to the public for recreational mathematics with Martin Gardner in Scientific American. I remember playing Sprouts at school and trying to impress people by calculating the day of the week with the Doomsday rule. For now, I’ll be limiting myself to Game of Life, but I highly recommend learning more of Conway: The world’s most charismatic mathematician is an excellent place to start.

Game of Life first appeared in the Mathematical Games column in the October 1970 issue of Scientific American. Anyone can access the article at ibiblio.org, or you can see a scan of the original at JSTOR (requires login via academic institution or library).

The Rules of Life

The universe of the Game of Life is an infinite, two-dimensional, grid of cells. A cell is one of two states: dead or alive. Every cell interacts with its eight neighbours (those to the left, right, top, bottom, and the four diagonals).

The following rules determine the fate of a cell in the next generation:

  1. Survival: Every cell with two or three neighbours survives.
  2. Deaths:
    a. Every cell with four or more neighbours dies from overpopulation.
    b. Every cell with zero or one neighbours dies from isolation.
  3. Births: Every empty cell with exactly three neighbours comes to life.

To understand this, it helps to see some practical examples. Common patterns within the Life universe have been given names. The diagram below shows two patterns: “Beehive” and “Beacon”.

Conway’s Life Examples

Every live cell in the Beehive pattern has two or three neighbours: so, no cells die. No dead cells in Beehive have three neighbours: so, no cells come to life. This pattern is categorised as a “still life”, because it doesn’t change from one generation to the next.

The Beacon pattern is a bit more interesting: it oscillates between two states. Two dead cells in the centre of the pattern have three neighbours, so come to life. However, they then have four neighbours, so die the next generation due to overcrowding: this pattern repeats endlessly.

However, things start to get really interesting with slightly more complex patters. The following photo shows the Gosper glider gun running on the Arty board. The gun repeatedly generates small patterns called gliders that step across the world.

Gosper Glider Gun

It’s even possible to construct logic gates using gliders, and ultimately a universal Turing machine. As this post is primarily about FPGA graphics, we’re not going to dig further into the esoteric possibilities of Conway’s Life, but check out Wikipedia’s article on Conway’s Game of Life.

A Hard Life

Now we have a basic understanding of Life, we’re going to create a hardware implementation.

Let’s start by rearranging the rules to simplify the design:

  1. If a cell is alive
    a. if it has 2 or 3 neighbours, it’s alive next generation
    b. otherwise, it’s dead next generation
  2. If a cell is dead
    a. if it has 3 neighbours, it’s alive next generation
    b. otherwise, it’s dead next generation

We need a two-dimensional array to hold our world. Our memory array obviously can’t be infinite, so we need a way to handle the edges.

  1. Surround the world with a border of dead cells
  2. Wrap the world around at left and right, and at top and bottom

Both approaches have their advantages and disadvantages, so we’ll support both, but start with option 1.

Since a cell’s state depends on all those around it, we can’t calculate the new state of each cell with one array. Instead, we have two array (or buffers): one contains the current generation; we use it to calculate the next generation in the second buffer. Every generation, we swap buffers and repeat the generation process.

Create a life module with the following design - [life.sv]:

module life #(
    parameter CORDW=16,   // signed coordinate width
    parameter WIDTH=6,    // world width in cells
    parameter HEIGHT=6,   // world height in cells
    parameter F_INIT=""   // initial world state
    ) (
    input  wire logic clk,      // clock
    input  wire logic rst,      // reset
    input  wire logic start,    // start generation
    output      logic ready,    // cell state ready to be read
    output      logic alive,    // is the cell alive? (when ready)
    output      logic changed,  // cell's state changed (when ready)
    output      logic signed [CORDW-1:0] x,  // horizontal cell position
    output      logic signed [CORDW-1:0] y,  // vertical cell position
    output      logic running,  // life is running
    output      logic done      // generation complete (high for one tick)
    );

    // world buffer selection
    logic next_gen;  // where to write the next generation
    always_ff @(posedge clk) begin
        if (start) next_gen <= ~next_gen;  // swap every generation
        if (rst) next_gen <= 0;
    end

    // world in BRAM
    localparam DATAW = 1;  // cells are either dead or alive
    localparam WORLD_WIDTH  = WIDTH  + 2;  // wider to handle boundary
    localparam WORLD_HEIGHT = HEIGHT + 2;  // taller to handle boundary
    localparam WORLD_CELLS = WORLD_WIDTH * WORLD_HEIGHT;
    localparam DEPTH = 2 * WORLD_CELLS;
    localparam ADDRW = $clog2(DEPTH);

    logic we;
    logic [ADDRW-1:0] cell_id, addr_read;  // cell_id is basis of write address
    logic [DATAW-1:0] data_in, data_out;

    // add offset to read and write addresses to match buffer used
    logic [ADDRW-1:0] addr_read_offs, addr_write_offs;
    always_comb begin
        addr_read_offs = addr_read + ((next_gen) ? 0 : WORLD_CELLS);
        addr_write_offs = cell_id + ((next_gen) ? WORLD_CELLS : 0);
    end

    bram_sdp #(
        .WIDTH(DATAW),
        .DEPTH(DEPTH),
        .INIT_F(F_INIT)
    ) bram_inst (
        .clk_write(clk),
        .clk_read(clk),
        .we,
        .addr_write(addr_write_offs),
        .addr_read(addr_read_offs),
        .data_in,
        .data_out
    );

    // cell coordinates
    localparam GRID = 3;    // neighbours are a 3x3 grid
    localparam STEPS = 11;  // 9 reads and 2 cycles of latency
    logic [$clog2(WORLD_WIDTH)-1:0]  cell_x;  // active cell (horizontal)
    logic [$clog2(WORLD_HEIGHT)-1:0] cell_y;  // active cell (vertical)
    logic [$clog2(STEPS)-1:0] read_step;      // reading step
    logic inc_read;                           // perform incremental read
    logic [GRID-1:0] top_sr, mid_sr, bot_sr;  // shift reg for neighbours
    logic [$clog2(GRID*GRID)-1:0] neigh_cnt;  // count of neighbours

    // life generation state
    enum {IDLE, INIT, READ, NEIGH, UPDATE, NEW_CELL, NEW_LINE} state;
    always_ff @(posedge clk) begin
        // single-cycle flags: 0 by default
        ready <= 0;
        we <= 0;
        done <= 0;

        case(state)
            INIT: begin
                read_step <= 0;
                inc_read <= 0;
                top_sr <= 0;
                mid_sr <= 0;
                bot_sr <= 0;
                neigh_cnt <= 0;
                state <= READ;
                running <= 1;

                // first cell after padding
                cell_x <= 1;
                cell_y <= 1;
                cell_id <= WORLD_WIDTH + 1;
            end
            READ: begin  // 1 cycle to set address and 1 cycle BRAM read latency
                case (read_step)
                    4'd0: begin
                        addr_read <= cell_id - WORLD_WIDTH - 1;  // A
                    end
                    4'd1: begin
                        addr_read <= cell_id - 1;  // B
                    end
                    4'd2: begin
                        addr_read <= cell_id + WORLD_WIDTH - 1;  // C
                        if (!inc_read) top_sr <= {top_sr[1:0], data_out};  // A
                    end
                    4'd3: begin
                        addr_read <= cell_id - WORLD_WIDTH;  // D
                        if (!inc_read) mid_sr <= {mid_sr[1:0], data_out};  // B
                    end
                    4'd4: begin
                        addr_read <= cell_id;  // E
                        if (!inc_read) bot_sr <= {bot_sr[1:0], data_out};  // C
                    end
                    4'd5: begin
                        addr_read <= cell_id + WORLD_WIDTH;  // F
                        if (!inc_read) top_sr <= {top_sr[1:0], data_out};  // D
                    end
                    4'd6: begin
                        addr_read <= cell_id - WORLD_WIDTH + 1;  // G
                        if (!inc_read) mid_sr <= {mid_sr[1:0], data_out};  // E
                    end
                    4'd7: begin
                        addr_read <= cell_id + 1;  // H
                        if (!inc_read) bot_sr <= {bot_sr[1:0], data_out};  // F
                    end
                    4'd8: begin
                        addr_read <= cell_id + WORLD_WIDTH + 1;  // I
                        top_sr <= {top_sr[1:0], data_out};  // G
                    end
                    4'd9: begin
                        mid_sr <= {mid_sr[1:0], data_out};  // H
                    end
                    4'd10: begin
                        bot_sr <= {bot_sr[1:0], data_out};  // I
                    end
                    default: addr_read <= 0;
                endcase

                if (read_step == STEPS-1) state <= NEIGH;
                else read_step <= read_step + 1;
            end
            NEIGH: begin
                neigh_cnt <= top_sr[0] + top_sr[1] + top_sr[2] +
                             mid_sr[0]             + mid_sr[2] +
                             bot_sr[0] + bot_sr[1] + bot_sr[2];
                state <= UPDATE;
            end
            UPDATE: begin
                // update cell state
                we <= 1;     // write new cell state next cycle
                ready <= 1;  // ready for output next cycle
                x <= cell_x - 1;  // correct horizontal position for padding
                y <= cell_y - 1;  // correct vertical position for padding

                if (mid_sr[1]) begin // cell was alive this generation
                    if (neigh_cnt == 2 || neigh_cnt == 3) begin  // still alive
                        data_in <= 1;
                        alive <= 1;
                        changed <= 0;
                    end else begin  // now dead
                        data_in <= 0;
                        alive <= 0;
                        changed <= 1;
                    end
                end else begin  // was dead this generation
                    if (neigh_cnt == 3) begin  // now alive
                        data_in <= 1;
                        alive <= 1;
                        changed <= 1;
                    end else begin  // still dead
                        data_in <= 0;
                        alive <= 0;
                        changed <= 0;
                    end
                end

                // what next?
                if (cell_x == WORLD_WIDTH-2) begin  // final cell on line
                    if (cell_y == WORLD_HEIGHT-2) begin  // final line of cells
                        state <= IDLE;
                        running <= 0;
                        done <= 1;
                    end else state <= NEW_LINE;
                end else state <= NEW_CELL;
            end
            NEW_CELL: begin
                cell_x <= cell_x + 1;
                cell_id <= cell_id + 1;
                inc_read  <= 1;  // incremental read
                read_step <= 6;  // read new column of 3 cells (skip A-F)
                state <= READ;
            end
            NEW_LINE: begin
                cell_y <= cell_y + 1;
                cell_x <= 1;
                cell_id <= cell_id + 3;  // skip 2 cells of padding
                read_step <= 0;  // read all nine cells at start of line
                state <= READ;
            end
            default: state <= (start) ? INIT : IDLE;  // IDLE
        endcase
        if (rst) begin
            state <= IDLE;
            ready <= 0;
            alive <= 0;
            changed <= 0;
            x <= 0;
            y <= 0;
            running <= 0;
            done <= 0;
        end
    end
endmodule

Explanation of life module will be added shortly.

To exercise this module we have a test bench for Vivado: life_tb.sv. If you have a Xilinx Vivado installed, try using the test bench with the included test seed files. You can find instructions for running the simulation in the design README.

Top Life

Now we have our life sim, we’re ready to render it with the design from Framebuffers.

The Arty version is shown below:

module top_life (
    input  wire logic clk_100m,     // 100 MHz clock
    input  wire logic btn_rst,      // reset button (active low)
    output      logic vga_hsync,    // horizontal sync
    output      logic vga_vsync,    // vertical sync
    output      logic [3:0] vga_r,  // 4-bit VGA red
    output      logic [3:0] vga_g,  // 4-bit VGA green
    output      logic [3:0] vga_b   // 4-bit VGA blue
    );

    localparam GEN_FRAMES = 15;  // each generation lasts this many frames
    localparam SEED_FILE = "simple_64x48.mem";  // world seed

    // generate pixel clock
    logic clk_pix;
    logic clk_locked;
    clock_gen_480p clock_pix_inst (
       .clk(clk_100m),
       .rst(!btn_rst),  // reset button is active low
       .clk_pix,
       .clk_locked
    );

    // display timings
    localparam CORDW = 16;
    logic hsync, vsync;
    logic de, frame, line;
    display_timings_480p #(.CORDW(CORDW)) display_timings_inst (
        .clk_pix,
        .rst(!clk_locked),  // wait for pixel clock lock
        .sx(),
        .sy(),
        .hsync,
        .vsync,
        .de,
        .frame,
        .line
    );

    logic frame_sys;  // start of new frame in system clock domain
    xd xd_frame (.clk_i(clk_pix), .clk_o(clk_100m),
                 .rst_i(1'b0), .rst_o(1'b0), .i(frame), .o(frame_sys));

    // life signals
    logic life_start, life_alive, life_changed;

    // start life generation in blanking every GEN_FRAMES
    logic [$clog2(GEN_FRAMES)-1:0] cnt_frames;
    always_ff @(posedge clk_100m) begin
        life_start <= 0;
        if (frame_sys) begin
            if (cnt_frames == GEN_FRAMES-1) begin
                life_start <= 1;
                cnt_frames <= 0;
            end else cnt_frames <= cnt_frames + 1;
        end
    end

    // framebuffer (FB)
    localparam FB_WIDTH   = 64;
    localparam FB_HEIGHT  = 48;
    localparam FB_CIDXW   = 2;
    localparam FB_CHANW   = 4;
    localparam FB_SCALE   = 10;
    localparam FB_IMAGE   = "";
    localparam FB_PALETTE = "life_palette.mem";

    logic fb_we;
    logic signed [CORDW-1:0] fbx, fby;  // framebuffer coordinates
    logic [FB_CIDXW-1:0] fb_cidx;
    logic [FB_CHANW-1:0] fb_red, fb_green, fb_blue;  // colours for display

    framebuffer #(
        .WIDTH(FB_WIDTH),
        .HEIGHT(FB_HEIGHT),
        .CIDXW(FB_CIDXW),
        .CHANW(FB_CHANW),
        .SCALE(FB_SCALE),
        .F_IMAGE(FB_IMAGE),
        .F_PALETTE(FB_PALETTE)
    ) fb_inst (
        .clk_sys(clk_100m),
        .clk_pix,
        .rst_sys(1'b0),
        .rst_pix(1'b0),
        .de,
        .frame,
        .line,
        .we(fb_we),
        .x(fbx),
        .y(fby),
        .cidx(fb_cidx),
        .clip(),
        .red(fb_red),
        .green(fb_green),
        .blue(fb_blue)
    );

    // select colour based on cell state
    always_comb fb_cidx = {1'b0, life_alive};

    life #(
        .CORDW(CORDW),
        .WIDTH(FB_WIDTH),
        .HEIGHT(FB_HEIGHT),
        .F_INIT(SEED_FILE)
    ) life_inst (
        .clk(clk_100m),          // clock
        .rst(1'b0),              // reset
        .start(life_start),      // start generation
        .ready(fb_we),           // cell state ready to be read
        .alive(life_alive),      // is the cell alive? (when ready)
        .changed(life_changed),  // cell's state changed (when ready)
        .x(fbx),                 // horizontal cell position
        .y(fby),                 // vertical cell position
        .running(),              // life is running
        .done()                  // generation complete (high for one tick)
    );

    // reading from FB takes one cycle: delay display signals to match
    logic hsync_p1, vsync_p1;
    always_ff @(posedge clk_pix) begin
        hsync_p1 <= hsync;
        vsync_p1 <= vsync;
    end

    // VGA output
    always_ff @(posedge clk_pix) begin
        vga_hsync <= hsync_p1;
        vga_vsync <= vsync_p1;
        vga_r <= fb_red;
        vga_g <= fb_green;
        vga_b <= fb_blue;
    end
endmodule

We use a 64x48 world, which is a tenth of the 640x480 screen dimensions. With the padding of dead cells, each world array has 66 x 50 = 3,300 cells, which comfortably fits into 4Kb (though iCEBreaker BRAM has a minimum width of two bits, so it uses two BRAMs per world buffer).

Building the Designs
In the Life on Screen section of the git repo, you’ll find the design files, a makefile for iCEBreaker, a Vivado project for Arty, and instructions for building the designs for both boards.

Once you’ve programmed your board, you should see a simple test pattern of oscillators and a still life. If that works, try the Gosper glider gun by changing the seed file in top_life.sv:

localparam SEED_FILE = "gosper_gun_64x48.mem";  // world seed

The Gosper pattern repeatedly generates small gliders that move down the screen. Our gliders doesn’t continue indefinitely because our world is currently surrounded by dead cells, which kill the gliders when they collide with it.

You can also change how fast Life runs by adjusting GEN_FRAMES:

localparam GEN_FRAMES = 4;  // each generation lasts this many frames

At 60 frames per second, a value of ‘4’ results in 15 generations per second.

Wrap Around

Let’s wrap our world around at left and right, and at top and bottom; this is known as a toroidal array. Contrast a toroidal array with a 2D map of Earth: the map wraps around at the east and west, but not at the north and south.

Design in progress

Explore

I hope you enjoyed this (draft) instalment of Exploring FPGA Graphics, but nothing beats creating your own designs. Here are a few suggestions to get you started:

  • Experiment with your own Life seed. Start with empty seed: res/seeds/empty_64x48.mem
  • Use changed from the life module to colour cells when they’re born or die
  • Implement a Universal Turing Machine with Life: take a look at Paul Rendell’s Attic

More ideas to follow…

Next Time

In part seven of this series, we’ll learn how to draw Lines and Triangles: the basis of 2D and 3D graphics.

Constructive feedback is always welcome. Get in touch with @WillFlux or open an issue on GitHub.

©2021 Will Green, Project F