exploring more dimensions with A*

When you're running A*, you're searching over the edges and vertices of a graph, where the graph's vertices represent some kind of state, and the edges between vertices are the state changes. In pathfinding, the states are positions, and edges are the smallest movements you can do to get between neighboring positions, like "move +X", or "move +Z".
State = {x, z}
State Transitions = { +x, -x, +z, -z }

You end up with a resulting path like this: Grey tiles are blocked, white are unblocked, and red shows the resulting path found by a pretty vanilla A*, going from upper right to lower left.
Blue shows the nodes we visited during the search.


This can be kind of crappy for games where you want to model more complex mechanics of motion: characters in games can't really just "move +Z". For an example, imagine a car - they can take several seconds to accelerate up to full speed, or to make a 90 degree turn. If we build a shortest-length path for the car to follow, he'll have to drive really slowly to make all the tiny fiddly sharp turns (or in the worst case, be completely unable to make them at all). This might be the shortest distance, but it's not the shortest duration path. And even in games with just human characters (which I work on), you can sometimes spot guys running at full speed trying to follow a shortest-distance path, which makes them look robotic. It can also cause bugs if we try to satisfy physical constraints about limited acceleration or turn speeds, and the path violates those contraints (eg. making 90 degree turns around corners).

If we can more accurately model the state space, we'll get a more accurate shortest-duration path:
State = { x,  z, vel_x, vel_z }
State Transitions = { +vel_x, -vel_x, +vel_z, -vel_z }  // the driver only controls acceleration, not position
Then if we also have an appropriate interface for A* to know about this more complex state (so get_neighbors(state) needs to return the result of acceleration in each direction, and heuristic_cost(state) takes velocity and acceleration into account to derive a minimum arrival time), we get something like this instead:


For this image, our dude can move at a top speed of 10 tiles/sec, but can only accelerate at 1 tile/sec^2 (which is a roughly car-ish ratio of top speed to acceleration).
What's cool about this is:
- it's indeed a shorter-duration path even though it's longer
- the driver avoids navigating around all the little obstacles
- you can see the faster path "swings wide" around that corner to be able to go faster
- you can see the explored region (in blue) finds the few quick paths through the obstacles

Neat! It makes me want to make an all-terrain driving obstacle course game. I think to be really accurate, you'd want to feed something close to the game's real rules/simulation into A* - so that it could explore the accurate consequences of its choices. In that case, the inputs for a car would probably be something like:
State Transitions = { rotate steering left, rotate steering right, more gas, less gas (or brake) }
(or whatever the inputs to a car are for your AIs).

The big downside, of course, is the cost of computing this stuff, since we're exploring in more dimensions. For the blue region shown on the map, in the worst case there can be up to 200 "visited" nodes overlapped on each tile position (because of how I quantized my velocity - I don't know how you'd do this with a more analog velocity space). Practically it wouldn't be so bad, but in my test code, paths were about 20x more expensive to find - and certain clever optimizations to A* (like jump point search) don't work anymore.

My pipedream, though is to write a bot for "quake done quick" that has the player's inputs as the state space:
State Transitions = { w, a, s, d, jump, aim delta, fire, switch weapons }
But that sounds impossibly slow, right? If that bot could discover rocket jumping, I'd be ecstatic.