ASM Porting Sonic 1 Squared's Priority Manager to Sonic 2

Here we go, my first how-to guide as a tech member.

@Hivebrain's Sonic 1 Squared contains a large number of improvements to the game's engine, but one of the more noteworthy ones is its overhauled priority system. Said system, dare I say it, rivals S3K's priority manager, and may in fact be a viable alternative to it for Sonic 2, not the least because it is more directly compatible with Sonic 2's engine. I'll show you how to port it to Sonic 2 shortly, but first, let's look at how it compares to the original manager and S3K's.

The original priority manager in Sonic 1 and 2, for reference, stores the priority value as a byte 0-7, which is copied as a word, left shifted, and'ed, and finally added to the start address of the sprite queue to make an offset to a priority section in the sprite queue, a process that takes 44 cycles:

Code (ASM):

1.    lea (v_sprite_queue).w,a1
2.    move.w ost_priority(a0),d0 ; get sprite priority (as high byte of a word)
3.    lsr.w #1,d0 ; d0 = priority * sizeof_priority
4.    andi.w #((1<<priority_count_bits)-1)<<priority_size_bits,d0
5.    adda.w d0,a1 ; jump to priority section in queue

S3K's priority manager speeds things up significantly by instead storing a pre-calculated offset in the OST. The priority manager simply adds this offset to the queue address, taking just 24 cycles:

Code (ASM):

1.     lea (v_sprite_queue).w,a1
2.     adda.w ost_priority(a0),a1

20 fewer cycles required for every sprite that is queued adds up to a significant speed improvement, so it's no wonder that porting this manager into Sonic 1 and 2 is so common. However, it comes with the drawback of requiring the OST structure to be rearranged, since the priority value is a full word as opposed to a byte.


Hivebrain's S1SQ manager takes an approach somewhere between the two: the priority value, while still a byte, is now an 2-byte stride index value (even numbers 0-$E) that is used to fetch the address of the priority section from a lookup table, taking 30 cycles:

Code (ASM):

1.        ; See below for full code of manager
2.        moveq   #0,d0
3.        move.b   ost_priority(a0),d0           ; get sprite priority
4.        movea.w   Disp_OffsetList(pc,d0.w),a1       ; get RAM address for priority level (movea.w sign extends to make full 32-bit address)

While a bit slower than S3K's system, it's still a significant improvement over the original S1/S2 priority manager, and crucially, it does not require altering the OST structure, making it much easier to install in Sonic 2 or base Sonic 1.


Installing this manager in Sonic 2 is not all that difficult; in fact, it is very close about to being a drop-in replacement in my ASM68K disassembly. Additionally, there is an optimization that can be made for those objects that use DisplaySprite3. Regardless of whether you're using SonicRetro AS or my ASM68K disasm, bugfixes MUST be enabled; the original game has a number of multisprite objects that mistakenly call DisplaySprite and pass garbage as the priority value; in the old system, this merely causes these sprites to display on random layers, but in the new system, this will crash the game. (Note that my ASM68K disasm isn't really ready for production use; the instructions for it are for the benefit of those who may use it in the future).

First, let's set up our values to these equates. If you're using Sonic 2 AS, insert the following somewhere in s2.constants.asm:

Code (ASM):

1. ; Sprite priorities
2. priority_0:       equ 0
3. priority_1:       equ 2
4. priority_2:       equ 4
5. priority_3:       equ 6
6. priority_4:       equ 8
7. priority_5:       equ $A
8. priority_6:       equ $C
9. priority_7:       equ $E

If you're using Sonic 2 ASM68K, there will already be a set of equates for these in Constants.asm; simply replace those with the ones above.

Now, we need to modify the code to use the new priority values. If you're using my ASM68K disasm, you may skip the first three steps of this part, as these values are already equated to constants. If you're using Sonic 2 AS (as I assume most are currently), let's go ahead and replace the raw immediates with constants.

Find EVERY instance where the priority OST slot is loaded with an immediate value (be careful, as both a0 and a1 are used):

Code (ASM):

1.  move.b #3,priority(a0)
2.  move.b #3,priority(a1)

To all of these, add priority_ before the number:

Code (ASM):

1.  move.b #priority_3,priority(a0)
2.  move.b #priority_3,priority(a1)

Next, find every subObjectData macro, and do the same with the priority value there, adding priority_ before the number

Code (ASM):

1.   subObjData Obj28_MapUnc_11E1C,make_art_tile(ArtTile_ArtNem_Animal_2,0,0),4,2,8,0 ; this...
2.   subObjData Obj28_MapUnc_11E1C,make_art_tile(ArtTile_ArtNem_Animal_2,0,0),4,priority_2,8,0 ; becomes this

Do the same with the OST data lists at Obj1C_InitData and Obj71_InitData...

Code (ASM):

1.   objsubdecl 0, Obj1C_MapUnc_11552, make_art_tile(ArtTile_ArtNem_BoltEnd_Rope,2,0), 4, 6 ; this...
2.   objsubdecl 0, Obj1C_MapUnc_11552, make_art_tile(ArtTile_ArtNem_BoltEnd_Rope,2,0), 4, priority_6 ; becomes this

...and for the prison capsule's OST data at Obj3E_ObjLoadData:

Code (ASM):

1.    dc.b   0,  2,$20,  4,  0 ; this...
2.    dc.b   0,  2,$20,  priority_4,  0 ; becomes this

Now, we need to deal with all of the multi-sprite objects that use DisplaySprite3. Due to the way the multi-sprite system works, these objects cannot use the priority OST slot; instead, they pass a pre-calculated priority section offset to DisplaySprite3, which skips the calculation steps. Rather than keep this, we'll change it to pass the same index values as normal objects, which will also allow for a nice optimization.

Near every call to DisplaySprite3 is a move.w instruction that places a priority section offset in d0:

Code (ASM):

1. ; Sonic 2 AS
2.   move.w   #object_display_list_size*2,d0
3.   jmp   (DisplaySprite3).l
4. ; =====================
5.    ; Sonic 2 ASM68K
6.     move.w   #sizeof_priority*priority_2,d0
7.     jmp   (DisplaySprite3).l

Find all 22 of these, including the ones in bugfixes, and change them to this:

Code (ASM):

1.   ; Sonic 2 AS
2.   moveq   #priority_2,d0
3.   jmp   (DisplaySprite3).l
4. ; =====================
5.    ; Sonic 2 ASM68K
6.     moveq  #priority_2,d0
7.     jmp   (DisplaySprite3).l

Since the priority value passed to DisplaySprite3 is now a positive byte, we can optimize all of these move.w instructions to moveq.

Finally, there are two objects which calculate a priority value for an object they are spawning. Special Stage Tails (Object 10) sets the priority for his tails under loc_36864 thusly:

Code (ASM):

1.  ; Sonic 2 AS
2.     move.b   priority(a0),priority(a1)
3.     subi_.b   #1,priority(a1)
4. ; =====================
5.    ; Sonic 2 ASM68K
6.     move.b   ost_priority(a0),ost_priority(a1)
7.     subi_.b   #1,ost_priority(a1)

Change the 'subi_.b #1' to a 'subq #2'.

The WFZ breakable plating (Object C1) does nearly the same under loc_3C1F4:

Code (ASM):

1. ; Sonic 2 AS
2.     move.b   priority(a0),d4
3.     subq.b   #1,d4
4. ; =====================
5.    ; Sonic 2 ASM68K
6.        move.b   ost_priority(a0),d4
7.        subq.b   #1,d4
8.  

Again, change the 'subq.b #1' to a 'subq #2'.


At last, we are ready to install the new manager. Find the DisplaySprite routines, and replace all three of them with this:

Spoiler: Sonic 2 AS

Code (ASM):

1. DisplaySprite:
2.    moveq   #0,d0
3.    move.b   priority(a0),d0           ; get sprite priority
4.  
5. DisplaySprite3:
6.    movea.w   Disp_OffsetList(pc,d0.w),a1       ; get RAM address for priority level
7.    move.w   (a1),d0
8.    cmpi.w   #object_display_list_size-2,d0           ; is this section full? ($7E)
9.    bcc.s   .full                   ; if yes, branch
10.    addq.w   #2,d0                   ; increment sprite count
11.    move.w   d0,a1                   ; jump to empty position
12.    move.w   a0,(a1,d0.w)                   ; insert RAM address for OST of object
13.  
14. .full:
15.    rts
16. ; ===========================================================================
17.  
18. Disp_OffsetList:
19.    dc.w Object_Display_Lists
20.    dc.w Object_Display_Lists+object_display_list_size
21.    dc.w Object_Display_Lists+(object_display_list_size*2)
22.    dc.w Object_Display_Lists+(object_display_list_size*3)
23.    dc.w Object_Display_Lists+(object_display_list_size*4)
24.    dc.w Object_Display_Lists+(object_display_list_size*5)
25.    dc.w Object_Display_Lists+(object_display_list_size*6)
26.    dc.w Object_Display_Lists+(object_display_list_size*7)
27.    if (*-Disp_OffsetList)/2<>total_object_display_lists
28.    fatal "Mismatch between DisplaySprite and total_object_display_lists."
29.    endif
30. ; ===========================================================================
31.  
32. DisplaySprite2:
33.    moveq   #0,d0
34.    move.b   priority(a1),d0           ; get sprite priority
35.    movea.w   Disp_OffsetList(pc,d0.w),a2       ; get RAM address for priority level
36.    move.w   (a2),d0
37.    cmpi.w   #object_display_list_size-2,d0           ; is this section full? ($7E)
38.    bcc.s   .full                   ; if yes, branch
39.    addq.w   #2,d0                   ; increment sprite count
40.    move.w   d0,a2                   ; jump to empty position
41.    move.w   a1,(a2,d0.w)                   ; insert RAM address for OST of object
42.  
43. .full:
44.    rts

Spoiler: Sonic 2 ASM68K

Code (ASM):

1. ; ---------------------------------------------------------------------------
2. ; Subroutine to add an object to the sprite queue for display by BuildSprites
3. ; DisplaySprite3 is used by multi-sprite objects
4.  
5. ; input:
6. ;   a0 = address of OST for object
7. ;   d0.b = index to priority section (DisplaySprite3 only)
8.  
9. ;   uses d0.w, a1
10. ; ---------------------------------------------------------------------------
11.  
12. DisplaySprite:
13.        moveq   #0,d0
14.        move.b   ost_priority(a0),d0           ; get sprite priority
15.  
16. DisplaySprite3:
17.        movea.w   Disp_OffsetList(pc,d0.w),a1       ; get RAM address for priority level
18.        move.w   (a1),d0
19.        cmpi.w   #sizeof_priority-2,d0           ; is this section full? ($7E)
20.        bcc.s   .full                   ; if yes, branch
21.        addq.w   #2,d0                   ; increment sprite count
22.        move.w   d0,(a1)
23.        move.w   a0,(a1,d0.w)               ; insert RAM address for OST of object
24.  
25.    .full:
26.        rts
27.  
28. Disp_OffsetList:
29.        dc.w v_sprite_queue
30.        dc.w v_sprite_queue+sizeof_priority
31.        dc.w v_sprite_queue+(sizeof_priority*2)
32.        dc.w v_sprite_queue+(sizeof_priority*3)
33.        dc.w v_sprite_queue+(sizeof_priority*4)
34.        dc.w v_sprite_queue+(sizeof_priority*5)
35.        dc.w v_sprite_queue+(sizeof_priority*6)
36.        dc.w v_sprite_queue+(sizeof_priority*7)
37.        if ((*-Disp_OffsetList)/2)<>countof_priority
38.        inform 3,"Mismatch between DisplaySprite and countof_priority."
39.        endc
40.  
41. ; ---------------------------------------------------------------------------
42. ; Subroutine to add a child object to the sprite queue
43. ;
44. ; input:
45. ;   a1 = address of OST for object
46.  
47. ;   uses d0.w, a2
48. ; ---------------------------------------------------------------------------
49.  
50. DisplaySprite2:
51.        moveq   #0,d0
52.        move.b   ost_priority(a1),d0           ; get sprite priority
53.        movea.w   Disp_OffsetList(pc,d0.w),a2       ; get RAM address for priority level
54.        move.w   (a2),d0
55.        cmpi.w   #sizeof_priority-2,d0           ; is this section full? ($7E)
56.        bcc.s   .full                   ; if yes, branch
57.        addq.w   #2,d0                   ; increment sprite count
58.        move.w   d0,(a2)
59.        move.w   a1,(a2,d0.w)               ; insert RAM address for OST of object
60.  
61.    .full:
62.        rts

That should more or less be it. You now have a priority manager that is 16 cycles faster and 52 bytes smaller (the new routine only uses 72 bytes as opposed to 80, and the moveq optimizations free up another 44), all without any RAM modifications! Credit me if you use it, report any issues you discover, and of course, happy hacking!

 

Sonic 2 uses all seven priority levels, so unfortunately it still needs the full sprite queue. RealMalachi's optimization still applies regardless. (Taking a nod from RISC architectures and loading values into a register to perform consecutive operations before writing back to memory always saves a few cycles since we don't have to memory reads/writes for each operation.)

 

Updated with @RealMalachi's optimization and fixed installation instructions (I missed an additional object that load priority values from an array and two others that calculate another object's priority from their own).