Conway's Life, which extra features would be nice?

Hi.

I am in the final progress of making a Conway's Life game with four 8x8 LED matrices. Just need to put an independent Arduino chip onto it and add the features I want.

Here is a picture of how it looks:

As you can see I have space for additional stuff on the Vero board.

Currently it simply runs until it detects a stagnation, then randomizes the display, and starts over again.

I intend to put this project inside a box and hang it up on a wall.

So I would like to know if someone can think of any additional features that would be nice to have.

Some features that I have thought of already and will most likely be added:

  1. Have a Light dependent resistor control the brightness of the screen.
  2. Keep a high score of how many generations have been made since it was plugged in (or keep the high score in memory).
  3. A button to press so you can see the high score without wiping out the current running game.
  4. Reset button, randomize display.
  5. Buttons to control the speed.
  6. I also thought about making it connect to my WiFi so I would be able to control it using any computer connected to my router. Not sure if that is possible though. It would need to host a web-service and that will make it not able to do the constant calculations required to keep the game going. Maybe using two Arduinos can be a solution.

If someone can think of something else then I would appreciate if you would post it here :slight_smile:

Regards..

simmisj:
Currently it simply runs until it detects a stagnation, then randomizes the display, and starts over again.

How do you define "stagnation"?

In the game, different type of "gliders" and "oscillators" may appear, that either change position and/or the number of living cells from step to step.

So if you should end up with one glider that runs across the field, or with an oscillator changing the number of living cells during its cycle, how do you detect "stagnation" then?

jurs:
How do you define "stagnation"?

I define stagnation if a sequence of patterns happen over and over again. For example if we simply use numbers from 0 to 9 in sequence to represent the array patterns:
if 2,6,1,4,3,1,4,3,1,4,3 happens then this is stagnation by the time we hit the second 3 (the last 1,4, and 3 will not be computed). And with my code below it would return 3 in this case.
Another example: 1,7,4,8,9,8,9,8,9 stagnation with a return of 2 by the time it hit the second 9 (the last 8, and 9 will not be computed.

I detect stagnation by keeping a snapshot of generations into the past. Currently I have 20 snapshots into the past.
Then every generation I run an algorithm that checks for stagnation.
In pseudo code it is like this:

int sizeofgenerations
an array of generations[sizeofgenerations]

if generations[sizeofgenerations-1]  to generations[sizeofgenerations-2] are same
    return 1
else if generations[sizeofgenerations-1]  to generations[sizeofgenerations-3] are same
AND  generations[sizeofgenerations-2]  to generations[sizeofgenerations-4] are same
    return 2
else if generations[sizeofgenerations-1]  to generations[sizeofgenerations-4] are same
AND  generations[sizeofgenerations-2]  to generations[sizeofgenerations-5] are same
AND  generations[sizeofgenerations-3]  to generations[sizeofgenerations-6] are same
    return 3

.....

else
   return 0

I also shift the generations in the array that holds them to make room for the next generations and erase the oldest generation.

This continues like that until you are comfortable with the number of stagnations you want to check for. In my code I go up to 9.

Then I just check for the integer it returns. If it returns 0 then some change happened, any other number means it is stagnated.

If a stagnation happens that involves more than 9 repetitive generations then I will NOT detect it. That is the limit of this method. But with only 16x16 array I think that is alright. If someone can prove mathematically how many repetitions are possible on a X by X array then that would be great :smiley: I think I might ask that question on Math Stackoverflow.

I hope my explanation is clear. If not I could try to explain it further or even just provide the code.

simmisj:
This continues like that until you are comfortable with the number of stagnations you want to check for. In my code I go up to 9.

I don't quite understand your description.

But if you want to check if 9 generations is enough, test with the easiest form of a glider:

 X
  X
XXX

Then let it run across your field.
Will your code detect stagnation while just one glider is crossing the playfield forever and ever?

My implementation has borders. It will not go off at the bottom and appear at the top for example.

simmisj:
My implementation has borders. It will not go off at the bottom and appear at the top for example.

So your implementation is not Conways Game of Life, but some modification using borders?

OK, in that case gliders will run into borders and die instead of running forever.

And in that case, playing time until stagnation will be relatively short.

jurs:
So your implementation is not Conways Game of Life, but some modification using borders?

Conway's Game of Life is actually a two dimensional infinite space and thus what you speak of would not happen in the original version.
Instead of running into infinity I use borders yes. Glad you mentioned this. This will go on the list of possible features. Both having infinite space and looping around the borders :slight_smile:

jurs:
And in that case, playing time until stagnation will be relatively short.

In my experience anywhere from 20ish to 500ish generations. Averaging about 100ish generations.
I wonder how much it will improve if I implement the lopping over borders...

I have never heard of Conway's game of life before, but it sounds interesting.

Can you share your code?

HazardsMind:
I have never heard of Conway's game of life before, but it sounds interesting.

Seriously? You must be very young ;D

25

You might want the option for a larger grid, with pan options on the display.

(I don't think you have enough room for a glider gun, for example)

HazardsMind:
Can you share your code?

If you have not heard of Conway's Game of Life then I can not imagine why you would want the code. But anyways..
I don't want to share it just yet since I have yet to modify it in extreme ways. But if you are implementing the game in some way and have some question about a specific part then I would be more than happy to help you.

KeithRB:
You might want the option for a larger grid, with pan options on the display.

(I don't think you have enough room for a glider gun, for example)

That is a good idea. Maybe have four directional buttons that move the visible screen around. Thanks for that suggestion.

jurs:
But if you want to check if 9 generations is enough, test with the easiest form of a glider:

 X

X
XXX



Then let it run across your field.
Will your code detect stagnation while just one glider is crossing the playfield forever and ever?

I just implemented the joining of the edges together and I see that detecting the spaceships (glider, etc) is going to be a complicated problem :smiley:

If I want to use my current method I will run out of memory :confused:
I need to figure out a more efficient way to detect stagnation.

simmisj:
If I want to use my current method I will run out of memory :confused:
I need to figure out a more efficient way to detect stagnation.

Could you generate a 16/8 bit CRC for each generation then you would only need to store/compare 2/1 bytes per generation looking for matching patterns.

I did a version of this for the Apple II, so I say: good work!

Riva:
Could you generate a 16/8 bit CRC for each generation...

Good idea. Something from Bob Jenkins may work better...
https://www.google.com/search?q=bob+jenkins+hash

Riva:
Could you generate a 16/8 bit CRC for each generation then you would only need to store/compare 2/1 bytes per generation looking for matching patterns.

I thought about that but I am not sure how to implement that in Arduino.

From the wiki page about Bob Jenkins hash:

uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

I have an array of integers so would I sum the numbers in the array and store the result?
Also, how would this be implemented in Arduino?

simmisj:
I have an array of integers so would I sum the numbers in the array and store the result?

Yes, you would use jenkins_one_at_a_time_hash function to calculate a hash value for your array.

Also, how would this be implemented in Arduino?

Uh, well, for the first parameter you would use a typecast to force the compiler to treat your array as char* and for second parameter you would pass the size of your array.

Alright thanks.
This thread is going a bit off topic. I have made a new post regarding the hashing part of my project. If someone is interested then it is here: Hashing function correctness and uniqueness.

For those that are interested, and did not get replies from previously asked questions, wikipedia (used to) has a good article on Conways. http://en.wikipedia.org/wiki/Conway's_Game_of_Life