13 Replies - 20504 Views - Last Post: 04 January 2012 - 09:17 PM

#1 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2239
  • View blog
  • Posts: 9,409
  • Joined: 29-May 08

Challenge: Conway Game of Life

Post icon  Posted 01 January 2012 - 10:10 PM

Challenge: Conway's Game of Life

Let's start off the life of the new Challenges forum, with you implement life itself (well at least Conway's version of it).

Challenge
  • Create UI-agnostic class that is capable of simulating Conway's Game of Life.
  • Create a UI that displays the current state of the game.



Life Rules
  • Any cell with fewer than 2 neighbors dies (of loneliness)
  • Any cell with 2 or 3 neighbors, survives into the next generation.
  • Any cell with more than 3 neighbor dies (of over crowding)
  • Any dead cell with exactly three neighbors, becomes alive (as if by reproduction)


The World
The world on which these cells live is a Torus.
So the top and a bottom edges are connected and the left and right edges are connected.

Requirements

- Publicly you can only create instance of them via one of, the following two factory methods.
CreateNew
Dim cwi = ConwayGame.CreateNew( Width:= 320, Height:= 240 )

CreateRandom
Dim cwi = ConwayGame.CreateNew( Width:= 320, Height:= 240, AliveCells:= 25000 )

Must be capable of generating at bitmap of the current state of the Conway Game, via the following shared function.
Dim bmp = ConwayGame.ToBitmap( ThisInstanceOfConwayGame )


The instance must have a function that returns to number of Alive Cells.
eg.
Dim acc = ThisInstanceOfConwayGame.AliveCellCount()





Entrants
  • Frameworks required.
  • vb.net submissions are preferred.
  • SourceCode must be in spoilered code tags.
    Spoiler

    If you don't want to reveal your code, then don't submit a submission.
  • If you like you can include a Zip-File of the project / executable.

This post has been edited by AdamSpeight2008: 01 January 2012 - 11:36 PM


Is This A Good Question/Topic? 3
  • +

Replies To: Challenge: Conway Game of Life

#2 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1937
  • View blog
  • Posts: 4,022
  • Joined: 11-December 07

Re: Challenge: Conway Game of Life

Posted 02 January 2012 - 07:45 AM

The first time I saw Conway's game of life was on the cassette supplied with the 48K Spectrum. :) I'll have a submission soon.

I like your challenges. Keep up the good work!

One question. Do cells have eight neighbours or four?
Was This Post Helpful? 0
  • +
  • -

#3 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2239
  • View blog
  • Posts: 9,409
  • Joined: 29-May 08

Re: Challenge: Conway Game of Life

Posted 02 January 2012 - 07:53 AM

Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent.
Was This Post Helpful? 1
  • +
  • -

#4 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1937
  • View blog
  • Posts: 4,022
  • Joined: 11-December 07

Re: Challenge: Conway Game of Life

Posted 02 January 2012 - 07:12 PM

Here is my first attempt. I'm going to have a shot at refactoring it to be more OO. I think that would make a few optimisations quite easy:

Spoiler


And the GUI:

Spoiler

Was This Post Helpful? 1
  • +
  • -

#5 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1937
  • View blog
  • Posts: 4,022
  • Joined: 11-December 07

Re: Challenge: Conway Game of Life

Posted 03 January 2012 - 09:48 AM

Tried my OO version. It failed miserably.

My thinking was that I could have a Cell class. Then instead of scanning the entire torus, I could work off a set of alive cells, looking at them to see if they died and their neighbours to see if they came to life. Turns out that too much of the board is in use for this to offset all those method calls, and especially the initial object creation.
Was This Post Helpful? 0
  • +
  • -

#6 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2239
  • View blog
  • Posts: 9,409
  • Joined: 29-May 08

Re: Challenge: Conway Game of Life

Posted 03 January 2012 - 01:15 PM

cfoley you may want to re-examine to requirements, factory-method creating of instances.
Any how. Nice to see somebody taking a interest.

What rate you getting? Generations Drawn/Sec ?


I may need to sit and examine this bit, just to see if the obeys the "life rules", plus a return type would help.
Private Function isNextGenerationAlive(ByVal x, ByVal y)
  Dim neighbours = aliveNeighbours(x, y)
  Return neighbours = 3 Or (cells(x, y) And neighbours = 2)
End Function



P.S. You don't know anyone with a lots of CPU cores going spare. As mine is maxing both cores on my desktop, I may have to awoken the beast (old rack server).

This post has been edited by AdamSpeight2008: 03 January 2012 - 01:17 PM

Was This Post Helpful? 0
  • +
  • -

#7 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1937
  • View blog
  • Posts: 4,022
  • Joined: 11-December 07

Re: Challenge: Conway Game of Life

Posted 03 January 2012 - 06:01 PM

Oops my mistake. I've put in the factory methods. Here is how I got to my life rules logic.


Spoiler


And here are my amended classes:

Spoiler


As far as performance goes, the refresh rate is controlled by a GUI timer. If I set the delay to 1 ms, and the image size to 320x240 and 25000 live cells, I get 836 frames in 1 minute (timed manually with a stopwatch). That's Just under 14 frames per second. However, the first couple of frames are much slower than the rest due to the number of cells dying (and therefore pixel editing in the image). CPU is at 25% with no multithreading. i.e. one core is maxed out.

Spoiler

This post has been edited by cfoley: 03 January 2012 - 06:03 PM

Was This Post Helpful? 1
  • +
  • -

#8 maffelu  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 40
  • View blog
  • Posts: 190
  • Joined: 21-August 08

Re: Challenge: Conway Game of Life

Posted 03 January 2012 - 11:54 PM

Was this only in VB.NET? Because I made one using jQuery, it's easier having it on the web :whistling:

http://demo.morkalork.com/game/CGoL/
Was This Post Helpful? 0
  • +
  • -

#9 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2239
  • View blog
  • Posts: 9,409
  • Joined: 29-May 08

Re: Challenge: Conway Game of Life

Posted 04 January 2012 - 04:16 AM

maffelu: vb.net submissions are preferred.
Allows other languages but since this in vb.net I would like it if they were predominantly vb.net.
Was This Post Helpful? 0
  • +
  • -

#10 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2239
  • View blog
  • Posts: 9,409
  • Joined: 29-May 08

Re: Challenge: Conway Game of Life

Posted 04 January 2012 - 06:30 AM

You can see me entry posted in my blog post. (As the code is a bit long)

On a 320 x 240 world with 25000 seeds, it does (on my machine) ~40 generations a second.

Note: There no point setting the timer below 25ms as windows and .net can time accurately.

This post has been edited by AdamSpeight2008: 04 January 2012 - 06:35 AM

Was This Post Helpful? 0
  • +
  • -

#11 piman314  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 32
  • View blog
  • Posts: 169
  • Joined: 07-August 09

Re: Challenge: Conway Game of Life

Posted 04 January 2012 - 10:27 AM

Here's my entry. Runs on Client Profile 4.0.
Runs at ~50 generations/second on my machine once it gets running.
It is a bit simplistic, but it works. The title text is "gen/sec alivecount".

ConwayGame
Spoiler


GUI
Spoiler

This post has been edited by piman314: 04 January 2012 - 10:47 AM

Was This Post Helpful? 0
  • +
  • -

#12 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2239
  • View blog
  • Posts: 9,409
  • Joined: 29-May 08

Re: Challenge: Conway Game of Life

Posted 04 January 2012 - 03:15 PM

Just look at your code, not tried running it yet.
piman314: First think I spotted, in your code.

Quote

frmView.CheckForIllegalCrossThreadCalls = False

Is asking for trouble, and your ignoring the issue.

The I spotted that your incrementing a shared variable on different tasks, non atomically. Increasing the odds of it producing the wrong value. When you count living cells.

Thirdly your way of calculating the average time seems wrong to me. Until at least 30 generation have to occur before you can average over 30. So first 29 generation have incorrect value for the rate,

This post has been edited by AdamSpeight2008: 04 January 2012 - 03:17 PM

Was This Post Helpful? 0
  • +
  • -

#13 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2239
  • View blog
  • Posts: 9,409
  • Joined: 29-May 08

Re: Challenge: Conway Game of Life

Posted 04 January 2012 - 04:09 PM

piman314: I've run it an it is using the wrong rules.
Was This Post Helpful? 0
  • +
  • -

#14 piman314  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 32
  • View blog
  • Posts: 169
  • Joined: 07-August 09

Re: Challenge: Conway Game of Life

Posted 04 January 2012 - 09:17 PM

I was hoping you wouldn't call me out on my bad practice :P

-I fixed the form thread issues by making the window text and image setting invoked.
-The numerator in the generations/sec counter now counts up to 30 instead of having an inaccurate value for the first 29 generations.
-Fixed the alive counter by using Interlocked.Increment and switched it to a for loop inside a Parallel.For (which seems to be faster than nesting Parallel.For on my machine)
-Fixed the rule error in AliveNext

I think that's everything.

ConwayGame
Spoiler


GUI
Spoiler

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1