Forum rules
Before asking on how to use a ZDoom feature, read the ZDoom wiki first. If you still don't understand how to use a feature, then ask here.
Please bear in mind that the people helping you do not automatically know how much you know. You may be asked to upload your project file to look at. Don't be afraid to ask questions about what things mean, but also please be patient with the people trying to help you. (And helpers, please be patient with the person you're trying to help!)
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.
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?
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.
Last edited by Sir Robin on Thu Jun 30, 2022 9:45 am, edited 1 time in total.
Sir Robin wrote: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.
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.
Sir Robin wrote: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.
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.
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;
}
}
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:
Create DistanceList
Loop through SpawnedThing, calculate each distance, and push it to DistanceList
DistanceList now has the same number of entries as SpawnedThing
Create IndexList, leave it empty
Call the sort function, pass DistanceList and IndexList
IndexList now has the same number of entries as DistanceList and SpawnedThing
Each entry in IndexList points to an index into SpawnedThing sorted by distance.
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.
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.
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.
22alpha22 wrote: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.
22alpha22 wrote: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.
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.
