Lattice Gasses

I implemented the lattice gas simulations in C with openGL for visualization. So far this is a pretty naive implementation. At 800x600 resolution it can run at 60FPS on my relatively anemic Macbook Air. The code is here, and depends on libglfw3 and libgl. If the dependencies are installed you should be able to compile it by running "make" in the source directory.

Data Structure

In both the square and hexagonal lattices the sites are stored in a byte array, which is treated as an MxN square grid. For the square lattice the sites take values from 0x00 to 0x0f, and in the hex lattice they go up to 0x3f.

Algorithm

The update step for both lattices consists of a collision step and a propogation step. The collision step for the square lattice is a simple table lookup. For the hex lattice there is one wrinkle because of the nondetermistic collisions. To handle these the rule table is doubled, so for a site in state x, there are rules at RuleTable[x] and RuleTable[0x80 | x]. For the deterministic rules the two entries are the same, but for the nondeterministic rules they are different. Handling the nondeterminism is then just a matter of randomly ORing the site with 0x80 or 0x00 before lookup.

The propogation step is a little more complex, and this is where storing the hex lattice in a square grid comes in. The lattice can be stored in a grid, but the resulting distortino needs to be accounted for in the connections between cells. See the below image from Wylie for a visualization of the site links.

To handle the periodic boundary conditions, at the beginning of each propgation step the outer edge of the simulation is copied to the opposite edge. Specifically its actually one layer in that is copied to the opposite outer layer, e.g. in an 8x10 grid, row 2 is copied to row 10, row 9 is copied to row 1, column 2 is copied to column 8, column 7 is copied to row 1, and then the corners are reflected similarly.

Possible Future Work

There are many optimizations that could be made here. One interesting idea is to apply the idea of the Hashlife algorithm, which stores the grid as a quadtree and memoizes the update step. This has huge speedups for Conway's Game Of Life, but is less effective when the CA doesn't have regular patterns.

This also seems very amenable to GPU processing, particularly as the algorithm does not require branching, so SIMD-style parallism is possible.

References

Wylie, Brian James Nisbet. Application of two-dimensional cellular automaton lattice-gas models to the simulation of hydrodynamics. Diss. University of Edinburgh, 1991.