Optimizing Conway's Game of Life code to run faster

Question

How could I take this code and optimize it so that I could possibly run Conway's Game of Life on a large grid at 15 frames per second?

public partial class MainWindow : Window
{

Cell[,] activeCells;
//List<Cell> nextGenCells;

static Timer time;
bool onOff = true;

int columnNum = 10;
int rowNum = 10;
int codeColumn;
int codeRow;

public MainWindow()
{
    InitializeComponent();
    createGrid(10, 10);
}

public void createGrid(int width, int height)
{
    if (cellPanel != null)
    {
        cellPanel.Children.Clear();
        codeColumn = width;
        codeRow = height;

        cellPanel.Columns = width;
        cellPanel.Rows = height;

        activeCells = new Cell[width, height];


        for (int i = 0; i < cellPanel.Columns; i++)
        {
            for (int j = 0; j < cellPanel.Rows; j++)
            {
                activeCells[i, j] = new Cell();

                Rectangle cellSpot = new Rectangle();
                cellSpot.Height = 35;
                cellSpot.Width = 35;
                cellSpot.DataContext = activeCells[i, j];
                cellSpot.MouseLeftButtonDown += activeCells[i, j].Clicked;

                Binding b = new Binding("IsAlive");
                b.Source = activeCells[i, j];
                b.Converter = (BoolToBrushConverter)Application.Current.FindResource("cellSwitch");
                cellSpot.SetBinding(Rectangle.FillProperty, b);

                cellPanel.Children.Add(cellSpot);
            }
        }
    }
}

public int getLivingNeighbors(int x, int y)
{
    int count = 0;

    if (x != codeColumn - 1)
    {
        //right
        if (activeCells[x + 1, y].IsAlive)
        {
            count++;
        }
    }

    if (y != codeRow - 1)
    {
        //down
        if (activeCells[x, y + 1].IsAlive)
        {
            count++;
        }
    }

    if (x != 0)
    {
        //left
        if (activeCells[x - 1, y].IsAlive)
        {
            count++;
        }
    }

    if (y != 0)
    {
        //up
        if (activeCells[x, y - 1].IsAlive)
        {
            count++;
        }
    }

    if (x != 0 && y != 0)
    {
        //diagonal upperleft
        if (activeCells[x - 1, y -1].IsAlive)
        {
            count++;
        }
    }

    if (x != codeColumn-1  && y != 0)
    {
        //diagonal upperright
        if (activeCells[x + 1, y - 1].IsAlive)
        {
            count++;
        }
    }

    if (x != codeColumn - 1 && y != codeRow - 1)
    {
        //bottomright diagonal
        if (activeCells[x + 1, y + 1].IsAlive)
        {
            count++;
        }
    }

    if (x !=0 && y != codeRow -1)
    {
        //bottomleft diagonal
        if (activeCells[x - 1, y + 1].IsAlive)
        {
            count++;
        }
    }


    return count;
}


public void updateCells()
{
    List<Cell> nextGenCells;
    nextGenCells = new List<Cell>();

    for (int i = 0; i < codeColumn; i++)
    {
        for (int j = 0; j < codeRow; j++)
        {

            Cell c = activeCells[i, j];




            int neighbors = getLivingNeighbors(i, j);

            if (c.IsAlive && neighbors < 2)
            {
                nextGenCells.Add(c);
            }


            if (c.IsAlive && neighbors > 3)
            {
                nextGenCells.Add(c);
            }



            if (!c.IsAlive && neighbors == 3)
            {
                nextGenCells.Add(c);
            }

        }
    }

    foreach (Cell cell in nextGenCells)
    {
        cell.IsAlive = !cell.IsAlive;
    }
}


private void oneGenerationButton_Click(object sender, RoutedEventArgs e)
{
    updateCells();
}

private void CreateBoardButton(object sender, RoutedEventArgs e)
{
    rowNum = (int) heightSlider.Value;
    columnNum = (int)widthSlider.Value;
    createGrid(rowNum, columnNum);
}

private void randomizeButton_Click(object sender, RoutedEventArgs e)
{
    Random rand = new Random();


    for (int i = 0; i < codeColumn; i++)
    {
        for (int j = 0; j < codeRow; j++)
        {
            if (rand.Next(0, 3) == 1)
            {
                activeCells[i, j].IsAlive = true;
            }
            else
            {
                activeCells[i, j].IsAlive = false;
            }
        }
    }
}

private void playButton_Click(object sender, RoutedEventArgs e)
{
    if(onOff)
    {
        onOff = !onOff; 
        time = new Timer(1000 / speedSlider.Value);
        time.Elapsed += time_Elapsed;
        time.Start();
        playButton.Content = "Stop";
    }
    else
    {
        onOff = !onOff;
        time.Stop();
        playButton.Content = "Play";
    }
}

void time_Elapsed(object sender, ElapsedEventArgs e)
{
    updateCells();
}

I've optimized it as much as I know how, but there has to be a way to do so even more so that it will run as quickly as I need it to. I've thought that maybe the 2D array is slowing me down, or possibly all iterating through for loops, but I am unsure of how I could work around those and have a higher speed rate.

I've also looked into Hashlife, but I do not know how to implement it.

class Cell:

class Cell : INotifyPropertyChanged
    {
        public event PropertyChangedEventHandler PropertyChanged;

        bool _isAlive;

    public void Clicked(object sender, System.Windows.Input.MouseButtonEventArgs e)
    {
        IsAlive = !IsAlive;

    }

    public bool IsAlive
    {
        get { return _isAlive; }
        set
        {
            _isAlive = value;

            if(PropertyChanged !=null)
                    PropertyChanged(this, new PropertyChangedEventArgs("IsAlive"));
        }
    }
}

XAML:

<Window x:Class="ConwaysGameofLife.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        Title="MainWindow" Height="500" Width="700">
    <Grid>
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="35*" />
            <ColumnDefinition Width="65*" />
        </Grid.ColumnDefinitions>

        <StackPanel>

            <Grid Margin="10px">
                <Grid.ColumnDefinitions>
                    <ColumnDefinition Width="8*" />
                    <ColumnDefinition Width="2*" />
                </Grid.ColumnDefinitions> 

                <Grid.RowDefinitions>
                    <RowDefinition Height="30px"/>
                    <RowDefinition Height="30px"/>
                    <RowDefinition Height="30px"/>
                    <RowDefinition Height="30px"/>
                </Grid.RowDefinitions>

                <Label Content="Height" />

                <Slider x:Name="heightSlider"
                        Grid.Column="0"
                        Grid.Row="1"
                        TickFrequency="1" 
                        Minimum="10"
                        Maximum="100"
                        SmallChange="1"
                        LargeChange="10"
                        IsSnapToTickEnabled="True"/>
                <Label Grid.Column="1"
                       Grid.Row="1"
                       Content="{Binding ElementName=heightSlider, Path=Value}"
                       HorizontalAlignment="Center"/>

                <Label Content="Width"
                       Grid.Row="2" />

                <Slider x:Name="widthSlider"
                        Grid.Column="0"
                        Grid.Row="3"
                        TickFrequency="1" 
                        Minimum="10"
                        Maximum="100"
                        SmallChange="1"
                        LargeChange="10"
                        IsSnapToTickEnabled="True"/>
                <Label Grid.Column="1"
                       Grid.Row="3"
                       Content="{Binding ElementName=widthSlider, Path=Value}"
                       HorizontalAlignment="Center"/>
            </Grid>

            <Button x:Name="breateBoardButton"
                    Content="Create Board"
                    Height="25px"
                    Width="110px"
                    Margin="5" Click="CreateBoardButton" />

            <Button x:Name="oneGenerationButton"
                    Content="Step Generation"
                    Height="25px"
                    Width="110px"
                    Margin="5" Click="oneGenerationButton_Click"/>

            <Button x:Name="randomizeButton"
                    Content="Randomize Grid"
                    Height="25px"
                    Width="110px"
                    Margin="5" Click="randomizeButton_Click"/>

            <Label Content="Speed" />

            <Grid Margin="10px">
                <Grid.ColumnDefinitions>
                    <ColumnDefinition Width="8*" />
                    <ColumnDefinition Width="2*" />
                </Grid.ColumnDefinitions>

                <Slider x:Name="speedSlider"
                        TickFrequency="1" 
                        Minimum="1"
                        Maximum="15"
                        SmallChange="1"
                        LargeChange="10"
                        IsSnapToTickEnabled="True"/>
                <Label Grid.Column="1"
                       Content="{Binding ElementName=speedSlider, Path=Value}"
                       HorizontalAlignment="Center"/>
            </Grid>

            <Button x:Name="playButton"
                    Content="Play"
                    Height="40px"
                    Width="100px"
                    FontSize="20px"
                    Margin="5" Click="playButton_Click"/>

        </StackPanel>

        <UniformGrid x:Name="cellPanel"
                     Columns="10"
                     Rows="10"
                     Grid.Column="1"/>
    </Grid>
</Window>

Answer 1

        if (rand.Next(0, 3) == 1)
        {
            activeCells[i, j].IsAlive = true;
        }
        else
        {
            activeCells[i, j].IsAlive = false;
        }

I'd assign the variable like activeCells[i, j].IsAlive = (rand.Next(0, 3) == 1); instead. It simplifies the structure.

---

        if (c.IsAlive && neighbors < 2)
        {
            nextGenCells.Add(c);
        }


        if (c.IsAlive && neighbors > 3)
        {
            nextGenCells.Add(c);
        }



        if (!c.IsAlive && neighbors == 3)
        {
            nextGenCells.Add(c);
        }

If you use else if here, that should save you a couple cycles.

---

List<Cell> nextGenCells;
nextGenCells = new List<Cell>();

Declare this on one line, there's no reason for you to split it up like you do.

---

public int getLivingNeighbors(int x, int y)

This function is filled with repeated if statements containing combinations of previously tested variables. Consider storing those in temporary variables instead and reusing them. That should improve readability.

Additionally, I can think of a couple things you could try to increase performance on an algorithmic level:

• Turn Cells into a net of objects where each object has a reference to its neighbors. This allows you to perform a for-loop over each cell's neighbors, counting isAlive. Such a thing might simplify and speed up the algorithm. Do your own benchmarking to test this.
• Skip large sections of empty cells. This might be hard to implement in the array based implementation, but if you kept a list of live cells, you could opt to check only the live cells and their neighbors. You could even enable and disable this strategy as certain percentages of tiles are alive, or just check per 5x5 block if it contains live cells. Having some sort of class to track sections also allows you to keep some sort of hasChanged flag, only including the section in calculations if hasChanged is true.
• Surround your actual grid with dead cells that you never check. This saves all the if-statement complexity at the cost of some memory.
• Alter your algorithm to return early. You check for up to 8 living neighbors, but any neighbor count above 4 is irrelevant.

Answer 2

There's nothing inherently slow in the code that I can see. However, in my opinion WPF is not particularly good at this kind of thing.

I think what might be happening is that the property changed events are being fired each time you set the IsAlive flag in the loop at the end of updateCells. This probably causes WPF to redraw the screen many more times than it should.

Try removing the PropertyChanged call from the IsAlive property and just call it once at the end of the update with an empty string.

So the first change is to try and remove the property changed call from IsAlive.

set
{
    _isAlive = value;

    //if(PropertyChanged !=null)
    //        PropertyChanged(this, new PropertyChangedEventArgs("IsAlive"));
}

At this point it might actually be enough to fix the issue, or at least see if that is the issue. Although, I suspect you will still need to raise a property changed event somehow.

The ideal place to raise it would be at the end of updateCells after setting all of the IsAlive properties. Raising it with string.Empty should tell WPF to update everything.

public void updateCells()
{
    // ... other code ...

    foreach (Cell cell in nextGenCells)
    {
        cell.IsAlive = !cell.IsAlive;
    }

    if(PropertyChanged !=null)
        PropertyChanged(this, new PropertyChangedEventArgs(string.Empty));
}

Of course, for code to compile your main window would need to implement INotifyPropertyChanged. Typically this is a pretty odd design, in my experience you would normally have a ViewModel instead of coding things in the code behind of the main window.

There might be some alternative way to refresh the main window but I'm not sure.

In any case, I'm just making guesses from experience. I would recommend running a profiler over the code to be sure.