Sprites and Animation Part 4

From EDM2
Jump to: navigation, search
Sprites and Animation / Part
1 2 3 4

Written by Larry Salomon Jr.

Introduction

And when you had thought that this topic had been exhaustively treated, here it comes again. This final article of the series will discuss the necessary changes to implement z-ordering within the sprite library; these changes will be discussed using the Common/2 library. Have no fear, however; as promised, the source for the module has been included with this article.

Voodoo Chili

(Slight Return)

(Yes, the misspelling was intended.)

When you think of z-ordering, you think of layering. The problem of designing and implementing z-ordering was approached with the latter term in mind, since it helps ease the transition from the abstract to the codable. Consider the algorithm for drawing a sprite, given the concept of sprite layering:

  1. Draw the background
  2. Draw all sprites below the sprite to be drawn (the current sprite), if and only if they overlap the bounding rectangle of the current sprite.
  3. Draw the current sprite.
  4. Draw all sprites above the current sprite, if and only if they overlap the bounding rectangle of the current sprite.

Simple enough, eh? Before you roll up your sleeves to code this yourself , consider the following:

  1. How the sprites are to be drawn
  2. Performance

Drawing

The first item can no longer use the method developed in the first part of this series (see [../0205/sprites.html EDM/2 - Volume 2, Issue 5]), since that blatently overpaints the bounding rectangle of the current sprite with the corresponding section of the background, effectively wiping out the drawing of the underlying sprites noted in step 2 of the drawing algorithm. Instead, we must draw each sprite sans background, in order to preserve the sprites below the current sprite. To get the background, then, we draw it as a separate step.

Of course, this requires modification to our drawing routines, as we will see shortly.

Performance

Then, there is the issue of performance. Given the worst-case scenario, suppose all sprites are of the maximum size, and they all overlap the current sprite. When we have to draw the current sprite, if we completely (that's the operative word) draw each of the overlapping sprites, our performance drops through the floor. Instead, we should calculate which portion of each overlapping sprite is actually overlapping and draw only that. This requires more thought up front, but saves us much in the long run.

Coding the Changes

Before any coding can take place, we must understand how z-ordering will be represented in the data structures. The easiest way, in my opinion, is by changing the interpretation of the current data structures, i.e. use the array of sprites in the playground data structure (ahsSprites). The handle in index 0 is the bottom-most sprite, while the handle in the highest index is the top-most sprite. This is nice, because it enables us to use simple for-loops when enumerating the sprites by z-order.

There are three routines which have changed to implement z-ordering: drawSpriteAt(), CmnSprDrawSprite(), and CmnSprSetSpritePosition(). We look at each of these in detail below.

drawSpriteAt()

This workhorse function of the drawing routines now accepts the rectangle of the sprite to be drawn, assuming a lower-left corner of (0,0).

static BOOL drawSpriteAt(HPS hpsDraw,
                         HCSSPRITE hsSprite,
                         PSIZEL pszlPlay,
                         PPOINTL pptlSprite,
                         PRECTL prclSprite)
//-------------------------------------------------------------------------
// This function draws the sprite at the specified position.  It is assumed
// that the background has already been drawn into hpsDraw before this
// function is called.
//
// Input:  hpsDraw - handle of the presentation space to draw in
//         hsSprite - handle of the sprite to draw
//         pszlPlay - points to the size of hpsDraw.  If NULL, the size
//                    of the playground is used.
//         pptlSprite - points to the point specifying the position.  If
//                      NULL, the sprite's current position is used.
//         prclSprite - points to the rectangle within the sprite to draw,
//                      i.e. a rectangle bounded by (0,0)-(cx,cy) which
//                      is added to the sprite's position to determine
//                      how much of the sprite is to be drawn.  If NULL,
//                      the entire sprite is drawn.
// Returns:  TRUE if successful, FALSE otherwise
//-------------------------------------------------------------------------

The change in the code is actually quite simple. Instead of assuming (0,0) as the lower left corner and (cx,cy) as the upper right corner, we use the values provided (if provided).

{
   SIZEL szlUsePlay;
   POINTL ptlUseSpr;
   RECTL rclUseSpr;
   POINTL aptlPoints[4];

   if ((!hsSprite->hpgPlay->bUpdate) || (!hsSprite->bVisible)) {
      return TRUE;
   } /* endif */

   //----------------------------------------------------------------------
   // Initialize the local variables with either what was passed in or
   // the defaults as noted above in the function prologue
   //----------------------------------------------------------------------
   if (pszlPlay==NULL) {
      CmnSprQueryPlaygroundSize(hsSprite->hpgPlay,&szlUsePlay);
   } else {
      szlUsePlay=*pszlPlay;
   } /* endif */

   if (pptlSprite==NULL) {
      ptlUseSpr=hsSprite->ptlPos;
   } else {
      ptlUseSpr=*pptlSprite;
   } /* endif */

   if (prclSprite==NULL) {
      rclUseSpr.xLeft=0;
      rclUseSpr.yBottom=0;
      rclUseSpr.xRight=hsSprite->bmihMask.cx;
      rclUseSpr.yTop=hsSprite->bmihMask.cy;
   } else {
      rclUseSpr=*prclSprite;
   } /* endif */

   //----------------------------------------------------------------------
   // Convert the xRight/yTop pair to the size of the sprite
   //----------------------------------------------------------------------
   rclUseSpr.xRight-=rclUseSpr.xLeft;
   rclUseSpr.yTop-=rclUseSpr.yBottom;

   aptlPoints[0].x=ptlUseSpr.x+rclUseSpr.xLeft;
    aptlPoints[0].y=ptlUseSpr.y+rclUseSpr.yBottom;
    aptlPoints[1].x=aptlPoints[0].x+rclUseSpr.xRight-1;
   aptlPoints[1].y=aptlPoints[0].y+rclUseSpr.yTop-1;
   aptlPoints[2].x=rclUseSpr.xLeft;
    aptlPoints[2].y=rclUseSpr.yBottom;
    aptlPoints[3].x=aptlPoints[2].x+rclUseSpr.xRight;
    aptlPoints[3].y=aptlPoints[2].y+rclUseSpr.yTop;

   if (clipBltPoints(hsSprite->habAnchor,aptlPoints,&szlUsePlay)) {
      //-------------------------------------------------------------------
      // Blit the mask and then the bitmap
      //-------------------------------------------------------------------
      GpiWCBitBlt(hpsDraw,
                  hsSprite->hbmMask,
                  4,
                  aptlPoints,
                  ROP_SRCAND,
                  BBO_IGNORE);

      GpiWCBitBlt(hpsDraw,
                  hsSprite->hbmBitmap,
                  4,
                  aptlPoints,
                  ROP_SRCPAINT,
                  BBO_IGNORE);
   } /* endif */

   return TRUE;
}

CmnSprDrawSprite()

This code no longer is so concise, although it still is rather simple. We do not simply call drawBackAt(), drawSpriteAt(), and return; now, we must loop through the sprites, drawing the intersecting rectangles of each.

Note: the intersecting rectangle of the current sprite with itself is an identity function, so no special checking needs to be performed.

SPRERROR EXPENTRY CmnSprDrawSprite(HPS hpsDraw,HCSSPRITE hsSprite)
//-------------------------------------------------------------------------
// This function draws a sprite
//
// Input:  hpsDraw - handle to the HPS to draw the sprite in
//         hsSprite - handle to the sprite
// Returns:  SPR_ERR_NOERROR if successful, SPR_ERR_* constant otherwise
//-------------------------------------------------------------------------
{
   USHORT usSemAction;
   RECTL rclSprite;
   ULONG ulIndex;
   HCSSPRITE hsLayer;
   RECTL rclLayer;
   RECTL rclInter;

   if (queryHandle(hsSprite)!=QH_HCSSPRITE) {
      return SPR_ERR_BADHANDLE;
   } /* endif */

   usSemAction=accessSem((PCMNHANDLE)hsSprite,ACCSEM_SET);

   if (hsSprite->hpgPlay==NULL) {
      accessSem((PCMNHANDLE)hsSprite,usSemAction);
      return SPR_ERR_HASNOPLAYGROUND;
   } /* endif */

   if ((!hsSprite->bVisible) || (!hsSprite->hpgPlay->bUpdate)) {
      accessSem((PCMNHANDLE)hsSprite,usSemAction);
      return SPR_ERR_NOERROR;
   } /* endif */

   CmnSprQuerySpriteRect(hsSprite,&rclSprite);

   rclSprite.xRight++;
   rclSprite.yTop++;

   drawBackAt(hpsDraw,hsSprite->hpgPlay,NULL,NULL,&rclSprite);

   rclSprite.xRight--;
   rclSprite.yTop--;

   for (ulIndex=0; ulIndex<hsSprite->hpgPlay->ulNumMembers; ulIndex++) {
      hsLayer=hsSprite->hpgPlay->ahsSprites[ulIndex];

      CmnSprQuerySpriteRect(hsLayer,&rclLayer);

      WinIntersectRect(hsSprite->hpgPlay->habAnchor,
                       &rclInter,
                       &rclSprite,
                       &rclLayer);

      if (!WinIsRectEmpty(hsSprite->hpgPlay->habAnchor,&rclInter)) {
         rclInter.xLeft-=rclLayer.xLeft;
         rclInter.yBottom-=rclLayer.yBottom;
         rclInter.xRight-=rclLayer.xLeft;
         rclInter.yTop-=rclLayer.yBottom;

         rclInter.xRight++;
         rclInter.yTop++;

         drawSpriteAt(hpsDraw,hsLayer,NULL,NULL,&rclInter);
      } /* endif */
   } /* endfor */

   accessSem((PCMNHANDLE)hsSprite,usSemAction);
   return SPR_ERR_NOERROR;
}

It should be obvious that the real work is done in the loop body. If there is an intersection of bounding rectangles, a call to drawSpriteAt() is made.

CmnSprSetSpritePosition()

Of the three functions, this one has the most new code, but that isn't saying much, since the code up to this point hasn't been very difficult to understand. If you'll remember, this function takes one of two paths, depending on whether the new position overlaps the old. Fortunately for us, in the original code, one of the paths called CmnSprDrawSprite(), so no change is needed in that case.

SPRERROR EXPENTRY CmnSprSetSpritePosition(HPS hpsDraw,
                                          HCSSPRITE hsSprite,
                                          PPOINTL pptlNew)
//-------------------------------------------------------------------------
// This function changes the position of the sprite.  This function is
// optimized so that, if the rectangle bounding the sprite at the new
// position overlaps the old, only one "bit blit" to the specified HPS
// is done, eliminating flicker.
//
// Input:  hpsDraw - handle to the HPS to draw the sprite in once it is
//                   moved
//         hsSprite - handle to the sprite
// Returns:  SPR_ERR_NOERROR if successful, SPR_ERR_* constant otherwise
//-------------------------------------------------------------------------
{
   USHORT usSemAction;
   SIZEL szlPlay;
   SIZEL szlWork;
   RECTL rclOld;
   RECTL rclNew;
   RECTL rclUnion;
   RECTL rclSrc;
   RECTL rclDest;
   ULONG ulIndex;
   HCSSPRITE hsLayer;
   RECTL rclLayer;
   RECTL rclInter;
   POINTL ptlWork;
   POINTL aptlPoints[4];

   if (queryHandle(hsSprite)!=QH_HCSSPRITE) {
      return SPR_ERR_BADHANDLE;
   } /* endif */

   usSemAction=accessSem((PCMNHANDLE)hsSprite,ACCSEM_SET);

   if (hsSprite->hpgPlay==NULL) {
      accessSem((PCMNHANDLE)hsSprite,usSemAction);
      return SPR_ERR_HASNOPLAYGROUND;
   } /* endif */

   if ((hsSprite->bVisible) && (hsSprite->hpgPlay->bUpdate)) {
      szlWork.cx=MAX_SPRITE_CX*2;
      szlWork.cy=MAX_SPRITE_CY*2;

      CmnSprQueryPlaygroundSize(hsSprite->hpgPlay,&szlPlay);

      CmnSprQuerySpriteRect(hsSprite,&rclOld);
      hsSprite->ptlPos=*pptlNew;
      CmnSprQuerySpriteRect(hsSprite,&rclNew);

      WinUnionRect(hsSprite->habAnchor,&rclUnion,&rclOld,&rclNew);

      if ((rclUnion.xRight-rclUnion.xLeft>MAX_SPRITE_CX*2) ||
          (rclUnion.yTop-rclUnion.yBottom>MAX_SPRITE_CY*2)) {

         rclSrc.xLeft=rclOld.xLeft;
         rclSrc.yBottom=rclOld.yBottom;
         rclSrc.xRight=rclSrc.xLeft+hsSprite->bmihBitmap.cx;
         rclSrc.yTop=rclSrc.yBottom+hsSprite->bmihBitmap.cy;

         drawBackAt(hpsDraw,hsSprite->hpgPlay,NULL,NULL,&rclSrc);

         CmnSprDrawSprite(hpsDraw,hsSprite);
      } else {
         rclSrc=rclUnion;
         rclSrc.xRight++;
         rclSrc.yTop++;

         rclDest.xLeft=0;
         rclDest.yBottom=0;
         rclDest.xRight=rclUnion.xRight-rclUnion.xLeft;
         rclDest.yTop=rclUnion.yTop-rclUnion.yBottom;

         drawBackAt(hsSprite->hpgPlay->hpsWork,
                    hsSprite->hpgPlay,
                    &rclDest,
                    &szlWork,
                    &rclSrc);

         for (ulIndex=0; ulIndex<hsSprite->hpgPlay->ulNumMembers; ulIndex++) {

            hsLayer=hsSprite->hpgPlay->ahsSprites[ulIndex];

            CmnSprQuerySpriteRect(hsLayer,&rclLayer);

            WinIntersectRect(hsSprite->hpgPlay->habAnchor,
                             &rclInter,
                             &rclUnion,
                             &rclLayer);

            if (!WinIsRectEmpty(hsSprite->hpgPlay->habAnchor,&rclInter)) {
               ptlWork.x=hsLayer->ptlPos.x-rclUnion.xLeft;
               ptlWork.y=hsLayer->ptlPos.y-rclUnion.yBottom;

               rclInter.xLeft-=rclLayer.xLeft;
               rclInter.yBottom-=rclLayer.yBottom;
               rclInter.xRight-=rclLayer.xLeft;
               rclInter.yTop-=rclLayer.yBottom;

               rclInter.xRight++;
               rclInter.yTop++;

               drawSpriteAt(hsSprite->hpgPlay->hpsWork,
                            hsLayer,
                            &szlWork,
                            &ptlWork,
                            &rclInter);
            } /* endif */
         } /* endfor */

         //----------------------------------------------------------------
         // GpiBitBlt is non-inclusive on source AND target
         //----------------------------------------------------------------
         aptlPoints[0].x=rclUnion.xLeft;
         aptlPoints[0].y=rclUnion.yBottom;
         aptlPoints[1].x=rclUnion.xRight+1;
         aptlPoints[1].y=rclUnion.yTop+1;
         aptlPoints[2].x=0;
         aptlPoints[2].y=0;
         aptlPoints[3].x=rclUnion.xRight-rclUnion.xLeft+1;
         aptlPoints[3].y=rclUnion.yTop-rclUnion.yBottom+1;

         if (clipBltPoints(hsSprite->habAnchor,aptlPoints,&szlPlay)) {
            GpiBitBlt(hpsDraw,
                      hsSprite->hpgPlay->hpsWork,
                      4,
                      aptlPoints,
                      ROP_SRCCOPY,
                      BBO_IGNORE);
         } /* endif */
      } /* endif */
   } else {
      hsSprite->ptlPos=*pptlNew;
   } /* endif */

   accessSem((PCMNHANDLE)hsSprite,usSemAction);
   return SPR_ERR_NOERROR;
}

As with CmnSprDrawSprite(), the real work is done in the loop; however, since there is an offset from the bottom of the workspace, the code is slightly different than the previous loop.

New Functions

So, now we have this fancy capability in our library, but we have no way of changing the z-order of a sprite once it has been established (save removing all of the sprites from the playing and re-adding them in the desired order). To alleviate this, two new functions were added which simply operate on the ahsSprites array of the playground. The code is presented below but will not be discussed.

SPRERROR EXPENTRY CmnSprSetLayering(HPS hpsDraw,HCSSPRITE hsSprite,LONG lPos)

//-------------------------------------------------------------------------
// This function sets the z-order of a sprite.
//
// Input:  hpsDraw - handle to the HPS to make the updates in.
//         hsSprite - handle to the sprite whose z-order is to be changed
//         lPos - an absolute layer number (0 to MAX_SPRITES-1) or an
//                SSL_* constant.
// Returns:  SPR_ERR_NOERROR if successful, SPR_ERR_* constant otherwise
//-------------------------------------------------------------------------
{
   USHORT usSemAction;
   SPRERROR seError;
   LONG lOld;
   LONG lNew;
   LONG lOldDx;
   LONG lNewDx;
   HCSSPRITE ahsCopy[MAX_SPRITES];
   ULONG ulIndex;

   if (queryHandle(hsSprite)!=QH_HCSSPRITE) {
      return SPR_ERR_BADHANDLE;
   } /* endif */

   usSemAction=accessSem((PCMNHANDLE)hsSprite,ACCSEM_SET);

   if (hsSprite->hpgPlay==NULL) {
      accessSem((PCMNHANDLE)hsSprite,usSemAction);
      return SPR_ERR_HASNOPLAYGROUND;
   } /* endif */

   seError=CmnSprQueryLayering(hsSprite,&lOld);
   if (seError!=SPR_ERR_NOERROR) {
      return seError;
   } /* endif */

   lNew=lOld;

   switch (lPos) {
   case SSL_TOP:
      lNew=hsSprite->hpgPlay->ulNumMembers-1;
      break;
   case SSL_BOTTOM:
      lNew=0;
      break;
   case SSL_UP:
      lNew=lOld+1;
      break;
   case SSL_DOWN:
      lNew=lOld-1;
      break;
   default:
      lNew=lPos;
   } /* endswitch */

   if ((lNew<0) || (lNew>hsSprite->hpgPlay->ulNumMembers-1)) {
      accessSem((PCMNHANDLE)hsSprite,usSemAction);
      return SPR_ERR_BADLAYER;
   } /* endif */

   if ((lNew==lOld) || (hsSprite->hpgPlay->ulNumMembers==1)) {
      accessSem((PCMNHANDLE)hsSprite,usSemAction);
      return SPR_ERR_NOERROR;
   } /* endif */

   memset(ahsCopy,0,sizeof(ahsCopy));
   ahsCopy[lNew]=hsSprite->hpgPlay->ahsSprites[lOld];

   lOldDx=0;
   lNewDx=0;

   for (ulIndex=0; ulIndex<hsSprite->hpgPlay->ulNumMembers-1; ulIndex++) {
      if (ulIndex==lOld) {
         lOldDx=1;
      } else
      if (ulIndex==lNew) {
         lNewDx=1;
      } /* endif */


ahsCopy[ulIndex+lNewDx]=hsSprite->hpgPlay->ahsSprites[ulIndex+lOldDx];

   } /* endfor */

   memcpy(hsSprite->hpgPlay->ahsSprites,ahsCopy,sizeof(ahsCopy));

   CmnSprDrawSprite(hpsDraw,hsSprite);

   accessSem((PCMNHANDLE)hsSprite,usSemAction);
   return SPR_ERR_NOERROR;
}

SPRERROR EXPENTRY CmnSprQueryLayering(HCSSPRITE hsSprite,PLONG plPos)
//-------------------------------------------------------------------------
// This function sets the z-order of a sprite.
//
// Input:  hsSprite - handle to the sprite whose z-order is to be queried
//         plPos - points to the variable to receive the layer number.
// Output:  plPos - points to the layer number (0 to MAX_SPRITES-1).
// Returns:  SPR_ERR_NOERROR if successful, SPR_ERR_* constant otherwise
//-------------------------------------------------------------------------
{
   USHORT usSemAction;
   ULONG ulIndex;

   if (queryHandle(hsSprite)!=QH_HCSSPRITE) {
      return SPR_ERR_BADHANDLE;
   } /* endif */

   usSemAction=accessSem((PCMNHANDLE)hsSprite,ACCSEM_SET);

   if (hsSprite->hpgPlay==NULL) {
      accessSem((PCMNHANDLE)hsSprite,usSemAction);
      return SPR_ERR_HASNOPLAYGROUND;
   } /* endif */

   for (ulIndex=0; ulIndex<hsSprite->hpgPlay->ulNumMembers; ulIndex++) {
      if (hsSprite->hpgPlay->ahsSprites[ulIndex]==hsSprite) {
         *plPos=ulIndex;
         return SPR_ERR_NOERROR;
      } /* endif */
   } /* endfor */

   accessSem((PCMNHANDLE)hsSprite,usSemAction);
   return SPR_ERR_NOTFOUND;
}

Collision Detection

(This section describes the concepts of collision detection, although no code has yet been written to implement this.)

Collision detection, a necessary function in most video games, is the method by which it is determined if two objects are touching at any point. Consider the following two sprites: sprites1.gif sprites2.gif

It is obvious that this is far more complicated a matter than simply checking the bounding rectangles, since the object drawn within will probably not encompass the entire bounding rectangle, nor will they be as regularly shaped as the examples above.

Et Tu, Brute?

As in most Computer Science problems, brute force could be applied here to solve this problem:

  1. If the bounding rectangles do not overlap, then the test fails.
  2. Calculate the union of the bounding rectangles
  3. For each pel in the union rectangle, check each sprite to see if it has a pel in that position also. If we find one, the test succeeds.
  4. The test fails if we reach this point.

While this algorithm would probably work, the performance is O(n*n), which is unacceptable for programs - such as video games - where pseudo-real-time response is necessary. However, this approach is not entirely without its merits...

Consider step 3 in the pseudo-code above, since that is the performance-eater. If we could reduce the CPU requirements of this step to below some threshold that we define, the algorithm becomes quite usable. Since the problem lies in our double-loop plus system call, that should be our area of concentration.

The first step in solving this is to figure out how we would implement the step in its unmodified state. The only fault-proof way that I could think of was to use the masks of each sprite, since they are not contaminated by the background bitmap. By adjusting our indices to allow for offsets of each mask relative to the positions of the corresponding sprites, we can easily determine if the sprite has a pel at any given position or not.

Some of you might already see the solution.

Using the monochrome property of the masks, we could speed up this algorithm considerable if we call GpiBitBlt() to copy each of the masks into a workspace and then check for the intersection of the two (black pels, if you do not remember. See the first article in this series.). However, the double loop still keeps the performance at O(n*n), although the prefixing coefficient is no longer as large.

The final step is to convert this to a linear operation, instead of a two-dimensional one. This is done by calling GpiQueryBitmapBits() and then using memchr() to search for any byte that is non-255. (If you don 't understand that, remember that we have a monochrome bitmap, so each white pel is represented by a set bit. All white therefore equates to 255, but we are looking for a single black pel.) Since monochrome bitmaps take very little memory and since the library has an inherent maximum size for sprites, we can allocate the memory to hold the bitmap bits during the CmnSprCreatePlayground() call and use the workspace that we are already allocating (hpsWork) for the GpiBitBlt() call.

If you are impatient, you can code this before I do.

Summary

In this final article, we looked at how z-ordering can and is implemented in our sprite library. If you get version 1.6.0 of the Common/2 library (now on ftp.cdrom.com) and compile the included I-495 sample to use this library, you will find that the performance does not suffer noticably.

Additionally, we looked into collision detection and how it could be implemented with maximum performance; this will undoubtedly be added to a future version of Common/2 to ease the burden of those inspired writers who wish to translate their favorite "shoot-em up" game to their favorite operating system.