Conways Game of Life C#

Question

Not sure if this is the correct place for this question or SO - mods please move if necessary.

I am going to have a go at creating GoL over the weekend as a little test project : http://en.wikipedia.org/wiki/Conway's_Game_of_Life

I understand the algorithm, however I just wanted to check regarding the implementation, from maybe somebody that has tried it. Essentially, my first (basic) implementation, will be a static grid at a set speed.

If I understand correctly, these are the steps I will need:

1. Initial seed
2. Create 2d array with initial set up
3. Foreach iteration, create temporary array, calculating each cells new state based on the Game of Life algorithm
4. Assign temp array to proper array.
5. Redraw grid from proper array.

My concerns are over speed. When I am populating the grid from the array, would it simply be a case of looping through the array, assigning on or off to each grid cell and then redraw the grid?

Am I on the correct path?

Answer 1

Instead of creating a temporary array for use when you update the game grid, you can get a simpler algorithm and better speed if you create 2 grids and fill one grid using data from the other. That way you don't have to cencern yourself with not overwriting current data in the next pass.

I.e. the grids take turns being updated;

1. fill grid1 with the initial setup
2. update the display using grid1
3. build grid2 using the data in grid1
4. swap grid1 and grid2
5. proceed to step 2

Answer 2

Your proposal sounds fine; you will not win any speed records but you will certainly learn how to build a basic Life implementation.

Once you have it all working using the simple implementation, consider implementing Gosper's Algorithm. You can calculate billions of generations per second on boards that are billions of times larger than you'd think would fit into your memory; it uses techniques from functional programming to achieve immense compression of both time and space. You'll learn a lot about both graphics and data structures.

Answer 3

I've actually done this myself in C#, and I did it pretty much the same way you're describing it. It wasn't very fast, but essentially I had an array of cells, and at every turn I created a temporary array and populated it based on the current array, then copied it to the new one, sort of like double buffering.

There exist faster algorithms for the Game of Life than going through each cell one by one that can give near-instantaneous results but I haven't researched the topic enough to tell you anything about them.

Answer 4

I would try, and I know this is somehow possible in .NET, to postpone 'physical' redrawing of the grid until all cells have been assigned their new value. The graphics library and hardware can redraw the whole

Answer 5

One tip of calculating the population of the new cell is to avoid doing addition for the eight surrounding cells each time. Instead, keep a counter and a few sums for left and right columns when you move to the next right cell:

counter = counter - lastLeftSum + newRightSum

This will save you a lot of array indexing and addition calculation.

I also tried the idea of partitioning the board to avoid calculation on large empty areas but didn't go through the implementation (complexity explodes). However, I think this approach allows your program to handle huge boards nicely. I can see some immediate improvements allowed by partioning:

1. Allows storing some common patterns to predict the board situation without calculation.
2. Parallel processing.

With a faster simulator, maybe more interesting setup can be discovered.