6
\$\begingroup\$

i am making a 3d tactics game, visually similar to something like final fantasy tactics. it's tile based, with units able to move up and down the level onto buildings and up staircases and what have you.

im using dijkstra's algorithm to score every tile on the map that is within a units movement stat, then i highlight all of the tiles that are within our characters movement, then when you select one of those tiles, the unit follows the shortest path to that tile.

this all works fine, but i have one issue i don't know how to resolve. if a unit jumps from a certain height, it takes damage. this is fine, and i want to let the player/ai do this in order to take shortcuts at the cost of some hp if they want to. the problem is i will sometimes run into a case where there is a safer route to take, that while actually a longer path, is still within the units movement. for example:

two images, one demonstrating a unit jumping forward 1 tile down a 3 tile drop, the other showing the unit traversing a 3 step stair case into the same position, but for 2 extra movement

in this case, the unit is able to move 3 spaces in one turn, and it wants to move from the red space to the blue space, the green tiles are the spaces it can reach this turn. since this unit can move 3 spaces, we can avoid jumping from this height by going down the descending tiles and using all 3 of our moves to reach the blue space safely. since it is a turn based game, it doesn't matter that we move a few extra tiles, as long as we don't move more than 3 tiles in a turn. so i would want the pathfinding to favor not taking damage when it can.

if it can't avoid damage, like in this case:

the same image as before except the unit is jumping 3 tiles down for 1 movement, and moving 2 more tiles forward, which it couldn't do if it took the staircase down, so in this case i would want it to jump

the only way the unit can reach that tile is by using all of its movement, so taking the fall damage is unavoidable, and we let the player make the choice to take the fall damage or not.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ You can solve this in a way analogous to Tile Based A* Pathfinding, but with a Bomb, replacing the "bombs used" stat for "damage taken", and setting the cost function to weigh damage much much higher than movement cost. If taking 1 damage costs more than the unit's whole movement budget, A*'s cost minimization will ensure the agent takes a damage-free path if available, and only incurs damage if no other path works. \$\endgroup\$
    – DMGregory
    Jan 23 at 13:21
  • \$\begingroup\$ @DMGregory im attempting this solution, and i think i have almost got it, right now with unlimited movement it works exactly how i want it, preferring long paths with no fall damage over any path with fall damage. but when i try to enforce a movement limit, by adding an extremely high cost penalty whenever moves exceeds the max move limit, it just pretty much ignores it? im kind of at a loss. \$\endgroup\$
    – graveyard
    Jan 23 at 21:19
  • 1
    \$\begingroup\$ You don't implement a movement limit by adding a high cost when exceeding the move limit. You add a move limit by saying that any node that would exceed the move limit is not a reachable neighbour at all and is not pursued any further. (ie. don't continue computing with ridiculously high values, just stop computing — do less work whenever you can) \$\endgroup\$
    – DMGregory
    Jan 23 at 21:21
  • \$\begingroup\$ @DMGregory i had tried that as well but neither way works. im still just using dijkstra's algorithm, and i basically have two methods of scoring, one based on how many moves to get to a tile which is only used to avoid tiles out of range, then the other is the amount of moves + 100 for every time damage is taken, which is used to find the path. i count the amount of tiles moved the same way i would in a basic dijkstra's implementation, so im not sure where the issue could be \$\endgroup\$
    – graveyard
    Jan 23 at 22:18
  • \$\begingroup\$ We won't be able to help you debug your implementation of this without seeing it. \$\endgroup\$
    – DMGregory
    Jan 24 at 12:23

4 Answers 4

2
\$\begingroup\$

It sounds like your game is turn-based, so there will be a movement phase where you get to use up a certain number of movement points or move a certain number of tiles. And it sounds like for the movement phase you don't care how many "movement points" or such can be used, just whether you can get there or not.

A different case would be if you had something like 'action points' where you might want to spend some on movement and retain some to perform an action like attacking. That would make it more complicated.

So what you want is a list of all available tiles you can go to and the least damage you can take while getting there. I think each tile in your path then needs an array of objects with distance and damage, and you can't simply mark a tile as 'visited', but check if the new way you get there gives you less distance, or less distance for a given damage value. Both paths should be evaluated.

So when you are checking tilesTo and the tile doesn't exist, add it. If it already exists, add path to an array of from paths along with the distance. An example, say you are on tile B trying to get to E, with the numbers representing the heights, and you take 10 points of damage for each level dropped above the first, and tiles are joined horizontally and vertically:

ABCDE
FGHIJ
KLMNO
PQRST

Height map:

24100
23200
12100
01000

You begin with a starting node:

{ tile: B, from: START, distance: 0, damage: 0 }

Then you look at the tiles you can get to and add paths to them, queueing for processing:

{ tile: A, from: B, distance: 1, damage: 10 }
{ tile: C, from: B, distance: 1, damage: 20 }
{ tile: G, from: B, distance: 1, damage: 0 }

The tile A node above generates only one new path to F if you can't climb back to B, carrying along the 10 damage from the previous record, which is added to your list and queued:

{ tile: F, from: A, distance: 2, damage: 10 }

The tile C node when you process it generates two new records (assuming you can't climb back to B) based on the distance 1 and damage 20, adding 1 more distance but no more damage. These are added to your results and queued for processing.

{ tile: D, from: C, distance: 2, damage: 20 }
{ tile: H, from: C, distance: 2, damage: 20 }

Then you add the 4 paths you can get to from G. But here you can check the existing nodes and either replace them or ignore your current path if it is worse/equal in both distance and damage:

{ tile: B, from: G, distance: 2, damage: 0 } // ignored
{ tile: F, from: G, distance: 2, damage: 0 } // replaces and queues
{ tile: H, from: G, distance: 2, damage: 0 } // replaces and queues
{ tile: L, from: G, distance: 2, damage: 0 } // adds and queues

So for new nodes you generate, check existing nodes for that tile:

  1. If an node already exists for the same tile where the damage and distance are both <= the new node's damage and distance, ignore the new node - STOP
  2. Remove existing nodes for the same tile that have >= both damage and >= distance of the new node. Because we ignored the new node and stopped at step 1 if they were both equal, either distance or damage will be greater than our new node and the other value be greater or equal, so the new node is better in some way and at least as good in the other.
  3. Add the new node and queue it for further processing

When adding the node to tile B, we see that there is an existing node with damage 0 and distance 0. Since there is an existing node with the same or lower damage and the same or lower distance, we ignore our new node, we don't add it and don't queue it for processing.

When adding the node for tile F, we see an existing node with the same or higher distance and more damage, so we remove that existing node, then add our new node and queue the new node for more processing.

When adding the node for tile H, there is an existing node from C with distance 2 and damage 20, so we replace it with our new one because it has lower damage and queue the new node.

When adding the node for tile L, there is no existing node for tile L so we add it and queue the new node. Our list now looks like this (comments on queued nodes)

{ tile: B, from: start, distance: 0, damage: 0 }
{ tile: A, from: B, distance: 1, damage: 10 }
{ tile: C, from: B, distance: 1, damage: 20 }
{ tile: G, from: B, distance: 1, damage: 0 }
{ tile: D, from: C, distance: 2, damage: 20 }// in queue
{ tile: F, from: G, distance: 2, damage: 0 } // in queue
{ tile: H, from: G, distance: 2, damage: 0 } // in queue
{ tile: L, from: G, distance: 2, damage: 0 } // in queue

That was the first difference, we can replace existing nodes only distance or damage is less than any existing nodes for that tile and the other value is the same or less than the existing tile. But you can have multiple nodes for tiles as well if one value is higher but the other is lower. In the queue we will generate a new node for C from H that will have a higher distance than the existing node, but a lower damage. So we will queue it and keep both.

{ tile: C, from: H, distance: 3, damage: 0 }

Both of those nodes will generate nodes for tile D by carrying over the damage and adding 1 to the distance:

{ tile: D, from: C, distance: 2, damage: 20 }
{ tile: D, from: C, distance: 4, damage: 0 }

Say you have a maximum movement of 4, so in this case you would not queue up the last node because the distance is already 4, but the first node would be in the queue and allow you to move on to tile E:

{ tile: E, from: D, distance: 3, damage: 20 }

If you were using action points, you might want to present both options for moving to tile D to your player. Either they can move there using 2 points and taking 20 damage but have 2 action points remaining, or use all 4 action points to move there and take no damage.

In your game I think you would want to condense the list to have only one entry per tile with the minimum damage, so you would keep the tile D node with distance 4 and damage 0. It seems like for your display you would just show it as green or something since you won't be taking damage, but the E tile will show as red because the only way to get that far is to take damage.

\$\endgroup\$
1
  • \$\begingroup\$ perfect answer, could not have been clearer, and the examples helped a ton with making sure i was doing everything right step by step. thank you so much! \$\endgroup\$
    – graveyard
    Jan 25 at 14:17
2
\$\begingroup\$

I think the easiest way to do this is to do two passes of pathfinding. First, treat any path that would cause damage as being impassable. Try to solve the path, and if you exhaust your set before reaching the goal, then try again but allow the damaging path to be passable.

This will always prefer to take a non damaging route when possible but not prevent it entirely.

\$\endgroup\$
4
  • \$\begingroup\$ This would work, although it doesn't extend to preferring the path with the least damage. \$\endgroup\$ Jan 22 at 21:21
  • \$\begingroup\$ Correct, finding the path with the least damage is much more involved \$\endgroup\$ Jan 22 at 22:22
  • \$\begingroup\$ i don't believe this method would really work for this, since if there is ever a case where there are more than one drops in a row, as in the unit falls, then moves and falls again. the first pass would stop at the first drop, then the second pass wouldn't try to minimize damage on any drop after the first drop, because only the first pass cares about potential damage. \$\endgroup\$
    – graveyard
    Jan 22 at 23:05
  • \$\begingroup\$ An improvement to this that would at least encourage avoiding damage on the second pathing would be to include damage in the distance calculation; e.g. a point of damage is scored as an extra 5 meters of travel. That would produce a compromise low damage unless it takes you way off route \$\endgroup\$ Jan 23 at 8:18
2
\$\begingroup\$

If you want to be able to distinguish not only no damage/ some damage but also find the lowest total damage possible then I think you need to add weights to the paths between neighboring tiles. So if you can pass directly from a tile to its neighbor without taking damage the weight of this passage is 1. If you can pass directly between the two tiles but take damage the weight is 100 times the amount of damage. If it is impossible to pass between the two tiles you can either put no path or a weight of 10000.

Next you apply a weighted pass finding algorithm that tries to find the path with the smallest total weight. If it is possible to find a path with no damage then this path will always have lower total weight than a pass with damage. If only paths with damage exist then if the individual damaging passages are weighted according to damage this will find the paths with the smallest amount of damage. Finally you need a check that if the total weight of the path is bigger than 10000 than you can't go there so you don't show that tile as reachable.

In response to comments: This algorithm makes indirect use of the fact that the maximal total number of steps a unit can make is limited, in OPs example to 3. You also need a hard check that only paths with at most 3 steps total are evaluated (or considered at the end). If you do this, this algorithm works as intended.

If you want to go from the red tile to the green tile at the bottom right next to it, the algorithm finds two possible paths using at most 3 moves. First the direct jump with cost 100 and 1 move and second taking the stairs with cost 3 and 3 moves total. Taking the stairs has lower total weight so this path will be picked.

If on the other hand you want to go from the red tile to the blue tile, there is only path using at most 3 moves, namely taking the jump with total weight 102, so this path will be picked. There is another path taking the stairs but that path takes 5 total moves, so it is not considered because of the hard 3 moves constraint.

\$\endgroup\$
11
  • 1
    \$\begingroup\$ Something to watch out for here is performance; you'll trigger the algorithm to try outrageously long paths before accepting damage. But I support the idea in general \$\endgroup\$ Jan 23 at 13:00
  • 1
    \$\begingroup\$ @RichardTingle If I understood OP correctly, a unit has a fixed maximal number of moves per turn, 3 in the example. So it only needs to check paths with up to 3 moves. \$\endgroup\$
    – quarague
    Jan 23 at 13:36
  • \$\begingroup\$ Ah yes, you're right. Then yes, this feels like the best answer \$\endgroup\$ Jan 23 at 15:48
  • 2
    \$\begingroup\$ @BlueRaja-DannyPflughoeft I'm not sure I understand why you're saying this won't work? This approach makes a route that takes damage "appear" much longer. And Dijkstra will avoid a long route if it can. \$\endgroup\$ Jan 23 at 18:34
  • 1
    \$\begingroup\$ @BlueRaja-DannyPflughoeft The point of the weights is to change the distance used in the algorithm. The paths that takes damages is much longer than the one that doesn't because of the weights. You don't need to remember multiple shortest paths and pick the correct one, the weights make it so that the path with damage is much longer. \$\endgroup\$
    – quarague
    Jan 23 at 18:47
0
\$\begingroup\$

If the only damage concern (or the primary) is fall damage from a height, adding that Av (vertical axis) to the calculation with an exponential component can help.

For instance, let's say your normal movements have a weight from 1-3 (maybe depending on terrain). If you set any vertical movement to Xv (spaces vertical) squared * 10, you get an increasingly non-preferred path. So one vertical is 1^2 * 10 = 10. A two vertical unit drop is 2^2 * 10 = 40 - a significantly larger impact to the path budget. A three vertical unit drop is 3^2 * 10 = 90. By using an exponentially increasing value, it will still prefer LESS damaging paths.

That exponent can be made larger if the budget is increased because the movement space is large. For instance, you don't want the NPC to take the damaging path that includes 3 vertical unit drop because there's a walkable path that is more units, but still preferred. In that instance, perhaps you use Xv^3 or even Xv^4 and play around with your base movement cost and your overall budget until it "fits".

\$\endgroup\$
7
  • 1
    \$\begingroup\$ the problem is that im trying to score tiles by fall damage taken, as well as keeping the path under a specific movement amount, there is already an answer suggesting pretty much the same thing as here, with comments discussing why it doesn't work, which seem to be accurate since it doesn't work when i try this method. \$\endgroup\$
    – graveyard
    Jan 24 at 17:58
  • \$\begingroup\$ Ah I see - this wouldn't work with an unmodified Dijkstra. This could potentially work with some form of A*. But it sounds like to get what you want, you aren't going to be able to use an unmodified Dijkstra anyhow. There are some differences between what I'm suggesting and what quarague suggested, though. I do not recommend increasing the number of steps/moves it takes. And I definitely don't recommend multiple passes as the other answer suggested - or at least not in serial. Exponential weighting takes amount of damage into consideration without arbitrary costs. \$\endgroup\$ Jan 24 at 20:46
  • \$\begingroup\$ Of note - both answers WILL work. If they fail to work, it's a code logic issue. A basic Dijkstra shouldn't have branching paths because it can't (as noted elsewhere) "remember" multiple acceptable paths. But again, you won't be able to do what you want with a raw Dijkstra anyway, so... you'll have to work around that. \$\endgroup\$ Jan 24 at 20:48
  • \$\begingroup\$ I know it can't be an unmodified dijkstra's, I was hoping for suggestions on specifically how to modify it to get what I need with this question. the scoring is the easy part \$\endgroup\$
    – graveyard
    Jan 24 at 20:57
  • \$\begingroup\$ One thing you note is that it works with a different max movement (or that was my understanding: 3 vs 4). What that tells me is that you're skipping when cost is exceeded, but not retroflecting when two paths contain the same cost. Sounds like it's following one of, but not all of, next paths that have the same cost associated. \$\endgroup\$ Jan 24 at 21:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .