3d game of life

[jaeg]

I'm working on a 3d version of Conway's game of life. I have a 3d array of scene nodes and basically visibility defines if it is dead or alive. Now to my question, what's the best way to check the neighbors of a cell? There are 26 neighbors max but cells along the edges have fewer. At first I started off with a whole bunch of if statements for each cell around a cell but then the problem of the edge cells arises so then I need statements to check to see if a cell is possible (ie i>0, i<width, etc). There has to be a better way than possibly 30+ 'if' statements because the locating of a cell in a 3d array is already O(N^3). I don't expect the program to run fast (it's a cellular automata so I want to see the generation progress).

[CuteAlien]

Write the 26 relative positions in an array and then loop over it (doing the border checks in the loop). At least that's what I probably would do.

[jaeg]

So you mean like -

Code: Select all

ISceneNode neighbors[26];
if (i<width)
     neighbor[0] = world[i+1][j][h];
else
     neighbor[0]=null;

then I just keep adding to that and checking if it's within the world and if not make it null or zero?

[hybrid]

I think I would separate the processing into separate parts. I.e. doing a few loops over the sections that the complete world consists of. Largest section is the inner part, where all neighbours are active. At the border you iterate over only the inner of one side, or the edges, or the corners. The latter are handled explicitly one for one.
Adressing then would go via an offset array to save space: neighbour[0]=-width-1-(width*height) This is the offset for all cells to the top-left-behind cell, i.e. neighbour up-left-behind. This assumes a plain one-dimension array, though. Don't know if you ever have to access an index randomly by its x,y,z indices, but IMHO it's at least only a corner case. So using a flat array would be much better, as you can iterate over the whole world easily as well.

[CuteAlien]

Yes, I meant the same as hybrid - use an array which just contains the relative addressing.
Using several loops for each of the border-checks is a clever optimization, but lots of loops (27 cases maybe? Would have to draw it on paper to be certain).

[jaeg]

So I could have a group of for loops engaging the inner portion which is 1 cell away from the edge. Then have a some loops to process the outer walls of the world minus the actual edge and after that process the actual edge? Each of these sections have their own limitations. Well mostly the last two groups.

Wrong direction?


Also I was thinking about 'cheating' a little bit by making the world 1 cell thicker but have the outer cells all be 0 so when looping through it would count those cells as null and not process them and when other cells look at them it would be considered dead.

EDIT -
btw this is my original way to locate the neighbors of a cell. It's not actual code just me trying to organize all the cases. Assume when you see something like x,y,z its another if statement checking to see if a node is visible.

Code: Select all

 
If (x<width)
        If (y<height)
                If (z>0)
                        X+1,y+1,z-1
                If (z>depth)
                        X+1,y+1,z+1
                X+1,y+1,z
        If (y>0)
                If (z>0)
                        X+1,y-1,z-1
                If(z<depth)
                        X+1,y-1,z+1
                X+1,y-1,z
        If (z>0)
                X+1,y,z-1
 
        If (z<depth)
                X+1,y,z+1
 
        X+1, y, z
        
        
If (x>0)
        If (y<height)
                If (z>0)
                        X-1,y+1,z-1
                If (z>depth)
                        X-1,y+1,z+1
                X-1,y+1,z       
        If (y>0)
                If (z>0)
                        X-1,y-1,z-1
                If(z<depth)
                        X-1,y-1,z+1
                X-1,y-1,z
        If (z>0)
                X-1,y,z-1
        If (z<depth)
                X-1,y,z+1
        X-1, y, z
 
        If (y<height)
                If (z>0)
                        X,y+1,z-1
                If (z>depth)
                        X,y+1,z+1
                X,y+1,z 
        If (y>0)
                If (z>0)
                        X,y-1,z-1
                If(z<depth)
                        X,y-1,z+1
                X,y-1,z
        If (z>0)
                X,y,z-1
        If (z<depth)
                X,y,z+1

[hybrid]

Yeah, if you can make those one cell larger, it would be probably easier to calculate. You must still ensure to only work on those cells which are safe. At least to not access out of bounds from the array. But that could be less overhead.
For the for loops: No, not really correct direction. I meant a few loops which work on those section for the whole world. I.e. you process in a first loop all inner cells, which have all neighbours. For those, you don't need any other checks inside the loop, just read the neighbour values. Then you process all cells which are on the outside, but still have all neighbours except the left/right/top/down/front/back slice. Basically those cells which are visible from the outside, but are neither edges nor corners. And then you have to process the edges and after that the corners. So it's 19 loops and the 8 corners. But it would avoid all checks inside the loop. You have to duplicate the cell calculation, though, as you have different numbers of values to work on in each phase.

[jaeg]

I have a working prototype going. It doesn't use the method you described yet but it does work to an extent. I'm unsure yet how I should modify the rules to account for the extra dimension so I've just been playing around with the values. The coding is kind of sloppy and I apologize for that.

Btw a cube over 80x80x80 tends to crash and a cube over 50x50x50 runs unimaginably slow. But that's safe to assume since there are 125000 scene nodes.

Code: Select all

//3d Life
 
/*Original Rules:
1.Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2.Any live cell with two or three live neighbours lives on to the next generation.
3.Any live cell with more than three live neighbours dies, as if by overcrowding.
4.Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
*/
#include <iostream>
#include <irrlicht.h>
using namespace irr;
 
using namespace core;
using namespace scene;
using namespace video;
using namespace io;
using namespace gui;
 
using namespace std;
 
const int overCrowd = 13;
const int underPop = 7;
const int reproduction = 12;
 
int main()
{
    //Establish 3d Window
    IrrlichtDevice *device =
                createDevice( video::EDT_OPENGL, dimension2d<u32>(640, 480), 16,
                        false, false, false, 0);
 
        if (!device)
                return 1;
 
        IVideoDriver* driver = device->getVideoDriver();
        ISceneManager* smgr = device->getSceneManager();
        IGUIEnvironment* guienv = device->getGUIEnvironment();
 
    //Defaults
    int width=10;
    int height=10;
    int depth=10;
 
    cout<<"Enter width of world: ";
    cin>>width;
    cout<<"Enter height of world: ";
    cin>>height;
    cout<<"Enter depth of world: ";
    cin>>depth;
 
    SMaterial mUnit;
    mUnit.setTexture(0, driver->getTexture("texture.bmp"));
 
    ISceneNode* world[width][height][depth]; //0-dead, 1-alive
 
    //Randomize the world
    for(int i=0;i<width;i++)
    {
        for(int j=0;j<height;j++)
        {
            for(int h=0;h<depth;h++)
            {
               world[i][j][h]=smgr->addCubeSceneNode(10,0,-1,vector3df(i*11,j*11,h*11),vector3df(0,0,0),vector3df(1,1,1));
               world[i][j][h]->getMaterial(0)=mUnit;
               world[i][j][h]->setMaterialFlag(EMF_LIGHTING, false);
               if (rand()%10>4)
               {
                   world[i][j][h]->setVisible(0);
               }
            }
        }
    }
 
    smgr->addCameraSceneNodeFPS(0, 100.0f, .3f, -1, 0, 0, false, 3.f);
 
    int generation = 0;
    while(device->run())
        {
        if (device->isWindowActive())
        {
            driver->beginScene(true, true, SColor(255,100,101,140));
 
 
            smgr->drawAll();
            guienv->drawAll();
 
            driver->endScene();
            int fps = driver->getFPS();
            stringw str = L" ";
            str += " FPS:";
            str += fps;
            str += "Generation: ";
            str +=generation;
 
            device->setWindowCaption(str.c_str());
                //Randomize the world
            for(int x=0;x<width;x++)
            {
                for(int y=0;y<height;y++)
                {
                    for(int z=0;z<depth;z++)
                    {
                        int neighbors=0;
                        if (x<width-2)
                        {
                            if (y<height-2)
                            {
                                if (z>0)
                                {
                                   if (world[x+1][y+1][z-1]->isVisible())
                                        neighbors++;
                                }
                                if (z<depth)
                                {
                                    if (world[x+1][y+1][z+1]->isVisible())
                                        neighbors++;
                                }
 
 
                                if (world[x+1][y+1][z]->isVisible())
                                        neighbors++;
 
                            }
                            if (y!=0)
                            {
                                if (z>0)
                                {
                                   if (world[x+1][y-1][z-1]->isVisible())
                                        neighbors++;
                                }
                                if (z<depth)
                                {
                                    if (world[x+1][y-1][z+1]->isVisible())
                                        neighbors++;
                                }
                                if (world[x+1][y-1][z]->isVisible())
                                        neighbors++;
                            }
 
                            if (z!=0)
                            {
                                if (world[x+1][y][z-1]->isVisible())
                                        neighbors++;
                            }
 
                            if (z<depth-2)
                            {
                                if (world[x+1][y][z+1]->isVisible())
                                        neighbors++;
                            }
 
                            if (world[x+1][y][z]->isVisible())
                                neighbors++;
                        }
 
                        //
                        if(x>0)
                        {
                            if (y<height-2)
                            {
                                if (z>0)
                                {
                                   if (world[x-1][y+1][z-1]->isVisible())
                                        neighbors++;
                                }
                                if (z<depth-2)
                                {
                                    if (world[x-1][y+1][z+1]->isVisible())
                                        neighbors++;
                                }
 
 
                                if (world[x-1][y+1][z]->isVisible())
                                        neighbors++;
 
                            }
                            if (y!=0)
                            {
                                if (z!=0)
                                {
                                   if (world[x-1][y-1][z-1]->isVisible())
                                        neighbors++;
                                }
                                if (z>depth-2)
                                {
                                    if (world[x-1][y-1][z+1]->isVisible())
                                        neighbors++;
                                }
                                if (world[x-1][y-1][z]->isVisible())
                                        neighbors++;
                            }
 
                            if (z!=0)
                            {
                                if (world[x-1][y][z-1]->isVisible())
                                        neighbors++;
                            }
 
                            if (z<depth-2)
                            {
                                if (world[x-1][y][z+1]->isVisible())
                                        neighbors++;
                            }
                            if (world[x-1][y][z]->isVisible())
                                neighbors++;
                        }
 
                                                //
                        //if(x>0)
                        {
                            if (y<height-2)
                            {
                                if (z>0)
                                {
                                   if (world[x][y+1][z-1]->isVisible())
                                        neighbors++;
                                }
                                if (z<depth-2)
                                {
                                    if (world[x][y+1][z+1]->isVisible())
                                        neighbors++;
                                }
 
 
                                if (world[x][y+1][z]->isVisible())
                                        neighbors++;
 
                            }
                            if (y!=0)
                            {
                                if (z!=0)
                                {
                                   if (world[x][y-1][z-1]->isVisible())
                                        neighbors++;
                                }
                                if (z>depth-2)
                                {
                                    if (world[x][y-1][z+1]->isVisible())
                                        neighbors++;
                                }
                                if (world[x][y-1][z]->isVisible())
                                        neighbors++;
                            }
 
                            if (z!=0)
                            {
                                if (world[x][y][z-1]->isVisible())
                                        neighbors++;
                            }
 
                            if (z<depth-2)
                            {
                                if (world[x][y][z+1]->isVisible())
                                        neighbors++;
                            }
                            if (world[x][y][z]->isVisible())
                                neighbors++;
                        }
 
 
 
 
                        if (neighbors>=overCrowd)
                        {
                            world[x][y][z]->setVisible(false);
                        }
 
                        if (neighbors<underPop)
                        {
                            world[x][y][z]->setVisible(false);
                        }
 
                        if (neighbors==reproduction)
                        {
                            world[x][y][z]->setVisible(true);
                        }
                    }
                }
            }
 
            generation +=1;
 
        }
        }
 
        device->drop();
 
    return 0;
}
 

[hybrid]

Yeah, check the threads about minecraft clones. You need to reduce the number of scene nodes to at most a few thousand, better just a few dozen. It's probably even better to recreate the rendered meshes each cycle (recalculating all vertices and indices and uploading to the GPU) than rendering each cube as a single call.

[hendu]

As far as I've read, nobody's tried to do a minecraft-style game with instancing? One call, please draw 100k blocks

[REDDemon]

I think that the whole game of life can run only on the GPU using shaders. Later or soon someone will try that

[jaeg]

Yah I eventually plan to reduce the number of draw calls by merging the cells into a single mesh or potentially making each cell a single vertex and watch it morph that way.

By the way I changed the rules and added a few new features:

Code: Select all

//3d Life
 
/*Original Rules:
1.Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2.Any live cell with two or three live neighbours lives on to the next generation.
3.Any live cell with more than three live neighbours dies, as if by overcrowding.
4.Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
*/
#include <iostream>
#include <irrlicht.h>
using namespace irr;
 
using namespace core;
using namespace scene;
using namespace video;
using namespace io;
using namespace gui;
 
using namespace std;
 
const int overCrowd = 10;
const int underPop = 7;
const int reproduction = 8;
 
int main()
{
    //Establish 3d Window
    IrrlichtDevice *device =
                createDevice( video::EDT_OPENGL, dimension2d<u32>(640, 480), 16,
                        false, false, false, 0);
 
        if (!device)
                return 1;
 
        IVideoDriver* driver = device->getVideoDriver();
        ISceneManager* smgr = device->getSceneManager();
        IGUIEnvironment* guienv = device->getGUIEnvironment();
 
    //Defaults
    int width=10;
    int height=10;
    int depth=10;
 
    cout<<"Enter width of world: ";
    cin>>width;
    cout<<"Enter height of world: ";
    cin>>height;
    cout<<"Enter depth of world: ";
    cin>>depth;
 
    int startWidth=10;
    int startHeight=10;
    int startDepth=10;
    cout<<"Enter starting width of world: ";
    cin>>startWidth;
    cout<<"Enter starting height of world: ";
    cin>>startHeight;
    cout<<"Enter starting depth of world: ";
    cin>>startDepth;
 
    SMaterial mUnit;
    mUnit.setTexture(0, driver->getTexture("texture.bmp"));
 
    ISceneNode* world[width][height][depth]; //0-dead, 1-alive
 
    //Create World
    for(int i=0;i<width;i++)
    {
        for(int j=0;j<height;j++)
        {
            for(int h=0;h<depth;h++)
            {
               world[i][j][h]=smgr->addCubeSceneNode(10,0,-1,vector3df(i*10,j*10,h*10),vector3df(0,0,0),vector3df(1,1,1));
               world[i][j][h]->getMaterial(0)=mUnit;
               world[i][j][h]->setMaterialFlag(EMF_LIGHTING, false);
               world[i][j][h]->setVisible(0);
            }
        }
    }
 
    //Randomize World
    for(int i=((width-startWidth)/2);i<width-((width-startWidth)/2);i++)
    {
        for(int j=((height-startHeight)/2);j<height-((height-startHeight)/2);j++)
        {
            for(int h=((depth-startDepth)/2);h<depth-((depth-startDepth)/2);h++)
            {
               if (rand()%10>3)
               {
                   world[i][j][h]->setVisible(1);
               }
            }
        }
    }
 
 
 
    smgr->addCameraSceneNodeFPS(0, 100.0f, .3f, -1, 0, 0, false, 3.f);
 
    int generation = 0;
    while(device->run())
        {
        if (device->isWindowActive())
        {
            driver->beginScene(true, true, SColor(255,100,101,140));
 
 
            smgr->drawAll();
            guienv->drawAll();
 
            driver->endScene();
            int fps = driver->getFPS();
            stringw str = L" ";
            str += " FPS:";
            str += fps;
            str += "Generation: ";
            str +=generation;
 
            device->setWindowCaption(str.c_str());
 
            for(int x=0;x<width;x++)
            {
                for(int y=0;y<height;y++)
                {
                    for(int z=0;z<depth;z++)
                    {
                        int neighbors=0;
                        if (x<width-2)
                        {
                            if (y<height-2)
                            {
                                if (z>0)
                                {
                                   if (world[x+1][y+1][z-1]->isVisible())
                                        neighbors++;
                                }
                                if (z<depth)
                                {
                                    if (world[x+1][y+1][z+1]->isVisible())
                                        neighbors++;
                                }
 
 
                                if (world[x+1][y+1][z]->isVisible())
                                        neighbors++;
 
                            }
                            if (y!=0)
                            {
                                if (z>0)
                                {
                                   if (world[x+1][y-1][z-1]->isVisible())
                                        neighbors++;
                                }
                                if (z<depth)
                                {
                                    if (world[x+1][y-1][z+1]->isVisible())
                                        neighbors++;
                                }
                                if (world[x+1][y-1][z]->isVisible())
                                        neighbors++;
                            }
 
                            if (z!=0)
                            {
                                if (world[x+1][y][z-1]->isVisible())
                                        neighbors++;
                            }
 
                            if (z<depth-2)
                            {
                                if (world[x+1][y][z+1]->isVisible())
                                        neighbors++;
                            }
 
                            if (world[x+1][y][z]->isVisible())
                                neighbors++;
                        }
 
                        //
                        if(x>0)
                        {
                            if (y<height-2)
                            {
                                if (z>0)
                                {
                                   if (world[x-1][y+1][z-1]->isVisible())
                                        neighbors++;
                                }
                                if (z<depth-2)
                                {
                                    if (world[x-1][y+1][z+1]->isVisible())
                                        neighbors++;
                                }
 
 
                                if (world[x-1][y+1][z]->isVisible())
                                        neighbors++;
 
                            }
                            if (y!=0)
                            {
                                if (z!=0)
                                {
                                   if (world[x-1][y-1][z-1]->isVisible())
                                        neighbors++;
                                }
                                if (z>depth-2)
                                {
                                    if (world[x-1][y-1][z+1]->isVisible())
                                        neighbors++;
                                }
                                if (world[x-1][y-1][z]->isVisible())
                                        neighbors++;
                            }
 
                            if (z!=0)
                            {
                                if (world[x-1][y][z-1]->isVisible())
                                        neighbors++;
                            }
 
                            if (z<depth-2)
                            {
                                if (world[x-1][y][z+1]->isVisible())
                                        neighbors++;
                            }
                            if (world[x-1][y][z]->isVisible())
                                neighbors++;
                        }
 
                                                //
                        //if(x>0)
                        {
                            if (y<height-2)
                            {
                                if (z>0)
                                {
                                   if (world[x][y+1][z-1]->isVisible())
                                        neighbors++;
                                }
                                if (z<depth-2)
                                {
                                    if (world[x][y+1][z+1]->isVisible())
                                        neighbors++;
                                }
 
 
                                if (world[x][y+1][z]->isVisible())
                                        neighbors++;
 
                            }
                            if (y!=0)
                            {
                                if (z!=0)
                                {
                                   if (world[x][y-1][z-1]->isVisible())
                                        neighbors++;
                                }
                                if (z>depth-2)
                                {
                                    if (world[x][y-1][z+1]->isVisible())
                                        neighbors++;
                                }
                                if (world[x][y-1][z]->isVisible())
                                        neighbors++;
                            }
 
                            if (z!=0)
                            {
                                if (world[x][y][z-1]->isVisible())
                                        neighbors++;
                            }
 
                            if (z<depth-2)
                            {
                                if (world[x][y][z+1]->isVisible())
                                        neighbors++;
                            }
                            if (world[x][y][z]->isVisible())
                                neighbors++;
                        }
 
 
 
                        if (neighbors>=reproduction && neighbors<=overCrowd)
                        {
                            world[x][y][z]->setVisible(true);
                        }
 
                        if (neighbors>overCrowd)
                        {
                            world[x][y][z]->setVisible(false);
                        }
 
                        if (neighbors<underPop)
                        {
                            world[x][y][z]->setVisible(false);
                        }
 
 
 
                        //cout<<"["<<x<<","<<y<<","<<z<<"] - "<<neighbors<<" Visible: "<<world[x][y][z]->isVisible()<<"\n";
                    }
                }
            }
 
            generation +=1;
 
        }
        }
 
        device->drop();
 
 
 
 
 
    return 0;
}
 

In this version I'm using a scaled up version of the original rules and you can define the starting world size as well as a max world size.

[hybrid]

I think that the whole game of life can run only on the GPU using shaders. Later or soon someone will try that

That's one of the standard examples, so yes, it already exists. But of course this makes the whole application handling a lot different, and some things might even mean to reinterpret the GPU results on the CPU later on.

[REDDemon]

O_O already existing? sob. I need to check more papers on that argument so XD

[Granyte]

I think that the whole game of life can run only on the GPU using shaders. Later or soon someone will try that

you can read papers or you can try this
http://irrlicht.sourceforge.net/forum/v ... fe#p262868

i wonder if it could be made to handle a 3d version of it without compute shader.
i gess 3d texture would be needed for this unles going as hard as me (1024 * 1024 px XD) would be just way to extreme