2

Hi,

I'm trying to have a sprite move in front of and behind other objects to simulate z-index ordering, but I'm not sure how to do this in PICO-8. I figured it would work something like if object_a.y > object_b.y, move behind that object.

I saw somewhere someone giving each object/sprite a "z" variable that would control what order things were drawn, but that wasn't for PICO-8 so I don't know if that could be recreated here.

After some searching, I see that this has been done in The Lair and Kick Wizards, but I'm very new to Lua/PICO-8 so I'm having a hard time finding how they're doing it. Any help is greatly appreciated.

The Lair: https://www.lexaloffle.com/bbs/?tid=4051
Kick Wizards: https://www.lexaloffle.com/bbs/?tid=27697

Thanks!

P#35146 2017-01-07 07:38 ( Edited 2017-01-09 17:25)

1

if you have an indexed sprite object list, you could just sort it and boldly draw it:

 ```function isorty(t) --insertion sort, ascending y for n=2,#t do local i=n while i>1 and t[i].y

isorty(spritelist)
for s in all(spritelist) do spr(s.num, s.x,s.y) end

P#35151 2017-01-07 09:23 ( Edited 2017-01-07 14:24)

ultrabrite's answer is basically it: you have to manually sort your objects by their Z coordinate, and then draw them in that order.

This is basically what Lair does, with a tweak. Instead of sorting, Lair just puts everything into a table keyed by Y, something like this (pseudocode):

 ```ordered={} for obj in all(objs) do ordered[obj.y] = ordered[obj.y] or {} -- ensure table is there add(ordered[obj.y],obj) end for i=0,127 do -- or whatever your min/max Y is for obj in all(ordered[i]) do draw(obj) end end ```

If you have a lot of moving objects, this should be faster than sorting. If you decide to keep a sorted list instead, consider using a fast and stable sorting algorithm, like a merge sort.

P#35178 2017-01-07 16:42 ( Edited 2017-01-07 21:42)

Re: fast sorting algorithm --this is the function I use, mostly stolen from Lua's standard quicksort:

 ```function zsort(arr) function comp (a, b) return a.z>b.z end function partition (a, lo, hi) pivot = a[hi] i = lo - 1 for j = lo, hi - 1 do if comp(a[j],pivot) then i = i + 1 a[i], a[j] = a[j], a[i] end end a[i + 1], a[hi] = a[hi], a[i + 1] return i + 1 end function quicksort (a, lo, hi) if lo < hi then p = partition(a, lo, hi) quicksort(a, lo, p - 1) return quicksort(a, p + 1, hi) end end return quicksort(arr, 1, #arr) end ```

Note the internal function "comp", which you would rewrite for your needs. Here I'm sorting my table of objects by greatest Z-value first—because if I just draw the table in order, the closest objects will be drawn last, i.e. on top of objects that are farther away.

krajzeg's method of building a new table keyed by depth every frame is very clever though--for most applications, that's definitely the best way.

P#35182 2017-01-07 17:18 ( Edited 2017-01-08 00:33)

Quicksort (specifically this implementation of it) is actually an example of a poor algorithm to use in this situation.

When sorting each frame, your object list will be mostly in the right order - with the exception of new objects, or objects that moved in the Z-order.

Quicksort is a good algorithm, but it's really slow on "mostly sorted" arrays when you pick the first/last element as a pivot. One partition (in your example code, less-than-pivot) will be very large, while the other (greater-than-pivot) will be very small, causing quicksort to approach it's O(N^2) worst case scenario.

Hence my suggestion of a merge sort, but insertion sort lie ultrabrite suggested is simpler to implement, and also performs well if there are few new objects each frame.

P#35263 2017-01-08 13:38 ( Edited 2017-01-08 18:38)

Ooops—that's a good point. Yes, I forgot why I was using quicksort, which was to sort transformed 3D triangles by distance from the camera. Because it's difficult to make assumptions about the state of sorted-ness in the next frame—and also desirable to omit certain triangles if they end up facing away from camera—I do not sort a list in place, but rather rebuild the drawlist every frame and quicksort it.

Leaving it up in case it's useful for anyone in a similar situation—but yes, insertion sort profiles much better in a "2.5D" case where the list does not grow or shrink much every frame.

P#35286 2017-01-08 18:38 ( Edited 2017-01-08 23:55)

Ultrabrite's suggestion seems to have worked. Thank you so much.

I am still trying to wrap my head around it and am having to refactor a lot of my code to accommodate this (I made the player a global object instead of spawning it in the same manner as the rest of the objects, which all get added to an actors {} (see https://www.lexaloffle.com/bbs/?tid=28500 for an example of what I'm talking about), which is then sorted using ultrabrite's code.

I may have more questions but I really appreciate the feedback.

P#35310 2017-01-09 02:38 ( Edited 2017-01-09 07:39)

you could just keep a reference to your player actor:

function spawn_actor(name)
local obj={}
obj.name=name
...
return obj
end

for i=1,30 do spawn_actor('npc') end
player = spawn_actor('player')

P#35336 2017-01-09 09:15 ( Edited 2017-01-09 14:15)
:: fweez

Just to confirm you're on the right track (or at least the same track I took), sort-then-drawing an actor list is how Kick Wizards works as well. Everything drawable is in that list, and then there are other sublists of some objects I need to treat differently -- monsters, players, scenery.

I am pretty sure that my choice of heapsort to sort the drawables list was simply because it was on the bbs and I was feeling lazy, so don't blindly copy my choice there.

P#35356 2017-01-09 12:25 ( Edited 2017-01-09 17:25)