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"

AnswerHub Maintenance

Background maintenance is scheduled to occur between 9 - 11am EDT on Tuesday, May 21. Site operation may be slower than normal during this time and a brief interruption in operation may be observed

Path cost jumps on polygon boundaries

On seeing some more unexpected pathfinding results, I've done some more in depth testing and found that the path cost calculations are generating wildly differing values when the start/end is moved across nav polygon (not tile) boundaries.

alt text

In the image above, the testing actor gives a path cost of 90 and pathfinding steps of 0. When moving one or both endpoints a tiny distance onto the next polygon, the pathfinding steps will jump up to 2 or 3, and with each jump, the path cost also jumps up, by around a further 90 each time. Note that the drawn path remains a simple, straight line.

I don't know the code, but my assumption is that pathfinding steps is a measure of the searching algorithm and shouldn't have any direct bearing on the actual cost in a gameplay sense, yet it appears that it does. So I'm guessing there's a bug in there somewhere.

Note that this is not merely limited to the output results of the navigation testing actor. It is leading to incorrect pathing in practice. In the below image, nav polygon edges are aligned with the camera direction, so the direct path crosses a couple of them, which is bumping up the calculated cost enough that the cost of going via my custom links as shown is actually lower. alt text

Product Version: UE 4.15
Tags:
pathcost1.png (481.6 kB)
pathcost2.png (590.5 kB)
more ▼

asked Apr 28 '17 at 04:39 AM in Using UE4

avatar image

kamrann
2.1k 83 33 119

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

1 answer: sort voted first

This behavior is a side effect of how Recast is finding paths - the pathing distance is measured between centers of portal edges (edges shared by two polygons). Path string-pulling is done as a post-processing step (and is optional). The behavior you observe depends heavily on navmesh's triangulation, so you can try different triangulation methods and see if it helps. Also, playing around with area costs usually helps a lot here .

Cheers,

--mieszko

more ▼

answered Jul 20 '17 at 09:42 AM

avatar image

MieszkoZ STAFF
7.3k 223 57 412

avatar image kamrann Jul 20 '17 at 09:37 PM

Hey Mieszko, thanks for the info.

So I've looked at the code and I think I see what you mean. String pulling seems to be on by default, and it makes sense since if it wasn't done at all then pathing routes would surely look strange. But I wonder in that case why cost calculation is done before string pulling, rather than afterwards in order to get more accurate costs?

Changing to the ChunkyMonotone partitioning allows me to reduce polygon size and so lessen the effect, but it seems very inefficient to create lots more polygons just for this purpose. Am I missing a better solution? My environments will generally be very flat and mostly have a single area cost - I don't quite understand in what way you mean playing with area cost could help?

Cheers.

avatar image MieszkoZ STAFF Jul 24 '17 at 11:24 AM

But I wonder in that case why cost calculation is done before string pulling, rather than afterwards in order to get more accurate costs?

It's not this way for two reasons: simplicity and efficiency. And it's usually good enough. If this is a huge problem for your game I'd suggest implementing your own pathfinding - you can do it by extending ReacatNavMesh and supplying custom FindPath-family functions.

My environments will generally be very flat and mostly have a single area cost - I don't quite understand in what way you mean playing with area cost could help?

If you're using mostly 'default' cost then changing costs won't help you much.

In summary, this is a project-specific issue because a solution depends heavily on how your levels look, how you generate navmesh, etc. You'll have to find the best way by trying different things. If you share a lot more details about your navigation requirements and setup I might be able to suggest some things.

avatar image kamrann Jul 24 '17 at 09:24 PM

Thanks Mieszko, that makes sense. I've played around some more and I can see that the problems are indeed mostly caused by the flat and simple nature of the levels. Even with ChunkyMonotone and high subdivision, there are still issues depending on what corridor is chosen on the largely regular grid of polygons.

My project will have small maps and won't be performance intensive. As such, my gut feeling is the way to avoid unnecessarily angled paths would be to stick to default partitioning to minimize the number of polygons, but then change the pathfinding implementation as you mention. I'd think with a small nav mesh, it would be feasible to do a more exhaustive search to try to find (when it exists) the precise corridor that contains the straight line between two given points. I don't know enough about how A* works to say for sure, but I think I'll leave it for now and tackle that further down the line.

(comments are locked)
10|2000 characters needed characters left
Viewable by all users
Your answer
toggle preview:

Up to 5 attachments (including images) can be used with a maximum of 5.2 MB each and 5.2 MB total.

Follow this question

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

Answers to this question