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
- 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.
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)