What algorithm can I implement to speed up some Cellular Automata simulations?

Question

I am writing a ncurses based C.A. simulator for (nearly) any kind of C.A. which uses the Moore or Neumann neighborhoods.

With the current (hardcoded and most obvious [running state funcs]) the simulation runs pretty well; until the screen is filled with 'on' (or whatever active) cells.

So my question is: Are there any efficient algorithms for handling at least life-like rules? or Generations, Weighted life/generations...

Thanks.

Answer 1

I think writing state machines is not as much algorhitms designing problem as is just problem how to write clean and "bug free" code. What are you probably looking for is implementation of cellular automata / state chart.

http://www.state-machine.com/ //<- no this is not coincidence http://www.boost.org/doc/libs/1%5F40%5F0/libs/statechart/doc/index.html

You might also try whit stackless python http://stackless.com/. It can be used for state machines or CA. Here http://members.verizon.net/olsongt/stackless/why%5Fstackless.html#the-factory it is tutorial for stackless implementing factory process simulation

Answer 2

it's generally nice to only run update passes in areas of the grid that had activity in the previous time step. if you keep a boolean lattice of "did i change this time?" for each pass, you only need to update cells within one radius of those with an "on" in the change lattice.

Answer 3

You could look into the HashLife algorithm and try to adapt its concept to whatever automata you are working on.