Is fewer paths better?

Tutorials and discussions about Mapping - Introduce your own ones!
User avatar
Zero_khan
Average
Posts: 31
Joined: Tue Nov 24, 2020 6:54 pm

Is fewer paths better?

Post by Zero_khan » Sun Nov 29, 2020 11:18 pm

Take DM-Morbias for example. The original author placed nodes next to each other and even next to ammo and pickup. Is having fewer paths better? Or must paths cover all possible areas of the map?

Suppose I make a corridor with two rows of pillars. Is it bad or good to place pathnodes at every intersection so that bots can run around every pillar?

I made a test room with two cases. Case 1 with 500 or so reachspecs. Case 2 with an excessive quantity of pathnodes to make the reachspecs go beyond 20000. I didn't notice anything different with bots, or with performance.
You do not have the required permissions to view the files attached to this post.
Good Bye. I'm leaving UT99 behind. I won't be around for UT's 30th.

Red_Fist
Godlike
Posts: 1883
Joined: Sun Oct 05, 2008 3:31 am

Re: Is fewer paths better?

Post by Red_Fist » Mon Nov 30, 2020 2:28 am

The least amount of nodes but will follow paths as if a Human were playing.

I try to never let the path lines intersect without a node. So I try to use the nodes just enough to still form a path without adding one in the intersection of the path lines.

That bottom picture is way to much.
Binary Space Partitioning

ExpEM
Skilled
Posts: 178
Joined: Wed Nov 09, 2016 1:48 am

Re: Is fewer paths better?

Post by ExpEM » Mon Nov 30, 2020 3:28 am

Fewer paths is faster to compute. But not necessary better.

A bot will always take the shortest path from 'A' to 'B', A bot knocked off of the path (e.g. splash from Eightball) will head back to the closest node to get back on the path.

Lets say you make a donut shaped level, if you place two rows of nodes with one on the inner radius and one on the outer radius the bots will always use the inner radius nodes to navigate around the donut because the path is shorter.

In your example of Morbius above, if a bot were standing where the camera is and wanted to grab a pickup on the ground level below it then in the first picture with less nodes it would jump down to the redeemer then backtrack under the lip, in the second image with more nodes it could jump down to the node in the corner of the redeemer base then under the lip saving a fractional amount of time and making it appear that little bit less bot like.

Edit:
Note: Shortest path doesn't mean fewest nodes it means shortest total distance.

User avatar
sektor2111
Godlike
Posts: 5340
Joined: Sun May 09, 2010 6:15 pm
Location: On the roof.

Re: Is fewer paths better?

Post by sektor2111 » Mon Nov 30, 2020 7:38 am

More nodes means loops as long as these devs are not perfect, these can be checked and seen in certain maps. UnPath.h refers to 3000 reachspecs, all time when I was lower I did not see any loop or issue. (Except default Bot's issues)
But it's not my problem if you do more spam data in maps, I won't use them.

The question is: Why Higor optimized his "Paths builder" from XC_Engine to work more simple with less paths, huh ? Because Engine has hard-coded limits not CPU limits. Sorting paths from a big array has chances to exhaust all those GCycles and discard paths at 1000 nodes searched...
viewtopic.php?f=5&t=13044&p=109109&hili ... om#p109106
viewtopic.php?f=5&t=13051&p=109137&hili ... om#p109137
If you take in account that from point A to point B are two reachspecs then you will want to be at least at 1400 1500 nodes or less for optimal operation.
More Nodes are just USELESS in all way. Even when I used default Editor devs and not working manually I could stay under 3000 and map was working smoother as oil... If exists a node in range and Bot can move there, other 4 nodes are having no purpose. Always the shortest route is granted to pawn - just check using default methods "RememberSpot" and "ShowPath".

And now... if I'm looking at the two images even if first looks simple and an ideal load for me on a way, I can see well certain paths doing a mess in that angle with ledge, those are Evils... they don't have to be there unless you will want to complete Bot_Jumpers...
Last edited by sektor2111 on Mon Nov 30, 2020 7:56 am, edited 1 time in total.

Higor
Godlike
Posts: 1832
Joined: Sun Mar 04, 2012 6:47 pm

Re: Is fewer paths better?

Post by Higor » Mon Nov 30, 2020 7:53 am

My input after all these years... the pathing network is better if
- Coverage over physical space is maximized.
- Physical pawn reachability is maximized.
- Reachspec count is minimized.

You can increase node count while at the same time decreasing reachspec count, it's a tricky situation but right now only achievable with XC_Core.
ImageImage
Image unreal://23.111.157.138:7777
Image unreal://46.228.199.205:7788

User avatar
Zero_khan
Average
Posts: 31
Joined: Tue Nov 24, 2020 6:54 pm

Re: Is fewer paths better?

Post by Zero_khan » Tue Dec 01, 2020 3:50 am

Just realized why sometimes bot run around in circles.
abc.jpg
BOT is at A and tries to jump down to B. But dumb bot JUMPs and end up at C. Bot runs back to A and repeat.

The solution is to block that specific path with a cube brush. Depending on the map you can imagine how much time is wasted checking bad paths everywhere in the map.

Another thing that I noticed. If there are paths connecting pathnodes that are too far away and there is no solid ground in between, then there is some BSP error creating solid ground in mid air. Fly there in spec mode and you hit some invisible wall or ground that is allowing bots to see that place as solid ground to jump on.
extra_path.jpg
You do not have the required permissions to view the files attached to this post.
Good Bye. I'm leaving UT99 behind. I won't be around for UT's 30th.

User avatar
sektor2111
Godlike
Posts: 5340
Joined: Sun May 09, 2010 6:15 pm
Location: On the roof.

Re: Is fewer paths better?

Post by sektor2111 » Tue Dec 01, 2020 8:19 am

It's nice that you understand some of these looping troubles how are happening. The fact is... there are more simple ways than building temporary brushes...
Evil path going down can be un-referenced in UT, even deleted in a more Pro Editor but not in UT. Even jumpy path over corner can be un-referenced (or deleted).
In other hand, you can push lower node A connecting point at bottom C and using a combo in straight line at ledge (90 degrees) having LiftExit near C Higher placed and pointing at C, all time map will support future builds without causing any damage. There are more or less stock maps ("bonuses") having this problem never described in tutorials and so no solution... but there are solutions. If pawn wants to move at point C will use combo as long as you are not creating an Evil reachSpec A-C but... more few others out of damaging movement. Sometimes the harder way is better.

Technically if this spot would be in my edits I would get rid of reachSpec A-C and even lowering node A. Then for going down I can add another node D in a better location at bottom and connecting A to D with a jumpy reachSpec. This is doable manually or else a Combo it's helpful for Editor's automated process of generating paths. Here newer point D can be linked where I want not where Editor says, but any future paths re-build will screw up all manual work.

Another way is using a blind teleporter (without teleporting) in MyLevel and connecting A-D in a more reachable manner. When Bot want to roam on top will do that, if wants to move down also won't have issues.
Zero_khan wrote:
Tue Dec 01, 2020 3:50 am
Depending on the map you can imagine how much time is wasted checking bad paths everywhere in the map.
Not necessary. If you know these buggers you can see them in seconds. Let me draw a scenario happening like I said and similar with your stage.

Edit: Done.
Bot fails to reach at bottom hitting the same floor, attempting a move through hole:
A_Bugger.PNG
Here is a combo solution.
A_Better.PNG
Usually I can see these before even to happen...
You do not have the required permissions to view the files attached to this post.
Last edited by sektor2111 on Tue Dec 01, 2020 9:12 am, edited 3 times in total.

Red_Fist
Godlike
Posts: 1883
Joined: Sun Oct 05, 2008 3:31 am

Re: Is fewer paths better?

Post by Red_Fist » Tue Dec 01, 2020 8:56 am

It looks like the area is too small for any practical paths. And do they have any other place to go ? like a pickup, or an enemy to chase ? Pathing is more map level with some tough spots in my opinion. They should equally disperse and not follow the same ways plus work their way around on the whole map level. Then they would have no reason to cycle through certain spots. As opposed to testing nodes with 3 or 4, the brush blocking seems not a good way to go.
Binary Space Partitioning

User avatar
sektor2111
Godlike
Posts: 5340
Joined: Sun May 09, 2010 6:15 pm
Location: On the roof.

Re: Is fewer paths better?

Post by sektor2111 » Tue Dec 01, 2020 9:00 am

NOPE, there are maps where these paths are needed but are bugged, I posted a solution above.

User avatar
Zero_khan
Average
Posts: 31
Joined: Tue Nov 24, 2020 6:54 pm

Re: Is fewer paths better?

Post by Zero_khan » Tue Dec 01, 2020 5:47 pm

Red_Fist wrote:
Tue Dec 01, 2020 8:56 am
It looks like the area is too small for any practical paths. And do they have any other place to go ? like a pickup, or an enemy to chase ? Pathing is more map level with some tough spots in my opinion. They should equally disperse and not follow the same ways plus work their way around on the whole map level. Then they would have no reason to cycle through certain spots. As opposed to testing nodes with 3 or 4, the brush blocking seems not a good way to go.
In my case there was a bridge and a health below. For some reason bot was trying to go down using the shortest path. But the dumb bot would jump and fail to fall down to where the health is, run back and try again. Forever in that loop.
Good Bye. I'm leaving UT99 behind. I won't be around for UT's 30th.

Buggie
Masterful
Posts: 510
Joined: Sat Mar 21, 2020 5:32 am

Re: Is fewer paths better?

Post by Buggie » Tue Dec 01, 2020 7:54 pm

My unprofessional and buggy 5 cents:

1. Look here for funny gifs:
viewtopic.php?p=123996&sid=3f355bfa1697 ... a9#p123996
Each picture is animated gif. Open it for play.
Conclusion do self. This is only facts.

2. About loops:
Bot are simple state machine without any memory.
So if fail reach point B from point A, and now in point C, and best path lead to point A, It goes to A and again try reach B. Which make loop.
No any memory of previous moves or failures. So if path can lead to loop - bot stuck on it.

Another example:
Bot has goal reach C via B, currently on A. but B point too high. So bot run to B, can not reach it and little goes to A and goes back to B. Forever.
This happens because of weird implementation of "bot reach position" stuff.
So sometimes you can think it is enough, but really bot not think it reach this point.

Example: armor on box in Deck16][ near lift.
Human can take armor not jump to box, because collusion cylinders enough wide for do this.
Bot never do this, even if you fix paths for allow it to see this armor from ground.
Because it walk not for armor. It want reach navigation node.
In most cases this targets similar, but not in this case.
So you can see how bot pickup armor and still try reach nav node for armor.
Because it dirty coded "reach node for item is same as take this item".
If bot check reach own goal like "I now has armor" + "armor on map taken" -> "i can do another task", it will be better.

3. System of paths not flexible enough.
Mapper just path some path nodes in some places and hope (and prey for this) UnrealEd understand his intention right and build desired connection between items.
No any fine tune.
Next level assumption goes when map run.
UnrealEd built some network which made on few assumption.
Bots use own system of rules.
Sometimes it is not correlate with rules which used when built network.

For easy cases all fine. In other cases can be anything.

Also rules very primitive mostly so produce not expected result for mapper.

For example jump to box with udamage in Deck16][ from ramp or from top near thighpads is easy for human. Easy for understand.
But not fit some simple rules used by UnrealEd (i can not say what rule exactly), so this connection between nodes can not be connected normally.

All of this things comes from simplicity code (because UT coded for weak CPU 20 years ago and mostly with unoptimal algorithms) and complexity task.
UnrealEd try read your mind when built network. Your communication very limited - you just place actors. You can not tell "i want there jump from here to here".

Upd:
Example of sektor show this:
scr_1606849139.png
let's analyze.
On first picture:
UnrealEd apply rule "if one node lower and angle in some range - then add yellow jump path between them".
Bot apply rule "if next path is jump path - make jump and aim to next node".
As you see "make jump" is mistake.
On second picture:
UnrealEd rule connect each LiftExit with LiftCenter mostly uncoditional.
Bot rule: "when follow path from LiftExit to LiftCenter just walk to here" + "when reach LiftCenter wait until height near same as target LiftExit and walk to it".
No any jump. So bot simply fall down.

If UnrealEd on first picture have rule for detect fall down ways it can work, but no such rule.
You do not have the required permissions to view the files attached to this post.

User avatar
sektor2111
Godlike
Posts: 5340
Joined: Sun May 09, 2010 6:15 pm
Location: On the roof.

Re: Is fewer paths better?

Post by sektor2111 » Tue Dec 01, 2020 10:07 pm

Buggie wrote:
Tue Dec 01, 2020 7:54 pm
If UnrealEd on first picture have rule for detect fall down ways it can work, but no such rule.
In UnrealEd this "detection" belongs to human eye... Usually I can see such paths in seconds - including those in angles nearby some column where Bot is looping due to Ledge rule vs Hitwall - BAD rule. But here are available two solutions:
#1 - unreferencing reachSpec - and moving nodes different;
#2 - adding a jumper/Kicker - kicker recommended "bRandomize" and a small Z velocity so to speak "screwing the screwed path" right on ledge - must apply this method if said route is mandatory for game.

Future sektor's tryout - adding a small Keypoint (BlockAll) causing Bot to lose contact with ground and then getting over ledge problem causing a jump in a bad mode... This is what I want to check.

I'm curious if something else can be done in UScript as a bad jumpy detector using some simple traces but... I think iterations boundary won't help in UScript and then, no help in overloaded maps :wink: .

Edit: On-Topic and tested.
This is a case when a jumpy bugger path won't need MORE paths and keeping them fewer and navigation operational.
First is the Image:
BadJump.PNG
This is the stage when we test ONE Bot (okay maybe two but not combat is the testing purpose) what does it do trying to gain HealthVials.
Let's see plain mapping where such stages are happening in X tens of maps. BAD case (I hope you'll figure it because I switched machines - this is slower, but I can see the hitWall bug).
DM-LedgeFail.7z
Bot here the mostly is hitting wall, unable to reach at desired jumpy angle trying to follow a path created by Editor itself this way.

And now let's see a short little tiny small correction - spectating again One bot.
DM-LedgeHack_well.7z
Loool, right now I was reading Polge's solution(s ?) at this 45 degrees angled jump request. That's only a BLA BLA BLA and not a solution when things were... Too Simple... Eh, he forgot what he did himself at pawn and how to cheat stepping... Here definitely we do have a bad angle but... issue mentioned in his document is like... almost None (except some combat stage but blocker can be a bit bigger) after tweaking a bit that ledge...

Note: This solution is supporting X number of paths building without any additional task. Such blockers are suitable in more cases - sometimes even for blocking the jump attempt through the hole and causing a forced fall and setting up collisions accordingly. Here can be used various other actors not only BlockAll type.
You do not have the required permissions to view the files attached to this post.

User avatar
sektor2111
Godlike
Posts: 5340
Joined: Sun May 09, 2010 6:15 pm
Location: On the roof.

Re: Is fewer paths better?

Post by sektor2111 » Thu Dec 03, 2020 5:38 pm

Okay, this should be "FlakForever" bug - it goes to ledge and jumping and failing...
ForeverFlak.PNG
Q: Solution ?
A: Yes...
First is The Bug...
DM-CornerJumper_Bugged.7z
And... Something different... Flak is Flak and Vials are Vials according to roaming desire...
DM-CornerJumper_Solved.7z
No more looping... Done ! Using the same paths like bugged version - once again, fewer paths is more recommended...
You do not have the required permissions to view the files attached to this post.