Sorting ints in descending order

[aussie]

Hi all! It's been years since I last posted here. It's great to see familiar nicks still around! 

Today I bring you an embarrasingly basic scripting question.

I am trying to set up the turns of a turn-based combat system. So far I have defined the characters' and enemies' attributes in structs in the header and main script. I can import and export these between the battle room and the main screen without problems. I can also have different enemy and hero parties depending on the battle I need to run, so I feel things are coming together nicely.

But here is where I run into trouble. Each character/enemy has a speed attribute (int) which should determine the order in which he is to act. Now I am trying to automate the turns and I feel I am getting stuck in one of the easy parts of the process. I have arranged the speed attributes in an array of int values and I need to have them in descending order. Any tips?

Thanks!

Edit: I have also run several searches in the forum but I cannot seem to find what I am after.

[Snarky]

In the general case, it's best to implement a performant search algorithm like quicksort or mergesort.

But if you're dealing with small arrays, on the order of maybe a dozen entries, you can use an inefficient but simple algorithm instead. I'll go with selectsort since it is pretty intuitive:

Code: ags

void selectSortMax(int array[], int arraySize)
{
  // Find the largest element, put it at the start, and then repeat for rest of array
  for(int sortStart=0; sortStart < arraySize; sortStart++)
  {
    // Find the largest remaining element
    int maxIndex = sortStart;
    for(int i = sortStart+1; i < arraySize; i++)
    {
      // If the new element is bigger than any seen so far, we have our max so far
      if(array[i] > array[maxIndex])
        maxIndex = i;
    }
    // Put that element at the top of the unsorted array (if not already in place)
    // by swapping it with the element there at the moment 
    if(maxIndex != sortStart)
    {
      int buffer = array[sortStart];
      array[sortStart] = array[maxIndex];
      array[maxIndex] = buffer;
    }
  }
}

(Untested; may include bugs)

[eri0o]

I made a quick sort here: https://www.adventuregamestudio.co.uk/forums/advanced-technical-forum/solved-doing-quicksort-in-ags-problems-with-pointers-and-managed-types/msg636624313/#msg636624313

I think if the party/monster is sufficiently small, you can assign an unique add to them and then just put in a group, then you can find the maximum from the group and just remove one by one the ones that are playing their turn. Once none is available the round ends and then you start a new round.

[aussie]

In the general case, it's best to implement a performant search algorithm like quicksort or mergesort.

But if you're dealing with small arrays, on the order of maybe a dozen entries, you can use an inefficient but simple algorithm instead. I'll go with selectsort since it is pretty intuitive:

Thanks Snarky. I have tried your solution. It appears to work, except I somehow can't call the function to sort my array. Here is my code. It is all within the room script, as I do not expect to use the sorting function outside it.

The error I get is in the very last line. I may not be calling the function properly, but I think I have tried all combinations.

Code: ags

//First your function

void selectSortMax(int array[], int arraySize)

(...)

//then get the speed of all characters/enemies in battle

heroLBspeed = hero[heroLB].herospeed;
heroUBspeed = hero[heroUB].herospeed;
heroUFspeed = hero[heroUF].herospeed;
heroLFspeed = hero[heroLF].herospeed;
enemyLBspeed = enemy[enemyLB].enemyspeed;
enemyUBspeed = enemy[enemyUB].enemyspeed;
enemyUFspeed = enemy[enemyUF].enemyspeed;
enemyLFspeed = enemy[enemyLF].enemyspeed;

//put them all in an array

int turnorder[8];
turnorder[0] = heroLBspeed;
turnorder[1] = heroUBspeed;
turnorder[2] = heroUFspeed;
turnorder[3] = heroLFspeed;
turnorder[4] = enemyLBspeed;
turnorder[5] = enemyUBspeed;
turnorder[6] = enemyUFspeed;
turnorder[7] = enemyLFspeed;

//Then I call the function you defined

selectSortMax (turnorder[],8); ---- [This is the line that gives me the error]

Depending on what I pass into the last line I get different errors:

- Type mismatch: cannot convert 'int' to 'int[]'
- Array index not specified

I made a quick sort here: https://www.adventuregamestudio.co.uk/forums/advanced-technical-forum/solved-doing-quicksort-in-ags-problems-with-pointers-and-managed-types/msg636624313/#msg636624313

I think if the party/monster is sufficiently small, you can assign an unique add to them and then just put in a group, then you can find the maximum from the group and just remove one by one the ones that are playing their turn. Once none is available the round ends and then you start a new round.

Thanks a lot eri0o. I have not tried your solution yet because it looks a little more complex and I have limited time today. I will do so as soon as I can then get back to you.

[Khris]

Try

Code: ags

  selectSortMax(turnorder, 8);

[aussie]

Try

Code: ags

  selectSortMax(turnorder, 8);

Thanks Khris. In that case I get the following error: Type mismatch: cannot convert 'int*' to 'int[]'

[Khris]

Right, it needs to be a dynamic array I guess.

Code: ags

  int turnorder[] = new int[8];

[aussie]

I see. That seems to work! Thanks!

You guys are legends!

EDIT. Now I realise I may have done something stupid. I have a perfectly sorted array of speed values, but I believe the script no longer knows which speed belongs to which character!

Instead of an array, is it possible to start with a struct with the speed and the name of the character, then sort it following Snarky's procedure? Any easier workarounds?

Thanks again!

[Snarky]

Yeah, for technical reasons, AGS only allows dynamic arrays as arguments to functions.

What I don't quite understand is how, having sorted the speeds, you are then able to tell which unit corresponds to each element in the sorted array and should move first. Do you do a lookup to find which unit has the particular speed? That adds another layer of inefficiency, if so. And what if multiple units have the same speed? (Edit: Ah, I see that you edited your post right before I finished this, and in fact can not tell.)

Also, one tip: It's a great benefit if you can use the same struct both for heroes and enemies, since that means you can, among other things, store them in a common array, which lets you easily do things like sort them or run through them one by one. And you wouldn't need separate .herospeed and .enemyspeed properties (and many other stat properties that are probably duplicated); instead you could just have one .speed property, and a single flag like bool isHero to tell them apart.

So what I would personally do in your situation would be something more like:

Code: ags

  // Assume a managed struct CombatUnit that is used both for hero and enemy units
  CombatUnit* combatUnit[] = new [MAX_COMBAT_SIZE];
  int unitCount = 0;
  combatUnit[unitCount++] = hero[0];
  // ...
  combatUnit[unitCount++]  = enemy[3];
  //  (In reality you wouldn't need the hero[] and enemy[] arrays,
  //   but could just assign the units directly to combatUnit[].) 

  sortByInitiative(combatUnit, unitCount);

This would use a version of the selectSort function that sorted an array of CombatUnit pointers by speed:

Code: ags

void sortByInitiative(CombatUnit* array[], int arraySize)
{
  for(int sortStart=0; sortStart < arraySize; sortStart++)
  {
    int maxIndex = sortStart;
    for(int i = sortStart+1; i < arraySize; i++)
    {
      if(array[i].speed > array[maxIndex].speed) // We use the .speed property to sort
        maxIndex = i;
    }
    if(maxIndex != sortStart)
    {
      CombatUnit* buffer = array[sortStart];
      array[sortStart] = array[maxIndex];
      array[maxIndex] = buffer;
    }
  }
}

[eri0o]

I really think you don't need to sort, just pick the unit with the maximum speed of a group and then remove it from the group - this should make it easier to add additional conditionals, like, maybe flying units goes first indifferent from speed.

Anyway, if your units all share a same index and you want to sort by speed and you have int sort working, a common trick is instead sorting "val= speed*256 + unit_index" and then later just filtering the index out by using "unit_index= val&0xFF".

[Snarky]

I really think you don't need to sort, just pick the unit with the maximum speed of a group and then remove it from the group

This is precisely what selectsort does, iteratively, so the only difference is whether you do it all in one go before you start processing the combat actions, or one at a time as the combat advances. Unless actions by earlier units can change the priority of later units, I don't think there is any benefit of one over the other. By which I mean: I think to do what you describe, you'd need pretty much every line of my selectSortMax() function—or some close equivalent—somewhere or other in your code (though the bit that swaps indices might be done differently depending on exactly how you implement "remove it from the group").

this should make it easier to add additional conditionals, like, maybe flying units goes first indifferent from speed.

Again, I don't see how it makes a difference, since you'll have to write the same priority/comparison condition either way. (Of course, if AGS allowed delegates or function pointers, that part could be abstracted out, but alas.)

Anyway, if your units all share a same index and you want to sort by speed and you have int sort working, a common trick is instead sorting "val= speed*256 + unit_index" and then later just filtering the index out by using "unit_index= val&0xFF".

OK, yeah; that's cool (as long as your array size is <256, of course).

[aussie]

What I don't quite understand is how, having sorted the speeds, you are then able to tell which unit corresponds to each element in the sorted array and should move first. Do you do a lookup to find which unit has the particular speed? That adds another layer of inefficiency, if so. And what if multiple units have the same speed? (Edit: Ah, I see that you edited your post right before I finished this, and in fact can not tell.)

Precisely my point. I only noticed after I tried your solution. I have a very nicely arranged array where I do not know which value goes with which character!

Also, one tip: It's a great benefit if you can use the same struct both for heroes and enemies, since that means you can, among other things, store them in a common array, which lets you easily do things like sort them or run through them one by one. And you wouldn't need separate .herospeed and .enemyspeed properties (and many other stat properties that are probably duplicated); instead you could just have one .speed property, and a single flag like bool isHero to tell them apart.

Yes. This is so true      . I have fixed all my code so that I now have a single struct where I previously had three. It makes things so much more convenient. I think this is also going to help me with the sorting problem.

I really think you don't need to sort, just pick the unit with the maximum speed of a group and then remove it from the group - this should make it easier to add additional conditionals, like, maybe flying units goes first indifferent from speed.

Anyway, if your units all share a same index and you want to sort by speed and you have int sort working, a common trick is instead sorting "val= speed*256 + unit_index" and then later just filtering the index out by using "unit_index= val&0xFF".

Agreed. That should work provided I remember to "put the character back in" once each round of individual turns is complete. I also get what Snarky is saying.

I still have a bit of thinking to do to make things work exactly as I want, but you guys have placed me on the right track. I might revisit this post in the coming days if I need further advice. For the time being, thank you so much!!!

[eri0o]

@aussie I think your signature website is giving a not found issue.