Need to sort one dimension of an array in C and store the order

Question

I need maybe two arrays to store values and quickly have access to them being sorted.

For example float scan_fraction[4][2] as the main array and int fraction_order[4] as a order storage. The point is so I can use the order array to quickly access directions with highest values.

In the first dimension I store direction info, like fraction[FR_LEFT][VALUE] and fraction[FR_LEFT][FR_ENABLED]

In the second dimension I store a float and another float (but could use int)that tells if the direction is enabled or conditionally enabled.

So in the end I could probably use a struct for this, and I would appreciate if someone gave examples how to do this also.

This is what I got:

void monster_jump(edict_t *self)
{
    if(!(self->monsterinfo.aiflags & AI_JUMPDODGE) && !(self->monsterinfo.aiflags & AI_JUMPDODGEPROJ))
        return;
    if (!self->groundentity)
        return;

    vec3_t left, right;
    vec3_t  jump_dir = { 0 };
    vec3_t  back, front;

    float scan_fraction[NUM_J_DIRS][2] =
    {
        0.0f, 0.0f, 0.0f, 0.0f, 0.0f, 0.0f, 0.0f, 0.0f

    };

    int fraction_order[NUM_J_DIRS] =
    {
        0, 0, 0, 0
    };

    int i = 0, each_tr_incomplete = 0, num_fullyenabled = 0, no_random_dir = 1, random_count = 0;


    if (self->monsterinfo.aiflags & AI_JUMPDODGEPROJ && self->monsterinfo.jump_ent)
    {
        
            VectorSubtract(self->s.origin, self->monsterinfo.jump_ent->s.origin, jump_dir);
            gi.bprintf(PRINT_HIGH, "monster_jump: should jump away from projectile!\n");
            jump_dir[2] *= 0.25;
            VectorNormalize(jump_dir);
            vec3_t end;
            VectorMA(self->s.origin, 128, jump_dir, end);
            trace_t tr = gi.trace(self->s.origin, NULL, NULL, end, self, MASK_SHOT);
            if (tr.fraction != 1)
            {
                VectorInverse(jump_dir);
                jump_dir[0] *= 1 + (crandom() * 0.25);
                jump_dir[0] *= 1 + (crandom() * 0.25);
                VectorNormalize(jump_dir);
                gi.bprintf(PRINT_HIGH, "monster_jump: should jump away from projectile!, path is blocked, so go randomly towards projectile\n");
            }
            //else
                //gi.bprintf(PRINT_HIGH, "monster_jump: should jump away from projectile!\n");

    }
    else
    {
        gi.bprintf(PRINT_HIGH, "monster_jump: should jump away from danger!\n");
        scan_fraction[FRAC_LEFT][FR_VAL] = scan_dir(self, SCAN_LEFT, 128, left); 
        scan_fraction[FRAC_RIGHT][FR_VAL] = scan_dir(self, SCAN_RIGHT, 128, right);
        scan_fraction[FRAC_BACK][FR_VAL] = scan_dir(self, SCAN_BACKWARDS, 128, back);
        scan_fraction[FRAC_FORWARD][FR_VAL] = scan_dir(self, SCAN_FORWARD, 128, front);
        gi.bprintf(PRINT_HIGH, "monster_jump: left = %f, right = %f, back = %f, forw = %f!\n", scan_fraction[FRAC_LEFT][FR_VAL], scan_fraction[FRAC_RIGHT][FR_VAL], scan_fraction[FRAC_BACK][FR_VAL], scan_fraction[FRAC_FORWARD][FR_VAL]);
        
        if (scan_fraction[FRAC_LEFT][FR_VAL] != COMPLETE_TR_FRACTION && scan_fraction[FRAC_RIGHT][FR_VAL] != COMPLETE_TR_FRACTION && scan_fraction[FRAC_BACK][FR_VAL] != COMPLETE_TR_FRACTION && scan_fraction[FRAC_FORWARD][FR_VAL] != COMPLETE_TR_FRACTION)
            each_tr_incomplete = 1;

        if (scan_fraction[FRAC_LEFT][FR_VAL] == COMPLETE_TR_FRACTION)
        {
            num_fullyenabled++;
            scan_fraction[FRAC_LEFT][FR_ENABLED] = ENABLED_FULLY;
        }
        if (scan_fraction[FRAC_RIGHT][FR_VAL] == COMPLETE_TR_FRACTION)
        {
            num_fullyenabled++;
            scan_fraction[FRAC_RIGHT][FR_ENABLED] = ENABLED_FULLY;
        }
        if (scan_fraction[FRAC_BACK][FR_VAL] == COMPLETE_TR_FRACTION)
        {
            num_fullyenabled++;
            scan_fraction[FRAC_BACK][FR_ENABLED] = ENABLED_FULLY;
        }
        if (scan_fraction[FRAC_FORWARD][FR_VAL] == COMPLETE_TR_FRACTION)
        {
            num_fullyenabled++;
            scan_fraction[FRAC_FORWARD][FR_ENABLED] = ENABLED_FULLY;
        }

        if (self->monsterinfo.aiflags & AI_JUMPATTACK && scan_fraction[FRAC_FORWARD][FR_VAL] > 1.0f) //let's skip this for now
        {
            self->monsterinfo.aiflags &= ~AI_JUMPATTACK;
            gi.bprintf(PRINT_HIGH, "monster_jump: should jump forward!\n");
            //goto jump_attack;
            VectorSubtract(self->s.origin, front, jump_dir);
        }
        else
        {
            gi.bprintf(PRINT_HIGH, "monster_jump: starting qsort!\n");
            size_t element_count = sizeof scan_fraction / sizeof scan_fraction[0]; // or NUM_J_DIRS
            size_t element_size = sizeof scan_fraction[0];
            qsort(scan_fraction, element_count, element_size, cmp2);
            for (i = 0; i < NUM_J_DIRS; i++)
            {
                gi.bprintf(PRINT_HIGH, "monster_jump: running qsort! i = %i, \n", i);
                
                fraction_order[i] = i;
                if (each_tr_incomplete)
                {
                    gi.bprintf(PRINT_HIGH, "monster_jump: each trace was incomplete\n", i);
                    scan_fraction[i][FR_ENABLED] = ENABLED_CONDITIONALLY;

                }
                else if (scan_fraction[i][FR_VAL] > 0.85f)
                    scan_fraction[i][FR_ENABLED] = ENABLED_FULLY;
                    
            }
        
            gi.bprintf(PRINT_HIGH, "monster_jump: ended qsort! %f %f %f %f\n", scan_fraction[fraction_order[0]][FR_VAL], scan_fraction[fraction_order[1]][FR_VAL], scan_fraction[fraction_order[2]][FR_VAL], scan_fraction[fraction_order[3]][FR_VAL]);
            
            if (num_fullyenabled) //there is at least one direction that can be used
            {
                full_traces:
                random_count++;
                gi.bprintf(PRINT_HIGH, "monster_jump: choosing from full traces, num = %i!\n", random_count);
                if (random_count >= RANDOM_FR_MAX_COUNT)
                    goto random_direction;
                
                switch(fraction_order[rand() % num_fullyenabled])
                {
                case FRAC_LEFT:
                    if (scan_fraction[FRAC_LEFT][FR_ENABLED] != ENABLED_FULLY)
                    {
                        gi.bprintf(PRINT_HIGH, "monster_jump: LEFT is disabled, retry\n");
                        goto full_traces;
                    }
                    gi.bprintf(PRINT_HIGH, "monster_jump: JUMP LEFT(FULL + RANDOM)\n");
                    VectorSubtract(self->s.origin, right, jump_dir);
                    break;
                case FRAC_RIGHT:
                    if (scan_fraction[FRAC_RIGHT][FR_ENABLED] != ENABLED_FULLY)
                    {
                        gi.bprintf(PRINT_HIGH, "monster_jump: RIGHT is disabled, retry\n");
                        goto full_traces;
                    }       
                    gi.bprintf(PRINT_HIGH, "monster_jump: JUMP RIGHT(FULL + RANDOM)\n");
                    VectorSubtract(self->s.origin, left, jump_dir);
                    break;
                case FRAC_BACK:
                    if (scan_fraction[FRAC_BACK][FR_ENABLED] != ENABLED_FULLY)
                    {
                        gi.bprintf(PRINT_HIGH, "monster_jump: BACK is disabled, retry\n");
                        goto full_traces;
                    }
                    gi.bprintf(PRINT_HIGH, "monster_jump: JUMP BACK(FULL + RANDOM)\n");
                    VectorSubtract(self->s.origin, front, jump_dir);
                    break;
                case FRAC_FORWARD:
                    if (scan_fraction[FRAC_FORWARD][FR_ENABLED] != ENABLED_FULLY)
                    {
                        gi.bprintf(PRINT_HIGH, "monster_jump: FORWARD is disabled, retry\n");
                        goto full_traces;
                    }
                    gi.bprintf(PRINT_HIGH, "monster_jump: JUMP FRONT(FULL + RANDOM)\n");
                    VectorSubtract(self->s.origin, back, jump_dir);
                    break;
                }
            }
            else if (no_random_dir)
            {
                
            sorted_traces:

                random_count++;
                gi.bprintf(PRINT_HIGH, "monster_jump: choosing from sorted, num = %i!\n", random_count);
                if (random_count >= RANDOM_FR_MAX_COUNT)
                    goto random_direction;

                switch (fraction_order[0])
                {
                case FRAC_LEFT:
                    if (!scan_fraction[FRAC_LEFT][FR_ENABLED])
                        goto sorted_traces;
                    gi.bprintf(PRINT_HIGH, "monster_jump: JUMP LEFT(sorted + RANDOM)\n");
                    VectorSubtract(self->s.origin, right, jump_dir);
                    break;
                case FRAC_RIGHT:
                    if (!scan_fraction[FRAC_RIGHT][FR_ENABLED])
                        goto sorted_traces;
                    gi.bprintf(PRINT_HIGH, "monster_jump: JUMP RIGHT(sorted + RANDOM)\n");
                    VectorSubtract(self->s.origin, left, jump_dir);
                    break;
                case FRAC_BACK:
                    if (!scan_fraction[FRAC_BACK][FR_ENABLED])
                        goto sorted_traces;
                    gi.bprintf(PRINT_HIGH, "monster_jump: JUMP BACK(sorted + RANDOM)\n");
                    VectorSubtract(self->s.origin, front, jump_dir);
                    break;
                case FRAC_FORWARD:
                    if (!scan_fraction[FRAC_FORWARD][FR_ENABLED])
                        goto sorted_traces;
                    gi.bprintf(PRINT_HIGH, "monster_jump: JUMP FRONT(sorted + RANDOM)\n");
                    VectorSubtract(self->s.origin, back, jump_dir);
                    break;
                }
            }
            else
            {
                random_direction:
                gi.bprintf(PRINT_HIGH, "monster_jump: choosing from random dir!\n");
            
                switch (rand() % 4)
                {
                case FRAC_LEFT:
                    gi.bprintf(PRINT_HIGH, "monster_jump: JUMP LEFT(RANDOM)\n");
                    VectorSubtract(self->s.origin, right, jump_dir);
                    break;
                case FRAC_RIGHT:
                    gi.bprintf(PRINT_HIGH, "monster_jump: JUMP RIGHT(RANDOM)\n");
                    VectorSubtract(self->s.origin, left, jump_dir);
                    break;
                case FRAC_BACK:
                    gi.bprintf(PRINT_HIGH, "monster_jump: JUMP BACK(RANDOM)\n");
                    VectorSubtract(self->s.origin, front, jump_dir);
                    break;
                case FRAC_FORWARD:
                    gi.bprintf(PRINT_HIGH, "monster_jump: JUMP FRONT(RANDOM)\n");
                    VectorSubtract(self->s.origin, back, jump_dir);
                    break;
                }
            }
        }
        VectorNormalize(jump_dir);
    }
    
    VectorMA(self->velocity, 300 + (100 * random()), jump_dir, self->velocity);

    self->velocity[2] += 150 + random() * 50;
    self->monsterinfo.jump_ent = NULL;
    self->monsterinfo.aiflags &= ~AI_JUMPDODGEPROJ;
    self->monsterinfo.aiflags &= ~AI_JUMPDODGE;



    gi.sound(self, CHAN_AUTO, gi.soundindex(va("player/step%i.wav", rand() % 5)), 1, ATTN_IDLE, 0);
    gi.sound(self, CHAN_AUTO, gi.soundindex(va("player/step%i.wav", rand() % 5)), 1, ATTN_IDLE, 0.05f);
}

Would be also nice to move from something medieval like:

random_direction: switch (rand() % 4) { case FRAC_LEFT: if (!scan_fraction[FRAC_LEFT][FR_ENABLED]) goto random_direction;

To something that doesn't use random numbers to make use of that one have a case (or cases) from a switch disabled.

Does this answer your question? [How to properly use qsort()?](https://stackoverflow.com/questions/25768588/how-to-properly-use-qsort) — Harith, Jan 03 '23 at 19:06
@Woju Good step of improvement. Sure would save time if post included definitions of `AI_JUMPDODGE, AI_JUMPDODGEPROJ, .aiflags, .jump_ent, monsterinfo, .groundentity, .origin, edict_t, vec3_t` and many others. What is best is a [mcve]. What appears so far is a partial code dump and not a select portion that demos the problem. — chux - Reinstate Monica, Jan 03 '23 at 22:04
@chux there would be too many things to include, I've added only the ones that are the most important and related to the problem. The sorting/comparing part was for a one-dimensional array, just not sure how to move forward from this. — Woju, Jan 03 '23 at 22:24
Please trim your code to make it easier to find your problem. Follow these guidelines to create a [minimal reproducible example](https://stackoverflow.com/help/minimal-reproducible-example). — Community, Jan 04 '23 at 00:31

score 0 · Answer 1 · edited Jan 08 '23 at 03:53

0

OP does not want to sort scan_fraction[] even though the code includes qsort(scan_fraction, ....

Instead, OP wants to get something sorted that can access an unchanged scan_fraction[] in a sorted way.

Create an array scan_fraction_sorted[] of pointers to each element of scan_fraction[].
Sort scan_fraction_sorted[]
Display scan_fraction[] in sorted order by referencing through scan_fraction_sorted[]

The below code demos this and is a bit ugly - but something got OP to chew on.

#include <stdio.h>
#include <stdlib.h>
#define NUM_J_DIRS 4

typedef float (d2)[2];

int cmp3(const void *v1, const void *v2) {
  // Code need improvement to well handle Not-a-numbers.
  const d2 **p1 = ( void *) v1;
  const d2 **p2 = ( void *) v2;
  //printf("cmp %g %g\n", p1[0][0][0], p2[0][0][0]);
  return (p1[0][0][0] < p2[0][0][0]) - (p1[0][0][0] > p2[0][0][0]);
}

int main(void) {
  // scan_fraction[] never changes.
  const d2 scan_fraction[NUM_J_DIRS] = { {0.1f, 1.0f}, {0.2f, 0.0f}, {0.3, 3.0f}, {
      0.4f, 2.0f}};

  const d2 *scan_fraction_sorted[NUM_J_DIRS];

  for (int i = 0; i < NUM_J_DIRS; i++) {
    scan_fraction_sorted[i] = &scan_fraction[i];
  }

  qsort(scan_fraction_sorted, NUM_J_DIRS, sizeof scan_fraction_sorted[0], cmp3);

  for (int i = 0; i < NUM_J_DIRS; i++) {
    printf("%g %g\n", scan_fraction_sorted[i][0][0], scan_fraction_sorted[i][0][1]);
  }
}

Output

edited Jan 08 '23 at 03:53

fatihyildizhan

8,614
7
64
88

answered Jan 04 '23 at 03:36

chux - Reinstate Monica

143,097
13
135
256

"// scan_fraction[] never changes." it's only set once here: `scan_fraction[FRAC_LEFT][FR_VAL] = scan_dir(self, SCAN_LEFT, 128, left); scan_fraction[FRAC_RIGHT][FR_VAL] = scan_dir(self, SCAN_RIGHT, 128, right); scan_fraction[FRAC_BACK][FR_VAL] = scan_dir(self, SCAN_BACKWARDS, 128, back); scan_fraction[FRAC_FORWARD][FR_VAL] = scan_dir(self, SCAN_FORWARD, 128, front);` – Woju Jan 04 '23 at 03:41
Woju Posted code demos that `scan_fraction[]` never changed _due to `qsort()`. Of course your code can initialize, assign it any way you want prior to `qsort(scan_fraction_sorted...` – chux - Reinstate Monica Jan 04 '23 at 03:44
So far as I could chew on your code, you are sorting through the direction states, not by actual (distance check fractions) values. I need an int to store (its state) if the direction is enabled, conditionally enabled (to be used later in the code), because later I have 3 situations to deal with 1. if there are multiple whole fractions scan_fraction[FRAC_LEFT][FR_VAL] = 1.0, scan_fraction[FRAC_RIGHT][FR_VAL] = 1.0 and so on, I need to randomly choose one from the complete fractions (thus disable incomplete ones), else use the biggest fraction, else if all fails choose randomly the direction. – Woju Jan 04 '23 at 04:34
Like I described earlier, I'm currently using medieval method of skipping incomplete fraction(s) and thus direction associated with them when there are multiple complete fractions to choose from. Btw I have trouble making a line break in a comment, tried help but that didn't work :D – Woju Jan 04 '23 at 04:36
Ok, I see that you are storing direction in a float right? – Woju Jan 04 '23 at 05:14
Look at the edit I sent (if you can, it's like first time I use Stack Overflow). I've swapped the values, but the pointers are wrong `0.4 2 0.3 3 0.2 0 0.1 1` – Woju Jan 04 '23 at 05:25

Need to sort one dimension of an array in C and store the order

1 Answers1