3

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?

katzenversteher
  • 810
  • 6
  • 13

2 Answers2

1

IMO in a realistic setting all cells should be updated simultaneously but I don't know how to implement something like that.

This is the approach I would suggest. Have two grids, an 'old' one and a 'new/current' one. When calculating the next generation, base your calculations on the old grid, and write your results to the new grid. Then display the new grid. Now swap the pointers so that the new grid is now the 'old' one, and the old grid becomes the new grid. Repeat.

Aaron J Lang
  • 2,048
  • 3
  • 20
  • 27
  • But what if two fishes decide to go to the same cell on the same turn? – Rogach Jan 15 '12 at 12:44
  • @Rogach good point, I was basing my answer on my experience with Conway's Game of Life. You're right, I don't think the same approach would work here. – Aaron J Lang Jan 15 '12 at 13:14
  • I was also thinking of something like that first but as mentioned by Rogach that can lead to some tricky situations. Maybe it would be possible to do it in multiple steps. Like: First plan what they want to do (move, eat, breed etc.), then update the new grid with actions that did not cause conflicts and then resolve all conflicts until no conflics are left. The big question then is how to resolve such conflicts... – katzenversteher Jan 17 '12 at 13:44
1

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.

Aaron J Lang
  • 2,048
  • 3
  • 20
  • 27
  • This would also be my preferred way. But since affenlehrer also mentioned "a little smarter species", random updating would make writing an AI a bit more difficult :) – Rogach Jan 15 '12 at 14:07
  • 1
    And by the way - the "don't bother keeping track" way may be better for "realistic" approach - after all, each animal moves at different speed in real world :) – Rogach Jan 15 '12 at 14:09
  • Sorry for the late reply... That sounds better than the approach I used! I was also thinking about the difference between lifeforms and cells. If I would have a list of individuals that have to be updated (no matter on which cell they life) then shuffeling the list and updating each of them could work too. However I'm not sure if that would still be regarded a CELLular automata. On the other hand, if I would do that with the cells it's indeed possible that the same individual (but not the same cell) is updated several times... – katzenversteher Jan 17 '12 at 13:38