I
N
D
E
X

There you are: your cool new vertical shooter game is about done. You've used every trick you know about to get it where it is today. You have an array for the players bullets, another for the enemy's shots and yet another for the enemies themselves. But you have a problem... the frame rate, while consistant, is slow [even with the help of tons of assembly]. Well it's time to look at your game object routines...

A game object routine is just a catch all term for game specific routines that involve the interaction of the various game pieces. An example of such a routine would be the way by which you check for collision between enemy fighters and players bullets. And more specifically how enemies and bullets are 'spawned'.

An example of a 'spawning' player bullet routine would involve calculating where the bullet will be on screen then placing these and other values into the 'bullet array'. The problem is figuring out which array subscript is 'open' or 'good' in order to place the stats for the bullet. A typical 'bullet array' may have a variable that indicates if the particular bullet is 'alive'. The usual way to do this is by scanning through the array with a FOR/NEXT loop looking the first 'dead' one you find.

This will seem very fast if, say, you only have 10 possible bullets to check. But look again. For every frame you would need to 'scan' the array for all the 'alive' bullets just to be able to draw them! Then again for each enemy that might be in contact with them! And again just to move them for the next frame!

If only one enemy is onscreen and you limit the bullets to ten max but only have one bullet that is 'alive'... that means for every frame you have to 'scan' the array 3 times!. If you have 20 onscreen bad guys and still only one bullet... your scanning 22 times [or to put it another way... your checking 220 times per frame if a bullet is 'alive']! Now you know why your game engine is so slow!

But what to do about it? Well you could use several index lists.

Index Lists
An index list is a simple 'list' of 'array subscripts' [or 'indexes']. You can have a separate index list for all the 'alive' bullets, the 'dead' ones, 'alive' enemies, and 'dead' ones too. In fact you could have a separate index list for just about anything you want in relation to a particular array.

The great thing about index lists is that they contain all the array subscripts you need for a particular routine. You no longer need to 'scan' a whole array to find the 'alive' from the 'dead'. In the example above, one bullet and 20 enemies might mean that you have 'scanned' the array 220 times per frame. With a index list of 'alive' bullets and 'alive' enemies you are no longer 'scanning' but instead you are working with only the 'alive' bullets and enemies.

Great, so how do I make an index list in QB?

Pure and simple... variable length STRINGs. That and the assorted QB functions like MID$, CVI, ASC, and MKI$ [NOTE: use of PEEK and POKE will give faster results, but for the sake of clarity I'll use MID$ and the others for this article].

Okay here are some routines for a 'bullet' array:

CONST maxbullets = 10

'bullet data type that contains
'x/y location and kind of bullet
TYPE bulletdata
x AS INTEGER
y AS INTEGER
kind AS INTEGER
END TYPE

' here is the bullet array
DIM SHARED bullets(maxbullets) AS bulletdata

' here are the index lists.. one for "alive bullets" [balive]
' the other for "dead" ones [bdead]
DIM SHARED balive AS STRING
DIM SHARED bdead AS STRING

The first thing you want to do is "initialize" the "dead" array, like below. This is done so that the index list is accurate in that all the bullets are effectively "dead" when the game starts.

FOR i = 1 TO maxbullets
bdead = bdead + MKI$(i)
NEXT i

'
'your game code here :P
'

These subs are used to "spawn", "kill", "hit detect"[hdbullet] the bullets

SUB spawnbullet( x%, y%, k%)
' spawns a bullet... just pass the
'location x/y and kind of bullet and thats all you have to do

This works by grabbing and removing the first "dead" bullet from the bdead STRING. It then adds it to the end of the balive string, thus it becomes active and it then enters the data into the array.

IF (LEN(balive)/2) < maxbullets THEN

index$ = MID$(bdead,1,2)

bdead = MID$(bdead,3,LEN(bdead))
balive = balive + index$

v% = CVI(index%)

bullets(v%).x = x%
bullets(v%).y = y%
bullets(v%).k = k%

END IF

END SUB

This removes a bullet from the balive STRING and adds it to bdead, thus the particular bullet becomes inactive. The variable passed to this SUB is the actual array subscript; however, this SUB is only intended to be CALLed by the collision detection routine named "hdbullet" or any routine [like movement] that will need to remove the bullet for some reason.

SUB killbullet(v%)

index$ = MKI$(v%)

IF index$ = MID$(balive,1,2) THEN

balive = MID$(balive,3,LEN(balive))

ELSE

IF index$ = MID$(balive,(LEN(balive)-2),2) THEN

balive = MID$(balive,1,LEN(balive)-2))

ELSE

FOR i = 3 TO LEN(balive) STEP 2
test$ = MID$(balive,i,2)
IF index$ - test$ THEN
balive = MID$(balive,1,(i-1)) + MID$(balive, i+2, LEN(balive))
EXIT FOR

END IF
END IF
END IF

bdead = bdead + index$

END SUB

This sub is where you will do hit detection with the enemy array subscript enum%, as most of this will really depend on the particular method you use for collision detection and etc.. My main reason for including this in the article is to show how to use a FOR/NEXT loop with the index list; by replacing the core "hit detection" routine inside the FOR/NEXT loop, you can replace it with sprite drawing routines,etc.. Just remember to use index% as the array subscript and not "i"

SUB hdbullet(enum%)

FOR i = 1 TO LEN(balive) STEP 2
index% = CVI( MID$(balive,i,2))

' IF bullets(index%) CONTACTS ENEMY(enum%) THEN
' CALL killbullet(index%)
' CALL killenemy(enum%) if need be....
' END IF

NEXT i

END SUB

Okay those more advanced programmers out there will see that you can have one large "generic" array for bullets, enemies, et al. And simply use a bunch of index list STRINGs [possibly even in an STRING array!]. Doing this will reduce your needed index list management subroutines to only a handful [spawn, remove, drawing, movement, and hit detection]! Mmm... less code equals less work, and less code to debug! :)

I've used a vertical shooter as a example game that would be helped out by index lists. But in truth any game could easily use this technique! If memory is a problem [but speed isn't] you could store the contents of your array in a RANDOM access file and use the index lists to GET/PUT one array record at a time. This would save a TON of memory as only the index list STRINGs would be needed! Another thing you can do with index list is to sort them based on some value held in the array. This is cool because only the order of characters in the STRING needs to be changed [and using a "radix" type sort programmed in Qbasic, it only takes less then a 10th of a second to sort 3,000 items on my P-150!].

So now you, hopefully, know some ways to optimize your code. If not, then I hope that you have learned of a new way to use STRINGs for things beside holding text...

Happy progging :)

Email MA*SNART telling him how you used a Reverse-culling bubble LZW Index in your game at this address.

L
I
S
T
S