x

Search in
Sort by:

Question Status:

Search help

  • Simple searches use one or more words. Separate the words with spaces (cat dog) to search cat,dog or both. Separate the words with plus signs (cat +dog) to search for items that may contain cat but must contain dog.
  • You can further refine your search on the search results page, where you can search by keywords, author, topic. These can be combined with each other. Examples
    • cat dog --matches anything with cat,dog or both
    • cat +dog --searches for cat +dog where dog is a mandatory term
    • cat -dog -- searches for cat excluding any result containing dog
    • [cats] —will restrict your search to results with topic named "cats"
    • [cats] [dogs] —will restrict your search to results with both topics, "cats", and "dogs"

Office Holiday

Epic Games' offices will be on holiday from June 22nd to July 7th. During this period support will be limited. Our offices will reopen on Monday, July 8th. 

[Closed] Path MoveBlocked handling / re-pathing advice

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.

Product Version: Not Selected
Tags:
more ▼

asked May 26 '16 at 04:59 PM in Using UE4

avatar image

Answers.Archive STAFF
1.9k 202 311 683

(comments are locked)
10|2000 characters needed characters left
Viewable by all users

The question has been closed May 26 '16 at 05:00 PM by AndrewHurley for the following reason:

The question is answered, right answer was accepted


1 answer: sort voted first

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 :) 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 :)

Cheers,

--mieszko

more ▼

answered May 26 '16 at 05:00 PM

avatar image

Answers.Archive STAFF
1.9k 202 311 683

avatar image Answers.Archive STAFF May 26 '16 at 05:00 PM

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.

avatar image Answers.Archive STAFF May 26 '16 at 05:00 PM

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.

avatar image Answers.Archive STAFF May 26 '16 at 05:00 PM

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.

avatar image Answers.Archive STAFF May 26 '16 at 05:00 PM

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 :D )

avatar image Answers.Archive STAFF May 26 '16 at 05:00 PM +

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

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

(comments are locked)
10|2000 characters needed characters left
Viewable by all users

Follow this question

Once you sign in you will be able to subscribe for any updates here

Answers to this question