A* Algorithm for Tactical RPGs?

Question

I'm messing around with writing a really poor tactical RPG in C++. So far I have a 2D tile map and just got the A* algorithm working based on the pseudocode in the wikipedia.

But real tactical RPGs don't just find the best path on a flat plane and move there. They typically have limited move ranges and must climb up or down. If you've ever played Final Fantasy Tactics these would be affected by the Move and Jump stats. This is where I get lost. How do I alter the A* algorithm so that it finds the best path toward a target, but the path is only so many tiles long? How should I take height differences and jump stats into account? How do I implement jumping over a gap?

If it helps, right now my map is represented by a Vector of Tile objects. Each tile has pointers to the North, South, East, and West tile, which are set to a nullptr if no tile exists there, such as along the edge of the map or if a tile is set to non-passable.

Answer 1

Climbing, and gaps, are just different cost functions. For a unit that can jump the gap has a normal(?) cost, while for a non-jumping unit it has arbitrarily high cost. Climbing costs extra, as does difficult terrain, etc. The A* algorithm is well able to handle cost functions, so if your implementation is not doing it already, just google for how to implement A* with a cost function.

Having said that, however, I don't think A* is a particularly good approach for a tactical RPG. Or more accurately, it's not a complete story. You don't want your units to blindly blunder towards their goal, you want them to position themselves to exploit cover, high ground, whatever, whilst progressing towards the ultimate goal and seeking to flank opponents and so forth. So the tactical value of the end point of each move is of huge importance, not just how close it is the goal. This requires more in-depth problem solving than mere pathfinding.

Answer 2

When you want all possible movement options of a unit, use Dijkstra's Algorithm.

The difference between A* and Dijkstra is that Dijkstra gives you all the possible shortest routes achievable with a given cost, and if none of them reaches your destination yet, it increases the cost by one and continues. A*, on the other hand, prefers to calculate those routes first which have a good chance to reach the destination.

So when you just want the shortest path from point A to point B, then A* is a good choice. But if you want all possible movement options and the shortest path to each of them, then Dijkstra is exactly what you want.

All you need to do is run Dijksta's Algorithm with no specific destination node, but with a maximum cost which must not be exceeded (the unit's movement range). When traveling to a node would exceed the maximum cost, do not visit it. When the algorithm terminates due to lack of unvisited edges, each node in the visited set is a possible destination, and the previous node markers of the nodes form a linked list representing the path back to the initial node.

Regarding jumps: Those can be represented as yet another edge in both A* and Dijkstra. They can have the same cost as traversing a regular edge or a different one. You can also pass a "jump_height" parameter to the algorithm which tells the algorithm to ignore jump-edges which exceed a given height.

Answer 3

The other answers have some good information, so be sure to read them.

However, to answer your question: based on the pseudocode that you linked to, you have some kind of function heuristic_cost_estimate where you're calculating the cost from tileA to tileB (assuming they are adjacent). Instead of using a flat (1) for that cost, you would have to adjust it to include the tile stats and unit stats, and possibly edge stats.

For example:

if (edge == JUMP && !unit.canJump()) 
    return INF;
if (tile.Type == Forest && unit.moveType == HORSE) 
    return 2;
//Other cases here
//-----
else 
    return 1;

This will give you your path. Then, you would simply move the unit along their path while consuming movement points and stop them when remainingPoints < edgeCost. Note that this may not be completely optimal if you end up with remainingPoints = 1, but it should be good enough for a practice RPG. In reality, you'd want more tactical, as Jack Aidley pointed out!

Challenge:
If you want to get more advanced, you probably want to use Djikstras as suggested to find all spaces within X distance, then you want to evaluate each space in that list for a "best" place, based on closeness to target, defense power, whether or not you can be attacked from that position, etc. Based on that info, you would choose a tile, then move there following the path you just calculated using Djikstras.

Answer 4

Climbing and gaps are pretty trivial since they only modify cost. Pathfinding (and most of tactical AI) is all about summing up the cost on all to-be-visited nodes and minimizing that. An impassable cliff will have an infinite (very, very high) cost, slopes will have a higher cost than normal, etc.

This, however, finds the globally optimal path which not the best solution because real adversaries usually do not find the optimal path. It's highly unrealistic, sometimes to a point which is obvious to the player, and annoying (especially when the AI as such is basically invincible because it, too, chooses the optimum).

Good simulations deliberately do not find the best path. A much better algorithm might be to do hierarchical pathfinding -- if nothing else, by drawing a straight line on the map, and taking 4-5 waypoints, then pathfinding from one waypoint to the next, considering only the node weights that are so far known, and setting all other node weigths to "indifferent". Alternatively, you can run A* on a coarser grid first, and then pathfind from one large node to the next (but I'm guessing that drawing a line on the map is just fine, too).

This is much more realistic (and also consumes a fraction of the processing power because the graph is much smaller). Yes, it can mean that a unit moves towards a cliff only to find out that it can't get across. That's fine, it happens to real adversaries, too. Next time, it won't happen again (because now the infinite cost is known).