I’m using a grid graph with blocking nodes mechanics (basically a slightly modified version of CircuitBoardExample) in order to achieve chase behavior but with all chasers separated from each other. The idea is to block a couple of the most far from start point nodes that were part of any calculated path in the current cycle, plus block each node that is occupied by any unit that is static.
The entire mechanic works well [enough] in most cases, but when the target is located in an area that is cut off from the rest of the graph (by blocked nodes), the game freezes. I assume that it’s the effect of processing entire graph due to being unable to reach destination node. So my question is, is there any mechanics that could prevent such behavior?
The other approach I’m thinking about is applying penalties for each calculated path and then discarding all paths that contain any node with a penalty. I haven’t tested this approach yet, but I’m wondering if such frequent modifications to graph are a good idea.
Btw. I’m currently using the free version (4.2.8) of the plug-in.
Are you sure it is the pathfinding code that freezes? It is not your script?
In those cases the pathfinding thread would have to search through all reachable nodes, but unless you have an enormous graph it shouldn’t take that long.
Ok, first of all I’m testing the mechanics conception on a 100x100 square grid. For such set up, with one target and one “pathfinding agent” calculating path takes 300+ms (screen included). Path refresh rate that I use is 0.25s (it’s my internal thing, not refresh included in the plugin code), so technically freezing is due to these two values coming together.
I was thinking, maybe I messed something up in my implementation (I’m not using Seeker class, just fetching path and pushing it to my movement system) but after testing various cases on one of the scenes included as examples, the values I get are more or less similar (processing entire 100x100 grid takes at least 270ms).
I assume, this means that problem I’m facing is related to the limitation of the technology.
P.S. Interesting thing is that when you use multiple smaller graphs instead of one huge, the time of calculating path to “normal” nodes goes up, but for cut off (via ITraversalProvider) nodes it’s down a lot.
Edit: Talking about some mechanics that would help to prevent some degree behavior mentioned in this thread, I was thinking about some kind of limitation on amount of processed nodes (once it’s reached, processing could return path to the best, found so far node).
This is unfortunately hard to avoid. When targeting a node that only the ITraversalProvider says it cannot reach it will have to search every possible node because any node could have a connection to the target node.
Searching a 100x100 grid (10000 nodes) is usually not that slow though. I suspect that the ITraversalProvider that you use slows things down quite a lot. You may want to see if you can optimize it.
Also, you are using the BlockUntilCalculated method. This will prevent the paths from being calculated in a separate thread. If you don’t use it you will be able to calculate the paths asynchronously without a freeze. See https://arongranberg.com/astar/docs/callingpathfinding.html
I finally took a look at pathfinding code and figured out that kind of limitation mechanic I was thinking about (and mentioned in the previous post) already is present (ABPath - searchedNodes counter and throwing error when it reaches a too hight value).
So I tempered a little bit with the asset code and ended up with something that is not “real pathfinding” anymore (I’m calculating only a bunch of nodes, so “path” I get is always few nodes long - it’s not necessarily optimal, always partial path, plus it can get itself blocked inside a U style obstacle) but the outcome is decent enough for me (for sure, so far, the best from what I was playing with).
Such approach is quite performant as well (due to very small amounts of nodes being processed) - 10 units need around 1-2 ms to recalculate their paths, but I’m still wondering if multi threading in the pro version will boost calculations even more (I’m still using blocking calculations; I’m also aware of optimization by disabling some code via compiler directives in pro) or maybe it’s unusable in this specific case.