0
\$\begingroup\$

I'm using this program called Quadtastic which is a sprite sheet management tool that lets you define quads on a sprite sheet, name them, etc, and export to metadata with those names (+ position, size, etc). It has a feature that automatically numbers selected quads from top left to top right by sorting first by y axis and then by x.

Ideally I want my sprites numbered in this order:

Sprites connected by arrows running rightward along each row, then diagonally down to the leftmost sprite in the next row

However, due to the arbitrary size of the sprites in my sprite sheet, the sprite identified as the top left wasn't the actual top left sprite. Another sprite on the same row had a larger bounding box than it and thus had a lower y position which caused it to get sorted before the actual top left one (which was sorted as 5th)

I tried to modify the source code to try a different algorithm where I sorted by the distance of each quad's top left corner to the top left corner of the minimum bounding box of all the selected quads (a rectangle that encompasses all of them). This somewhat worked and was able to correctly sort the top left sprite as the first but a bunch of others were incorrect.

So, where can I go from here? I can't really think of any other algorithms for sorting. If anyone has any ideas for other algorithms I could try, that'd be great!

And, if anyone is wondering, the code for the sorting can be found here.

If you want to run and test algorithms yourself you need the 32 bit version of Love 10.1. If you get errors about an lfs.dll, take it from the shared folder in the repo and put it in the base directory of 32-bit Love 10.1, where love.exe, is and you should be able to run it.

\$\endgroup\$
0

2 Answers 2

0
\$\begingroup\$

Try something like:

local function sort(quad_a, quad_b)
  return (quad_a.y + quad_a.height) < quad_b.y or (quad_a.y < (quad_b.y + quad_b.height) and quad_a.x < quad_b.x)
end

This sorts A before B if:

  1. A's bottom is above B's top (ie. B is definitely in a lower row), or...

  2. A is not below the bottom of B (if 1 fails and 2 passes, then A and B overlap on the y axis, which we'll take to mean "same row")...

    • ...and A starts to the left of B
\$\endgroup\$
3
  • \$\begingroup\$ This seems to have same issues (quads not numbered properly) but I currently have found a working solution and will be posting my answer in a bit \$\endgroup\$ Oct 29, 2022 at 17:39
  • \$\begingroup\$ This is why I asked you for an example of input that's behaving badly - we can't test proposed solutions without a test case. \$\endgroup\$
    – DMGregory
    Oct 29, 2022 at 18:02
  • \$\begingroup\$ if you stil want to test, you can find the part of the sheet I'm testing with here imgur.com/a/QEUkySz \$\endgroup\$ Oct 29, 2022 at 18:58
0
\$\begingroup\$

I was able to solve this by using Row-major ordering, which you can read more about here. The general gist of how I approached it (at the time I didn't know about row-major ordering) can be seen in this image:

1. Create rows by grouping quads with low difference in height, 2. order rows from top to bottom, 3. order elements in row left to right, 4. place all elements into a single table

This works for pretty much all cases in the sprite sheet I'm using but may not work for all cases (depending on layout of a sprite sheet, size of frames, how close they are, etc). Some edge cases can also be solved by allowing the user to define a threshold when they sort to avoid erroneous detection of rows.

The code is pretty horrendous (performance and quality) and is pretty tightly integrated into this software's codebase. I'll update this post with a link to the code on my fork of quadtastic when I'm happy with the code.

\$\endgroup\$
1
  • \$\begingroup\$ Please embed images here, not linked off-site where the link can rot. Your previous text-based description of your solution was more accessible for users who make use of screen readers or translation software. \$\endgroup\$
    – DMGregory
    Oct 29, 2022 at 23:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .