MAJOR bot-pathing request

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

Re: MAJOR bot-pathing request

Post by Higor » Fri Dec 30, 2016 4:12 am

Be advised, this is going to take a week (at least).

In the meantime, most of the initial work is going towards simplifying the path network.
- Increasing distance between path nodes in hallways.
- Making bunches of ammo items only generate a single InventorySpot actor.

Added a test MonsterWaypoint on the first objective (should be a button on the floor).
Will be testing once the whole path leading to this object is acceptable.

PD: Added a small Jeronimo shortcut which becomes available once someone uses the lift at least once so bots don't get stuck waiting one after another.
You do not have the required permissions to view the files attached to this post.
ImageImage
Image unreal://23.111.157.138:7777
Image unreal://46.228.199.205:7788

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

Re: MAJOR bot-pathing request

Post by Higor » Sun Jan 01, 2017 4:56 am

Lil' update.

First goal pathed, FerBotz play it almost great (they aggresively rush towards titans lol), UT bots need a little assistance yet.
I'm using the ancient MonsterHunt.u (first build) on this UnrealTournament, the good side of this is that if it works here, it works in all MH builds.
I don't think I'm gonna path the whole water, will think of a workaround later.

There's a lot of item clusters creating unnecessary InventorySpot actors and possibly breaking the navigation network.
I temporarily took most ammo's out during test builds to avoid this (it's all saved don't worry).

Removed all 8 PlayerStart actors.
Added a single 'SpreadPlayerStart' with:
- Matrix size = 384
- Matrix subdivision = 7 x 7
** This single player start can spawn up to 49 players at the same time without a telefrag.

Teleporter destinations moved 256 units above the ground so they are not used during navigation (except when teleporting).
Created a 'TeleporterPathFixer' actor that runs through these teleporters every second and disables navigation between teleporter and destination if not enabled.
- Can cache up to 48 teleporters, destinations, and reachspec index.
- Will remove the reachspec on both ends when disabled, readd when enabled.
- Will set 'ExtraCost' to either 0 or 10000000 on the destination to double-ensure those disabled teleporters are not considered.


I'm gonna halt pathing for a couple of days while I finish a custom Path builder on XC_Engine, and this map will be the experiment.
Some stuff I want to change with this path builder:
- Altering max scan range between path nodes (default is 1000)
- Avoid deleting InventorySpot (and derivates) that are visible in the editor.
- Avoid adding InventorySpot into items/weapons that are not visible in the editor.
- Force a connection between any generic NavigationPoint with it's 'Event' field.
- (Maybe) Automatic addition of LiftCenter actors to elevators without them.

If this works as intended I'll be able to:
- Hide all ammo clusters and manually place custom InventorySpot's that auto-scan nearby items and marks them, this way one InventorySpot will work for each Ammo cluster.
- Reduce path node count in straight routes.
- Connect paths without resorting to weird placements.
- Simplify elevator pathing.

Want the current map build to check it out?
ImageImage
Image unreal://23.111.157.138:7777
Image unreal://46.228.199.205:7788

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

Re: MAJOR bot-pathing request

Post by sektor2111 » Sun Jan 01, 2017 12:11 pm

In large fields I wouldn't add a bunch of nodes, NoLost Actor unlocks Bot perfectly... However, that island is stupidly isolated from main route, there are needed a few links + a few nodes in water here and there as references in case of insane hunting leaving pathed area, but not entire lake needs paths, just visibility to a node from path-net...

Yeah I'm interested about that Teleporter-Control because I was thinking at some iterator from time to time switching cost, probably you have a solution way better optimized.
Higor wrote: Teleporter destinations moved 256 units above the ground so they are not used during navigation (except when teleporting).
This should be done by default but no one cares.

Else for advanced pathing hacks I guess the map has to work without XCGE as well... there are plenty of people staying away from XCGE, (Linux the mostly) for different reasons - they did not post their issues for getting help ( :noidea ) and then we need the map to work as should without any XCGE dependencies. While I was running XCGE properly I did not have that much issues as I had without XCGE in the past - I go for XCGE but no Adds, PrimitiveMesh in maps with 220 creatures made tickrate to go at 1-5 values deviating a lot, pretty expensive for me, but anyone having an I20 CPU can experiment what wants. For machines without SSE2 this seems utterly borked, it's almost stuck machine. However, for "default" games using monsters I'm using this mesh system (max 20 creatures spawned /Level) it helps in preventing dumb telefraging of monsters - ONLY for monsters I'm using it).

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

Re: MAJOR bot-pathing request

Post by Higor » Mon Jan 02, 2017 9:13 am

The XCGE path maker works wonderfully, got to cut InventorySpot actors to a third and there's way less PathNodes around.
Added a couple more MonsterWaypoint actors into the stronghold but bots easily get stuck in gates, will do something about that later.

My biggest concern is that at some points bots will simply stop searching for a route when they hit X navigation point (changes everytime I rebuild the network), I believe there's way too many nodes in the map and I'm gonna have to remove a whole lot more of them.
ImageImage
Image unreal://23.111.157.138:7777
Image unreal://46.228.199.205:7788

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

Re: MAJOR bot-pathing request

Post by sektor2111 » Mon Jan 02, 2017 11:59 am

Well, if map has a bad geometry (WarMaster said that if I well recall) it's possible to have areas where DevPath doesn't move nothing. On slow machine map develop lags... else teleporters, yes...., okay I'll try my way then, first I need to know if areas are navigable else it's a waste of time trying Bot Support.

Edit:Ok, I changed slow machine with a better one now let's see what do says MHBotyMan about teleporter zones...
[attachment=0]Tele_Zones.jpg[/attachment]
I did not activated any teleporter there yet but... shortest route to Position2 is there, definitely I have to write something for DevPath :loool: EPIC. Where is the damned SpecialCost ?
Edit2:
I guess I have properly hacked Teleporters group:
Spoiler
Show

Code: Select all

//=============================================================================
// TeleControl.
//=============================================================================
class TeleControl expands Actor;

var() int TrackRadius;
var() float CheckInterval;

event PostBeginPlay()
{
	InitialState='TrackPlonkers';
	if (CheckInterval <= 0)
		CheckInterval = 3.000000;
	if (TrackRadius > 1600)
		TrackRadius = 1600;
}

function CheckAndSet()
{
	local Teleporter T;

	foreach RadiusActors (class 'Teleporter',T,TrackRadius,Location)
	{
		if (T.URL != "" && (T.class == class'Engine.Teleporter'
			|| T.class == class'BotPack.VisibleTeleporter' 
			|| T.class == class'UnrealShare.FavoritesTeleporter'))
		{
			if (!T.bEnabled)
				T.ExtraCost = 10000000;
			else
				T.ExtraCost = -2;
		}
	}
}

Auto State TrackPlonkers
{
Begin:
	Sleep(2.00);
Looping:
	CheckAndSet();
	Sleep(CheckInterval);
	if (Level.Game.bGameEnded)
		GoToState('');
	GoTo('Looping');
}
But indeed some Nodes have to be more spread and stupid ammo under 50 UU distance from each-other also need more love.
Edit3:Okay, some paths are needed down in water because... if pawn hunter is boosted from elevator around towers, after a long fall, wild water driving nowhere doesn't help. Next annoying thing Triggers and Doors, it seems like with over 200 Movers in Level, triggers won't react as should - Timeeeers !. I must look over some stuff in purpose to prevent Bot stuck at doors... :wth: .
Edit4:Karma popped into stage. Around that long range elevator Bots were waiting their turn, eh, one of them has noticed snipers from building far way and decided to fire a redeemer, now team has been blown away. Okay they were recovering PathNet (MBot_D natively) but that long route to Towers area back to elevator did something funky:

Code: Select all

DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
DevPath: 1000 navigation nodes searched from PathNode1145!
Veery long route, probably this way map won't work. Time for a small, break. I think I have to lock routes unused, else I have to do some voodoo nodes which might go in sleep when no seeker has been noticed 10 minutes by looking the route for being discarded from seeking cycles. I'm not sure if this is a response but I don't know how to get over this limitation... Else for this Level assuming all team is into last area, I think that first area until first lift to water can be ruined and PathNodes buried in order to discard from now on unused long routes. By Example if a Pawn has reached on bridges and shortcut has been created we can ruin completely paths behind based on their TAG or simply a start and an end might be increased in cost in purpose to discard that old route.
You do not have the required permissions to view the files attached to this post.

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

Re: MAJOR bot-pathing request

Post by Higor » Tue Jan 03, 2017 7:09 am

Teleporters?
Not a problem.

Making bots go around said teleporters?
Not a problem.

Bots failing to board lifts that return upwards?
Not a problem.

Bots failing to use horizontal lifts?
Not a problem.

Finding that FerBotz have a bug that make them unable to handle both cases of lifts?
Well shit, time to patch FerBotz right after I release XC_Engine v19.
And this FerBotz build will be 100% unrealscript, but with mandatory XC_Engine v19 requirement.

=========
Maybe I could release a small guide to help pathing this very difficult cases.

Also, no need to add a trigger on top of an elevator that can be called from a secondary button/lever.
Just set 'PlayerBumpEvent' to the lift's own tag and it will self-trigger when you stand on it, also bots understand it when the lift goes up-to-down instead of down-to-up.

=========


PD:
XCGE path builder magic in action, deprecating 227 editor little by little.
You do not have the required permissions to view the files attached to this post.
ImageImage
Image unreal://23.111.157.138:7777
Image unreal://46.228.199.205:7788

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

Re: MAJOR bot-pathing request

Post by sektor2111 » Tue Jan 03, 2017 7:38 am

Horizontal lift called Mover113 set me on trash.

Well, I have to write a small toy for Bot because they don't have a lot of patience there, else Bot boosted away by Snipers is just falling... long fall... right in the lake. And... from lake to a said waypoint P12 they just went over 1000 Nodes. By using only default engine I did not exhausted solutions yet, I have to make things to work in 2 pieces of road:
- Bot from lake will only walk to Start for items - ONLY in base I need InventorySpots letting them to gain stuff a la DM like a magnet;
- Bot arrived in Base will go at top again because... from this Start-Location I am still under 1000 nodes.
Problem comes when both roads from middle of lake to the Mover113-Waypoint12 is just getting over 1000 Nodes and then I think to remove a lot stupid nodes from roofs of some buildings as well because... are useless, no, I lie, they are "useful" for blabbering DevPath with a charge with no purpose. Such a map with long routes (LandsOfNapali) is being still navigable if routes checked are sequential (parts of Path-Net), when a Pawn is falling or some bad location makes it unable to see paths, engine will test every point getting over 1000 Nodes - because UE1 is very "optimized" at this point...
Else if I won't be able to do this task for default engine, I'll apology to EG in the name of this Ross guy, clueless with lifts and I won't do nothing at this point, and then... XCGE with your solution will enter stage for this mess which has BSP, rendering problem at very far surfaces, a bit of frames lost (eh, my rigs) - map is pushing UE1 beyond boundaries, DevPath is the first one perfectly rammed, yeah "awesome" map...
All I did until this moment is UT's UE and nothing from 227 - I'm not making an editing soup. Map running in UT will use UT's Engine regarding to other "powerz" which won't help here...
Probably this is an example showing why do we need XCGE.

User avatar
Barbie
Godlike
Posts: 2152
Joined: Fri Sep 25, 2015 9:01 pm
Location: moved without proper hashing

Re: MAJOR bot-pathing request

Post by Barbie » Tue Jan 03, 2017 2:19 pm

Is that limit (I think it's a limit?) of 1000 configurable in any way? It looks like an arbitrary choosen value matching hardware power of the late 1990th.
BTW: Does anyone know what algorithm is used in UE1 to find a path between two network points?
"Multiple exclamation marks," he went on, shaking his head, "are a sure sign of a diseased mind." --Terry Pratchett

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

Re: MAJOR bot-pathing request

Post by sektor2111 » Tue Jan 03, 2017 4:37 pm

Barbie wrote:BTW: Does anyone know what algorithm is used in UE1 to find a path between two network points?
Ask Smirtch, he was working at UE1 for Unreal - mainly original natives are the same.
Configurable ? No. is hard-coded for preventing nasty things (- it does lags anyway). Trust me, when 500 pawns are looking for a path to some sudden enemy tickt-rate went to 0.3 in my machines and I'm doubt to not mess even a stronger machine.
At a moment I was thinking to rewrite something in UScript but... I think is a dumb idea, because UScript cannot access all natives involved. If I'm not mistaking the name we can think about Dijkstra's algorithm.
https://en.wikipedia.org/wiki/Pathfindi ... _algorithm
but probably UE has add-ons (SpecialCost, Extracost, OneWay, ReachFlags, etc) Higor knows better these, he worked with them, even he was showing how to link 2 Nodes un-linked right in game and creating new paths.

Recall what I was saying: CPU Cycles not CPU Timers - this is main mistake and for this reason better a CPU is not that helpful as supposed due to these hard-coded limits. Strong machines I'm sure they can find paths with high speed even scanning 9000 Nodes (9.000 × 800 UU = around 7.200.000 UU Navigation Length) but right now it clamps at 1000 × 800 = 800.000 UU - for happy cases with ideal geometry else it is lower.

I think Higor can bypass this default limit with the price of performance but... a configurable option CPU dependent would be priceless (FinPathToward, FindPathTo, FindRandomDest, FindBestInventoryPath - lol, RouteCache[64]), I'm already dreaming green horses in kitchen... :lol2:
Aside if I would be skilled in Machine Code I would byte-hack this limit for my personal needs (and for who need such things).

Edit:On Topic a bit. Map has some BSP trobles in the cave with flies (somewhere in lake) there paths went broken due to some ledge. After a rebuild I got 2 paths over that point but... bug was moved in one tower making DevPath to clamp before Position11 creating a nasty invisible barrier. I still get a few tens of warnings right from Editor, regarding to reducing paths in caves and around large areas, I think I'll wait Higor's results, I'm getting tired of testing stupid things.

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

Re: MAJOR bot-pathing request

Post by Higor » Fri Jan 06, 2017 8:05 am

I got one horizontal lift working, it involves a supplementary AttachMover to cleverly place the destination LiftExit during the main lift's movement.
If the bot can see the destination LiftExit in a horizontal trip, it'll attempt to reach it... play with that in a test map lol.
Now I have to properly make the last horizontal lift work for UT bots (FerBotz handle them ok without the attach trick).

The whole map is already pathed except some caves and spots in the water, and there's MonsterWaypoint actors located only at major objectives (as it is intended).
Any other behaviour besides going after objectives has to be properly handled by the bot controller (either in MonsterHunt or in the Botz plugin).

Speaking of FerBotz, lift handling got far better in 3 hours than in 3 years, it really does when you create an utilitary function like this:

Code: Select all

//*************************NearestMoverKeyFrame - Mover a BFM, DistanceThreshold adds an additional check to make sure elevator is near said target keyframe
static final function bool NearestMoverKeyFrame( Mover M, vector TargetPoint, optional float DistanceThreshold )
{
	local float Dist, BestDist;
	local int i, iNearest;

	//First, find which keyframe is the nearest to target
	BestDist = VSize( M.BasePos + M.KeyPos[0] - TargetPoint);
	For ( i=1 ; i<M.NumKeys ; i++ )
	{
		Dist = VSize( M.BasePos + M.KeyPos[i] - TargetPoint);
		if ( Dist < BestDist )
		{
			BestDist = Dist;
			iNearest = i;
		}
	}
	return (M.KeyNum == iNearest) && (DistanceThreshold == 0 || VSize(M.BasePos + M.KeyPos[iNearest] - M.Location) < DistanceThreshold);
}
It easily lets you figure out if a lift is coming towards you or not, you can also add a distance requirement to make sure the lift is near the intended keyframe (not just interpolating at any point).
If it returns true, it means the lift is coming to the best keyframe for TargetPoint and that it's within the required distance (to said keyframe)

Once I get to run another succesful local test with both kinds of bots in it I'll put in a preliminary version of the map here (only the UNR file).

=========
Regarding FerBotz:
- XC_Engine v19 will be a mandatory requirement for it and I'll try hard to get rid of FerBotz.dll in favor of XC_Engine.
- Will also get rid of the dummy pawn hack for servers and will try to replace with a relevancy trick.
So the whole roadmap is:
This map > XC_Engine 19 > FerBotz > MonsterHunt split.
Will try to do this over these days as quick as I can.
ImageImage
Image unreal://23.111.157.138:7777
Image unreal://46.228.199.205:7788

User avatar
Carbon
Inhuman
Posts: 855
Joined: Thu Jan 17, 2013 1:52 pm
Personal rank: Hoarder.

Re: MAJOR bot-pathing request

Post by Carbon » Fri Jan 06, 2017 9:44 am

Higor, you're a beast! :gj:

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

Re: MAJOR bot-pathing request

Post by sektor2111 » Fri Jan 06, 2017 12:05 pm

Carbon wrote:Higor, you're a beast! :gj:
That's good to me...
However, using Original Engine (as the most of users) this map will look like without too much Bot options - exactly as it is. Only using another natives (C++ in stage) maps becomes operational. EG, get ready for 21th century - XC_Engine proved itself a M.H. (Not Monster Hunt as much as... a Must Have).
Explanation: map pushes Engine beyond hard-coded limitations so run-time hacks are needed right here or... another game-engine.

User avatar
EvilGrins
Godlike
Posts: 8237
Joined: Thu Jun 30, 2011 8:12 pm
Personal rank: God of Fudge
Location: Palo Alto, CA

Re: MAJOR bot-pathing request

Post by EvilGrins » Sat Jan 07, 2017 2:48 am

sektor2111 wrote:EG, get ready for 21th century
Image
...21st Century...
http://unreal-games.livejournal.com/
Image
medor wrote:Replace Skaarj with EvilGrins :mrgreen:
Smilies · viewtopic.php?f=8&t=13758

User avatar
papercoffee
Godlike
Posts: 9987
Joined: Wed Jul 15, 2009 11:36 am
Personal rank: coffee addicted !!!
Location: Cologne, the city with the big cathedral.

Re: MAJOR bot-pathing request

Post by papercoffee » Sat Jan 07, 2017 2:52 am

EvilGrins wrote:
sektor2111 wrote:EG, get ready for 21th century
Image
...21st Century...
You'll survive.

User avatar
EvilGrins
Godlike
Posts: 8237
Joined: Thu Jun 30, 2011 8:12 pm
Personal rank: God of Fudge
Location: Palo Alto, CA

Re: MAJOR bot-pathing request

Post by EvilGrins » Sat Jan 07, 2017 3:02 am

papercoffee wrote:You'll survive.
Image
http://unreal-games.livejournal.com/
Image
medor wrote:Replace Skaarj with EvilGrins :mrgreen:
Smilies · viewtopic.php?f=8&t=13758