algorithmlanguage-agnosticsynchronizationautomataartificial-life

Wa-Tor like cellular automata. In which order should the cells be updated?


Some time ago I've written a Wa-Tor like cellular automata (see Wikipedia) but with a few more species and a little smarter species. Except for a lot of fine tuning to get a stable system it was quite simple and worked well. However since that time I'm asking myself (and now you) how to update the cells "realistically".

My 'world' was a grid and was always updated from the top-left to the bottom-right. IMO that also means that the cells that are closer to the top and left are always faster. So e.g. a fish in cell [3, 3] can be eaten by a shark in [3, 2] before being updated. If the cells would have the opposite positions the fish would always escape from the shark since it can move away from the shark before it is updated.

Am I correct that this is a 'problem' (or at least unrealistic)?

IMO in a realistic setting all cells should be updated simultaneously but I don't know how to implement something like that. Another method I can imagine is to evaluate the cells in a 'shuffled' order.

How would you solve this problem / how are such problems usually solved?


Solution

  • As @Rogach mentions, simultaneous updates won't work. Because your cellular automata is non-deterministic, two fish won't know the next position of each other and may collide.

    I think the best solution, given that your cellular automata is non-deterministic, is to update your grid in a non-deterministic way, ie. randomly. Pick random cells to update. Either pick cells randomly and keep track of which one's you've updated, so each cell is updated exactly once per tick, or pick cells randomly and don't bother keeping track. The second approach would be easier, but risks some cells being updated slightly more often. On average all cells would be updated the same amount, if you had an evenly distributed random function.