News:

Building a 3D Ray Tracer  By stevmjon

Main Menu

Timer Based Movement Tutorial

Started by kevin, May 20, 2007, 11:47:15 PM

Previous topic - Next topic

kevin




 Visit www.PlayBasic.com


>> Timer Based Movement in PlayBasic PART #1<<


 'The Interpolation Approach'

By Kevin Picone

19,May,2007

www.UnderwareDesign.com - www.PlayBasic.com

(c) copyright 2007/2012 Kevin Picone, All Rights Reserved.

  Document Revision: V006

Download

 Timer Base Movement Tutorial & Examples






Intro

 

    The following tutorial demonstrates one possible solution to approximate 'consistent' movement and spawning rate in a game, regardless of computers physical frame rate.


   To clarify - Physical frame rate refers to how fast a computer can process & draw the objects/characters on screen. Back in the 8/16 bit era of computing, this was largely unnecessary as games were designed to run on one standard hardware configuration. Meaning there was virtually no diversity between users home systems. So developers could assume all systems would run have the same CPU and graphics speed. So how it runs on one machine, gives a 99.9% indication of how it will run
across all machines of that type.


   Today however we don't have this luxury. Why ? - Because the computers people use today, are built from a virtually endless combination of components I.e. CPU, VIDEO, SOUND RAM and MotherBoard etc etc. This diversity gives each system vastly different performance. While this is great for users power & flexibility, let alone their bank balance. It does mean that program authors can no longer rely upon the "if it works on my machine" it'll work on all machines philosophy.


   Traditionally movement and redrawing in 2D games was all interconnected. So each update programmers would move the characters and draw them to the screen at their new positions. This process is commonly referred to a refresh or frame. How fast this occurs, is therefore directly linked to how fast the computer can move and refresh the screen.


   For example, lets say we have a program that draws 100 characters all moving left to right across the screen. If our program moves each character 1 pixel (dot) to the right each refresh. Then how fast the characters appear to move is now totally dependent upon how fast the computer can execute the program.


   To get a clearer picture, Lets compare how long it would take a characters to move all the way across the screen, on two different computers. Assuming the screen is 800 pixels wide.



      * Machine A - (slow system - older than 5 years) Sub 1000 Mhz

          Lets say this machine can execute the program at a solid refresh rate
         of 30 times per second. This means that each character moves
         30 pixels to the left in any one second time period. So to complete
         it's journey, it's going to take (800/30) = 26.6 seconds from start
         to end.



      * Machine B - (fast system - less than 1 year old) faster than 3000 Mhz

          Lets say this machine can execute the program at a solid refresh rate
         of 1000 times per second. This means that each character moves 1000
         pixels to left in one second. So to complete it's journey it's going
         to take (800/1000) = 0.8 seconds from start to end




   Clearly there's a big discrepancy here. People running the program on system A would see the character slowly moving across the screen, while people running it on system B, would see the character flash across the screen in less than a second.

   You might have noticed this yourself playing old DOS games on a new PC's, Or perhaps while playing retro games under emulation. It's the exact same issue.








How Do We Solve This ?


   There's a few approaches, the simplest is to cap the performance of your application. This will stop it from running too fast on more modern computers. To do this, we simply check how long it took our program to update the game characters and draw the screen. If the computer is faster than we need it to be, then it'll be able to refresh everything in less time than we expect! When this occurs, we force the computer to wait the excess time. Thus slowing our game down to our desired rate. This has the added benefit of giving back any extra processing time back to any other applications that might be running in the background.

   If that sounds too complicated, then you're in luck. In PlayBASIC you can just use the SETFPS feature, it does the exact the same thing.

   I.e.
PlayBASIC Code: [Select]
   ; Tell PB to limit this program to a 30 frames per second or less
SetFps 30

; declare the XPOS variable
Dim Xpos as integer

; Start of the main loop
Do

; Clear The Screen
Cls rgb(0,0,0)


; Move our example object from left to right
Xpos=Xpos+1


Circle Xpos,300,30,true


; Display how Fast it's running
Print Fps()


; Refresh the display
Sync

; loop back to the do-statement to keep the program running
loop





    While this will work, it only addresses stopping the program from running too fast. Which is only halve of the problem. What happens if we run our program on a machine that is unable to maintain the required refresh rate ? The program slows down. The slower the computer, the slower the program. For games this can be unacceptable.

    You can either choose to ignore those users (ie. why support obsolete technology?) , or look into some methods that approximate movement based on some type system constant.  Like the system TIMER()



The Raw Concept


   The previous program above follows a linear path. Where it handles the  movement / drawing each complete refresh cycle. That is to say, the program steps the character(s), draws the character(s) and repeats that process over and over.  So the user sees every step of the characters movement. The problem with this, as we've just discovered, is that this approach ties our programs performance to the performance of the computer it's been executed on.  Which is not always good.


   One alternative (and the method used in the included example) is that we can scale our movements according to the amount of time that has elapsed since the object was created.






About Timer()


   When we talk about game timing in PlayBASIC, we're not simply referring to getting the current time and date. Those just aren't accurate enough for our needs. This is because our game will be refreshing anywhere between say 30 to 100 frames per second. So we need something that can measure time at least at that speed or faster preferably. Introducing Timer()


   The Timer() function returns the current time in what's called milliseconds. In case you're not familiar, there's 1000 milliseconds in a second, Or another way of thinking of it, is that each millisecond represents a 1000th of a second. Either way, it's very fast!

  Since the Timer() returns values that represent 1000th of second, it's not bound to the speed to the computer. So 10, 50, 100, 500 milliseconds take the same amount of time regardless of how the fast the computer we're running on.  So it's perfect for our game timing needs.





Basic Implementation



   To do this, we need to keep track of the creation time of each spawned character in our game. Then each refresh, we subtract the current time (in milliseconds) from it's creation time (in milliseconds). This gives us the total number of milliseconds that object has been alive for.

   E.g

         TimePast#= Timer()- ThisCharactersCreationTime



   Now depending upon your personal preference here, and personally I like keep my objects speeds in pixels per frame, rather than pixels per millisecond. This means that once I've established the TIMEPAST, I then divide this by the Number of milliseconds that each frame should take. This gives me the number of Frames past since the object was created, or perhaps changed direction.


 
   E.g

         FamesPast#=TimePast#/MillisecondsPerFrame#



   So calculating the objects position at any given time is just a matter of multiplying the characters movement speed by the FramesPast# value. This gives us how far the character has moved since it was created. So assuming the object is just moving along the X axis, that calculation might look like this.


   E.g

         DistanceMovedAlongXaxis#=CharacterSpeed#*FramesPast#


   All that remains now is to calculate it's Current position. Which is just a matter of adding the Distance the character has moved since it was created, to it's starting position.


   E.g

          CurrentXposition# = CharactersStartingXposition# + DistanceMovedAlongXaxis#


   And there we have it, the great mystery of the Timer Based Movement is solved.   or is it ?





Calculating Milliseconds Per Frame


   You'll have notice in the above there's one missing ingredient from our calculations, whats this mysterious MillisecondsPerFrame# value ?

   MillisecondsPerFrame# is a the number of the milliseconds one complete refresh should take, when our game is running at our 'perfect' frame rate. To calculate it, we divide the total number of milliseconds in one second (1000) by whatever our ideal frame rate should be. In the included example is 50 frames per second.



   E.G
 
          GamesIdealFramesPerSecond# = 50

          MillisecondsPerFrame# = 1000.0 / GamesIdealFramesPerSecond#
 



   This gives us the number of milliseconds one complete frame should take. This can then use it to calculate the how many frames have past, or for example it can be used to calculate and control when new characters should be spawned.






Spawning New Characters ?



    One of the most commonly overlooked topics when talking about timer based movement, is not only keeping our characters moving at a nice relative rate, but making sure we spawning new characters evenly also.

    To get an idea of the problem, lets revisit the previous example. Lets imagine were want to move our characters on screen from left to right again. Each time we update the refresh the game, we add a new random character to the left hand side of the screen. So we theoretically have a constant stream of characters being  spawned and moving across the screen.

   The the main loop (in pseudo code) might look something like this.





         ; Start of main loop
        do

          ; clear the screen
           Cls

          ; draws/moves our list of characters across the screen
           DrawCharacters

          ; Randomly Spawn a new character every loop
           SpawnNewCharacter


          ; refresh the screen so the user can see the changes
           Sync

        ; loop back to the DO statement to keep the program running
         loop




   Now assuming the characters movements are based on the computers timer, the characters should each appear to move at relatively the same speed regardless of the computer the loop is running on. But what about SpawnNewCharacter ?, should this be executed every time the main loop is processed ?

   No, it shouldn't. Why ?, because the speed the of computer dictates how frequently the Main loop is being executed here. The slower the machine, the less frequently this loop will be executed. The faster the machine, the more frequently the loop is executed.  In other words slower machines spawn less new characters than faster ones. Therefore Making the your games behave differently  across different speed systems. Which is Not ideal!


  How do we get over come this? Just as we did previously with movement, we just have make sure our character spawning mechanisms work independently of the speed of the host computer. So rather than adding a new character each time the computer processes the main loop. We only add a new character after a certain number of milliseconds has transpired.

  So if we wished to spawn new characters at our games ideal frame rate, we need monitor the spawn time relative to our ideal frame rate. The method I normally use is to simply hold the Time of when the next frame is expected to start. Then each time the main loop executes, we're comparing the current system timer() with our expected time.



PlayBASIC Code: [Select]
      ; Our ideal frame rate of our game
IdealFramesPerSecondRate=50


; the number of milliseconds one complete frame will take
MillisecondsPerFrame= 1000.0/IdealFramesPerSecondRate

; Init the Expected time in milliseconds of when the current frame has ended
StartOfNextFrame=Timer()+MillisecondsPerFrame

; Start of main loop
Do

; clear the screen
Cls 0

; draws/moves our list of characters across the screen
DrawCharacters

; Only Spawn a new character if enough time has passed
if Timer()=>StartOfNextFrame

; randomly spawn a new character
SpawnNewCharacter

; Adjust our time variable forward to the time that the
; next frame will start.
StartOfNextFrame=Timer()+MillisecondsPerFrame

endif

; refresh the screen so the user can see the changes
Sync

; loop back to the DO statement to keep the program running
loop





   This will work, but there's a problem. It's only limiting the number of character spawns on computers that can process the main loop faster than our ideal frame rate. But on slower machines we'll still miss character spawns. Which the will change the behavior the game on those systems.

   The solution is simple, rather than just assuming only one frame has passed and spawning one character, we'll actually calculate the number of frames (to meet our ideal frame rate) that have past since the last refresh. On fast machines this will generally only be one frame, but on slower machines, or when the game is being bogged down by rendering too much graphics perhaps. Two, three or more frames might have passed. So in order to cope with this, we need back track our character spawning and generate any characters that would have been otherwise missed.


   What this effectively does is ensures that we get a fairly consistent spawning behavior across the broad spectrum of possible computer speeds. It's not necessarily perfect, but it's highly unlikely the player will notice any inaccuracies. So it's more than good enough to make the illusion appear seamless !








kevin

#1





>> Timer Based Movement in PlayBasic PART #2<<

 'The Interpolation Approach'

By Kevin Picone

19,May,2007

www.UnderwareDesign.com - www.PlayBasic.com

(c) copyright 2007/2008 Kevin Picone, All Rights Reserved.

  Document Revision: V005






 
Potential Problem Areas



    Yes, believe it or not, there are some issues that need to be resolved in order to get a timer based system working perfectly. Some of which are character Collisions, Animations and None Linear Movements.



    Collision

      Collision detection can create issues in timer based systems when detection     relies purely upon two regions overlapping. The problem occurs when our program is running on machines that's are unable to keep up with the games ideal frame rate.    This is a problem because on those machines, characters are being moved greater distances each refresh, to compensate for the slower machine.  So some frames have been skipped.    In those situations, it's not uncommon for two reasonable fast moving objects to 'skip' over each other, even when on a collision course.



    Solution Ideas:
 
     1)  A quick way to detect if they might have hit, is to create bounding
        boxes around the objects paths (padded to include the objects size).  Then
        we can just compare the regions together.  If the regions overlap, then
        it's possible they intersected at some point during the last update.  If not,
        there's no need to compare them any further.   When they do overlap though,
        we'd still need some secondary method to check if they actually hit each
        other while traveling.   This just gives us a way to reject trivial/impossible
        cases quickly.


     2)  Solution would be keep track of the paths the objects are move from last
        update to this update.   We'd then compare the two paths (rays)  to find the
        close point between the two paths.  Ie  The first point where they could have
        potentially hit (when the distance between the paths is less than the total
        combined radius of both objects).   This doesn't necessarily mean the objects
        are touching, just that a collision is possible.  

     3)  Another solution cheap & easy is to use a binary chop approach.   That is we
        examine how far the two objects have moved between this update and the last
        update.  We then chop this distance in half and check for a collision at this
        point.   If no collision, we check at the end point.    This could be taken
        further by recursively cutting up the paths the two characters are moving along
        and comparing them in smaller steps.  

     4)  A Variation of #3 is that rather just subdividing the paths, we get the speeds
        of the two characters.  Then take the speed of the slowest moving character,
        and use that to step along the two paths.   Comparing the object at each step.

     5)   Ray intersection.  This is similar to solution #1+2 combined.  After
        comparing the two paths via bounding boxes (method #1) we then make two
        rectangle/polygon shapes from the paths.   The shape represent the paths of
        both object (including the objects width) So where making two fat polygon lines.

          Once we have these we can check if these regions overlap using PlayBasic
        shape intersections.  If they do, we could then run ray/line to shape
        intersections to try an find the closest point along the movement paths where
        they intersect.
 


  There are lots of combination approaches, but hopefully these will give you some
ideas on how to cope with collisions better.



   Animation

      This not so such a huge problem, just something that we need to bring into our considerations when making games run off the system timer().   Commonly 2D games use frame based animations.  By that I mean, the each time the game refreshes the world,  it steps animated characters forward through a series of user defined animation frames.  This not only gives the illusion to the player that the character is performing some action, it make animations bound to the speed of the computer.    Which is what were trying to avoid here.  


      Thus Animation needs to be tackled much the same as movement, where the current animation frame will be calculated from the time this redraw refresh  is taking place.   For cyclical animation this is pretty straight forward.  All we need is the time when the object was spawned, the number of frames in the  animation and the animations ideal frame rate.   So here we can calc what frame  we should be displaying at this refresh.
   
      In more complex animation systems, (where animations are chainable perhaps)  you'll have to keep track of what animation your currently in.  Which just means keeping track of when this animation starts and is expected to end.  If the current refresh time is greater than the end time, we move to the next animation  sequence.  We do this recursively, since It's also possible that the next  animation  may well have already ended.  So we'd need to skip those also. Once  we've found the current anim set, we just locate the current frame as per above.



  NOTE:  For the best collision results,  Movement & Animation need to be considered!





 
None Linear Movement



       This tutorial and example that comes with it, basically assumes characters are moving in straight lines at fixed speeds.  While this suits most     traditional 2D games,  things can get a little more complicated if you want/need a more elaborate movement system.


      There's three basic approaches that come to mind.  

      1)  You can use formulas that lets you plot movements against time
          (Projectile Motion)


      2)  You manually step the movement forward according to the number of
         frames that past since last update.    


      3)  Combination of both.




Done



  Hopefully this will give you some insight on how to go about implementing  timer control  mechanisms into your games & demos.  I wish you the best and hope to see your creations one day !



 
Download



 Timer Base Movement Tutorial & Examples