First I've met the game of life theory at the uni on a class named: computer science in biology. It was fascinating, the first micro program that actually seemed to be alive. Tonight I finally got a few hours to implement the code.
My problem with the game of life program is that it's quite heavy. On an N by M matrix you have N * M cells which need to be checked and adjusted individually. Of course there need to be some optimization in order to keep the memory footprint low and not to use the CPU as a muffin cooker.
However my solution at this point is medium-low. It's just good enough to be able to represent couple of hundreds of thousands of cells. I choose to use HTML5 Canvas and CoffeeScript just not to waste too much time on the technical part.
A quick recap about the game. So each cell's life depend highly on its neighbors. If it's too much or too few it dies. However if it's the optimal number it can breed new cells. The basic rules are the following:
Any live cell with fewer than two live neighbours dies, as if caused by under-population.
Any live cell with two or three live neighbours lives on to the next generation.
Any live cell with more than three live neighbours dies, as if by overcrowding.
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
As every prototype it starts with the HTML frame:
<!DOCTYPE html> <html> <head> <title>Game of Life</title> </head> <body> <canvas width="128" height="128" id="world"></canvas> <script src="script.js"></script> </body> </html>
Nothing extraordinary, really, a basic canvas tag and the script loader at the end of the file. I decided not to play with onload and whatnot.
Let's autopsy the Coffee code. We need some variables:
canvas = document.getElementById('world')
ctx = canvas.getContext('2d')
h = canvas.height
w = canvas.width
Obviously we need the canvas to be able to put the cells on it. Cells will be represented by black and white pixels. If you look for performance suggestions you will find soon that the imageData is a better way to present them than tiny rectangles:
livePixelImageData = ctx.createImageData(1, 1) deadPixelImageData = ctx.createImageData(1, 1)
Then we need some in-between storage that keeps information about the cells:
lifeMap = []
neighbors = []
neighborsMap = [[-1, -1], [-1, 0], [-1, 1],
[0, -1], [0, 1],
[1, -1], [1, 0], [1, 1]]
[lifemap] contains where are the living cells on the map. [neighbors] contains how many live neighbors the cell has. The [neighborsMap] will simply helps us to traverse the cell's neighbors on the matrix.
Let's add the cell creation and removal functions:
addPoint = (x, y) ->
pos = y * w + x
if !lifeMap[pos]
lifeMap[pos] = true
ctx.putImageData(livePixelImageData, x, y)
for offset in neighborsMap
neighbors[(y + offset[1]) * w + (x + offset[0])] += 1
return
What does it do? We check first if the cell lives. We only want to change the state (and use CPU) when we need to. If there is no living cell we create one. That means we save to cache that the position got a cell, then we draw the cell and finally increase all neighbors by one - telling them they got a new lovely neighbor cell. I also added return just to force CoffeeScript not to hassle around the return object, that gives us a little performance improvement too.
The cell removal function is almost the same, it's just doing the oposite:
removePoint = (x, y) ->
pos = y * w + x
if lifeMap[pos]
lifeMap[pos] = false
ctx.putImageData(deadPixelImageData, x, y)
for offset in neighborsMap
neighbors[(y + offset[1]) * w + (x + offset[0])] -= 1
return
Now we can take care of the heart of the system - handling a single life cycle:
refreshWorld = () ->
for y in [0..(h - 1)]
for x in [0..(w - 1)]
pos = y * w + x
if lifeMap[pos]
if !neighbors[pos] || neighbors[pos] <= 1 || neighbors[pos] > 3
removePoint(x, y)
else
if neighbors[pos] == 3
addPoint(x, y) if Math.random() > 0.18
return
It's a bit ineffective at the moment, but it's Saturday night, I should be in a pub drunk anyways. Here we also check if we need to change anything and implement the 4 rules. We check each cells and change them if necessary. I added a little random variant to birth - 82% of birth rate - in order to avoid overpopulation too soon.
Now we have some partial details to handle. First I added a shortcut for the refresher call, so it's easier to call:
iterate = (ms, callback) -> setInterval callback, ms
Then last the initialization:
init = () ->
for y in [0..(h - 1)]
for x in [0..(w - 1)]
pos = y * w + x
lifeMap[pos] = false
neighbors[pos] = 0
for i in [0..2]
livePixelImageData.data[i] = 0
deadPixelImageData.data[i] = 255
livePixelImageData.data[3] = 255
for i in [1..(h * w >> 3)]
addPoint Math.floor(Math.random() * w), Math.floor(Math.random() * h)
iterate 10, ->
refreshWorld()
return
First we clear the cell cache variables. Then we add the black and white colors to the dead / live cells. The third block generates an initial world state with some live cells. Last command will call the world iterator in every 10 milliseconds. That's pretty fast and if you look at the Chrome performance tool the time ratio between the operation and frame load is quite optimal.
And yeah, we can call init() and start life:
init()
That's it. You can check out the running app on demo page or sniff the repo on GitHub.
As I said already it's relatively slow. You can play with it by downloading the code and setting manually the size of the Canvas in the HTML.
As an improvement I can imagine to use integers instead of arrays and do binary operations instead of arithmetics. If you have any ideas please let me know.
---
Peter
No comments:
Post a Comment
Note: only a member of this blog may post a comment.