Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
1  
This questions belongs to StackOverflow. –  LennyProgrammers Feb 21 '11 at 16:16
    
This question doesn't belong on SO as is. It's too vague, and I'd vote to close it there too. It would be better if the OP were to try something and run into a specific problem. –  David Thornley Feb 21 '11 at 16:38
2  
When you get it done, consider doing it in 3D as well.It's exactly the same, but you have a 3D array and render the cells inside a cube instead. Also render the cells as points and use thousands of them. The effect is awesome, akin to a morphing cloud. Very cool! –  Martin Wickman Feb 21 '11 at 17:28
    
@Martin - that sounds pretty awesome. Will definately give that a try when I have finished the 2d one. In the 3d version, each cell will obviously have more neighbours, do you alter the algorithm?? –  Darren Young Feb 21 '11 at 17:33
    
The algorithm should be the same, except you must look for neighbors in more directions. –  Martin Wickman Feb 21 '11 at 18:00

5 Answers 5

up vote 3 down vote accepted

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
share|improve this answer
    
Sounds good. I think I will implement both and then measure the speed, for interest purposes. –  Darren Young Feb 21 '11 at 17:35

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.

share|improve this answer
    
Excellent - thanks for the info re Gospers. Will certainly have a look at that. –  Darren Young Feb 23 '11 at 19:24

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.

share|improve this answer
    
Thanks for the comment. –  Darren Young Feb 21 '11 at 17:35

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

share|improve this answer
    
Yes, that's what I intend to do. Basically re-populate the grid, and then invalidate it so that it redraws. –  Darren Young Feb 21 '11 at 17:34

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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