AI pathfinding methods

I’m trying to figure out what to do about my AI pathfinding.

My game will have very large numbers of enemies and I want to make sure to use a method that is fast and allows for physics.

Navmesh works well enough, especially if I limit the path update, but navmesh agents just don’t take well to physics. I suppose I can swap between a navigation and a physics state, but it seems to be a can of worms of bugs.

A* is simple enough, and I figure I can do it with raycasts. But I’m wondering if that would be too many rays.

I’m also interested in node based AI like old school unreal tournament used to do, but I can’t seem to find much on how that worked. Any links is appreciated.

Any suggestions?

 

How does physics come into play? Is it what Puppet Master allows, meaning characters can stumble and fall over, then recover? Or could the entire world shift around, or wind forces, or large explosions?

Games that I've seen that apply physics to crowds of characters seem to put them in a physics-controlled state temporarily. Perhaps such a game doesn't actually use pathfinding but rather directed movement with either flocking (swarm) behaviour or local avoidance so that characters stay a distance from each other. But that wouldn't allow them to navigate narrow spaces let alone mazes like A* would allow them to do.

Another combo is: physics force, then recover and directed walk towards last known walkable path, then continue pathfinding (or spline follow). I think Planet Coaster visitors behave like this when they're forced off the path or the path is removed under them. Let's Game It Out has a couple videos showcasing exactly this (among other things).

 

Well, it’s an open fps, so I don’t need them to return to a path.

im glad to hear that’s what others have done because that was my initial thoughts on a solution (temporary physics).

im needing to knock them back with shots and explosions, and I need them to be grabbable with a gravity gun.

 

Sounds like you really need Puppet Master.

 

I’m always hesitant to buy a package because I have a hard time just trusting others code and often feel like it’s more effort to navigate someone else’s solution than to just make my own.

I went down that path with UFPS.

It was completely unmanageable for me. I know lots of people use it with great success, but for me it was just easier making my own controller that I know and understand thoroughly.

I’m worried that might be the same case.

EDIT: Also, this IS a hobby for me. Making my own AI is part of the fun.

 

Probably less likely to happen with Puppet Master. After all it's mainly something you need to set up and tweak to make it look cool and do the right thing rather than having to live with how a core aspect of the game (character controller) handles things and may be limiting and the code is somewhat offputting and all that. I know I had great fun toying with Puppet Master and it opens up a lot of possibilities.

 

You can use boids for basic obstacle avoidance behavior and you can combine it with navmesh or any other algorithm. Boids is not pathfinding, it is flocking/avoidance behavior.

Basically, for every agent you compute where it wants to go, and where it wants to move away from, then you sum them together and use that to decide final movement vector. When you combine it with other pathfinding algorithm, the other pathfinding algorithm is just another "where it wants to go" vector.

Regarding physics, if you have crowds, then the crowd cannot be ragdoll.

Blade and Sorcery used fully physical puppets, and they quickly learned to turn off physics for any NPC the player is not interacting with. Because it is costly.

You can cheat there a little. There's "Hitman Ragdoll" method, where character is not represented with rigidbodies and joints, but rather as a system of balls connected with springs.

Spoiler

http://liu.diva-portal.org/smash/get/diva2:23898/FULLTEXT01.pdf

Those are less computationally expensive, but such characters will fall through each other, and will only interact with the world. What's more, unity does not implement anything like that, so you'd need to code it.

Regarding blade of Sorcery, there characters are controlled like puppets. Meaning you have a ragdoll, and you have puppet-provided invisible kinematic positions for head, hands, feet, etc, and the ragdoll is connected to the kinematic positions with a springy/stretch joint constraint.

See here for similar approach:
https://forum.unity.com/threads/vr-physical-interaction-test.1212024/

 

For rigidbody herd/crowd nav I used a waypoint system with a Waypoint component that had a List of the next accessible waypoints and a circumference of arrival, either a distance or collider trigger to indicate whether the rigidbody had reached the area of that waypoint whether I wanted it tight and specific or just a general area of l*w or a radius. I would then just push the rigidbodies with AddForce with the vector towards the next waypoint and avoiding other rigidbodies around it while maintaining the primary goal of reaching the waypoint. By moving the waypoints around ands watching the sim I got pretty reasonable african animal herd behaviour, as well as fish school and bird flock behaviours including species clustering.

 

I would probably not use rag dolls, but if I were to, I would just put a limit on how many rag dolls there were at a time.

 

For large groups who are going to the same place a flow field might be the way to go. They're an efficient way to do mass pathing as long as you have a small number of destinations. If you're then messing with physics then when you update the field accordingly everything which uses it will "automatically" react.

Updating the field both optimally and correctly is probably quite tricky, but it probably also isn't necessary. Update stuff near the player a lot, have a time budget for updating stuff further away based on priority, and use simple rules for updates around physics changes and the like (e.g. if an obstacle appears, point all cells it overlaps away from it, and request increased priority for a proper update of the area).

This could occasionally lead to cases where agents visibly make mistakes, but that's something which really happens when people are getting around.

 

You know that you can use a NavNeshAgent to only find a path and then use whatever method you want to move the character? In your case, probably AddForce or something physics-based. I've done this before and previously posted example code here:

https://forum.unity.com/threads/player-jump-not-allowed-on-navmeshagent.718364/#post-4799339

Edit: notice I set _Agent.updatePosition = false and _Agent.updateRotation = false in Start(). That's how you can bypass the NavMeshAgent's automatic movement.

 

As to performance of a crowd of ragdolls, DOTS and specifically Havok physics (for DOTS) are game-changers for such features.

Most commonly the performance of such a crowd drops due to the inter-person collisions. Depending on what you need these ragdolls for you could make the ragdoll non-collidable and have each person a simple capsule collider for inter-person collisions. Or use Havok as it tends to be a LOT faster for a high number of collisions per frame.

 

If you do a unit of characters or a swarm I'd just have 1 guidance object doing navigation/pathfinding and the crowd just tries to stay in their formation position relative to the main object.

That guiding object could just use navmesh, waypoints, a*, and your AI characters follow with their offset, and have physics..... similar to boids but more uniform formation.

Doesn't even have to be swarms, each AI could have a guiding object that pathfinds and they try to follow it.

 

It’s funny, i was just reading an article on flow fields by catlike coding.

https://catlikecoding.com/unity/tutorials/tower-defense/the-board/

 

Thats not really a proper flow field just to be clear And nowhere does Jasper (catlike coding) claim that it I dont think. This link is basically just tile based pathfinding using a breadth first search for the most part.

Theres some similarities but its waaaay more rudimentary than a proper flow field implementation - the linked article by @angrypenguin is a bit better but to be honest that also isnt a full implementation.

The really difficult part is actually updating the flow field in realtime without destroying performance, the actual initial generating it part is a very simple algorithm. So far none of the links in the thread show that part (I am also looking into flow fields for a project right now so Ill come back and post anything I find thats useful )

 

Eizenhorn discusses flowfield approach in his team Diplomacy is not an option game. He links to papers with gates concepts between chunks. And about caching flowields, over duration of the game.

You would need to search his thread. He also discusses this on one of his YT vids, in the chat discussion.

Bear in mind, this game uses DOTS.
However, principles of gated flowfield is applicable in any solution.

 

Not even close. I only meant for it to clarify the concept. I suspect that a "full implementation" would need a bunch of game-specific logic.