Geodesic Game of Life


#1

Hi,

I managed to make a icosahedron-based geodesic CA engine with hexagonal tiles. In this implementation it’s running on a B2S34 ruleset I saw on the wikipedia page. I haven’t added in mouse input yet, but there’s a board randomizer function.

It’s not spectacularly fast, but that’s mostly because I’m a n00b. I was wondering if anyone has any suggestions for optimizations.

Right now I’m using a neighbour count array, so that the adjacent cells don’t have to be examined when the current cell isn’t changing state. The board is represented as a list of hexes, each of which contains a list of references to the adjacent hexes.

The hexes consist of hardware instanced triangles, so render is not such a big load, at least according to PStats. The loop that updates the color info arrays does introduce some significant overheads though.

Screenshot of the initial randomized board.

After reaching steady state:

Video:
http://www.youtube.com/watch?v=cU_T1jxl4I8

Some rough notes about how the program functions:

https://docs.google.com/document/d/1KgUHMjjOg8K-XdsKTWw0KzTqu_XnhlL9EJ5o-q2poQ4/edit?hl=en&authkey=CKj5xNoF

Main

# To change this template, choose Tools | Templates
# and open the template in the editor.

__author__="Jon"
__date__ ="$Apr 13, 2011 10:06:15 AM$"

from direct.showbase.ShowBase import ShowBase
from panda3d.core import GeomVertexFormat, GeomVertexData, Geom
from direct.gui.OnscreenText import OnscreenText
from panda3d.core import GeomVertexWriter, GeomTriangles, GeomNode
from panda3d.core import Vec3, Point3, Mat4, Vec4, PTAFloat
from panda3d.core import PStatClient, BoundingSphere
from panda3d.core import TextNode
from direct.task.Task import Task
from random import randint
import math

class Graph():
    def __init__(self, icosphere, subdivisions):
        facenodes = icosphere.getChildren()
        self.nodepath = icosphere
        self.faces = []
        self.subdivisions = subdivisions

        self.hexlist = self.genHexList()
        self.trianglelist = self.genTriangleList()

        #Initialize faces
        for i in range(20):
            #Need to use a copy function to make new istance of the hexlist
            #No need for that for the trianglelist, since its just a reference
            self.faces.append(Icoface(i, facenodes[i], subdivisions, self.hexlist.copy(),
                                        self.trianglelist))
        #Generate face adjacencies
        for i in range(20):
            if i <=4:
                self.faces[i].RB = [self.faces[(i+1)%5], "RG"]
                self.faces[i].RG = [self.faces[(i-1)%5], "RB"]
                self.faces[i].GB = [self.faces[i+5], "BG"]
            elif 5 <= i <=9:
                self.faces[i].RB = [self.faces[10+(i-1)%5], "BR"]
                self.faces[i].RG = [self.faces[10+i%5], "GR"]
                self.faces[i].GB = [self.faces[i-5], "BG"]
            elif 10 <= i <=14:
                self.faces[i].RB = [self.faces[5+(i+1)%5], "BR"]
                self.faces[i].RG = [self.faces[i-5], "GR"]
                self.faces[i].GB = [self.faces[i+5], "BG"]
            elif 15 <= i <=19:
                self.faces[i].RB = [self.faces[15+(i-1)%5], "RG"]
                self.faces[i].RG = [self.faces[15+(i+1)%5], "RB"]
                self.faces[i].GB = [self.faces[i-5], "BG"]

        for i in range(20):
            self.faces[i].initHexes()
        for i in range(20):
            self.faces[i].loadAdjacencies()
            self.faces[i].assignTriangles()

    def genTriangleList(self):

        triangle_count = self.subdivisions ** 2
        radius = self.subdivisions /3 + 1
        row = 0
        column = 0
        out = []

        for i in range(1,triangle_count+1):
            r = int(round((1.0/3.0) * (column - row)))
            b = int(round((0.75 + 2*row - 0.5*column)/3.0))-radius+1
            g = int(round((-0.75 - row - 0.5*column)/3.0))+radius-1
            out.append((r,g,b))

            column += 1
            if i == ((row+1)**2):
                row += 1
                column = 0

        return out

    def genHexList(self):

        radius = self.subdivisions /3 + 1
        out = {}

        for r in range(radius):
            x = 0
            y = -r
            z = r
            if (x/2.0 + z <= (radius-1)/2.0 and
                y/2.0 + x <= (radius-1)/2.0 and
                z/2.0 + y <= (radius-1)/2.0):
                out[(x,y,z)] = None

            #Ensures the coordinates are within the triangle

            for i in range(r):
                x = x+1
                z = z-1
                if (x/2.0 + z <= (radius-1)/2.0 and
                    y/2.0 + x <= (radius-1)/2.0 and
                    z/2.0 + y <= (radius-1)/2.0):
                    out[(x,y,z)] = None
            for i in range(r):
                y = y+1
                z = z-1
                if (x/2.0 + z <= (radius-1)/2.0 and
                    y/2.0 + x <= (radius-1)/2.0 and
                    z/2.0 + y <= (radius-1)/2.0):
                    out[(x,y,z)] = None
            for i in range(r):
                x = x-1
                y = y+1
                if (x/2.0 + z <= (radius-1)/2.0 and
                    y/2.0 + x <= (radius-1)/2.0 and
                    z/2.0 + y <= (radius-1)/2.0):
                    out[(x,y,z)] = None
            for i in range(r):
                x = x-1
                z = z+1
                if (x/2.0 + z <= (radius-1)/2.0 and
                    y/2.0 + x <= (radius-1)/2.0 and
                    z/2.0 + y <= (radius-1)/2.0):
                    out[(x,y,z)] = None
            for i in range(r):
                y = y-1
                z = z+1
                if (x/2.0 + z <= (radius-1)/2.0 and
                    y/2.0 + x <= (radius-1)/2.0 and
                    z/2.0 + y <= (radius-1)/2.0):
                    out[(x,y,z)] = None
            for i in range(r-1):
                x = x+1
                y = y-1
                if (x/2.0 + z <= (radius-1)/2.0 and
                    y/2.0 + x <= (radius-1)/2.0 and
                    z/2.0 + y <= (radius-1)/2.0):
                    out[(x,y,z)] = None

        return out

class Icoface():

    def __init__(self, ID, nodepath, subdivisions, hexlist, trianglelist):
        self.ID = ID
        self.nodepath = nodepath
        self.trianglelist = trianglelist
        self.hex = hexlist
        self.RB = None
        self.RG = None
        self.GB = None
        self.subdivisions = subdivisions
        self.radius = subdivisions / 3 + 1

    def initHexes(self):
        for coord, hex in self.hex.iteritems():
            found_copy = False
            copy = None

            #From the way we are iterating through the faces, we will never
            #attempt to init a face with a vertex that has already initialized
            #neighbours that are non-adjacent , so checking the adjacents will
            #find all the existing instances even for the pentagons

            if coord[0]/2.0 + coord[2] == (self.radius-1)/2.0:
                #Tile straddles the GB border. Adjacency type is always BG, so
                #we don't have to worry about that.
                if self.GB[0].hex[-coord[0], -coord[2], -coord[1]] != None:
                    found_copy = True
                    copy = self.GB[0].hex[-coord[0], -coord[2], -coord[1]]

            if coord[1]/2.0 + coord[0] == (self.radius-1)/2.0:
                #Tile straddles the RB border. The transformation to the
                #adjacent vertex will be different depending on the type
                if self.RB[1] == "RG":
                    transform = (-coord[0], -coord[2], -coord[1])
                elif self.RB[1] == "BR":
                    transform = (-coord[2], -coord[1], -coord[0])
                else:
                    print "Undefined adjacency type!!"
                if self.RB[0].hex[transform] != None:
                    if not found_copy:
                        found_copy = True
                        copy = self.RB[0].hex[transform]
                    else:
                        #check if the found copy is the same as the previously
                        #found copy
                        if copy != self.RB[0].hex[transform]:
                            print "Different tiles in pentagon?"

            if coord[2]/2.0 + coord[1] == (self.radius-1)/2.0:
                #Tile straddles the RG border. The transformation to the
                #adjacent vertex will be different depending on the type
                if self.RG[1] == "RB":
                    transform = (-coord[0], -coord[2], -coord[1])
                elif self.RG[1] == "GR":
                    transform = (-coord[1], -coord[0], -coord[2])
                else:
                    print "Undefined adjacency type!!"
                if self.RG[0].hex[transform] != None:
                    if not found_copy:
                        found_copy = True
                        copy = self.RG[0].hex[transform]
                    else:
                        #check if the found copy is the same as the previously
                        #found copy
                        if copy != self.RG[0].hex[transform]:
                            print "Different tiles in pentagon?"

            if found_copy:
                self.hex[coord] = copy
                copy.coordinates[self.ID] = coord
            else:
                self.hex[coord] = Hex(self.ID, coord)

    def loadAdjacencies(self):
        for coord, hex in self.hex.iteritems():
            neighbours = [(coord[0]  , coord[1]-1, coord[2]+1),
                          (coord[0]+1, coord[1]-1, coord[2]  ),
                          (coord[0]+1, coord[1]  , coord[2]-1),
                          (coord[0]  , coord[1]+1, coord[2]-1),
                          (coord[0]-1, coord[1]+1, coord[2]  ),
                          (coord[0]-1, coord[1]  , coord[2]+1)]

            for neighbour in neighbours:
                if neighbour in self.hex:
                    hex.adjacencies.append(self.hex[neighbour])

            if coord[0]/2.0 + coord[2] == (self.radius-2)/2.0:
                #Tile touches the GB border. Adjacency type is always BG, so
                #we don't have to worry about that.
                if self.GB[0].hex[-coord[0], -coord[2], -coord[1]] != None:
                   hex.adjacencies.append(self.GB[0].hex[-coord[0], -coord[2], -coord[1]])
                else:
                    print "Adjacent hex unintialized!!"

            if coord[1]/2.0 + coord[0] == (self.radius-2)/2.0:
                #Tile touches the RB border. The transformation to the
                #adjacent vertex will be different depending on the type
                if self.RB[1] == "RG":
                    transform = (-coord[0], -coord[2], -coord[1])
                elif self.RB[1] == "BR":
                    transform = (-coord[2], -coord[1], -coord[0])
                else:
                    print "Undefined adjacency type!!"
                if self.RB[0].hex[transform] != None:
                    hex.adjacencies.append(self.RB[0].hex[transform])
                else:
                    print "Adjacent hex unintialized!!"

            if coord[2]/2.0 + coord[1] == (self.radius-2)/2.0:
                #Tile touches the RG border. The transformation to the
                #adjacent vertex will be different depending on the type
                if self.RG[1] == "RB":
                    transform = (-coord[0], -coord[2], -coord[1])
                elif self.RG[1] == "GR":
                    transform = (-coord[1], -coord[0], -coord[2])
                else:
                    print "Undefined adjacency type!!"
                if self.RG[0].hex[transform] != None:
                    hex.adjacencies.append(self.RG[0].hex[transform])
                else:
                    print "Adjacent hex unintialized!!"

    def assignTriangles(self):

        # i is triangle index, starting from the apex
        i = 0
        for coordinate in self.trianglelist:
            self.hex[coordinate].triangles.append([self.ID, i])
            i += 1


class Hex():

    def __init__(self, faceid, coordinates):

        self.coordinates = {}
        self.coordinates[faceid] = coordinates
        self.adjacencies = []
        #In the form of [ [faceid, triangle index], [...], .....]
        self.triangles = []
        #Even generations, odd generations
        self.alive = False


def makeIcoface(name='face', radius=1, subdivisions=1):
    '''Make an icosahedron face'''

    format = GeomVertexFormat.getV3n3c4t2()
    vdata = GeomVertexData(name, format, Geom.UHStatic)

    vertex = GeomVertexWriter(vdata, 'vertex')
    normal = GeomVertexWriter(vdata, 'normal')
    color = GeomVertexWriter(vdata, 'color')
    texcoord = GeomVertexWriter(vdata, 'texcoord')


    phi = (1+math.sqrt(5)) / 2

    edgewidth = radius / ( 0.5 * math.sqrt(1 + phi**2))

    d2 = phi * edgewidth
    d = math.sqrt(edgewidth**2 + d2**2)

    vtx_1 = Point3(0, 0, d/2)
    vtx_2 = Point3(edgewidth * edgewidth/(2*d), -d2/2 ,d2 * edgewidth/(2*d))
    vtx_3 = Point3(d2 * edgewidth/d, 0, d2 * edgewidth/(2*d))

    vec_1 = vtx_2 - vtx_1
    vec_2 = vtx_3 - vtx_1
    norm_vec = vec_1.cross(vec_2)

    #Shrinks the triangle to the corner (doesn't actually subdivide)
    vtx_4 = vtx_1 + vec_1 / subdivisions
    vtx_5 = vtx_1 + vec_2 / subdivisions

    vertex.addData3f(vtx_1)
    vertex.addData3f(vtx_4)
    vertex.addData3f(vtx_5)

    normal.addData3f(norm_vec)
    normal.addData3f(norm_vec)
    normal.addData3f(norm_vec)

    color.addData4f(0.5,0.0,0.0,1.0)
    color.addData4f(0,1,0,1)
    color.addData4f(0,0,1,1)

    texcoord.addData2f(0,0)
    texcoord.addData2f(1,0)
    texcoord.addData2f(0.5,edgewidth*0.5*math.sqrt(3))

    #Define triangles
    prim = GeomTriangles(Geom.UHStatic)
    prim.addConsecutiveVertices(0,3)
    prim.closePrimitive()

    geom = Geom(vdata)
    geom.addPrimitive(prim)

    geomnode = GeomNode(name)
    geomnode.addGeom(geom)

    geomnode.setBounds(BoundingSphere(Point3((vtx_1+vtx_2+vtx_3)/3),edgewidth/math.sqrt(3)))

    return geomnode

def makeIcosphere(radius=1, subdivisions=1, shader_on=True):

    sphere = render.attachNewNode('Icosphere')


    face = sphere.attachNewNode(makeIcoface(name='face'+str(0), radius=radius,
                                            subdivisions=subdivisions))
    facecount = 1
    #Generate the angles needed to transform the faces
    phi = (1+math.sqrt(5)) / 2
    d = math.sqrt(1 + phi**2)
    angle58 = math.degrees(math.acos(1/d))
    angle32 = math.degrees(math.acos(phi/d))

    tile_count = subdivisions ** 2
    face.setInstanceCount(tile_count)

    #Place copies of Icoface at the correct locations
    for i in range(1,5):
        newface = sphere.attachNewNode(makeIcoface(name='face'+str(facecount),
                                       radius=radius, subdivisions=subdivisions))
        facecount +=1
        newface.setHpr(i*72,0,0)
        newface.setInstanceCount(tile_count)

    for i in range(5):
        newface = sphere.attachNewNode(makeIcoface(name='face'+str(facecount),
                                       radius=radius, subdivisions=subdivisions))
        facecount +=1
        newface.setHpr(i*72+126,-angle32,180+angle58)
        newface.setInstanceCount(tile_count)

    for i in range(5):
        newface = sphere.attachNewNode(makeIcoface(name='face'+str(facecount),
                                       radius=radius, subdivisions=subdivisions))
        facecount +=1
        newface.setHpr(i*72+18,angle32,angle58)
        newface.setInstanceCount(tile_count)

    for i in range(5):
        newface = sphere.attachNewNode(makeIcoface(name='face'+str(facecount),
                                       radius=radius, subdivisions=subdivisions))
        facecount +=1
        newface.setHpr(i*72+144,0,180)
        newface.setInstanceCount(tile_count)

    #Pregenerate transform vectors
    vtx_1 = Point3(0, 0, d/2) #not real vertices!!!
    vtx_2 = Point3(1/(2*d), -phi/2 ,phi/(2*d))
    vtx_3 = Point3(phi/d, 0, phi/(2*d))

    edgewidth = radius / (0.5 * math.sqrt(1 + phi**2))


    tvec_1 = (vtx_2 - vtx_1) * (edgewidth) / subdivisions#down the left hand side
    tvec_2 = (vtx_3 - vtx_2) * (edgewidth) / subdivisions #left to right along rows
    #tvec_3 = vtx_1 - ((vtx_2 + vtx_3) / 2) #bottom midpoint to apex

    axis = tvec_1.cross(tvec_2)
    axis.normalize()
    rotate_mat = Mat4(2*axis.x*axis.x-1, 2*axis.x*axis.y, 2*axis.x*axis.z, 0,
                      2*axis.y*axis.x, 2*axis.y*axis.y-1, 2*axis.y*axis.z, 0,
                      2*axis.z*axis.x, 2*axis.z*axis.y, 2*axis.z*axis.z-1, 0,
                      0,0,0,1)

    #Uses a test vertex to get the transform
    vtx_4 = Point3(0,0, math.sqrt(edgewidth**2 + (phi * edgewidth)**2)/2)
    test_vtx = rotate_mat.xformVec(vtx_4)
    tvec_3 = vtx_4 - test_vtx

    shader = loader.loadShader("geodesic.sha")
    sphere.setShaderInput("cinfo", PTAFloat.emptyArray(tile_count))
    sphere.setShaderInput("tvec_1", Vec4(tvec_1.x,tvec_1.y,tvec_1.z,0))
    sphere.setShaderInput("tvec_2", Vec4(tvec_2.x,tvec_2.y,tvec_2.z,0))
    sphere.setShaderInput("tvec_3", Vec4(tvec_3.x,tvec_3.y,tvec_3.z,0))
    sphere.setShaderInput("rot_mat", rotate_mat)
    sphere.setShaderInput("radius", PTAFloat([radius]))

    sphere.setShader(shader)

    return sphere

class World(ShowBase):
    def __init__(self):
        ShowBase.__init__(self)

        #Must be multiple of 3
        self.subdivisions = 48

        self.title = OnscreenText(text="HW Instanced Geodesic Sphere Demo",
                                  fg=(1,1,1,1), pos=(-1.3, 0.95), scale=.07,
                                  align=TextNode.ALeft)
        self.atext = OnscreenText(text="Subdivisions = "+str(self.subdivisions),
                                  fg=(1,1,1,1), pos=(-1.3, 0.88), scale=.05,
                                  align=TextNode.ALeft)
        self.atext = OnscreenText(text="R to randomize board",
                                  fg=(1,1,1,1), pos=(-1.3, 0.83), scale=.05,
                                  align=TextNode.ALeft)
        self.atext = OnscreenText(text="SPACE to toggle board",
                                  fg=(1,1,1,1), pos=(-1.3, 0.78), scale=.05,
                                  align=TextNode.ALeft)

        self.sphere = makeIcosphere(10, self.subdivisions)

        self.graph = Graph(self.sphere, self.subdivisions)

        self.hexdict = {}
        self.hexlist = []
        self.colorarray = []

        for face in self.graph.faces:
            self.colorarray.append(PTAFloat.emptyArray(self.subdivisions ** 2))
            for coord, hex in face.hex.iteritems():
                self.hexdict[hex] = 0

        print len(self.hexdict)
        self.neighbourcounts = [self.hexdict.copy(), self.hexdict.copy()]

        self.generation = 0
        self.nextgen = 1

        self.randomizeBoard()
        
        self.activated = False
        #self.activated = True

        self.accept("r", self.randomizeBoard)
        self.accept("space", self.toggleBoard)
        #self.accept("space", self.iterateBoard)
        taskMgr.add(self.iterateBoard, 'iterateBoard')

        #self.base = makeIcosphere(1,1,False)

        #PStatClient.connect()

    def randomizeBoard(self):

        cur_dict = self.neighbourcounts[self.generation]
        #First pass to clear neighbour counts
        for hex, neighbourcount in cur_dict.iteritems():
            cur_dict[hex] = 0

        for hex, neighbourcount in cur_dict.iteritems():
            rand = randint(0,1)
            hex.alive = (rand == 1)
            if hex.alive:
                for adj in hex.adjacencies:
                    #for initializing the neighbourcounts
                    cur_dict[adj] += 1
            #Update triangles
            for entry in hex.triangles:
                self.colorarray[entry[0]][entry[1]] = rand

        #copy to the next generation neighbourcounts
        self.neighbourcounts[self.nextgen]= cur_dict.copy()

        for i in range(20):
            self.graph.faces[i].nodepath.setShaderInput("cinfo",self.colorarray[i])

    def toggleBoard(self):
        if self.activated:
            self.activated = False
        else:
            self.activated = True

    def iterateBoard(self, task):

        if self.activated:

            for hex, neighbourcount in self.neighbourcounts[self.generation].iteritems():
                if neighbourcount == 2 and not hex.alive:
                    hex.alive = True
                    #Since it definitely changed states, neighbourcounts updated
                    #for adjacent tiles
                    for adj in hex.adjacencies:
                        self.neighbourcounts[self.nextgen][adj] += 1
                    #Update triangles
                    for entry in hex.triangles:
                        self.colorarray[entry[0]][entry[1]] = 1
                elif (neighbourcount == 3 or neighbourcount == 4) and hex.alive:
                    #The cell definitely didn't change, so nothing happens
                    pass
                else:
                    #cell dies, check if it was alive and we need to update
                    if hex.alive:
                        hex.alive = False
                        for adj in hex.adjacencies:
                            self.neighbourcounts[self.nextgen][adj] -= 1
                        for entry in hex.triangles:
                            self.colorarray[entry[0]][entry[1]] = 0

            #copy the array
            self.neighbourcounts[self.generation] = self.neighbourcounts[self.nextgen].copy()

            #swop the numbers of the cur generation and the next generation
            self.generation = self.nextgen
            self.nextgen = (self.nextgen + 1) % 2

            #Refresh board
            #turns out this is unnecessary
            #for i in range(20):
            #    self.graph.faces[i].nodepath.setShaderInput("cinfo",self.colorarray[i])

        return Task.cont


app = World()
app.run()

Shader

//Cg
//Cg profile gp4vp gp4fp

struct VertexDataIN{
    float4 vtx_position : POSITION;
    float4 vtx_color : COLOR;
    float2 vtx_texcoord0 : TEXCOORD0;
    int l_id : INSTANCEID;
};

struct VertexDataOUT{
    float4 o_position : POSITION;
    float4 o_color : COLOR;
    float2 o_texcoord0 : TEXCOORD0;
};

//vertex shader
void vshader(VertexDataIN IN,
        out VertexDataOUT OUT,
        uniform float4x4 mat_modelproj,
        uniform float4 tvec_1,
        uniform float4 tvec_2,
        uniform float4 tvec_3,
        uniform float radius,
        uniform float4 cinfo[576],
        uniform sampler2D tex0,
        uniform float4x4 rot_mat)
{
    int row = floor(sqrt(IN.l_id));
    int column = IN.l_id - row * row;
    float4 vpos = (0,0,0,0);
    if ((column % 2) == 1)
    {
        vpos = mul(rot_mat, IN.vtx_position);
        vpos = vpos + tvec_3 + (row+1)*tvec_1 + (floor(column/2)+1)*tvec_2;
    } else {
        vpos = IN.vtx_position + row*tvec_1 + floor(column/2)*tvec_2;
    }

    vpos.xyz = vpos.xyz * radius / length(vpos.xyz);
    
    OUT.o_position = mul(mat_modelproj, vpos);

    float col = cinfo[IN.l_id/4][IN.l_id%4];

    if (col == 0){
        OUT.o_color = float4 (1,1,1,1);
    } else if (col == 1){
        OUT.o_color = float4 (0,0,1,1);
    }
    
    //OUT.o_color = IN.vtx_color / 256 ;

}

//fragment shader
void fshader(VertexDataOUT vIN,
        uniform sampler2D tex0,
        out float4 o_color : COLOR)

{
    o_color = vIN.o_color;
}

#2

Very cool snippet. Though, your classes should inherit from the built-in Python class

object

.

So, for example:

class Hex()

should be

class Hex(object)

Still, that’s pretty minor. Nice job!


#3

Hmm I cut my teeth on Python 3, so I never realised I had to do that.

It was surprisingly effective though.


#4

That’s really a matter of coding style preferences. It’s not required by Python. Most people prefer not to, I think (the Panda code generally doesn’t).

Nice job on the application!

David