Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Game of Life

edited November 2012 Posts: 371

Hey everyone Here is my latest project, Conway's Game of Life!

For those who don't know how it works, it is a simulation where each cell is either alive or dead. There are a few rules to it though...
1. If a cell has 2 or less alive cells around it, it dies
2. If a cell has 4 or more alive cells around it, it dies
3. If a cell has 3 cells around it and is dead, it becomes alive

Here is my code:

-- Game Of Life

-- Use this function to perform your initial setup
function setup()
gSize = 32
displayMode(FULLSCREEN)
grid = { width = WIDTH / gSize, height = HEIGHT / gSize - 2 }
for x = 1, grid.width do
grid[x] = {}
for y = 1, grid.height do
grid[x][y] = 0
end
end
paused = 0
backingMode(RETAINED)
background(255, 255, 255, 255)
t = 0
c = 1
speed = .25
end

-- This function gets called once every frame
function draw()
local g = { width = WIDTH / gSize, height = HEIGHT / gSize - 2 }
t = t + DeltaTime
if t > c then
c = c + speed
background(255 - 128 * paused)
for x = 1, grid.width do
g[x] = {}
local r = grid[x]
for y = 1, grid.height do
local n = numSurrounding(x, y, grid)
local l = r[y]
g[x][y] = l
fill(0, 255 * l, 0)
--text(n, (x - .5) * gSize + 1, (y - .5) * gSize + 1)
rect((x - 1) * gSize + 1, (y - 1) * gSize + 1, gSize - 2, gSize - 2)
if paused == 0 then
if n < 2 then
g[x][y] = 0
elseif n == 2 then
g[x][y] = grid[x][y]

elseif n == 3 then
g[x][y] = 1
elseif n > 3 then
g[x][y] = 0
end
end
end
end
grid = g
end
end

function touched(touch)
if touch.state == ENDED then
if touch.y < HEIGHT - gSize * 2 then
grid[math.ceil(touch.x / gSize)][math.ceil(touch.y / gSize)] = 1 - grid[math.ceil(touch.x / gSize)][math.ceil(touch.y / 32)]
else
paused = 1-paused
end
end
end

function numSurrounding(x, y, g)
local n = 0
for i = x - 1, x + 1 do
for j = y - 1, y + 1 do
if not (i < 1 or j < 1 or i > grid.width or j > grid.height or (i == x and j == y)) then
n = n + g[i][j]
end
end
end
return n
end

And here's a video of it in action:

DEBUG MODE: To enable this, there is a commented line in draw, Uncomment it, and comment the rect call below it

Tagged:

• Posts: 384

This was fun, thanks! And in such a short code listing too.

• edited November 2012 Posts: 2,161

Your code is correct but your explanation has a minor error:

If a cell has 2 or less alive cells around it, it dies

Not so. If it is alive and has two alive neighbours then it stays alive.

• Posts: 371

Oh, whoops It should be one or zero, thanks Andrew

• Posts: 3,295

Very nice job,@Jordan

• Posts: 2,161

Yes, I forgot to say that I also like the simplicity of the code.

Now, I have a suggestion for you @Jordan. I don't know how much you've been following what's happening with the latest beta, so you may already know this. Using beta features (shaders) I recently did a Game-of-Life program. Using shaders means using the GPU which is ridiculously fast at doing the multiple parallel calculations needed for GoL. But the GPU is a waste of time if the events happen linearly. Then, one should use the flexibility of the CPU.

One thing that the "standard" GoL lacks is the ability to see what's happening. Because the whole field changes every time it can be difficult to look at one patch and see why something happens. After showing my version to my kids then we had to resort to pieces of paper to understand why we saw what we saw. It would have been great to have a system where we could enter in (as in your case) an initial state and then watch it progress almost tile-by-tile.

So my suggestion is that you develop your code to do this: a system where one can specify an initial state and set it going to see what happens (this is what you have) and, just as importantly, why it happens. It would have to be possible to see actual decisions and some visual indication of why a particular decision goes the way it does (and it should skip - as in not show the details - "boring" decisions).

Anyway, there's a suggestion for you - which you are, of course, free to ignore!

• Posts: 371

Thanks Andrew, what do you think about a animation controlled by you with a button which simply goes to the next generation, with a few steps in between?

• Posts: 2,161

That'd be a good start - particularly if you could run it backward!, but I'd also like something where you could somehow see it doing the computation.

• Posts: 7,807

Here is a version of The Game of Life to the extreme. If this is too slow for you, change the value of size to 4, 8, or 16 in setup(). At a size of 2, the initial screen takes about 5 seconds to show, with about 5 seconds between generations. I don't know how long it will take to reach a stable generation. At least not yet. Each initial run is a random mix with about half set. I did everything I could think of to max out the speed.

displayMode(FULLSCREEN) function setup()     size=2    -- try a value of 4, 8, or 16     xs=WIDTH/size; ys=HEIGHT/size     ltab={}; ctab={}     setInitialRandom()     fill(255) end function draw()     local x; local y; local lt; local ct     background(40, 40, 50)     checkEachSquare()     for x=0,xs do         for y=0,ys do             lt=ltab[x][y]; ct=ctab[x][y]             if lt==1 then                 if ct<2 or ct>3 then                     ltab[x][y]=0                 end             elseif ct==3 then                     ltab[x][y]=1             end             if ltab[x][y]==1 then                 rect(x*size,y*size,size-1,size-1)              end                                      end     end end function checkEachSquare()     local x; local y     for x=0,xs do         for y=0,ys do             checkNeighbors(x,y)         end      end     end function checkNeighbors(cx,cy)     local a1; local b1; local a; local b; local c=0     for a=-1,1 do         for b=-1,1 do             a1=cx+a; b1=cy+b             if a1>=0 and a1<=xs and b1>=0 and b1<=ys then                 if a~=0 or b~=0 then                     if ltab[a1][b1]==1 then                         c = c + 1                     end                 end             end         end     end     ctab[cx][cy]=c     end function setInitialRandom()     local x; local y     for x=0,xs do         ltab[x]={}; ctab[x]={}         for y=0,ys do             ctab[x][y]=0; ltab[x][y]=0             if math.random(200)>100 then                 ltab[x][y]=1             end         end     end     end
• Posts: 2,161

I found that the DeltaTime on your code got less as it went on. It seemed to stabilise at around 3.3s per frame. The code below outperforms that by a factor of about 2.

For reference, the GLSL shader version (with the same density, but also rendering to a torus) outperforms your code by a factor of 100 - but then that's due to using the GPU instead of the CPU. Having optimised your code a little, I'm now wondering if it is possible to optimise that code a bit more in a similar vein.

displayMode(FULLSCREEN)
function setup()
size=2    -- try a value of 4, 8, or 16
smo = size-1
xs=WIDTH/size; ys=HEIGHT/size
lnbd={}; cnbd={}
ltab={}; ctab={}
nbrs = {
{-1,-1},
{-1,0},
{-1,1},
{0,-1},
{0,1},
{1,-1},
{1,0},
{1,1}
}
setInitialRandom()
fill(255)
end

function draw()
local ct
local size = size
local smo = smo
local nbrs = nbrs
local rect = rect
background(40, 40, 50)
local ltab = ctab
local lnbd = cnbd
local lctab = {}
local lcnbd = {}
for x=-1,xs+1 do
lcnbd[x] = {}
for y=-1,ys+1 do
lcnbd[x][y]=0
end
end
for x=0,xs do
lctab[x] = {}
for y=0,ys do
if lnbd[x][y] == 3 or (ltab[x][y] and lnbd[x][y] == 2) then
for _,a in ipairs(nbrs) do
lcnbd[x+a][y+a] = lcnbd[x+a][y+a] + 1
end
rect(x*size,y*size,smo,smo)
lctab[x][y] = true
end
end
end
ctab = lctab
cnbd = lcnbd
end

function setInitialRandom()
for x=-1,xs+1 do
cnbd[x]={}
for y=-1,ys+1 do
cnbd[x][y]=0
end
end
for x=0,xs do
ctab[x]={}
for y=0,ys do
if math.random()>.5 then
for _,a in ipairs(nbrs) do
cnbd[x+a][y+a] = cnbd[x+a][y+a] + 1
end
ctab[x][y] = true
end
end
end
end

• Posts: 2,161

Not sure if this is actually faster, but it shortens one loop.

displayMode(FULLSCREEN)
function setup()
size=2    -- try a value of 4, 8, or 16
smo = size-1
xs=WIDTH/size; ys=HEIGHT/size
lnbd={}; cnbd={}
ltab={}; ctab={}
nbrs = {
{-1,-1},
{-1,0},
{-1,1},
{0,-1},
{0,1},
{1,-1},
{1,0}
}
setInitialRandom()
fill(255)
end

function draw()
local size = size
local smo = smo
local nbrs = nbrs
local rect = rect
background(40, 40, 50)
local ltab = ctab
local lnbd = cnbd
local lctab = {}
local lcnbd = {}
for x=-1,0 do
lcnbd[x] = {}
for y=-1,ys+1 do
lcnbd[x][y]=0
end
end
for x=0,xs do
lctab[x] = {}
lcnbd[x+1] = {}
lcnbd[x+1][-1] = 0
lcnbd[x+1] = 0
for y=0,ys do
if lnbd[x][y] == 3 or (ltab[x][y] and lnbd[x][y] == 2) then
for _,a in ipairs(nbrs) do
lcnbd[x+a][y+a] = lcnbd[x+a][y+a] + 1
end
lcnbd[x+1][y+1] = 1
rect(x*size,y*size,smo,smo)
lctab[x][y] = true
else
lcnbd[x+1][y+1] = 0
end
end
end
ctab = lctab
cnbd = lcnbd
end

function setInitialRandom()
for x=-1,xs+1 do
cnbd[x]={}
for y=-1,ys+1 do
cnbd[x][y]=0
end
end
for x=0,xs do
ctab[x]={}
for y=0,ys do
if math.random()>.5 then
for _,a in ipairs(nbrs) do
cnbd[x+a][y+a] = cnbd[x+a][y+a] + 1
end
cnbd[x+1][y+1] = 1
ctab[x][y] = true
end
end
end
end

• Posts: 7,807

Thanks @Andrew_Stacey. Your first example is just over 2 times faster and the second about 1.5 times faster. The bad thing is, apparently I don't know Lua well enough to know how to get the most speed out of it. The good thing is, I have something new to figure out. I guess I'll have to lookup Lua optimization and see what they say. And, I'll have to look through your code to see what you did to speed it up that much.

• Posts: 2,161

The real curiosity is why the second is slower than the first.

The secret to the initial speed-up is that I didn't optimise the lua code, I optimised the mathematics. So although there are a few lua optimisations (such as using local very aggressively), the biggest gain comes from thinking of GoL slighly differently.