****************************************************************************
****************************************************************************
**                                                               
**  Platinum (Enemy to bullet collision)
**
**  This software is in the public domain.  There is no warranty.
**
**  by Patrick Davidson (pad@calc.org, http://pad.calc.org/)
**
**  Last updated July 25, 2001
**
****************************************************************************
****************************************************************************

******************************************** DETECT & PROCESS HITS TO ENEMIES
*
* The basic enemy detection routine steps are as follows:
*
* 1) Sort enemies and bullets together by X coordinate (using radix sort)
*
* 2) Create priority queues for enemies and bullets (using binary heaps)
*
* 3) Process list in order (simulates sweeping left to right) as follows:
*
*    A) Delete all items in either heap having key less than its left edge
*       (i.e. items completely to the left of it)
*
*    B) For each item encountered, check for collisions with other heap and
*       process collisions detected
*
*    C) If not destroyed, insert in its heap using its right edge as a key
*
* The following tricks are used to improve performance:
*
* 1) Pointers to enemies and bullets are only words (which is not a problem
*    since the stack, where the structures are, is at an address below 8000)
*
* 2) Before adding enemies, the minimum and maximum X coordinates of bullets
*    are calculated, and enemies outside this range are skipped
*
* 3) While adding enemies not already excludd, calculates the minimum and
*    minimum Y coordinates of enemies; bullets outside this range skipped
*
********

******************************************** TEMPORARY DATA STRUCTURES
*
* Since these data structures are used right after the screen is copied and
* before the new background is drawn, they can corrupt screen memory
* without causing any problems.
*
* Buckets and binary heaps are simple arrays, in which the first element is
* the size in bytes (i.e. number of items times two) which can simply be
* added to the start address to find the last item.
*
********

bucket_size     equ     128             ; large enough for 63 items
num_buckets     equ     16

buckets_1       equ     0
buckets_2       equ     3200

bullet_heap     equ     0
enemy_heap      equ     128

******************************************** MAIN COLLISION CHECKING ROUTINE
*
* This routine first performs the radix sort with code in itself, and then
* calls subroutines for each item to be processed.
*
********

******************************************** PREPARE FOR RADIX SORT

Enemy_Collisions:
        lea     (a5),a0                 ; Clear initial buckets               
        moveq   #15,d0
\init_buckets_1:
        clr.w   (a0)
        lea     bucket_size(a0),a0
        dbra    d0,\init_buckets_1

******************************************** CALCULATE BULLET X RANGE

        move.w  #217,d6                 ; minimum bullet X coordinate
        moveq   #40,d7                  ; maximum bullet X coordinate
        move.w  num_b(a5),d1
        lea     bullets_data(a5),a0
\bullet_edges:
        tst.w   (a0)                    ; skip non-existent bullet
        beq.s   \no_bullet
        move.w  b_x(a0),d0
        cmp.w   d0,d6                   ; set new minimum X if needed
        ble.s   \no_left_bullet
        move.w  d0,d6
\no_left_bullet:
        add.w   b_w(a0),d0              ; set new maximum X if needed
        cmp.w   d0,d7
        bge.s   \no_bullet
        move.w  d0,d7
\no_bullet:
        lea     b_size(a0),a0
        dbra    d1,\bullet_edges

******************************************** RADIX SORT FIRST PASS (ENEMIES)

        move.w  #156,d4                 ; minimum enemy Y coordinate
        moveq   #20,d5                  ; maximum enemy Y coordinate

        lea     enemies_data(a5),a0     ; Insert enemies
        moveq   #num_en-1,d1
\insert_enemies
        tst.w   (a0)                    ; skip non-existent enemy
        ble.s   \no_insert_enemy
        move.w  e_y(a0),d3              ; skip enemy off screen
        ble.s   \no_insert_enemy

        move.w  e_x(a0),d0              ; skip enemy with X below minimum
        cmp.w   d0,d7
        ble.s   \no_insert_enemy
        move.w  e_w(a0),d2              ; skip enemy with X above maximum
        add.w   d0,d2
        cmp.w   d2,d6
        bge.s   \no_insert_enemy

        and.w   #$f,d0                  ; D0 = bucket number
        lsl.w   #7,d0
        lea     0(a5,d0.w),a1           ; A1 -> bucket start
        addq.w  #2,(a1)                 ; increment bucket size
        add.w   (a1),a1                 ; A1 -> bucket end
        move.w  a0,(a1)                 ; place item in bucket

        cmp.w   d3,d4                   ; set new minimum Y if appropriate
        ble.s   \no_top_enemy
        move.w  d3,d4
\no_top_enemy:
        add.w   e_h(a0),d3              ; set new maximum Y if needed
        cmp.w   d3,d5
        bge.s   \no_insert_enemy
        move.w  d3,d5
\no_insert_enemy:
        lea     e_size(a0),a0
        dbra    d1,\insert_enemies

******************************************** RADIX SORT FIRST PASS (BULLETS)

        lea     bullets_data(a5),a0     ; Insert bullets
        move.w  num_b(a5),d1
\insert_bullets:
        tst.w   (a0)
        beq.s   \no_insert_bullet       ; skip non-existent bullet

        move.w  b_y(a0),d0              ; skip bullet with Y below minimum
        cmp.w   d0,d5
        ble.s   \no_insert_bullet
        add.w   e_y(a0),d0              ; skip bullet with Y above maximum
        cmp.w   d0,d4
        bge.s   \no_insert_bullet

        move.w  b_x(a0),d0
        and.w   #$f,d0
        lsl.w   #7,d0
        lea     0(a5,d0.w),a1           ; A1 -> bucket start
        addq.w  #2,(a1)                 ; increment bucket size
        add.w   (a1),a1                 ; A1 -> bucket end
        move.w  a0,(a1)                 ; place item in bucket
\no_insert_bullet:
        lea     b_size(a0),a0
        dbra    d1,\insert_bullets

******************************************** RADIX SORT SECOND PASS

        lea     buckets_2(a5),a0               
        moveq   #15,d0
\init_buckets_2:
        clr.w   (a0)
        lea     bucket_size(a0),a0
        dbra    d0,\init_buckets_2

        lea     (a5),a4                 ; A4 -> source bucket
        lea     buckets_2(a5),a6        ; A6 -> start of destination buckets
        moveq   #15,d0                  ; D0 = # of source buckets left
\sort_phase_2:
        move.w  (a4),d1                 ; D1 = size of source bucket
        beq.s   \bucket_done
        lsr.w   #1,d1
        subq.w  #1,d1                   ; D1 = # of source items
        lea     2(a4),a3                ; A3 -> position in source bucket
\process_bucket:
        move.w  (a3)+,a2                ; A2 -> item being considered
        move.w  b_x(a2),d2              ; D2 = item's key
        and.w   #$f0,d2
        lsl.w   #3,d2                   ; D2 = offset in bucket
        lea     0(a6,d2.w),a1           ; A1 -> destination bucket start
        addq.w  #2,(a1)                 ; increment destination bucket size
        add.w   (a1),a1                 ; A1 -> bucket end
        move.w  a2,(a1)                 ; place item in bucket
        dbra    d1,\process_bucket
\bucket_done:
        lea     bucket_size(a4),a4
        dbra    d0,\sort_phase_2

******************************************** SWEEP SORTED DATA
*
* Now that the buckets contain the sorted data, the routine goes through
* them, processing each item.  It expects all subroutines to preserve
* a3/a5-a7 and d4-d6.  Routines return by branching to item_handled.
* Subroutines are called with a4 pointing to the item to deal with.
* D7/A4 must also be preserved by deletekey stuff
*
********

        clr.w   (a5)                    ; initialize the heaps
        clr.w   enemy_heap(a5)

        lea     enemies_data(a5),a0
        move.w  a0,d6                   ; d6 = start of bullets
        moveq   #15,d4
handle_buckets:
        move.w  (a6),d5                 ; d5 = size of this buckets
        beq.s   no_items
        lsr.w   #1,d5
        subq.w  #1,d5
        lea     2(a6),a3                ; A3 -> position in bucket
handle_bucket:
        move.w  (a3)+,a4
        move.w  e_x(a4),d7
        lea     (a5),a0
        bsr.s   delete_keys_below_d7
        lea     enemy_heap(a5),a0
        bsr.s   delete_keys_below_d7
        move.l  a3,-(sp)
        cmp.w   a4,d6
        ble     process_new_enemy
        bra     process_new_bullet
item_handled:
        move.l  (sp)+,a3
        dbra    d5,handle_bucket
no_items:
        lea     bucket_size(a6),a6
        dbra    d4,handle_buckets
        rts

******************************************** DELETE ITEMS FROM HEAP
*
* This routine removes every item with a key less than or equal to the
* value in d7 from the heap in A0.
*
********

heap_not_empty:
        move.w  2(a0),a1                ; A1 -> first item in heap
        move.w  e_x(a1),d0
        add.w   e_w(a1),d0
        cmp.w   d0,d7
        blt.s   exceeded_d7
        bsr.s   deleteMin
delete_keys_below_d7:
        tst.w   (a0)
        bne.s   heap_not_empty
exceeded_d7:
        rts

******************************************** DELETE MINIMUM ITEM FROM HEAP
*
* Deletes the minimum item from the heap at (A0).  Preserves d4-d7/A0/A3-A6.
*
********

deleteMin:
        move.w  (a0),d0                 ; d0 = size of the heap
        move.w  0(a0,d0.w),2(a0)         ; move last item in heap to front
        subq.w  #2,(a0)                 ; restore heap size

        moveq   #2,d1                   ; d1 = item being processed
\reorder_heap:
        move.w  0(a0,d1.w),a1            ; A1 -> this item
        move.w  e_x(a1),d0
        add.w   e_w(a1),d0              ; d0 -> this item's key

        move.w  d1,d2
        add.w   d2,d2                   ; d2 = left child
        cmp.w   (a0),d2
        beq.s   \left_child_only
        bgt.s   \past_heap_end

\both_children:
        move.w  0(a0,d2.w),a2            ; A2 -> this item's left child
        move.w  e_x(a2),d3
        add.w   e_w(a2),d3              ; d3 = key of left child
        cmp.w   d3,d0
        bge.s   \left_child_smaller
        move.w  d1,d3                   

\left_child_smaller:
        move.w  d3,d0                   ; d0 = key of smallest item so far
        move.w  d2,d3                   ; d3 = smallest found so far
\d3_smallest:
        move.w  2(a0,d2.w),a2           ; A2 -> this item's right child
        sub.w   e_x(a2),d0
        sub.w   e_w(a2),d0
        ble.s   \no_smaller_found
        move.w  d2,d3
        addq.w  #2,d3
\no_smaller_found:
        cmp.w   d2,d3
        beq.s   \past_heap_end          ; done if no smaller children

        move.w  0(a0,d3.w),a2            ; A2 -> smallest item
        move.w  a2,0(a0,d1.w)
        move.w  a1,0(a0,d3.w)            ; exchange with smallest child
        move.w  d3,d1
        bra.s   \reorder_heap

\left_child_only:
        move.w  0(a0,d2.w),a2            ; A2 -> this item's left child
        sub.w   e_x(a2),d0
        sub.w   e_w(a2),d0              ; d0 = own key - left child's key
        ble.s   \past_heap_end          ; exit if child's key >= ours
        move.w  a2,0(a0,d1.w)            ; swap item with child
        move.w  a1,0(a0,d2.w)
                                        ; since now at end, can quit
\past_heap_end:
        rts

******************************************** PROCESS A NEW BULLET
*
* First checks the bullet for hits with existing enemies.  If any is found,
* this routine returns immediately.  Must save d4-d7/A3/a5-A6 and return to
* the item_handled label.  Called with A4 pointing to bullet.
*
********

bullet_hit_something:
c3:     clr.w   (a4)                    ; kill bullet
        move.w  b_dmg(a4),d0
        sub.w   d0,e_dmg(a3)            ; damage enemy
        bge     item_handled            ; return if not destroyed
        lea     Destroy_Base(pc),a0     ; call destruction code
        add.w   e_dstry(a3),a0
        exg     a3,a4
c4:     jsr     (a0)
        exg     a3,a4
        bra     item_handled

process_new_bullet:
        move.w  enemy_heap(a5),d7       ; D7 = size of enemy heap
        beq.s   \nothing
        lsr.w   #1,d7
        subq.w  #1,d7                   ; D7 = items left in enemy heap
        lea     enemy_heap+2(a5),a1
\test_collisions:
        move.w  (a1)+,a3                ; A3 -> item from enemy heap
        tst.w   (a3)
        ble.s   \no_enemy_here
        bsr     collision_detect_2
        bne.s   bullet_hit_something
\no_enemy_here:
        dbra    d7,\test_collisions
\nothing:
        lea     bullet_heap(a5),a0

******************************************** INSERT ITEM INTO HEAP
*
* Inserts A4 into the heap at A0.  Preserves d4-d6/A3/A6, returns to the
* item_handled_label.
*
*******

insertKey:
        move.w  e_x(a4),d2              ; D2 = this item's key
        add.w   e_w(a4),d2
        addq.w  #2,(a0)
        move.w  (a0),d0                 ; D0 = position of bubble
\loop:  cmp.w   #2,d0                   ; check if at root
        beq.s   \bubble_done
        move.w  d0,d1
        lsr.w   #1,d1                   ; D1 = parent(D0) index
        bclr    #0,d1
        move.w  0(a0,d1.w),a1           ; A1 -> parent item
        move.w  e_x(a1),d3
        add.w   e_w(a1),d3
        cmp.w   d3,d2                   ; parent's key - key
        ble.s   \bubble_done            ; done if parent has lower key
        move.w  a1,0(a0,d0.w)           ; move bubble up
        move.w  d1,d0
        bra.s   \loop
\bubble_done:
        move.w  a4,0(a0,d0.w)
        bra     item_handled

******************************************** PROCESS A NEW ENEMY
*
* First checks the enemy for hits with existing bullets.  If any is found,
* this routine returns kills the bullet, damages the enemy, and returns if
* the enemy was destroyed.  Must save d4-d7/A3/a5-A6 and return to
* the item_handled label.  Called with A4 pointing to bullet.
*
********

enemy_hit_something:
c1:     clr.w   (a3)                    ; kill bullet
        move.w  b_dmg(a3),d0
        sub.w   d0,e_dmg(a4)            ; damage enemy
        bge.s   no_bullet_hit           ; continue if not destroyed
        lea     Destroy_Base(pc),a0     ; call destruction code
        add.w   e_dstry(a4),a0
        pea     item_handled(pc)
c2:     jmp     (a0)

process_new_enemy:
        move.w  bullet_heap(a5),d7      ; D7 = size of bullet heap
        beq.s   nothing
        lsr.w   #1,d7
        subq.w  #1,d7                   ; D7 = items left in bullet heap
        lea     bullet_heap+2(a5),a1
test_collisions:
        move.w  (a1)+,a3                ; A4 -> item from bullet heap
        tst.w   (a3)
        ble.s   no_bullet_hit
        bsr     collision_detect_2
        bne.s   enemy_hit_something
no_bullet_hit:   
        dbra    d7,test_collisions
nothing:
        lea     enemy_heap(a5),a0
        bra.s   insertKey

******************************************** COLLISION DETECTION ROUTINE
*
* Like regular collision detection, only guaranteed to preserve
* A1/A3-A7/D4-D7.
*
********

collision_detect_2:
        movem.l a3/a4,-(sp)
        bsr     Test_Collision
        movem.l (sp)+,a3/a4
        rts