Add node size constant for initializing NavMeshQuery objects

[NickTaSpy]

I decided to use these libraries for a project. I have a big city which means my nav surface is quite complex (it's flat but there are many buildings).

The end goal is to be able to spawn at least a few thounsand entities that can travel around the city. I noticed that when I spawn a few hundred entities (using your spawning library), then as soon as I start adding NavNeedsDestination components it, understandably, takes a long time to calculate the paths.

The paths I am going to need are going to be static so if I was able to save the paths for later use like in NavMesh.CalculatePath that would be great. Are there any other tricks I could try? Would it be better to use Unity's non-DOTS NavMesh API for my case? Or maybe I am just doing something wrong 😅

I am using: nav/v0.10.0

This is how my city looks like:

Thank you in advance!

[reeseschultz]

The NavPerformanceDemo can spawn tens of thousands of agents without any noticeable lag at all, and that's just in the editor—building it affords much more power. Your city is complex, but I wouldn't anticipate a noticeable performance issue because of that. Not sure what's going on, so let's try some things:

1. One issue I can tell you right off the bat is that you're using a 2019 editor version. nav/v0.10.1 depends on 2020.1.0b12. Switching to that will drastically improve performance for the RenderMeshSystemV2, which is part of the Hybrid Renderer package. If that package is used with a 2019 editor version, it can result in undefined behavior. (Don't feel bad, I had no idea about this for months and have been using the wrong editor version until the other day.)

2. Another thought that comes to mind is that you may have to manually adjust something in NavConstants, such as the ITERATION_MAX, PATH_NODE_MAX, and/or PATH_SEARCH_MAX. They may need increasing, I'm thinking. For example, PATH_SEARCH_MAX defaults to 1000, but it looks like your surface is 1900×1900. That could be a problem if you didn't change it, possibly the problem, resulting in agents that appear to be processing, but don't ever seem to get around to complete it. My docs describe that particular constant as the "upper limit on the search area size during path planning."

3. If the above two points don't help, then I need more information to help, and I'm happy to do so. Getting a look at your Entity Debugger (maybe a screenshot or two) when you're experiencing this issue would be very useful to me. Even more useful would be either access to this project's files, the Git repository, or a reproduction of sorts.

Please let me know if any of that helps.

[NickTaSpy]

I tried your step 1 and I definitely got a significant performance boost. However, my current test scenario is kind of unrealistic and unfair because I spawn 500 entities that calculate paths all the time. I'll comment another time with a better scenario because I am low on time at the moment. Here are my results so far:

Unity: https://youtu.be/GU7zInIfAP8

Profiler data: https://www.mediafire.com/file/pm8gw1kky4wnha4/profiler.zip/file

[reeseschultz]

Okay, I see what you mean. Based on the video, it looks like you're trying to calculate 500 paths at approximately the same time, which will surely exceed the thread limit on average hardware, explaining the slowdown. The difference between the NavPerformanceDemo and your scene is that the demo keeps the agents busy by interpolating across long paths. So basically only an inkling of them need a new path at any given time, assuming they all wander indefinitely.

Your map is gigantic, but you're testing the nav package by using a small fraction of it and setting the same destination on the agents. I agree that your test scenario is "unrealistic" based on what I'm assuming your end-goal intentions appear to be. With the current state of the nav package, thousands of agents can traverse a large map as long as you keep the majority of them busy with movement and possibly other actions.

What I think you should do, but I could be wrong. I get the impression the test scenario doesn't really cover what you're wanting to accomplish, so you could try using longer and more varied paths in your city instead of what I'm seeing in that video. But again, I could see path saving being a feature somebody, maybe you, would want given that everything is static.

A solution for the nav package. The path at any given time is stored as a DynamicBuffer. I could look into allowing users to assign the DynamicBuffer themselves with some helpful utility code. This approach would skip the path planning processing. But in that case, NavMesh.CalculatePath would have to be called elsewhere.

A better solution. Even better, though, I could hash paths for quick lookup, then, entirely in the nav package without user intervention, reuse paths. That may require some rounding and/or intentional loss of floating-point precision. I'm lazy so I would probably use a ConcurrentDictionary much like how I've hacked one into the NavSurfaceSystem, but it's managed code so it can't benefit from Burst compilation. Not ideal but not a huge deal either, it'd still be multi-threaded.

Workaround. I'm short on time as well, and I need to think about this more. If your test scenario is representative of your goal, then, yes, using the good-old NavMesh API may be more suitable in the interim.

And by the way, thanks for bringing this up. It's an illuminating case I hadn't considered.

[NickTaSpy]

Sorry for not replying here for so long. The project I am working on is for a university assignment and I'll be done with it by July 1st. I'll post feedback by then. I'll most likely upload it on github too.

[reeseschultz]

Sounds good. Just be sure to check with your professor or advisor on the plagiarism policy. Many professors I've had were against letting me upload assignments publicly even after I completed them, since other students could then find them and use them. Seemed completely ridiculous that I would be culpable for somebody else using my work in a future assignment, but apparently that's somehow an acceptable and widespread norm. Just letting you know.

[NickTaSpy]

I remember my professor told me I could optionally upload my source with the assignment's document. Everyone has their own unique assignment because it's for the diploma so I doubt this applies to my case. Thanks for the tip nonetheless!

[NickTaSpy]

I am facing a problem with NavMeshQuery. Some of my agents are permanently stuck with NavPlanning because of this line:

https://github.com/reeseschultz/ReeseUnityDemos/blob/c5b8898908847497690edc5f5f320330f379180e/Packages/com.reese.nav/Agent/NavPlanSystem.cs#L77

Basically the status is OutOfNodes and the NavPlanning component is not removed so this slows everything down. I added: commandBuffer.RemoveComponent<NavPlanning>(entityInQueryIndex, entity); as a temporary solution so I don't get 5 fps.

I tried increasing PATH_NODE_MAX to like 1500 but I get the error: Entity archetype component data is too large. Previous archetype size per instance {archetype->InstanceSizeWithOverhead} bytes. Attempting to add component size {componentInstanceSize} bytes. Maximum chunk size {chunkDataSize}

I am not sure if this is easily fixable. I haven't tried to fix this for real yet because I am still a noob at DOTS. As a workaround I make sure the distance between the start and end points is not over like 200m.

[reeseschultz]

It looks like the logic in the NavPlanSystem can be improved to passthrough OutOfNodes and potentially Failure as component tags added to a given agent. That way users such as yourself can handle that situation more cleanly.

Furthermore, I think I may be able to suggest something else that could help, but I need to explain it. The PATH_NODE_MAX is just used to preallocate the capacity of a dynamic buffer for each entity (which you can think of as an array of float3s). Here's what I'm doing:

[InternalBufferCapacity(NavConstants.PATH_NODE_MAX)]
public struct NavPathBufferElement : IBufferElementData
{
    public static implicit operator float3(NavPathBufferElement e) { return e.Value; }
    public static implicit operator NavPathBufferElement(float3 e) { return new NavPathBufferElement { Value = e }; }

    /// <summary>A waypoint along the path calculated by the NavPlanSystem.
    /// </summary>
    public float3 Value;
}

Note InternalBufferCapacity. While it seems you ran into a limitation of the Entities API, I actually have reason to believe it's not a big deal. If the PATH_NODE_MAX is exceeded, heap memory will be allocated on the spot, according to the dynamic buffer docs. Access is not as fast when addresses are noncontiguously strewn about, but it still works. In other words, just use a reasonable value for that constant.

With all that said, here's what I think you should do if you haven't already: please try increasing the PATH_SEARCH_MAX as I mentioned earlier. It deals in the square area surrounding an agent. Here's how:

var status = navMeshQuery.BeginFindPath(
    navMeshQuery.MapLocation(worldPosition, Vector3.one * NavConstants.PATH_SEARCH_MAX, agent.TypeID),
    navMeshQuery.MapLocation(worldDestination, Vector3.one * NavConstants.PATH_SEARCH_MAX, agent.TypeID),
    NavMesh.AllAreas
);

With a big enough search area, I think you should be okay. But if you're still experiencing performance issues, let me know.

[NickTaSpy]

I've already tried that. It looks like I get the same issue even with PATH_SEARCH_MAX = int.MaxValue. I check if the paths are reachable with NavMesh.CalculatePath() before spawning entities so I doubt there's a problem with that unless it's not the same... I can upload the project if necessary but you may have to register at Mapbox for it to work.

[reeseschultz]

Yeah, I'd like to take a look at the project to see what's going on.

[NickTaSpy]

Here's my project: https://github.com/NickTaSpy/EpidemicSimulator

I believe you have to register at Mapbox so you can create a token which you then need to put in Mapbox > Setup > Access Token.

The "main" file is MapManager.cs. Some parts of the project are messy because I was testing stuff. I will post later when I have more time to explain this further unless you can figure it out. I understand if you don't wanna go through the trouble by the way 😅.

[reeseschultz]

It's all good, no need to explain. I'm up and running. I'll get back to you later tonight or tomorrow morning.

[reeseschultz]

Okay, I've confirmed what I believe to be the core problem after poking around your project. Thanks for sharing it, by the way.

In addition to allocating dynamic buffers for paths, PATH_NODE_MAX is also used to initialize each thread-indexed NavMeshQuery that is orchestrated in the NavPlanSystem. You can see that allocation performed in the NavMeshQuerySystem. What I need to do is create a separate constant to set the max nodes for a given NavMeshQuery. Probably NAV_MESH_QUERY_NODE_SIZE or something.

If you're wondering why that would help, it's because the NavMeshQuery cannot allocate more memory dynamically, but it's also not as size-constrained as the dynamic buffer. So basically you're running into a limit that really should not apply, because we're dealing with two separate things. The dynamic buffer constant should be obviously separate from the one used to initialize the NavMeshQuery. That's definitely an oversight on my part.

As a workaround, you can set the following in NavMeshQuerySystem:

var query = new NavMeshQuery(
    NavMeshWorld.GetDefaultWorld(),
    Allocator.Persistent,
    100000 // <- !!!
);

You can probably find a more reasonable number for pathNodePoolSize. Then you shouldn't be running out of nodes, and your agents should traverse fine.

Stuff I will do soon:

• Create a separate node constant for NavMeshQuery initialization.
• Add documentation on how to avoid OutOfNodes with said constant.
• Add documentation explaining the limitation on the dynamic buffer constant.
• Handle non-success statuses more appropriately (#35).

You may still experience performance issues, I'm not sure. As previously mentioned, I know that randomizing differently-sized paths for the agents should keep the path planning down to a small proportion at any given time. Beyond that, if there are still performance issues, then there's a good chance you'd want to look into hierarchical planning. Let me know what you think.

[NickTaSpy]

My problem seems to be fixed. Thanks for your help! As for the performance issues I doubt I'll have any problem. There are a couple of simple ways to improve it like the ones you mentioned. It's already going well anyway.

I'll keep working on my project for a few months because I postponed my assignment to September. Your demo projects are simple so if my project can benefit yours in any way feel free to use it.

[reeseschultz]

Excellent, you're welcome. If you experience more problems or have any ideas, please open more issues. I'll close this issue after I make some changes.