15
\$\begingroup\$

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.

\$\endgroup\$
  • 5
    \$\begingroup\$ I don't know why move range is a problem. Find the shortest path, and then after that, move 'speed' squares along that path. \$\endgroup\$ – Mooing Duck Jan 28 at 19:23
33
\$\begingroup\$

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.

\$\endgroup\$
  • 10
    \$\begingroup\$ Good points about the 'tactical positioning', but those decisions might be applied at a level higher than the basic pathfinding. On the other hand, applying costs to the nodes in the pathfinding algorithm that are generated by some sort of tactical analyser might be a good option. For example, if the enemy has line of sight across with terrain then make nodes on that terrain have a very high cost. \$\endgroup\$ – DrMcCleod Jan 28 at 13:33
  • 1
    \$\begingroup\$ @DrMcCleod: Indeed, and that is what I meant by "Or more accurately, it's not a complete story". You could certainly be using A* or another algorithm to do part of the processing, however I think I would avoid approaches such as trying to avoid watched nodes through movement cost since moving across terrain where a unit might come under fire is better handled as a risk/reward calculation, IMO. \$\endgroup\$ – Jack Aidley Jan 29 at 9:50
13
\$\begingroup\$

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.

\$\endgroup\$
  • 9
    \$\begingroup\$ Worth mentioning here that A* is really just a generalisation of Dijkstra, so if you understand one it shouldn't be too hard to understand the other. \$\endgroup\$ – Cubic Jan 28 at 12:08
  • 8
    \$\begingroup\$ Indeed, if you have a heuristic that just returns 0 in your A* algorithm, congratulations! You have just written Dijkstra's algorithm. \$\endgroup\$ – Yann Jan 28 at 12:18
  • 9
    \$\begingroup\$ "Dijkstra gives you all the possible shortest routes achieveable with a given cost, and if none of them reaches your destination yet, it increases the cost by one and continues" - That is neither how it works nor what it outputs. It's actually just a generalization of breadth-first search to weighted graphs. It finds a single shortest path. A* is just a generalization of that, for when you have a distance-heuristic available. \$\endgroup\$ – BlueRaja - Danny Pflughoeft Jan 28 at 18:05
  • 1
    \$\begingroup\$ Not sure why this is so upvoted. From a pragmatic viewpoint, Dijkstra is obsolete. It's taught in CS for educational and historical reasons. Even A* is obsolete for serious work; Google Maps certainly doesn't use it. You'd be looking at ArcGraph variants nowadays. \$\endgroup\$ – MSalters Jan 29 at 8:32
  • 2
    \$\begingroup\$ @MSalters Dijkstra and A* are perfectly fine algorithms for simple problems such as tactical RPGs. There is a very narrow range of valid movements (tiles) and a very limited amount of ways to move across said tiles (orthagonal, sometimes diagonal) and usually a fairly short maximum path: SQRT(ArenaWidth² * ArenaHeight²). Computationally, the difference is negligible on a modern machine for what's likely fairly small values so why bother with a more complex implementation when a simple one is sufficient for the purposes outlined here? \$\endgroup\$ – Valthek Jan 29 at 10:59
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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).

\$\endgroup\$
  • 1
    \$\begingroup\$ Mind you, that "simple hierarchical pathfinding" can look pretty stupid. You get units walking straight to a mountain ridge, only to discover there that the path is blocked. They then route through the mountain pass to the next waypoint, and from there to their destination - even if that latter waypoint was way off course for them. Preprocessing would have identified the mountain pass up front and waypointed through there. But even if you don't do that, once you are too far off the planned course you should re-plan the remainder. \$\endgroup\$ – MSalters Jan 29 at 14:47
  • \$\begingroup\$ @MSalters: That can happen with the "draw a line" method even after the first attempt, yes. It's unlikely to happen more than once with the coarse grid hierarchical method (which e.g. takes the average, or the median, or even the max cost value of the nodes within). It's pretty much exactly how a human adversary would play -- avoid big obstacles that you know about or can see from afar like a mountain chain, and otherwise plan a coarse mostly straight route, and bite your way through. Unless you know that there's a mountain, you walk straight to it. \$\endgroup\$ – Damon Jan 30 at 9:53

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.