7
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ Couldn't you try to find a way to give a value to the cost incurred by inertia and add it to your pathfinding algorithms? From what I recall, they are based on cost from traversing node graph, so inertia could serve as weight? \$\endgroup\$ – Vaillancourt Jun 9 '15 at 21:51
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Wouldn't that mean that we could never stop travelling in the direction that we started out going in? For example, if you started accelerating left, and you continued that for several tiles, you couldn't stop in just 1 tile. You would have to continually slow down over the course of several tiles. \$\endgroup\$ – Stack Tracer Jun 9 '15 at 22:10
  • \$\begingroup\$ @StackTracer If inertia is implemented then yes slow down must be continuous unless some other form of slowdown is added. \$\endgroup\$ – newton1212 Jun 9 '15 at 22:13
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.