Hi. I have implemented a navmesh but have some trouble calibrating the vehicle movement on it. First let me briefly describe the navmesh implementation: Least cost paths are precalculated in the navmesh. When a vehicle wants to go from point A to point B: - it checks the cell it is in. - it reads up the cell edge index through which it must go. - it calculates the intersection between its vector and that edge as an intermediary destination. - once this intermediary destination is reached, it is in the next cell and goes through the same cycle until it reaches the destination face. I have difficulty to have my vehicle correctly navigate the mesh. The vehicle uses simplified physics (the same as described in Craig Reynolds' article on flocking behaviors). The vehicle does not compensate/anticipate enough on its inertia. My questions are about your implementation of navmesh navigation. - What kind of vehicle model have you used ? - What were the troubles you encountered when calibrating the movement of your vehicle on the navmesh ? - How did you solve your troubles ? Thanks in advance. Ghostly yours, Red.

Okay.
I now have a decent navigation. Still, I am quite surprised it requires in the end some hand tuning once all the steering algorithms have been checked. I do not recall having read anything about the tuning process (in the gems books or on the web).

I am still interested to hear about others experiences to see if it was solved algorithmically or if the vehicle characteristics were hand tuned to best effect.

I am especially interested about the tuning of navigation systems when having mixed size cells (the navigation in close quarters versus navigation in large space like navigating a corridor vs navigating a large room).

Thanks in advance.
Ghostly yours,
Red.

typically with vehicles your solution will involve a combination of something like the nav-mesh solution that you've created and a set of rules about how to design that nav mesh. basically you come up with a way for vehicles to move, then you ensure that your levels are designed in a particular way so that the vehicles behave happily on that level. I'm not sure there are simple generic solutions that will work on all level layouts.

In all the AIs i've worked on we've always required some hand tuning of specific levels because the AI wasn't behaving completely happily there. But the realities of the development cycle were such that we didn't have the luxury of developing the AI and then developing levels that maximise the AI's "intelligence". Both happened in parallel and so we inevitably ended up with some maps on which the AI wasn't really happy that required hand tuning.

-me

Thank you for your answer.
I am glad I am not alone on that one.
Ghostly yours,
Red.

Hi Red,

In robotics there are some methods of including kinematic constraints of a vehicle into searching process, such as usage of "Ego-kinematic space". Unfortunately, those are too complex for real-time applications such as games.

Since pathfinding and steering are usually separate tasks in games, I don't think there is any way to guarantee collision free paths for a vehicle (besides designing levels where collisions are very improbable). But as you did, there are methods of configurating the pathfinder to provide paths that are easier to follow by steering algorithms (altough I'm not sure if you were talking about tuning the steering algorithms or the pathfinder).

I can come up with three ways of improving vehicle navigation:
- Use a graph that provides paths which are easy to follow (triangle-based navmesh may not be the best one)
- Use post-processing to smooth paths. The smoothing process should make sure that paths remain collision-free.
- Configure the steering algorithms to match the locomotion model of a vehicle. Instead of using vector math based steering, neural networks could provide automatic adaptation to the kinematic constraints.

I'd be interested to hear how exactly did you configure your system!

-Jarmo

If you want an exact solution to your problem, then you can perform a search on a graph where nodes represent spatial constraint points for splines. The splines are further constrained by a velocity constraint, which is expressed as a constraint on the parametric velocity of the solution spline generated to fit the nodes. Obviously there are many such splines that could fit a given set of nodes, so you further enforce cost constraints on the spline; choose the spline that minimises some cost function on the spline (just as you do when you connect two search nodes in a normal pathfinding search by a straight line... you assume that this is the cheapest path between those nodes). Then your search algorithm is a search for the lowest cost spline over the space of splines defined by a discrete set of constraint points and the velocity constraints. Hopefully that makes sense. It sounds harder than it actually is! 8)

Cheers,

Timkin

@JarmoKauko:
In fact regarding my own simple implementation, I am tuning manually the vehicle model based on the kind of mesh I am using.
My simple vehicle model uses three characteristics:
- Max speed
- Max steering angle at a given speed away from velocity vector(between 30 and 90 degrees)
- Mass of vehicle

In twisty navmeshes, I reduce the max speed and increase the max steering angle (I can also reduce mass to increase the reactivity of the vehicle).
In large navmeshes, I increase the max speed and decrease the max steering angle.

As to the steering algorithm, I have two steps:
- calculate the next intermediary destination based on the Face the vehicle is in and the position and Final destination vertices. This calculation is done each time the vehicle changes face. The path is already smoothed because the algorithm searches a few faces ahead.
- calculate wether there is a wall (i.e. a face edge not leading to another face) directly in front (wether it is in the same face or in the next faces) and the distance from that wall in percentage of the velocity vector. The velocity vector is clamped by that percentage.

I use a dynamic algorithm because of collision avoidance with other vehicles: I don't know where my vehicle will end when avoiding dynamic obstacles.

@Timkin: Interesting... It does look like an algorithm for racing cars. Eventhough I do not need such precision, it started me thinking on an evolution. Since I tune my vehicle based on the kind of mesh I encounter, I also could directly encode in the navmesh the speed limit for certain faces to avoid overreaction. This may be certainly better than having the vehicle bumping in certain circumstances at max speed the wall and sliding along. This will certainly reduce the amount of manual vehicle tuning.

Thanks everybody.
Ghostly yours,
Red.