AstarPath.Update() / TileHandler.CutPoly() Frame Time Spikes

General
#4

I was just about to update my post when you replied:
I’m using 1 recast graph where I periodically update Navmesh Cut scripts, I also then update Graph Update Objects (but the performance cost to that seems insignificant compared to the Navmesh Cut scripts).

The reason I’m trying this is because I read a few posts where you seemed…‘displeased’? with the idea of using multiple graphs in a scene. So I figured that I could try using 1 graph, then having Navmesh Cut scripts act as ‘buffers’ around static terrain. So a small agent would use ‘small buffers’ and large agents would use ‘large buffers’ and so on.

#5

I’m sorry, I mean Graph Update Scene (still having edit issues with the forum).

#6

Hi

If you have agents with different sizes, then multiple graphs is definitely a better way to do it.
What are you doing now? Enabling/disabling all navmesh cut scripts in the scene every time you request a path (or do you have some other clever way of using the buffers without updating the graph every time)?

#7

“do you have some other clever way of using the buffers without updating the graph every time?”
-(answers this question while being very embarrassed) No…I wish I did though, for now I’m not competent enough to do anything clever…Here is basically how things are setup:

-> Agent decides they need a path somewhere, registers with a pathfinding job queue (prevent multiple simultaneous updates from overwriting each other). When its turn comes up:
-Go through and update (initially the default way using TilerHandlerHelper, later on my own modified ForceUpdate() method) NavmeshCut scripts (the ‘buffers’) corresponding to the size bracket of the agent (in my cast small/medium/large). Not ideal because not all agent in one size bracket are actually the same size, but otherwise I would need way too many sets of ‘buffer objects’ due to the amount of static objects.
-Go through and update other agents, this is done second because otherwise they will get overridden by the other ‘buffer objects’. It is also more precisely based off each agent’s size and speed, a ‘desired buff’ is calculated, the NavmeshCut object’s size is adjusted (as is its corresponding GraphUpdateScene script for later use). Then it is updated like the first set.
-Now update the GraphUpdateScene scripts for the static objects using the Apply() method.
-Now update the GraphUpdateScene scripts for the agents after applying the new scale.
-Calculate the path with StartPath().
-Once we get the new path start the cleanup: reset agent GraphUpdateScene scripts, reset static object GraphUpdateScene scripts, reset the agent’s NavmeshCut scripts, reset the static object NavmeshCut scripts. Obviously it isn’t ideal to essentailly have to go through the cost of applying an update, then do it again for un-applying it, but I’ve seen that without doing that, sooner than later you will get ‘too many perturbations’ and other cutting errors that crash the game.
-> Remove job from queue, cleanup, look for more jobs, repeat.

I did consider breaking zones into ‘sections’ (so you could imaging the NPC is in Section 1, the Player in section 3, with Section 2 in between), the NPC could know where which section it is in, then only update the scripts in that section (though it would pathfind the whole way), when it gets to Section 2, it would repeat the process (pathfind to destination, but only deal with resetting section 1 and updating section 2). Not exactly clever, but in theory it would reduce the work from ‘6 areas’ (1 big map instead of 3 sections doing 1 update and 1 reset down to ‘2 areas’ with 1 update and 1 rest or possibly just 1.

There is also the option of ‘advanced steering behaviors’, but I couldn’t thing of anything particularly great that didn’t have some horrible flaw(s) that came along with it.

As an aside, have you heard any interesting ways of accomplishing that (using ‘buffers’ / Cutting objects without updating the graph)? And I’m curious, when you update a NavmeshCut script you only change the local area correct, not the whole graph? So updating less of them would be better? I’m wondering does only the amount ‘vertices in the area’ mean anything or is the amount of scripts also meaningful (ex. 1 script cutting 10 nodes vs 2 scripts cutting 5, if both involved the same number of areas/triangles/vertices)?

#8

Hi

Ok, I think you should consider using multiple different graphs instead. That will probably give you better results.
Note however that currently the TileHandlerHelper will only pick up the first recast graph in the scene, however there is a method on it which you can use to specify another graph to update.

I have actually been trying to write a funnel modifier which can also apply a desired offset from the wall. It works… but it is really tricky because of all the floating point math and there are some edge cases where it fails, so I have not released it.
Have you tried using the RadiusModifier, it isn’t perfect, but maybe it can be of some help at least.

Well, you could technically do some interesting stuff with tags, but it is probably better to just use multiple graphs.

Yes, the NavmeshCut script will only update the tiles it touches (though all nodes will have their Area field recalculated, but that is comparatively fast). The cost is roughly proportional to the number of nodes in the tile and the number of those nodes that are actually touching the cut. When a tile is updated all navmesh cuts that touch it are included in the calculation, so if two navmesh cuts are in the same tile and you tell the system to first update one of them, and then the other, that will essentially just double the work done.

1 Like
#9

“Have you tried using the RadiusModifier”
-No, I’ll look into it.

“you tell the system to first update one of them, and then the other, that will essentially just double the work done.”
-Well, that would explain the overall time increase per cut problem with my modified ForceUpdate() would it not? That said, is there any reason that jumps out at you as to why when I update all the cuts in one batch (the normal way), instead of getting long ‘cutting times’ I instead seem to get long ‘node update times’? At least I think that was what you were pointing out in my 2 screen shots of the profiler.

#10

Not sure if that is the case. There is a bunch of stuff going on in that profiler window and I am only seeing a single frame.

#11

Fair enough.

-I’m working through the multiple grid idea, got some very basic test code to make sure I’m getting all the graphs and applying updates to the correct one (hopefully I’m doing this correctly):

`

foreach (RecastGraph rc in AstarData.active.astarData.FindGraphsOfType(typeof(RecastGraph)))
    {
        TileHandler th = new TileHandler(rc);
        th.CreateTileTypesFromGraph();

        handlers.Add(th);
    }

    Debug.Log("handlers count is: " + handlers.Count);

    for (int counter = 0; counter < handlers.Count; counter++)
    {
        if (handlers[counter].graph.graphIndex == 0)
        {
            tileHandlerHelper.UseSpecifiedHandler(handlers[counter]);
        }
    }`

Just wondering if what you were alluding to with Tags (instead of Cutting) was something like:

-Use multiple Seeker scripts with each one corresponding to a agent type / size (so Small Seeker, Medium Seeker, Large Seeker).

-Each type has its own node penalty list (so Small would accept everything except un-walkable areas / Medium would enforce penalties in Small area nodes, but accept medium and large node areas, and Large would enforce penalties on both Small and Medium nodes).

So in this way, you don’t really change anything, you just evaluate each node differently based on its type. The only changes would be the agents themselves during their cutting / node updates.

Off the top of your head, do you see one approach as clearly ‘better’ than the other?

#12

@aron_granberg

Did some work on this possible new setup, tried following the general outline here (NavMesh cutting during bake) for in-editor cutting, never had any success trying to get the navmesh to update. But, while I was working on that I realized that for multiple graphs, I would also then need to re-work the system a bit to allow GraphUpdateScene scripts to update a specific graph. I think I’ve got a way to do it, but at this point, if the ‘multiple seekers with different penalties’ idea is just as good performance wise, that may be the more simple way to go in the end (no re-writing Astar scripts, no multiple graphs). Any thoughts?

#13

Yes, something very similar to that.

However you would need navmesh cuts to be able to create nodes around the objects in a good way (using the isDual field on the NavmeshCut and a GraphUpdateScene object). However I am not sure if you would be able to have more than 2 different sizes (due to how isDual works).

I think multiple graphs is generally to be preferred since it avoids the complexity and extra work of having to configure multiple navmesh cuts and penalties.

Yeah, the GraphUpdateScene component does not expose a graph mask. If you use a GraphUpdateObject instead (which is what GraphUpdateScene does behind the scenes) you can set the nnConstraint.graphMask field to the graphs that you want to update. Or you can modify the GraphUpdateScene component to expose this field.

#14

@aron_granberg Thank you for all the help so far, unfortunately causing problems seems to be the only thing I’ve become good at so far…

The Issue I Ran Into:
-Regardless of using one or multiple graphs, it occurred to me that when my agents cut, the original tag information on the nodes is destroyed, and in order to fix that I then have to re-enable the GraphUpdateScene scripts (which was causing the whole performance issue in the first place…).

My Possible Work-Around:
I thought that instead of ‘re-setting’ the node data, I could just re-load the original pre-made graph which I create during runtime then save to file using your “Save to File” UI button. It seemed quite fast and avoided the problems.

But That Raised Another Problem:
-So far, when using DeserializeGraphs(someFile.bytes) either through code or the UI button, the ‘load’ seems to be fine (the node areas and tag values show up as expected). But when trying to use NavmeshCut to cut something (when TileHandlerHelper is updated), I get a:

  • “Graph Doesn’t Exist” error [ Pathfinding.AstarData:GetGraphIndex(NavGraph) (at Assets/zThirdParty/AstarPathfindingProject/Core/AstarData.cs:705) ]
    As well as a:
    -“IndexOutOfRangeException: Array index is out of range.” error [ Pathfinding.TriangleMeshNode.GetNavmeshHolder (UInt32 graphIndex) (at Assets/zThirdParty/AstarPathfindingProject/Generators/NodeClasses/TriangleMeshNode.cs:29) ]

Any idea on a direction to point me to in order to fix this? I’m looking around for the chain of events I would need to modify, but haven’t found anything yet.

As a side note, do you even think this is a good idea? Maybe there is a way to ‘catalog’ each node changed and its original tag, and after I’m done cutting to re-set the nodes using that data.

#15

Hi

Well… I have been recommending another solution in the last few posts.

I thought you wouldn’t cut the navmesh more than at the beginning of the game now? Why do you need to cut it again?
Yes, tag information will be lost, and unfortunately it is pretty hard to recover that because sometimes triangles with different tags can be merged and then there is no well defined tag for that triangle. The only case where all tags would definitely be defined where if the tags were set before any cutting was done.

Do you happen to have a longer stacktrace for that?

#16

@aron_granberg Hopefully this will explain what is going on as per your questions:

“Well… I have been recommending another solution in the last few posts.”

-It isn’t that I’ve ignored them (I think these quotes summarize them):

“I think you should consider using multiple different graphs instead”
“Use multiple Seeker scripts with each one corresponding to a agent type / size (so Small Seeker, Medium Seeker, Large Seeker).? RE: Yes, something very similar to that.”

-In the grand scheme of things, the two problems I was having was cutting large sections of the navmesh and then updating large sections of the navmesh node tag data. Using your multiple graph suggestion (or my modified single graph) does eliminate pretty much all the issues with the cutting of the mesh (only the agents would need to cut anything), so that is good.

-However, neither approach addresses the problem of nodes losing their tag data when re-cut (which again requires the updating of large areas of the navmesh). That key fact is a large oversight on my part, really should have remembered that earlier.

-That being the case, my method of changing how the initial cutting is done and using only 1 graph just simplifies the setup and operation.

-So my newest thought was to just ‘re-load’ the pre-created navmesh after agent cutting / pathfinding was done. It would re-establish all the node and tag data (and seemed to be quite a fast operation), so it is possibly the best way to accomplish this from a performance standpoint. Unfortunately I can’t seem to do it without errors (more on that at the end of this post).

“I thought you wouldn’t cut the navmesh more than at the beginning of the game now? Why do you need to cut it again?”

-I realize that my setup probably is very strange to someone that isn’t looking directly at it, so, I’ve tried to prepare a image that will give you a much better idea about what is actually happening:

So here, I have created ‘areas’ that define ideal places for agents of different size to operate (basically by defining 2 ‘outer areas’ that use cutting and then 1 ‘middle area’ that functions as a ‘buffer’ to keep cutting scripts from merging areas that share an edge. All areas then have their tag data changed to reflect the type of area they are.

In this example, a blockage has occurred (agents cut an area around them to invalidate the area under them and around them), and because of this all the agents must take path around it instead of just using ‘large area’ to go straight to it.

So each unit follows its own logic:

Large Agent: allowed to use Medium areas if absolutely necessary (determined by script) to reach the destination (‘medium areas’ carry a high penalty, and ‘small area’ is not allowed at all).

Medium Agent: also uses ‘medium area’ (carries no penalty at all, nor does ‘large area’).

Small Agent: uses ‘small area’ (no penalties for any type of area node) but using ‘small area’ results in the shortest path in this case.

This could of course be changed to allow more risky / more conservative pathing, as well as even forcing all units to use larger areas (giving a slight penalty to other types that would still be okay to use) for more safety.

However, once the blockage clears, the nodes will have lost their data (having gone from: original ‘area tag’ -> ‘invalid tag’ -> nothing. This still requires updating of node data (1 of the 2 original problems). Hence my attempt to re-load the original data.

“Do you happen to have a longer stacktrace for that?”

-Here are two images of the errors, “IndexOutOfRangeException” occurs 1 time per occurrence, “GraphDoesn’tExist” happens more than 1 time (and the amount is variable).

“The only case where all tags would definitely be defined where if the tags were set before any cutting was done.”

-Well, I do have a ‘pre-created’ navmesh with tag info before the agents try to do any cutting. So it would in theory be possible to know which nodes you are about to cut over, save their tag data, then after cutting / pathfinding when the navmeshcut script is turned off and the navmesh ‘goes back to its original state’, the data for those nodes could then be re-applied?

#17

Have an update on the error after more testing:

After making a simple scene, trying to load, and still having the same problems I have found a fix that appears to work (though it could have unintended consequences, I don’t know):
-Calling “AstarData.active.astarData.UpdateShortcuts();” after the load.
-Updating the “_graph” variable in the TileHandler object after UpdateShortcuts().
-If needed, calling CreateTileTypesFromGraph() if the new ‘clean’ graph has different geometry than the old ‘clean’ graph.

Seems to work so far, I will try to apply it back to the more complex project and see what happens. Have not tried doing this with nodes containing Tag data.

#18

Another Update:

This does still seem to work in the complex scene, however it is still just too slow…It basically is like going from horrible -> bad (better than nothing I guess), though if you only did this with navmeshes with low node counts it might be ok.

So I’ll give ‘collecting and resetting pre/post cut node data’ a try, see if that fairs any better (seems like a better bet than trying to modify the entire ‘loading process’, which I’m sure was never meant to be used frequently in the first place.

#19

Ok, but what do you need the tags for if you are using multiple graphs?
When using multiple graphs you would not need any tags to signify which units can walk on it.

Also. Are you adding navmesh cuts to agents which use pathfinding as well?
That is usually a bad idea because that makes the agent avoid itself since it is constantly saying that “this part of the navmesh that I am standing on should not be possible to stand on”.

#20

“what do you need the tags for if you are using multiple graphs?”

-The need for multiple tags is used to create ‘more or less favorable areas’. A large unit wouldn’t -want- to walk in medium areas (poor clearance leading to goofy steering, could get stuck, etc) but it would have the option to if there is no better way to get somewhere. Whether I use multiple graphs or not, without tags you end up with all / nothing areas in which all area is treated equally and is evaluated only by distance. Meaning that a large unit would end up trying really ‘dangerous’ paths because that area isn’t evaluated as ‘less favorable’ and is the shorted path to a destination.

"That is usually a bad idea because that makes the agent avoid itself since it is constantly saying that “this part of the navmesh that I am standing on should not be possible to stand on” "

-True, in my case though, the agents are cutting with isDual and the agent doing the pathfinding does not cut at all. So the only issue here is that the cutting is removing node tag data, which I’m still trying to find the best way to ‘restore’ after it has been altered (which usually means it has become un-walkable since an agent is occupying it), the final path calculated, and the cut ‘released’ which restores the default navmesh areas but with no tag data.

#21

Update:

So the idea this time is to:

-Create the ‘final graph setup’ in the editor.

-Capture the node data and assign a ‘baseTag’ (a field I added to the GraphNode class) marking what the node tag should be in a clean state.

-After any change is made to the navmesh through cutting after it is no longer needed and the ‘cutter’ is turned off, the navmesh ‘goes back to its original state’ (as it was before any cutting was done, just with no tag info).

-At this point, I tried to go through all the nodes to determine which ones no longer had their baseTag set properly against a list of the original base tags (using the nodeIndex to determine matches) to see what needs re-setting.

So the hang up I’m having is on how nodeIndex is determined. It looks like:
If you had 100 nodes, and you changed nodes 3 and 4, your index list would be 1,2,5-100, ~101, ~102 (not necessarily that, but with the 2 nodes using new numbers) with index positions never being re-used? So at this point it is a matter of matching up new node

#22

Hi

Just a question. Have you considered using grid graphs? It seems like they would be vastly easier to work with given your requirements.

#23

Have you considered using grid graphs?
-Yes, but unfortunately due to the size of the areas (up to x1.5km) and still needing a relatively high level of accuracy around terrain, the total numbers of grid nodes needed were well in excess of 1 million+. Even on my strong PC generation time was nasty, and eventually porting this to a less strong MAC prior to iOS deployment probably would end up crashing the program if I needed to make any changes.

As far as the navmesh goes, it only takes ~4.5k nodes to accomplish the same / better accuracy for that space. Even if I increased the number of nodes ten times, it still would be a drop in the bucket compared to the grid setup.