MapGarbage discussion

[Buggie]

For prevent derailing other topic with discussions about MapGarbage tool - created this topic.
Tool placed here: https://hofgamingclan.com/forums/viewto ... =502#p3365
Author: sektor2111

---

Automatically merged

original post

MapGarbage was capable to find duplicated actors but... in this map Editor is crashing in runaway loop as long as it will iterate to the death.

However... concerning discussion with UT limits,
viewtopic.php?f=5&t=14671#p130078
the good news is that some of these can be passed and things can be oriented different.

ReachSpecs can be enlarged making for real Patroling Titans (perhaps up to 255 not 70 UU), interations limit at least for Editor can be passed/suppressed too making MapGarbage to hunt all sort of borked actors from heavy loaded maps. This one is a sample:

Code: Select all

Duplicated: Panel95 was found 2 times.
Duplicated: Panel96 was found 2 times.
Duplicated: Actors might be removed by using subsequent bTryFixDuplicates set to True.
Duplicated: Operation recommended in another clean editing session with both values set True.
Duplicated: Panel136 was found 2 times.
Duplicated: Panel137 was found 2 times.
Duplicated: Panel138 was found 2 times.
Duplicated: Panel139 was found 2 times.
Duplicated: Panel148 was found 2 times.
Duplicated: Panel149 was found 2 times.
Duplicated: Panel159 was found 2 times.
Duplicated: Panel160 was found 2 times.
Duplicated: Found 10 duplicated Actors.
Processed: UScript count: 57709724 iterations. //Added
Duplicated: Duplicated Actors scanning is being finished.

Indeed it takes time, CPU cooler starts going crazy but... it works. And then certain pathing tweaks and fixes which I could do but I quit thinking at them now can be resumed. Yes, it takes time for details but CPU it's faster than a human being...

The Solution - this is my batch command firing Editor - no, I don't launch it directly as it works faster this way:

Code: Select all

@echo off
echo Start Unreal Editor 440 + XC with higher priority
start "Unreal Editor 440 + XC" /WAIT /ABOVENORMAL /MAX UnrealEd.exe -norunaway
del Running.ini
exit

It won't be any trash file called "Running.ini" left in System because Editor has a dumb exit - even "Exit" is bugged in UT436...

Either way I think I'm not recommending suppressing "runaway" in dedicated servers. Reason: some script "good timings" might lock-down server, won't crash and restart, it simply loops permanently.

This dumb solution might solve issue with MapVoteLAv2 when server it's crashing because of sorting iterations when maps count goes to 1700 1800 maps. Server will need to be restarted with "runaway" removed, maps loaded and generated a list, then stopped server and added back the "runaway". This way maps are getting sorted and wrapped in a list file. This is not answer for poorly codes from MapVoteLAv2 but at least I believe it will solve maps-loading-sorting issues. MVU3 doesn't have problems here, it is based on a state code - slower but operational.

1. Play with UnrealEd priority ("/ABOVENORMAL") - good way hang your PC.

2. Look like you doing duplicate search very wrong.

Code: Select all

ScriptLog: Duplicated: Panel95 
ScriptLog: Duplicated: Panel96 
ScriptLog: Duplicated: Panel136 
ScriptLog: Duplicated: Panel137 
ScriptLog: Duplicated: Panel138 
ScriptLog: Duplicated: Panel139 
ScriptLog: Duplicated: Panel148 
ScriptLog: Duplicated: Panel149 
ScriptLog: Duplicated: Panel159 
ScriptLog: Duplicated: Panel160 
ScriptLog: Checked 15251 actors. Found 10 duplicates.

main part of code:

Code: Select all

	local Actor Actor;
	local string buf, tmp;
	local int i, k, n;

	buf = " ";
	foreach LevelInfo.AllActors(class'Actor', Actor) {
		i++;
		tmp = Actor.Name $ " ";
		n = InStr(buf, " " $ tmp);
		if (n == -1) {
			buf = buf $ tmp;
			continue;
		}
		Log("Duplicated: " $ tmp);
		k++;
	}

	tmp = "Checked" @ i @ "actors. Found" @ k @ "duplicates.";
	Log(tmp);
	return BadParameters(tmp);

No any runaway. On this map found duplicates in near 3 seconds.
I suspect iteration usage less from 10*ActorsCount.
For 15 000 actors less from 150 000.
So limit of 10 000 000 - is fine there.

[sektor2111]

Until that wrong code to be used I did not see anything finding & fixing this problem before - it's good that it can be improved.
Whenever a code is better it will be used. With said code I successfully cleaned more borked maps.

Bypassing iterations limit might be mandatory for pathing fixes/builds when all navigation charge goes higher. By scanning if all data is placed properly and fixing if needed is easy to reach at boundary. If you have faster solutions I'm eyes and ears. Here I needed FIXING the duplicated ones during the same execution. Whatever is there wrong it was very helpful for me.

Editor "/abovenormal" never hang my Editor - except when I fired some crapped code in builders... which did damage in any environment. I'm always using a higher priority for Editor.

What I need at this moment is a solution for creating paths and preventing a lot of connections in similar directions. If A is connected at B and C is a bit more far in almost the same direction as B (around 30 degrees) I don't want any A connected to C and a better solution with bunches of Inventories - perhaps removing useless adds such as two PathNodes closer than 50-60 UU to an InventorySpot or another PathNode, these don't make any sense. I worked a lot for not reaching at a crash resulting nothing, but right now I think the code should be more completed because runaway can be ignored...

[Buggie]

Recently I play with priority and UnrealEd - https://github.com/OldUnreal/UnrealTour ... issues/383 - hang my PC. I use RealTime priority but in general any increase priority can cause this.

About optimize code - we can talk only on specific cases. Not in general way.

As I see count of iterations increased only by VM execute Jump or IfNot instructions. So if you want bypass this limits you need properly use good approach in every bottleneck.

For example dumb approach for sort cause complexity O(n^2) - which lead to 225 000 000 iterations at least for 15 000 actors.
OK. we use not so dumb way as two loops one inside another. we break inner loop. And get near 110 000 000 iterations.

If we smart and know about fast sort algorithms - we can sort initially data via O(n*log(n)) after that use binary search on sorted array if we need random access - again O(n*log(n)).
If we need sequential access then we need only O(n) iterations.

For our case O(n*log(n)) it is near 15 000 * 14. less from 225 000. So we speed up our dumb approach in 1000 times.

It is just simple example.

Very big win we can use from proper storage and decide what important for us.

Linked list not good in term of binary search for example.
Array limited in size but sometimes can be fast.
String mostly unlimited in size, search on it case-sensitive but usually fast enough because use well-known c++ assembler implementation under the hood. Knuth–Morris–Pratt algorithm can be enough effective.
And you not spent iterations for it. Just simple call one function. If you not call this often in loop - result can be great as in example above.

In some langs, where not exists real static indexed arrays, strings can be answer for very fast access with linear access time.

Back to example - what decision made on write this code?
1. strings enough - because not use iteration count and speed fine.
2. 15 000 actors * 20 average bytes per name = 300 KB string. Which not a big at all for modern PC.
3. We not store or calculate count of duplicates of each name - because this info not need for user but compute it not easy task and spent iterations for nothing.
4. IDK how really compiled this code, but possible "continue" inside "if" make less Jumps from usual "if-else".
5. We use fact about actor names - it is indexed name and can not be different cases if names same - for avoid case-insesitive search (which slow) or lower all data before make buffer or search.
6. All data stored in vars for prevent compute same stuff twice.

In general it is transform from general decision to decision optimized for our task with usage appropriate algorithms.

---
> If you have faster solutions I'm eyes and ears.

Show real bottleneck with code and task conditions - I can try think what can be done.

---

Automatically merged

You need fixing? No problem.

In general it is bad idea because only human can decide what wrong here. Safe delete actor or not. But if you want...

If you need only duplicate actor you can do it just in-place in loop.
Instead of
Log("Duplicated: " $ tmp);
you can call
Actor.Destroy();
for example or do something other.

If you need both actors of duplicates you can make string which contain all duplicates names and make second foreach loop over all actors.
If name in list - apply some fix, store in linked list - do what you want. For example set bHiddenEd based on it. All match set false. All other - true.
And let's user manually investigate what wrong with this duplicate.

Second search even more faster operation, because operate on fixed buffer and not mess on concatenate strings for new buffer.

[sektor2111]

I'll remap this finder and fixer as an alternate option.

[Buggie]

About A B C task - in general need write any dumb prototype implementation which able work at all on test case.
Only after make good prototype make sense try optimize it only if not fit some requirements on big data.

Now it is more like pure idea. Good luck with that. There nothing do for optimization yet.
You need make worked example for little input data before start think about any optimization.

---

Automatically merged

In general need understand simple thing - not exists bad algorithms. Exists algorithm implemented in conditions which not good.
If you fine with bubble sort - no any problem:
https://github.com/Slipyx/UT99/blob/f2e ... ath.uc#L99
// Now sort the elements (using a crappy bubble sort.. hey it's < 30 elements)

When you have 30 elements picked sort algorithm really doesn't matter.

When you have 15 000 elements it can be problem.

In general you need reduce amount of work and after that you can use any simple approach.

For example with duplicates - after you built linked list contains only duplicated items you can do any slow things.
If you have 100 duplicated actors, then you can use even O(n^2) algorithms and nobody die.
If you have more then 100 duplicated actors - just count it and work on first 100.
Tell about this user: I work on first 100 from your 1000 actors. If you want - run me few times.
So you fit all cases and avoid try solve problem which can be hardly solve and which possible never appear at all.

[sektor2111]

I don't know yet how to optimize code and if my initial solution it's a good one and it cannot be done more simple than that. This is first paths maker done in UScript using some XC natives...

XC_BrushScanner_AlphaRes.7z

(11.11 KiB) Downloaded 8 times

Keep in mind that I can create Navigation Chain. Epic "const" types for me are just plain stupid. What are for those restrictions anyway ?

SoFarStage.PNG (9.39 KiB) Viewed 534 times

[Buggie]

I worked a lot for not reaching at a crash resulting nothing, but right now I think the code should be more completed because runaway can be ignored...

If you not able make prototype which work for small subset of data - no any talk can be here.

If you have real prototype which good work on small subset but pushed to limit of iterations - we can talk.
Post code at describe what and where.

Bypass iterations count it is not an silver bullet at all.
10 000 000 iterations it is really big count. So if you not fit in it - possible user will be not comfortable wait hours for builds something.

Even f you able lift limits, need do this only if it is really last option.

---

Automatically merged

I don't know yet how to optimize code and if my initial solution it's a good one and it cannot be done more simple than that. This is first paths maker done in UScript using some XC natives...
XC_BrushScanner_AlphaRes.7z

What is bottleneck here?

[sektor2111]

A solution for Crowded Spots - Options, some "HowTo" hints. Using some square area, whatever...
Prevent multiple connections at Nodes in the same direction, picking best options toward collision accepted for similar directions, etc.

I'm not sure if this "template" mainly is the answer at how a Paths Maker should work. It does paths but maybe are not the best ever ones.

[Buggie]

This is first paths maker done in UScript

Look like as wrong tool for this,
UScript significantly slower from plain C/C++. In such things it really matter,
So you better look for native mods for this.
UScript will be slow as hell.

It is bad choice it only because you know only it.

It is same as try render something complicated on it. You never win in fight for FPS.

Optimization of course can get some profit. But this profit is not endless.

You choose wrong tool on start - so your idea is dead even before born.

For simple task UScripts fits. For complicated like build fresh navigation network - definitely no.
Better spent your time for learn C++ and make native mod instead.

UnrealEd currently exists only for Windows so you not need mess even with Linux and MacOS.

Let's be honest UScript is ugly but safe and good for scripting. Not for real code.
Good tool for special set of tasks. Build navigation network not contains in this set.

You need example of wrong tool for solve problem? Look At UnrealEd 1.0 written on VisualBasic.
They too (possible) know only it on time of creation. This not help. Until UnrealEd not rewritten in C++ it be almost unusable thing.

Maybe not need repeat such mistake?

---

Automatically merged

A solution for Crowded Spots - Options, some "HowTo" hints. Using some square area, whatever...
Prevent multiple connections at Nodes in the same direction, picking best options toward collision accepted for similar directions, etc.

it is idea.
Bottleneck sounds as
"I know how compute this, but it take too long or too many iterations. Here code <CODE> it is work fine for this simple map, but spent too much time/iterations in this place."

For example with duplicate actors:

"I search duplicate actors, but my code use complexity O(n^2) and when I run it on 15 000 actors I get 225 000 000 iterations with overrun. Here main code of it <CODE>"

[sektor2111]

Look like as wrong tool for this,
UScript significantly slower from plain C/C++. In such things it really matter,
So you better look for native mods for this.
UScript will be slow as hell.

Yes and no.
While in a simple map Editor does a lot of load and taking 5-6 seconds or a little bit faster, this builder does simple paths under 1-2 seconds depending on range used preventing a lot of not needed "shortcuts" at 1000 range. But... I will work here alone, in the way I know if you think this has no use - I already mapped paths with this boy and... you can even manually connect missing things - if are needed or adjust paths dimensions for bigger pawns - It's what Editor will never do and I'm serious when I'm saying that Editor is slower. Code here is too simple for taking ages, it will take more if it goes more complex than that. I wrote everything here from byte zero thinking more simple as possible.
Let's check a simple stage with Editor known as Goblin

And then my not the best ever Pathing tool - Results in Non-Monster Mode:

You see ? I do not have reasons in such a stage for using Editor with those invisible PrunedPaths and other useless ones guiding pawn in the same locations.
Even if it would be 10 times slower, I will still use it if it does VALID and REAL paths not those jumpy stories. Either way, here are not added those "chains" or bytes without any usage as long as map during run-time is adjusted constantly. For me it's also important the capability to add missing paths exactly how I want in UT, not only in U227, and this builder can do exactly what user wants - if user knows what is doing.

If you will give me something in C++ for this task, flexible and with all needs I'll install it in my Editor in seconds.

[Buggie]

You do not understand me.
I tell you one thing, you tell me something else.

First. Everything written above concerns a full-fledged navigational network builder.
This is when you press a button and it SELF builds the entire network, inserting the missing PathNode where necessary.

This is called a navigation path builder.
You can't do anything here without C++.

You may be trying to build an existing network optimizer. This is when you simply add paths between existing points without creating new points.
Or you delete unnecessary paths.

Here you still have some chances. Although, in general, it is better to do such a task in C++.

I didn't mention Editor at all. I don't know why you dragged him in.

You need a tool - VisualStudio is at your service.
Learn C++ and write your path builder or corrector in a very fast language with powerful features.

---

Automatically merged

UScript is a victory in portability at the cost of speed, flexibility and power.

Why do you need this portability if you need to work only on Windows exclusively in UnrealEd v436?

Compile your .dll, connect it to UnrealEd as a native part of the UScript class and do very cool things quickly and without straining.

[sektor2111]

Okay, the right terms would be Paths Definer not Paths Builder. The tool won't add PathNodes, not even Polge didn't do this properly...

The tool does a sort of "Paths Define" but flexible if you look at second image. It's all simplified and operational.

Why I mention Editor ? Because these are Builders known as Editor Plugins and this builder did a better job than those C++ natives. And you asked me what any code should be adjusted simplified. Not only MapGarbage can be enhanced but... we do have other things available and doable because already XC has a few things usable as they are.
Look here:

Code: Select all

native final function bool GetReachSpec( out ReachSpec R, int Idx);
native final function bool SetReachSpec( ReachSpec R, int Idx, optional bool bAutoSet);
native final function int ReachSpecCount();
native final function int AddReachSpec( ReachSpec R, optional bool bAutoSet); //Returns index of newle created ReachSpec
native final function int FindReachSpec( Actor Start, Actor End); //-1 if not found, useful for finding unused specs (actor = none)
native final function CompactPathList( NavigationPoint N); //Also cleans up invalid paths (Start or End = NONE)
native final function LockToNavigationChain( NavigationPoint N, bool bLock);
native final function iterator AllReachSpecs( out ReachSpec R, out int Idx); //Idx can actually modify the starting index!!!
native final function DefinePathsFor( NavigationPoint N, optional Actor AdjustTo, optional Pawn Reference, optional float MaxDistance); //N must have no connections!

I don't think I need to rewrite these twice. They are done, ready for use.

For MapGarbage I wanted something as helper and this is what it is. Instead of checking if a FlagBase is okay, builder is reporting problem instantly. Why not ?
Instead of counting Starts you have the tool during an eye blink and more things useful preventing an average of time wasted with details heavy to track with eyes.

Either way if you will help me with a tutorial about writing simple C++ assets starting with lesson ZERO - including configuration needed and all required dependencies, you can imagine that I'll download it and I'll read it. Doesn't matter language I can read all sort of english formats.
The fact is in UT there are already embedded functions which unfortunately are not very documented and all stuff must be checked line by line, eh...

Why working in 436 ? Because builder works also in 469b under XC_Engine v25b but... it's 4-5 times slower - believe me or not, the script is moving like a doggy slow in 469b.

Edit:
Okay, recommend me other optimizations doable in MapGarbage.

[Buggie]

Even for Paths Definer, you need the speed and flexibility that UScript has problems with.

So I advise you to learn how to write native classes and code for them.

But you can of course continue to hammer in nails with a microscope. At first, and with simple tasks, the microscope also copes there.

In general, I advise you to study graph theory specific for this task, since that's all about it.

As for what comes with UT v436 - unfortunately, almost any implementation is better than what is out there. So it's pointless to compare with him.

---

Automatically merged

You can't teach programming. These are the things that you learn yourself. If they want.

You yourself were engaged in all this fuss with paths and so on.

All information is easy to find if you want.

You can get started here: viewtopic.php?p=39260#p39260[hr][/hr]

Automatically merged

I cannot give advice on what I am not aware of.

As I wrote earlier, if you show the code the bottleneck and the problem conditions, it is possible find something. Improve existing code.

[sektor2111]

All right then, I'll look elsewhere for C++ Lesson Zero when time will come for that - there is a discussion already at another Level, for the moment my builder does what has to do and I'm not sure if worth wasting time writing the same thing in other programming language for getting 2 seconds. Improving traces and algorithm generally is my goal. Building paths in a private map which I received took 2.1 seconds - Editor did them in 6+ seconds adding 2316 specs while I got navigation with only 612 specs in 2 seconds - Monster Compatible, no pain, no headaches. Sooner or later I'll drop it out for users capable to install XC assets in Editor. I'm not in a rush, so far it's all almost as planned. I understand that you might go for another Level here, more expanded, perhaps x times faster - no doubt it can be better, but as guy which I don't work in programming in any way, what I did here is enough for me. I have a tool for fixes/adds and this is what I wanted UNDONE yet in a more Pro Formula and... I can live with these as they are if I don't see anybody else showing some good IT product - don't expect a non-programmer guy to do a Pro Tech product - it won't happen, more to speak is that I did not see yet anything like this done before, probably not all pro boys are understanding specs and what do they do and how to setup User Interface for manual paths handling/mangling.

In other hand I see there is nothing else to improve at MapGarbage. Good to know, I'll go for a relaxing time then.

[Buggie]

Native need not only for speed. Usually natives open new horizons. For example you can fix, improve or make own way of check Reachability if old not fit you.

For example possible create tool which align pillar texture in one click.

In C++ you not limited set of calls coded by someone else. You can add own which do what you need.