Sign in to follow this  
Bromordra

Speed issues in game of life.

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

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
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
Wow splendid idea to build this small 'game'!!

I just build the game myself in like 3 hours, haha, amazing algorithm. It shows once again that simple rules can produce extremely complex results (just like ants do, just like atoms behave). I love this kind of stuff.

Anyways, here the code if you long for it:
#include <iostream>
#include <ctime>

extern "C"
{
#include <lua/lua.h>
#include <lua/lualib.h>
#include <lua/lauxlib.h>
}

#include "window.hpp"

////////////////////////////////////////////////////////////////

double timer;

void process();

////////////////////////////////////////////////////////////////

int main(int /*argc*/, char */*argv*/[])
{
try
{
process();
}
catch (...)
{
std::cerr << " -- Unhandled exception\n" << std::flush;
}

timer = (Window::GetSystemTime() - timer);
std::cerr << "Destroying: " << timer << '\n' << std::flush;
return 0;
}

////////////////////////////////////////////////////////////////

struct Vertex
{
Vertex()
: r(),
g(),
b(),
a(1.0f)
{
}

float x, y;
float r, g, b, a;
};

struct Cell
{
Cell()
: alive(),
neighbours(),
new_neighbours()
{
}

bool alive;
unsigned char neighbours, new_neighbours;
};

float modulus(float a, float b)
{
int result = static_cast<int>(a / b);
return (a - static_cast<float>(result) * b);
}

void neighbour(Cell *cells, size_t x, size_t y, size_t w, size_t h, int d_neighbours, bool new_only = true)
{
size_t left = x > 0 ? x - 1 : w - 1;
size_t right = x < w - 1 ? x + 1 : 0;

size_t top = y > 0 ? y - 1 : h - 1;
size_t bottom = y < h - 1 ? y + 1 : 0;

cells[(top * w) + left].new_neighbours += d_neighbours;
cells[(top * w) + x].new_neighbours += d_neighbours;
cells[(top * w) + right].new_neighbours += d_neighbours;

cells[(y * w) + left].new_neighbours += d_neighbours;
cells[(y * w) + right].new_neighbours += d_neighbours;

cells[(bottom * w) + left].new_neighbours += d_neighbours;
cells[(bottom * w) + x].new_neighbours += d_neighbours;
cells[(bottom * w) + right].new_neighbours += d_neighbours;

if (!new_only)
{
cells[(top * w) + left].neighbours += d_neighbours;
cells[(top * w) + x].neighbours += d_neighbours;
cells[(top * w) + right].neighbours += d_neighbours;

cells[(y * w) + left].neighbours += d_neighbours;
cells[(y * w) + right].neighbours += d_neighbours;

cells[(bottom * w) + left].neighbours += d_neighbours;
cells[(bottom * w) + x].neighbours += d_neighbours;
cells[(bottom * w) + right].neighbours += d_neighbours;
}
}

void process()
{
srand((unsigned) time(NULL));

int width = 1024;
int height = 1024;

float cell_width = 10.0f;
float cell_height = 10.0f;
float cell_space = 1.0f;
float fade = 0.01f;
float life_step = 0.1f;

std::string filename = "settings.lua";
lua_State *lua_state = lua_open();
if (luaL_loadfile(lua_state, filename.c_str()) || lua_pcall(lua_state, 0, 0, 0))
{
fprintf(stderr, "ERROR: Could not load score file; Lua says `%s'\n", lua_tostring(lua_state, -1));
lua_close(lua_state);
}
else
{
////////////////

lua_getglobal(lua_state, "width");
if (lua_isnumber(lua_state, -1))
{
width = lua_tonumber(lua_state, -1);
}
else
{
std::cerr << "WARNING: No width set, defaulting to '" << width << "'\n";
}
lua_pop(lua_state, 1);

lua_getglobal(lua_state, "height");
if (lua_isnumber(lua_state, -1))
{
height = lua_tonumber(lua_state, -1);
}
else
{
std::cerr << "WARNING: No height set, defaulting to '" << height << "'\n";
}
lua_pop(lua_state, 1);

lua_getglobal(lua_state, "cell_width");
if (lua_isnumber(lua_state, -1))
{
cell_width = lua_tonumber(lua_state, -1);
}
else
{
std::cerr << "WARNING: No cell_width set, defaulting to '" << cell_width << "'\n";
}
lua_pop(lua_state, 1);

lua_getglobal(lua_state, "cell_height");
if (lua_isnumber(lua_state, -1))
{
cell_height = lua_tonumber(lua_state, -1);
}
else
{
std::cerr << "WARNING: No cell_height set, defaulting to '" << cell_height << "'\n";
}
lua_pop(lua_state, 1);

lua_getglobal(lua_state, "cell_space");
if (lua_isnumber(lua_state, -1))
{
cell_space = lua_tonumber(lua_state, -1);
}
else
{
std::cerr << "WARNING: No cell_space set, defaulting to '" << cell_space << "'\n";
}
lua_pop(lua_state, 1);

lua_getglobal(lua_state, "fade");
if (lua_isnumber(lua_state, -1))
{
fade = lua_tonumber(lua_state, -1);
}
else
{
std::cerr << "WARNING: No fade set, defaulting to '" << fade << "'\n";
}
lua_pop(lua_state, 1);

lua_getglobal(lua_state, "life_step");
if (lua_isnumber(lua_state, -1))
{
life_step = lua_tonumber(lua_state, -1);
}
else
{
std::cerr << "WARNING: No life_step set, defaulting to '" << life_step << "'\n";
}
lua_pop(lua_state, 1);

////////////////
}
lua_close(lua_state);

Window::initialise("Life", width, height, false, 0);

glViewport(0, 0, width, height);

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(0.0f, width, height, 0.0f, -1.0f, 1.0f);

glMatrixMode(GL_MODELVIEW);
glLoadIdentity();

glShadeModel(GL_SMOOTH);
glDepthFunc(GL_LEQUAL);
glHint(GL_PERSPECTIVE_CORRECTION_HINT, GL_NICEST);

glClearColor(0.2f, 0.2f, 0.2f, 1.0f);
glClearDepth(1.0);

glColor4f(1.0f, 1.0f, 1.0f, 1.0f);
glTranslatef(0.0f, 0.0f, -1.0f);

glEnable(GL_BLEND);

////////////////

bool active = true;

timer = Window::GetSystemTime();

////////////////

size_t grid_width = static_cast<float>(width + cell_space) / (cell_width + cell_space);
size_t grid_height = static_cast<float>(height + cell_space) / (cell_height + cell_space);
grid_width = std::min(grid_width, grid_height);
grid_height = std::min(grid_width, grid_height);

size_t grid_length = grid_width * grid_height;

Vertex *vertices = new Vertex[grid_length * 4];
Cell *cells = new Cell[grid_length];

////

float grid_x = static_cast<float>(width - (grid_width * (cell_width + cell_space))) / 2.0f;
float grid_y = static_cast<float>(height - (grid_height * (cell_height + cell_space))) / 2.0f;

float t_grid_x = grid_x;
float t_grid_y = grid_y;

Vertex *vertex = vertices;
for (unsigned int y = 0; y < grid_height; y++)
{
for (unsigned int x = 0; x < grid_width; x++)
{
vertex[0].x = vertex[3].x = t_grid_x;
vertex[1].x = vertex[2].x = t_grid_x + cell_width;

vertex[0].y = vertex[1].y = t_grid_y;
vertex[2].y = vertex[3].y = t_grid_y + cell_height;

t_grid_x += cell_width + cell_space;
vertex += 4;
}

t_grid_x = grid_x;
t_grid_y += cell_height + cell_space;
}

////

glEnableClientState(GL_VERTEX_ARRAY);
glEnableClientState(GL_COLOR_ARRAY);

glVertexPointer(2, GL_FLOAT, sizeof(Vertex), (char *) vertices);
glColorPointer(4, GL_FLOAT, sizeof(Vertex), (char *) vertices + (sizeof(float) * 2));

////////////////

timer = (Window::GetSystemTime() - timer);
std::cerr << "Initialisation: " << timer << '\n' << std::flush;

bool mousebutton_down = false;
bool mouse_growmodus = false;

bool life = false;
double life_timer = Window::GetSystemTime();
while (active)
{
SDL_Event sdl_event;
while (SDL_PollEvent(&sdl_event))
{
if (sdl_event.type == SDL_QUIT || (sdl_event.type == SDL_KEYDOWN && sdl_event.key.keysym.sym == SDLK_ESCAPE))
{
active = false;
}
else if (sdl_event.type == SDL_KEYDOWN && sdl_event.key.keysym.sym == SDLK_SPACE)
{
life = !life;
}
else if (sdl_event.type == SDL_KEYDOWN && sdl_event.key.keysym.sym == SDLK_c)
{
Cell *cell = cells;
for (unsigned int i = 0; i < grid_length; i++)
{
cell->alive = false;
cell->neighbours = cell->new_neighbours = 0;

cell++;
}
}
else if (sdl_event.type == SDL_MOUSEBUTTONDOWN && sdl_event.button.button == SDL_BUTTON_LEFT)
{
if (modulus(static_cast<float>(sdl_event.motion.x) - grid_x, cell_width + cell_space) < cell_width && modulus(static_cast<float>(sdl_event.motion.y) - grid_y, cell_height + cell_space) < cell_height)
{
size_t x = (static_cast<float>(sdl_event.motion.x) - grid_x) / (cell_width + cell_space);
size_t y = (static_cast<float>(sdl_event.motion.y) - grid_y) / (cell_height + cell_space);

mousebutton_down = true;
if (!cells[(y * grid_width) + x].alive)
{
mouse_growmodus = true;
}
else
{
mouse_growmodus = false;
}

cells[(y * grid_width) + x].alive = !cells[(y * grid_width) + x].alive;

int d_neightbours = 1;
if (!cells[(y * grid_width) + x].alive)
{
d_neightbours = -1;
}

neighbour(cells, x, y, grid_width, grid_height, d_neightbours, false);
}
else
{
mousebutton_down = true;
mouse_growmodus = true;
}
}
else if (sdl_event.type == SDL_MOUSEBUTTONUP && sdl_event.button.button == SDL_BUTTON_LEFT)
{
mousebutton_down = false;
}
else if (sdl_event.type == SDL_MOUSEMOTION)
{
if (mousebutton_down)
{
if (modulus(static_cast<float>(sdl_event.motion.x) - grid_x, cell_width + cell_space) < cell_width && modulus(static_cast<float>(sdl_event.motion.y) - grid_y, cell_height + cell_space) < cell_height)
{
size_t x = (static_cast<float>(sdl_event.motion.x) - grid_x) / (cell_width + cell_space);
size_t y = (static_cast<float>(sdl_event.motion.y) - grid_y) / (cell_height + cell_space);

if (cells[(y * grid_width) + x].alive != mouse_growmodus)
{
cells[(y * grid_width) + x].alive = mouse_growmodus;

int d_neightbours = 1;
if (!mouse_growmodus)
{
d_neightbours = -1;
}

neighbour(cells, x, y, grid_width, grid_height, d_neightbours, false);
}
}
}
}
}

bool life_burst = false;
if (life && (Window::GetSystemTime() - life_timer) >= life_step)
{
life_timer = Window::GetSystemTime();
life_burst = true;
}

if (life_burst)
{
Cell *cell = cells;
Vertex *vertex = vertices;
for (unsigned int i = 0; i < grid_length; i++)
{
bool new_alive = cell->alive;
if (cell->alive && (cell->neighbours < 2 || cell->neighbours > 3))
{
new_alive = false;
}
else if (!cell->alive && cell->neighbours == 3)
{
new_alive = true;
}

if (new_alive != cell->alive)
{
int d_neightbours = 1;
if (!new_alive)
{
d_neightbours = -1;
}

neighbour(cells, i % grid_width, i / grid_width, grid_width, grid_height, d_neightbours);
cell->alive = new_alive;
}

if (cell->alive && vertex[0].r != 1.0f)
{
for (unsigned int j = 0; j < 4; j++)
{
vertex[j].r = std::min(1.0f, vertex[j].r + fade);
vertex[j].g = std::min(1.0f, vertex[j].g + fade);
vertex[j].b = std::min(1.0f, vertex[j].b + fade);
}
}
else if (!cell->alive && vertex[0].r != 0.0f)
{
for (unsigned int j = 0; j < 4; j++)
{
vertex[j].r = std::max(0.0f, vertex[j].r - fade);
vertex[j].g = std::max(0.0f, vertex[j].g - fade);
vertex[j].b = std::max(0.0f, vertex[j].b - fade);
}
}

cell++;
vertex += 4;
}
}

Cell *cell = cells;
Vertex *vertex = vertices;
for (unsigned int i = 0; i < grid_length; i++)
{
float t_fade = fade;
if (!life)
{
t_fade *= 4;
}

if (cell->alive && vertex[0].r != 1.0f)
{
for (unsigned int j = 0; j < 4; j++)
{
vertex[j].r = std::min(1.0f, vertex[j].r + t_fade);
vertex[j].g = std::min(1.0f, vertex[j].g + t_fade);
vertex[j].b = std::min(1.0f, vertex[j].b + t_fade);
}
}
else if (!cell->alive && vertex[0].r != 0.0f)
{
for (unsigned int j = 0; j < 4; j++)
{
vertex[j].r = std::max(0.0f, vertex[j].r - t_fade);
vertex[j].g = std::max(0.0f, vertex[j].g - t_fade);
vertex[j].b = std::max(0.0f, vertex[j].b - t_fade);
}
}

if (life_burst)
{
cell->neighbours = cell->new_neighbours;
}

cell++;
vertex += 4;
}

if (1)
{

Window::pre_frame();

/////////////////

glDrawArrays(GL_QUADS, 0, grid_length * 4);

//////////////////

Window::post_frame();
}
else
{
Window::delay();
}

Window::caption_fps();
}

//////////////////

glDisableClientState(GL_COLOR_ARRAY);
glDisableClientState(GL_VERTEX_ARRAY);

delete[] cells;
delete[] vertices;

//////////////////

Window::shutdown();
timer = Window::GetSystemTime();
}

////////////////////////////////////////////////////////////////






EDIT:
I've added colours to my version as well, blue is under population, red over population, green is growth. It looks really nice, hehe.

The original is:
under_population_till = 1
reproduction_from = 3
reproduction_till = 3
over_population_from = 4

You gotta try this:
under_population_till = 2
reproduction_from = 3
reproduction_till = 4
over_population_from = 5



It looks like a tumor or something, really nice effects.

The following looks like a maze or something:
under_population_till = 1
reproduction_from = 2 or 3
reproduction_till = 3
over_population_from = 5



[Edited by - Decrius on December 11, 2010 12:08:04 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this