Golang Implementation of Conway's Game of Life

title: Implementing Conway's Game of Life in Golang
date: 2022-05-23 17:15:00
toc: false
index_img: http://api.btstu.cn/sjbz/?lx=m_dongman&cid=2
category:

Go
tags:
Read
Create
Golang
Traverse
Calculate
Solve
Simulate
Output
Statistics
Print
Game

Experiment: Slice Life#

In this experiment, we will build a simulator called "Conway's Game of Life" to simulate the process of human reproduction. Since the simulation needs to take place on a two-dimensional grid filled with cells, this experiment will focus on slices.

Each cell in the grid has a total of 8 neighboring cells in horizontal, vertical, and diagonal directions. In each generation, the survival of a single cell will depend on the number of neighboring cells that are alive.

The Beginning#

When initially implementing the Game of Life, we need to constrain the world to a fixed size. Specifically, we need to decide on the dimensions of the grid and define the corresponding constants:

const (
  width  = 80
  height = 15
)

Next, we need to define the Universe type to hold the two-dimensional cell grid, using boolean values true and false to represent the survival and death of cells, respectively:

type Universe [][]bool

By using slices instead of arrays to represent the world, functions and methods can more easily share and modify the world.

After this, we will also write the NewUniverse function, which allocates and returns a Universe with height rows and width columns using make:

func NewUniverse() Universe

Since the elements of the newly allocated slice will be set to the default zero value false, there will be no living cells in the world at the beginning.

Observing the World#

Please write a method for Universe that can print the current state of the world to the screen using functions from the fmt package, where living cells are represented by asterisks and dead cells by spaces. Additionally, it needs to move the cursor to a new output line after printing each row of cells:

func (u Universe) Show()

Please write a main function that calls the NewUniverse function to create a new world and then calls the Show function to print this world. Before continuing with the experiment, please ensure that your program runs correctly, even if there are currently no living cells in the entire world.

Activating Cells#

Please write a Seed method that can randomly activate about 25% of the cells in the world (setting the corresponding slice elements to true):

func (u Universe) Seed()

When implementing this method, don't forget to import the math/rand package to use the Intn function. After this, please modify the main function to activate the world using the Seed method and then print the activated world using the Show function.

Survival of the Fittest#

Here are the specific rules of Conway's Game of Life:

When a living cell has fewer than 2 living neighbors, it dies.
When a living cell has 2 or 3 living neighbors, it survives to the next generation.
When a living cell has more than 3 living neighbors, it dies.
When a dead cell has exactly 3 living neighbors, it becomes alive.

To implement these rules, we need to break them down into the following 3 steps and implement each step as a corresponding method:

A method to determine if a cell is alive
The ability to count the number of neighboring living cells
The logic to determine if a cell survives or dies in the next generation

Alive or Dead#

Determining if a cell is alive can be done by checking the boolean value of the corresponding element in the Universe slice; as long as that value is true, the cell is alive.

Please write an Alive method for the Universe type with the following signature:

func (u Universe) Alive(x, y int) bool

The most challenging part of implementing the Alive method is handling out-of-bounds situations. For example, how do we determine if the cell at (-1, -1) is alive or dead? Or how do we determine if the cell at (80, 15) is alive or dead on an 80x15 grid?

To solve this problem, we need to implement wrapping for the world. This way, the cell above (0, 0) will no longer be (0, -1), but rather (0, 14), which can be calculated by adding height to y. If y exceeds the grid's height, we need to use the modulus operator (%) introduced when calculating leap years, and then take y modulo height to get the corresponding remainder. This method also applies to x and width.

Counting Neighboring Cells#

Please write a method to count the number of living neighbors of a given cell and return a value between 0 and 8:

func (u Universe) Neighbors(x, y int) int

To implement wrapping for the world, please use the Alive method instead of directly accessing the world data.

Additionally, when counting neighboring cells, do not include the given cell itself in the count.

Game Logic#

After implementing the method to count neighboring living cells, we can formally implement the game rules listed at the beginning of this section in the Next method:

func (u Universe) Next(x, y int) bool

This method will not directly modify the world but will return a boolean value indicating whether the given cell will survive or die in the next generation.

Parallel Worlds#

To complete the simulation, the program needs to traverse each cell in the world and use Next to determine their state in the next generation.

One important issue to note is that counting neighboring cells must be based on the previous state of the world. If the program modifies the world while performing the count, such modifications will inevitably affect the counting results of neighboring cells.

A simple solution to this problem is to create two equally sized worlds and set world B while reading world A. Please write a Step function to perform this operation:

func Step(a, b Universe)

Once world B has been updated to the next generation, the program can swap these two worlds and continue to the next update:

a, b = b, a

Before displaying the new generation of cells, the program needs to use the special ANSI escape sequence "\x0c" to clear the screen. After that, the program can print the entire world and use the time package's Sleep function to slow down the speed of generation changes.

Note: Outside of the Go Playground, you will need to use other mechanisms to clear the screen; for example, on macOS, you need to print "\033[H" instead of "\x0c".

Now, you should have all the components needed to write and run a complete implementation of Conway's Game of Life in the Go Playground.

Implementation#

Code up to The Beginning#

package main

import "fmt"

const (
	width  = 25
	height = 15
)

type Universe [][]bool

func NewUniverse() Universe {
	u := make(Universe, height)
	for i := range u {
		u[i] = make([]bool, width)
	}
	return u
}

func main() {
	u := NewUniverse()
	for _, i := range u {
		fmt.Println(i)
	}
}

Output:

[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]
[false false false false false false false false false false false false false false false false false false false false false false false false false]

Program exited.

Complete Code#

package main

import (
	"fmt"
	"math/rand"
	"time"
)

const (
	width  = 80
	height = 15
)

type Universe [][]bool

func NewUniverse() Universe {
	u := make(Universe, height)
	for i := range u {
		u[i] = make([]bool, width)
	}
	return u
}

func (u Universe) Set(x, y int, b bool) {
	u[y][x] = b
}

func (u Universe) Seed() {
	for i := 0; i < (width * height / 4); i++ {
		u.Set(rand.Intn(width), rand.Intn(height), true)
	}
}

func (u Universe) Alive(x, y int) bool {
	x = (x + width) % width
	y = (y + height) % height
	return u[y][x]
}

func (u Universe) Neighbors(x, y int) int {
	n := 0
	for v := -1; v <= 1; v++ {
		for h := -1; h <= 1; h++ {
			if !(v == 0 && h == 0) && u.Alive(x+h, y+v) {
				n++
			}
		}
	}
	return n
}

func (u Universe) Next(x, y int) bool {
	n := u.Neighbors(x, y)
	return n == 3 || n == 2 && u.Alive(x, y)
}

func (u Universe) String() string {
	var b byte
	buf := make([]byte, 0, (width+1)*height)

	for y := 0; y < height; y++ {
		for x := 0; x < width; x++ {
			b = ' '
			if u[y][x] {
				b = '*'
			}
			buf = append(buf, b)
		}
		buf = append(buf, '\n')
	}

	return string(buf)
}

func (u Universe) Show() {
	fmt.Print("\x0c", u.String())
}

func Step(a, b Universe) {
	for y := 0; y < height; y++ {
		for x := 0; x < width; x++ {
			b.Set(x, y, a.Next(x, y))
		}
	}
}

func main() {
	a, b := NewUniverse(), NewUniverse()
	a.Seed()
	for i := 0; i < 300; i++ {
		Step(a, b)
		a.Show()
		time.Sleep(time.Second / 30)
		a, b = b, a
	}
}

Please visit the Go Playground to see: Go Playground - The Go Programming Language