GMLscripts.com

Discuss and collaborate on GML scripts
Invert

You are not logged in.

#1 2011-04-15 23:37:45

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

CHALLENGE: Conway's Game of Life

Background Information

The subject is John Conway's Game of Life. Life is a sort of simulation. Technically, it is called a Cellular Automaton. Its form is a grid of individual cells all operating according to very simple rules. Each cell exists in one of two states, alive or dead. Each "generation" it may change or keep its current state according to its surroundings. The rules are (1) if a cell is dead, it will be alive the next generation if it is surrounded by exactly 3 living neighbors, and (2) if a cell is alive, it will survive to the next generation if it is surrounded by exactly 2 or 3 living neighbors. Each cell's neighbors are the eight cells that are immediately adjacent to it (called a Moore neighborhood). Finally, all cells must operate in lock-step, changing their states at exactly the same time. Despite the simplicity of the rules, the automaton is capable of some rather complex behavior and can seem almost alive at times (hence the name).

gyuUjq9.gif
This is the simplest possible oscillator. It is called a "Blinker". This is a good one to try on paper to help understand the CA rules of Life.

9UXis2S.gif
The "Glider" is the simplest "spaceship", an oscillating pattern that shifts itself through space. It is often seen in the wild and is another good exercise to try on paper.

X4jSVte.png
A simple "Methuselah" configuration called "the F-pentomino" that gives rise a long lived colony. This kind of pattern is also called an "acorn" because it starts small but grows quite large.

I highly recommend checking out the gob-smackingly amazing Golly if you want to tinker with Cellular Automata. There are many types of CA, the Game of Life is merely one of the first and is certainly best known. "Wireworld" is a really intriguing four-state CA that is Turing Complete, meaning it can be used as the basis for any computing device. Golly features a "circuit" that calculates prime numbers and includes seven-segment LED-style displays. It's also worth noting Will Wright's SimCity is simulated at its core using several layers of cellular automation, include the Life rule set.


The Challenge

The challenge will be to demonstrate a functioning — once mythical — "Glider Gun" running as fast as possible on a 40x40 grid. Bill Gosper invented the first one and won $50 from John Conway for his creation. It is often called a "Gosper Gun" and this is what it looks like in operation.
heALR3m.gif

I think this is an interesting challenge because it affords many opportunities for optimization. Cellular Automata can be brutally slow with Game Maker's interpreter. Naive solutions for a 40x40 grid run around 1 FPS on my machine. Better solutions are dozens of times faster. Entrants are encouraged to submit any sort of interesting tricks they've used to solve this problem, even if they aren't the fastest methods they have come up with.

Here is the initial configuration image (below left) to get you started. Your entry should run from this starting state. Black pixels are dead cells and white pixels are living cells.

Yu67TIE.pngLnpDaad.png
(enlarged to show detail)

You may represent or encode the data within your demonstration in any form you wish. You may use any mechanism to run the CA as long as it uses built-in Game Maker functionality (ie. No DLLs). The display can take any form you wish, but it must be visible and clearly discernible on screen while the CA is running "live". Speed will be measured in generations per second. For simplicity of judging, please perform one full generation per frame, and display actual FPS in some fashion. If you wish, you are free to post executable-only versions before revealing your technique at the end of the challenge period. This won't be much of a learning experience if we can't see your code, so editable entries must be submitted before midnight May 1st, GMT.

Beyond the scope of the competition, feel free to also demonstrate other configurations, alternate CA rule sets, universal CA engines, DLL assisted demos, or anything else you come up with during this challenge that you find interesting.


Optional Challenge

I'll be sitting out the main competition because I've already constructed what I think is a rather unfair ringer (which will be posted). If this doesn't phase you, I offer a secondary challenge that is far more grand. Run this 400x400 pattern at a visibly detectable speed. wink

CN940Za.png
(credit to David Dauthier for coming up with this amazing oscillator)


Prizes

Like all GMLscripts.com challenges, prizes include bragging rights, expanded horizons, and camaraderie.

Last edited by xot (2011-04-17 14:09:00)


Abusing forum power since 1986.

Offline

#2 2011-04-17 12:07:50

blopit
Member
Registered: 2009-05-19
Posts: 7

Re: CHALLENGE: Conway's Game of Life

http://www.megaupload.com/?d=7586U982
Runs at around 2500 fps on my craptop. 3500 at best. 80 x 80 grid because 40 x 40 was too small for me. Goes more then 4x faster in 40x40 though.
I assure you that I'm not multiplying the fps shown, the fps is legit. Probably uses the same method as xot's "rather unfair ringer".
I put some other patterns in the zip file for your enjoyment. Snail is one of my favourites.

If you want to see 40x40 version go here http://www.megaupload.com/?d=04JQN3HS doesn't use the fps booster method of the previous. But only the gosper gun file is small enough to work in it.

Last edited by blopit (2011-04-17 12:31:41)

Offline

#3 2011-04-17 13:58:08

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: CHALLENGE: Conway's Game of Life

Wow, an entry already! Cool .... but .... hmmm -- I'm a little puzzled by this entry, in part because you don't supply an editable version. That's fine, although it is expected before the end of the competition period.

If I understand this correctly, the first number displayed is the frame rate, which is around 2800 fps on my machine. The second number appears to be the generation number which increases at a considerable slower rate, around 15 generations per second. This seems to be consistent with the observed changes in the pattern as the engine runs. Am I correctly understanding what I'm seeing?

Ironically, your non-"fps booster" version runs considerably faster, an apparent (and respectable) 75 fps on my machine.

I think I need to emend the rules to say that one full generation needs be performed each frame.


Abusing forum power since 1986.

Offline

#4 2011-04-17 15:11:16

blopit
Member
Registered: 2009-05-19
Posts: 7

Re: CHALLENGE: Conway's Game of Life

Actually the "fps booster" version only runs slower because it uses a 80x80 grid instead of 40x40. But yea I thought it was cheating. Thats why I posted the other version. Will post gmk later.

Last edited by blopit (2011-04-17 15:11:36)

Offline

#5 2011-04-17 16:27:47

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: CHALLENGE: Conway's Game of Life

Rob Fearon of Retro Remakes just retweeted this really neat application of cellular automation. Otomata is described as a generative sequencer that uses CA rules to produce sound events. It spits out some pretty passable music with simple input.

Play with it yourself here:
http://www.earslap.com/projectslab/otomata/


This isn't the first application of cellular automation I've seen for music generation. Stephen Wolfram, best know for Mathematica and Wolfram|Alpha, is also well known for his extensive, cutting-edge CA research. In fact he wrote an absolutely massive book devoted to the subject, A New Kind of Science. His WolframTones program is a pretty sophisticated automatic composition tool that can mimic specific styles of music.

http://tones.wolfram.com/


Abusing forum power since 1986.

Offline

#6 2011-04-17 19:59:08

creativebunch
Member
Registered: 2011-04-17
Posts: 3

Re: CHALLENGE: Conway's Game of Life

This peeked my interest, I've always been interested in simulating living things (or similar). I gave it a go but my method might be pretty inefficient. I make two grids, I copy the first one over to the second and loop through it checking the neighbours, then I set the first grid based on that and copy the first grid over to the second so it can start again.

Here is the exe: http://www.mediafire.com/?gnx73bo0j3bcja8 or http://www.host-a.net/u/grungegames/Cel … omaton.exe
Controls show up on game start.

EDIT: To start and stop the simulation press enter (can't believe I forgot that one).

Last edited by creativebunch (2011-04-18 05:55:24)

Offline

#7 2011-04-18 00:22:52

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: CHALLENGE: Conway's Game of Life

There appears to be some sort of trouble with your upload. MediaFire gives me a 403 Forbidden error.


Abusing forum power since 1986.

Offline

#8 2011-04-18 05:40:07

creativebunch
Member
Registered: 2011-04-17
Posts: 3

Re: CHALLENGE: Conway's Game of Life

Hmm that's weird, it works fine for me. I'll upload it to another site and edit my previous post with the link.

Offline

#9 2011-04-19 05:19:51

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: CHALLENGE: Conway's Game of Life

The new link works a treat, thanks. I'm guessing the room speed has been set to 30. I'm curious to see how fast this entry can actually run.


Abusing forum power since 1986.

Offline

#10 2011-04-20 01:39:45

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: CHALLENGE: Conway's Game of Life

Are there data files that specify your test patterns I don't know how to build that machine

Offline

#11 2011-04-20 03:13:34

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: CHALLENGE: Conway's Game of Life

This 40x40 image represents the initial configuration.
Yu67TIE.png

If your Life engine is working correctly, and if the starting state is populated with the live (white) and dead (black) cells shown, the Gosper Gun should function like the animation.

The image was created with this code, if that helps any:

/// Gosper Gun
{
    gospergun  = "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000010000000000000";
    gospergun += "0000000000000000000000001010000000000000";
    gospergun += "0000000000000011000000110000000000001100";
    gospergun += "0000000000000100010000110000000000001100";
    gospergun += "0011000000001000001000110000000000000000";
    gospergun += "0011000000001000101100001010000000000000";
    gospergun += "0000000000001000001000000010000000000000";
    gospergun += "0000000000000100010000000000000000000000";
    gospergun += "0000000000000011000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    gospergun += "0000000000000000000000000000000000000000";
    
    draw_clear(c_black);
    draw_set_color(c_white);
    w = 40;
    h = 40;
    for (i=0; i<w; i+=1)
    {
        for (j=0; j<h; j+=1)
        {
            stateA[i,j] = real(string_char_at(gospergun,w*j+i+1));
            if (stateA[i,j]) draw_point(i,j);
        }
    }
    screen_save_part("gospher-gun-initial.png",0,0,w,h);
}

Abusing forum power since 1986.

Offline

#12 2011-04-20 22:17:34

blopit
Member
Registered: 2009-05-19
Posts: 7

Re: CHALLENGE: Conway's Game of Life

ngen=ds_grid_create(W,H);
pgen=ds_grid_create(W,H);

gen=0

dslist=ds_list_create()

f=file_text_open_read(get_open_filename('life file|*.cells;*.txt',""))
iy=0
do{
str=file_text_read_string(f)
ix=0
repeat(string_length(str)){
if string_copy(str,ix,1)=="O"{ds_grid_set(ngen,ix+1,iy+1,1)}
ix+=1}
file_text_readln(f)
iy+=1
}until file_text_eof(f)
file_text_close(f)

If it helps, here's the pattern loader I made that loads patterns from files into ds_grids,
file is here: http://www.megaupload.com/?d=7586U982 along with my slow example. Or you can just make a .txt file of this:

..................................................
..........................O.......................
........................O.O.......................
..............OO......OO............OO............
.............O...O....OO............OO............
..OO........O.....O...OO..........................
..OO........O...O.OO....O.O.......................
............O.....O.......O.......................
.............O...O................................
..............OO..................................
..................................................

I will post my entire .gmk later when its faster.

Last edited by blopit (2011-04-20 22:22:37)

Offline

#13 2011-04-21 01:09:53

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: CHALLENGE: Conway's Game of Life

Here's mine. I'm a little upset I cant figure out why my gridded version does not work. It's the exact same code as the one that works except I remap the check to a grid...

Short story, instead of looping through a grid, each cell is an instance. 3 of the life conditions can be resolved checking neighbours with collision point. The last check, "birth" is only done on cells that are empty and have neighbors... It's actually the cell that is alive the will check if the empty neighbour ce3ll can be reborn

8 collision checks/instances + 8 collision checks for neighbour cells that are empty each iteration

So empty cells that have nothing living around them are not checked.

The larger the number of instances, the slower the fps.

http://www.host-a.net/u/icuurd12b42/Life.zip

You can try to check why the gridded version does not work. I lost too much hair on this already. My debug draw shows the get grid data function does work but the cells seem to get wrong result.

[edit]
Also, if you look at the 2 permanent blockers in the setup, you will see my method makes the same garbage when the group hits, but the garbage trickles down where the video it trickles up, but the patern look the same (but inverted)

Last edited by icuurd12b42 (2011-04-21 01:16:26)

Offline

#14 2011-04-22 18:39:02

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: CHALLENGE: Conway's Game of Life

Very interesting instance-based approach. Quite similar to what a very famous Game Maker user did with his Life demo. Instances can be intolerably slow, but if they are only used for living cells, they can neatly minimize the amount of calculations required. Since most Life configurations quickly reduce to very sparse populations, it can provide some serious gains over methods that iterate over every element of a grid or array.

I also like your use of color to show the age of the cells.

I haven't yet found what is wrong with the grid version, but I feel compelled to point out that anyone using grids for this should take a good look at the other grid functions for any that might be applicable here. Could be good for a small boost, unless you are extra clever, in which case it is good for a large boost.


Also, if you look at the 2 permanent blockers in the setup, you will see my method makes the same garbage when the group hits, but the garbage trickles down where the video it trickles up, but the patern look the same (but inverted)

It's not your method. It's actually caused by a non-critical difference in the construction of the gun. You'll notice that in the initial configuration I provided the blocks at the ends are each offset vertically by a pixel compared to the animated illustration. Both configurations are from the linked Wikipedia article, but I didn't notice the difference until you mentioned it.


Abusing forum power since 1986.

Offline

#15 2011-04-24 00:14:17

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: CHALLENGE: Conway's Game of Life

We're now entering the final week. I hope we can get some more participants in before the deadline.

I'm posting a tiny taste of my non-entry. Maybe someone can divine the significance of the image.

8dAeL5a.png

If you perceive what's being shown, it's a big clue as to what I'm doing. wink


Abusing forum power since 1986.

Offline

#16 2011-04-24 02:18:19

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: CHALLENGE: Conway's Game of Life

I'm thinking the grid check will boost the performance of my entry. However, I still cant figure out wtf is going one. It's funny, I make the first version in 30 minutes, takes me 10 minutes to convert it the a grid check.... then blammo. Can't figure it out.


My bet on your method... grid addition or multiplication... with a biased decision Of course you have been very sneaky with grids in the past so that what my suspicion is based on... + your other post

My method can also be achieved with a grid/array and a list/array for minimizing the checks. A linked system. But instances provided a lazy way to achieve this.

Last edited by icuurd12b42 (2011-04-24 02:21:31)

Offline

#17 2011-04-24 02:40:03

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: CHALLENGE: Conway's Game of Life

very sneaky with grids

I will be showing something like that, but that would merely be "extra clever", not "rather unfair".

It is not what is being shown above. ph34r


Abusing forum power since 1986.

Offline

#18 2011-04-24 06:08:48

creativebunch
Member
Registered: 2011-04-17
Posts: 3

Re: CHALLENGE: Conway's Game of Life

Gah, forgot about this hmmm

Well here is my gmk file, complete with messy goodness (GM8 if that matters).

It actually has two objects, the second one is a slightly different variation which I thought would run faster, it uses repeat (which I've been told is faster than while) and everything is done in the draw event, however it runs 50% slower than the previous one which loops both in the step and draw, I have absolutely no idea why it runs slower it would be good if someone does.

I would think the only to get 400*400 to run in GM is to avoid loops somehow, I've only managed to get 4 fps but I'm not too smart, I would love to see if someone managed to accomplish it.

Last edited by creativebunch (2011-04-24 06:09:29)

Offline

#19 2011-04-24 13:45:05

blopit
Member
Registered: 2009-05-19
Posts: 7

Re: CHALLENGE: Conway's Game of Life

Here's my gmk: http://www.megaupload.com/?d=1GFM7AYJ. I can't wrap my mind around xot's method >.> looks...confusing.

For 'FPS Booster' which really doesn't do much, just add:

CREATE:
t=0
tt=200
set_automatic_draw(0)

STEP:
t+=1
if t>tt{t=0; screen_redraw()}else{t+=1}

Offline

#20 2011-04-24 20:41:17

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: CHALLENGE: Conway's Game of Life

xot wrote:

very sneaky with grids

I will be showing something like that, but that would merely be "extra clever", not "rather unfair".

It is not what is being shown above. ph34r

Oh oh oh, I could blend in an answer.... But I wont. I just think an answer is surfacing in my head.

Last edited by icuurd12b42 (2011-04-24 20:51:13)

Offline

Board footer

Powered by FluxBB