views:

178

answers:

5

I vaguely remember reading about a programming exercise where objects are drawn on the screen. If an object has less than 2 neighbors, it dies because it is lonely, if it has more than 3 it dies because it is crowded. If the amount of neighbors is 2 or 3 then it will spawn children. the general idea was to see how many generations could last.

Anyway, does anyone remember the name of this exercise as well as the name of the algorithm to do it?

+1  A: 

It's the game of Life. I don't believe there was a specific name for the algorithm (unless it's the algorithm of Life which sounds like something you'd buy from those late-night shonky infomercials).

paxdiablo
+3  A: 

Sounds like Conway's Game of Life, as for algorithms etcetera, there are plenty of sources out there if you just search for the name.

Sciolist
+1  A: 

It is called the game of Life, and you can find out some more information about it here. I don't know the name of the algorithm to do it, however.

scwagner
+2  A: 

More generally these are called cellular automata. There are whole classes of interesting cellular automata including ones that can make swirling fractal-style geometry and others that can seem very intelligent. They've also been used to model real-life processes quite accurately too, see: http://en.wikipedia.org/wiki/Cellular_automaton

Ron Warholic
+1  A: 

Determining the neighbours in Conways Game of Life is trivial. The whole cellular automata is just a big 2D array, so you can look up adjacent items by incrementing/decrementing co-ordinates. Details depend on the implementation language, but you'd probably have some code similar to the following...

count := previous[x-1,y] + previous[x+1,y] + previous[x,y-1] + previous[x,y+1];
next [x,y] := 1 if ((count >= MIN) and (count <= MAX)) else 0;

One issue I've glossed over is bounds checking - making sure that only in-range co-ordinates are used. Cellular automata are often built for speed, so you probably wouldn't put checks in your inner loops - you'd have special case code for doing the corners and for looping along the edges.

This isn't what I'd call an algorithm to find an objects neighbour. One approach to the nearest neighbour problem is to construct an index based on a Voronoi diagram.

Steve314