2
\$\begingroup\$

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

Jump Example

\$\endgroup\$
7
  • \$\begingroup\$ map each jump that is possible (either by hand or automatically) once and add those to the graph \$\endgroup\$ Jan 24 '14 at 9:25
  • \$\begingroup\$ Well I've gotten that far, but I'm trying to figure out the most bulletproof way to calculate the jump metrics in the algorithm's list processing. For example calculating the jump arc, how should this be accomplished? \$\endgroup\$
    – Ash Blue
    Jan 24 '14 at 9:40
  • 1
    \$\begingroup\$ Are you wishing to calculate the set of points the jumper will go through whilst jumping from one platform to another? \$\endgroup\$
    – AturSams
    Jan 24 '14 at 10:32
  • 1
    \$\begingroup\$ I don't understand the relationship between path finding and jumping physics? Are you writing code to decide if it's possible to jump from A to B? Or how long does it take to jump there? \$\endgroup\$
    – AturSams
    Jan 24 '14 at 11:06
  • 1
    \$\begingroup\$ Jordan Fisher (the guy behind Cloudberry Kingdom) had published a article on gamasutra about how to create a procedural plaformer, you might have a look there : gamasutra.com/view/feature/170049/… \$\endgroup\$
    – tigrou
    Jan 24 '14 at 14:30
3
\$\begingroup\$

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.

\$\endgroup\$
11
  • 1
    \$\begingroup\$ dijkstra is A* with heuristic set to 0, the heuristic can just be euclid distance to goal \$\endgroup\$ Jan 24 '14 at 13:51
  • \$\begingroup\$ Only needs to fire once every couple seconds. Its for companions to follow the main character. Meaning there is some leeway to cut corners for reducing overhead. Thx you btw, this is a great writeup. \$\endgroup\$
    – Ash Blue
    Jan 24 '14 at 13:58
  • 2
    \$\begingroup\$ "If you can't make a heuristic that gets close enough to the actually required time then Dijkstra's algorithm is often faster" - This is incorrect, A* with a consistent heuristic is always as fast or faster than Dijkstra's, even if that heuristic is horribly inaccurate. \$\endgroup\$ Jan 24 '14 at 18:02
  • 1
    \$\begingroup\$ Scoreboard? Search tree? Collisions? Can you give more details about what you mean by these, and how it's different from Dijkstra's algorithm? \$\endgroup\$
    – amitp
    Jan 24 '14 at 22:17
  • 1
    \$\begingroup\$ @eBusiness: with Dijkstra you have a variable cost, not 1 at every step, and you have to order the queue just like A*. I think you're thinking of Breadth First Search. \$\endgroup\$
    – amitp
    Jan 25 '14 at 0:14
0
\$\begingroup\$

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/

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .