Path MoveBlocked handling / re-pathing advice

Development Programming & Scripting AI
, , , , ,
1

I’m curious about how to best approach situations where the AI’s path is blocked by dynamic props/obstacles, other AI/characters, etc.

I’ve experimented with having certain characters/objects affect the navmesh when they are stopped, but it causes constant rebuilds and really segments the navmesh.

If I left things as they are by default using the base detour crowd wrapper, the AI will eventually be pushed around into a unblocked poly, but this solution is not ideal.

Ideally I would think the blocked AI would repath around what is blocking them, but I don’t know how to do that cleanly. I imagine you could find the poly that is blocked and exclude that with a custom query filter. I imagine that making dynamic navigation area’s that affect an area cost is also not an ideal solution.

I could see the situation happening a ton in Paragon so was wondering how its being tackled.

2

Hey Daniel,

Annotating navmesh when an obstacles stops is the ideal solution, in terms of the effects you get. It’s not ideal if you have a lot of objects like that, because you’ll end up with lots of navmesh rebuilds (although impact here can be controlled by navmesh tile size).

Paragon indeed suffers from this as well, and to be honest we haven’t handled that just yet :slight_smile: We’re currently using CharacterMovementComponent’s RVO implementation.

Regarding toggling “blocked” polygons on/off (or changing the area ID), it’s a good idea, but the effect heavily depends on navmesh triangulation. It might be fine, depends on the specific game.

Alternatively you can offset the visual indication of this issue occurring by having pawn bump reactions, and having static pawns give way to moving ones.

In short: it’s not a trivial issue :slight_smile:

Cheers,

–mieszko

3

We’re currently using CharacterMovementComponent’s RVO

Could you please list the reasons why you don’t use CrowdFollowing? At a first glance, it is much more superior solution.

4

It offers much better accuracy, but performance price is quite high. Even if you disable all internal repaths that detour crowd does under the hood, it’s still slower.

We’re not using regular path following most of the time either (in favor of baked flow fields, cuts down both path finding and path following time) but still need avoidance between AI agents and players. Detour simulation requires some input velocity from current path to work on. Including external inputs means selective control over simulation steps and this is too much of a hassle, especially since end results are slower than AvoidanceManager’s RVO.

Only missing part is navmesh edge awareness. We added hookups for it (4.11 IIRC) with INavEdgeProviderInterface and use simple octree based cache.

This doesn’t solve blocking/repaths like Mieszko mentioned, but is good enough for what project needs.

5

Any chance you could give a rundown on the baked flow fields and how that interfaces with the nav system? My project has AI with extremely similar pathing needs as paragon.

6

Navigation on map doesn’t change at runtime. All/almost all walkable areas have single Z value for given XY pair, aka no overhangs.

Custom navigation data actor holding arrays of 2D tiles, one for height data shared across all lanes, one for move directions. Directions are stored for specific lane + team pair to suit project needs.

Important overrides:

  • ConditionalConstructGenerator() : custom generator
  • GetBounds() : required
  • NeedsRebuild() : keeping in sync with navmesh, set by NavigationSystem, cleared after flow field rebuild
  • ConstructRenderingComponent() : data rendering

Also some caches, lookups, reading data from flow fields at given location, etc.

Navigation system overrides OnNavigationGenerationFinished() to mark flow field nav data as dirty when navmesh is updated. We spawn and register flow field nav data manually in Build() override, although right now I don’t remember why…

Supported agents define both navmesh and flow field actors, but only navmesh have valid agent size (radius+height), to ensure that all AIControllers are using it by default.

Path following component makes use of FCustomMoveSharedPtr param in RequestMove() to switch between using regular navigation path and flow fields. Second option is skipping everything in UpdatePathSegment() and reads desired velocity at agent location from cached flow field inside FollowPathSegment() function.

Move itself it triggered by simple behavior tree task: cache data, make FAIMoveRequest with custom game data param and send it along fake FNavigationPath to AIController.RequestMove()

Always use navmesh paths during combat.

Custom navigation data generator handles creating actual flow fields. Since we’re using navmesh to do all path findings, build have to wait for it.

Important overrides:

  • RebuildAll() : try to start (NavigationSystem.GetMainNavData, check if generator is still running - IsBuildInProgress())
  • TickAsyncBuild() : the same
  • IsBuildInProgress() : wait until rebuild is finished

Generation itself it pretty straight forward:

  • gather lane data from actor markup
  • build poly graphs for each lane+team pair flooding navmesh from goal, use polys on lane axis to guide exploration (costs)
  • once we have walkable space defined (sum of graphs), generate 2D tiles, locations of samples and shared data (height, etc)
  • for each tile, run async task that goes through all samples in tile, finds desired move point, path to it and stores direction along first segment
  • postprocess data to add some smoothing, handle drop down links
  • additionally, mark all navmesh polys outside walkable space (inside geometry) with null area for easier projection later

It’s worth to mention, that running expensive part - pathfinding and postprocess - in parallel (Async, TFuture types) allowed signification speed boost for rebuild in editor (2m down to 10s IIRC). Also, navmesh exploration and building lane graphs needs to be done manually through RecastNavMesh.GetPolyNeighbors because built in flooding will very likely exceed limit of visited nodes.

(sorry for hijacking thread :smiley: )

7

Awesome reply, this is exactly the sort of thing I was looking to learn more about.

(my thread so I don’t care =P )

8

So I started diving down this rabbit hole yesterday and had a few more questions. Not sure if this should be discussed via email or another post or something else. This might be too granular and too specific for whats commonly answered, but I figured I’d give it a shot.

I got all the easy classes setup and have the generator left to code. Are there any plans to port what you have over to main or could I reference it in any way via perforce or similar? Would save me a lot of time :O.

My current gameplay scenario is I have a variable # of lanes with the AI moving towards a target. The target will sometimes move, but not when any AI are around and there might be multiple targets, but not multiple targets for a single AI.

I plan to regenerate the poly graph during our down phase when there is no AI around and I have the cycles to spare. The level layout can change during gameplay, but not while AI is active. The direction samples for a given tile should not have to change that much. The AI will revert to normal pathfinding when it aggro’s an attackable target. I could potentially generate all possible baseline polygraphs, but we also have player placeable props that cut out the navmesh.

The custom Navigation Data is spawned and registered in the derived navigationSystem build() override since its like the abstract nav data and not associated with a given agent right? That’s the only reason I could see why it would be spawned there.

Currently I’m just overriding follow path segment in the derived path following component to get the direction from the flow data. The AI should only stop moving when its in combat and using normal pathfinding so I think that should be enough. I was curious if/where you created the fake FNavigationPath and how it was used in normal requestmove execution via the custom BT Task. After one of my AI spawns they will currently only have a single desired move point, unless they are in combat.

On a code note I had to declare an implementation of FallbackAgentRadius inside my derived navigation system due to the extern declaration. It seemed a weird way of declaring a fallback default global.

The main part of the generator that I was unsure about was how you subdivided the poly graph into the set of uniform 2D tiles and then samples. From a data perspective that part is a little confusing/vague to me. The past influence map work I’ve done has all been on a uniform grid and I’m not sure yet how to layer a similar type grid onto the polygraph to get the uniform samples for defining the direction.

And lastly, what actor markup data do you use for the initial polygraph generation. Currently I was planning a basic pre-placed set of actors to define a lane/direction and floodfill out from those actors to a defined distance from the source lane actor.

9

I don’t have any plans for moving implementation outside Paragon, it’s not generic enough.

Navigation data is spawned manually because I didn’t want to associate it with any agent params. It ensures that nothing will try to use FindPaths on it directly when someone changes or adds new agent setup. Ideally, this should be handled on navigation system side, but it needs to wait it turn for refactor/feature pass :confused: Thanks for mentioning about FallbackAgentRadius, I’ll add a new ticket for it.

Main purpose of build overrides was to include flow field during editor path rebuild. What you’re describing sounds like dynamic one, not necessarily coupled with runtime navmesh updates. Since you’ll want to trigger rebuild manually when game is in right state, it may be better to detach your navigation data from regular rebuild flow: ignore RebuildDirtyAreas, never SupportsRuntimeGeneration or NeedsRebuild, empty RebuildAll, own function for accessing/duplicating ANavigationData::RebuildAll.

As for the triggering part, we simply use dedicated BT task. It handles requesting, AController.ShouldPostponePathUpdates (can’t path while falling, etc) and aborting on its own. Fake path is passed only to make path following, since there are a few Path->IsValid calls scattered around. Could be better and reuse some data, but works for now:

	FAIMoveRequest FakeRequest;
	FakeRequest.SetUsePathfinding(false);
	FakeRequest.SetUserData(MakeShareable(CustomData));

	// don't register in navigation data, this path won't be used
	TArray FakePathPoints;
	FakePathPoints.Add(FVector::ZeroVector);
	FakePathPoints.Add(FVector::ZeroVector);
	FNavPathSharedPtr FakePath = MakeShareable(new FNavigationPath(FakePathPoints));

	const FAIRequestID RequestID = MyAI.RequestMove(FakeRequest, FakePath);
	const bool bRequested = RequestID.IsValid();

Splitting data into two sets of 2D tiles is memory optimization and one of “not generic enough” reasons. Our flow fields share quite a lot data (e.g. two one directional flow fields for each lane), but at the same time there are huge pockets of emptiness in space defines by navigation bounds. If your project can use simple 2D grid then it’s better for you :slight_smile:

For markup, we have a goal actor (enemy base) and simple actors placed along lanes organized into arrays. Exploration starts with
finding paths between those lane actors and then we flood from goal. Link cost during flood loop is cheaper if neighbor poly belongs to previously found paths on lane - this allows shaping graph to lane geometry. If your lanes don’t need complicated shapes and using single direction is good enough then go for it. It really all depends on project’s design.