BFS() vs ReachableNodes(): what's the difference?

I’m a bit confused about the difference between the BFS() and ReachableNodes() functions in PathUtilities. I understand that ReachableNodes() uses DFS, but I’m mainly asking about the practical differences.

  1. The docs say BFS “returns all nodes within a specified node distance which can be reached from the seed node”. So the nodes returned by BFS are all reachable, just like those returned by ReachableNodes, right? And they’re sorted by path distance from the seed, not the euclidian distance, correct? So then is there any practical difference in which nodes are returned by either function, or the order they’re returned in?

  2. What’s the best way to get those path distances from the seed when calling BFS() or ReachableNodes()? If possible I’d rather not do a whole new asynchronous iteration calculating paths for each seed and result node.

  3. Slightly un-related, but can I use ListPools outside of runtime? Other pooling systems I’ve used have been restricted to runtime so I wanted to make sure. I’m doing all of this outside of runtime, and am basically baking data that AI agents will query in-game, so I need to be able to create ListPools and then use them at runtime.

Thanks!

Hi

  1. ReachableNodes returns all reachable nodes, not just the ones within a fixed distance. However it is true that if you set the max distance for BFS really high, then they will be essentially the same. However ReachableNodes will likely be a bit faster.

  2. This is not exposed at the moment I’m afraid. The BFS method keeps track of this internally using the map field, but it’s not returned.
    You could copy the BFS method (it’s pretty short) to your own code and make a version that also returns the map field.

  3. You cannot create a list during Unity edit mode and then use it in play mode. Unity reloads the whole runtime so it is not possible to keep anything. You will need to save the data in an asset or a file.

@aron_granberg Thanks so much for the detailed response, this is extremely helpful!

Your suggestion in #2 is what I was thinking of doing, I’ll go that route.

Regarding #3, All this code is running in a scriptable object, sorry for not clarifying that. For a similar process of baking data outside runtime, I used a serialized dictionary where the key was a NodeIndex and the value was an array of computed values. But as I’m doing more and more of these sorts of calculations in scriptable objects, I’m starting to get concerned about memory management. My test scene is pretty small but still has some 3,000 nodes. I’ve been thinking of switching to arrays and just making sure that the indexes match the NodeIndex values in the GridGraph. Since pooling is usually used to avoid the cost of instancing/creating objects at runtime, I was skeptical it would be useful anyway.

Thanks again!

1 Like