NavMesh with vehicles - a navmesh agent with a turning radius?

[MD_Reptile]

Hello guys.

TLDR:
What is a solid solution for vehicle pathfinding? AKA pathfinding for agents who have a limited turning radius (possibly considering that they can go in reverse)?

I wrote a replacement to the default NavMesh Agent using agent.Move method and it basically does the same thing as the default NavMesh agent, but instead of rotating and sliding around so much as it follows its path very directly, my custom agent acts more like a wheeled vehicle, only moving forwards and rotating to aim towards the “steeringTarget”, which is the next point/turn in the path. It is similar to what you can see in this tutorial video:

Use Unity3D NavMeshAgent.Move to customize your navigation control

The idea is to have a dummy navmesh agent that can pathfind through a city, and have the dummy followed by a physics driven car. As the physics driven car moves around in pursuit of the navmesh agent dummy, it allows the navmesh agent to move further along its path.

This lets me use dynamic rigidbody vehicles but also pathfind with the built in navmesh unity offers. Great!

But… that is where things get complicated. Sure, now the agent moves in a way more similar to a real car, and the physics car can follow it more easily than if it took hard turns all the time like the regular navmesh agent might do, but it still is hitting some snags.

One drawback to this whole turn rotation limiting on the agent, is that the agent will hit the edges of the navmesh sometimes, and will kind of slide slowly until it rotates enough or slides slowly enough to get back in the open again.

Another drawback is that the actual path is the same as it would be for a regular old navmesh agent, and this doesn’t consider that a vehicle might be travelling too fast or just can’t turn tight enough to make a certain angle of a turn. Even though a vehicle might be able to fit in an alleyway, doesn’t mean the vehicle can come down the street and make a 90 degree turn into the alley - and even if the agent rotates slowly before hitting the wall in that alley, it’ll still get the physical car stuck in the alley (Image below for reference shows a red “actual path” and a yellow “points along the path the agent provides” example):

I’ve tried some other approaches like an all raycasting based avoidance system (not reliable enough and crashes frequently), or a system where the ai driver follows normal road waypoints (not robust enough and the driver can’t go offroad or take shortcuts around traffic very well).

These other approaches just don’t seem to work very well though, and the navmesh approach seems to be pretty promising so far because its possible to go on and off the road without a nutty amount of waypoints all over, and allows for obstacle avoidance to be kind of baked in to some extent with navmesh obstacles carving.

What would you suggest might work to pathfind through the navmesh for a vehicle that has a limited turning radius, unlike a humanoid or other typical navmesh agent character might have? If it means a custom pathfinding algorithm instead of taking a path from a navmesh agent I’d be open to trying that out, but I’m not sure if I’d be able to still use the built in navmesh component and still hack out my own “curve-y A star” or something, or if that is even possible using these tools (to use your own pathfinding algorithm to find a path on the nav mesh).

Obviously this isn’t a trivial problem to solve - but I’d like to hear some advice about what might work for cars pathfinding on a navmesh. I know there isn’t going to be an “out of the box” solution to this, but what sort of things might help push me in the right direction to solve this type of problem? Has anybody ever done something this complex on the navmesh in unity and lived to tell the story? I’ve seen vague references to this “corridor map method” but I can’t find a good implementation anywhere. I’d scrap the idea of a navmesh in favor of a smarter approach if somebody knows one - just working off that because it has had promising results so far, and I think a proper solution that also takes advantage of the navmesh would be really cool.

USEFUL ARTICLES/SITES:

Hardcore pathfinding for self-driving cars

Explaining the Hybrid A Star pathfinding algorithm for selfdriving cars

ftp://ftp.math.ucla.edu/pub/camreport/cam09-74.pdf (A Practical Path-planning Algorithm for a Vehicle with a Constrained Turning Radius: a Hamilton-Jacobi Approach)
Scrapsgame.com: Fighting Games Reviews, Tips, and News

A* in Action - Artificial Intelligence for Robotics

[MD_Reptile]

BUMP - so the best stuff I’ve seen so far is “Reeds-Shepp” related algorithms and stuff that seems to be called “Lattice grid path planner” algorithms.

Those both produce results like the youtube video I shared in the OP.

Anybody ever implemented either of those very complex algorithms in C# or perhaps Java? I can only find C++ and python examples so far…

[MD_Reptile]

Figured I’d add what I settled on.

Firstly, I went with a more simple vehicle physics system where the vehicles have a pretty tight turning radius. This made a big difference, because the AI could more easily follow a path. Secondly, I made the navmesh not let the car go into an area thats too tight (raised the radius of the character for the mesh) and this prevented the AI from going down paths that are just too tight for it to turn smoothly into. This produces pretty good results so far!

[MD_Reptile]

Also - I added raycasting for avoidance that overrides whatever the pathfinding decides, and this helps the vehicles avoid one another, and dynamic obstacles - all without the added cost of “cutting” the A* mesh at runtime or other techniques that got too heavy. Basically I have the AI guide it first, and then check second if it should instead perform an evasive turn to avoid hitting some detected obstacle ahead of the vehicles.

[disorganized]

Just out of curiosity, what do you do if the vehicle enters a 4-way intersection and you want to make a left-hand turn? Does the pathfinding just hug the left-hand side of the road? How do you get the pathfinding to stay on the right side of the road and still turn left into the correct lane?
I have a similar situation but I ended up using a waypoint/rail riding system (works OK since my situation is all city driving).

[MD_Reptile]

I am not for sure, but it sounds like your talking about vehicles driving normally and obeying traffic laws and such - which are different than what I was going for with this vehicle AI I implemented.

For all pathfinding ai cars, regardless of the situation, I used a navmesh with A*. My pathfinding vehicles did not follow the rules of the road or even know anything about a road. All they did was follow a guide object that was following an A-star path, and they use raycasting to avoid any obstacles like traffic cars or other agent vehicles. The vehicles that are agents following the navmesh were police and criminal vehicles, speeding through intersections ignoring signal lights and laws as they chased or evaded other vehicles - so they didn’t need to consider any kinds of waypoints or a network for the roads, they just had to avoid obstacles and get from point A to point B (or from where they are to where a target vehicle is if they are pursuing).

The traffic cars themselves I used a simpler physics model up to the point they crashed or crashed into - I had vehicles basically “on rails” interpolating along carefully generated road network waypoints, with a single raycast watching so the traffic cars don’t run into vehicles in front of them. Luckily it wasn’t a very realistic setting in the game, and I didn’t need the traffic vehicles to carefully avoid each other in intersections and turns, as it was ok if sometimes they wrecked, but the forward raycast worked well enough as they would detect a car turning in front of them as they approached an intersection, and would slow down and avoid an accident usually.

Anyway, for the intersections there would just be a waypoint at the point where the vehicle is about to enter the intersection, and then another couple waypoints in a bit of a curved position through the intersection towards the next lane that they lead to. The traffic cars turning left would aim towards the middle points at an angle not directly towards the next point, before heading right to the next waypoint at the start of the lane they were turning into. I hope that makes sense!

Here is an GIF that maybe helps explain:

Here you can see white triangles that represent the waypoints “in the middle” of the intersection, and the traffic cars go towards these before going towards the blue ones, which are the main waypoints of the lane they are going into. For the record - later I didn’t use navmesh “cutting” or whatever you would call it for avoid traffic cars, as that was too expensive for performance, and instead had raycasting to avoid the traffic vehicles for the navmesh vehicles. Also used only a single raycast on traffic cars, here shows 3 per car.

[disorganized]

I understand.
I think for my situation (takes place in the 1920s, city grid-roads) riding on rails works 'cause the cars aren’t fast or move in any kind of fancy way. I just ‘pre-set’ the turns at each intersection so they stay in the correct lane. The only other issue is checking for parking space. I’m debating using colliders for the 4 sides of the car, instead of raycasting from different directions. Not sure if that makes it any more efficient.
I’ve always thought about how I could return to a navmesh type of movement but I don’t think it really works for me.

Thanks for the reply.

[Ch1ckenNug]

If anybody still has this issue, try making some sort of implementation of this tutorial. It helped me a lot:

Car AI logic - P6 Simple Traffic System in Unity