Game Of Life 3D

I had to implement Game of Life in a 3D matrix (int a[ ][ ][ ]) , but the complexity of my implementation is O(n^6) (6 imbricated for) and it runs very slow . Can anyone help me with an optimized version of Game of life , even with a 2D matrix . Or how the Game of Life in general could be optimized ?

he first place to start with optimisation is to have clear goals for the desired performance. "As fast as possible" is not precise enough, or at least is too expensive; basically it means "buy a grid of weather computers" which probably runs into $000,000,000's. Also that may end up being too fast; with Life you often want to watch what's going on. And without a precise goal you have no way of knowing when you've succeeded, which at this stage isn't important, but when you start using these skills in the workplace you need to know when you're there.

So a good goal would be to define a maximum number of frames per second you want. For example you may decide 10 generations per second (one generation per frame) will be sufficient, so that you can watch the simulation unfold.

A number of frames per second gives you the time each generation needs to take. 10 fps = 100ms per frame. Obviously measurement is next: how many fps do you get?

The next place to go is with a code profiler to find out where it's spending its time, and that will point to what you have to optimise. Many decent development kits come with profilers, and there are separate profilers available too. Obviously this will depend on what OS and compiler you're using, which you haven't said.

Having said that though, there are a number of culprits which are immediately obvious:

Display code can be very slow, so make sure you're only drawing what you have to. Don't redraw a cell if its new value is the same as its old value. Check first that display code really is slow though! If you're just blatting cells out to a terminal, or if your computer has separate display hardware then it might not be an issue.

Have two arrays, one for the old values and one for the new. Don't try to use the same array for both, this leads to more computation which leads to slower performance. Have a separate array for the new values then you won't have to untangle the old values from the new all the time.

Do you look at each cell and count its neighbours? This will obviously lead to each cell being looked at 26 times (8 in the plane plus 9 in each neighbouring plane), whether its alive or not. Try initialising all next generation counts to zero, then parsing the current generation array just once, and for each cell that is alive increment its 26 neighbours' counts.

If you wrap around and thus have a lot of "if a<0 a=MAX-1; if a>=MAX a=0" type code, try duplicating the boundaries. A visual representation can be easier: if you have [a b c d e], then obviously to get the next value for a you need to consider e, and so you might loop i from 0 to 4 checking each time if i is 0 or 4 and wrapping round if you need to. If instead you have [e a b c d e a] and loop from 1 to 5, then you only need to consider i-1 and i+1 at each step, and you lose all that tedious wrapping round.

In one game of life I wrote these 4 accounted for a massive performance increase, even given that this requires (a) that you start with an initial count set of zeros and (b) you have to parse the counts afterwards to find out whether each next gen cell is alive or not (however you can roll these two up into the same loop, which helps).

Can u share ur code? I think I can help u