Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
34 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to For Beginners

Speed issues in game of life.

Started by
9 comments, last by Decrius 13 years, 4 months ago
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.alive)<br>                            CellArray[i, j].neighbors++;<br><br>                        <span class="cpp-keyword">if</span> (CellArray.alive)<br>                            CellArray[i, j].neighbors++;<br><br>                        <span class="cpp-keyword">if</span> (CellArray.alive)<br>                            CellArray[i, j].neighbors++;<br><br>                        <span class="cpp-keyword">if</span> (CellArray.alive)<br>                            CellArray[i, j].neighbors++;<br><br>                        <span class="cpp-keyword">if</span> (CellArray[i, j - <span class="cpp-literal"><span class="cpp-number">1</span></span>].alive)<br>                            CellArray[i, j].neighbors++;<br><br>                        <span class="cpp-keyword">if</span> (CellArray.alive)<br>                            CellArray[i, j].neighbors++;<br><br>                        <span class="cpp-keyword">if</span> (CellArray.alive)<br>                            CellArray[i, j].neighbors++;<br><br>                        <span class="cpp-keyword">if</span> (CellArray[i, j + <span class="cpp-literal"><span class="cpp-number">1</span></span>].alive)<br>                            CellArray[i, j].neighbors++;<br>                    }<br><br>                <span class="cpp-keyword">foreach</span> (Cell c <span class="cpp-keyword">in</span> CellArray)<br>                {<br>                    <span class="cpp-keyword">if</span> (c.alive)<br>                    {<br>                        <span class="cpp-keyword">if</span> (c.neighbors == <span class="cpp-literal"><span class="cpp-number">2</span></span>)<br>                            c.alive = <span class="cpp-literal">true</span>;<br>                        <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span> (c.neighbors == <span class="cpp-literal"><span class="cpp-number">3</span></span>)<br>                            c.alive = <span class="cpp-literal">true</span>;<br>                        <span class="cpp-keyword">else</span><br>                            c.alive = <span class="cpp-literal">false</span>;<br>                    }<br>                    <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span> (!c.alive)<br>                    {<br>                        <span class="cpp-keyword">if</span> (c.neighbors == <span class="cpp-literal"><span class="cpp-number">3</span></span>)<br>                            c.alive = <span class="cpp-literal">true</span>;<br>                    }<br><br>                }<br>            }<br><br><br></pre></div><!–ENDSCRIPT–><br><br>Current implementation of the game, at least the part relevant to this question.<br><br><!–EDIT–><span class=editedby><!–/EDIT–>[Edited by - Bromordra on December 11, 2010 2:23:44 AM]<!–EDIT–></span><!–/EDIT–>
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.alive)<br>          CellArray[i, j].neighbors++;<br>  }<br>}<br><br><br><br><br></pre></div><!–ENDSCRIPT–>
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.
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!
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.

Video Game Programmer.
5 years in industry.

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.
My Blog
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.alive)<br>                                        CellArray[i, j].neighbors++; <br>                                    <span class="cpp-keyword">for</span> (<span class="cpp-keyword">int</span> m = -<span class="cpp-number">1</span>; m &lt;= <span class="cpp-number">1</span>; m++)<br>                                        <span class="cpp-keyword">for</span> (<span class="cpp-keyword">int</span> n = -<span class="cpp-number">1</span>; n &lt;= <span class="cpp-number">1</span>; n++)<br>                                            <span class="cpp-keyword">if</span> (!(m == <span class="cpp-number">0</span> &amp;&amp; n == <span class="cpp-number">0</span>) &amp;&amp; CellArray.alive)<br>                                                CellArray.neighbors++;<br>                                    <span class="cpp-keyword">if</span> (!ActiveList.Contains(CellArray))<br>                                        ActiveList.Add(CellArray);<br>                                }<br>                        }<br>                    }<br><br></pre></div><!–ENDSCRIPT–><br><br>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.
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.
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.

Video Game Programmer.
5 years in industry.

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.

This topic is closed to new replies.

Advertisement

Popular Topics

Aybe One
How do you manage yourself and your time as years pass on? GDNet Lounge
Jikoob
Too many managers? General and Gameplay Programming
ReignOnU
Do your part to stop global warming and climate change GDNet Lounge
aigan
The promise of freedom in story games Game Design and Theory
robertrobert
Facebook Ads for sales on steam, does it work? Games Business and Law
AliAbdulKareem
Understanding the wavy-like shape in alpha-testing magnification for text rendering Graphics and GPU Programming
Advertisement

Recommended Tutorials

Myopic Rhino
XGDX 2004 Report Event Coverage
jhenriques
Vulkan 101 Tutorial Graphics and GPU Programming
Alconost
Localizing Your Indie Game: Crazy Idea or Growth Hack? Production and Management
Myopic Rhino
Designing Great Games Game Design and Theory
Myopic Rhino
Appearance Map General and Gameplay Programming

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top