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(n
3) time and produces approximately n
2 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