Sorted list as long as needed

[Barbie]

In the end I like to have a list of all pawns sorted descending by health. For easiness it don't need a GUI but can be written to log. Does anyone have a basic framework for a sorted list?

[Buggie]

As far as I know, this is not a trivial task.

You'll need to build a linked list first, since UT does not support dynamic arrays.
And then implement some sorting on the linked list.

This one is instant.

If you need to constantly keep such a list, then when creating a new Pawn you will need to insert it in a suitable place on the list.

Next, you need to maintain the consistency of the list. With each change in the volume of life - move Pawn up or down in the linked list.

Most likely, this will all be too low-performance solution.

Perhaps this is not possible at all with a large number of Pawns due to the "Runaway loop detected (over 100000 iterations)" error.

It might be better to describe what you want to achieve than to indicate a specific action. It may be easier to dump everything into a file, and then call linux sort on that file. Or run a script that sorts the contents of the file in the desired order.

In any case, it can be merge sort for linked list: https://www.chiark.greenend.org.uk/~sgt ... tsort.html

IDK how UE1 calculate Runaway loops, but if it simple counter, then merge sort must work up to 10,000 pawns, since N*log(N) for N = 10,000 is near 100,000.

According to https://forums.epicgames.com/udk/udk-de ... naway-loop

Runaway loop check involves a global loop counter that counts the number of jumps over an entire update cycle (tick/frame). In UE1/2 this counted every conditional jump (if, while, for, until) and unconditional jump (else, break, continue, end of for loop, end of while loop, goto in function code), even if it wasn't part of a loop.

Real limit can be significantly low from 10,000 pawns for sort. Maybe even lower then 1,000 pawns.

So maybe dump, and sort later with third-party tool can be only one solution.

[Barbie]

I already use double linked lists a lot. The algorithm to insert an item into a sorted list is clear:

Code: Select all

ListItem = ListStart;
While (compare(me.property, ListItem.property) < 0)
	ListItem = ListItem.NextItem;
ListItem.insert(me)

So access grows with n/2, what should not really be a problem. IMO it is better to sort the list as it grows than processing a sort algorithm on the filled list.

What I want to achieve is said in first post: "In the end I like to have a list of all pawns sorted descending by health". This list can be build in PostBeginPlay() or in the auto state of an actor. I want to use that list to decide what monsters have to be adjusted in MH maps.

[Buggie]

The task is not clear. You say Health, but Health is variable. I suspect we are talking about the starting value of Health, otherwise the sorting will collapse with almost any change in Health for any Pawn.

[Barbie]

Of course the health value before game starts.

[Buggie]

Just build linked list from scratch. You need build it in any case, so when build, build it in descending order.

Or you have already build list (not from your code) and want it sort?

[TheDane]

Is there any particular reason the original code that sorts the players by score in the scoreboard class cannot be altered to fit your needs?

[sektor2111]

In my way of doing, this might be an expensive code. By "Expensive Code" I mean risk to get at engine boundary for iterations. As result I would go for a code like I wrote in those newer MapVote-s (over 2048 maps) turning sorting function in a state code with "sleep"s... but taking time. Monster is initialized and code has to wait all game processes, then reacting, but this reaction should not take ages and neither pushing a crash.
It will need adding health into some array and then moving elements for each next monster tested up or down depending on health data found in said array. Array can be a 512 size, if map has more monsters doesn't matter, you need to sort the bigger ones (or smaller ones), like in scoring systems. Definitely some linked lists can save iterations but during sorting stage... it's a processing task that needs to be in account. Here if you go for their removal you will notice Events or moving these Events at another creature. However I wouldn't remove big guys, just push them back. Not 200,000 HP but 20,000 or less. Why spamming for no purpose ?

Another note: Using SetPawnDifficulty for capping monster at certain value. If code is too fast (some mods have various reactions here) and monster might screw itself, just check health in a "SYF" code or a Monster Counter which won't only count monsters but will check health in the same time. No extra stuff would be needed, just adding a check in current codes and conform mod against a mismatch problem, new health check-line won't do any damage at this point. In XC_MonsterHunt I have this health check exactly in "SetPawnDifficulty" which can be rewritten with more than 20 extra-checks (against other dumb settings) with no issue as long as is called ONCE in relevance and CheckReplacement. In this check you can attach a temporary actor owned by monster and waiting 10 ms for figuring if monster won't have some other activity - Skaarj Fix might be done here, allow him to initialize and if has a flaw fix it and then destroy actor.
I even attach such tweaking actors to movers, I have too many things tested and then some maps heavy loaded were crashing game, so I went to another strategy, spawn a controller, wait a bit++ for each of them, do the tweak and be gone. Movers can be adjusted even if autostate is running dropping them into another state, definitely works proved in logs and in game.
This actor controller-tweaker can be spawned in a single iteration (using PawnList will save cycles - I guess). This actor might have a default configuration. Whatever property is out of desired configuration can be modified. No sorting, no lists, no extra processing, just allow each monster to be adjusted by its own tool.

[Feralidragon]

Like most things in coding, the right algorithm to use largely depends on your requirements and boundaries, and this is especially true for sorting algorithms, since each one has their pros and cons.

If you need to sort a list only once without having to update it anymore, you can generally use quicksort.
If you need to keep a sorted list at all times and have to continually add and remove elements, you generally use binary trees (there are several implementations, but the base idea is the same, reduce the time complexity of anything to O(log n)).

That is to say that you need to give more info on what exactly you intend to do with this list, and what kind of changes that list will have over time: is it generated only once at the start of the game? Is it updated over time? Is health really the starting health or the current health? And so on.

For example, if you intend to have a sorted list, which is updated over time with monsters being added and removed from it, but you only care about the starting health, then one assumption you may be able to make is that the same type of monsters will all have the same starting health.

Under this assumption, you could have a list of buckets rather than a simple list, where each bucket would represent a list of monsters with the same starting health, and from there you would just need to sort the buckets and not the monsters.

So if you have 1000 monsters, rather than sorting through 1000 elements, you would need only to sort unique starting health values, reducing the problem to something with 1-10 elements in practice, and at that point you can use any sorting algorithm you wish, be it an optimized one like quicksort, or a naive one with O(n²) time, it won't make much of a different when the number of elements is small.

But this only works if this is indeed your requirement, otherwise you need to provide more info.

Is there any particular reason the original code that sorts the players by score in the scoreboard class cannot be altered to fit your needs?

The problem is the algorithm that code uses: it's somewhat fine for small tiny lists, but it will wreck performance with longer lists, since the time complexity of that function is about O(n(n+1)/2), which is almost as bad as O(n²).

It may be used however if Barbie opts to use bucket lists like I suggested above, since at that point a large list of monsters becomes a small list of buckets to sort instead.

[Barbie]

Thanks for all of your responses, and I see that my explanation above what I need the list for was insufficient obviously.

When I want to put a MH map on my server, in some maps monster's health is oversized and not balanced to the given weapons. With a MapPatcher I "correct" such unloved circumstances in run time when the map is loaded on server. To code these modifications I open the map in UnrealEd and check monster's health manually. In this moment a sorted list showing monster's health in decreasing order would be very helpful. Of course the list will be static once created before game start, and monsters with health below a threshold can be ignored and skipped - I'm only interested in the healthiest monsters and not in weak ones like flies an pupaes. ^^ So the list could also be static because I assume that it won't have more than about some hundred entries. But a static list (=array) has the disadvantage that inserting an item in the middle is more expensive compared to a linked list. So one or two hours of coding could reduce the run time from 2 to 1 sec.


Back to my question: I asked if someone has a template or a framework for such a list. Then I have to adjust the compare function and variable types only.

[Buggie]

I still do not understand one thing:
1. Do you already have a linked list and want to sort it?
.2. Or will you build it from scratch and want to sort it on the fly, during construction?

For build sorted single-linked list your code can be modified:

Code: Select all

ForEach AllActors(class'ScriptedPawn', pawn) {
	if (pawn.Health <= 100) continue; // some threshold
	item = new(None) class'ListItem';
	item.pawn = pawn;
	if (ListStart == None) {
		ListStart = item;
		continue;
	}
	ListItem = ListStart;
	While (ListItem.NextItem != None && ListItem.NextItem.pawn.Health > pawn.Health) {
		ListItem = ListItem.NextItem;
	}
	item.NextItem = ListItem.NextItem;
	ListItem.NextItem = item;
}

This is a simple forehead implementation. Perhaps adding a small cache will speed it up significantly if there are problems with speed or the number of iterations.