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 in Code Sharing 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

Comments

  • 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

  • Jmv38Jmv38 Mod
    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.

  • dave1707dave1707 Mod
    Posts: 7,611

    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[1]][y+a[2]] = lcnbd[x+a[1]][y+a[2]] + 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[1]][y+a[2]] = cnbd[x+a[1]][y+a[2]] + 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] = 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[1]][y+a[2]] = lcnbd[x+a[1]][y+a[2]] + 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[1]][y+a[2]] = cnbd[x+a[1]][y+a[2]] + 1
                    end
                    cnbd[x+1][y+1] = 1
                    ctab[x][y] = true
                end
            end
        end    
    end
    
  • dave1707dave1707 Mod
    Posts: 7,611

    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.

Sign In or Register to comment.