# Consistent Simulation of Cellular Automata on Infinite Grid

Let's say that you have an infinite grid of cells.

A program is run per cell, where you have read access to some finite number of cells (for the previous state in time), but you only have write access to the specific cell you being run on (for the next state in time).

The program reads cell data about the LAST state of the infinite grid, and writes that happen are for the NEXT state of the infinite grid.

In that setup, let's say that each cell has a cell type, and there is a set of logic for how cells behave based on their immediate neighbors (the 8 neighbors in the 8 cardinal directions).

Giving some real world properties to these abstract cells, lets say that cell types include...

• empty space
• stone
• sand
• water
• many others

Then, let's say you have logic like this:

• empty space does nothing
• stone does nothing
• if the cell below sand is empty, it will move there. Else it will try moving down left and down right.
• water has the same rules as sand, but if it wasn't able to make a move using that logic, it will try to flow to the left (simplification of the actual logic)
• more complex logic, like a seed might absorb neighboring water cells, and sprout a plant after absorbing 3 water cells.

Is there a way to craft the per-cell program that runs such that you get a simulation consistent with a rule set like the above?

A problem I'm hitting is in the case below, where black is empty space, stone is white, and water is blue. The water on the left wants to go to the lower right, and the water on the right wants to go to the lower left.

The program running for the water on the left says "I'm moving down and to the right, so I'm erasing my cell" and clears out it's cell.

The program running for the water on the right says "I'm moving down and to the left, so I'm erasing my cell" and clears out it's cell.

The program running for the destination cell that they both want to move to runs and checks both up and left for a water cell and up and right for a water cell, but ultimately has to pick one as the winner (whichever if statement comes first).

It clones that cell and since both cells were cleared when their program runs, one water "cell" has vanished.

The problem is, that the water cell on the right has to know what the water cell on the left is going to choose, but doesn't have all the information the left water cell has when making it's decision. It could get THAT information, but this is recursive, so you then need to have knowledge of the entire previous state of the infinite grid to make a decision about how to act.

Is there a way to constrain this problem to give reasonable results (no particle destruction / cloning for example) while only having limited knowledge of the rest of the grid?

As a practical requirement for such a solution, each cell effectively has the storage of 4 real numbers, so you couldn't just do something like store how much of each particle type is present per cell by having a real number per particle type, since there are numerous particle types. This is being implemented within a pixel shader for what it's worth.

Thanks!

Edit: Here's a diagram referring to what I think makes Yuval's answer not work. It would be nice to be wrong though!

Yuval's proposition is that water can move down, and down right, without needing any extra protection. If moving down left, it would look at the information for it's nearby neighbors and determine if something else wanted to move to that spot too (looking in the upper left quadrant I'd guess!), and if there was a conflict, don't do the move.

The problem is that in this case, if we are considering what way water particle $A$ wanted to move, we would have to figure out how particle $B$ wanted to move to know if there was a conflict. In this case, the way particle $B$ wants to move is based on how particle $C$ moved which is based on the particle to the left. It continues possibly infinitely to the left, so I'm saying you'd need to possibly do an infinite number of reads to figure out whether there was a conflict or not.

(Note, i have read access to the previous state of the grid, and write access to the next state of the grid, but not read access to what other cells have written so far. If that is where the misunderstanding is, sorry for not making that clearer)

• How would you simulate infinitely many cells? – Yuval Filmus Jan 23 '16 at 23:27
• All go to one direction, but at the boundaries (you probably have them) water stays because pipe is blocked due to flow from another source? The problem is with one blocked cell and lack of resolution what to do without looking at all cells. – Evil Jan 23 '16 at 23:33

As your example shows, the specific rules you gave aren't self-consistent.

Is it possible to modify the rules to come up with some other set of rules that will be self-consistent? Yes. There will be multiple ways to do it; there's not a single correct answer. For instance, one possible approach is to artificially impose an order in which you apply the rules. For your set of rules, something like "scan the cells from bottom to top, right to left, and determine the new value of each cell as you scan over it" might suffice, though there's no guarantee that will always work. Another possible approach is to impose some order on the "particles", and process each particle in that order (figuring out where it will move); this essentially resolves any conflicts in favor of particles that appear earlier in the order.

As a side note, this isn't a cellular automaton (CA). For a CA, the contents of a cell $c$ at time $t$ are a function of the contents of the cells in a small neighborhood around $c$ at time $t-1$. Notice that there is not necessarily any meaningful notion of "particles" in such a system.

• I don't have the ability to change what order of execution unfortunately. Do you have any suggestions for making it consistent otherwise by chance? – Alan Wolfe Jan 23 '16 at 5:18

One way to solve your problem is as follows:

• Each water cell is aware of its immediate neighbors.
• Each water cell tries to propagate downwards. If it wants to propagate down left and there is a conflict, then it stays put. (If it wants to propagate down right then there is no problem.)

This symmetry breaking rule ensures that there are no conflicts, and can be implemented locally.

One thing missing in this solution is which way a water cell chooses to propagate if it has several options. There are many possible choices, and it's up to you to decide which one to use.

• Thanks Yuval. If I only have read access to the last state (which I do unfortunately), its possible the water to the left may be able to go down left or down right, so would possibly be based on a particle out of sight of the current cell. This can extend to the left infinitely so I don't think I can know if there is a conflict ): – Alan Wolfe Jan 23 '16 at 15:53
• @AlanWolfe, I don't understand why Yuval's approach won't work. Seems like you only need to be able to see cells 1 or 2 away (assuming each particle can only move one position per unit of time). – D.W. Jan 23 '16 at 22:43
• Right, but to know if the other water particle is going to move where the current water particle wants to move, you need to have all the information it has when making the choice. Since that particle similarly could be based on information further to the left out of view you'd potentially need an infinite amount of reads to the left to know if there would be a conflict or not. – Alan Wolfe Jan 23 '16 at 22:51
• @AlanWolfe I beg to differ. – Yuval Filmus Jan 23 '16 at 22:56
• I hope you are right, I'll make a diagram for us, one minute – Alan Wolfe Jan 23 '16 at 22:57