Timeline for In a tile based game, with units that can move a specific amount per turn, how do i make my pathfinding avoid damage unless it is the only valid path?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 24, 2024 at 16:47 | comment | added | Richard Tingle | @JasonGoemaat if you say make damage equivalent to 10000 tiles of movement you have to allow your algorithm to not give up until it gets to loads more than 10000. And usually you'd set it to give up. So it may try an outrageously long path that normally it would not consider. In the specific example here this isn't relevant as was pointed out to me in an earlier reply. In the locked door case it would be allowed to give up | |
| Jan 24, 2024 at 15:56 | comment | added | Jason Goemaat | @RichardTingle how is performance any different than in the case say where there is a locked door and there is no path to the destination? | |
| Jan 24, 2024 at 11:34 | comment | added | Richard Tingle | @BlueRaja-DannyPflughoeft ah, I think I understand what you're saying. Because start-> end is possible without taking damage. Just not also while staying within the 3 move rule. Interesting, I still think this answer is a sensible starting point but as you say does need some modifications | |
| Jan 24, 2024 at 7:40 | comment | added | quarague | @BlueRaja-DannyPflughoeft You also need to check whether the absolute bound on the total number of moves is satisfied. Added an explanation in the answer. | |
| Jan 24, 2024 at 7:38 | history | edited | quarague | CC BY-SA 4.0 | more detailed explanation |
| Jan 23, 2024 at 23:46 | comment | added | BlueRaja - Danny Pflughoeft | @RichardTingle (and quarague) - Yes exactly, Dijkstra will avoid the long route. In OP's last example, if A = red, C = blue, and B = a tile between them, this algorithm will always take the stairs to get from A-->B, but in this example we want to take the jump. Dijkstra's cannot handle the situation where local optimality depends on global state (the exact distance to C), so this answer won't work. A modified version may work (although I'm not sure how), but as written this answer is wrong. | |
| Jan 23, 2024 at 18:47 | comment | added | quarague | @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. | |
| Jan 23, 2024 at 18:34 | comment | added | Richard Tingle | @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. | |
| Jan 23, 2024 at 18:29 | comment | added | BlueRaja - Danny Pflughoeft | -1 This answer was my first thought too, but it doesn't work. If the unit is going from A-->C and B is along the best path, Dijkstra's must first find the shortest path from A-->B. However there are two (or more) shortest paths - the short one that takes damage, and the longer one that doesn't. Which one we need to take depends on how far away C is. Dijkstra's has no way of remembering that multiple "shortest" paths exist. | |
| Jan 23, 2024 at 15:48 | comment | added | Richard Tingle | Ah yes, you're right. Then yes, this feels like the best answer | |
| Jan 23, 2024 at 13:36 | comment | added | quarague | @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. | |
| Jan 23, 2024 at 13:00 | comment | added | Richard Tingle | 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 | |
| S Jan 23, 2024 at 11:59 | review | First answers | |||
| Jan 23, 2024 at 14:43 | |||||
| S Jan 23, 2024 at 11:59 | history | answered | quarague | CC BY-SA 4.0 |