How can I incorporate the path of a jump into my A* implementation?

Question

I need to calculate the path of a jump via A* for a simple platformer game. Calculating the direction is simple, but translating the jump physics into pre-calcuted voxel paths is a bit difficult. Especially when you factor things in like obstacles. Based on the image below, what is the best way to calculate jump in A*?

To give better context, here is a video of the game I'm working on. Will be implemented here to get companions following the player

http://www.youtube.com/watch?v=yMrbCtb2Buk

Answer 1

First of all understand that A* only works well for a limited set of problems. If you can't make a heuristic that gets close enough to the actually required time then Dijkstra's algorithm is often faster. On top of that it works with teleporters, speed boosters and anything else that breaks the standard assumptions of Euclidean geometry. And it is easier to implement.

The theoretical perfect solution to the problem is to use a search space that include velocity, and any other variable that is relevant to movement, so for a typical 2D platformer you would have a 4D search space consisting of position and velocity. Whether or not this is computationally feasible depend very much on the nature of the game.

If you use float precision it is pretty much impossible to make perfect pathfinding in any case, but if your physics system binds all values to a limited integer space it may be perfectly doable.

If the complete search for any reason is too much you may want to artificially limit the search space, this could for instance be through any combination of the following:

• Do not allow slowing down while running. (Though you must provide some means for the character to turn around before and after jumps.)
• Do only allow jumping at specific points. (Edge of platform and X distance before the end of other reachable platforms seems suitable.)
• Limit the air control to only change simulated input every X physics frames.
• Implement "buggy A*", that is favour branches that are physically closer to the target even though you cannot guarantee that they will be faster if they are chosen.
• Converge paths that are almost at the same spot in search space, if two routes lead to running in the same direction on the same platform you should terminate the slowest of the two search branches.

Depending on the context the result of these implementations may be satisfactory.

This whole answer assumes a fixed physics rate, combining variable physics rate and predictive AI is a world of trouble.

Answer 2

After heavily contemplating and consulting with many devs on how to solve this problem, I eventually came to the conclusion that A* on a pre-processed map is the best solution. Here's why:

• Practically instant run time since A* traverses the map with everything it needs to calculate the jumps
• Pre-processing can be performed at level load, fast enough to run again later after tile destruction
• Clearance support is extremely achievable
• Maps can be easily broken up into quadrants for extremely large tile amounts (1000 x 1000 voxels plus)

The process to use pre-processing with A* for gravity can be broken down into a few simple steps. If you already have A* this shouldn't take too long to implement.

1. Calculate clearance values from collision tiles
2. Discover all ledges by looking for missing tiles on the top, left, and/or right or a tile. Also get all walkable tiles
3. Connect all ledges within the maximum jumping distance and that pass a simulated parabola line test (or physics but this will probably kill your runtime)
4. Perform a runoff test on all ledges that draws a curved 135 degree angle in the direction of the ledge. Anywhere the test lands create another jump connection
5. Run a drop test to see if fall locations are present on the sides of ledges
6. A pre-existing A* implementation should be able to swallow this information with minimal tweaking since it can traverse through flat walkways and ledge connections now

Additionally here is an interactive demo I built based upon the above theory (source code available).

http://ashblue.github.io/pathfinding-platformer/