Getting BFS Routes

I’m writing a turn based tactical game, where each unit has a limited movement distance each turn. I’m working on the enemy AI at the moment.

I’m using Pathfinding.PathUtilities.BFS at the moment to get all the squares they can reach that turn, and then do some AI thingies to determine which is the best square to move to.

However, some tiles are going to have environmental or other dangers, and to calculate that, I need to know the route they’re going to take, so I can modify the decision accordingly .

I don’t particularly want to loop through the results of BFS and generate fresh routes for each, because I’m guessing that’s going to be very expensive for nothing - so is there a better way of doing this?

Hi

You could use the MultiTargetPath possibly.
See also https://arongranberg.com/astar/docs/seeker.html#StartMultiTargetPath

Okay, let me explain better.

Each Unit takes it’s turn. For each unit - I get every single tile they can reach (Using BFS), and then calculate some weights to determine which is the best tile to be in (for instance - being able to attack an enemy or whatever). To clarify - I will only choose ONE tile, but I need to calculate all of them to take the best decision.

Now, I also need to determine the route to reach that tile - but if they can reach 50 tiles in one turn, I’d have to generate 50 routes which seems excessive.

So my question is - if I have the results of BFS - can I somehow determine the route they’d take to reach that tile?

Okay. I see.
Currently the BFS does not save that information. However if you modify the BFS method slightly you could get that.

  1. Add a new variable called currentNode, make sure to set currentNode = n inside the while loop.
  2. Add a new variable called parents (of type Dictionary<GraphNode, GraphNode>)
  3. In the callbacks, every time something is added to the map, set parents[node] = currentNode

Make sure to output the parents dictionary as well. Now you can trace the whole path back to the starting point by using the parents dictionary. If you have a node A, the previous node in the path is parents[A], the one before that is parents[parents[A]] etc. Until you get to the start node.

1 Like

Looks simple enough, I’ll give it a try.

Thanks :slight_smile:

1 Like