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]
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
[pbcode]
` *=----------------------------------------------------------------------=*
` >> 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.
PlayerSpr=Player.sprite
; position player sprite at the mouse position.
PositionSprite PlayerSpr,MouseX(),mousey()
; Check for Collision between the player and the Alien Ship Sprite Class
HitSprite=SpriteHit(PLayerSPr,GetFirstSprite(), 2) ; Check against sprite list with a collision class (mask) of 2
; While a collision occurs, flash the sprite, subtract the hitpoints and then continue on checking for more collisions (if any)
While HitSprite>0
;Get the Next Sprite after the one that was sprite
NextSprite=GetNextSprite(HitSprite)
; grab the object pointer from within the sprite. This pointer allows us to access the associated Ship objects properties
; without having to scan through the ship list to find it
HitShip=GetSpriteLocalInt(HitSprite,0)
; Change drawmode so when it's next drawn at this of this frame we SEE the impact !
SpriteDrawMode HitSprite,2+4096
SpriteAlphaAddColour HitSprite,rndrgb()
; Subtract one from this objects hit points counter
HitShip.HitPoints=HitShip.HitPoints-1
; Check if the hitpoints is lower than 1, if so, kill this sprite and award the player some score.
if HitShip.HitPoints<1
; add Score from this ship alien to the player
player.score=player.score+HitShip.KillScore
; Tag this object as dead. This method ensures the player sees the collision, if we delete it here, then player
; only ever sees the object _before_ it collided (the previous refresh of the screen).
HitShip.Status=Dead
endif
; check if this next sprite is legal it not, if not we're at the end of the sprite list so we should now exit the While/Loop
if GetSpriteStatus(NextSprite)=False then ExitWhile
; if it's not the end, then we check for any more impacts upon this player
HitSprite=SpriteHit(PLayerSPr,NextSprite, 2) ; Check against sprite list with a collision class (mask) of 2
EndWhile
EndIF
EndFunction
` *=----------------------------------------------------------------------=*
` >> Add Ship <<
` *=----------------------------------------------------------------------=*
Function AddShip(x#,y#)
; Add a new ship to the SHIP list
Ship = new tShip
; tag this object as alive
Ship.Status=Alive
; Tag the amount of hits and score for killing this ship
Ship.HitPoints=rndrange(1,10) ; the number of hits it takes to kill this object
Ship.KillScore=rndrange(100,1000) ; score for killing this object
; Init this objects speed and movement direction
Ship.Speed =rndrange#(1,5)
Ship.Direction =rnd#(360)
; Make an image as pixel representation of this ship
img=MakeParticle(rndrange(32,64),rndrgb())
; Create a sprite as output channel of this ships image
Spr=NewSprite(x#,y#,img)
SpriteDRawmode Spr,2
SpriteCollisionMode Spr,6
SpriteCollisionClass Spr, 2 ; Each object type has it's own class. Allowing PB to screen for impacts
; Store to pointer to the parent object inside the sprite, so the object can be looked up in reverse.
CreateSpriteLocals Spr, 4
SpriteLocalint spr,0, GetShipPtr(ship()) ; Store a pointer in this sprite back to it's parent object the Ship structure.
; now impacts can reversed.
; remember the sprite this ship uses
Ship.Sprite=spr
EndFunction
` *=----------------------------------------------------------------------=*
` >> Update All The Ships <<
` *=----------------------------------------------------------------------=*
Function UpdateShips()
; Process Ships list
for each ship()
Select Ship.Status
; ---------------------------------
case Alive
; ---------------------------------
; Simulate some AI for the ship.
Spr=Ship.Sprite
;Reset Sprites draw mode to mode 2 (in case it was hit from a previous refresh)
SpriteDRawmode Spr,2
; get the speed and irection the object is moving in
Speed#=Ship.Speed
Angle#=Ship.Direction
MoveSprite Spr,CosRadius(Angle#,Speed#),SinRadius(Angle#,Speed#)
; get the sprite position after it's moved
x#=GetSpritex(spr)
y#=GetSpritey(spr)
; Check if the sprite/object has left the screen, if so, tag it to be deleted
if PointInBox(x#,y#,-100,-100,900,700)=false
ship.status=dead ; kill upon next refresh.
continue
endif
; ---------------------------------
case Dead
; ---------------------------------
; Object was killed at some point, so lets release it.
DeleteCurrentShip(Ship())
continue
EndSelect
next
EndFunction
` *=----------------------------------------------------------------------=*
` >> Delete Current Ship <<
` *=----------------------------------------------------------------------=*
Function DeleteCurrentShip(me.tShip)
Spr=me.Sprite
; Find what image this sprite was using
img=GetSpriteImage(spr)
; delete the sprite and the image
deletesprite Spr
Deleteimage img
; and finally free and unlink this object from the ship list
me = null
EndFunction
` *=----------------------------------------------------------------------=*
` >> GetShipPtr <<
` *=----------------------------------------------------------------------=*
`
` This nifty little function retrieves the pointer to current ship in
` the ships list.
` *=----------------------------------------------------------------------=*
Function GetShipPtr(me().tShip)
result=int(me(0).tShip)
EndFunction result
` *=----------------------------------------------------------------------=*
` >> Make particle Image <<
` *=----------------------------------------------------------------------=*
Function MakeParticle(Size,Col)
ThisImage=NewFXImage(Size,Size)
RenderPhongImage ThisImage,Size/2,Size/2,col,255,260/(size/2)
EndFunction ThisImage
[/pbcode]
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
QuoteI 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[pbcode]
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
[/pbcode]
QuoteWhat 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.
QuoteDoes SpriteHit() consider the Z order of the sprites?
Nope, PB is 2D.
QuoteWhat 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.