Game Of Life + Marching Cubes

Adam Spurgin

CSC 471: Spring 2013

Conway's Game Of Life

The Game of life is a cellular automaton simulation of a set of rules developed by John Horton Conway in 1970. Typically 'played' in a 2d
field, the game of life generates many interesting patterns based on a set of simple rules, such as:
  • Any live cell with < 2 live neighbors dies, as if by under-population.
  • Any live cell with 2-3 live neighbors lives on to the next generation.
  • Any live cell with > 3 live neighbors dies, as if by overcrowding.
  • Any dead cell with exactly 3 live neighbors becomes a live cell

These rules produce many interesting phenomena, such as "gliders", periodicly stable microsystems, and configuations that spawn other automata.
In my version of this game, it takes place in 3 dimensions and follows the following rules:
  • Any live cell with < 5 live neighbors dies, as if by under-population.
  • Any live cell with 5-7 live neighbors lives on to the next generation.
  • Any live cell with > 7 live neighbors dies, as if by overcrowding.
  • Any dead cell with exactly 5 live neighbors becomes a live cell

Marching cubes

Marching cubes is an algorithm used to fit a generalized geometry to a scalar field of values. The large number of possible polygon configurations are usually handled through lookup arrays. The algorithm 'marches' through each unit volume in the space and processes the values of each point in it. This algorithm runs in O(n3) time and produces approximately n2 polygons, where n is the length of one dimension of the volume being processed (width, diameter, etc...).

Controls

w forward
s backward
a left
d right
p toggle sphere demo
f toggle wireframe
space stop(red b.g.)/go(green b.g.)
click+drag look

Using

build with make, run produced executable.

Tricks and techniques

This application could get very resource intensive very quickly, so I had to take various steps to keep performance acceptable.
  • The game itself is based off a map storage system with the coordinate for each cell being the key. This reduces the proccessing time used to calculate the next 'turn' to a bare minimum by only processing active cells (the ones in the map). As a tradeoff, this method has slightly larger overhead costs and potential memory footprint.
  • The active game area is restricted to a 20x20x20 area centered around the origin. With the map implementation I used, It is theoretically possible to have a nearly boundless game, but for performance reasons, this must be limited.
  • In order to prevent creating a new vertex buffer for each polygon, a single triangle polygon was used with dummy identifier values used the place of the traditional vertex position values. 3-length vectors were then passed in as uniform values to the vertex shader, and depending on the vertex being processed, a difference value was chosen for the vertex location.

New graphics related things I did for this project

  • Marching cubes algorithm
  • Improved keystroke recognition; It toggles keys in a bool array on and off, using each tick to check the status of all currently pressed buttons. The result is much smoother navigation in space and the ability to have multiple different buttons being registered as pressed at the same time
  • Went against the norm of using the vertex buffer object as solely a position/normal info carrier. Instead I used it as an indexer, and passed vec3's as uniforms to generate every possible triangle from one buffer. This seemed to have a noticible difference iin performance over generating a new VBO for every polygon.
  • I tweaked shaders to make the shapes produced by the game to stand out more, darkening faces on the edge of shapes, and highlighting differences in depth with color
  • Used baysian coordinates to create my own highly anti-aliased, GPU accelerated, wireframe

Additional images