I'm working on something with lots of overlapping sprites, that need to be drawn in the correct order. After my failed attempts at implementing quicksort, I found a thread suggesting Z values could be used as keys in a table. My table of sprites will be rebuilt every frame, so the plan is to insert sprites at specific positions in the table once they're created. This way, I should hopefully be able to iterate over the table with a for loop without sorting it at all. Unfortunately, I wasn't able to figure the last part out.
table={} add(table, 10, 1) add(table, 20, 2) add(table, 15, 1.5) add(table, 27, 2.7) for i in all(table) do print(i) --[[ 15 27 10 20 ]] end print(table[1.5]) --[nil] print(table[1]) --15 |
As a test, I tried something like this, only to realize add()
floors your input keys, and ignores the keys of previously added items. What I really need for this to work, is a way to add a key and value to a table directly, and a way to stop PICO-8 treating my numerical keys like a sequence. I've tried adding items the way you would with string keys, but it didn't work.
table={ 1 = 10, 1.5 = 15, 2 = 20, 2.7 = 27 } --[[ syntax error line 1 (tab 0) table = { unclosed { ]] |
The syntax error probably has something to do with the fact that variable names can't start with a number; however, even if it worked the way I want it to, this method wouldn't allow me to add new items to the table. If my ramblings haven't been very clear, here's some pseudocode to explain my desired result:
table={} for i=1, spriteamount do --Every frame, sprites are added to the table local sprite={ x = somexvalue, y = someyvalue, otherproperty = example } --Add the sprite to the table, with the z as its key somemagicaladdfunction(table, sprite, z) end --[[ Once the table is fully populated with sprites, we can iterate over them in _draw(). If everything works as planned, the table will iterate from lowest to highest z. ]] |
I'm sure there's some PICO-8/Lua knowledge I'm missing, but on the other hand, what I'm trying to do may be impossible. I'd greatly appreciate any help in determining whether I can achieve this or I need to give quicksort another try :)
![](/gfx/set_like0.png)
![](/gfx/top_drop.png)
![](/media/92447/Logo.png)
You can fix the syntax error by doing
table={ [1] = 10, [1.5] = 15, [2] = 20, [2.7] = 27 } |
and you can add keys to a table by doing
table[z] = sprite
![](/gfx/set_like0.png)
![](/gfx/top_drop.png)
![](/media/85395/picocolordance_24.gif)
Take a look at https://www.lexaloffle.com/dl/docs/pico-8_manual.html#Table_Functions and specifically, the warning:
- With the exception of PAIRS(), the following functions and the # operator apply only to tables that are indexed starting from 1 and do not have NIL entries. All other forms of tables can be considered as hash maps or sets, rather than arrays that have a length.
Note that the caveat also applies for non-integers as they are considered keys rather than indices. You can use pairs()
(as described shortly below that) to iterate through all values in the table, but note that order is not guaranteed so you may still need to sort them yourself.
![](/gfx/set_like0.png)
![](/gfx/top_drop.png)
![](/media/45608/2_rgbg_avatar.png)
Okay, so the comments have addressed how using tables works, so I'll address the other issue with your idea: each key can only have 1 value. This means that using the z positions as keys would require either the values to be nested tables or that every sprite have a unique z position.
I'm not an expert in sorting or such. However, it seems like the first thing to try in your case would be the easiest form of sorting. That way you can check if you even need quicksort. If that's too slow, there's also the option of seeing if there's some consistent pattern to the z positions of your sprites so that you can order groups of sprites first and then order the individual sprites later. Alternatively, if you happen to know of any sprites that aren't going to overlap, you can be sloppy about your sorting.
![](/gfx/set_like0.png)
![](/gfx/top_drop.png)
![](https://www.lexaloffle.com/bbs/files/32759/comovic.gif)
I recommend using the z parameter honestly.
I will share my favorite sort.
function quicksort(v,s,e) if s < e then local p=s for i=s+1,e do if v[i].z < v[s].z then --asc --if v[i].z > v[s].z then --desc p+=1 v[p],v[i]=v[i],v[p] end end v[s],v[p]=v[p],v[s] quicksort(v,s,p-1) quicksort(v,p+1,e) end end -- v: Table containing z { {id=10, z=1}, {id=20, z=2}, {id=15, z=1.5}, ... } -- s: Start index -- e: End index -- Example usage: quicksort(table,1,#table) |
![](/gfx/set_like0.png)
![](/gfx/top_drop.png)
![](/media/82211/7_realshadowcaster.png)
Sort by z seems to be exactly what you need (qsort by @Felice)
-- a: array to be sorted in-place -- c: comparator (optional, defaults to ascending) -- l: first index to be sorted (optional, defaults to 1) -- r: last index to be sorted (optional, defaults to #a) function qsort(a,c,l,r) c,l,r=c or ascending,l or 1,r or #a if l<r then if c(a[r],a[l]) then a[l],a[r]=a[r],a[l] end local lp,rp,k,p,q=l+1,r-1,l+1,a[l],a[r] while k<=rp do if c(a[k],p) then a[k],a[lp]=a[lp],a[k] lp+=1 elseif not c(a[k],q) then while c(q,a[rp]) and k<rp do rp-=1 end a[k],a[rp]=a[rp],a[k] rp-=1 if c(a[k],p) then a[k],a[lp]=a[lp],a[k] lp+=1 end end k+=1 end lp-=1 rp+=1 a[l],a[lp]=a[lp],a[l] a[r],a[rp]=a[rp],a[r] qsort(a,c,l,lp-1 ) qsort(a,c, lp+1,rp-1 ) qsort(a,c, rp+1,r) end end function somemagicalfunction(x,y) -- return abs(x-y return ((x-64)>>16)^2+((y-64)>>16)^2 end while true do cls() spriteamount=1000 table={} for i=1, spriteamount do --every frame, sprites are added to the table local sprite={ x = flr(rnd(128)), y = flr(rnd(128)), sp = flr(rnd(8)) } sprite.z=somemagicalfunction(sprite.x,sprite.y) add(table,sprite) end -- sort array by z qsort(table,function (a,b) return a.z<b.z end) -- display the sprites in sorted order for i=1,#table do --print(table[i].z) spr(table[i].sp,table[i].x,table[i].y) end print"press ❎ to retry" while not btnp(❎) do flip() end end |
![](/gfx/set_like0.png)
![](/gfx/top_drop.png)
![](/media/82039/2_profile.png)
Thanks so much for the help, everyone. It's unfortunate there's no magical solution but at least I know where to get started. I also appreciate the code snippets, hopefully I'll be able to figure out where I went wrong last time. Thanks again for the support!
[Please log in to post a comment]