Best Way To Sort A Dynamic Array?

[22alpha22]

I have a function which adds all shootable actors within a set radius around the caller into a dynamic array. So far so good. I have set a max target limit so that only so many actors can be added to the array. In order for this to work, I created two additional arrays, giving me three arrays in total. One array for storing all possible targets, another array for storing the distance between all possible targets and the caller, and finally an array for storing the final list of targets that have been organized from closest to the caller to furthest cutting off any additional targets that go beyond the max target limit.

An example, say there are 25 possible targets around the caller and the target limit is 12. In that case, the first array would have all 25 targets added to it and the second array would have all their distances to the caller added to it. I've managed to accomplish all this without issues. The problem is when it comes to populating the third and final array. The third array should only be composed of the 12 nearest targets disregarding the rest and this is where I am stuck. I created a function that is supposed to sort targets into the third array by using the data from the first two arrays but GZDoom just hard freezes whenever it is called.

Here is the sorting function:

Code: Select all • Expand view

   Void SortBeamTargetsRange(Int MaxTargets)
   {
      Array<Double> Ranges;
      Double ClosestRange;
      Bool Sort;

      For (Int I = 0; I < InitialTargets.Size(); I++)
      {
         Ranges.Push(Distance3D(InitialTargets[I]));
      }

      ClosestRange = -1.0;
      Sort = False;

      For (Int I = 0; 0 < InitialTargets.Size(); I++)
      {
         If (I > -1)
         {
            If (!Sort)
            {
               If (I >= InitialTargets.Size())
               {
                  Sort = True;
                  I = -1;
               }
               Else If (ClosestRange == -1.0 || ClosestRange > Ranges[I])
               {
                  ClosestRange = Ranges[I];
               }
            }
            Else
            {
               If (ClosestRange >= Ranges[I])
               {
                  BeamTargets.Push(InitialTargets[I]);
                  InitialTargets.Delete(I,1);
                  Ranges.Delete(I,1);
                  ClosestRange = -1.0;
                  Sort = False;
                  I = -1;

                  If (BeamTargets.Size() >= MaxTargets)
                  {
                     Return;
                  }
               }
            }
         }
      }
   }

Any ideas why it hard freezes?

EDIT:
I've changed the function a bit and it now works correctly without freezing, performance could be a bit better. Any tips on how to rewrite it to improve performance or is this the best I'm gonna get?

[Sir Robin]

Maybe post your new routine so we can look at it. Looking at your old one, this line:

Code: Select all • Expand view

For (Int I = 0; 0 < InitialTargets.Size(); I++)


is probably causing you the biggest slow downs.

You should do a web search for "sorting algorithms" if you are unfamiliar with how to write a sort. Some of the most basic ones are bubble, selection, merge, and quick. There are many others and many variations, so read up on the pros and cons of each. Generally speaking bubble sort is the easiest to write but can be one of the slowest, and quick sort can be trickier to write but can be one of the fastest performances.

What exactly are you trying to do? If your InitialTargets has 25, do you want all 25 sorted? Or do you just want the know the closest one or closest few? If just one or a few then selection sort will probably be your fastest.

[22alpha22]

Maybe post your new routine so we can look at it.

The above code is the current function I'm using, I updated it over a week ago when I solved the hard freezing problem. Now the only issue that remains is a bit of performance loss when there are a lot of targets to sort.

If it helps here is the entire code related to this function, it is for a Quake II style BFG 10K ball. I've trimmed out all code not related to the BFG 10K ball for your convience otherwise this would be really, really long.

Code: Select all • Expand view

Class AlphaProjectileBaseClass : Actor Abstract
{
   Array<Actor> InitialTargets;
   Array<Actor> BeamTargets;
   Int SpawnTics;

   Void A_BFG10KBall(Int MaxTargets = 12, Double Range = 1024.0, Int Damage = 600, Class<Actor> ParticleType = Null, Double OffsetX = 1.0, Double OffsetZ = 0.0)
   {
      BlockThingsIterator TargetFinder;
      Vector3 BallPos;
      Vector3 TargetPos;

      Let Plr = AlphaPlayerBaseClass(Self.Target);
      Let OriginalDirection = (Angle,Pitch);

      If (SpawnTics == 0)
      {
         SpawnTics++;

         Vel3DFromAngle(Max(GetDefaultSpeed("AlphaBFG10KBall"),Vel.Length()),Angle,Pitch);
      }
      Else If (Vel.Length() > GetDefaultSpeed("AlphaBFG10KBall"))
      {
         Vel3DFromAngle(Clamp(Vel.Length() * 0.99,GetDefaultSpeed("AlphaBFG10KBall"),Vel.Length()),Angle,Pitch);
      }

      If (SpawnTics <= 15)
      {
         If (SpawnTics == 15)
         {
            bHITOWNER = True;
         }

         SpawnTics++;
      }

      If (Plr)
      {
         TargetFinder = BlockThingsIterator.Create(Self,Range,False);

         While (TargetFinder.Next())
         {
            Let TempTarget = TargetFinder.Thing;

            If (TempTarget)
            {
               If (TempTarget.bSHOOTABLE && !TempTarget.bDORMANT && TempTarget.Health > 0 && !Plr.IsTeammate(TempTarget) && !Plr.IsFriend(TempTarget))
               {
                  If (Distance3D(TempTarget) <= Range && CheckSight(TempTarget,SF_IGNOREWATERBOUNDARY))
                  {
                     InitialTargets.Push(TempTarget);
                  }
               }
            }
         }

         If (InitialTargets.Size() > MaxTargets)
         {
            SortBeamTargetsRange(MaxTargets);
         }
         Else
         {
            BeamTargets.Move(InitialTargets);
         }

         If (BeamTargets.Size() > 0)
         {
            BallPos = (Pos.X,Pos.Y,Pos.Z + (Height / 2));

            For (Int I = 0; I < BeamTargets.Size(); I++)
            {
               Let TempTarget = BeamTargets[I];

               TempTarget.DamageMObj(Self,Plr,Damage,'Laser',DMG_NO_ARMOR,0.0);
               TempTarget.SpawnLineAttackBlood(Self,(TempTarget.Pos.X,TempTarget.Pos.Y,TempTarget.Pos.Z + (TempTarget.Height / 2)),TempTarget.AngleTo(Self,False),Damage,Damage * 0.01);

               If (ParticleType)
               {
                  TargetPos = TempTarget.Pos;
                  TargetPos.Z += TempTarget.Height / 2;
                  Let AttackVector = TargetPos - BallPos;
                  Let Distance = AttackVector.Length();
                  AttackVector /= Distance == 0 ? 1 : Distance;

                  A_Face(TempTarget,0.0,0.0,0.0,0.0,FAF_MIDDLE,0.0);

                  For (Double D = 0.0; D < Distance; D += OffsetX)
                  {
                     Let ParticlePos = BallPos + D * AttackVector;
                     ParticlePos.Z += OffsetZ;
                     Let Particle = Spawn(ParticleType,ParticlePos,NO_REPLACE);
                     Particle.Angle = Angle;
                     Particle.Pitch = Pitch;
                  }
               }
            }
         }

         Angle = OriginalDirection.X;
         Pitch = OriginalDirection.Y;
         InitialTargets.Clear();
         BeamTargets.Clear();
         TargetFinder.Destroy();
      }
   }

   Void SortBeamTargetsRange(Int MaxTargets)
   {
      Array<Double> Ranges;
      Double ClosestRange;
      Bool Sort;

      For (Int I = 0; I < InitialTargets.Size(); I++)
      {
         Ranges.Push(Distance3D(InitialTargets[I]));
      }

      ClosestRange = -1.0;
      Sort = False;

      For (Int I = 0; 0 < InitialTargets.Size(); I++)
      {
         If (I > -1)
         {
            If (!Sort)
            {
               If (I >= InitialTargets.Size())
               {
                  Sort = True;
                  I = -1;
               }
               Else If (ClosestRange == -1.0 || ClosestRange > Ranges[I])
               {
                  ClosestRange = Ranges[I];
               }
            }
            Else
            {
               If (ClosestRange >= Ranges[I])
               {
                  BeamTargets.Push(InitialTargets[I]);
                  InitialTargets.Delete(I,1);
                  Ranges.Delete(I,1);
                  ClosestRange = -1.0;
                  Sort = False;
                  I = -1;

                  If (BeamTargets.Size() >= MaxTargets)
                  {
                     Return;
                  }
               }
            }
         }
      }
   }
}

Actor AlphaBFG10KBall : AlphaProjectile
{
   Tag "BFG 10K Ball"
   Damage (Random(50000,75000))
   Speed 10
   FastSpeed 10
   Radius 13
   Height 26
   DeathHeight 36
   BurnHeight 36
   Mass 500
   ThruBits 1
   RenderStyle Add
   Scale 0.66667
   Decal "BFG10KScorch"
   CameraHeight 2
   Obituary "$OB_MPBFG_BOOM"
   DamageType "Plasma"
   DeathType "Plasma"
   PainType "Plasma"
   +ALLOWTHRUBITS
   +BRIGHT
   +EXTREMEDEATH
   +AlphaProjectileBaseClass.BOOSTRADIUSDMG
   States
   {
      Spawn:
         BFGB A 0 NoDelay A_StartSound("BFG10KBall/Buzz",CHAN_BODY,CHANF_LOOPING,1.0,ATTN_NORM,1.0,0.0)
         BFGB AABBCCDDEEFFGG 1 Light("PointBFG10KBall1") A_BFG10KBall(16,1024.0,Random(400,600),"AlphaBFG10KBeamParticle",3.0,0.0)
         Goto Spawn+1
      Death:
         BFGB H 2 A_StartSound("BFG10KBall/Explode",CHAN_VOICE,CHANF_DEFAULT,1.0,0.33333,1.0,0.0)
         BFGB I 2 A_SpawnDecal(13)
         BFGB J 2 A_ProjectileExplode(PEX_STOP|PEX_NOGRAVITY|PEX_EXTREMEDEATH,0.66667,STYLE_Add,1.0,CHAN_BODY,Random(5000,7500),256,XF_HURTSOURCE|XF_EXPLICITDAMAGETYPE|XF_THRUSTZ,True,32,"Explosive")
         BFGB KLMN 2
         Stop
   }
}

Note: All above code assumes that all actors have had their health and mass increased by a factor of 100, which they have in my mod.

What exactly are you trying to do? If your InitialTargets has 25, do you want all 25 sorted? Or do you just want the know the closest one or closest few? If just one or a few then selection sort will probably be your fastest.

The 25 was only an example scenario. Real world the base number of targets needs to be however many valid targets are found in a set radius. That could be zero to infinite, theoretically, however many there are, they are all added to the InitialTargets array. From the InitialTargets array I want to select only the closest x to be added into the BeamTargets array, with x being determined by the MaxTargets arg in the A_BFG10KBall function.

EDIT:
A couple screenshots of the ball in action.

---

[Sir Robin]

Okay, I threw together a dynamic array quick sorter. Rather than tie it to a specific thing, like distance from an actor to a specific point, it just generically sorts an array of doubles and returns a list of the indices. So it's up to you to feed it a list of those distances and then check the indices against your original list.

Here's the code:

Code: Select all • Expand view

class ArraySort
{
   //Pass this function an array of doubles and it will return that array sorted alongside an array of original indices
   static void SortDouble(array<double> ValueList, array<int> IndexList)
   {
      //make a list of indices, same size as the list of values
      IndexList.clear();
      for (int i = 0; i < ValueList.size(); i++)
      {
         IndexList.push(i);
      }
      
      //quicksort the values and indices lists silmultaneously
      QuickSortDouble(ValueList, IndexList, 0, ValueList.size() - 1);
   }
   
   //internal function, don't call this directly unless you know what you're doing
   static void QuickSortDouble(array<double> ValueList, array<int> IndexList, int low, int high)
   {
      if (low < high) {
         int pi = QuickSortPartitionDouble(ValueList, IndexList, low, high);
         QuickSortDouble(ValueList, IndexList, low, pi - 1);
         QuickSortDouble(ValueList, IndexList, pi + 1, high);
      }
   }
   
   //internal function, don't call this directly unless you know what you're doing
   static int QuickSortPartitionDouble(array<double> ValueList, array<int> IndexList, int low, int high)
   {
      double pivot = ValueList[high];

      int i = (low - 1);

      for (int j = low; j <= high- 1; j++)
      {
         if (ValueList[j] < pivot)
         {
            i++;
            SwapDouble(ValueList, i, j);
            SwapInt(IndexList, i, j);
         }
       }
      SwapDouble(ValueList, i + 1, high);
      SwapInt(IndexList, i + 1, high);
      return (i + 1);
   }
   
   //internal function, don't call this directly unless you know what you're doing
   static void SwapDouble(array<double> ValueList, int index1, int index2)
   {
      double temp=ValueList[index1];
      ValueList[index1]=ValueList[index2];
      ValueList[index2]=temp;
   }

   //internal function, don't call this directly unless you know what you're doing
   static void SwapInt(array<int> ValueList, int index1, int index2)
   {
      int temp=ValueList[index1];
      ValueList[index1]=ValueList[index2];
      ValueList[index2]=temp;
   }
}


And I created a handler to demonstrate it:

Code: Select all • Expand view

class SortTestHandler : EventHandler
{
   const SpawnThingsCount = 5;
   array<actor> SpawnedThing;
   
   override void OnRegister()
   {
      console.printf("[DEBUG]SortTestHandler registered");
   }

   override void PlayerSpawned(PlayerEvent e)
   {
      console.printf("[DEBUG]SortTestHandler PlayerSpawned "..e.PlayerNumber);
      
      PlayerInfo Player = players[e.PlayerNumber];
      
      for (int i = 0; i < SpawnThingsCount; i++)
      {
         bool omg;
         actor wtf;
         [omg,wtf]=Player.mo.A_SpawnItemEx("ExplosiveBarrel", random(-256,256), random(-256, 256));
         if (omg && wtf) SpawnedThing.push(wtf);
      }

      ShowSpawnedDistances(player.mo);
      
      ShowSpawnedItemsSortedByDistance(player.mo);
   }

   void ShowSpawnedDistances(actor source)
   {
      if (!source) {console.printf("[ERROR]ShowSpawnedDistances: Bad source"); return;}
      
      console.printf("Source: "..source.GetCharacterName().." pos="..source.pos);
      
      for (int i = 0; i < SpawnedThing.size(); i++)
      {
         console.printf("Thing "..i.." distance = "..source.Distance3d(SpawnedThing[i]));
      }
   }

   void ShowSpawnedItemsSortedByDistance(actor source)
   {
      if (!source) {console.printf("[ERROR]ShowSpawnedItemsSortedByDistance: Bad source"); return;}
      
      array<double> DistanceList;
      
      for (int i = 0; i < SpawnedThing.size(); i++)
      {
         DistanceList.push(source.Distance3d(SpawnedThing[i]));
      }
      
      array<int> IndexList;
      
      ArraySort.SortDouble(DistanceList, IndexList);

      console.printf("Indices count: "..IndexList.size());

      for (int i = 0; i < IndexList.size(); i++)
      {
         console.printf("Index "..i.." = "..IndexList[i]..", distance = "..source.Distance3d(SpawnedThing[IndexList[i]]));
      }
      
   }
}


What this does is that as soon as a player spawns, it also spawns 5 barrels at random locations near the player and keeps them in the SpawnedThing array. It then lists the distance from the player to each barrel and then sorts that list and shows the sorted indices.

The code you'll be interested in is that last function, ShowSpawnedItemsSortedByDistance. notice the steps in that function:

1. Create DistanceList
2. Loop through SpawnedThing, calculate each distance, and push it to DistanceList
3. DistanceList now has the same number of entries as SpawnedThing
4. Create IndexList, leave it empty
5. Call the sort function, pass DistanceList and IndexList
6. IndexList now has the same number of entries as DistanceList and SpawnedThing
7. Each entry in IndexList points to an index into SpawnedThing sorted by distance.

[Sir Robin]

And here is your SortBeamTargetsRange function rewritten to use my ArraySort.SortDouble function:

Code: Select all • Expand view

   Void SortBeamTargetsRange(Int MaxTargets)
   {
      //build a list of ranges
      Array<Double> Ranges;
      For (Int I = 0; I < InitialTargets.Size(); I++)
      {
         Ranges.Push(Distance3D(InitialTargets[I]));
      }
   
      //create a list to hold indices, then sort the ranges
      array<int> IndexList;
      ArraySort.SortDouble(Ranges, IndexList);
      
      //determine the number of beam targets
      int TargetCount = clamp(MaxTargets, 0, InitialTargets.size());

      //push InitialTargets into BeamTargets using the sorted indices for order   
      For (Int i = 0; i < TargetCount; i++)
      {
         BeamTargets.Push(InitialTargets[IndexList[i]]);
      }
   }


I haven't tested that in your code but it should work based on how your code appears to work.

The sort happens pretty fast. In my brief testing I didn't notice any slowdown in FPS even doing a sort every tic with 10,000 InitialTargets.

Also I did some performance tests with allocating the arrays instead of pushing them and with using distance indexes instead of the distance3d function. Neither of these seems to affect performance (even at 10,000 sorts per tick) so I ripped them out for sake of easier code.

[22alpha22]

It took me a moment before I was able to follow your code, now that I think I understand it, it does not actually seem to return anything. The ArraySort class is separate from the projectile class and therefore does not share variables, furthermore, the SortDouble function does not actually return anything, it sorts the input but does not return it again. In fact it can't return the input because functions cannot return dynamic arrays. I thought about trying to use a struct instead of a class but structs cannot use arrays, so I decided to turn the ArraySort class into a Mixin.

Here is the result:

Code: Select all • Expand view

Mixin Class ArraySorter
{
   Array<Double> ValueListDouble;
   Array<Int> IndexList;

   //Pass this function an array of doubles and it will return that array sorted alongside an array of original indices
  Void SortDouble(Void)
   {
      //make a list of indices, same size as the list of values
      For (Int I = 0; I < ValueListDouble.Size(); I++)
      {
         IndexList.Push(I);
      }

      //quicksort the values and indices lists silmultaneously
      QuickSortDouble(ValueListDouble, IndexList, 0, ValueListDouble.size() - 1);
   }

   //internal function, don't call this directly unless you know what you're doing
   void QuickSortDouble(array<double> ValueList, array<int> IndexList, int low, int high)
   {
      if (low < high) {
         int pi = QuickSortPartitionDouble(ValueList, IndexList, low, high);
         QuickSortDouble(ValueList, IndexList, low, pi - 1);
         QuickSortDouble(ValueList, IndexList, pi + 1, high);
      }
   }

   //internal function, don't call this directly unless you know what you're doing
   int QuickSortPartitionDouble(array<double> ValueList, array<int> IndexList, int low, int high)
   {
      double pivot = ValueList[high];

      int i = (low - 1);

      for (int j = low; j <= high- 1; j++)
      {
         if (ValueList[j] < pivot)
         {
            i++;
            SwapDouble(ValueList, i, j);
            SwapInt(IndexList, i, j);
         }
       }
      SwapDouble(ValueList, i + 1, high);
      SwapInt(IndexList, i + 1, high);
      return (i + 1);
   }

   //internal function, don't call this directly unless you know what you're doing
   void SwapDouble(array<double> ValueList, int index1, int index2)
   {
      double temp=ValueList[index1];
      ValueList[index1]=ValueList[index2];
      ValueList[index2]=temp;
   }

   //internal function, don't call this directly unless you know what you're doing
   void SwapInt(array<int> ValueList, int index1, int index2)
   {
      int temp=ValueList[index1];
      ValueList[index1]=ValueList[index2];
      ValueList[index2]=temp;
   }
}

Class AlphaProjectileBaseClass : Actor Abstract
{
   Mixin ArraySorter;

   Void SortBeamTargetsRange(Int MaxTargets)
   {
      //build a list of ranges
      For (Int I = 0; I < InitialTargets.Size(); I++)
      {
         ValueListDouble.Push(Distance3D(InitialTargets[I]));
      }

      //create a list to hold indices, then sort the ranges
      SortDouble();

      //determine the number of beam targets
      int TargetCount = clamp(MaxTargets, 0, InitialTargets.size());

      //push InitialTargets into BeamTargets using the sorted indices for order
      For (Int i = 0; i < TargetCount; i++)
      {
         BeamTargets.Push(InitialTargets[IndexList[i]]);
      }

     ValueListDouble.Clear();
     IndexList.Clear();
   }
}

Performance with this method of sorting seems to be mostly the same, maybe slightly better but not by much, so it must be something else that is killing performance, maybe all the particle actors or something. Nevertheless, this method of sorting seems more flexible and cleaner than what I originally had, so I'm gonna keep it. I appreciate the help.

[Sir Robin]

It took me a moment before I was able to follow your code, now that I think I understand it, it does not actually seem to return anything. The ArraySort class is separate from the projectile class and therefore does not share variables, furthermore, the SortDouble function does not actually return anything, it sorts the input but does not return it again. In fact it can't return the input because functions cannot return dynamic arrays. I thought about trying to use a struct instead of a class but structs cannot use arrays, so I decided to turn the ArraySort class into a Mixin.

That's correct that the functions don't return anything. You see the "void" keyword before most of my function definitions, that means they don't return anything. Zscript doesn't allow functions to return arrays or even dynamic arrays. And even if it did, the quick sort algorithm is recursive, so passing all those arrays in and out of functions at each recursion level would see a performance hit in memory usage and handling required. My functions are written to take the lists in as parameters and sort them in-place.
That's correct that the ArraySort class is it's own independent class. It has only static functions (you see the "static" keyword in front of the function definitions) and no instance variables, so there is no need to instantiate it or even tie it to a particular class. Think of functions like console.printf() or stringtable.localize() - you don't need to create any object for them to work, they just work on their own. That's the same way I designed the ArraySort class to work. You just call ArraySort.SortDouble() with your lists and it does everything from there, no extra work needed.

Performance with this method of sorting seems to be mostly the same, maybe slightly better but not by much, so it must be something else that is killing performance, maybe all the particle actors or something. Nevertheless, this method of sorting seems more flexible and cleaner than what I originally had, so I'm gonna keep it. I appreciate the help.

I did testing with spawning 10,000 items and sorting them every tick and didn't see any slowdown in FPS. You can change that SpawnThingsCount in SortTestHandler and see for yourself. The actors, particle actors or not, couldn't possibly be slowing it down. The sort routine is just looking at a list of doubles and a list of ints, it's not even aware of the actors the lists point to, so there's no way they could be slowing it down. Maybe if you added something to the code that might be slowing it down, but my code doesn't even talk to the actors after getting their distance3d results at the very beginning.

Anyway, sorry the code was hard to read, I tried to make it as simple as possible. But seems like you got it working anyway, so that's what matters. Good job.

[Sir Robin]

For what it's worth I'm maintaining the ArraySort functions in this thread. If you've found this thread while searching for array sorting functions, check that thread for updates.