Musings #1: Spooky Revelations - An adult game about self-discovery

Note: this was originally was posted on TIGForums on Oct 13 2022, that's why the title has a #1. I get good feedback on TIGSource, so I won't stop posting there, but I'll post on itch.io first because it allows me to save drafts.

So, first post of the first game.

Meh. I'm supposed to be interesting.

So!

I'll write a tad about my problem with setting the drawing order of images.

My game is supposed to have a lot of images on top of each other, and at first they were just drawn in order of type (items would be drawn first, then people) and then by creation order (so people created last would get drawn on top of every other person). This was obviously less than ideal.

This is an image of the problem (left), next to the solution (right)

So I looked for sorting algorithms, and with me being a n00b, a simple algorithm would be suitable. So I checked Wikipedia's Sorting algorithm page. A generally fast algorithm is nice but:

• Algorithms can be simpler or more complicated, with complicated algorithms taking more time to implement
• Different algorithms are faster in different conditions
• Some algorithms are stable meaning that things with the same position won't be moved; I'm using floating point for X and Y positions so that's unlikely, but I would want to avoid flickering due to two images being moved towards the front and then towards the back through the frames
• Some algorithms are adaptive meaning that if they are close to be in order, it is faster. Important because between frames most of the time the sorting order will remain the same

I just decided to pick the insertion sort algorithm.

Thanks to Wikipedia's page adding insertion sort was only translating pseudocode to Lua code, and switching from zero-based arrays (in Lua, arrays start at 1).

I did hit a small snag after implementing it... looking at the output numbers everything looked fine, but now some of the drawables were not being drawn. Turns out that I'm sorting by position in the X axis (Y-axis comes later), but I'm sorting by properties of objects, but what I'm sorting are the objects themselves. So I just made a small modification to the algorithm to separate the sorting criteria from what's being sorted:

This is Wikipedia's pseudocode (for zero-based arrays)

i ← 1
while i < length(A)
    x ← A[i]
    j ← i - 1
    while j >= 0 and A[j] > x
        A[j+1] ← A[j]
        j ← j - 1
    end while
    A[j+1] ← x
    i ← i + 1
end while

So at this point mine, because my arrays start at 1 and because I'm sorting objects by their property, is this:

i ← 2
while i < length(A)
    obj_ref ← A[i]
    j ← i - 1
    while j > 0 and A[j].property > obj_ref.property
        A[j+1] ← A[j]
        j ← j - 1
    end while
    A[j+1] ← obj_ref
    i ← i + 1
end while

After that I added the ability to pass an offset function for the sorting criteria, given that I don't actually want to sort by the X and Y axis of the images, because those are at the top left corner; the offset function just adds half width and height so they can be sorted by their center contact point with the floor, not their origin.

That worked well, and after sorting by the X axis, I just repeated the sorting for the Y axis. So yes! Finally no one's feet are on no one's face!

I don't expect a lot of (any?) people to read this, but if you do, know I'll continue posting but it will be erratically at first until I get into an schedule.

Finally, because I copy-pasted the pseudocode from Wikipedia I'm required to talk legalese and say this devlog entry is licensed to the public under the CC-BY-SA 4.0 License.