DODonHopkins·Feb 13, 2025
In this recent discussion of "SimCity in the web browser using WebAssembly and OpenGL (micropolisweb.com)", I posted a description of a couple of general purpose cellular automata optimization techniques for CPUs (which don't apply to GPU cores working in parallel, but optimize the edge condition branching and memory bandwidth of a serial scanning CPU implementation). I used both techniques in my CAM6 simulator, and the SimCity/Micropolis code, to run CA in SimCity's tiles.
The edge condition optimization eliminates the eight conditional branches in the inner loop checking for edge conditions, and the memory optimization eliminates six out of nine loads per cell in the inner loop.
Here are the comments about optimization from the CAM6 code:
https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...
// Optimization Techniques
//
Read the rest
// Extra copying is eliminated by swapping between two cell buffers,
// one for the past and the other for the future. After applying the
// rule, the past cell buffer becomes the future, and the future
// becomes the past. It's necessary to have two buffers, because
// you can't apply cellular automata in-place in one buffer, since
// you would stomp on your past neighbors whose future you just
// computed, since the neighbors above and to the left would be
// from the future instead of the past.
//
// Edge conditions eliminated from inner loop by making cell buffers
// two cells wider and taller, and wrapping edges around to the
// extra edge cells before applying rule, so the inner loop does not
// have to check for edge conditions to wrap the cells, and other
// edge treatments can be applied besides wrapping, like clamping or
// reflecting.
//
// Index table lookup based rules, that allow you to define rules in
// JavaScript in terms of their neighbors, which are then applied to
// every possible combination of neighbor states, to generate a
// lookup table that is used by the neighborhood to evaluate the
// rule without running a lot of JavaScript code. This is how the
// CAM6 hardware works, and the rule tables are compatible with its
// rule tables. The hardware concatenates the bits of the neighbors
// into an index that is used to look up the next cell value in the
// lookup table. It's not clear if this is actually any faster in
// software, because it's a software emulation of a hardware
// optimization, and depends a lot on the rule and the code that
// implements it, but at least it lets you write your rule
// definitions clearly without worrying about efficiency, and also
// translate the Forth rules defined in the Cellular Automata
// Machine to JavaScript (or use old rule tables generated by Forth
// if you can find them), and run them in the simulator.
//
// JavaScript code templates for neighborhood functions, rules,
// tools, colormap generators, etc, with slots that let rules inject
// custom code into the inner loop, disable unnecessary code,
// calculate parameters, inline constants, etc. This enables
// neighborhoods to be much more general purpose, and not only
// deeply parametrizable but also arbitrarily extensible,
// supporting complex rule definition, as well as real time analysis
// and event reporting (like the cell value histogram). And it also
// enabled users to play around with writing their own rules and
// modifying and extending existing ones, and they will still run
// efficiently.
You can play with the SimCity/Micropolis CA by disobeying the important safety warning about not opening up the Space Inventory, by pressing the space bar a few times:
https://micropolisweb.com
Here's a video I recoded of playing around with that to music:
SimCity Micropolis Tile Sets Space Inventory Cellular Automata To Jerry Martin's Chill Resolve:
https://www.youtube.com/watch?v=319i7slXcbI
The musical style of "Chill Resolve" may ring a bell, because Jerry Martin is the musician who composed the music for The Sims and SimCity 2000 and many other Maxis games, and he has some more great free music on his web site:
https://boombamboom.com/
And here is a longer demo that explores some of the more subtle effects, starting out with an homage to "Powers of 10", with some more great music by Juho Hietala, Blamstrain:
Micropolis Web Space Inventory Cellular Automata Music 1:
https://www.youtube.com/watch?v=BBVyCpmVQew
The space bar randomly toggles between two CA rules (one heat diffusion with randomized parameters, and one combination of Anneal, Life, and Brain's Brain).
Here's the code that implements the cellular automata running in SimCity's 16 bit tile memory. I originally wrote it a long time ago in C on a 68k Sun 3 Workstation, so it uses some terribly ugly C macrology. This code is written in C++ and compiled to WebAssembly, and is adapted to deal with SimCity's in-memory tile layout that doesn't have an gutter around it, so it performs an extra copy, so isn't optimal. But if you were implementing a pure optimized cellular automata not duct-taped and bailing-wired into an existing game, you could just use two buffers of the same size with gutters around them, and swap their pointers each iteration, to eliminate the extra copy of all the cells, of course:
https://github.com/SimHacker/MicropolisCore/blob/main/Microp...
The heatWrap parameter switches between different edge condition wrapping/clamping modes applied to the gutters, defaulting to 4, which wraps the edges around like a torus.
You can play with the CAM6 emulator here, which is written in JavaScript. Click the square in the upper right corner to show the controls, and switch the rule to Life, but it has many other rules too:
https://donhopkins.com/home/CAM6
Here's the source code of a hard-coded Life rule (with some bonus features like running a heat diffusion in parallel in the upper bits, and rotating the scanning order to cancel out the heat diffusion dithering artifacts):
https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...
There is another lookup-table based implementation of Life that is compatible with the way the CAM6 hardware works. It uses a Moore neighborhood. This code snippet is not run in the inner loop, it's run over all possible input configurations to generate a lookup table that is used by the generic Moore neighborhood code. So it doesn't need to be optimized because it runs outside of the inner loop:
https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...
// ruleFunction_Moore_life computes the life rule Moore
// neighborhood lookup table.
function ruleFunction_Moore_life(ruleDict, state) {
var sum8 =
ruleUtil_Moore_sum8_0(state);
if (state.c0) {
return (((sum8 == 2) ||
(sum8 == 3))
? 1 : 0);
} else {
return ((sum8 == 3)
? 1 : 0);
}
}
There's some other rule compiler code that calls that function repeatedly over all possible permutations of neighbor states in ruleDict, to generate the lookup table, that's used by the Moore neighborhood (which itself also has some fancy optional features):
https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...
Moore neighborhood explained:
https://en.wikipedia.org/wiki/Moore_neighborhood
Here's an in-depth technical demo that I recorded for Norman Margolus explaining how it was inspired by his book and how it works:
https://www.youtube.com/watch?v=LyLMHxRNuck
Here's the technique for reducing the number of memory loads per cell in the inner loop from 9 to 3. For each row you "prime the pump" by loading the right two columns of a 3x3 window, and then for each cell you scroll the window to the left and load the three incoming cells.
for (var cellY = 0;
cellY < height;
cellY++) {
// Load the right two columns of the 3x3 window.
n = cells[cellIndex - nextCol - nextRow]; ne = cells[cellIndex - nextRow];
c = cells[cellIndex - nextCol ]; e = cells[cellIndex ];
s = cells[cellIndex - nextCol + nextRow]; se = cells[cellIndex + nextRow];
for (var cellX = 0;
cellX < width;
cellX++) {
// Scroll the 3x3 window to the right, scrolling the middle and right
// columns to the left, then scooping up three new cells from the right
// leading edge.
nw = n; n = ne; ne = cells[cellIndex + nextCol - nextRow];
w = c; c = e; e = cells[cellIndex + nextCol ];
sw = s; s = se; se = cells[cellIndex + nextCol + nextRow];
Here's the explanation of the edge condition gutter optimizations that I posted recently:
https://news.ycombinator.com/item?id=40701784
DonHopkins 8 months ago | parent | next [–]
Amazing!
Decades ago, Will Wright suggested to me a nice optimization for cellular automata and convolution filters that lets you eliminate the bounds checks in the inner loop, which I implemented in my CAM6 cellular automata machine simulator:
Eliminate the edge conditions (and conditionals in the inner loop) by making a "gutter" of one extra pixel (or however many pixels your neighborhood extents out) around all the edges of the bitmap (i.e. increase the width and height by 2, then inset x and y by 1), then before processing each frame, copy the appropriate edges into the corresponding gutters (wrapping or clamping), then iterate over the pixels just inside the gutters, so you don't have to perform any bounds checks.
https://github.com/SimHacker/CAM6/blob/master/javascript/CAM...
[...see Optimization Techniques comments above...]
You can either wrap the cells into the gutter from the opposite edge like a torus, which makes nice seamlessly tileable patterns, or in the case of something like SimCity pollution diffusion, you can just clamp the pixels into the gutter along the same edge.
Shaders have a way of wrapping and clamping and mirroring automatically (wrapping modes):
https://webglfundamentals.org/webgl/webgl-3d-textures-repeat...
But on old school consoles you have have to use software tricks like that instead of relying on the hardware.
And of course if you're using power of two sized bitmaps you can just mask the coordinates, which is practically free.
You could fix SimCity to use that trick, but it would make the code more complex, and it's probably not worth it on anything but really old hardware like the C64 or Sega Dreamcast.