cellular automata

Not having a background in computer science, this is probably more of a general programming question than specifically arduino. I'm looking to program a cellular automata model (like conway's game of life) on the arduino to drive an led array. The only problem I foresee is how to simulate parallelism. The only solution I see is to loop through each cell from the same matrix, all the while updating a copy of the matrix for each, change the leds only when all the cells are done, and then switch to the copy for the next iteration. Has anyone whose done this before have any better ideas? Thanks in advance.

The arduino may be more than fast enough so you shouldn’t need to do anything that complicated. How big is your array and how long do you think it will take to calculate an iteration?

I'm not worried about processing power. The issue is sequential vs. parallel programming. Everything we do in arduino is sequential. However, each cell must be updated simultaneously and independently. The technique I've described above should simulate a parallel process, but I think there must be a more elegant (and efficient) solution.

zach, it sounds like you want to simulate parallelism as an exercise rather than because you think your app will needs it. Is that correct?

If not then I think sequential code will look like the processing is done in parallel because a human eye would not be able to detect any time gap from lighting the first LED to the last, unless your array was huge.

If you haven't seen it already you might be interested in what I've done here: http://www.arduino.cc/playground/Main/DirectDriveLEDMatrix (look at the second code example). I use a double buffer exactly as you suggest - without a parallel processing language you're going to have to do things sequentially.

Although, I suppose you could always have one Arduino/AVR chip per cell... See here for a modular solution: http://store.makezine.com/ProductDetails.asp?ProductCode=MKGMLIFE

Andrew

Thanks Andrew, that was exactly what I was looking for. I guess my interest in parallelism is mostly theoretical. Can anyone recommend a reference for simulating parallelism in C?

Isn’t there a project called TinyOS designed for microcontrollers?

There is parallelism (or concurrency) at many levels. There are timers and IO devices running independent of your code on the ATmega.

Forget about external LED drivers for a moment, and assume we can use only Arduino IO pins to make an interesting game. In this case there are two generations “stored” in the ATmega - the one you are displaying, stored in the output pin buffers, and the next generation you are calculating, probably stored in some RAM.

For a more complex case, where you are lighting the LEDs momentarily using some sort of matrix (and relying on persistence of vision to make them seem continuously on), you can call your “LED update” function frequently, between calculations. for example:

for (i=0; i<MAX; i++)
    for (n=0; n<MAX; n++)
        {
            do_something(data[i,n]);
            display_output(old_data);
         }

This is some manual timeslicing to make it appear your program is doing two things at once.

One thing that I have to really think about when I am using electronics to interact with the physical world is time - a few instructions (or a few thousand) can execute literally in the blink of an eye. I would guess that your game of life project would need some very long sleeps between generations to make the output visible to the user - otherwise, the LEDs would just sort of glow dimly until the game reaches a steady-state.

My advice would be to try it and see what happens. If it’s too complex, you can always use another Arduino as a display processor.

-j