5
\$\begingroup\$

I'm working on a Game Of Life clone as my first project. I'm still relatively new to programming, so my code is probably not really optimised.

The biggest bottleneck is in my Start() method, but that contains a lot of Unity3D specific methods which most people here probably don't know about. That's why I'm leaving that out.

My second bottleneck is somewhere in my Update() method. In here, I'm looping through my array which is currently 100 by 100 large, 10.000 in total.

I've been checking with the built-in profiler of Unity3D, and this reports that the biggest bottleneck is the garbage collection.

I also tried to put half of the loop in another thread, but that didn't work out properly, because it needs to look up cells in the other half.

If you see any other ways to improve my code, and not just the performance, feel free to let me know. But please, keep it simple, as I'm still relatively new to programming.

The relevant code:

void Update()       
{
    timeElapsed += Time.deltaTime;                  // this will add deltaTime to timeElapsed,
    if (timeElapsed >= timeBetween)                 // until timeElapsed exceeds timeBetween, 
    {                                               // which allows a new generation to be calculated
        timeElapsed -= timeBetween; 
        if (gameState == GameState.Game_Playing)
        {               
            grid = CheckAdjacent(grid);             // draw new generation
            UpdateInformation();                    // update information variables
        }
    }
}

public static void DrawGeneration(bool[,] grid)
{
    for (int x = 0; x < gridX; x++)
    {
        for (int y = 0; y < gridY; y++)
        {
            cubeGrid[x,y].renderer.enabled = grid[x,y]; // enables the renderer for active cells.
        }
    }
}

private void UpdateInformation()
{
    generation++; //counts the generations
}

public static int GetAliveCells ()
{
    int i = 0;
    for (int x = 0; x < gridX; x++)
    {
        for (int y = 0; y < gridY; y++)
        {
            if (grid[x, y]) // counts the number of alive cells
                i++;
        }
    }       
    return i;
}   

bool IsCellAlive(int adjacentCount, bool isAlive)
{
    if (isAlive)
        return liveRule.Contains(adjacentCount);
    else
        return becomeAliveRule.Contains(adjacentCount);
}

private bool[,] CheckAdjacent(bool[,] grid)
{
    int adjacentSquares = 0;
    bool[,] newGrid = new bool[gridX, gridY];

    for (int x = 0; x < gridX; x++)
    {
        for (int y = 0; y < gridY; y++)
        {
            adjacentSquares = 0;                

            if (grid[calcX(x - 1), calcY(y - 1)])
                adjacentSquares++;              
            if (grid[calcX(x), calcY(y - 1)])
                adjacentSquares++;              
            if (grid[calcX(x + 1), calcY(y -1)])
                adjacentSquares++;              

            if (grid[calcX(x - 1), calcY(y)])
                adjacentSquares++;
            if (grid[calcX(x + 1), calcY(y)])
                adjacentSquares++;

            if (grid[calcX(x - 1), calcY(y + 1)])
                adjacentSquares++;
            if (grid[calcX(x), calcY(y + 1)])
                adjacentSquares++;
            if (grid[calcX(x + 1), calcY(y + 1)])
                adjacentSquares++;

            newGrid[x,y] = IsCellAlive(adjacentSquares, grid[x,y]);
        }
    }       
    return newGrid; 
}

private int calcX(int x)
{
    x += gridX;
    return (x % gridX);
}

private int calcY(int y)
{
    y += gridY;
    return (y % gridY);
}
\$\endgroup\$
1
  • \$\begingroup\$ This is too awesome... favourited! \$\endgroup\$
    – ANeves
    Feb 14, 2012 at 16:06

2 Answers 2

5
\$\begingroup\$
  1. I would advise you to count neighbours from alive points, not for cells to be checked. Null a 100x100 int array Neighbours. For every alive cell add +1 into every neighbouring cell in Neighbours. After the pass you have number of neighbours for the every cell, but time used is about 1/4 at most, because you saved the time not counting neighbours for zero cells.

  2. You are taking left neighbours for utmost left cells, for example. Out of boundaries! You are blocking this by taking a function and modulo and thus making the toroid out of plane, but thus you are counting much longer - division or modulo are slow, functions even more slow. Simply count neighbours normally for the field except boundaries, otherwards for the four sides and four corners. More to write, but less to count later.

  3. If you want a shorter code, you could use a help arrays ( I have invented them for myself in 1978)

    // neighbor-vectors in xy coordinates clockwise from algebraic x axis.
    int [8] dx={1,1,0,-1,-1,-1,0,1};
    int [8] dy={0,-1,-1,-1,0,1,1,1};
    

    and in counting neighbours for a cell do:

    if(cell[x,y]>0)
    for(i=0;i<8;i++){
       x1=x+dx[i];
       y1=y+dy[i];
       if(x1>=0 & x1<100 & y1>=0 & y1<100){
           neighbours[x1,y1]++;
       }
    }
    
  4. Count the time spent for different activities, for not to waste time on optimizing part that takes 0.1% of time.

    So you can throw off many objects, not to create them at all. Only hold 2 desk in 2x100x100 array - each time one will be active, the other will be old. You can even count neighbours and later make living/dead cells on the same desk. No garbage collection.

\$\endgroup\$
5
  • \$\begingroup\$ Thank you very much for the help! Will try to implement it later, at home. With suggestion 4, do you mean to make the array [2, 100, 100], instead of 2 arrays of [100, 100]? \$\endgroup\$ Feb 14, 2012 at 9:35
  • \$\begingroup\$ You are welcome. Yes, thus you could easier switch from one to another. BTW, if you like some post, except thanks there are upvotes and answer markings :-) \$\endgroup\$
    – Gangnus
    Feb 14, 2012 at 9:48
  • \$\begingroup\$ I know ;) Was a bit in a hurry and didn't think of upvoting. \$\endgroup\$ Feb 14, 2012 at 10:06
  • \$\begingroup\$ Of course, you can also make array [2] of arrays [100,100]. Choose what is more understandable. But if you make the desk as an object, that will have array and, for example, the number of generation, and/or other things, then Desk[2] array would be more natural \$\endgroup\$
    – Gangnus
    Feb 14, 2012 at 10:36
  • \$\begingroup\$ The garbage collection problem will go away if you allocate two grids and 'double buffer' by reading from one to the other on each generation and then back the other way on the next. That is what @Gangnus is recommending at the end of his post. \$\endgroup\$
    – user59064
    Dec 30, 2014 at 10:31
4
\$\begingroup\$

@Gangnus made some very good suggestions. But additionally, two ideas.

  1. Instead of having a grid of bool and calculate each cell, why not have an intermediate grid of int?

  2. Another improvement might be to harness the power of parallel processing: http://www.dotnetcurry.com/ShowArticle.aspx?ID=608
    Instead of using regular for cycles, and since each iteration is independent from all other iterations, you can convert for(int i=0; i<10; i++) { ... } into Parallel.For(0, 10, i => { ... });.

This second one is more advanced than what you are looking for and specifically asked, but very interesting nevertheless. You can still disregard it and look into only the first one.

So your CheckAdjacent method could be:

private bool[,] CheckAdjacent(bool[,] grid) {
    int[,] newGrid = new int[gridX, gridY];
    Parallel.For(0, gridX, x => {
        Parallel.For(0, gridY, y => {
            if(grid[x,y]) {
                IncrementNeighbours(newGrid, x ,y);
            }
        });
    });
    bool[,] newGridBools = new bool[gridX, gridY];
    Parallel.For(0, gridX, x => {
        Parallel.For(0, gridY, y => {
            newGridBools[x,y] = IsCellAlive(newGridBools[x,y], grid[x,y]);
        });
    });
    return newGridBools;
}

// @Gangnus' code fits perfectly. YOINK! <3
// This can probably be improved; but what for, if it works perfect?
static readonly int [8] dx={1,1,0,-1,-1,-1,0,1};
static readonly int [8] dy={0,-1,-1,-1,0,1,1,1};
private void IncrementNeighbours( int[,] newGrid, int x, int y ) {
    for(i=0; i<8; i++){
        x1=x+dx[i];
        y1=y+dy[i];
        if(x1>=0 & x1<100 & y1>=0 & y1<100){
            neighbours[x1,y1]++;
        }
    }
}
\$\endgroup\$
8
  • \$\begingroup\$ I especially like the Parallel.For(). Have been looking for something similar before, but regular threading, or even GPGPU didn't work. This will probably be a large improvement in speed! \$\endgroup\$ Feb 14, 2012 at 16:45
  • \$\begingroup\$ Unfortunately, Unity doesn't seem to support .NET 4.0 :( \$\endgroup\$ Feb 14, 2012 at 17:56
  • \$\begingroup\$ Thank you for the compliment. I haven't even supposed the possibility to use booleans :-). Use of integers was so obvious for me, that I haven't declared it explicitly. Of course, it should be done. --- What is "YOINK <3", please ? --- I thint your idea of parallel computing would be the best realised on the graphic cards for this task. Uhm. not for this, of course, but if the desk will be 10000x10000. \$\endgroup\$
    – Gangnus
    Feb 15, 2012 at 9:14
  • \$\begingroup\$ @SimonVerbeke not supported? Ah well. But this Parallel.For seems really useful; I just learned about here somewhere here on codereview too. \$\endgroup\$
    – ANeves
    Feb 15, 2012 at 9:29
  • \$\begingroup\$ @Gangnus YOINK <3 is a "yoink" and a heart. An attempt at showing appreciation. \$\endgroup\$
    – ANeves
    Feb 15, 2012 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.