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!

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<t[i-1].y do
			t[i],t[i-1]=t[i-1],t[i]
			i-=1
		end
	end
end

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

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.

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.

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.

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.

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.

you could just keep a reference to your player actor:

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

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

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.