• Advertisement
Sign in to follow this  

game of life...

This topic is 4338 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey, Do you know Conway's Game Of Life ? Ok, how would you create the data structure to support this? The simplest and most straightforward way would be to just have a huge bidimensional array and pick random values for that array at first (for initialization)... but im sure its not the best way memory and performance wise... any ideas? Thanks

Share this post


Link to post
Share on other sites
Advertisement
I found that using a C styled approach, I got the best performance out of my Life Game I did in SDL. For that, I just used an int * for the board (accessed with the row * NumCols + col forumla) and then used memcpy's to apply the rules. Here's the snippet for that:


void ApplyRules(const int &delay)
{
// Copy the current board into the temporary board
memcpy(mTempBoard, mBoard, size);
for(int r = 0; r < mRows; r++ )
{
for(int c = 0; c < mCols; c++ )
{
int neig = CountNeighbors(r, c);
// Underpopulation
if(neig < 2 )
mTempBoard[r * mCols + c] = mDeadValue;
// Birth
else if(neig == 3)
mTempBoard[r * mCols + c] = mAliveValue;
// Overpopulation
else if(neig > 3 )
mTempBoard[r * mCols + c] = mDeadValue;
}
}
// Copy the updated temporary board into the real board
memcpy(mBoard, mTempBoard, size);
generation++;
}



By using that, I moved the previous bottleneck when I was using a std::vector from the cosntant clears/copys to the graphics package I am using -- SDL, although it seems very fast when working with it. In terms of space, well my method is not that "effective" (Rows * Cols * sizeof(int)) but the advantage I end up getting is simple implementation and quite fast. I'd have to reconsider if I wanted to simulate a "huge" world though.

Have a look for yourself though! Life-Demo (just demo). My code has quite a few extras added in, such as file loading/saving and the like, but for this demo I just threw together (did this project for fun 10/16/05), I just took it out so it's just a core system. Hope this helps a bit, is this a for fun project or does it have a specific purpose (i.e. you are moving into AI programming)?

Share this post


Link to post
Share on other sites
k, thanks for the replies...
Its mainly for fun.

I dont think multidimensional arrays are the only way to go however.
I was thinking of a tree where each node can have a max of 8 childs (one for each adjacent cell). This would remove all the for cycles and the checking of the rules would be pretty simple: if(cell.children.count<2) cell.kill() , etc.

what do u think?

Share this post


Link to post
Share on other sites
Isn't it possible to keep two exactly the same sized bords in memory, then having two pointers called currentBoard and temporaryBoard respectively. Then you would on update switch them and step over each square in the currentBoard, quering for the corresponding number of neighbours in the temporaryBoard? For any other functions after update it's just to check the currentBoard pointer for the most recent board. This way you avoid two memory copies (if that's an issue, shouldn't be anyhow with small arrays).

Share this post


Link to post
Share on other sites
That would be the problem (I think) with using a tree structure. When I put a simple little 2D Life together using arrays I remember finding that you had to work from the current board onto a copy, so that a cell that had just "died" this turn would still persist for the rest of the turn to influence cells around it.

Slightly off topic, I started trying to turn it into a two player game where you ran around firing those

***
*
* (or whatever, you know what I mean)

shape things that move diagonally across the board at each other while avoiding all the live cells but gave up. Shame really. Might have been good.

Share this post


Link to post
Share on other sites
Homework! Seriously, how hard could something like this be? Read your assignment specification more closely.

Share this post


Link to post
Share on other sites
Quote:
Original post by FreJa
Quote:
Original post by EasilyConfused
Did anybody ever come up with a 3D version of Life? Always thought that would be cool.


yeah there are some: http://www.google.com/search?hl=en&q=3d+game+of+life&btnG=Google+Search


There is also a 1D Game of Life. I am only vaguely familiar with it, but I know that Stephen Wolfram (creator of Mathematica) has written some book(s) on the topic.

Share this post


Link to post
Share on other sites
One optimisation I can think of would be that when a square becomes alive, you push it and its neighbours onto a queue. At the end of each generation you remove duplicates from the queue, and then process only squares in the queue next time etc.
Depending upon the percent of squares that are alive, this would probably sometimes end up being slower.
Other ideas are keeping track of a rectangle enclosing the top, left, bottom, and rightmost alive cells, so that your for-loops don't iterate over as many dead cells unnecessarily. In fact, you could have a seperate array that keeps track of the first and last alive cells in each row. You have to be careful to process nearby dead cells properly so that you don't muck things up though.

Seriously though, I think brute-forcing it should be fine. I mean software 3D renders have far more work to do than this. They also draw every pixel each frame, and they can typically draw 640*480 at 20fps without problems. But you have no large textures to worry about, so you can probably get it much faster than this.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by FreJa
Hey,

Do you know Conway's Game Of Life ?
Ok, how would you create the data structure to support this? The simplest and most straightforward way would be to just have a huge bidimensional array and pick random values for that array at first (for initialization)... but im sure its not the best way memory and performance wise... any ideas?

Thanks
An array (or a hash table for the same purpose) is useful and fast for look-up. For iteration you could keep a list (e.g. dynamic array) of all the active cells and only do updates near those, instead of iterating through the entire grid. But if the grid is quite densely packed with material, the fastest way is quite likely to just iterate it from top to bottom (better cache consistency than when using a list of active cells).

Share this post


Link to post
Share on other sites
I wrote a reasonably fast framework for CA once, and I only used 2 multi-dimensional (in my case 2-D) arrays, with two pointers pointing to them (like Unwise owl is suggested above).

One pointer was pointing to the "current" board, and the second was pointing to the "next" (=after 1 step) board. The update function always read the "current" board and wrote to the "next" board. When it finished it swapped the pointers around. The display function always read from the "current" board.

This way I avoided the need to 'memcpy' the whole board after each update, and it saved a lot of time with larger boards.


The second big speed-up came from recycling the results of the neighbour look-up from the last inner step in the update function.

Imagine you are working with a simple Moore neighbourhood (3x3 cells centered around the cell being updated). Traditionally, you would read all 9 neighbourhood cells for each cell you were updating, directly from the board. Now, you have to realise that CPU's cache doesn't really like it when you tell it to read from such distant parts of the memory for every cell you update (in the above case from 3(!) different contigous parts of the memory for each cell).

Now, I figured that if I were to update cells in rows (top to bottom), I could recycle some neighbours from the last neighbourhood look-up and use them to update the current cell, since the neighbourhoods of two vertically adjacent cells overlap. I was storing the current neighbourhood in a 3x3 array, and when I moved down onto the next cell to update it, I simply "shifted" the values in the neighbourhood array upwards by 1.

That way I could recycle 3*(3-1) cells in most cases, and only had to read the 3 bottommost cells of the neighbourhood in 1 chunk from the board (assuming I stored the board primarily left to right). That way no neighbour's value was read more than 3 times from the board each update cycle! The only complication was handling the edges of the board, but it was quite solvable.


I also planned to implement a variation of a quad-tree to quickly discard inactive areas of the board (say, big areas of exclusively dead cells in Game of Life, or inactive parts of the circuit in WireWorld), but never really got around to implementing it.

Roughly speaking, it would work by dividing the board into rectangular segments, each with a "trip-wire" zone around them (the width of this zone would be the same as the "radius" of the neighbourhood in the cellular automata rules). Each segment, whose cells didn't change during an update cycle would be flagged as inactive. Two adjecent segment's "trip-wire" zones would completely overlap between them. If any disturbance occured in the "trip-wire" zone of an inactive segment, it would be automatically activated for the next update cycle. Only active segments and adjacent "trip-wire" zones around them would be actually updated during the update cycle.

If I would've indeed implemented this, I believe it would have resulted in HUGE speed-ups for most cellular automatas (except perhaps for CA's that use constantly changing [quasi-]continuous cell values, like Rug and alike).


Anyway, I do believe an implementation similiar to the above could be considered preety close to optimal. If anybody has any thoughts on how to further improve it, I would love to hear it (really, I would)! :)

Kind regards,
Devilogic

[Edited by - Devilogic on April 6, 2006 6:31:46 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement