A* Algorithm for Tactical RPGs?

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP












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.










share|improve this question









$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















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.










share|improve this question









$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













15












15








15


8



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










share|improve this question









$endgroup$




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.







path-finding






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked Jan 28 at 7:53









user137user137

21828




21828







  • 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












  • 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







5




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




$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










4 Answers
4






active

oldest

votes


















32












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






share|improve this answer











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






share|improve this answer











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






share|improve this answer











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






    share|improve this answer









    $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





    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "53"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );













    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fgamedev.stackexchange.com%2fquestions%2f167545%2fa-algorithm-for-tactical-rpgs%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    4 Answers
    4






    active

    oldest

    votes








    4 Answers
    4






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    32












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






    share|improve this answer











    $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















    32












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






    share|improve this answer











    $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













    32












    32








    32





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






    share|improve this answer











    $endgroup$



    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.







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited Jan 28 at 13:52

























    answered Jan 28 at 12:54









    Jack AidleyJack Aidley

    1,243613




    1,243613







    • 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












    • 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







    10




    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




    $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




    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




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






    share|improve this answer











    $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















    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.






    share|improve this answer











    $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













    13












    13








    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.






    share|improve this answer











    $endgroup$



    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.







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited Jan 29 at 18:19

























    answered Jan 28 at 9:28









    PhilippPhilipp

    79.5k19183236




    79.5k19183236







    • 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












    • 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







    9




    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




    $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




    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




    $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




    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





    $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




    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




    $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




    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




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






    share|improve this answer











    $endgroup$

















      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.






      share|improve this answer











      $endgroup$















        2












        2








        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.






        share|improve this answer











        $endgroup$



        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.







        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited Jan 29 at 2:07

























        answered Jan 29 at 1:51









        MarsMars

        1213




        1213





















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






            share|improve this answer









            $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















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






            share|improve this answer









            $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













            1












            1








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






            share|improve this answer









            $endgroup$



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







            share|improve this answer












            share|improve this answer



            share|improve this answer










            answered Jan 29 at 11:02









            DamonDamon

            1,26466




            1,26466







            • 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












            • 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







            1




            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$
            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




            $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

















            draft saved

            draft discarded
















































            Thanks for contributing an answer to Game Development Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid


            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.

            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fgamedev.stackexchange.com%2fquestions%2f167545%2fa-algorithm-for-tactical-rpgs%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown






            Popular posts from this blog

            How to check contact read email or not when send email to Individual?

            Displaying single band from multi-band raster using QGIS

            How many registers does an x86_64 CPU actually have?