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)
Answer
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:
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.
In this graph, jumps to higher platforms are allowed from lower ones.
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)
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:
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.
I hope this post answered at least some of the questions not answered in the linked post. If you need more help, please comment.
No comments:
Post a Comment