Fixed Rate Logic and Millisecs() Wrapping
BlitzMax Forums/BlitzMax Programming/Fixed Rate Logic and Millisecs() Wrapping
| ||
| I've been researching various game timing methods and stumbled upon a great article which gives overviews of four popular game timing methods. The article is located here: http://www.koonsolo.com/news/dewitters-gameloop/ For my game I've implemented the last timing method mentioned in the article, "Constant Game Speed independent of Variable FPS". This method relies on a fixed logic rate (i.e. updating user input/physics/etc. X times per second) while rendering things as fast as possible. Interpolation is used on the render-side to keep movement/rotation/animation/etc. smooth, even when the number of logic updates per second is low. The pseudocode given for this in the article (and slightly changed to be more Blitz compatible) is: The snag I've ran into with all of this (and something the article doesn't cover) is that the logic loop doesn't account for times when Millisecs() hits the storage limit for an integer and wraps around. To illustrate the problem, here's an example: Let's say Millisecs() has a min and max value of (-1000, 1000). So when Millisecs() = 1000, adding 1 more to it would cause it to wrap around to -1000. When the program starts, next_game_tick is set to, say, 960. The inner while() loop runs fine the first time as Millisecs() would return slightly more than 960 (say, 970, indicating 10ms has passed since next_game_tick was initially set) and 970 is indeed greater than 960. The inner while() loop would essentially be evaluating: 970 > 960. So the inner while() loop runs once. update_game() is called, next_game_tick is incremented by 25 (or whatever value is assigned to SKIP_TICKS) and the loop ends. Unfortunately update_game() took 40ms to perform. In that time, Millisecs() has increased by 40 and has wrapped around to -990. next_game_tick was incremented in the previous loop so it's value remains (960 + 40) or 1000. The inner while() loop will now attempt to evaluate: -990 > 1000. This obviously returns false and so we don't do a logic update that frame. Say 40ms go by, Millisecs() now returns -950. next_game_tick is still set to 1000. The inner while() loop once again evaluates things: -950 > 1000. Nope. Still no logic update. And so on. If I'm understanding things correctly, once Millisecs() wraps around, the program is dead until it's restarted because the inner while() loop (or logic loop) will never run again. So, the main question is: does anyone have any ideas on working around this? |
| ||
| You realise how long that would take? Anyway what you do is see if the absolute differance of the logic timer is greater than a certain amount, NOT equal to a certain amount, or signed greater than This also gets round problmes of PC freeze |
| ||
| One way is to use the high resolution timers, which start counting when the program is executed, instead of when the computer was turned on. I have a HR module in the code archives and I believe there are a couple of alternative ones there as well. Another way is to check if the next_game_tick is above the millisec() rollover value. If it is, then subtract the correct amount to compensate. It would only need to be done once, since the timer and the variable will now be in sync. I can't remember the correct value to subtract or check for, but I'm sure you can find that info on the web somewhere. |
| ||
| >> "You realise how long that would take?" Millisecs() wraps around roughly every 25 days I believe. That's not an unusually long uptime at all for many systems. In this case it's not really about how often Millisecs() wraps around but what happens in the rare case that it wraps around while the game is running. That could mean the game has to run for ~25 days, an hour, ten minutes, a single second, etc. >> "Anyway what you do is see if the absolute value of the logic time is greater than a certain amount, NOT equal to a certain amount" Toss some pseudocode my way perhaps? Thinking about all of this has turned my brain to mush. :] The solution can't be a simple "run this loop every X ms" because that's only half the problem. In the current version the inner while() loop will run at least once every 40ms or multiple times consecutively (up to a max of MAX_FRAMESKIP) if the logic loop takes longer than SKIP_TICKS to process. In other words, there's a mechanism for playing 'catch up' if things start to slow down. >> "One way is to use the high resolution timers, which start counting when the program is executed, instead of when the computer was turned on. I have a HR module in the code archives and I believe there are a couple of alternative ones there as well." Hmm. I've stayed away from QueryPerformanceCounter()/gettimeofday() due to some horror stories about consistent support across different hardware. I know this was an issue with Torque Game Engine games as recently as 4 years ago (something about AMD processors with Cool'n'Quiet enabled?). I haven't kept up with timer support so things may have gotten better since then. |
| ||
| Problem with HR timers is they are not thread safe. If you read a timer on a multi-processor system, you don't know which core the timer will be read from and the timers can be off from each other. If you always read them from the main thread, it should be ok, except on a few older buggy systems, or systems so old they don't even have HR timers. I did have another thought, maybe you could use event timers. Use CreateTimer() to create a timer, then put TimerTicks() before your logic loop to find out how many ticks have passed since last call. You could even set up an event handler if you want so the logic could be set up in another function to be called automatically every tick. Pseudocodish :)
Local Timer:TTimer = CreateTimer(TICKS_PER_SECOND)
While GameNotDone
Local Ticks:Int = TimerTicks(Timer)
While Ticks
DoGameLogic()
Ticks :- 1
Wend
DoGraphics()
Flip
Wend |
| ||
| In the current version the inner while() loop will run at least once every 40ms or multiple times consecutively (up to a max of MAX_FRAMESKIP Ahh, I'll look at the code next time lol ;(If we are allowing Timer code and stuff take a look at this BRILLIANT code lol http://www.blitzbasic.com/codearcs/codearcs.php?code=1721 Global TheBeatname:TBeat = New TBeat.Create (Millisecdelay:int, Ptr Function to call)Would then auto call whatever function you pointed to every "millisecdelay", and cos it uses events, if will call it more times if the pc had hit a freeze for whatever reason |
| ||
| @ TomToad: Timers may work, I'll have to do some more research. It's not terribly difficult coming up with a way of running something at set time intervals that doesn't rely on Millisecs(). The wrench in all of this is handling the part of the inner loop that says "ok, we're running behind! let's play catch up!". The current version basically says: if enough time has passed since the last logic update AND we haven't ran the logic loop MAX_FRAMESKIP times then update_game(). If things are running well (say, on a fast computer) then Millisecs() will only be slightly larger than (next_game_tick + SKIP_TICKS) and so the loop will only run once/update_game() will only be called once. If things are running slowly then Millisecs() will be much larger than (next_game_tick + SKIP_TICKS) so the inner while() loop will run multiple times, effectively taking SKIP_TICKS sized "bites" out of the time difference until Millisecs() is no longer larger than next_game_tick OR until the loop runs MAX_FRAMESKIP times. It's a tough problem for sure and there's a surprising lack of information about this. Probably because the problem will only occur in rare circumstances and restarting the game will immediately fix it (at least for another ~25 days!). @ H&K: Brilliant code for sure! ;] I haven't used the event system in BMax much. I'll take a look at the above and see what happens. Edit: Another thought I had that might be the most straightforward solution: just detect the wrap around event (i.e. if in one frame Millisecs() goes to -2billion while next_game_tick is still +2billion) then set next_game_tick to Millisecs() again, thereby ensuring that the logic loop runs once and Millisecs() will continue to be greater than next_game_tick. I think I just had a "Duh!" moment. :P Edit 2: How does this strike everyone as a way of detecting the wrap around event: If ((Millisecs() < 0) and (next_game_tick > SKIP_TICKS)) Then next_game_tick = Millisecs() What this is saying is if Millisecs() is negative while next_game_tick is positive and greater than SKIP_TICKS (indicating it's more than 1 'tick' apart from Millisecs()) then Millisecs() has wrapped around so next_game_tick needs to be reset. |
| ||
| The right way is to avoid comparisons like time2 > time1. Use differences like (time2 - time1) > 0. The wraparound is then a non-issue. For example in your (-1000,1000) system consider starting with time 995. After 10 clock ticks the time is 1005, which wraps to -996 = 1005 - 2001. The direct comparison -996 > 995 fails. But ( -996 - 995 ) = -1991, which wraps to -1991 + 2001 = 10. So the test ( -996 - 995 ) > 0 is evaluated as 10 > 0 as it would be with no wrapping. |
| ||
| Hello. It would be a slight overhead, but to avoid the wraparound problem couldn't you check to see if the second time recorded is smaller than the first - that would allow you to deal with wraparound. Goodbye. |
| ||
| Well that's just ingenious, Floyd! |
| ||
| Actually Floyd's idea wouldn't work. The problem is that Millisecs() uses 16 bit precision while an Int is 32 bit. So the result of the subtraction would be another negative number. In his example it would be -996-995 = -1991. Since that is within the precision of the result (which would be -2000 to 2000 in the example) it will not roll over and not be greater than 0. If that were not the case, then he could just simply continue to do as he was doing before since the Next_Tick would just roll over automatically like Millisecs() would. |
| ||
| Its funny this topic just came up because I just had to redo part of my timing system to accommodate discrete timing better. I was going to say the same thing about the wrap as floyd.. but he beat me to it! My system now limits the time delta to a full tick... but stores the remaining time as a tween value. so... if 2.5 ticks go by it will update the tick value 2 times (if thats the limit), have a last_ms time set to the tick boundary (boundary=1000/freq), but will have a tween value of 0.5 stored for use by whatever needs it...presumably the draw routine. I did this because of some reading I did on networked games. It mentioned that it is easiest to network a game that had predictable game "states" ie predictable sprite locations (updated once per game "tick"). I was using the tween value between calls but I found I had sprite timing mis-aligning from sequencer timing (sequencers control values over time) Since your working on timing I thought I might mention it. |
| ||
| On second look, Millisecs() uses timeGetTime() function which returns a 32 bit value. Is the problem maybe when Next_Tick rolls over but Millisecs() hasn't? For example, Next_Tick = 980, Millisecs() = 981. Game runs the logic loop once. Next_Tick :+ 40 = 1020 which rolls over to -980. By the time Millisecs() is tested again, only 14 milliseconds have passed and Millisecs() now equals 995. 995 is greater than -980, so the logic loop executes. It will actually execute over and over again until MAX-FRAMES is reached. This will continue each time Millisecs() is tested until Millisecs() finally rolls over, causing a huge acceleration of game logic. Now Next_Tick = MAX_Frames * (number of times Millisecs() was tested before rollover) so the game freezes until Millisecs() catches back up to the Next_Tick value. Now taking Floyds example, 995 - (-980) = 1975 which rolls over to -975 which is less than 0, so Floyd's example should work after all. |
| ||
| I was a bit concerned about the case where next_game_tick wraps around before Millisecs() as well. I'm a visual guy so I ended up writing a quick test case to see how Floyd's method handled such an event: The result should be: DebugLog:Starting MS: 2147483645 DebugLog:Starting NT: 2147483644 DebugLog:Run logic loop? 1 DebugLog:Elapsed MS: 2147483647 DebugLog:Elapse NT: -2147483612 DebugLog:Elapsed MS - Elapsed NT = -37 DebugLog:Run logic loop? 0 DebugLog:Run logic loop? 1 Which is saying: * these are the starting times * run loop? * these are the new elapsed times * run loop? * ...40ms passes... * run loop? It works as expected. :] @ Skully: Isn't game timing such a joy? Ugh. The method I posted above also interpolates entity states between logic ticks (hence the "interpolation = float( Millisecs() + SKIP_TICKS - next_game_tick ) / float( SKIP_TICKS );" line) Now actually making use of that interpolation value for render tweening (especially for rotations of 3D entities) is a bit beyond me right now. :] |
| ||
| Now actually making use of that interpolation value for render tweening (especially for rotations of 3D entities) is a bit beyond me right now. :] if you know the last x,y position you can determine a movement vector & normal from that, and then multiply it by the tween 0-1 value |
| ||
| if you know the last x,y position you can determine a movement vector & normal from that, and then multiply it by the tween 0-1 value Going off topic here but I'm having some trouble wrapping my head around applying interpolation to positions. The article I linked says to do interpolations between positions as such: view_position = position + (speed * interpolation)Where view_position is the actual rendering position of the object. In my game I'm using MoveEntity() to move entities a set distance relative to their orientation (i.e. MoveEntity(0, 0, 5.0) will always move the entity 5 units forward, regardless of what direction "forward" is). Where I'm running into a brick wall is reworking this so that I can create a view_position. I suppose a good starting point is figuring out how to do what amounts to a MoveEntity() that only updates a "fake" position. This "fake" position will (hopefully?) plugin in the interpolation equation, like so: view_position = "fake_position" + (speed * interpolation). This is fun stuff that makes you appreciate Blitz3D's CaptureWorld/RenderWorld tween# param. :p |
| ||
| Ohhh.. I didn't realize you were doing 3D! What are you using miniB3D? |
| ||
| so Floyd's example should work after all. Yes, unless something dramatic has changed recently with the way Millisecs works, Floyd's answer should indeed be correct. |
| ||
| Ohhh.. I didn't realize you were doing 3D! What are you using miniB3D? Yep, 3D via miniB3D. I've gotten rotations tweening appropriately but being able to "move" entities along their direction vector while also interpolating their positions is just beyond me. |
| ||
| Possibly move the entity to it's current position, then get the absolute x,y,z values, move the entity to the next position, get that x,y,z value, then do an absolute move to the tweened position. |
   |