views:

4290

answers:

21

Alright, so I've always wanted to write myself a nice little Game of Life program where you could play with the rules and adjust the number of cells and such; I've just never really had the time to mess around to do this (until recently). I understand the basic algorithm and such (if you don't, go to the Game of Life Wikipedia page to check it out.) but only have a little experience with GUI programming. I'm considering doing this in python, but I was really wanting to figure out how to go about doing this in general, so feel free to give code snippets in your language of choice.

To summarise:

  • How would you go about programming a "Conway's Game of Life" simulation in your language of choice?
+32  A: 

Don't just dive in. The project sounds easy and exciting but if you just dive in and start hacking away at it you may find it difficult to cope if you get stuck.

In fact, this sort of project is ideal for pulling the model of your application (a grid of little organisms that obey certain rules) from the User Interface (Pointy-Clicky-Shiny Fun). I'd highly recommend that you investigate a unit testing framework for your chosen language (I can't recommend a Python one I'm sorry) and build a Model of the little organisms without any UI.

Perhaps make it an object with a method on it that moves the Game of Life forward by one step and exposes a two-dimensional array of where all the creatures are at any given moment. This way you can add a timer later on that moves the game forward at a variable speed (useful for Game of Life).

Once the Model is working you can build a simple UI which "watches" the model of the little organisms and displays them to you (the user). This will be easier if the model can notify observers when it changes (like at a timestep). At this point you are sure that the Game of Life bits are working and you can concentrate on the UI (the View to be precise).

If you want to add some user control then add in a new component to respond to user events and have it update the model directly. Again you are only changing a single component and you know that the Model and the view was already working. You can call this component a Controller.

Now you have a Model, a View and a Controller and you can independently change how the system:

  1. responds to a single timestep (by adjusting the Model)
  2. displays it's info (by adjusting the View)
  3. reacts to use input (by adjusting the Controller)

If you haven't seen it before this is a standard design pattern frequently abbreviated to MVC.

Wolfbyte
From a pragmatic perspective, I agree. But this approach would just spoil the fun!
Artelius
If he were looking at building a commercial product or a framework for larger projects I would agree with you 100% but it sounds like he just wants a fun "learn the language/api" project. Trying to figure out the "right" way to structure your code in a new language is suicidal. Just have fun!
Toji
@Toji I can see your point but the problem with wading into a new language on a not insignificant project is that when you get stuck, you get really stuck. You could go either way but I'd go for structure most of the time. These patterns transcend language and act like a safety net for first-timers.
Wolfbyte
+1 for mentioning MVC.
Ionuț G. Stan
This sounds a little overengineered for a relatively simple project o_O
int3
plus: getting stuck is good for practicing refactoring^
Dave
+1  A: 

If you wanted to be super simple about it, you could take your favorite graphics API and have each pixel represent a single cell. That takes away all of the difficulties of GUI programming, though interfacing with the grid would require some input handling.

If you want to provide a more complete GUI, .NET is a very straightforward way to go, and it's probably the solution I would take. I'm biased, though, given my C# experience. Python has good GUI modules, I'm sure. I've worked with Tkinter, and I've heard good things about wxPython. Pick your poison.

Daniel F. Hanson
A: 

Keep it simple from the start.

My personal preference would be to use python because it simplifies a number of the problems I anticipate but when I wrote my version of Life it was in Sinclair Basic 20 years ago :)

If you put together something simple in C (or C++) consider submitting it to Cymons as a community learning tool.

sparkes
+2  A: 

I've written a few implementations of Conway's Game of Life. I find it quite a fun way to get comfortable with the graphics side of a language. It's nice and simple - my first implementation was in x86 assembly (good old mode 13h :). Most recently, I did one in SDL/C.

All you need is two pixel buffers of the same size, one seeded with some random pixels. Then you just repeatedly apply the rules of life (count live neighbours, etc) to each pixel in one buffer, putting the resulting "dead" or "alive" pixel/cell in the same (x,y) location, but in the other buffer. Each iteration, swap the buffers, and copy one to the screen.

Once you have the thing working, it should be easy enough to add Pause/Play buttons, and simple drawing controls to create live/dead cells.

Blorgbeard
+7  A: 

Chapters 17 and 18 of Michael Abrash's Graphics Programmer's Black Book are one of the most interesting reads I have ever had. It is a lesson in thinking outside the box. The whole book is great really, but the final optimized solutions to the Game of Life are incredible bits of programming.

Chris Marasti-Georg
I also remember a talk he game at some conference - I saw the video of it on Gamasutra back in the day (back when streaming video was "wow"). Highly recommend experimenting with some of the techniques that he writes about.
Daemin
The links no longer work.
Michael Myers
Thanks mmyers, the links have been updated to a mirror that works.
Chris Marasti-Georg
+33  A: 

Just dive in. This project is easy and exciting, and if you just dive in and start hacking away at it you will learn quickly and be rewarded with instant results.

Once you have working code, you can easily upgrade it and expand it as you see fit.

The grid can be represented by a 2D array of Cell data types, where at first they might just be boolean. When the timer goes off, you create another 2D array in memory based on the rules of life, and then apply the rules.

Once you start playing with this, you are likely to find that this implementation is too slow. At this point the fun begins, where you learn how to optimize for speed and try to minimize your processing footprint.

For example, one optimization you can do is have each Cell remember its neighbors' states, and then when you update the Cell, you simply use its own data to calculate the next result. Don't forget to update each neighbor when Cell changes though!

As for which programming language and GUI you plan to use, this would be a good time to ask yourself, "Which language do I want to start becoming good at?" I would recommend C and SDL, just because it seems like they would be a fun combination for this.

superjoe30
A: 

I have used an Agent Modelling Framework in Java called Ascape which is available on sourceforge. It removes the need for understanding UI and handles things such as Von-Newmann neighbourhoods for you. This way you can get to the interesting part of the problem without needing to worry about the boring frameworky sort of things. The guy who created Ascape is fantasticly helpful and very active on ther user forums, so you can always go there and ask for help (as I have done myself a few times!)

It is fantasticly easy for this type of problem. It even has an example of conways game of life if you get stuck (but give it a shot yourself first!)

Aidos
+3  A: 

Conway's G.O.L. is a great way to explore some aspects of low-level bit twiddling!

One speed up trick to try, the learning of which can lead to more general insights on optimizing algorithms, is handle a running count of neighboring cells that you retain and update as you iterate over cells.

Consider a 4x3 block of cells,

A B C D  
E F G H  
I J K L

When computing the new state for cell F, you add the states of the nine cells A B C E F G I J K. Do some logic, save the next state in another buffer.

Next we compute cell G. Rather than add up the nine cells B C D F G H J K L, we retain the count from computing F. Subtract B F J and add D H L - only six operations. 50% faster - at the cost of some monkeying around with handling the first and last cells of each row.

DarenW
Surely Subtract A E I?
Paul Smith
uh, yeah. oops. good thing i'm not a brain surgeon.
DarenW
+3  A: 

Here is a really quick and very dirty implementation in C#. It uses a picturebox 599 by 399 pixels wide, a timer and a button. You should be able to figure out the events handled from the code below. I thought it could be fun to pick apart as some kind of collective code review.

You need to draw your starting colony with the mouse in the picturebox. Enjoy!

using System;
using System.Drawing;
using System.Windows.Forms;

namespace GameOfLife
{
public partial class MainForm : Form
{
    cField Field = new cField();
    bool MouseIsDown = false;

    public MainForm()
    {
        InitializeComponent();


    }

    private void pictureBox1_Paint(object sender, PaintEventArgs e)
    {
        for (int i = 0; i < 150; i++)
            for (int j = 0; j < 100; j++)
                if (Field.Cells[i, j] > 0)
                    e.Graphics.DrawRectangle(new Pen(Color.FromArgb(Math.Min(Field.Cells[i,j], 255), Math.Min(Math.Max(Field.Cells[i,j]-255, 1), 255), Math.Min(Math.Max(Field.Cells[i,j]-512, 1), 255)), 2), i * 4, j * 4, 2, 2);
    }

    private void btnStart_Click(object sender, EventArgs e)
    {
        timer1.Enabled = !timer1.Enabled;
        pictureBox1.Refresh();
        btnStart.Text = timer1.Enabled ? "Stop" : "Start";
    }

    private void timer1_Tick(object sender, EventArgs e)
    {
        Field.Recalculate();
        pictureBox1.Refresh();
    }

    private void pictureBox1_MouseDown(object sender, MouseEventArgs e)
    {
        timer1.Enabled = false;
        MouseIsDown = true;
        Field.Cells[e.X / 4, e.Y / 4] = 1;
    }

    private void pictureBox1_MouseMove(object sender, MouseEventArgs e)
    {
        if (e.X < 0) return;
        if (e.Y < 0) return;
        if (e.X / 4 > 149) return;
        if (e.Y / 4 > 99) return;

        if (MouseIsDown)
        {
            Field.Cells[e.X / 4, e.Y / 4] = 1;
            pictureBox1.Refresh();
        }
    }

    private void pictureBox1_MouseUp(object sender, MouseEventArgs e)
    {
        MouseIsDown = false;
        if (btnStart.Text == "Stop")
            timer1.Enabled = true;
    }
}

public class cField
{
    public int[,] Cells = new int[150,100];
    public int[,] newCells = new int[150, 100];

    public void Recalculate()
    {
        int neighbours = 0;

        for (int i = 0; i < 150; i++)
            for (int j = 0; j < 100; j++)
                newCells[i, j] = 0;

        for (int i = 0; i < 149; i++)
            for (int j = 0; j < 99; j++)
            {
                neighbours = 0;

                if (i > 0 && j > 0)
                {
                    if (Cells[i - 1, j - 1] > 0)
                        neighbours++;
                    if (Cells[i - 1, j] > 0)
                        neighbours++;
                    if (Cells[i - 1, j + 1] > 0)
                        neighbours++;

                    if (Cells[i, j - 1] > 0)
                        neighbours++;
                    if (Cells[i, j + 1] > 0)
                        neighbours++;

                    if (Cells[i + 1, j - 1] > 0)
                        neighbours++;
                }

                if (Cells[i + 1, j] > 0)
                    neighbours++;
                if (Cells[i + 1, j + 1] > 0)
                    neighbours++;

                if (neighbours < 2)
                    newCells[i, j] = 0;
                if (neighbours > 3)
                    newCells[i, j] = 0;
                if ((neighbours == 2 || neighbours == 3) && Cells[i, j] > 0)
                    newCells[i, j] = Cells[i,j]+10;
                if (neighbours == 3 && Cells[i, j] == 0)
                    newCells[i, j] = 1;
            }

        for (int i = 0; i < 150; i++)
            for (int j = 0; j < 100; j++)
                Cells[i, j] = newCells[i,j];
    }
}
}
Niklas Winde
A: 

Here's my submission http://madcoderspeak.blogspot.com/2007/02/test-driving-conways-game-of-life-in.html
I used this example to learn Ruby as well as TDDing in Ruby. It's a non-optimized version. I spent a weekend trying to optimize it by keeping neighbour counts to predict next generations... but couldn't manage to get it right.

Gishu
+1  A: 

How about a Game of Life on a GPU (on XNA)

epatel
+1  A: 

Long ago on the Amiga I wrote a program (and an article for Amazing Computing) of a way to implement Conway's Life that used the blitter as a parallel adder. The basic idea was to think of the screen as an array of 4-bit accumulators that can be implemented as 4 bitplanes. By using the 3 input capability of the Amiga's blitter one could generate sums for all pixels in 9 blit operations. It ran really really fast. Bonus is you can make the actual 'cells' look like anything, glossy bubbles or whatever.

Scott Evernden
I remember you. That was a big deal. I loved Amazing, too (even though I worked for Amiga Resource Magazine).
Nosredna
+1 That was a nice hack.
Michael Foukarakis
A: 

You could check out my java applet if you want... Here is the source and here is the page with the applet. You need to scroll down a bit. The page is in swedish...

c0m4
A: 

Hi, having programmed life in pascal/delphi (windows only) before, I wanted to have it run in a webpage (multi platform). So I did it in Javascript and jquery. Have a look (at the code): http://www.ashware.nl/graylife Small draw-back: it doesn't run in Internet Explorer. Try Chrome for fastest results!!! The trick I found to speed things up, is not looking around every cell to count its neighbours, but keep an array with coordinates of living cells and 'warn' each cells 8 neighbours that they have a neighbour. Then convert the number of warnings for each cell to 'alive' or 'dead'. Massive speed gain.

A: 

Cymon's Games just featured a version of the game of life, but designed for 2 players. (Thank's for the mention, Sparkes. You prompted me to finally register with this site.) This game borrowed it's algorithm from an old BASIC game. The whole thing was done with a single array of ints. It goes through the array and every time it finds a "1" in the ones place adds 10 to the eight cells around it. Then it iterates through the array a second time comparing the values of each cel against a list of "survivors."

Of course for the multiplayer version the 100s, 1000s, and 10,000 places were thrown into the mix.

It's an elegant solution in it's own way.

Cymon
A: 

Conway's Game of Life in 1 line of APL:

http://www.catpad.net/michael/apl/

Dave
That's simultaneously beautiful and repulsive!
Dinah
+3  A: 

If you're interested in writing it in python, use Pygame. From the site:

Pygame is a set of Python modules designed for writing games. Pygame adds functionality on top of the excellent SDL library. This allows you to create fully featured games and multimedia programs in the python language. Pygame is highly portable and runs on nearly every platform and operating system. Pygame itself has been downloaded millions of times, and has had millions of visits to its website.

There's even a few books on the subject. I like Beginning Game Development with Python and Pygame: From Novice to Professional by Will McGugan. It's great for developing games in other languages as well.

Have fun!

Elizabeth Buckwalter
A: 

conwaylife.com is prety good app and conwaylife.com/wiki is good wiki with many things explained (including file formats for patterns).

I'm also making game of life like game and as first step I made simple widget that print alive cells. Second I've added mousePressEvent handling so I could click on widget to on/off particular cell. Third step was to add 4 buttons 'Start' 'Stop' 'Step' 'Clear' and to implement timing in my widget.

I thing those are basic requirements for game of life app.

Now I wont to implement support of online database of patterns conwaylife.com :D

And maybe in future I'll add support for different rules.

I'm writing with Python and PyQt also c++ and Qt. And any windows library have drawing routines that are good enough for this kind of game.

przemo_li
A: 

Why has no-one mentioned Life32?

http://psoup.math.wisc.edu/Life32.html

It's so much fun I still can't stop playing.

Sleepingrock
A: 

I once did a life implementation in 3D using OpenGL and C++. I did it by creating the world as a cube and played around with having points, spheres and cubes as life entities. I really liked using points with a high resolution world-cube. The end result looked like a cloud swirling, growing and changing. Very cool :-)

It wasn't much harder than the 2D version except I needed more RAM memory and some special handling with the life entities not crossing over the cubes edges. It also gave me some introduction to 3D and OpenGL.

Martin Wickman
+1  A: 

I managed to get a decent speedup in my C++ Life game by changing the way I counted the neighbours. I previously had a countNeighboursOf(x, y) function which worked a bit like this (where cells is an array of bools):

return
cells[x-1][y-1] +
cells[x][y-1] +
cells[x+1][y-1] +
cells[x-1][y] +
cells[x+1][y] +
cells[x-1][y+1] +
cells[x][y+1] +
cells[x+1][y+1];

The function was actually more complicated than that, because I had to use conditionals to take into account cells along the edge.
To speed it up, I created another array, each element containing eight bool pointers to point to the neighbours of each cell.

bool *neighbours[width][height][8];

At the beginning of the program, I looped though that array to set each pointer to a neighbour of a cell (wrapping around for the edge cells), then I changed my countNeighboursOf function to something like this:

return
*neighbours[x][y][0] +
*neighbours[x][y][1] +
*neighbours[x][y][2] +
*neighbours[x][y][3] +
*neighbours[x][y][4] +
*neighbours[x][y][5] +
*neighbours[x][y][6] +
*neighbours[x][y][7];

Now I don't have to perform any arithmetic on the x and y variables, nor do I need to be careful about wrapping at the edges of the array, because my pointer array did all that for me at the start.

geckojsc