Pathfinding with inertia

Question

I'm currently working for pathfinding for a game where units are moving, but they have inertia. Most typical pathfinding algorithms (A*, Djikastra, etc.) are simply designed to minimize the length of the path.

However, these techniques do not apply, as far as I know, to instances where the unit has inertia. If the unit has inertia, then there is a significant difference in the cost to leave a tile in a particular direction based on the direction you want to go.

For example, the cost of leaving a tile proceeding North is significantly higher if you entered the tile from the East than if you entered from the South. (In the former example, you would have to slow down to halt you East-West velocity, while in the latter, you could go straight through.)

The fact that the system has inertia means that in order to make a turn, you may have to slow down well in advance of making the turn. My best thought to date is that you calculate the additional time it would take to slow down, and then add it to the heuristic cost of moving. However, this would seem to imply that you could never add a tile to the closed list, as entering from another direction could fundamentally change the cost of moving.

In addition, the concept of using a grid is an abstraction anyway, because both position and velocity are floating-point concepts. Is there some algorithm that could handle pathfinding on an open plane with inertia better than A*, or what modifications could I make to a pre-existing algorithm to make it suitable to this kind of motion?

Answer 1

The only new constraint that inertia lays onto path-finding is continuity, which means no sudden breaks in velocity. Start by generating an A* path, but with a big twist. The reason A* by itself is not appropriate is because it violates continuity, so lets make a new one.

A* chooses the best path as the shortest path, but with inertia the shortest path is no longer the fastest path. The fastest path is going to be the one that gives the shortest path without breaking continuity.

Normal A* allows each iteration to "jump" to an adjacent tile starting with the lowest cost. Instead of allowing only adjacent tiles, we will allow any tile that is within our range of motion for the next turn. This means the only tiles we can choose next are the tiles that would require us to change momentum an amount the object physically can.

TLDR: We shift the choices of A* by our momentum and add that to our momentum.

Answer 2

Pathfinding algorithms like A* can deal with inertia (or any other dimension you can throw at it) just fine. The key is to treat them as an additional dimension, and create a higher-dimensional search graph to search in.

To keep things simple, let's suppose we have only two speeds: slow and fast, and this path:

A --(sharp turn)-- B ----------- C --(ravine)-- D

To execute the sharp turn AB, we need to be slow; to jump the ravine, we need to be fast, and we can only change speeds on paths. Here's the resulting search graph:

(fast): A       B ----> C -----> D
                  \   ^
                    X
                  /   v
(slow): A ----> B ----> C        D

So you can see, the only path from A to D in this case is by A to B slow, B to C speeding up to fast, and C to D fast.

Path cost is also easy: it depends on the speed. So if we arbitrarily decide that the cost of fast-fast is 1, fast-slow or slow-fast as 2, and slow-slow as 3, the cost of A->D is 3 + 2 + 1 = 6.

The problem as you may have guessed, is that A* operates on graphs, and not on continuous ranges. That is, you need to come up with discrete speeds like I did with slow/fast, and each additional speed level will multiply the size of your search graph. The more physically demanding your game, the more speed levels you'll need, and the more costly pathfinding will be, and at worst it will be too expensive for games. If it is, then you have some other options:

• Make your AI cheat so it can fudge some paths, for example being able to make a turn even if it's going slightly too fast. This means you can get away with less speed levels in your A* search graph
• Similar to racing games, pre-calculate ideal path curves, and your AI simply navigates to the best node on that curve and continues along it