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

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

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/