Basic graphical game programming how-to needed

Everything todo with programming goes HERE.
Post Reply
gss
Average Program
Posts: 74
Joined: Wed Jun 08, 2005 2:25 pm

Basic graphical game programming how-to needed

Post by gss »

Anybody know of a good how-to for writing a graphics based game? Specifically, I'm trying to figure out the timing structure of generating graphics frames. Should the game be based on a timing interrupt that occurs every x milliseconds, grab user input and game state, and draw a new frame? How is the timing guaranteed in a multithreaded OS?

It would be prudent of me to go through AA code to figure out how it is implemented, but I'm hoping the software wizards here could give me a head start.

I'm asking because... I'm building a custom pinball machine with an LCD under the playfield. The physical pinball will be able to 'interact' with graphics on the LCD. My initial concept prototype (http://www.youtube.com/watch?v=93MJJPrmy6E) has a very simple graphical app running on linux using gtk and cairo. It's based on a timing loop (gtk_timeout_add), but even for my very simple app, the loop times are unpredictable and usually take around 30-40ms despite my asking for 10ms. If I remove the cairo calls to draw a couple circles or squares, the loop times speed up to 1 or 2 ms. Maybe cairo is a bad choice, though I suspect there must be a more efficient way to do what I'm trying to do. Granted, I'm a hardware guy... not a software guy, but I'm hoping to learn enough to be able to write a fairly simple graphics-based game.

Anyway, ignoring the implementation issues in my proto app, please help me understand the best way to structure an app like this.

Thanks.
- Gerry
User avatar
Lucifer
Project Developer
Posts: 8683
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

The pygame how-tos are pretty decent.

Basically, you need a main game loop that runs in the main thread of the program. Use whatever you need to deal with any other threads you have, but generally speaking, if you don't create a thread, you don't have to worry about multithreaded stuff. :)

Get a time value at the beginning of the loop. You need millisecond resolution, however you do it, and you need it to be accurate. Arma used to use an SDL call for that, which gives the time in milliseconds, and it gives the time since the first time its called (so the first time, you get 0).

Use that value for all of your simulation. So if you're simulating a ball falling, and you have a function like f(x) = some physics formula I've forgotten that I normally look up, you'd pass that time value you got at the beginning to your f(x), and update the ball's position accordingly.

Don't assume graphics aren't simulations. :)

The loop itself will typically be something like:

Code: Select all

while(!done) {
// do all the stuff
}
"done" is a boolean, and it's set to "False" all the time, unless some user input lets you crank it over to "True", and then the loop exits. :)

Then you ignore framerate entirely, for the most part.

The reason you do it this way is so that you can smoothly render your animation and do your simulation, take all the time you need to do so, and not have to worry about exceeding some arbitrary timer of some sort. So if you need 40ms, you can take that time and not worry about it.

If your framerate is unacceptably low, then you do regular profiling and optimization and so forth to deal with that.

It's also common to take the initial time, count the number of frames you run, and when you're done, take the final time. Then you do "framecount/(final - initial)" to get the average framerate (and if your time values are in milliseconds, you'll want to convert the denominator to seconds).

In the end, the real determining factor for "acceptable framerate" is esthetic preferences. If you think it looks smooth enough, then your framerate is acceptable. :)

Brush up on your trig, if you haven't already. I've found that graphical effects need a lot of sin/cos to get them to repeat properly. You can do some serious math to get really nice graphics (that's what 3d programming is all about, after all!), or you can fake it and get decent graphics.

Er, I forgot something. If you're in a multithreaded OS and you do what I've said, you will find very quickly that your main loop consumes all available CPU time. That is usually very bad, so you want to tell the kernel at a certain point (usually the very last call of the loop) that it's ok to schedule another thread. You usually do this with a pause of some sort, but depending on your OS, there may be a "yield" command that lets the kernel go ahead and keep your thread going when no other threads need attention. Of course, if your program is the only thing running, you don't have to worry about this (like on a console machine, or your pinball machine).
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden
gss
Average Program
Posts: 74
Joined: Wed Jun 08, 2005 2:25 pm

Post by gss »

Great response. Thanks for the detail. I'm sure I'll have a ton more questions, but a couple come to mind right away...
Lucifer wrote: Basically, you need a main game loop that runs in the main thread of the program.

<snip>

Get a time value at the beginning of the loop. You need millisecond resolution, however you do it, and you need it to be accurate.

<snip>
OK, that makes sense. All of the cairo demo apps I looked at registered a timer with a callback (or inputevents) for rendering new frames. Of course, they were all simple apps.
Lucifer wrote: The reason you do it this way is so that you can smoothly render your animation and do your simulation, take all the time you need to do so, and not have to worry about exceeding some arbitrary timer of some sort. So if you need 40ms, you can take that time and not worry about it.
Though I do need to ensure I react fast enough to the ball moving on the playfield. For instance, if I have an object drawn at a position on the screen and the ball rolls over that position, I need to make sure I don't miss that event. While I will have dedicated hardware scanning the LCD grid in real-time, the time the program reads the captured grid data is dependent on this loop time or framerate. The grid scanning needs to occur at approx 10ms to avoid missing anything. I suppose there must be ways to keep my hardware scanning at 10ms and accept a slower framerate. After all, this example wouldn't be any different than a bullet hitting a moving target in any shoot-em-up game, would it?

I guess I need to think more about the algorithms I'll need to detect these ball/graphics interactions. Sounds like if my algorithms force my framerate to be as fast as the grid scanning, the algorithms are bad.
Lucifer wrote:If your framerate is unacceptably low, then you do regular profiling and optimization and so forth to deal with that.
Please define 'regular profiling'.

Thanks again, Luci. This is a lot of help!
User avatar
Lucifer
Project Developer
Posts: 8683
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

gss wrote: Though I do need to ensure I react fast enough to the ball moving on the playfield. For instance, if I have an object drawn at a position on the screen and the ball rolls over that position, I need to make sure I don't miss that event. While I will have dedicated hardware scanning the LCD grid in real-time, the time the program reads the captured grid data is dependent on this loop time or framerate. The grid scanning needs to occur at approx 10ms to avoid missing anything. I suppose there must be ways to keep my hardware scanning at 10ms and accept a slower framerate. After all, this example wouldn't be any different than a bullet hitting a moving target in any shoot-em-up game, would it?

I guess I need to think more about the algorithms I'll need to detect these ball/graphics interactions. Sounds like if my algorithms force my framerate to be as fast as the grid scanning, the algorithms are bad.
One reason to resort to serious math (which I learned reading arma code) is that it's much faster than fake math. There is a world of difference between how someone who has studied calculus will write a game simulation compared to someone who has only studied algebra.

The other thing is, if you look through arma code (and discussions here on the forums), your issue is real. At some point, we had a bug where cycles would pass through walls, and the problem is similar to what you described. You have to check for that somehow, and when you find that the ball's position is on the other side of a wall when it shouldn't be, you roll back the timer (only for the ball), figure out where the collision happened, change it's movement function accordingly, then simulate from the collision to the current timestep again. That's one way, at least. But yes, you'll have to work on that problem, and it'll bite you again and again.

Even worse, when you have two moving objects whose paths cross, what do you do there? Arma has to assign priority in that case, somehow, because whoever crossed the point of convergence first left a wall there for the other to crash into.
Lucifer wrote:If your framerate is unacceptably low, then you do regular profiling and optimization and so forth to deal with that.
Please define 'regular profiling'.
Regular profiling is what you'd do for any other program that you wanted to optimize for performance. Sometimes you actually run a profiler, other times you put stuff in your program to take direct measurements for particular pieces of code, etc. Maybe you'll have your unit tests also measure runtime for the stuff they're testing. Optimizing for games isn't really any different than optimizing any other program, just that your target performance requirements can be much higher (although not necessarily. There are websites whose performance requirements far exceed those for arma).
Thanks again, Luci. This is a lot of help!
Hey, any time. :)
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden
gss
Average Program
Posts: 74
Joined: Wed Jun 08, 2005 2:25 pm

Post by gss »

Lucifer wrote:The other thing is, if you look through arma code (and discussions here on the forums), your issue is real. At some point, we had a bug where cycles would pass through walls, and the problem is similar to what you described. You have to check for that somehow, and when you find that the ball's position is on the other side of a wall when it shouldn't be, you roll back the timer (only for the ball), figure out where the collision happened, change it's movement function accordingly, then simulate from the collision to the current timestep again. That's one way, at least. But yes, you'll have to work on that problem, and it'll bite you again and again.
It sounds like I should definitely add timestamps to my grid scanning logic... something I hadn't considered doing. Otherwise I'd just be guessing about when the ball crossed each spot, with each guess limited by framerate + USB latencies. Timestamps will tell me exactly when the ball crosses each grid-point; so the only complicated logic is finding what animations were active at the spot at that time.

Now that you mention it, it's interesting how my app is similar to what happens on the arma grid. Guess I'm in the right place to get help. ;) I won't have multiple users playing at the same time, but I will potentially have multiple pinballs flying around and multiple 'virtual targets'.

Fun stuff!
User avatar
Lucifer
Project Developer
Posts: 8683
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

Heh, timestamp everything. :) Best to use an input system that also timestamps.

We have a problem where we roll back the timer to figure out which cycle passed first, but here it's about network latency. You can't ever know the exact time it takes for a given datagram to be sent, so you can't actually know when a cycle turns. The reason? You can't trust the client clocks. A player could conceivably modify his game in such a way that he always wins, if we trusted client clocks. Besides that, they're never in sync with the server anyway due to limitations in the underlying technology. So, if you can't know when a datagram is sent, how do you determine who turned first to avoid the collision? So we roll back the timer and step through carefully to see where the turns probably happened, then guess, essentially. We try to make the best guess available, but it's never perfect. It can't be.

We do stamp each packet so we can determine what order turns and stuff are made in, and that helps, but since we can't trust the clocks, the stamp itself is relatively useless. It's not exploitable for anything, afaik. But even so, network latency being what it is, you still can't really know who turned first, you can only know the order in which a given player executed turns, and you do your best to place them on the grid at the place where they turned.

I suspect there's a lot more arma code that has as its sole purpose convincing the player that what they see is what they actually did, and does nothing else. ;)

Anyway, yeah, timestamp input for sure, if you can. This needs to be done as soon as the input is received, not when you read it from your input buffer. Think about it, when you read it from your input buffer, all input that's currently buffered gets the same stamp. You have a similar situation to what I described, though. You know the order in which the input came, but without a timestamp, you don't know the exact times at which the input happened. You don't have to deal with ping spikes and whatnot, which is nice. But even so, if you know the player clicked the paddle at a particular time, you can look at the paddle's motion relative to the incoming ball at that same time, and step through carefully to see if the collision will happen soon, and mark as appropriate for you to check in future iterations if the collision has happened yet. Without that timestamp, what do you do? ;) (You can approximate, and then take measurements on how often inputs actually come in, because your loop may very well run faster than a person can click, so you may actually be able to trust your loop's current time value as also the same time input was received)

Anyway, there are whole areas of computer science and mathematics dedicated to studying and resolving these problems. When you hit a snag, it's worth studying up on how other people solved them, even if you don't take their solutions (or they're not applicable to your specific problem).
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden
gss
Average Program
Posts: 74
Joined: Wed Jun 08, 2005 2:25 pm

Post by gss »

Lucifer wrote:Anyway, yeah, timestamp input for sure, if you can.
Yep, I can do that. I've implemented the real-time functions (switch/grid scanning, coil driving, light driving, etc) in an FPGA that communicates back to the host over USB. It's a simple matter to have the FPGA log a timestamp each time a switch/grid event occurs. The events will be stored with their timestamps in a queue which the host can request whenever it wants... likely each time through the main program loop.
User avatar
Z-Man
God & Project Admin
Posts: 11624
Joined: Sun Jan 23, 2005 6:01 pm
Location: Cologne
Contact:

Post by Z-Man »

Another important aspect is that in your main loop, you should separate rendering from simulation. Rendering typically takes much more time than simulating the world, so it makes sense to do multiple simulation steps per rendering step. If you don't do that and your ball moves from grid position (4,6) to (6,8) from one rendering frame to the next, which can always happen if it moves fast enough or something interrupts your program for a bit, the ball will appear to 'jump' in your simulation and never touch grid position (5,7). What we do in Arma basically is this:

Code: Select all

// simulation of game world
// dt is the size of the timestep
void Simulate( float dt )
{ // stuff
}

// renders the game world
void Render()
{ // more stuff
}

// returns the current time in seconds
float GetTime();

// game loop
void MainGameLoop()
{
    float lastTime = GetTime();

    // the maximal simulation timestep
    const float maxTimeStep = 0.1;    

    while( !done )
    {
        // determine total timestep
        float time = GetTime();
        float dt = time - lastTime;

        // for big total timesteps, simulate in smaller steps
        while( dt > maxTimeStep )
        {
            Simulate( maxTimeStep );
            dt -= maxTimeStep;
        }
        Simulate( dt );

        Render();

        lastTime = time;
    }
}
There's more. With timestamped input, you should process the input after every simulation step and not take the timer from the system timer, but from the input timestamp. In the ball moving example, you'll likely have several input events:
t=2.00: ball at (4,6)
t=2.01: ball at (5,7)
t=2.02: ball at (6,8)
So there you'd process the first input, simulate .01 seconds, process the second input, simulate another .01 seconds, process the third input, and only then render.

Whether this is useful or necessary depends on the nature of your simulation, of course. It may be simply enough to just process all input events if there's little interaction between grid cells (for example, if you just want to display a trail for the ball). If there's complex interaction (and in games, there usually is), you don't get away with that. If you want to run a "Game of Life" simulation where each grid cell the ball touches comes alive, then you should definitely to the small step simulations as outlined above.
gss
Average Program
Posts: 74
Joined: Wed Jun 08, 2005 2:25 pm

Post by gss »

Z-Man wrote:There's more. With timestamped input, you should process the input after every simulation step and not take the timer from the system timer, but from the input timestamp. In the ball moving example, you'll likely have several input events:
t=2.00: ball at (4,6)
t=2.01: ball at (5,7)
t=2.02: ball at (6,8)
So there you'd process the first input, simulate .01 seconds, process the second input, simulate another .01 seconds, process the third input, and only then render.

Whether this is useful or necessary depends on the nature of your simulation, of course.
Thanks Z-Man, this will definitely be necessary, especially if there's more than 1 ball in play at the same time.
User avatar
Lucifer
Project Developer
Posts: 8683
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

Heh, throw in some drift, too. Game programming isn't easy. :)

If you recall your calculus, when you integrate, if you can find an antiderivative for the function, you can find exact values for any integral.

A computer, however, doesn't work symbolically. Your game loop is basically an integration step (and in physics simulators like ODE, they call it what it is, an integration). And what you're doing is basically approximating the function value for a small interval, then using the results to feed into the next computation (which happens in the next loop iteration).

There is drift! If you sit and work out on paper, using real math, and compare the exact values you get that way to the values that come out of multiple iterations of your game loop, there will be drift.

The first question you have to answer is "Does it matter?" For non-realistic simulations which only have to be believable, it may not matter. For simulations of real things where the player is expected to use his intuitive knowledge of physics, it does matter.

It also matters when you start including different types of functions. For example, it's common to use a linear velocity function for a ball moving, say, in a breakout game. There, you don't have gravity, typically. So you can just take the interval size itself and use it to compute the ball's new position and there's no problem. But if you add in gravity for some reason (usually a crippling powerup), now you can't use the interval size because of the drift. Other objects may still be using linear functions, but you may need to use a function where you can put in the time from the start of the function instead so you can get exact values out of it. (We'll ignore whether or not floats can be considered exact values for the moment) But that makes for functions that are really a pain to work with, and nearly impossible anyway. (You'll have this same problem if you introduce friction into the simulation, I suspect)

If this is something you think you should be concerned about, I suggest you check out ODE and read about it. There's another physics engine, Impulse-somethingorother, from a German PhD researcher, and he goes into a lot of discussion about how his impulse-based integrator is better than the more common integrators (like that used by ODE). You might do it anyway just to get a good, solid idea what you're supposed to be doing in the game loop. ;)
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden
gss
Average Program
Posts: 74
Joined: Wed Jun 08, 2005 2:25 pm

Post by gss »

That all makes sense. Fortunately I don't think I have to deal with accurate physical models and algorithms. In my case the ball really is physical; so it's hard to screw up its position. If I limit 'collision' points to grid intersection points, I'll only care about times when I know exactly where the ball is versus estimating an in-between position. As for the 'video game' physics, I have no intentions (yet) of making any complicated motion algorithms. Think pac-man or missile command or things along those lines. :)
User avatar
nsh22
Round Winner
Posts: 378
Joined: Fri Sep 07, 2007 8:12 pm
Location: eating, cooking or writing (about cooking).
Contact:

Post by nsh22 »

i r confused. how much of your time did it take you guys to learnall this stuff about programming and code? also, have u been to school for it?
User avatar
Lucifer
Project Developer
Posts: 8683
Joined: Sun Aug 15, 2004 3:32 pm
Location: Republic of Texas
Contact:

Post by Lucifer »

nsh22 wrote:i r confused. how much of your time did it take you guys to learnall this stuff about programming and code?
34 years and counting. Programming is life, therefore by living a full life, you will become a better programmer.
also, have u been to school for it?
Hard Knox University.

(Real programmers don't have programming degrees, only codemonkeys have programming degrees)
Image

Be the devil's own, Lucifer's my name.
- Iron Maiden
User avatar
Tank Program
Forum & Project Admin, PhD
Posts: 6712
Joined: Thu Dec 18, 2003 7:03 pm

Post by Tank Program »

nsh22 wrote:i r confused. how much of your time did it take you guys to learnall this stuff about programming and code? also, have u been to school for it?
I'm no expert, but what I do know I've picked up over the last 8 or 9 years. In fact, I'm in the middle of school studying for an entirely unrelated degree.
Image
gss
Average Program
Posts: 74
Joined: Wed Jun 08, 2005 2:25 pm

Post by gss »

After spending some time learning some of the qt and gtk frameworks, I'm back with another noobish question.

How do you implement this variable framerate style of program 'while (1)' and use these event-based frameworks? Are they mutually exclusive?
Post Reply