Monday, 29 July 2013

Python - Game of Life - Alternative Starts

In an earlier blog post I explained how to write a version of Conway's Game of Life using Python and Pygame.

Game of Life Blog

The starting point for the 'game' was completely random. Before running the game we went through each of the cells in the grid and either made them alive or dead.

As the Game of Life progresses the cells either multiply or die out depending upon the state of the surrounding cells. After a period of time the majority of the cells die, and eventually the system finishes in a stable state. You may well have a few oscillators, cells which live and die in a set pattern, but the system is stable.

Does this have to be the case?

People have spent a lot of time looking into the Game of Life and seeing if the system will ever become unstable. There are a few interesting starting patterns which I thought I would share, so you can use them as an alternative to the random pattern.

If you remember, when programming the Game of Life we stored all the data about our cells in a dictionary called lifeDict. This dictionary listed the co-ordinates for each of the cells, and stored the information telling us if they were alive, using a 1, or dead, using a 0.

To create this dictionary initially we called a function called blankGrid. This returned a dictionary containing all the cells. All the cells in this dictionary were dead.

We then called a second function called startingGridRandom which set our starting grid to be completely random. To do this it randomly set all cells in the library as a 0, for dead, or a 1 for alive.

If we wrote another function and used that to define our starting state layout instead of the startingGridRandom function we could play around with our starting state to try out a few different options. Let's do that now.

I am assuming that you have already a working copy of my code for Conways Game of Life. If not you can download it from my previous blog by following this link.

Game of Life Blog

The first alternative starting state we will try is called the R-pentomino.

What I like about the R-pentomino is it releases gliders. A glider is a group of cells that appear to move across the screen. In other words they form a pattern that never stabilises, the pattern repeats until the glider runs off the screen.

The R-pentomino grows quite large, so to avoid it hitting the side of the grid you will need to make a few modifications to the size of your grid.

Set the global values of WINDOWWIDTH, WINDOWHEIGHT and CELLSIZE as shown below.


Now below the function called startingGridRandom we will create a new function called startingRPentomino. Again we will need the dictionary lifeDict to be passed to the function, so we can alter it to match our new starting point.

As you can see from the image of the R-pentomino above there are 5 cells which we need to make alive to form the R-pentomino. I have experimented with this a lot, so know the cells produced (other than the gliders!) do not hit the edge of the grid. Each line below takes a co-ordinate on the grid and turns it into an alive cell. If you look at these co-ordinates you will see they form the R-pentomino. If you don't believe me, try plotting them onto some graph paper!

Finally we need to return the cells which are in lifeDict

The code for the new function should look like this.

def startingRpentomino(lifeDict):
    lifeDict[48,32] = 1
    lifeDict[49,32] = 1
    lifeDict[47,33] = 1
    lifeDict[48,33] = 1
    lifeDict[48,34] = 1
    return lifeDict

Now in our main() function we can see that we make all cells blank and then we put the output from startingGridRandom() into lifeDict. Lets put a # in front of that line, which will stop our program calling it. Instead add a line underneath which calls our new starting function.

    ###Starting options
    #lifeDict = startingGridRandom(lifeDict) # Assign random life
    lifeDict = startingRpentomino(lifeDict) # Setup R-pentomino

Ok that should be all the changes we need in order to run the program. Press F5 to save and then run the program, and watch the R-pentimino do its thing.

It's quite impressive that those few cells keep generating new cells for so long.

Did you see the gliders moving across the screen?

This looks good, but its not the most impressive. The R-pentomino is definitely trumped by the acorn. Although I am not sure, this must have gained its name because it grows as large as an oak! The acorn takes a whopping 5206 generation to stabilise, and releases a total of 13 gliders.

A picture of the Acorn is shown below.

This grows larger than the grid system provided, but I will let you play around with the grid size you think you will need. Remember the larger the size of the grid the slower your program will run. For now leave it as it was for the R-pentomino.


Write a new function underneath the startingRpentomino function called startingAcorn.

To create the Acorn use the following co-ordinates.

def startingAcorn(lifeDict):
    lifeDict[105,55] = 1
    lifeDict[106,55] = 1
    lifeDict[109,55] = 1
    lifeDict[110,55] = 1
    lifeDict[111,55] = 1
    lifeDict[106,53] = 1
    lifeDict[108,54] = 1
    return lifeDict

Make sure you call the new startingAcorn function before pressing F5 to save and run the game.

    ###Starting options
    #lifeDict = startingGridRandom(lifeDict) # Assign random life
    #lifeDict = startingRpentomino(lifeDict) # Setup R-pentomino
    lifeDict = startingAcorn(lifeDict) # Setup Acorn

You should see this grows until it finally reaches a stable state.

Another interesting starting position is called the die-hard. When this reaches a stable position there are no living cells left, they all die. It takes 130 generations for that to happen.

Set the size of the screen to the same as the R-pentoimino again.


The function to start off a Die-hard is as follows.

def startingDiehard(lifeDict):
    lifeDict[45,45] = 1
    lifeDict[46,45] = 1
    lifeDict[46,46] = 1
    lifeDict[50,46] = 1
    lifeDict[51,46] = 1
    lifeDict[52,46] = 1
    lifeDict[51,44] = 1
    return lifeDict

Make sure you place a # in front of the code calling the Acorn and write some new code to call the startingDiehard function.

    ###Starting options
    #lifeDict = startingGridRandom(lifeDict) # Assign random life
    #lifeDict = startingRpentomino(lifeDict) # Setup R-pentomino
    #lifeDict = startingAcorn(lifeDict) # Setup Acorn
    lifeDict = startingDiehard(lifeDict)

Ok we have seen that a few cells can lead into a massive amount of growth before becoming stable, and it's possible for all cells to die before the stable position is reached. What if there was a pattern which created an unstable system? Well there are numerous, but the first one created was known as a Gosper Glider Gun. This was named after its creator - Bill Gosper. And unsurprisingly produces that cool pattern of unstable cells, which look as though they are moving across the screen... Gliders!

Keep the size of the screen as used previously.


Below is the code which will create a Gosper Glider Gun

def startingGosperGliderGun(lifeDict):
    #Gosper Glider Gun
    #left square
    lifeDict[5,15] = 1
    lifeDict[5,16] = 1
    lifeDict[6,15] = 1
    lifeDict[6,16] = 1

    #left part of gun
    lifeDict[15,15] = 1
    lifeDict[15,16] = 1
    lifeDict[15,17] = 1
    lifeDict[16,14] = 1
    lifeDict[16,18] = 1
    lifeDict[17,13] = 1
    lifeDict[18,13] = 1
    lifeDict[17,19] = 1
    lifeDict[18,19] = 1
    lifeDict[19,16] = 1
    lifeDict[20,14] = 1
    lifeDict[20,18] = 1
    lifeDict[21,15] = 1
    lifeDict[21,16] = 1
    lifeDict[21,17] = 1
    lifeDict[22,16] = 1

    #right part of gun
    lifeDict[25,13] = 1
    lifeDict[25,14] = 1
    lifeDict[25,15] = 1
    lifeDict[26,13] = 1
    lifeDict[26,14] = 1
    lifeDict[26,15] = 1
    lifeDict[27,12] = 1
    lifeDict[27,16] = 1
    lifeDict[29,11] = 1
    lifeDict[29,12] = 1
    lifeDict[29,16] = 1
    lifeDict[29,17] = 1

    #right square
    lifeDict[39,13] = 1
    lifeDict[39,14] = 1
    lifeDict[40,13] = 1
    lifeDict[40,14] = 1

    return lifeDict

Finally you need to call the startingGosperGliderGun function in the main part of your program to get this to work.

    ###Starting options
    #lifeDict = startingGridRandom(lifeDict) # Assign random life
    #lifeDict = startingRpentomino(lifeDict) # Setup R-pentomino
    #lifeDict = startingAcorn(lifeDict) # Setup Acorn
    #lifeDict = startingDiehard(lifeDict)
    lifeDict = startingGosperGliderGun(lifeDict)

I hope you have had fun playing around with different starting options for the game of life. This hopefully has given you a flavour of why people find the Game of Life so intriguing. Perhaps you can investigate some other starting options yourself which will beat those I have shown you here!

Source Code Game of Life - Alternative Starts