Game Design, Programming and running a one-man games business…

Something I learned today about STL and Z-sorting…

cliffski

So here is a thing, you might be interested in if you use STL, if you don’t…well sorry :D

if use use the sort()n function thats built into an STL list, it guarantees to preserve the order of identical objects in the list. if you use the vector version, all bets are off.

Bloody hell.

So if you have a bunch of asteroids with these Z values

5,9,3,0,0,0,-2,-5

And you use a list to sort them, all is good in the world. if you use a vector, those 3 asteroids at 0 are going to Z-fight like crazy things.

the solution?

use stable_sort()

well call me mr-picky but I think I’d be happier if stable_sort() was the default, and we actually renamed sort() to be take_your_chances_and_do_random_crap_sort().

I presume stable_sort is slower… Luckily I’m not sorting asteroids every frame (that would be NUTS), and I only sort things when I have to, so it isn’t mega critical. it led to a bug where the biggest hulk chunks from spaceships did Z-fighting if theyu weighed ewnough to all have a Z-speed of zero, and thus a Z position(relative) of 0, so when other objects spinning away caused a z-sort, their order got scrambled. If you are a non coder and don’t know what Z-fighting is, it’s a flickering effect you get in 3D games where two images seem to be undecided about which one is in front. You often see it on ‘decals’ such as blood splats on the floor or posters on a wall. It’s annoying…

7 thoughts on Something I learned today about STL and Z-sorting…

  3. That’s has been one of the sticking point for a long time. And the problem is, I tend to forget about it until I get bit in the arse. Again.

    And you see that everywhere, too, just clicking sort twice on a column header in most games, and things magically change in order.

    And Z-fighting seems to be everywhere.

  4. If you only need to sort by a few bits, radix sort is much better, and preserves order too.

  5. No need to get all sarcastic! This is just a thing you have to know about std::sort. Now you know it so it’s not a problem. Job done!

    Note: std::list is strange in that is has ‘sort’ as a member function which actually behaves like ‘stable_sort’. Other containers don’t do this; it’s list that’s the odd one out. Everything else ‘uses’ the non-member std::sort and friends (which are all worth reading about).

  6. Huh. I gotta admit, I would have been pretty upset when I got into debug mode.

    Ok… There’s my call for sort… Step over…. and…. what the devil just happened? What?! Does sort not mean sort?! A quick Google later and I’m asking myself why sort doesn’t mean sort and what ever happened to the English language and questioning my life decision to become a developer. Is this like when literally started to mean figuratively?

    It’s been a long time since I’ve coded in c++, last time was to make a minesweeper clone, but thanks for sharing. I now know that in some parts of the world sort is a lie and I’ll be on my guard.

  7. One useful trick is that sometimes adding a bit of randomness helps performance. In this case, if the values sorted are Z positions, maybe you could shift them from 0 by a tiny random number. Invisible for the eye, and then all your values are different and problem solved. If being precisely 0 had other purposes, you could use that shift only when sorting.

    I think I once used a similar trick in grid-based pathfinding, where using tiny additional costs gives both an optimization by breaking all the equal cases (where the algorithm must check further to decide the best choice), and also, similar to your case, more stability because when pathfinding in a large uniform grid, there are many different optimal paths, thus any variation changed the path to something completely different. Where if there is only one optimal path (in your case, correct order), alternate solutions will tend to stay close to it.

    Of course, the trick is to have such randomness much smaller than anything relevant to the gameplay.

Comments are currently closed.