Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  1.  
  2.  Fixed Rate Pig - a fixed logic frame rate demo
  3.  ----------------------------------------------
  4.  
  5.      This SDL programming example - a simple
  6.      platform game - demonstrates the use of
  7.      a  fixed   virtual  logic   frame  rate
  8.      together with interpolation, for smooth
  9.      and   accurate   game  logic   that  is
  10.      independent of the rendering frame rate.
  11.    
  12.      The example  also  demonstrates  sprite
  13.      animation  and partial display updating
  14.      techniques,   suitable  for  games  and
  15.      applications that need high frame rates
  16.      but can do  without updating  the whole
  17.      screen every frame.
  18.  
  19.  
  20. Fixed Logic Frame Rate
  21. ----------------------
  22. Having a fixed logic frame rate means that the game
  23. logic (that is, what defines the gameplay in terms
  24. of object behavior and user input handling) runs a
  25. fixed number of times per unit of time. This makes
  26. it possible to use "frame count" as a unit of time.
  27.    More interestingly, since the logic frame rate
  28. can be set at any sufficient value (say, 20 Hz for
  29. a slow turn based game, or 100 Hz for fast action)
  30. the logic code will run exactly once per frame.
  31. Thus, there is no need to take delta times in
  32. account, solving equations, making calculations on
  33. velocity, acceleration, jerk and stuff like that.
  34. You can just deal with hardcoded "step" values and
  35. simple tests.
  36.    Perhaps most importantly, you can *still* rely
  37. on the game behaving *exactly* the same way,
  38. regardless of the rendering frame rate or other
  39. system dependent parameters - something that is
  40. virtually impossible with delta times, since you
  41. cannot have infinite accuracy in the calculations.
  42.  
  43.  
  44. Virtual Logic Frame Rate
  45. ------------------------
  46. By "virtual", I mean that the actual frame rate is
  47. not necessarily stable at the nominal value at all
  48. times. Rather, the *average* logic frame rate is
  49. kept at the nominal value by means of controlling
  50. the number of logic frames processed for each
  51. rendered frame.
  52.    That is, if the rendering frame rate is lower
  53. than the nominal logic frame rate, the engine will
  54. run the game logic several times before rendering
  55. each frame. Thus, the game logic may actually be
  56. running at tens of kHz for a few frames at a time,
  57. but this doesn't matter, as long as the game logic
  58. code relies entirely on logic time.
  59.    So, do not try to read time using SDL_GetTicks()
  60. or similar in the game logic code! Instead, just
  61. count logic frames, like we did back in the C64 and
  62. Amiga days, where video frames were actually a
  63. reliable time unit. It really works!
  64.  
  65.  
  66. Resampling Distortion
  67. ---------------------
  68. Now, there is one problem with fixed logic frame
  69. rates: Resampling distortion. (The same phenomena
  70. that cause poor audio engines to squeal and feep
  71. when playing back waveforms at certain pitches.)
  72.    The object coordinates generated by the game
  73. logic engine can be thought of as streams of values
  74. describing signals (in electrical engineering/DSP
  75. terms) with a fixed sample rate. Each coordinate
  76. value is one stream.
  77.    Since the logic frame rate is fixed, and the
  78. game logic runs an integer number of times per
  79. rendered frame, what we get is a "nearest point"
  80. resampling from the logic frame rate to the
  81. rendering frame rate. That's not very nice, since
  82. only the last set of coordinates after each run of
  83. logic frames is actually used - the rest are thrown
  84. away!
  85.    What's maybe even worse, especially if the logic
  86. frame rate is low, is that you get new coordinates
  87. only every now and then, when the rendering frame
  88. rate is higher than the logic frame rate.
  89.  
  90.  
  91. Getting Smooth Animation
  92. ------------------------
  93. So, what do we do? Well, given my hint above, the
  94. answer is probably obvious: interpolation! We just
  95. need to replace the basic "nearest sample" method
  96. with something better.
  97.    Resampling is a science and an art in the audio
  98. field, and countless papers have been written on
  99. the subject, most of which are probably totally
  100. incomprehensible for anyone who hasn't got a degree
  101. in maths.
  102.    However, our requirements for the resampling can
  103. be kept reasonably low by keeping the logic frame
  104. rate reatively high (ie in the same order of
  105. magnitude as the expected rendering frame rate) -
  106. and we generally want to do that anyway, to reduce
  107. the game's control latency.
  108.  
  109.  
  110. Chosing An Interpolator
  111. -----------------------
  112. Since the rendering frame rate can vary constantly
  113. in unpredictable ways, we will have to recalculate
  114. the input/output ratio of the resampling filter for
  115. every rendered frame.
  116.    However, using a polynomial interpolator (as
  117. opposed to a FIR resampling filter), we can get
  118. away without actually doing anything special. We
  119. just feed the interpolator the coordinates and the
  120. desired fractional frame time, and get the
  121. coordinates calculated.
  122.    DSP people will complain that a polynomial
  123. resampler (that is, without a brickwall filter, or
  124. oversampling + bandlimited downsampling) doesn't
  125. really solve the whole problem. Right, it doesn't
  126. remove frequencies above Nyqvist of the rendering
  127. frame rate, so those can cause aliasing distortion.
  128. But let's consider this:
  129.    Do we actually *have* significant amounts of
  130. energy at such frequencies in the data from the
  131. game logic? Most probably not! You would have to
  132. have objects bounce around or oscillate at insane
  133. speed to get anywhere near Nyqvist of (that is, 50%
  134. of) any reasonable (ie playable) rendering frame
  135. rate. In fact, we can probably assume that we're
  136. dealing with signals in the range 0..10 Hz. Not
  137. even the transients caused by abrupt changes in
  138. speed and direction will cause visible side
  139. effects.
  140.    So, in this programming example, I'm just using
  141. a simple linear interpolator. No filters, no
  142. oversampling or anything like that. As simple as it
  143. gets, but still an incredible improvement over
  144. "nearest sample" resampling. You can enable/disable
  145. interpolation with the F1 key when running the
  146. example.
  147.  
  148.  
  149. Rendering Sprites
  150. -----------------
  151. In order to cover another animation related FAQ,
  152. this example includes "smart" partial updates of
  153. the screen. Only areas that are affected by moving
  154. and/or animated sprites are updated.
  155.    To keep things simple and not annoyingly non-
  156. deterministic, updates are done by removing all
  157. sprites, updating their positions and animation
  158. frames, and then rendering all sprites. This is
  159. done every frame, and includes all sprites, whether
  160. they move or not.
  161.    So, why not update only the sprites that
  162. actually moved? That would allow for cheap but
  163. powerful animated "backgrounds" and the like.
  164.    Well, the problem is that sprites can overlap,
  165. and when they do, they start dragging each other
  166. into the update loop, leading to recursion and
  167. potentially circular dependencies. A non-recursive
  168. two-pass (mark + render) algorithm is probably a
  169. better idea than actual recursion. It's quite
  170. doable and neat, if the updates are restricted by
  171. clipping - but I'll leave that for another example.
  172. Pretty much all sprites in Fixed Rate Pig move all
  173. the time, so there's nothing to gain by using a
  174. smarter algorithm.
  175.  
  176.  
  177. Efficient Software Rendering
  178. ----------------------------
  179. To make it a bit more interesting, I also added
  180. alpha blending for sprite anti-aliasing and effects.
  181. Most 2D graphics APIs and drivers (and as a result,
  182. most SDL backends) lack h/w acceleration of alpha
  183. blended blits, which means the CPU has to perform
  184. the blending. That's relatively expensive, but
  185. SDL's software blitters are pretty fast, and it
  186. turns out *that's* usually not a problem.
  187.    However, there is one problem: Alpha blending
  188. requires that data is read from the target surface,
  189. modified, and then written back. Unfortunately,
  190. modern video cards handle CPU reads from VRAM very
  191. poorly. The bandwidth for CPU reads - even on the
  192. latest monster AGP 8x card - is on par with that of
  193. an old hard drive. (I'm not kidding!)
  194.    This is why I wanted to demonstrate how to avoid
  195. this problem, by rendering into a s/w back buffer
  196. instead of the h/w display surface. If you're on a
  197. system that supports hardware display surfaces, you
  198. can see the difference by hitting F2 in the game,
  199. to enable/disable rendering directly into VRAM.
  200.    Indeed, SDL can set that up for you, but *only*
  201. if you ask for a single buffered display - and we
  202. do NOT want that! Single buffered displays cannot
  203. sync animation with the retrace, and as a result,
  204. we end up hogging the CPU (since we never block,
  205. but just pump out new frames) and still getting
  206. unsmooth animation.
  207.    Accidentally, this approach of using a s/w back
  208. buffer for rendering mixes very well with partial
  209. update strategies, so it fits right in.
  210.  
  211.  
  212. Smart Dirty Rectangle Management
  213. --------------------------------
  214. The most complicated part of this implementation
  215. is keeping track of the exact areas of the screen
  216. that need updating. Just maintaining one rectangle
  217. per sprite would not be sufficient. A moving sprite
  218. has to be removed, animated and then re-rendered.
  219. That's two rectangles that need to be pushed to the
  220. screen; one to remove the old sprite image, and one
  221. for the new position.
  222.    On a double buffered display, it gets even worse,
  223. as the rendering is done into two alternating
  224. buffers. When we update a buffer, the old sprites
  225. in it are actually *two* frames old - not one.
  226.    I've chosen to implement a "smart" rectangle
  227. merging algorithm that can deal with all of this
  228. with a minimum of support from higher levels. The
  229. algorithm merges rectangles in order to minimize
  230. overdraw and rectangle count when blitting to and
  231. updating the screen. See the file dirtyrects.txt for
  232. details. You can (sort of) see what's going on by
  233. hitting F3 in the game. Here's what's going on:
  234.  
  235.    1. All sprites are removed from the rendering
  236.       buffer. The required information is found
  237.       in the variables that store the results of
  238.       the interpolation.
  239.    2. The dirtyrect table for the display surface
  240.       is swapped into a work dirtyrect table. The
  241.       display surface dirtyrect table is cleared.
  242.    3. New graphic coordinates are calculated, and
  243.       all sprites are rendered into the rendering
  244.       buffer. The bounding rectangles are fed
  245.       into the display surface dirtyrect table.
  246.    4. The dirtyrect table compiled in step 3 is
  247.       merged into the work dirtyrect table. The
  248.       result covers all areas that need to be
  249.       updated to remove old sprites and make the
  250.       new ones visible.
  251.    5. The dirtyrect table compiled in step 4 is
  252.       used to blit from the rendering buffer to
  253.       the display surface.
  254.  
  255.    On a double buffered display, there is one
  256. dirtyrect table for each display page, and there
  257. is (obviously) a page flip operation after step 5,
  258. but other than that, the algorithm is the same.
  259.  
  260.  
  261. Command Line Options
  262. --------------------
  263.  
  264.         -f      Fullscreen
  265.         -s      Single buffer
  266.         <n>     Depth = <n> bits
  267.  
  268.  
  269.         //David Olofson  <david@olofson.net>
  270.