Let's Compartmentalize Coding (Go Life). Yes, let's!

 

Let's Compartmentalize Coding (Go Life). Yes, let's!

Premise

I think one of the main things that used to give me grief whenever I needed to start working on any new project (my currently unfinished game included) was - where do you even start? So I would just jump into it, start coding, then jump into some other bit of it and it’d either take quite a few reassessments of what I was doing with some rewriting of the code before I’d be happy with it; or it’d end up consisting of monstrous, hideous, terrible code.

Splitting the task into small, manageable chunks works. You don’t make a matryoshka doll with all the dolls inside and painted in one go (heh). Isolated pieces of functionality, one piece at a time. That’s how you do it.

Talking about splitting the task into small chunks is all great, but an example would be nice, right? Don’t worry, I’m on it.

Go Life

Last week I’ve been sort of talking about Conway’s Game of Life, and before that had a post on Go, let’s be consistent. Let’s make Conway’s Game of Life in Go.

Quick refresher:

In Conway’s Game of Life you have a conceptually infinite grid that consists of cells. Each cell can either be alive or dead. The user can provide the initial setup of the grid.

The state of each cell is defined by four simple rules:

  1. If a live cell has fewer than two neighbours that are alive - it dies (under-population);
  2. If a live cell has two or three alive neighbours - it survives;
  3. If a live cell has more than three neighbours that are alive - it dies (over-population);
  4. A dead cell with exactly three alive neighbours becomes a live cell (reproduction).

Rules get applied cyclically.

Let’s do this!

So okay, let’s split the problem into smaller pieces.

Let’s try and get a mental image (or draw an actual representation - on a sheet of paper, whiteboard, blackboard, a wall) of the implementation we want to have. We have a grid filled with cells, some of them are alive, some are dead. We have four rules that get applied to each cell. The state of the grid gets updated based on rules, too. So we need to have cycles. We need a way to display the grid at the end of each cycle, one way or another. Also the grid starts off with some sort of configuration, it would be nice to be able to easily define it. Oh yeah, the grid is conceptually infinite.

So we need: a [user-provided] configuration, an [infinite] grid, cells, rules, an update loop, output.

Cells

Cells really aren’t complicated. They need to have information about their x and y coordinates and can be either alive or dead. So let’s create a struct with two ints and a boolean.

	var Cell struct {
		x, y  int
		alive bool
	}

Grid

The Grid. [A digital frontier. I tried to picture clusters of information as they moved through the computer. What did they look like? Ships? Motorcycles? Were the circuits like freeways? I kept dreaming of a world I thought I’d never see. And then, one day…]

How can we represent the grid? We can use a list or an array. Let’s go for simplicity and use an array. We can make it a one-dimensional array and populate it with cells. But let’s think about it some more. If we do that - how do we look for a cell’s neighbours? Will we need to have an additional nested for loop to go through the whole array and look at x and y values of each cell to determine whether they’re a neighbour or not? We can write a simple formula that will calculate the positions of neighbours for each cell…

Let’s be lazy instead. Let’s have a two-dimensional array, an array of rows, if you will. Indices will represent coordinates. grid[1][12] would return a cell with x of 1 and y of 12. But, wait a second, then we don’t need Cells to contain coordinates in them, duplication sucks.

Cells

Okay, let’s remove the coordinates.

	var Cell struct {
		alive bool
	}

So now we end up with a struct that’s essentially a wrapper for a boolean. Do we need that? No, no we don’t. Here’s our new Cell struct:



Grid

So, based on all the decisions up to now, our grid is a two-dimensional array of booleans. Let’s make it small for now too.

	var grid [3][3]bool

Seed

We want to be able to populate the grid somehow. Don’t forget, we’re being lazy, so let’s go for something easy. How about a text file with zeroes and ones representing alive and dead states. Cool. How do we read the file contents into our grid?

Because writing a file reader isn’t the point of this exercise, let’s see if Google has anything for us. Hint: it does:

	func fileToString(path string) string {
		dat, err := ioutil.ReadFile(path)
		check(err)
		return string(dat)
	}

	func check(e error) {
		if e != nil {
			panic(e)
		}
	}

Perfect. So now we are getting the contents of the file as a string of characters. We want to iterate through those characters, put a false into the grid when we come across a zero and a true when we come across a one. We can add a check for the next line character to know when we need to move on to the next row, but how about we don’t. A quick check shows us that the string we’re getting contains an end of line character and a next line character and that is just too much stuff to deal with. Let’s use the fact that we know the size of the grid, so we can use division and modulo to determine where in the row we are and whether we need to increment it. But now hard coding the size of the grid seems like a silly idea. Hold on.

Grid

	const size int = 23
	var grid [size][size]bool

Seed

Now then, how about this?

	func stringToGridArray(gridFileContents string) {
		validCharacterCounter := 0

		for _, character := range gridFileContents {

			if string(character) == "0" || string(character) == "1" {
				initCell(validCharacterCounter/size, int(math.Mod(float64(validCharacterCounter), float64(size))), string(character) == "1")
			} else {
				validCharacterCounter--
			}

			validCharacterCounter++
		}
	}

And yes, I actually used the initCell function before creating it, because at this point I don’t care about its implementation.

If you haven’t seen Go before and are curious about that underscore - range gridFileContents returns two values (the index and the value), since we don’t care about the index, because for us it doesn’t accurately represent indices of valid characters (remember, the string contains end of lines and next lines as well) we use a blank identifier for that. Which, in Go, means that we don’t very much care about the fact that we’re getting it.

Anyway, once this function is done - we can write initCell, which is as simple as:

	func initCell(x, y int, alive bool) {
		grid[x][y] = alive
	}

To test it we can call fileToString and stringToGridArray from main and then print out the contents of the grid.

	fmt.Printf("%v", grid)

Now we have a grid with alive and dead cells. Time to move on.

Rules

We have four rules, and all of them require counting the number of alive neighbours for each cell we’re looking at. So before we implement any of the rules - we need a way to do the counting. And, come to think of it… our grid is finite and it shouldn’t be. What should we do when we’re looking for neighbours of a cell conveniently located right on the edge? Let’s think about how we can fake the grid being infinite.

We can assume that the neighbours that are not in our grid array are all dead cells, if we come to the point that one or more of those cells need to come to life - we can make a bigger array and move all the values from the smaller one to it. That sounds like it might take some time. Any other options?

Well, many old school videogames (NES and pre-NES times) used to have this thing - when you go off the screen on the one side - you reappear on the opposite side. A good example is Pacman with those little paths in the middle-right and middle-left. How about we do that for every edge of our grid? I know, it’s sort of cheating, but I really-really don’t want to implement an actual infinite grid.

Ok, so what do we need and where do we start? All of the cells that we will be teleporting to already exist in the grid array, so rules will be applied to them by default. Which means, that we only need to worry about them when we are checking for neighbours.

Neighbours

Right, forget about everything I’ve just said for a second and pretend that we do, in fact, have an infinite grid, how would we get the alive neighbours of cells. Well, suppose we give coordinates of our current cell to a function and it gives us back coordinates of a specific neighbour and then we check if it’s alive or dead, rinse and repeat.

Each cell has exactly eight neighbours. Imagine we’re looking at cell ‘1’.

	000
	010
	000

What would be the coordinates of its neighbours?

Top row: (x-1, y-1), (x, y-1), (x+1, y-1)
Middle row: (x-1, y), (x+1, y)
Bottom row: (x-1, y+1), (x, y+1), (x+1, y+1)

We can either write eight functions, one for each neighbour, or try to be more generic. Let’s try to be more generic, it feels like it’s less work.

	func getLeft(x *int) int {
		return *x - 1
	}

	func getRight(x *int) int {
		return *x + 1
	}

	func getUp(y *int) int {
		return *y - 1
	}

	func getDown(y *int) int {
		return *y + 1
	}

Fantastic, that would probably work if we had an actual infinite grid, but we don’t, so we’ll run into out of bounds errors. So now, finally, is the time to do our infinite grid cheat. Before checking for the cell at coordinates provided by getLeft, getRight, getUp and getDown we call accountForEdges which is just what you’d expect it to be.

	func accountForEgdes(x, y *int) {
		if *x < 0 {
			*x = size - 1
		} else if *x >= size {
			*x = 0
		}

		if *y < 0 {
			*y = size - 1
		} else if *y >= size {
			*y = 0
		}
	}

Checking if a cell is alive is pretty easy. Let’s say we pass in the coordinates of a neighbour and an integer that represents the total number of alive neighbours for a specific cell. If the neighbour is alive - we increment the integer.

	func checkAliveAndIncrement(x, y, aliveNeighbours *int) {
		if grid[*x][*y] == true {
			*aliveNeighbours++
		}
	}

Now we need to make all those functions work together.

	func getNoOfAliveNeighbours(x, y int) int {
		aliveNeighbours := 0

		countAlives(getLeft(&x), getUp(&y), &aliveNeighbours)
		countAlives(getLeft(&x), y, &aliveNeighbours)
		countAlives(getLeft(&x), getDown(&y), &aliveNeighbours)
		countAlives(x, getUp(&y), &aliveNeighbours)
		countAlives(x, getDown(&y), &aliveNeighbours)
		countAlives(getRight(&x), getUp(&y), &aliveNeighbours)
		countAlives(getRight(&x), y, &aliveNeighbours)
		countAlives(getRight(&x), getDown(&y), &aliveNeighbours)

		return aliveNeighbours
	}

	func countAlives(x, y int, aliveNeighbours *int) {
		accountForEgdes(&x, &y)
		checkAliveAndIncrement(&x, &y, aliveNeighbours)
	}

Sweet. A good way to test it would be to initialize the grid and check that every cell has an expected number of alive neighbours whilst playing around with the initial state of the grid.

Rules

Rules are so easy they basically translate into a set of conditionals themselves. So we pass in: the number of alive neighbours a cell has, whether the cell itself is alive or dead and set it to

	func evolveCell(numberOfAliveNeighbours int, cellAlive bool) {
		if *cellAlive && numberOfAliveNeighbours < 2 { // underpopulation
			*cellAlive = false
		} else if !*cellAlive && numberOfAliveNeighbours == 3 { // reproduction
			*cellAlive = true
		} else if *cellAlive && numberOfAliveNeighbours > 3 { // overpopulation
			*cellAlive = false
		} else if *cellAlive && (numberOfAliveNeighbours == 3 || numberOfAliveNeighbours == 2) { // propagation
			*cellAlive = true // not necessary and is only added for completeness sake
		}
	}

Wait no… Wait, wait… We can’t update the state of cells in real-time. If we kill off or give birth to cells in the same grid that we’re currently applying rules to - everything will break really quickly. Cells will start losing or gaining neighbours, chaos will ensue, Donald Trump will win the elections.

We need some sort of buffer that we can write the next state of the system to, as we’re calculating it. So (last change, I promise):

Grid

	const size int = 23

	var grid [size][size]bool
	var nextGrid [size][size]bool

We’ll need to initialize it somewhere as well. Because we don’t particularly care what’s in it for the first ever iteration - we can populate it with all ones, all zeroes, draw your favourite pattern in it or just initialize it using the seed.

	func initCell(x, y int, alive bool) {
		grid[x][y] = alive
		nextGrid[x][y] = alive // for the initialization nextGrid == grid
	}

Rules

And now we can pass an additional boolean to evolveCell - the new state of that cell.

	func evolveCell(numberOfAliveNeighbours int, cellAlive, nextGridCell *bool) {
		if *cellAlive && numberOfAliveNeighbours < 2 { // underpopulation
			*nextGridCell = false
		} else if !*cellAlive && numberOfAliveNeighbours == 3 { // reproduction
			*nextGridCell = true
		} else if *cellAlive && numberOfAliveNeighbours > 3 { // overpopulation
			*nextGridCell = false
		} else if *cellAlive && (numberOfAliveNeighbours == 3 || numberOfAliveNeighbours == 2) { // propagation
			*nextGridCell = true // not necessary and is only added for completeness sake
		}
	}

Now I could’ve renamed initCell and used it to set the value of nextGridCell, that would require passing coordinates into this function (and I don’t like passing in more than three values) or, instead of setting the boolean in this function - return it and then pass it into initCell with coordinates (however, I wanted to play around with pointers, since I don’t get to do that with Java). So, I admit - this is not the cleanest solution, but it’s a conscious decision.

Now, we need to group getting the number of alive neighbours and applying rules together and, preferably, do it for each cell in the grid.

	func evolve() {
		for i := 0; i < size; i++ {
			for j := 0; j < size; j++ {
				aliveNeighbours := getNoOfAliveNeighbours(i, j)
				evolveCell(aliveNeighbours, &grid[i][j], &nextGrid[i][j])
			}
		}
	}

Our main function looks something like this.

	func main() {
		initialize()
		evolve()
		grid = nextGrid
	}

But it only runs once.

Update Loop

Luckily Go’s default set of libraries seems to come with a timer. So we create one that triggers, say, once every second until the end of the world and put all our logic inside.

	timer := time.Tick(1000 * time.Millisecond)
	for tick := range timer {
		_ = tick

		evolve()
		grid = nextGrid
	}

Using a timer requires creating a tick variable. Go is fussy about variables that are not used, up to the point of not compiling, so we use another blank identifier. If we cared about ticks, we could print them to the console and get the exact time of each tick. But we don’t.

This leaves the last bit.

Output

So the remaining bit is to come up with a straightforward, easy-to-understand way of displaying the state of our grid at each cycle.

Now, to be completely honest, my initial plan was to have cells represented as coloured rectangles, displayed in a window. Colour would determine whether they’re alive or dead. If there’s extra time - add the ability for the user to set the initial state of the grid by clicking on rectangles and then hitting ‘play’ or something.

Four hours of researching Go libraries proved that I have been overly optimistic. There seem to be libraries that allow you to draw to a png, jpeg or gif programmatically (cool, but irrelevant for this exercise); OpenGL libraries (also cool, but feels like overkill), GUI libraries (neat, but also irrelevant); and a few that provide 2d graphics functionality (bingo!). I have tried to use a couple of those 2d graphics libraries, got frustrated a couple of times, looked at my watch, noticed that four hours have passed and remembered something. We’re going for the lazy approach.

So let’s just print the grid to the console after each update.

func printGrid() {
	fmt.Println("======================")

	for i := 0; i < size; i++ {
		for j := 0; j < size; j++ {
			if grid[i][j] == true {
				fmt.Print(1)
			} else {
				fmt.Print("-")
			}
		}
		fmt.Println("")
	}
}

So we end up with something like this:

Do a tiny bit of renaming of variables, re-arrange the functions in the order of them being called and boom, we’re done!

Conclusion (or something)

Hopefully it’s obvious that planning this solution out beforehand helped. Sure, a couple of times along the way I had realizations that something should’ve been done differently, which probably means that I could’ve planned it out better, but they never involved any massive changes to existing code. Which was my point.

Anyhow, for a complete version of working code click here.