How do I fix my qsort() algorithm? It gives different results every time

Question

I'm currently attempting to create a minimal "3D" engine that renders voxels and planes, but I'm having a bit of a hiccup. Right now, I'm trying to make an algorithm that sorts objects based off of their position from the camera. Things further in the back are always drawn first, and if their Z axis (distance directly in front of the camera) is the same, it draws which ever is further away from the center of the screen.

I have a version that I know works on my PC, using both gcc and clang, but as soon as I compile it using the toolchain for the device I'm developing for, it starts glitching out and doesn't do exactly what I want. The output changes every other time. Could I have any pointers as to what I could do to fix it or implement a qsort function separate from the toochain I am using?

// includes

int8_t player_x = 0;
int8_t player_y = 0;
int8_t player_z = 0;


int compareCoordinates(const void *a, const void *b) {

    int8_t *coord1 = (int8_t *)a;
    int8_t *coord2 = (int8_t *)b;
    
    
    if ((coord2[2] - coord1[2]) != 0) {
        return (coord2[2] - coord1[2]);
    }
    
    int value = (abs(coord2[0] - player_x) + abs(coord2[1] - player_y)) - (abs(coord1[0] - player_y) + abs(coord1[1] - player_y));

    if (value == 0){
        return 1;
    }
    
    return value;
}




void sortCoordinateList(int8_t coordinates[][3], int numCoordinates) {

    qsort(coordinates, numCoordinates, sizeof(coordinates[0]), compareCoordinates);
}

int8_t coordinates[][3] = {
        {1, 2, 5},
        {-1, 2, 5},
        {-3, 2, 5},
};

int main(void)
{

    sortCoordinateList(coordinates, LEN(coordinates));
    for (int i = 0; i < LEN(coordinates); i++) {
        dbg_printf("(%d, %d, %d)\n", coordinates[i][0], coordinates[i][1], coordinates[i][2]);
    }
    dbg_printf("\n\n");
}

This is a snippet of the code, removing the moving functions, but this is the main thing. I am fairly new to C programming, but I know that qsort treats items with the same value randomly or something along those lines, called stable sorting, but I am pretty confident that this is not the case.

I tried multiple different ways of debugging and testing, but I am just completely stumped. Usually when I come across an error, I figure it out myself, but I had to cave in and ask my first StackOverflow question. BTW, I've been working on this for at least 13-15 hours between today and yesterday, so yes I have tried everything I can.

Answer 1

This line looks suspicious:

int value = (abs(coord2[0] - player_x) + abs(coord2[1] - player_y)) - (abs(coord1[0] - player_y) + abs(coord1[1] - player_y));

There's 4 expressions in that "value" computation:

• coord2.x - player.x
• coord2.y - player.y
• coord1.x - player.y ????
• coord1.y - player.y

This subexpression: (abs(coord1[0] - player_y) doesn't doesn't seem right. It's subtracing an "x" value with a "y" value.

If I had to guess, you are sorting based on z-depth first. Then as a tie breaker for items on the same z index, sort based on distance from the player's {x,y,z} coordinate.

I think you really want this:

int compareCoordinates(const void* a, const void* b) {

    int8_t* coord1 = (int8_t*)a;
    int8_t* coord2 = (int8_t*)b;

    int8_t x1 = coord1[0];
    int8_t y1 = coord1[1];
    int8_t z1 = coord1[2];

    int8_t x2 = coord2[0];
    int8_t y2 = coord2[1];
    int8_t z2 = coord2[2];

    if (z2 != z1) {
        return z2 - z1;
    }

    int distance1 = (x1 - player_x) * (x1 - player_x) + (y1 - player_y) * (y1 - player_y);
    int distance2 = (x2 - player_x) * (x2 - player_x) + (y2 - player_y) * (y2 - player_y);

    return distance2 - distance1;

    return 0;
}

Where distance1 and distance2 are the "squared distances". No need to take the square root for purposes of computing distance.

None of this explains why you'd be getting different results. That's why I think SPD's answer is likely the source of the bug you are seeing.

Update

To address the issue of sorting "an array of arrays", with qsort, it's helpful to use a typedef:

typedef int8_t COORD[3];

Then your sort function is a quick adjustment;

int compareCoordinates(const void* a, const void* b) {

    COORD* coord1 = (COORD*)a;
    COORD* coord2 = (COORD*)b;

    int8_t x1 = *(coord1)[0];
    int8_t y1 = *(coord1)[1];
    int8_t z1 = *(coord1)[2];

    int8_t x2 = *(coord2)[0];
    int8_t y2 = *(coord2)[1];
    int8_t z2 = *(coord2)[2];

    if (z2 != z1) {
        return z2 - z1;
    }

    int distance1 = (x1 - player_x) * (x1 - player_x) + (y1 - player_y) * (y1 - player_y);
    int distance2 = (x2 - player_x) * (x2 - player_x) + (y2 - player_y) * (y2 - player_y);

    return distance2 - distance1;

    return 0;
}

And then everything else is a quick fix to use the COORD struct

void sortCoordinateList(COORD* coordinates, size_t numCoordinates) {
    qsort(coordinates, numCoordinates, sizeof(coordinates[0]), compareCoordinates);
}

COORD coordinates[3] = {
        {1, 2, 5},
        {-1, 2, 5},
        {-3, 2, 5},
};


int main(void)
{
    sortCoordinateList(coordinates, sizeof(coordinates) / sizeof(COORD));

Answer 2

It's a type-problem, you don't get what you think you get as arguments to the comparison function.

The qsort will use the pointer-to operator & to pass pointers to the elements of the array. If you have an array of arrays of three int8_t elements, the comparison function will get a pointer to an array of three int8_t elements.

The correct type is int8_t (*)[3], not int8_t *:

int compareCoordinates(const void *a, const void *b) {

    int8_t (*coord1)[3] = (int8_t (*)[3])a;
    int8_t (*coord2)[3] = (int8_t (*)[3])b;

    // ...

Answer 3

it draws which ever is further away from the center of the screen.

It addition to others' good answers about array access, I wanted to suggest a compare calculation that does not overflow for any x, y, z, player_x, player_y values.

Code can resort to a wider type or stay within int/unsigned.

#include <inttypes.h>
#include <limits.h>

int8_t player_x = 0;
int8_t player_y = 0;
int8_t player_z = 0;  // Not used

#define uabs(a, b) ((a) > (b) ? \
    (unsigned)(a) - (unsigned) (b) : \
    (unsigned)(b) - (unsigned) (a))
#define cmp(a, b) (((a) > (b)) - ((a) < (b)))

#if LONG_MAX/2/INT_MAX > INT_MAX
typedef long int2x;
#elif LLONG_MAX/2/INT_MAX > INT_MAX
typedef long long int2x;
#else
#error TBD code
#endif

int compareCoordinates(const void *a, const void *b) {
  const int8_t (*coord1)[3] = (void*) a;
  const int8_t (*coord2)[3] = (void*) b;

  // if ((coord2[2] - coord1[2]) != 0) {  // Possible overflow
  if (coord2[0][2] != coord1[0][2]) {  // Avoid overflow
    return (coord2[0][2] > coord1[0][2]) - (coord2[0][2] < coord1[0][2]);
  }

  // int value = (abs(coord2[0] - player_x) + abs(coord2[1] - player_y)) - (abs(coord1[0] - player_y) + abs(coord1[1] - player_y));
  // Each of these 4 have values in the [0...UINT_MAX] range.
  unsigned dx1 = uabs(coord1[0][0], player_x);
  unsigned dy1 = uabs(coord1[0][1], player_x);
  unsigned dx2 = uabs(coord2[0][0], player_y);
  unsigned dy2 = uabs(coord2[0][1], player_y);

#if 0
  // Rather than radial distance (d = sqrt(x*x + y*y)),
  // which rapidly overflows,
  // let us use OP's distance which is like "perpendicular distance"
  // https://en.wikipedia.org/wiki/Perpendicular_distance
  // This allows us not to use a wider type than int/unsigned.

  if (dx2 > dx1) {
    if (dy2 > dy1) {
      return 1; // Both x & y distances of a are more than b.
    }
    dx2 -= dx1;
    dy1 -= dy2;
    return cmp(dx2, dy1);
  }
  if (dx1 > dx2) {
    if (dy1 > dy2) {
      return -1; // Both x & y distances of b are more than a.
    }
    dx1 -= dx2;
    dy2 -= dy1;
    return cmp(dy2, dx1);
  }
  return cmp(dy2, dy1);
#else
  int2x d1squared = (int2x) dx1 * dx1 + (int2x) dy1 * dy1;
  int2x d2squared = (int2x) dx2 * dx2 + (int2x) dy2 * dy2;
  return cmp(d1squared, d2squared);
#endif
}