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:
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;
}