7
\$\begingroup\$

I've been programming for about 4 months now, just trying to learn by myself. I've tried my way with coding the Game of Life here, would like some general feedback as well as some pointers on how I can speed it up because right now it seems to run incredibly slowly. Keep in mind I'm a newbie so I would like some easy ways to optimize it.

Both positive and negative feedback are very welcome.

Here's the complete code:

public partial class MainFom : Form
{
    Grid formGrid;
    CancellationTokenSource tokenSrc = new CancellationTokenSource();

    public MainFom()
    {
        InitializeComponent();
    }

    private void MainFom_Load(object sender, EventArgs e)
    {
        formGrid = new Grid();
    }

    private void MainFom_Paint(object sender, PaintEventArgs e)
    {
        e.Graphics.DrawImage(formGrid.toBitmap(), 0, 0);
        e.Graphics.Dispose();
    }

    private void startBtn_Click(object sender, EventArgs e)
    {
        Task tempTask = Task.Factory.StartNew(
            (x) =>
            {
                while (!tokenSrc.IsCancellationRequested)
                {
                    formGrid.UpdateGrid();
                    Graphics graphics = this.CreateGraphics();
                    graphics.Clear(this.BackColor);
                    graphics.DrawImage(formGrid.toBitmap(), 0, 0);
                    graphics.Dispose();
                }
            }, tokenSrc);

        startBtn.Hide();
        Button stopBtn = new Button() { Text = "Stop", Location = startBtn.Location, Size = startBtn.Size };
        this.Controls.Add(stopBtn);
        stopBtn.Click += new EventHandler(
            (x, y) => 
            { 
                tokenSrc.Cancel(); 
                stopBtn.Hide();
                startBtn.Show();
                tempTask.Wait();
                tokenSrc = new CancellationTokenSource();
            });

    }
}

class Grid
{
    #region Properties/Fields

    const int MAX_CELLS_X = 41*2;//41;
    const int MAX_CELLS_Y = 35*2;//35;
    Random RNG = new Random();
    CellCollection cells;

    #endregion

    public Grid()
    {
        //Initialize grid (both frontend and backend)
        cells = new CellCollection();

        for (int x = 0; x < MAX_CELLS_X; x++)
        {
            int XCord = 10 * (x + 1);

            for (int y = 0; y < MAX_CELLS_Y; y++)
            {
                int YCord = 10 * (y + 1);
                Point point = new Point(XCord, YCord);

                if (RNG.Next(100) < 7)
                { // 10% chance of initial seed creating a live cell
                    cells.Add(new Cell(new Rectangle(point, new Size(10, 10)), point) { isAlive = true });
                } else
                {
                    cells.Add(new Cell(new Rectangle(point, new Size(10, 10)), point));
                }
            }
        }
    }

    public void UpdateGrid()
    {
        //Create copy of cells since all changes must be done simultaneously
        CellCollection copy = cells;

        for (int i = 0; i < copy.Count; i++)
        {
            //Rule 1: Any live cell with fewer than two live neighbours dies, as if caused by under-population.
            if (cells[i].isAlive && cells.GetNeighbours(cells[i]).Length < 2)
            {
                copy[i].Kill();
            }
            //Rule 2: Any live cell with more than three live neighbours dies, as if by overcrowding.
            if (cells[i].isAlive && cells.GetNeighbours(cells[i]).Length > 3)
            {
                copy[i].Kill();
            }
            //Rule 3: Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
            if (!cells[i].isAlive && cells.GetNeighbours(cells[i]).Length == 3)
            {
                cells[i].Alive();
            }
        }
        // Now that all cells are changed we can copy those changes simulatenously by copying the copy back to the original
        cells = copy;
    }

    public Bitmap toBitmap()
    {
        Bitmap gridBmp = new Bitmap(1000, 1000); // TODO: Find optimal size for bmp

        using (Graphics gfxObj = Graphics.FromImage(gridBmp))
        {
            // Draw grid here and Dispose() on Pen, gfxObj is implicitly disposed
            Pen myPen = new Pen(Color.LightGray);
            SolidBrush myBrush = new SolidBrush(Color.Black);

            foreach (var cell in cells)
            {
                if (!cell.isAlive) {
                    gfxObj.DrawRectangle(myPen, cell.rect);
                } else {
                    gfxObj.FillRectangle(myBrush, cell.rect);
                }
            }
            myPen.Dispose();
        }

        return gridBmp;
    }
}

class CellCollection : List<Cell>
{
    public Cell[] GetNeighbours(Cell cell)
    {
        List<Cell> neighbours = new List<Cell>();

        foreach (Cell entry in this)
        {
            //Top row
            if(entry.point.Y.Equals(cell.point.Y - 10)) {
                if (entry.point.X.Equals(cell.point.X-10) || entry.point.X.Equals(cell.point.X) || entry.point.X.Equals(cell.point.X+10))
                {
                    if (entry.isAlive) {
                        neighbours.Add(entry);
                    }
                }
            }
            // Middle row
            if (entry.point.Y.Equals(cell.point.Y)) {
                if (entry.point.X.Equals(cell.point.X - 10) || entry.point.X.Equals(cell.point.X + 10))
                {
                    if (entry.isAlive) {
                        neighbours.Add(entry);
                    }
                }
            }
            //Bottom row
            if (entry.point.Y.Equals(cell.point.Y + 10))
            {
                if (entry.point.X.Equals(cell.point.X - 10) || entry.point.X.Equals(cell.point.X) || entry.point.X.Equals(cell.point.X + 10))
                {
                    if (entry.isAlive) {
                        neighbours.Add(entry);
                    }
                }
            }
        }

        return neighbours.ToArray();
    }
}

class Cell
{
    public bool isAlive { get; set; }
    public Rectangle rect { get; set; }
    public readonly Point point;

    public Cell(Rectangle rect, Point point)
    {
        this.rect = rect;
        this.point = point;
    }

    public void Alive()
    {
        isAlive = true;
    }

    public void Kill()
    {
        isAlive = false;
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ I updated my answer after you accepted it, to point out another bug. \$\endgroup\$
    – ChrisW
    Commented Mar 14, 2014 at 12:10
  • 2
    \$\begingroup\$ If you want to improve your performance iteratively, use a profiler, find the slowest thing, optimize that. If you want to improve your performance massively, use Gosper's Algorithm, but keep in mind that Gosper's Algorithm is hard to understand and implement unless you have a good grasp on immutable types and memoization. Gosper's Algorithm can easily do boards of a quadrillion cells and calculate trillions of generations per second, which sounds impossible but it is not! \$\endgroup\$ Commented Mar 14, 2014 at 15:19

2 Answers 2

7
\$\begingroup\$

It looks well-written.


You're hard-coding 10 in several places. What if you want to change it to 12, or (worse) to 12.33333? Instead of storing Rect and Point in Cell, I'd suggest storing the zero-based x and y grid coordinate of the cell: that makes your UpdateGrid calculation easier. point and rect can be a property of Cell, calculated on-the-fly ...

Point point { get { return new Point(this.x * 10, this.y * 10); } }

... or initialized in the Cell constructor:

Point point;
int x;
int y;
public Cell(int x, int y)
{
    this.x = x;
    this.y = y;
    this.point = new Point(this.x * 10, this.y * 10);
}

In C# the convention is to use PascalCase instead of camelCase: so IsAlive instead of isAlive etc.


To make it faster, currently you are calling the GetNeighbours method several times for each cell, which is a waste:

    for (int i = 0; i < copy.Count; i++)
    {
        //Rule 1: Any live cell with fewer than two live neighbours dies, as if caused by under-population.
        if (cells[i].isAlive && cells.GetNeighbours(cells[i]).Length < 2)
        {
            copy[i].Kill();
        }
        //Rule 2: Any live cell with more than three live neighbours dies, as if by overcrowding.
        if (cells[i].isAlive && cells.GetNeighbours(cells[i]).Length > 3)
        {
            copy[i].Kill();
        }
        //Rule 3: Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
        if (!cells[i].isAlive && cells.GetNeighbours(cells[i]).Length == 3)
        {
            cells[i].Alive();
        }
    }

It would be better to call that method only once:

    for (int i = 0; i < copy.Count; i++)
    {
        int countNeighbours = cells.GetNeighbours(cells[i]).Length;
        //Rule 1: Any live cell with fewer than two live neighbours dies, as if caused by under-population.
        if (cells[i].isAlive && countNeighbours < 2)
        {
            copy[i].Kill();
        }
        //Rule 2: Any live cell with more than three live neighbours dies, as if by overcrowding.
        if (cells[i].isAlive && countNeighbours > 3)
        {
            copy[i].Kill();
        }
        //Rule 3: Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
        if (!cells[i].isAlive && countNeighbours == 3)
        {
            cells[i].Alive();
        }
    }

Your GetNeighbours returns a List but it only needs to return an integer count.

Your GetNeighbours searches the whole grid for neighbours; it could just find them instead:

// position of this cell
int x = cell.x;
int y = cell.y;
return
    // row above
    IsAlive(x - 1, y - 1) +
    IsAlive(x, y - 1) +
    IsAlive(x + 1, y - 1) +
    // left and right on this row
    IsAlive(x - 1, y) +
    IsAlive(x + 1, y) +
    // row below
    IsAlive(x - 1, y + 1) +
    IsAlive(x, y + 1) +
    IsAlive(x + 1, y + 1);

bool IsAlive(int x, int y)
{
    // x and/or y might be off the board
    if ((x < 0) || (y < 0) || (x >= MAX_CELLS_X) || (y >= MAX_CELLS_Y))
        // no cell here therefore not alive
        return false;
    // find the cell at (x,y)
    int index = (y * MAX_CELLS_X) + x;
    Cell found = this[index];
    return found.isAlive;
}

It would be more conventional to model the Grid as a two-dimensional array than as a one-dimensional list.

Grid probably shouldn't be a subclass of (i.e. inherit from) List: at most it should contain a List as a data member.


You should Dispose your SolidBrush as well as your Pen: do that with further using statements.


This doesn't create a copy:

//Create copy of cells since all changes must be done simultaneously
CellCollection copy = cells;

It creates a variable named copy which is a reference to the same CellCollection as cells.

To create a copy, given that CellCollection is a List, define a 'copy constructor' ...

CellCollection(CellCollection copyFrom)
    // invoke this List constructor:
    // http://msdn.microsoft.com/en-us/library/fkbw11z0(v=vs.110).aspx
    : base(copyFrom)
{
}

... and invoke it e.g. like this:

CellCollection copy = new CellCollection(cells);

There's a typo in your rule #3 processing: you set aliveness of cell instead of copy.


Beware making all your properties settable; for example, your API allows callers to set the isAlive and rect properties:

public bool isAlive { get; set; }
public Rectangle rect { get; set; }

Why have Alive and Kill methods if callers can also/instead set the isAlive property directly? And do you want callers to change the rect property after the cell has been constructed?

Some people (e.g. people who use scripting languages) like a permissive API which allows you to do as much as possible; conversely there's also something to be said for a restrictive API which lets you do as little as possible i.e. only what is necessary and no more: for example if I have no need to change the rect after the Cell is constructed then I don't define an API which permits that.


I just noticed that even making a copy of the grid isn't enough: because the copied list would contain the same Cell instances as the original list. You can fix that:

  • By making a copy (using new Cell) of each Cell as you copy it into the new List
  • Or by saying that Cell is a struct instead of a class
  • Or by giving up on the idea of copying Cells, and adding a new property like bool NextGenerationAliveness which you initialize in UpdateGrid: a) walk through the grid using IsAlive to set NextGenerationAliveness b) walk through the list again to set IsAlive = NextGenerationAliveness.
\$\endgroup\$
10
\$\begingroup\$

Some quick comments:

  • Syntax: coord[inate], not "cord".
  • PascalCase is for public properties/fields, local variables should use camelCase: int xCoord = 9001;

I spot a bug

//Create copy of cells since all changes must be done simultaneously
CellCollection copy = cells;

I do not think this does what you think it does.

Cache calculations

Don't redo this 3 times, once for each of the successive ifs: cells.GetNeighbours(cells[i]).Length.

Make CellCollection a Cell[][]

Instead of a List<Cell>. Because:

  1. It would make the structure match better the format of the data;
  2. It allows you to find the neighbours directly by index (x-1;y-1, x;y-1, etc) instead of travelling the whoooole list like you are doing - what if the board has 1 million cells?

Outdated comment...

if(RNG.Next(100) < 7)
{ // 10% chance of initial seed creating a live cell

10%? Or 6?

Simplifications

instead of

for (int x = 0; x < MAX_CELLS_X; x++)
{
    int xCoord = 10 * (x + 1);

i'd do

for (int x = 1; x <= MAX_CELLS_X; x++)
{
    int xCoord = 10 * x;

And:

var cell = new Cell(new Rectangle(point, new Size(10, 10)), point);
if (RNG.Next(100) < 7)
{
    cell.IsAlive = true;
}
cells.Add(cell);

or

cells.Add(new Cell(new Rectangle(point, new Size(10, 10)), point) { IsAlive = RNG.Next(100) < 7 });
\$\endgroup\$

Your Answer

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

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