Linked List/SpriteHit Game Frame Work Example

[kevin]

 Linked List / SpriteHit  Game Frame Work Example

   This demo creates a simple game including a mouse controlled player and some randomly moving ball objects. The players objective in the game is to ram the balls and collect some score. Thrilling huh ! :)

   While the game isn't very entertaining to play, the code is designed to demonstrate a couple of PlayBasic forgotten features.  Namely Linked Type lists and SpriteHIT / SpriteClass based collisions.

   The game uses linked type lists to manage the alien ships/ball objects.  The benefit of using a list, rather than an array to house our objects, is that you can do away with INDEXS,  and let PB manage the list transparently.   This does mean we need to change how we add/delete and step through the list though.  But it's not rocket science.  To add new objects to the list we use the NEW operator, to delete them with simply NULL a link and to iterate through a list, we use a special the  FOR EACH  OBJECTNAME() / NEXT looping structure.    

  Sprite Collision is particular problem that many new PB programmers struggle with.  While traditionally programmers would roll their own collision code to manually find  intersections between objects (SpriteOverlap).  There are other approaches.   Namely via using SpriteHit and reserve look ups.  Which flips the problems on it's head.  

  The difference is probably best described by hacking through an example.   So lets imagine we have a single player and list of 10 bad guys.  


 Method #1) SpriteOverlap

  To detect collisions between the players sprite any bad guys using SpriteOverlap, means we individually comparing the Player sprite to each bad guy sprite.    To do this,  we  need to traverse through our Bad list/array comparing  the player  to BadGuy[1],  BadGuy[2] etc etc up to BadGuy[10].    So if there are 10 bad guys then we end up called SpriteOverLap 10 times,   Regardless of whether the players hit a bad guy or not..    So clearly under this approach the more bad guys there are,  the more loop/comparison overhead we run into.    This is further compounded when we start doing nested comparisons.  I.e.  Checking the groups of player bullets against a group of bad guys.   For example,  If there are 10 bullets and 10 bad guys, then we're manually calling SpriteOverlap 10*10 times.   If there's 20 bullets and 50 bad guys then that 20*50=1000 calls.   On a modern machines you'd probably get away with it,  but not upon old clunkers.  



 Method#2) SpriteHit

 To detect collisions using sprite hit between the player and the bad guys, we call the SpriteHit function, passing it the players Sprite (the one to find impacts against), the starting sprite where it should started searching for impacts from and the Collision Class bits.     If SpriteHit detects a collision, the function returns the sprite index/handle that was intersected.

 Now there's the problem most people seem to run into, this gives us the sprite, but if doesn't give us what position in the bad guy list/array that this sprite was attached to.   So how can work out how many hit points, or the score of killing this bad guy ?     Well, you could scan through the bad guy list and find the one that is using this sprite and delete it, or subtract damage from the player easy enough.    While this is less work for the PB runtime than method #1 above,   Couldn't we just store the array index/pointer inside the sprite as a sprite local data ?  This way,  when a collision is detected,  we can look up what bag guy it belongs to instantly.   Which is how this demo code bellow works.

 If we expand this demo further and add bullets for the player and bad guys,  then we can even detect collisions between groups of opposing objects in one hit.  Simply by assigning each character type different collision class bits.     In this demo, the Player uses collision class (bitmask) of 1 and aliens use a bitmask of 2.    If we expanded this and added a bullets class to the player(s) of 4 say and bullet class to the bad guy bullets of  8.   Then using SpriteHit we can now detect any collision between the player and the bad guys + their bullets in one call by using a collision class of (2+8) (Bad guy class + Bad Guy Bullet Class).   While ignoring collisions between other players and other players bullets.


 Which might look a bit like this.   [Pseudo code]

Code Select Expand



 SpriteThatWasHit=SpriteHit(PlayerSprite, GetFirstSpriet(),  2+8)

  While SpriteThatWasHit>0

            ; Get the Next Sprite in the Sprite List
            NextSpriteAfterHitSprite=GetNextSprite(SpriteThatWasHit)

             ; Get the Collision Class of this sprite to work out if we hit a Bad guy or a Bag guy bullet
             Select GetSpriteCollisionClass(SpriteThatWasHit)

                   case  2
                             ; Player hit a bad guy..  subtract damage

                    case 8
                             ; PLayer hit a bad guy bullet.  
              EndSelect

             ; Check if the player is dead from this impact ?
            if Player=dead then exitwhile
   
            ; Check if the Next sprite exists or not, is not exit the loop.  (Since SpriteThatWasHit was the last sprite in the sprite list)
            if GetSpriteStatus(NextSpriteAfterHitSprite)=false then exitWhile
         

       ; If the player isn't dead, then keep checking  any more hits on the player  ?
        SpriteThatWasHit=SpriteHit(PlayerSprite, NextSpriteAfterHitSprite,  2+8)

   EndWhile









Compatible with PB1.63  &  PB1.7x

PlayBASIC Code: [Select]

` *=----------------------------------------------------------------------=*
`                        >> Basic Game Frame Work <<
`
`                            by Kevin Picone
`
`         (c) copyright 2008 Kevin Picone, All Rights Reserved
` *=----------------------------------------------------------------------=*
`
`     This demo creates a simple game including a mouse controlled player
` and some randomly moving ball objects. The players objective in the game
` is to ram the balls  and collect some score. Thrilling huh ! :)

`     While the game isn't very entertaining to play, the code is designed
` to demonstrate a couple of PlayBasic forgotten features.  Namely Linked
` Type lists and SpriteHIT / SpriteClass based collisions.
`
` *=----------------------------------------------------------------------=*

; Tell PB to limit to program to a max of 60 frames per second or less   
   Setfps 60
   

; Declare some constants to represent the two states objects in the
; game can be.  ALIVE or DEAD
   Constant Alive   =1
   Constant Dead   =2
   


; declare the tSHIP object type
   Type tShip
      Status         ; This objects current Status (ALIVE or DEAD)

      Speed#         ; Speed of object
      Direction#      ; Direction this object is moving

      Sprite         ; the sprite this ship uses for it's on screen representation

      HitPoints      ; number of hits required to kill this ship
      KillScore      ; number of points awarded to player for killing this ship
   EndType


; declare the ship as linked list 
   Dim Ship as tShip list
   

   
; declare the Players type, so we can keep all the players fields together
   Type tPlayer
      Status
      Score
      Level      
      Sprite   
   Endtype

; declare the player typed variable for easy global access
   Dim Player as tplayer


; Init the player 
   InitPlayer()   


` *=----------------------------------------------------------------------=*
`                         >> MAIN LOOP <<
` *=----------------------------------------------------------------------=*

   Do
      
      ; clear the screen to black
         Cls rgb(0,0,0)

         if Spacekey()=true or timer()>AddObjectTime
            AddShip(rnd(800),rnd(600))
            AddObjectTime=Timer()+rndrange(100,400)
         endif         

      ; Update/Process all of the Ships in the ship list
         UpdateShips()

      ; Process the player
         UpdatePLayer()

      ; Draw the sprite scene   
         DrawAllsprites


      ; Draw the score for the player
         If Player.Status
            CenterText 400,20,"SCORE:"+digits$(Player.Score,6)
         endif

      ; Show the player the screen   
      Sync

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






` *=----------------------------------------------------------------------=*
`                            >> Init Player <<
` *=----------------------------------------------------------------------=*

Function InitPlayer()
   
   PLayer.Status=Alive
   PLayer.Score=0
   PLayer.level=1
   

   ; Make the Image for the player
   img=MakeParticle(50,rgb(100,130,210))   


   ; Make srpite
   Spr=NewSprite(0,0,img)
   SpriteDRawMode Spr,2
   CenterSpriteHandle Spr         ; center the sprite handles around it's current image
   SpriteCollisionMode Spr,6      ; Set this sprite to pixel perfect collision
   SpriteCollisionClass Spr,  1       ; Each object type has it's own class. Allowing PB to screen for impacts     

   ; Remember what sprite this player uses
   Player.Sprite=spr
   
EndFunction



` *=----------------------------------------------------------------------=*
`                            >> Update Player <<
` *=----------------------------------------------------------------------=*


Function  UpdatePlayer()

   ; declare a typed pointer for accessing any SHIPS the players might have hit this update.   
   Dim HitShip as tShip POinter


   ; Check if the player is actually alive ?                  
   if PLayer.Status=Alive

         ; Get the Sprite this player is using.

Login required to view complete source code

[thaaks]

This is a great example and should help many people to get their objects and collisions organized!

Linked lists are definitely one of the best features of PlayBasic that can really simplify your life! Dynamically growing and shrinking self organizing lists.

I would love to know how much faster usage of SpriteHit is compared to SpriteOverlap. Do you have any numbers?

What happens inside of SpriteHit()? Does it traverse the whole sprite list? Or does it store separate lists for each collision classes?
Does the sprite list "know" that there is currently no sprite of collision class X in the game? Does SpriteHit() consider the Z order of the sprites? What if I delete the Sprite that is currently checked or delete the Sprite that hit the checked sprite and still continue calling SpriteHit()?

Anyway, two thumbs up for these features and this example  8)

Cheers,
Tommy

[kevin]

I would love to know how much faster usage of SpriteHit is compared to SpriteOverlap. Do you have any numbers?

   And what would be a meaningful number ?   Too many factors, such as image types, size, rotation, scaling, comparison mode etc  


SpriteHit VS SpritesOverlap Speed test

PlayBASIC Code: [Select]

   Setfps 60


   ; Simulate the number of nested collision calls  (ie bullets to aliens)
   Nests=10

   ; Max of sprites in test scene
   MaxSprites=250

   ; spawn test sprites.
   For lp=1 to MaxSprites
       MakeSprite(rnd(800),rnd(600),50)
   next


   TestSprite=MakeSprite(x#,y#,50)

   Do
         Cls rgb(30,40,5)

         inc frames

         PositionSprite TestSprite,mousex(),mousey()
         DrawOrderedSprites

         hits=0
         T=timer()
            For Nest=1 to Nests
               For Spr=1 to MaxSprites         
                     HitS=Hits+SpritesOverlap(TestSprite,Spr)         
               next
            next
         tt1#=tt1#+(timer()-t)
         Print "Average Sprite Overlap Time:"+str$(tt1#/frames)
         print "Calls:"+str$(Nests*MaxSprites)
         print "Hits:"+str$(hits)
         print ""


         hits=0
         T=timer()
            For Nest=1 to Nests
               HitSprite=SpriteHit(TestSprite,GetFirstSprite(),2)
               While HitSprite>0
                     NextSprite=GetNextSprite(HitSprite)
                     if NextSprite<1 then exit         ; Just make sure the next sprite isn't the end of the list
                                                      ; which can cause infinite loops in old editions of PB   
                     hits=hits+1
                     HitSprite=SpriteHit(TestSprite,NextSprite,2)
               EndWhile
            next
         tt2#=tt2#+(timer()-t)
         Print "Average Sprite Hit Time:"+str$(tt2#/frames)
         print "Calls:"+str$(Hits*Nests)
         print "Hits:"+str$(hits)
         print ""
         

      Sync      
   loop



` *=----------------------------------------------------------------------=*
`                   >> Make Generic Sprite With Image <<
` *=----------------------------------------------------------------------=*

   
Function MakeSprite(x#,y#,z#)
   img=MakeParticle(rndrange(16,64),rndrgb())   
   Spr=NewSprite(x#,y#,img)
   CenterSpriteHandle Spr
   PositionSpriteZ spr,z#

   SpriteDrawMode Spr,2
   SpriteCollisionMode Spr,6
   SpriteCollisionClass Spr,2

   
EndFunction spr

` *=----------------------------------------------------------------------=*
`                            >> Make particle Image << 
` *=----------------------------------------------------------------------=*

Function MakeParticle(Size,Col)
      ThisImage=NewFXImage(Size,Size)    
      RenderPhongImage  ThisImage,Size/2,Size/2,col,255,260/(size/2)
EndFunction ThisImage

What happens inside of SpriteHit()? Does it traverse the whole sprite list? Or does it store separate lists for each collision classes?

   Nothing special, it just steps through the list.   It's how it manages the media internally that gives a better yield, among other things.

Does SpriteHit() consider the Z order of the sprites?

   Nope, PB is 2D.

What if I delete the Sprite that is currently checked or delete the Sprite that hit the checked sprite and still continue calling SpriteHit()

    Sprites (and all media in PB) are connected in through linked lists internally. If you delete a hit sprite (before reading the next sprite) and then feed the original handle back into the SpriteHIT() you effectively telling PB to access null data.  How PB reacts, depends upon the version.    Old versions, pre 1.64  allow it and seems to screen the look up as harmless in debug runtimes, but will probably crash in release runtimes.  New versions (PB1.64 and above)  will pop an error.