I’m running a very modest graph. Approx 25x25 nodes in a grid. It’s a cube based game with one node per cube. Think something like Minecraft but with no overhangs (all blocks fall so the gameplay only has to care about the surface).
My first challenge is to find all reachable nodes within a certain path length of the character.
My initial approach was to use a multitargetpath and pass it a list of all possible positions, then filter out the ones that don’t return a valid path or are too long. This is slow and kinda dumb, and also doesn’t always return the shortest path to each node (the algorithm seems to like to follow the search tree even if another path would be faster). Should I be looking at something like PathUtilities.BFS and doing a second distance calculation on each path? FloodPath?
A second semi-related problem is that I’d like to add hazards that the units will path around if possible, but will walk through if necessary to get to the target node. Right now I’m doing that by setting the hazard nodes to have a very high penalty then running two pathfinding steps and removing all the penalties for the second step. That gives a list of paths avoiding hazards and a second list that walks through them and we can combine them to get the final movement list. Is there something I could do with tags or rules to do this calculation in a single step?
Hahaha nothing better than asking a question and being like “man how the hell do I do this?” then having that “Oh.” moment not long after.
So I think this is the expected way to do this- specifically with the tags and penalties, but I think we can cut it down to a single pathfinding call- what’s your goal for this? Did you want them to randomly choose to go through it or not? Go through the obstacle at a certain distance? Let me know your ideal situation and I’ll help how I can
You don’t need to remove all penalties/tags before running the other search. If you use tags, you can set the cost of each tag per path request, and if you need full control you can use the ITraversalProvider interface (see docs).
The unit start at A, and has a max movement of 5 tiles. It has to move through a hazard to get to B (because B is a hazard square), but it avoids the hazard as much as possible. It can avoid the hazard to get to C so paths around it. It has to go through two hazard squares to get to D.
E and F just to demonstrate that the unit will take a longer path even if a shorter hazard path is available.
For UI purposes we also need to know whether a path involves a hazard, ideally without having to do an additional pathfinding call.
e: to be clear on the output - I’m looking for a list of “squares I can get to without hazards” and an additional list of “squares I can get to if I’m willing to go through a hazard”. Right now two passes with ConstantPath works well but might be inefficient, I dunno.
