Hi guys, i've been toying with the "game of life" for a few days, and
been able to achieve blazing speed by using shaders to compute the
next generation on the gpu (it can also do all the work on the cpu, so i
can compare both methods speed).
The problem i have is this: at some point, the game will be "stuck", generating
the same 2 frames over and over, alternating between them forever... I need
a way to detect this. If i do it on the cpu, it's easy since i could just
compare the last few frames to see if the game is stuck, using memcmp, or even
better, generate a hash while computing the next gen and just compare the last few of them. Easy.
But when i use the gpu path, i only have the first frame in client memory (ram),
and i don't know how to solve this problem other than use the slow glReadPixel.
Perhaps a PBO could help, but im not very familliar with them. From what i remember,
it wouldn't be that much faster anyway. What i want is some clever way to do that without
losing too much framerate.
So, any though?
/////////////////////////////////////////////////////////////////////////
Those 2 files simply show how i use the code for both mode:
CPU example code.txt
GPU example code.txt
Those are the 2 main classes of the project:
GLEngine.h
GLEngine.cpp
The game of life.h
The game of life.cpp
Note: (most relevant bits of code is near the bottom of each files)
And finally, the shaders:
Life.vs + Life.fs
If you see anything i can improve on, please let me know!
Game of life on GPU question...
For a short term solution you could generate two generations in a single iteration, I think it would be sufficient unless you really want the crazy speed. (Yet I don't think it will reduce performance that much).
"I need a way to detect this."
Welcome to the "halting problem". (Life patterns are general computers and hence determining their termination falls under the halting problem).
There's no general way to detect these loops -- While two-stage cycles are quite common, you can get three stage... and four stage...
In fact you get N length cycles with a probability of something around 1/N.
There are also sequences which don't repeat exactly, but also don't produce new information -- the famous "r-pentomino" settles down into a sea of static objects, blinkers and a couple of gliders. The blinkers/statics form a simple loop of 2, but the gliders are more problematic -- while they repeat their internal pattern, they move across the plane so the generations aren't identical.
The good news is that because life is forwardly deterministic, if you see ANY generation you've ever seen before, you know you've entered a loop.
So one simple approach might be to hash your array and keep the hashes. If you see one again, it's a loop.
It won't help you with the gliders... you'll have to get MUCH more creative with them. Note that there is an arbitrarily large set of moving-but-effectively-unchanged objects. Collectively they're call "spaceships" and there's a couple of dozen of them. (There's a catalogue at http://www.conwaylife.com/wiki/Spaceship)
You could measure the expansion of your life frontier (the boundary of live cells) and the count of total live cells. If it steadily increases at a linear rate for more than a certain amount of time, you could conclude that you have a looping system along with a cloud of spaceships moving away from the objects. Spaceships move at known fractions of c -- a glider is c/4 and after 4 cycles it returns to the same number of cells... The problem is that if you have (say) a 5-blinker in your static objects, your loop is now 20 generations, so what you're looking for in that system is a long-term linear trend in the boundary growing at some fraction strictly less than c while the number of cells oscillates through a set of counts (which annoyingly can also be arbitrarily long...)
To emphasise there is NO general purpose solution -- it's demonstrable mathematically for this class of systems that you cannot produce one and trying to will consume periods of time bounded only by your lifespan.
You can get a "good enough for me" solution so aim for that.
glReadPixel.
Perhaps a PBO could help, but im not very familliar with them. From what i remember,
Remembering a 1600*1200x4 big memory is like 16.0*12.0*0.004 DB what doesnt make sense, but maybe it breaks even L3 1.2MB big cache. You may render and generate mip maps of render target though. And try to accquire the particular level onto cpu, a luxury scale of 128x64 pixels :)
