;; ======================================================================== ;;
;;  Space Patrol Data Structures                                            ;;
;; ======================================================================== ;;

Space Patrol uses a wide array of data structures to keep track of its
"universe."  To understand these data structures, it's useful to know
Space Patrol's nomenclature.


MOB         One of the STIC's 8 hardware "Movable OBjects."
Sprite      One of 12 objects that SP tracks and maps onto the STIC's MOBs.
Bad Guy     One of the sprite-based enemies in the game.  Abbreviated "BG"
BG Bullet   One of the bullets fired by a Bad Guy.  Abbreviated "BGB"
Good Guy    The player.  Abbrev. "GG," but usu. referred to as "tank"/"buggy"
GG Bullet   The player's bullets.  Abbreviated "GGB."
Buggy       The player's vehicle.
Tank        A synonym for buggy.
Course      One of the 8 A-Z worlds the player gets to play
BGMP        Bad Guy Motion Program
Spawn       A record describing how to place a BG on the screen
Cue         A record in the world indicating a set of spawns
Exit        A record in the world cueing BGs to leave or change behavior
BG Tag      Tags associating spawns and courses with sprite attributes
Exit Tag    Tags allowing different subsets of BGs to be exit-cued separately


Sprites and sprite motion
-------------------------

Space Patrol keeps track of sprites with four separate tables in RAM,
and a fifth table in ROM.  These are:

    SPAT    SPrite ATtribute         (8-bit)
    SPXYP   SPrite X/Y Position      (16-bit)
    SPXYV   SPrite X/Y Velocity      (16-bit)
    SPHSCR  SPrite Horizontal Scroll (8-bit)
    SPATBL  SPrite Attribute TaBLe   (in ROM)

These tables hold one entry for each of the 12 sprites.  These tables 
are notionally divided into two subtables each, with indices 0-4 always
referring to BGs, and indices 5-11 referring to BGBs and GGBs.  These
two groupings are referred to as "Group 1" and "Group 2" in the source
code.  Group 2 is further subdivided:  BGBs are always at indices 5-9
and GGBs are always at indices 10 and 11.  (It bears noting here that
only 2 of the 3 GGBs are sprites.)

The SPAT table holds a single byte for each active sprite.  This byte
indicates which entry in the SPATBL should be used for rendering that
sprite.  The SPATBL contains a 4-word entry for each sprite image.
The first 3 words indicate the STIC programming for the X, Y and A
registers when the sprite gets mapped onto a MOB.  The fourth word
indicates the bounding box for that sprite.

The SPXYP and SPXYV tables store 16-bit values that represent the 
fractional position and velocity of the 12 sprites.  Space Patrol uses
an unusual representation for these values.  Rather than a traditional
"integer/fraction" 2s complement fixed point representation, Space 
Patrol uses a 1s complement representation that places the fractional
portion in the 8 MSBs and the integer portion in the 8 LSBs.  

SP uses 1s complement because 1s complement arithmetic is commutative
with respect to rotation.  This allows us to put the integer portion of
the word in the lower byte.  This further allows us to read the integer
portions of both X and Y into a single 16-bit word with "SDBD ; MVI@",
and it eliminates a SWAP when copying out X/Y values from SPXYP to
actual MOB registers.  All in all, rather useful.


Mapping Sprites to MOBs
-----------------------

Space Patrol treats MOBs separately of sprites.  This allows SP to
track more objects than the hardware can display, with the game logic
multiplexing as needed to show this larger set of objects on screen.
SP uses an aggressive multiplexing technique intended to minimize 
flicker as much as possible.

SP divides the MOBs into 4 groups:

   MOBs 0 and 1:  Dedicated to displaying the tank.
   MOB 7:         Dedicated to displaying level-marker, if visible.
   Group 1:       Sprites from sprite group 1.  Minimum of 3 MOBs.
   Group 2:       Sprites from sprite group 2.  Minimum of 2 or 3 MOBs.

The player's tank never participates in multiplexing.  It is the "star"
of the game and gets top priority for display.  There's an additional
technical reason for this:  SP relies on hardware collision to detect
sprite collisions with the tank.  It's easier to track this when the
tank-to-MOB mapping is fixed, even when the enemy-to-MOB mapping is not.

Group 1 and Group 2 both start with 3 MOBs allocated to them.  Then,
the partitions between Group 1 and Group 2 get shifted as follows:

 -- If a Level Marker is visible, deduct 1 from group 2.
 -- If group 1 has fewer than 3 sprites, add the extra to group 2.
 -- If group 2 has fewer sprites than its allocation, add them to
    group 1 if it needs them.

SP tracks this allocation in the variables GP1ACT and GP2ACT.  The
multiplexing logic uses this allocation information to guide the
sprite-to-MOB rendering code.

Sprites are active if their entry in SPAT is non-zero.  To disable a
sprite (e.g. "kill a bad guy"), all the game must do is zero out its
SPAT entry.

Each group keeps a separate "multiplex counter" to handle multiplexing.
The code in UPMUX steps through the sprites in group 1 and group 2,
allocating sprites to MOBs, starting at the sprite number indicated by
that group's multiplex counter.  The allocator wraps the counter around
automatically.  When the number of active sprites is less than or equal
to the number of MOBs allocated to that group, all sprites get displayed.
If the number of sprites is larger, the multiplex counter is left pointing
at the first not-displayed sprite in the group, thus ensuring display
allocation begins with that sprite during the next display frame.

As the MOBs get generated, the engine writes the MOB register image to a
table named SDAT in 16-bit memory.  The ENGINE1 interrupt service routine
(ISR) then copies these 24 words directly into the STIC registers.  This
allows the MOB generation/update to occur outside interrupt context.


Updating Sprite Positions
-------------------------

The sprite position update is a fixed activity.  SP merely steps through
the SPXYP and SPXYV tables, adding the current velocity to the current
position.  It performs this update blindly--that is, it computes new
X/Y positions for all 12 sprites, regardless of whether they're actually
active.  This reduces peak loading at the expense of average loading.

The first 5 sprites (corresponding to group 1) can also have an
additional "horizontal scroll" flag bit set in the table SPHSCR.
When set, this flag enables a further update to the sprite position
for the corresponding sprite.  Whenever the foreground scrolling pane
scrolls left one pixel, SP will scroll sprites flagged by SPHSCR left
by 1 pixel as well.  This pegs their motion to the motion of the screen.

Some objects, such as the rolling boulders, have both a horizontal peg
via SPHSCR as well as a non-zero horizontal velocity.  The engine adds
both of these velocities into these objects' positions.


Manual Collision Detection
--------------------------

Space Patrol only uses hardware collision detection to determine
whether BGs or BGBs hit the tank.  For everything else, it uses
software based manual collision detection.  It dects two sets of
collisions manually:  GGB vs. BG/BGBs, and tank vs. rock/crater.

For GGB vs. BG/BGB collisions, the engine consults the following:

    GGBx        GGB positions, derived from SPXYP and HBCOL.
    SPATBL      Bounding box information for each of the sprites.
    SPXYP       Position information for the bad guys.

The code extracts the X/Y position of the 3 GGBs and then compares
that against the bounding box for each of the active BGs and BGBs.
When it finds a collision, it kills the offending BG/BGB.

For the tank vs. rock/crater, the engine consults four separate
sets of data:

    JHGT        The current jump-height of the tank.
    MJHIDX      Minimum Jump Height InDeX.
    MJHTBL      Minimum Jump Height TaBLe.
    BACKTAB     The actual pattern of rocks/craters around the tank.

The code looks at the current tank horizontal position, and uses
that to derive a neighborhood of cards that the tank overlaps.  
The code then looks to see if any of those cards have their MSB 
set, and if they do, whether they correspond to a rock or a crater.

For cards that correspond to rocks and craters, the code looks up
which sub-table of MJHTBL to consult in the MJHIDX table.  Based
on the relative position of the tank and the display scroll, the
code looks up the required minimum jump height required between
the tank and whatever object it needs to jump.  If the tank's jump 
height is too low, the game registers a collision.



Updating Bad Guys
-----------------

Bad guys are tracked with a set of parallel tables in 8-bit memory,
and a lookup table in ROM:

    BGMPTBL     Bad Guy Motion Program TaBLe
    BGEXIT      Bad Guy Exit programming
    BGMPIND     Bad Guy Motion Program INDirect (ROM)

The BGMPTBL contains a series of 4-byte records.  The first byte is an
indirect pointer to the "thinker" function for each bad guy.  A zero in
this byte indicates a dead bad-guy.  The second byte is the "thinker
delay," which counts down 30Hz ticks between calls to the thinker.
The remaining two bytes are status bytes that each BG can use as it sees
fit to track its status.

The main BGMP update engine simply steps through the BGMPTBL, counting
down the sleep-delay for each of the non-dead BGs and invoking the
thinker for each BG when its sleep delay expires.  Some thinkers are
very simple: For example, boulders have a null thinker most of the time,
and mines have a simple "blink randomly" thinker.

Others have more involved thinkers.  Saucers have a somewhat elaborate
control scheme described in bg/bgsaucer.asm.  The Follower actually must
coordinate the actions of two BG entries, as described in bg/bgfollow.asm.

Thinkers control both the steady state action of a BG as well as how
it exits.  The BGEXIT table binds an Exit Tag to a BG.  The course can
cue sets of BGs to exit at various times using one of several tag values.
The BGEXIT table indicates which tag each BG responds to, as well as the
thinker that BG should switch to when it's time to exit.

The BGMPIND table maps thinker programs to small integer indices.
This allows us to store the thinker function pointers in 8 bit memory
efficiently.  Furthermore, by ensuring all exit thinkers are near the
beginning of the table (currently, indices smaller than 8), Space Patrol
is able to pack the exit tag with the exit thinker number.  This allows
storing both sets of information in the same byte of RAM.  


Building the world
------------------

The world is factored into several pieces:  Course data, rock/crater
placement data, bad guy cues, bad guy exit cues, caution cues and
checkpoints.

Course data consists of a set of run-length encoded records.  These
records can indicate which of the above elements needs to be emitted
next, followed by the number of blank locations that exist between
the requested element and the next one.

Rocks and craters trigger a second sub-engine that copies out the specific
set of cards for the rock/crater image.  The structures "RCS1" and "RCS2"
contain the BACKTAB words describing the various rocks and craters.
Bit 15 of each word indicates whether a card is within the object.  The
subengine uses this information to know when it's done outputting a 
rock or crater.  The collision logic uses this to determine whether it
needs to evaluate a tank/rock or tank/crater collision for that card.

Bad guys are cued onto the screen using "CUE" records.  These CUE 
records are mapped to a series of SPAWNs defined in world/spawn.asm.
A SPAWN record indicates the following about the requested bad guy:

1.  The BGTAG being spawned.
2.  Its initial BGMP 
3.  Its exit BGMP
4.  Its exit tag, or 0 for none
5.  Its initial X and Y positions
6.  Its initial values for its two state bytes
7.  A flag indicating whether the SPAWN chains to the next SPAWN.

BGTAGs add a layer of indirection between the BG being spawned and the
actual SPAT associated with the SPAWN.  BGSTBL (Bad Guy Spawn TaBLe) maps
a small-integer BGTAG to an actual SPAT value.  The BGTAG gets augmented
with the upper 2 bits of the course number, thereby giving each pair of
courses a different mapping of BGTAGs to SPATs.  This makes it cheap to
give the Moon, Mars, Pluto and Mercury course-pairs their own unique look
while reusing the same SPAWN records.

SPAWNs can be chained together so that a single CUE brings more than one
BG onscreen at a time.  This provides useful compression for level data,
as only a single record in the world can refer to several creeps.  When a
SPAWN is CUEd, the engine populates the BGMPTBL, BGEXIT, SPAT and SPXYP
tables with the data from the SPAWN record.  If all 5 BGs are taken when
the engine attempts to spawn a new BG, the additional BG gets dropped.

Exit cues are somewhat simpler than spawn cues.  Exit cues specify an
exit tag number.  Upon decoding an exit cue, the engine steps through
the BGEXIT array looking for matching tags.  Wherever a match is found,
the engine sets the thinker function to the recorded exit BGMP for
that object.

Note that the object isn't required to exit in response to an exit
request.  For example, the Follower uses the exit tag to indicate when to
move to the next stage of movement.  The first stage has it hover behind
the tank.  The second stage has it move in front of the tank.  The final
stage has it exit.  So, to get a Follower to exit, one must cue it to
exit twice.  The Follower achieves this by recording its current state in
its status byte, and resetting its BGMP number in the BGMPTBL as needed.

Caution cues are quite simple.  They simply tell the engine to blink the
"caution" light on the game dash board.  The caution cue specifies one
of four caution light colors to flash.

Checkpoints are similarly simple.  They cue a level-marker character
to scroll by.  The engine treats these specially, dedicating a MOB to
them and scrolling them with the screen.  That way, they do not detract
from the 12 available sprites.  Level markers are specified in upper or
lower case.  Lower case indicates checkpoints associated with summary
screens, such as those that appear at E, J, and so on.





