Cellular automaton rule with 6-neighbourhood

For a regular grid it is easy to do a simulation based on rules. Each rule should be applied to each grid cell to change the state of the cell. In our case the grid is a 3D voxel array. If there is a single output of which state the cell should have this whole thing would be called cellular automaton.

We changed this to multiple input multiple output rules to be faster and more flexible.

Automaton rule with multiple output

Why faster? In a normal cellular automation on each cell each rule has to be applied, because e.g. an empty cell could get anything in the next step. For 300 x 60 x 300 world with 10 species this causes 54,000,000 rule computations per simulation step. We decided to simulate 4 steps per second...
So we changed the point of view: Only a few living cells of a known type are simulated. These can  change their neighbourhoods too. Therefore an empty cell could be filled and the automaton can basically do the same thing as before. Now we are just simulating at most 5,000 cells and apply exactly one rule depending on the voxel type. This is less than before by a factor of >10,000.

Why should the multiple output structure be more flexible? In a standard automaton it would be necessary to create rules for any possible neighbourhood of different voxel types. For a 3 x 3 x 3 area this means to write rules for 27^10 different settings. Of course we could group them but it is stell not feasible. The new view allows to write rules per species. To fill the gab of the remaining 26^10 rules per species rules can be written generic and are allowed to return don't cares.

Example for a simple beetle rule: Iterate over all neighbours and count the empty cells. If there is at least one empty cell choose one of them randomly. Return EMPTY for the current cell and BEETLE for the chosen cell.

Rule for a flying beetle (most boxes on the right side are don't cares)

From a local rule to a more global decion

Until now a rule sees only a 3 x 3 x 3 region and has to make decisions on that. Using larger regions would only make things much more complicated. So we added more information as "resources" and "generation" to the living voxels. It is therefore possible to now the distance to the last branch in a tree or things like that. The usage and maintenance of these information depends on the type specific rules.

Summary

The Voxel Seeds automaton implementation maintains a 3D voxel grid with one byte type information per cell. Additionally it holds a list of living voxels with further information. Four times in a second all living voxels are simulated in parallel to the rendering, input handling, .... So a simulation could take 0.25s before the game would be slowed done. After each step an incremental update of all changed voxels is pushed to the GPU synchronously.

We are very happy with the performance and behavior of our small rule sets. Remember: all this was designed and implemented in 48 h on one weekend.