Would a custom pathfinding solution solve these problems?

Hello. I've started work on a custom pathfinding solution to assist with advanced behaviors such as flanking. I'd like to make sure I've got the right idea before going much further, so I've created mockup images to illustrate the two main scenarios I have in mind. These mockups portray a grid for simplicity, but I'd be applying this approach to navmeshes.

The first scenario is AI flanking an enemy machine gun nest. From what I can tell, the only way to make this work in the general case is to increase weights for all nodes in line of sight of the machine gun nest. This would have to be done on a per-agent (or per-team) basis so that weights are not affected for agents friendly to the machine gunner, allowing them to move in the open. This appears to be impossible with native pathfinding, because developers can't copy the navmesh data and readjust weights on a per-agent basis.

In my first couple of screenshots, the machine gunner is red, the pathing agent is green, and cover is blue.



The machine gun has a limited firing arc, allowing it to fire only on the orange tiles in the screenshot below. The pathing agent's goal would be the first tile where it has line of sight to the machine gunner but not the other way around (so no orange tiles). The expected path would look something like the green tiles.



The second scenario is flanking by melee enemies. I'm specifically thinking of the castle water room in Resident Evil 4, where enemies flank the player immediately upon entering. My next screenshot is a mockup of this, where the blue tiles are pools of water rather than cover. The player is at the bottom and enemies at the top, each one a different color.



If using only agent avoidance, the enemies would all travel down the middle. The ideal solution is for magenta and orange to choose paths first. When calculating for yellow and cyan, all middle polygons would then be weighted higher in their copies of the navmesh, causing them to path around the pools. The final screenshot shows the resulting paths.



The order of path selection could be problematic, e.g., if yellow selects first it would take magenta's path, forcing magenta to move around yellow to take its path. Another problem is having so many agents that later paths go too far out of the way, although this might be mitigated with fine-tuned weighting and additional constraints, like only considering nodes within a certain distance. Agents could also be explicitly grouped such that group members ignore weights set by others, allowing them to share nodes. A final concern is how unpredictable the size and shape of navmesh polygons can be, but this might be manageable with careful grouping, or if necessary, reverting a more grid-based approach.

Anyway, I just want to make sure these advanced behaviors are not practical with Unity's native pathfinding, and that my approach is a viable alternative. Thanks for any feedback!

 

Yeah, I honestly wouldn't know an elegant way to solve this using only Unity's NavMesh systems and scripting.
I'd definitely go ahead and roll with a custom solution there.
Now I'm actually curious to see how you'd solve these. Mind sharing your ideas and progress here as you go?

 

Thanks, it's reassuring to see some interest! I'm thinking of documenting my solution in a series of blog posts as I progress. Another major goal besides advanced AI is creating something that can be adapted for navigation on tiny planets, Super Mario Galaxy style.

I have to actually start a blog first, something I may not have time for in the next couple of weeks. I'll be sure to reply here when I do, though.

 

You could use Unity's navmesh and might still be able to achieve what you want by using

NavMeshAgent.SetAreaCost

and changing the NavMesh during runtime, e.g. by changing the layer of the navmesh with dynamically generated

NavMeshModifiersVolumes

and updating the NavMesh asynchronously.

Let me know if you have any questions in that regard.

 

First blog post is up! I started a new thread in the WIP forum, where I mostly formalized what I brought up here. The next post will dive into code with a functioning A* demo.

By the way, thanks for the input, DwinTeimlon! I wasn't aware of that functionality, but unfortunately it's not practical for my purposes, since it would be difficult to match the dynamic volumes to things like line of sight.