Modifiers and Combining Modifiers


#1

Hi there,

I noticed that in RichAI there is a TraverseFunnel functin. This function seems to walk a funnel, but I thought that the intended effect was that you would add modifiers to the Seeker and it would calculate the path.

My units are being caught on some geometry, and they continuously repath back and forth never escaping it. With my debugging, it looks like the funneled path runs into walls, forcing them to bounce off.

Why does the funnel modifier not take radius into account?

Thanks!


#2

Hi

Well, it works that way for AIPath and AILerp. However the RichAI script has its own internal funnel modifier which it runs every frame. Hence it will ignore the modifiers attached to the GameObject because it only uses the list of nodes from the path, not the list of points that most modifiers update.

The navmesh should already have been shrunk to take the agent’s radius into account. This is controlled by the ‘Character Radius’ field in the recast graph settings.


#3

That’s interesting! I was using a version of the RichAI, but it was giving unexpected results. In fact, most AI I have tried to used have done unexpected things. I have wondered about the costing algorithm you use. In previous implementations I have done, some issues I ran into were costing the path from the midpoint of the triangle’s lines rather than after string pulling.

I’m not currently looking at the code right now, but does AStar cost after modifiers or before?


#4

I’m not sure what you mean by ‘does A* cost after modifier or before’? Care to elaborate?

The RichAI script has it’s own internal funnel (string pulling) algorithm, but the other movement scripts require the funnel modifier to be attached.


#5

Apologies, I refer to your library as AStar. Let me clarify. The library seems to find suboptimal paths. In my debugging I have found that it seems that you cost the paths based on the mid point of the triangle edges rather than on the post optimized path.

Is that the case?


#6

Can I get an update here?

I’m running into lots of issues with nonmultithreading and path construction.

Specifically, is GetConnectionSpecialCost the only spot we run with costMagnitude? I’m seeing paths that make very little sense, and it appears to be down to how we cost the path prior to funneling.


#7

Hi

Yes, this package uses the regular A* pathfinding algorithm and does distance calculations based on the node centers. There is a more accurate algorithm called Theta*, but unfortunately this package does not implement that (I do want to, but it’s veeery hard to do while maintaining compatibility and there is also a lot of code to convert). This page discusses how you can reduce the effect of this: https://arongranberg.com/astar/docs/getstarted2.html#navmeshnotes.


#8

Barring my rewriting your AStar implementation into Theta*, is it not feasible, given short enough pathing distances, to perform an entire path query, including postprocess modifiers, and compare the path length then?

It is definitely because we use the center of the triangle node rather than the closest point on the edge according to the radius of the unit in question.


#9

Can I ask why the recast mesh doesn’t attempt a delaunay triangulation?


#10

Well, technically you could run the funnel modifier after every node the search visits. This will have a very very high overhead in terms of performance… but it is possible.

Mostly because that is a bit complicated to do while also supporting overlapping regions (e.g a spiral staircase). If you use navmesh cutting it will try to flip some edges to make it more delaunay-like though as navmesh cutting can make the triangulation very suboptimal in some cases otherwise. Currently this is not done on the output from recast though.


#11

I see.

My concern is that I was hoping to achieve path parity with Unity’s output, and they use recast. Once I got that, I was going to begin adding features.

I guess I’ll keep working. I’ll have more questions I’m sure. Thanks for your time.