John Conway's Game of Life
Spork Frog
Posts: 212
Hello all!
This is a simple implementation of John Conway's Game of Life, using a 20x20 grid, on a Hydra with VGA output. Suprisingly, I don't think this has been done yet with the Hydra.
Wrtitten completley in Spin as a self programming test over about 6 hours.
Questions? Comments? Criticisms? Concerns? I'd like to hear them!
Attatched is the source and a picture. Here's a video of it in action (on youtube.):
EDITED: See new version below
Enjoy!
Spork
NEW VERSION UPLOADED: See posts below
Post Edited (LarryHedgehog) : 8/7/2007 9:31:54 PM GMT
This is a simple implementation of John Conway's Game of Life, using a 20x20 grid, on a Hydra with VGA output. Suprisingly, I don't think this has been done yet with the Hydra.
Wrtitten completley in Spin as a self programming test over about 6 hours.
Questions? Comments? Criticisms? Concerns? I'd like to hear them!
Attatched is the source and a picture. Here's a video of it in action (on youtube.):
EDITED: See new version below
Enjoy!
Spork
NEW VERSION UPLOADED: See posts below
Post Edited (LarryHedgehog) : 8/7/2007 9:31:54 PM GMT
Comments
But do we call you Larry or Spork?
And I'm already working on the next version of this as well, which will hopefully go fullscreen instead of just 20x20 and with mouse control as well. We'll see though with the speed... I put some nasty "if" statements in there...
Use a lookup table. Each cell has 8 neighbors right? So, collect their values and use them as a lookup into an array that has the resulting cell state already pre-computed.
00000000 = 0
00001010 = 1
00010101 = 0
etc...
..or would the bit mashing take up more compute time than simple if - then statements?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Propeller Wiki: Share the coolness!
youtube.com/watch?v=b6i8dxWyWgw
TODO:
-Fix speed issues. As seen in the first part of the video, it's horiffically slow. I think I'll split the screen into 4 parts and have 4 cogs render each part, with a fifth cog controlling them all. I'll also see what I can do about the actual loop, to see what can be improved.
-Mouse action is a little jerky.
Enjoy!
Spork
EDITED: Attatchment removed. Scroll down for newest version.
Post Edited (Spork Frog) : 9/1/2007 1:32:45 AM GMT
Andre'
John Conway is an esteemd great grand father of this all..
One way to speed the processing up considerably (for this particular set of CA rules) is to take advantage of the fact that 1) The patterns which evolve from life are never heavily populated (i.e. there are typically more empty cells than full) and 2) The rule set in life depends only upon the number of neighbors and not their relative positions. Having made those two observations, you can create a "neighbor count" array of 20 x 20 bytes (i.e. one for cell). For each pass you zero the neighbor count array, then search the cell array for populated cells. Most will be empty, and you can move on doing no math at all. When you do find a cell, increment the neighbor count for all surrounding cells. When done, make another pass and apply the spawn/survive/die logic to each cell based on its neighbor count. You'll end up having to access far fewer than 3200 (8x20x20) cells and should get a significant speed improvement. For very sparse screens you'll be down around 400 (cell check pass) + 200(incrementing adjacent cells on 25populated cells) = 600 or so cell accesses instead of 3200, which is about a 6x boost in execution speed.
Well, actually theres also the pass to zero the array (400) and the pass to check the array when done (400), which puts you at 1400 instead of 3200 so perhaps its a 2x increase in speed, but you can do some things to speed that up as well. For one thing you can use nibbles instead of bytes (i.e. store two counts per byte) which will halve the size of your neighbor count array, and you can use a block fill to zero it which will be very fast.
The propeller can only do one-dimensional arrays. But, in this scenario, I needed a 2-dimensional array. So I was mapping one virtually onto the array using some quick math: array[noparse][[/noparse]x + (y * 20)]. While this works, because the propeller has no built-in multiply instruction, it has to add. A lot. So, instead, I decided on this: So you have a location array[noparse][[/noparse]i ]. To the left of it is array[noparse][[/noparse]i-1], right is array[noparse][[/noparse]i+1], below it is array[noparse][[/noparse]i+20]... and using only addition and subtraction there instead. That alone boosted performance about 3x.
But the more I think of it, the more I realize that neighbor count array is a good idea. I'll try that.
It helps that in Life you are only ever looking at adjacent cells, so the offsets can be precomputed as you stated and you can avoid the multiplication altogether. In cases where you need rapid random access to to an array a useful trick is to dimension your array so the horizontal width is a power of two, and then use bit shifts instead of multiplies to calculated the offset. For instance, if you needed to randomly access a 20x20 array you would allocate space for a 32 wide (X) by 20 tall (Y) array and then the offset of any location can be quickly calculated by OFFSET = X << 5 + Y (where << is a left bit shift (in C; I Can't remember if the SPIN syntax for that operation is the same)). X << 5 is equivalent to X * 32 but it executes extremely fast and can be done by a single processor-native instruction.
By the way, I don't know if you saw v0.2, but the grid is now 98x46.
I'm liking this. Actually forcing myself to learn efficient coding methods, versus PC programming where you can really write code (almost) as inefficiently as you want to and get away with it because of how fast the CPU is.
So anyway, here's another trick; For the cost of TWO shifts and TWO adds you could (again, if you wanted general purpose random access to your array) drop you horizontal width by 2 and then decompose your 98-2=96 into two shifts and three adds (Offset = X << 6 + X << 4 + 5 + Y). X<<6 is equivalent to X * 64, and X<<5 is equivalent to X*32, so you get X*64 + X*32 = X * (64+32) = X * 96.
If you don't want give up 2 columns, then reinterpret your array as being rotated 90 degrees, and imagine it as a 46x98 array (but still displayed as 98x46), add two to the new "width" to get 48 (so you're wasting two columns, but that's not too much overhead), then you can play the same trick using Y<<5 + Y<<4 = Y*32+Y*16 = Y*48.
I've refined the mouse movement so it's not quite as "jerky" as it was before. Bounds inside the mouse driver, such as the new version from Parallax, would have been nice, but it's still feasible without them.
EDIT: I've refined the code as far as I wanted to. Not seeing quite as much speed increase as I anticipated. ASM port soon
Post Edited (Spork Frog) : 8/30/2007 1:28:41 AM GMT
Started ASM development today. However, coding on this project will most likely be reduced because of school starting again soon.
Post Edited (Spork Frog) : 9/1/2007 1:31:58 AM GMT
I just got my Hydra hooked up to a VGA monitor and got it running...
Pretty cool to see all the cells wandering around...
My Hydra has been in a box for a while, got a new house and didn't unpack the Hydra until a couple of weeks ago.
I was a little bit nervous for a while when I hooked it up to my TV and nothing, just a blank screen...
Luckily it was the TV that broke during the move and not the Hydra.
So I managed to get a left over VGA monitor from my mother in law and I'm finally back to programming...
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Living on the planet Earth might be expensive but it includes a free trip around the sun every year...
Experience level:
[noparse][[/noparse] ] Let's connect the motor to pin 1, it's a 6V motor so it should be fine.
[noparse][[/noparse] ] OK, I got my resistors hooked up with the LEDs.
[noparse][[/noparse]X] I got the Motor hooked up with the H-bridge and the 555 is supplying the PWM.
[noparse][[/noparse] ] Now, if I can only program the BOE-BOT to interface with he Flux Capacitor.
[noparse][[/noparse] ] I dream in SX28 assembler...
/Bamse