6
\$\begingroup\$

I have an A* implementation that works in "top down" situations where gravity is not taken into account for pathfinding. But, I am looking to modify to work in a 2d platformer situation. I am using the Unity Engine in C# but any examples or even pseudocode would be really helpful. I have found a source so far but it haven't been that helpful as I am not understanding the way they have adapted A*, I have listed them below.

http://gamedevelopment.tutsplus.com/tutorials/how-to-adapt-a-pathfinding-to-a-2d-grid-based-platformer-theory--cms-24662 (Very specific to authors implementation and hard to understand)

\$\endgroup\$
2
21
\$\begingroup\$

You don't need to adapt A* at all. The only consideration is where you put your nodes and how you connect them. The linked article seems to convert from a platformer-friendly model to a grid based pathfinding model, which I don't think you want.

A* itself is a tree search algorithm which finds the optimal path through your graph and requires some heuristic - meaning a function, which establishes how close to the target they are. In your case this can just be Manhattan or Euclidean distance. A* doesn't really care what the graph represents, it just sees it as a graph.

The only concern here is how to create the actual graph and how to determine movement cost between nodes. When moving on a 2 dimensional plane (so not a platformer), I've found that making a move in a cardinal direction (horizontal or vertical) costing '1' and a move in a diagonal direction costing '2.49' works well. Similarly, for your platformer, you will likely want to give a higher cost to jumps and drops.

Crating the graph

As the thread How can I implement platformer pathfinding? says, the way you will create your graph depends heavily on how your platformer works - what mobs can actually do and what you would like them to do. Here are a few examples though:

Simple platformer pathfinding graph

This first example assumes you cannot "jump through" blocks. Meaning you can't jump up through a block to reach a higher level, and can't jump down through a block. The graph can be simplified by removing all non-intersecting nodes (meaning nodes with exactly two ways out). I kept them in the image to contrast it with the next one.

Platformer pathfinding graph with allowed jumps to higher platforms

In this graph, jumps to higher platforms are allowed from lower ones.

Platformer pathfinding graph with allowed drops to lower platforms

In this graph, jumps are allowed to lower platforms. Usually games tend to have 'specially marked' platforms, where drops are allowed, so this sort of connection might only be present with a particular kind of platform in your game.

And of course you can also do this so both drops from platforms and jump to platforms are allowed: (just for the sake of completeness)

Platformer pathfinding graph with allowed drops to lower platforms and jumps to higher platforms

Pathfinding events (animations, physics, jumps)

You will likely want to implement some sort of animation for each of these or some sort of behaviour, which ensures the move actually happens. For example, for jumps you might want to apply some force to the mob. The amount of force to apply you'll need to calculate yourself for your game, or determine through trial and error. What I wanted to mention is that, once the path has been determined and stored in the NPC, and the path is actually being executed (meaning the NPC is following the stored path), you will want to keep track of the next node it's moving towards. Once the node is reached, you trigger some sort of event on the NPC, for example NPC.OnPathfindingNodeReached(action). the parameter action can be stored in the nodes for each of their possible exits. For example:

Actions stored in pathfinding nodes for possible paths

Movement cost and common errors

In terms of common non-obvious errors in pathfinding, they mostly have to do with mismatched movement costs. To ensure decent looking pathfinding, you must ensure that shorter paths always have a smaller cost. Depending on whether you manually or algorithmically assign costs, this can be much harder to do properly than it might seem at first and a major nightmare to debug. I recommend that you give a lot of care to assigning costs when doing this and testing everything as you make it.

Movement cost consideration in pathfinding

I hope this post answered at least some of the questions not answered in the linked post. If you need more help, please comment.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you very much. I am shocked, this is the best response I have ever seen. This has been really useful to me, I will see what I can conjure up with this new knowledge :D This is far more than adequate and I am sure will be useful to many others as well. Thanks once again. Have a good easter! \$\endgroup\$ – toinfiniityandbeyond Mar 27 '16 at 21:16

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.