I've seen a few folks discuss here how they've handled ordering their objects, mostly in terms of how flickering is handled and whatnot. I'm looking conceptually for a processor-efficient way to order objects based on their y value to suggest 2.5d depth. I feel like mechanically, I've developed a pretty good engine for this, but visually, it's still all sorts of funky.
Right now my engine has object slots and they are static, and the drawing runs through objects 0-n. Also, unfortunately, I had been drawing the player and 'player objects' separately from other game objects.
I suppose what I'd have to do is use the same functions to get the necessary values, however make a single drawing routine that includes all objects to be drawn (and not have player objects and monster objects separate). It's a headache to think about recoding that, but I can at least conceive of that part of it. I'm trying to figure out the most efficient way, though, to populate some sort of array to determine the order in which the objects should be drawn. I can think of a few very long ways, but I'm wondering if anyone has any suggestions on an efficient way to do this?
The tough part about creating sprite layers on the NES is that the frontmost objects could end up causing sprites behind them to flicker a lot or even disappear. Sorting by the Y coordinate is not the hard part, balancing the layering and the flickering is... see, you need the flicker/cycling so that no object becomes invisible for several consecutive frames, but it directly negates the layering effect if two overlapping objects have their priorities cycled.
Maybe the answer is to detect which objects overlap (maybe you already have this information from the collision detection part of the engine), and make sure that groups of overlapping objects are rendered with the correct priority based on their Y coordinates, but still randomize the priority between different groups and single objects.
I've seen this suggested while perusing the forums, perhaps by you even. I foresee a slight problem with that with the way I handle actual object-to-object collision currently. Imagine a '1 unit tall' object behind the top of a '4 unit' tall object. They don't and shouldn't collide. Collision would not be detected in this case (and as written mechanically, do not collide). This is how my current collision detection works...essentially, utilizing a quasi 2.5d bounding box. However, these sprites DO collide visually, which is the exact nature of the issue, as if the 1 unit overlaps the sprite of the 4 unit, it looks like the object is flying (if you can picture this in your head).
This would seem to suggest a separate collision detection method for just this purpose to determine whether the sprite as a whole is sharing space with another sprite as a whole, and if so, re-order. That's one of the methods I considered, but it seemed that it would be excruciatingly long for each object do a second collision detect against all other objects, then also to re-order, storing in the correct index spot to be drawn.
Am I understanding that?
2.5 d?
Do you mean an object which is sometimes in front of the hero and sometimes behind the hero, depending on his y coordinate? I don't think I've ever seen that done in an NES game. Definitely you will have to reorganize sprite priorities dynamically.
Doug - yes. And it was done plenty in NES titles (think of beat em ups, for an example, even though my game is not a Beat em up).
Functionally, with a little tweaking, I think it actually works pretty good. But the graphic issue definitely will be a problem.
Yeah, I've got to figure out a system of dynamic prioritizing for the drawing. That's exactly it. Looking for quick methods.
It's true, a visual overlap can be different from a logical overlap depending on the game, and handling all those collisions plus the sorting does sound very inefficient.
I just came up with an idea that hopefully isn't so slow:
Try representing the groups of objects as linked lists. For each group, a byte indicates which object is the first in that list, and then each object has a byte indicating which object is the next. Linked lists are good because you can easily insert and move items around without having to rewrite the entire list.
Something simpler than the typical collision detection could be used to decide whether to group objects together, like horizontal collision only, which will create groups arranged like vertical stripes. This might affect how the sprite cycling looks (e.g. sprites on the left side of the screen will alternate with sprites on the right side), but hopefully it won't look bad. You could maybe just compare the X coordinates and group the objects when the difference is below a certain threshold. Not as precise, but might be a good enough approximation. This will require some experimentation.
Anyway, so you start with no groups at all. Start testing the objects for horizontal proximity using whatever method you see fit, and group them when they're found to be horizontally overlapping/close. Check if either of the objects that are deemed close already belong to a group (each object would need to remember the index of the group they belong to). If so, add the object that doesn't have a group yet to the group the other object belongs to, by making it the first, and having it point to the old first as the next entry in the list, effectively making that the second entry. If neither object belongs to groups, create a new group and insert both objects in it. Now, if the 2 objects belong to different groups, you have to merge the groups by making the last element of one of them point to the first element of the other, and then kill the list that became empty.
Then you sort the objects of each group according to their Y coordinates, and finally render the groups to OAM in random order, to cycle priorities across them.
After having written this, I see that it doesn't sound efficient at all, and the horizontal proximity thing won't do any good if many objects are gathered in column formations, because the ones in the back/top will simply vanish when there are too many sprites.
I believe tepples had a good solution for this problem, maybe we should search for that.
How many cycles would it take to create an array of all sprite objects and simply bubble sort them by y coordinate? That wouldn't resolve flickering, though. Maybe, after that, separate them into groups (by y) and shuffle them randomly within the group.
I am doing this in my game. I sort the sprites with a simple insertion sort. It is quick since my objects will be mostly sorted every frame anyways. If I detect any sprite overflows (yeah I know it's supposed to be buggy, but it works good enough in my case) I have four different predetermined orders I draw the objects in that I cycle through. It looks OK, and the list of objects is kept sorted so I won't need a big heavy sort when the overflow is over. The flicker is not too bad, it really depends on the design of the game. Try and make it so that loads of objects don't often line up.
Here is a video I made with 15 characters on screen ordered by Y coordinate with the method described above. Still some crap to figure out, but it's good enough that I can move on to other parts of the game. Maybe I'll revisit the sorting/flickering later on.
https://www.youtube.com/watch?v=wYrYlWcRtjg
Great example. That would suit the purposes just fine. I'm curious how to code an insertion sort in asm. Completely get the concept of shifting array values after a compare, but am trying to do it as efficiently as possible, and never really thought it out in ASM...
Anyone offer any tips before I dive in and make a bigger mess than is necessary? Haha
Insertion sort should be fairly efficient to implement if the elements are in a linked list, because you don't need to shift lots of elements around to perform an insertion. You can probably make sure each object is in the correct position in the list every time it moves, so you don't have to sort the whole thing every frame.
Gnome sort is a conceptually easy to understand visual model of insertion sort. Think of a garden gnome sorting flower pots: he would look at a pair, swap them if they're out of order, keep backing up and swapping until they're in order, and then run back past the sorted pairs to move the next pot into place.
Code:
Start with here = 0 and all_seen = 0.
While all_seen + 1 < length:
If item[here] and the next item are in the correct order:
Go to the next unseen pair (add 1 to all_seen, then set here to all_seen).
Else:
Swap them.
If there is a previous pair (here > 0):
Go to the previous pair (subtract 1 from here).
Else:
Go to the next pair (add 1 to all_seen, then set here to all_seen).
The details in parentheses are for an array list. With a linked list, you'd replace "subtract 1" and "add 1" with "follow the previous link" and "follow the next link".
Implement gnome sort on an array, and you can proceed to optimize it into
Shell sort (decreasing gap insertion sort) if you need to move pots large distances.
The advantage of insertion sort is that you can insert objects into the list one at a time. If you have a mostly sorted list from last frame, it is quick to insert a couple of changes into it. If you have to re-sort the whole list every frame, maybe it's a different problem. Also, if the list is small, the algorithmic complexity of the sort is probably not very relevant. O(N^2) isn't necessarily worse than O(N log N) if N is small and the O(N log N) takes more work per N.
The variation of an insertion sort I'd suggest:
1. Move an object, updating its Y coordinate.
2. Sort that object into its correct place, by moving it left or right in the list
3. Repeat step 1 for each object.
As long as the objects are still sorted from the previous frame before you start moving them around, each individual sort within the list should only have to move a short distance. If the Y sort list is a linked list within the objects, it should be a rather quick operation.
For the first frame, just insert objects one by one at position 0 (and move right until it's in the correct place). After each insertion, the list will be sorted again, ready for the next insertion. If you add a new object at some later frame, just insert it at position 0 (or any convenient position; e.g. you could insert it after the object that spawned it).
You guys are awesome. I really do need some help with this routine. Again, I'm understanding the concept alright, and I successfully prepped my object drawing routine to draw based on moveable indexed values, but still having a hard time with the actual sorting.
I've got an array drawOrder. It holds values 0-0F and is populated upon init with those successive dummy values.
Each respective object's y values is determined by objectY_hi,x.
I understand that I should be loading objectY_hi,0 and checking it against the rest, then continuing, checking objectY_hi,1 against those that follow, etc. But I'm not sure the best way to do a direct compare, nor how to move all of the values. I've tried some messy things with populating some temp variables and using them to shift values around, but keeps making my head spin.
Wrapping what I've tried around a higher level language, it might look something like this:
Code:
if (objectY_hi[var] > objectY_hi[var+1])
{
var2 = objectY_hi[var]
var3 = objectY_hi[var+1]
objectY_hi[var]=var3
objectY_hi[var+1]=var2
}
etc etc etc. Again, to me, this seems super convoluted, especially considering the twists to get something like objectY_hi[var+1] ... not quite as simple in ASM, especially considering having to use the registers to identify placement in the array. Any and all help is greatly appreciate!
I'm absolutely sure there is a simpler way, and a better way to do this in ASM.
I would most likely use a
doubly linked list, using indices to your object arrays instead of pointers.
The advantage of the linked list is that you don't move any object data around. Your objects stay where they are in the memory array, and you just update the link indices when you're sorting the objects around.
Depends on the list size, though. If the list is small, I might just use an array of indices instead.
Sounds reasonable. Again, though, having a rough time translating the concept from high level into ASM. It's definitely my higher level thinking getting in the way, but I haven't found any references for doing something like this specifically for nes development. Might benefit folks like me to see an example?
In the meantime I'll keep noodling. Thanks!
** my tragically ugly and non-working attempt looks something like this**
Code:
SetObjectOrder:
LDX #$00 ;; load 0 into x
OrderLoop:
LDY drawOrder, x ;; now y represents the value of
;; the first value in the array
Cycle:
LDA objectY_hi, y ;; get the y value of first array object
STA temp ;; store it
INX
LDY drawOrder, x ;; one value higher in store array
LDA objectY_hi,y ;; get y value of next array object
CMP temp ;; compare it against first
BCS doneWithSwapItem ;; if it's in right order, do nothing
LDA drawOrder, x ;; otherwise, load 'higher' draw order value
STA temp2 ;; store it
DEX
LDA drawOrder, x ;; load 'first' draw order value
STA temp3 ;; store it
;; now we can swap them
LDA temp2
STA drawOrder, x ;; now 'higher draw order value'
;; is in 'first draw order' spot
INX
LDA temp3 ;; and the 'first draw order value'
STA drawOrder, x ;; is in the 'higher draw order' spot
doneWithSwapItem:
;; in either case, whether or not swap happened,
;; x is now the 'higher' swap value
CPX objectCount
BNE OrderLoop
RTS
This is the sort of method I've tried (and modified to try other things). I'm not married to anything like this, it's just how my brain is thinking out the process. Would really love a better example at approach for sure! Thanks.
This is a rough idea of how I'd implement what I was suggesting:
Code:
; Three functions:
; sort_init
; sort_insert (X = ID of object to insert)
; sort_object (X = ID of object to re-sort)
;
; 1. call sort_init to build the sorted list the first time after setting up your objects
; 2. if you create a new object later, immediately call sort_insert to add it to the list
; (do not add or move any other objects before doing this)
; 3. if you ever move an object, imediately call sort_object to re-sort the list
; (do not add or move any other objects before doing this)
;
; naming convention:
; object ID = index within object data
; draw list index = index within drawOrder list (i.e. drawOrder is a list of IDs)
; RAM
; object data
MAX_OBJECTS = 16
object_on: .res MAX_OBJECTS
objectX_hi: .res MAX_OBJECTS
objectX_lo: .res MAX_OBJECTS
objectY_hi: .res MAX_OBJECTS ; we will sort on this
objectY_lo: .res MAX_OBJECTS
; ... etc.
; draw list for objects
drawCount: .res 1
drawOrder: .res MAX_OBJECTS
; temporary storage, probably should go in the zero page
temp: .res 1
; CODE
; call this to build the entire sorted list from scratch
.proc sort_init
; empty the sorted list
ldx #0
stx drawCount
@loop:
; insert each active object, one at a time
tax
lda object_on, X
beq :+
txa
pha
jsr sort_insert
pla
tax
:
inx
cpx #MAX_OBJECTS
bcc @loop
rts
.endproc
; adds one new object to the draw list
; call when a new object has just been spawned
; also called internally
;
; X = ID of object to insert
.proc sort_insert
; add to end of list
txa
ldx drawCount
inc drawCount
sta drawOrder, X
; sort into correct place
jmp sort_
.endproc
; re-sorts an object already in the list (call immediately after moving it)
;
; X = ID of object to sort
.proc sort_object
; finds the object in the list
txa
ldx #0
:
cmp drawOrder, X
beq sort_
inx
cpx #MAX_OBJECTS
bcc :-
; not found
rts
; maybe want to TAX and jmp sort_insert here instead of rts?
; (you could then call sort_object instead of sort_insert,
; and not have to worry about accidental double-insertion)
.endproc
; internally called by functions above, re-sorts an object already in the list
; for this to function correctly, the entire list (except this object)
; must already be in sorted order.
;
; X = draw list index of object to sort
.proc sort_
ldy drawOrder, X
lda objectY_hi, Y
sta temp ; temp = thisY
; at left edge of list, can only sort to the right
cpx #0
beq sort_right_
; at right edge of list, can only sort to the left
inx
cpx drawCount ; X+1 compared to drawCount
dex ; note, DEX does not affect carry flag
bcs sort_left_
; determine which direction to sort the object:
; if rightY < thisY, can only sort to the left
inx
ldy drawOrder, X
lda objectY_hi, Y
dex
cmp temp
bcc sort_left_
; otherwise sort to the right
jmp sort_right_
.endproc
; called internally by sort, moves object left until sorted
;
; X = draw list index of object to sort
; temp = objectY_hi of object to sort
.proc sort_left_
cpx #0
bne :+
; X == 0, already at edge of list
rts
:
dex
ldy drawOrder, X
lda objectY_hi, Y
cmp temp
bcc :+
; leftY >= thisY, we're in the correct place
rts
:
; swap to the left, then continue
; (note at this point X -> X-1, see DEX above)
tya
pha
lda drawOrder+1, X
sta drawOrder+0, X
pla
sta drawOrder+1, X
jmp sort_left_
.endproc
; called internally by sort, moves object right until sorted
;
; X = draw list index of object to sort
; temp = objectY_hi of object to sort
.proc sort_right_
inx
cpx drawCount
bcc :+
; X+1 >= drawCount, already at edge of list
rts
:
ldy drawOrder, X
lda temp
cmp objectY_hi, Y
bcc :+
; thisY >= rightY, we're in the correct place
rts
:
; swap to the right, then continue
; (note at this point X -> X+1, see INX above)
tya
pha
lda drawOrder-1, X
sta drawOrder-0, X
pla
sta drawOrder-1, X
jmp sort_right_
.endproc
Wrote this quickly, haven't tested or anything, but I hope it's correct enough + the comments should explain the intent. It starts with an insertion sort, and from there you can incrementally insert or re-sort objects in the list.
In the >= cases in sort_left_ and sort_right_, you could also test for == and give that a random chance to continue or not, which could give you some primitive OAM cycling for things that are on the same Y co-ordinate.
A game using a semi-overhead view, such as
Zelda or
Smash TV, needs to sort sprites by their Y coordinate so that sprites lower on the screen appear in front of sprites higher on the screen. Because sprites' Y coordinates don't change much from one frame to another, it's helpful to use sorting algorithms that work well with already sorted data. If CPU time is especially tight, as it may be on 8- or 16-bit platforms, algorithms that take linear time but produce momentary incorrect results may be acceptable.
- Bubble sort compares adjacent elements on each pass, except it's slow at handling "turtles", which are elements at the end of the list that should be placed near the start. If you use one pass of bubble sort, place new objects entering a scene at the start.
- Insertion sort, which I illustrated above with the garden gnome analogy, is a good all-purpose choice for mostly sorted data, but I don't see how it can be made approximate. Limiting swap distance to 1 makes it equivalent to a pass of bubble sort.
- Cocktail sort is bubble sort that alternates forward and backward directions on each pass, eliminating the turtle problem.
- Comb sort is a variant of bubble sort that compares elements a certain gap distance apart, with this gap decreasing by about 25% each pass.
I propose using forward bubble sort at gap 1 and reverse bubble sort at gap 2 or 3, alternating between the two strategies frame by frame. This combines the good parts of comb sort and cocktail sort, quickly handling small movements of one sprite past a small number of others as well as large movements of one or two sprites in either direction. In frames using the reverse sort, the comparison function could be weakly randomized for sprites that are close enough to vertically overlap but twice too far to horizontally overlap. This would produce both correct vertical ordering for overlapping sprites and randomized flickering for sprites that do not overlap but occupy the same scanline. But because it compares non-adjacent elements, it needs an array list to hold the ordering instead of a linked list.