Sprite Link List
If you've been reading this whole series then by now you should know that I end each article by speculating on what the next will cover. I then follow-up by doing something different. I'm keeping that trend alive once again. In the previous article I said I'd continue to ignore the sprite overlay problem that's been around for a while and instead implement dialogs. As you just guessed, I did exactly the opposite.
I figured this sprite overlay issue was due to my complete lack of understanding about the sprite link list and that it would take a while to fix. I was half right, it turned out to be an easy fix.
I was thinking of making this the intro to a larger piece but decided to make it it's own article because I found it difficult to find documentation on the sprite link list. Don't get me wrong, there's documentation around I just had a hard time deciphering it. That could be my own stupidly, I did flunk out of junior college after all, or maybe it was just hard to digest without a code example. Now poor unfortunate souls Googling for "Sega Genesis sprite link list" can browse to page 3 or 4 of the results and see an article with real code and stuff. I hope both of those people are happy.
Let's start by explaining how this all works... First need to rewind back to the part where we loaded sprites. The Sega Genesis VPD has a region set aside for sprite data. There is an implicit data structure for sprite data that follows a format like:
SPRITE_PLAYER_INIT_X=$0100 ; starting x location of player sprite
SPRITE_PLAYER_INIT_Y=$0100 ; starting y location of player sprite
SPRITE_NPC1_INIT_X=$0180 ; starting x location of player sprite
SPRITE_NPC1_INIT_Y=$00E0 ; starting y location of player sprite
[...]
PlayerSpriteDefinition:
;---------------------------------------------------------------------------
; index + 0 = vertical coordinate
; ---- --yy yyyy yyyy
;---------------------------------------------------------------------------
dc.w SPRITE_PLAYER_INIT_Y
;---------------------------------------------------------------------------
; index + 2 = size (00=8px,01=16px,11=32px)
;---------------------------------------------------------------------------
;----hhvv
dc.b %00000111 ; width=16,height=32
;---------------------------------------------------------------------------
; index + 3 = link field
;---------------------------------------------------------------------------
;-lllllll
dc.b %00000001 ; 1
;---------------------------------------------------------------------------
; index + 4 = priority, palette, flip, pattern
;---------------------------------------------------------------------------
;pccvhnnnnnnnnnnn
dc.w %0110000000000101 ; priority=0,palette=2,vflip=0,hflip=0,pattern=5
;---------------------------------------------------------------------------
; index + 6 = horizontal coordinate
; ---- --yy yyyy yyyy
;---------------------------------------------------------------------------
dc.w SPRITE_PLAYER_INIT_X
NPCSprite1Definition:
;---------------------------------------------------------------------------
; index + 0 = vertical coordinate
; ---- --yy yyyy yyyy
;---------------------------------------------------------------------------
dc.w SPRITE_NPC1_INIT_Y
;---------------------------------------------------------------------------
; index + 2 = size (00=8px,01=16px,11=32px)
;---------------------------------------------------------------------------
;----hhvv
dc.b %00000111 ; width=16,height=32
;---------------------------------------------------------------------------
; index + 3 = link field
;---------------------------------------------------------------------------
;-lllllll
dc.b %00000000 ; 0
;---------------------------------------------------------------------------
; index + 4 = priority, palette, flip, pattern
;---------------------------------------------------------------------------
;pccvhnnnnnnnnnnn
dc.w %0110000001100101 ;priority=0,palette=2,vflip=0,hflip=0,pattern=65
;---------------------------------------------------------------------------
; index + 6 = horizontal coordinate
; ---- --yy yyyy yyyy
;---------------------------------------------------------------------------
dc.w SPRITE_NPC1_INIT_X
When the Sega Genesis VPD draws these sprites sprites it starts with the first sprite (obviously) then goes to the sprite specified by the first sprite's link field and so on. The order the sprites are loaded does not control the draw order. So if you want to make a sprite draw over another you need to either (a) move it to the high sprite plane or (b) set the link field to the desired draw order. (b) is the better of these options because it allows the illusion of multiple sprite layers. Think of a game like Streets of Rage where there are 4-5 sprites that might vertically overlap each other.
To implement this in my tiny demo-ish thing I first needed to add a "sprite zero" that is drawn off-screen. There might be a better way to do this but my thinking went like: if the first sprite in the sprite table is always drawn first then neither the player nor an NPC can be that first sprite or it will always overlap the others. This means I'll be limited to something like 59 on-screen characters at a time which won't be an issue. The other option is having an NPC in every area that hangs around the bottom edge and can never be overlapped. Maybe this is why some RPGs have a "town greeter" fixated by the entrance?
Anyway, here's the new sprite definition:
SpriteZeroDefinition:
;---------------------------------------------------------------------------
; index + 0 = vertical coordinate
; ---- --yy yyyy yyyy
;---------------------------------------------------------------------------
dc.w $0000
;---------------------------------------------------------------------------
; index + 2 = size (00=8px,01=16px,11=32px)
;---------------------------------------------------------------------------
;----hhvv
dc.b %00000000 ; width=8,height=8
;---------------------------------------------------------------------------
; index + 3 = link field
;---------------------------------------------------------------------------
;-lllllll
dc.b %00000001 ; 1
;---------------------------------------------------------------------------
; index + 4 = priority, palette, flip, pattern
;---------------------------------------------------------------------------
;pccvhnnnnnnnnnnn
dc.w %0110000000000000 ; priority=0,palette=0,vflip=0,hflip=0,pattern=0
;---------------------------------------------------------------------------
; index + 6 = horizontal coordinate
; ---- --yy yyyy yyyy
;---------------------------------------------------------------------------
dc.w $0000
So you don't have to hunt this code down in a previous tutorial, here's how sprites are loaded:
VDP_VRAM_WRITE_SPRITE=$78000002
VDP_CONTROL=$00C00004
VDP_DATA=$00C00000
[...]
;-------------------------------------------------------------------------------
; load and setup the sprites
;-------------------------------------------------------------------------------
LoadSprite:
lea SpriteZeroDefinition,a0 ; store address of sprite definition
move.w #$05,d0 ; 1 sprite = 2 longs, 3 sprites = (6-1)
move.l #VDP_VRAM_WRITE_SPRITE,(VDP_CONTROL) ; set write location
LoadSpriteLoop:
move.l (a0)+,(VDP_DATA)
dbra d0,LoadSpriteLoop
When sprites move we need to check if the player sprite has a higher Y value than the NPC sprite and reorder accordingly.
The code to reorder these two sprites isn't complex:
VDP_VRAM_WRITE_SPRITE=$78000002
VDP_CONTROL=$00C00004
VDP_DATA=$00C00000
[...]
MEM_PLAYER_SPRITE_Y=$00FF00018 ; virtual y position of the player
MEM_NPC1_SPRITE_Y=$00FF00026; virtual y position of NPC1 sprite
[...]
OrderSprites:
move.l #VDP_VRAM_WRITE_SPRITE,d5
move.w (MEM_NPC1_SPRITE_Y),d6 ; copy NPC Y to d1
cmp.w (MEM_PLAYER_SPRITE_Y),d6 ; test which is higher
bge.s .1 ; branch if NPC Y > player Y
; NPC Y < player Y -> sprite order is 0,1,2
; sprite zero link field
add.l #$00020000,d5 ; move to index 2
move.w #$0700,d6 ; width=16,height=32 - TODO - derive or constant
add.w (MEM_PLAYER_SPRITE_ID),d6 ; link to npc sprite id
move.l d5,(VDP_CONTROL) ; set write location in VDP (sprite[0] link)
move.w d6,(VDP_DATA) ; store new sprite link field
; player link field
add.l #$00080000,d5 ; move to index 2 of next sprite
move.w #$0700,d6 ; width=16,height=32 - TODO - derive or constant
add.w (MEM_NPC1_SPRITE_ID),d6 ; link to npc sprite id
move.l d5,(VDP_CONTROL) ; set write location in VDP (sprite[0] link)
move.w d6,(VDP_DATA) ; store new sprite link field
; NPC1 link field
add.l #$00080000,d5 ; move to index 2 of next sprite
move.w #$0700,d6 ; width=16,height=32 - TODO - derive or constant
move.l d5,(VDP_CONTROL) ; set write location in VDP (sprite[0] link)
move.w d6,(VDP_DATA) ; store new sprite link field
rts
.1 ; NPC Y > player Y -> sprite order is 0,2,1
; sprite zero link field
add.l #$00020000,d5 ; move to index 2
move.w #$0700,d6 ; width=16,height=32 - TODO - derive or constant
add.w (MEM_NPC1_SPRITE_ID),d6 ; link to npc sprite id
move.l d5,(VDP_CONTROL) ; set write location in VDP (sprite[0] link)
move.w d6,(VDP_DATA) ; store new sprite link field
; player link field
add.l #$00080000,d5 ; move to index 2 of next sprite
move.w #$0700,d6 ; width=16,height=32 - TODO - derive or constant
add.w (MEM_NPC1_SPRITE_ID),d6 ; link to npc sprite id
move.l d5,(VDP_CONTROL) ; set write location in VDP (sprite[0] link)
move.w d6,(VDP_DATA) ; store new sprite link field
; NPC1 link field
add.l #$00080000,d5 ; move to index 2 of next sprite
move.w #$0700,d6 ; width=16,height=32 - TODO - derive or constant
add.w (MEM_PLAYER_SPRITE_ID),d6 ; link to npc sprite id
move.l d5,(VDP_CONTROL) ; set write location in VDP (sprite[0] link)
move.w d6,(VDP_DATA) ; store new sprite link field
rts
Now the sprites are layered as expected when they move around:
This is obviously a brute-force method that only works with these two specific sprites. To make this work for an arbitrary number of sprites we need an algorithm that works for N number of sprites.
For the sake of simplicity let's assume we're dealing with an already sorted NPC list. Since we completely control the order that sprites are loaded this is totally doable. This becomes a tad more complicated if the player sprite has followers like the Phantasy Star games. It's now really clear to me why Square usually uses a single character sprite to represent the entire party. For this iteration let's also go with Square's approach of a single player sprite.
Here's how I think this should work:
1) NPCs are pre-sorted by descending Y value. The reason being that higher Y values correspond to being lower on the screen and therefore having higher priority.
2) Starting with NPC[0], find the first NPC sprite with a lower Y value than the player sprite. Adjust the sprite links to insert the player sprite between this NPC and the one before it.
3) "Sprite zero" will link to the last NPC unless the player sprite has a higher Y value.
We can optimize this a bit by checking the direction the player sprite is moving and then only moving up or down the sprite list accordingly. If the player is moving down (increasing Y value) then the algorithm should work like:
We then need to account for the case when the sprite moves to the highest Y position of all sprites:
Likewise, when the player moves up (decreasing Y value) the algorithm should work like:
So then we need to handle when the player becomes the lowest priority sprite:
The problem with my thinking on this is it's only accounting for the player sprite. An actual implementation of this should work so when any sprite moves we can check if it's:
(a) Now above the sprite it's linking to.
(b) Now below the sprite linking to it
Since the sprite list is a single linked list this is more than trivial to check. I suppose it's too late to ask the engineers at Sega to use a doubly-linked list. It's immediately obvious why this is a problem for (b), but even shifting a sprite up in the list hits this challenge:
Shifting down is easier in a trivial case but harder in a complex one:
I think I'll wait until I have more sprites to implement this...
Other Notes
The priority flag on the sprite didn't help with this problem at all. When I first looked at this I thought a really simple solution would be to set this flag to 1 for all sprites with a higher Y value than the player sprite. After reading a few different sources I was wrong in my understanding of the priority flag. It's used to determine which sprites are drawn when more than 20 are drawn on the same line. I doubt I'll hit this problem.
It would be a fun exercise to implement quicksort in 68000 assembler but for now it's not necessary. It will be a while, possibly never, before I have more than 10 or so sprites walking around. For a list of 10 or fewer items the difference between this insertion sort like approach and quicksort isn't huge. This is especially true if the sprites are already loaded in sorted order which we can do. In this case, insertion sort is faster and we don't need to worry about the memory allocation required for quicksort. Also since we're not moving objects around, only updating pointers, we are better off sticking with in-place sorting algorithms even if they are less efficient on the CPU side.
Bonus: Memory Map Generation
Early on one slightly annoying thing was keeping track of the memory map. Part of the old-school programming experience is dealing with manual memory management. To help with this I created a giant list of constants to keep track of the memory map:
MEM_DEBUG_1=$FF00000 ; general debug register
MEM_DEBUG_2=$FF00002 ; general debug register
MEM_VBLANKFLAG=$FF00004 ; indicates whether vblank in-progess
MEM_VBLANK_COUNTER=$FF00006 ; incremented at vblank - used for debug & RNG
[...]
MEM_OBJECT_LIST_OBJS=$FF0004E ; list of objects in current map
MEM_OBJECT_LIST_NPCS=$FF0008A ; list of npcs in current map
MEM_COLLISION_DATA=$FF000C6 ; collision data for the current map
The address values are based on the address of the previous item plus the size (number of bytes) of the previous item. That's easy to track if nothing is ever moved or inserted in the middle or resized. To get around that I kept the values in a LibraOffice spreadsheet. That was convenient for a short time but I really didn't want to make LibraOffice part of the build tools so I converted that sheet to a CSV:
MEM_DEBUG_1,2,general debug register
MEM_DEBUG_2,2,general debug register
MEM_VBLANKFLAG,2,indicates whether vblank in-progess
MEM_VBLANK_COUNTER,2,incremented at vblank - used for debug & RNG
[...]
MEM_OBJECT_LIST_OBJS,60,list of objects in current map
MEM_OBJECT_LIST_NPCS,60,list of npcs in current map
MEM_COLLISION_DATA,256,collision data for the current map
And then wrote a small Java class to convert this to a list of constants the assembler can understand:
public class CSVMemoryMap{
private static final String newLine=System.lineSeparator();
private static final String delimiter=",";
public static void main(String[] args){
String defaultBaseAddress="0FF00000";
BufferedReader bufferedReader=null;
OutputStreamWriter outputStreamWriter=null;
int lineNumber=0;
String currentLine=null;
try{
if(args.length<2){
throw new Exception("Expecting two required arguments: sourcefile outputfile");
}
String sourceFile=args[0];
String outputFile=args[1];
String currentAddressHex=defaultBaseAddress;
if(args.length>2){
currentAddressHex=args[2];
}
int currentAddressInt=Integer.valueOf(currentAddressHex,16);
bufferedReader=new BufferedReader(new InputStreamReader(new FileInputStream(sourceFile)));
outputStreamWriter=new FileWriter(outputFile);
while((currentLine=bufferedReader.readLine())!=null){
lineNumber++;
String[] split=currentLine.split(",");
if(split.length!=3){
throw new Exception("Invalid length in line "+lineNumber+" expected 3 actual "+split.length);
}
StringBuffer stringBuffer=new StringBuffer();
stringBuffer.append(split[0]);
stringBuffer.append("=$");
stringBuffer.append(Integer.toHexString(currentAddressInt).toUpperCase());
stringBuffer.append("\t; ");
stringBuffer.append(split[2]);
stringBuffer.append(newLine);
outputStreamWriter.write(stringBuffer.toString());
int size=Integer.parseInt(split[1]);
currentAddressInt+=size;
}
}
catch(Exception x){
if(lineNumber>0){
System.out.println("Error in line: "+lineNumber);
}
if(currentLine!=null){
System.out.println("Current line: "+currentLine);
}
x.printStackTrace();
}
finally{
try{
if(bufferedReader!=null){
bufferedReader.close();
}
}
catch(Exception x){}
try{
if(outputStreamWriter!=null){
outputStreamWriter.flush();
outputStreamWriter.close();
}
}
catch(Exception x){}
}
}
}
I figure I already have one build tool in Java, for the collision maps, so adding another doesn't introduce a new technology to the stack. Also I suspect I'll build quite a few other helpers like this over time.
Download
Download the latest source code on GitHub
Related
