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.
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:
, consider the following:
- How the sprites are to be drawn
- Performance
Drawing
The first item can no longer use the method developed in the first part of
this series (see 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:
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:
- If the bounding rectangles do not overlap, then the test fails.
- Calculate the union of the bounding rectangles
- 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.
- 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.
