Jump to content
  • Advertisement
Sign in to follow this  
Bromordra

Speed issues in game of life.

This topic is 2927 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

Howdy everyone. For my current project I decided to hack together a quick and dirty implementation of Conway's Game of Life. I got the program to work perfectly smoothly, but I noticed when I modified the game to run with a higher cell resolution, I get huge slowdowns in calculating the generations. It tends to get unuseable when the cell array is about 200x200.

I know it's all to do with the blinding inefficiencies of my implementation, which is pretty much brute-force. Any help with speeding it up would be more than appreciated.



if ((Keyboard.GetState().IsKeyDown(Keys.A) && NewGenerationReady) || Keyboard.GetState().IsKeyDown(Keys.S))
{
NewGenerationReady = false;

for (int i = 1; i < (Window.ClientBounds.Width/8)-1; i++)
for (int j = 1; j < (Window.ClientBounds.Height/8)-1; j++)
{
CellArray[i, j].neighbors = 0;
if (CellArray[i - 1, j].alive)
CellArray[i, j].neighbors++;

if (CellArray[i - 1, j - 1].alive)
CellArray[i, j].neighbors++;

if (CellArray[i - 1, j + 1].alive)
CellArray[i, j].neighbors++;

if (CellArray[i + 1, j].alive)
CellArray[i, j].neighbors++;

if (CellArray[i, j - 1].alive)
CellArray[i, j].neighbors++;

if (CellArray[i + 1, j - 1].alive)
CellArray[i, j].neighbors++;

if (CellArray[i + 1, j + 1].alive)
CellArray[i, j].neighbors++;

if (CellArray[i, j + 1].alive)
CellArray[i, j].neighbors++;
}

foreach (Cell c in CellArray)
{
if (c.alive)
{
if (c.neighbors == 2)
c.alive = true;
else if (c.neighbors == 3)
c.alive = true;
else
c.alive = false;
}
else if (!c.alive)
{
if (c.neighbors == 3)
c.alive = true;
}

}
}




Current implementation of the game, at least the part relevant to this question.

[Edited by - Bromordra on December 11, 2010 2:23:44 AM]

Share this post


Link to post
Share on other sites
Advertisement

if (c.neighbors == 3)
c.alive = true;
else if (c.neighbors == 3)
c.alive = true;







Go through your code and fix glaring issues first plz :)

Anyway, the swath of if statements that find neighbors can be reduced to:

for (int i = 1; i < (Window.ClientBounds.Width/8)-1; i++)
for (int j = 1; j < (Window.ClientBounds.Height/8)-1; j++)
{
CellArray[i, j].neighbors = 0;
for(int k = -1; k<= 1; k++)
for(int m = -1; m<= 1; m++)
if(!(k==0 && m==0) && CellArray[i + k, j + m].alive)
CellArray[i, j].neighbors++;
}
}




Share this post


Link to post
Share on other sites
derp derp derp derp

Sorry, that was simply an artifact from when I was tweaking around the ruleset to experiment with different CA rules. There's no real flaw with the code. I'll change it back to the proper implementation now.

Also, thanks much for the implementation change, looks very, very much cleaner and faster and makes me feel like a damn fool for not thinking it up sooner.

Share this post


Link to post
Share on other sites
Erm... sorry for all the edits, I should really check my code before submitting :)
Anyway, theres probably ways to optimize it, but I'm too tired...
Good night!

Share this post


Link to post
Share on other sites
How about keeping track of all the living cells and then adding them and all their neighbors into a set. Then running the algorithm on the set. This would eliminate the need to check cells that aren't alive without alive neighbors.

Share this post


Link to post
Share on other sites
Though this is kinda more advanced, you might get some good information out of reading about the Hashlife algorithm. There is an implementation called Golly that you can look at as well.

Share this post


Link to post
Share on other sites
Okay, so I tried to do a combination of what Ninja and xytor suggested. Here's the code I came up with

[source lang=c#]
for (int i = 2; i < (Window.ClientBounds.Width / 4) - 2; i++)
for (int j = 2; j < (Window.ClientBounds.Height / 4) - 2; j++)
{
if (CellArray[i, j].alive)
{
if(!ActiveList.Contains(CellArray[i,j]))
ActiveList.Add(CellArray[i, j]);
for (int k = -1; k <= 1; k++)
for (int l = -1; l <= 1; l++)
{
if (!(k == 0 && l == 0) && CellArray[i + k, j + l].alive)
CellArray[i, j].neighbors++;
for (int m = -1; m <= 1; m++)
for (int n = -1; n <= 1; n++)
if (!(m == 0 && n == 0) && CellArray[i + k + m, j + l + n].alive)
CellArray[i + k, j + l].neighbors++;
if (!ActiveList.Contains(CellArray[i + k, j + l]))
ActiveList.Add(CellArray[i + k, j + l]);
}
}
}



The problem is, now the program doesn't work. I believe it has something to do with me not properly checking for neighbors somewhere, but I do not know where the problem is.

Share this post


Link to post
Share on other sites
I was wondering recently if this sort of thing could be sped up by doing calculations with a fragment shader somehow? I'm just learning how to write shaders so I haven't gotten so far as to actually get one working properly but I wrote a generic implementation on the 4-neighbor von neumann neighborhood (ie the rule was arbitrarily set with a 16-bit rule) but had the same problem on resolutions above ~500x500. It used bitwise operations and OpenGL bitmap drawing.

Share this post


Link to post
Share on other sites
Thats not what I meant exacly.
Once a cell is made active add it to a list, once it dies remove it from said list. This is very fast to do. Now with this list create a set by adding all the cells that are in the list and all their neighbors. A set can only contain one instance with a specific data combination. For example if 1,2,2,3,3,4,4,6,6,1,1 was added to a set it would contain 1,2,3,4,5,6.

Then you only need to update all the cells in the set.

Just to make myself clear.

class Cell{
private:
static vector<Cell*> active_cells;
bool alive;
public:
setAlive(){ active_cells.add(this); alive = true; }
setDead(){ active_cells.remove(this); alive = false; }
}

Kinda like this.

Share this post


Link to post
Share on other sites
Quote:
for (int i = 1; i < (Window.ClientBounds.Width/8)-1; i++)
for (int j = 1; j < (Window.ClientBounds.Height/8)-1; j++)

*ALWAYS* iterate by row, so swap those lines.


Now for algorithmic improvements.

For center particle, these are the interacting neighbors:
+-+-+-+
|1|2|3|
+-+-+-+
|4|5|6|
+-+-+-+
|7|8|9|
+-+-+-+


If you look how this is calculated, you'll notice that each cell is tested 3 times. 2, for example, is tested for 4,5 and 6.

Instead, reverse the problem. 1 affects 2,4 and 5 (and those not visible on the left). 2 affects 1,4,5,6 and 3.

But there is a lot of symmetry. So now the entire update cycle can be done by testing each pixel exactly once:
+-+-+
|x|D|
+-+-+
|D|D|
+-+-+

if (x.alive) D=1 else D=0


The loop now becomes:
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (cells[y,x].alive) {
cells[y ,x+1].neighbors++;
cells[y+1,x ].neighbors++;
cells[y+1,x+1].neighbors++;
}
}
}

for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (cells[y,x].neighbors == 2 || cells[y,x].neighbors == 3) {
cells[y,x].alive=true;
} else {
cells[y,x].alive=false;
}
cells[y,x].neighbors = 0; // reset neighbor count here, after cell was updated
}
}



An implementation detail - the array storing the cells must have dimensions width+1,height+1, but valid cells are located in 1..width-1, 1..height-1. This is due to symmetry used above, where certain edge cells are not fully updated.

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!