Game of Life demo
Moderator: Mask of Destiny
-
- Very interested
- Posts: 50
- Joined: Tue Dec 24, 2013 1:00 am
Game of Life demo
So, I made a game of life simulation with GCC and the SGDK.
(thanks stef!)
Nothing too fancy, but it works on real hardware
https://dl.dropboxusercontent.com/u/358 ... yte-v1.bin
Controls
- Start - toggle simulation
- D-pad - when paused, move cursor
- A - when paused, toggle a cell
- B - when paused, randomize grid
- C - when paused, clear grid
I have a few ideas for improvement and optimization that I will hopefully be able to roll out into a new version pretty soon.
(thanks stef!)
Nothing too fancy, but it works on real hardware
https://dl.dropboxusercontent.com/u/358 ... yte-v1.bin
Controls
- Start - toggle simulation
- D-pad - when paused, move cursor
- A - when paused, toggle a cell
- B - when paused, randomize grid
- C - when paused, clear grid
I have a few ideas for improvement and optimization that I will hopefully be able to roll out into a new version pretty soon.
Last edited by ehaliewicz on Fri Dec 27, 2013 1:33 am, edited 1 time in total.
-
- Very interested
- Posts: 145
- Joined: Sun Jan 28, 2007 2:01 am
- Location: DCEvolution.net
- Contact:
-
- Very interested
- Posts: 2442
- Joined: Tue Dec 05, 2006 1:37 pm
- Location: Estonia, Rapla City
- Contact:
Very cool !
Mida sa loed ? Nagunii aru ei saa
http://www.tmeeco.eu
Files of all broken links and images of mine are found here : http://www.tmeeco.eu/FileDen
http://www.tmeeco.eu
Files of all broken links and images of mine are found here : http://www.tmeeco.eu/FileDen
-
- Very interested
- Posts: 50
- Joined: Tue Dec 24, 2013 1:00 am
Update - game of life v2
Update has arrived
https://dl.dropboxusercontent.com/u/358 ... yte-v2.bin
I've improved the controls, added a grid, and a generation counter.
The resolution is also quadrupled, so it's quite a bit slower.
I still have an different algorithm to try, which I hope will make it run fullspeed. It's tricky to implement though, so we'll see when it's done.
Controls
A: When paused, toggle cell, when simulating, toggle grid display.
B: When paused, randomize grid, when simulating, toggle generation counter.
C: Clears grid when paused
D-Pad: Moves cursor when paused
Glider gun
Random cells
Edit: This has not yet been tested on hardware, so let me know if it doesn't work properly.
EDIT 2: Made a performance improvement by skipping multiple empty cells at once rather than single cells (by fetching 4 1-byte cells at once in the main loop)
Also, A and B are switched while simulating.
https://dl.dropboxusercontent.com/u/358 ... e-v2.2.bin
https://dl.dropboxusercontent.com/u/358 ... yte-v2.bin
I've improved the controls, added a grid, and a generation counter.
The resolution is also quadrupled, so it's quite a bit slower.
I still have an different algorithm to try, which I hope will make it run fullspeed. It's tricky to implement though, so we'll see when it's done.
Controls
A: When paused, toggle cell, when simulating, toggle grid display.
B: When paused, randomize grid, when simulating, toggle generation counter.
C: Clears grid when paused
D-Pad: Moves cursor when paused
Glider gun
Random cells
Edit: This has not yet been tested on hardware, so let me know if it doesn't work properly.
EDIT 2: Made a performance improvement by skipping multiple empty cells at once rather than single cells (by fetching 4 1-byte cells at once in the main loop)
Also, A and B are switched while simulating.
https://dl.dropboxusercontent.com/u/358 ... e-v2.2.bin
Last edited by ehaliewicz on Fri Dec 27, 2013 8:03 pm, edited 1 time in total.
-
- Very interested
- Posts: 50
- Joined: Tue Dec 24, 2013 1:00 am
Did you try the updated version? It's a bit faster.r57shell wrote:too slow . where is vsync?
is there source available?
As for vsync, when the screen is really hectic updating takes longer than a VBLANK (at least, I think that's the issue) so you'll always have tearing.
I can't really do much about the speed without some fairly hairy optimization which I'm currently working on.
I'll post the source after cleaning it up a bit.
You can try prebuild table of tranlations, calculation of new state will be like:
C[x][y] = T[a][c];
where x, y - cell position. and a,b,c bitmasks of 3 rows.
or somehow in another way.
so, you don't need then make loop for 9 cells, and make calculations.
I don't know now how to make it in best way...
But, prebuild is definitely better, than mere calculations.
C[x][y] = T[a][c];
where x, y - cell position. and a,b,c bitmasks of 3 rows.
or somehow in another way.
so, you don't need then make loop for 9 cells, and make calculations.
I don't know now how to make it in best way...
But, prebuild is definitely better, than mere calculations.
-
- Very interested
- Posts: 50
- Joined: Tue Dec 24, 2013 1:00 am
r57shell wrote:You can try prebuild table of tranlations, calculation of new state will be like:
C[x][y] = T[a][c];
where x, y - cell position. and a,b,c bitmasks of 3 rows.
or somehow in another way.
so, you don't need then make loop for 9 cells, and make calculations.
I don't know now how to make it in best way...
But, prebuild is definitely better, than mere calculations.
A simple lookup table doesn't speed it up because the bottleneck is the fact that I do two passes over the arrays for each generation. One for a memcopy, the second for processing.
It skips over empty space quickly and keeps each cell's alive neighbor count in the same byte as the cell's state so I don't need to do more than one memory read to check each 4 cells.
I only write to memory when a cell changes, in which case I update the alive neighbor counts for all neighboring cells.
The only way I can think of speeding up this algorithm up significantly is by interleaving the memory copy with the cell processing, but it's tricky to get right, so instead I'm changing it to keep a list of all changed cells to process. That way I can avoid copying and only process cells that need to be processed.
Do you use lookup table to draw?
And, you don't need to do copy.
You can make something like thisand then swap Counts, and CountsNew pointers (different addreses)
And, you don't need to do copy.
You can make something like this
Code: Select all
for (int x=1; x < width+1; ++x)
CountsNew[x][0]=0;
for (int y=1; y < height+1; ++y)
CountsNew[0][y]=0;
for (int y=1; y < height+1; ++y)
for (int x=1; x < width+1; ++x)
{
CountsNew[x+1][y+1]=0;
if(there_will_be_cell(x,y))
add_count_around(x,y);
}
-
- Very interested
- Posts: 50
- Joined: Tue Dec 24, 2013 1:00 am
I need to copy the array because I don't reset the counts to 0. I don't fully recalculate the counts each pass, I increment and decrement them as cells turn on and off.r57shell wrote:Do you use lookup table to draw?
And, you don't need to do copy.
You can make something like thisand then swap Counts, and CountsNew pointers (different addreses)Code: Select all
for (int x=1; x < width+1; ++x) CountsNew[x][0]=0; for (int y=1; y < height+1; ++y) CountsNew[0][y]=0; for (int y=1; y < height+1; ++y) for (int x=1; x < width+1; ++x) { CountsNew[x+1][y+1]=0; if(there_will_be_cell(x,y)) add_count_around(x,y); }
I do use a lookup table for drawing 4 cells per each 8x8 tile.
ok then only lookup table will help.
hmm! you can inc/dec by adding long.
*(long *)&Counts[x][y-1] += 0x01010100
*(long *)&Counts[x][y-1] += 0xFFFFFF00
hmm! you can inc/dec by adding long.
*(long *)&Counts[x][y-1] += 0x01010100
*(long *)&Counts[x][y-1] += 0xFFFFFF00
Last edited by r57shell on Fri Dec 27, 2013 11:14 pm, edited 3 times in total.
-
- Very interested
- Posts: 50
- Joined: Tue Dec 24, 2013 1:00 am
Haha, well, my solution already has most of the benefit of the lookup table anyway.r57shell wrote:ok then only lookup table will help.
A lookup table requires a bunch of reads (and shifts/ands to create the bitmap) to check cells, I only require one read (and a couple of compares) to check a cell, then a bunch of writes if it needs to change.
So it's a tradeoff either way.
That's great thanksr57shell wrote:*(long *)&Counts[x-1][y] += 0x01010100
*(long *)&Counts[x-1][y] += 0xFEFEFE00
-
- Very interested
- Posts: 50
- Joined: Tue Dec 24, 2013 1:00 am
I don't do any DMA except for perhaps when loading tiles on startup..r57shell wrote:Adding long can be not faster though. I don't really know.
Updated previous post, and I'm still thinking that bits->bits lookup is possible.
Do you use DMA to write name table into VRAM? I don't know which way is faster.
I don't think it makes much of a difference because I'm only drawing one tile at a time anyway.
Thanks for the ideas though, I'm still fiddling around with it and I'll post again once it's faster
-
- Very interested
- Posts: 50
- Joined: Tue Dec 24, 2013 1:00 am
Ok, so I've figured out what the bottleneck was.
It's not the memcopy, or even the cell processing, but the drawing.
I restructured the program to use DMA to draw the whole screen at once, so that's very quick now.
I have to speed up the algorithm (or use a different one) if I want it to be faster now.
Edit:
https://dl.dropboxusercontent.com/u/358 ... e-v2.4.bin
No more tearing!
It's not the memcopy, or even the cell processing, but the drawing.
I restructured the program to use DMA to draw the whole screen at once, so that's very quick now.
I have to speed up the algorithm (or use a different one) if I want it to be faster now.
Edit:
https://dl.dropboxusercontent.com/u/358 ... e-v2.4.bin
No more tearing!