Just bought a pro version. After studying the algorithms (in the grid graph) I have a few questions.
1st. It seems that the “walkable” of each node is detected as if the agent can be placed in the center of this node. Further, we can walk from one node to another, if the second one is also walkable (I neglact climb and slope for now). But what to do with the situation I illustrated in the figure below? Both nodes A and B (gray squares) are walkable, but due to obstacles you cannot walk from A to B. The agent will think that he can pass and will stuck. Am I right or am I missing something?
2nd. Is it possible to limit the maximum length of desired path? For example I have a character in labyrinth. I want to let the pathfinder look for some very simple pathes but not the whole way from the beginning to the end (which exists). I need the follow behaviour: if player click somewhere - the pathfinding look for a way not longer than XXX. If he can reach the target - the agent moves (blue target in the figure below), else (orange target) - agent moves to the node, that is the closest to target, but not far from the agent.
3rd. How much memory will take the grid 1000x1000? I do not need height, slope or climb control.
For 1, the graph shouldn’t end up looking like that if you generate it with a character radius that matches your agent’s radius. If you have agents of different sizes, someone more knowledgeable needs to step in
If not, the path finding would need to find the shared edge of all triangle crossings, and make sure that edge has a minimum length - the length of your agent’s diameter. I haven’t dug through the code enough to figure out where you’d go about doing that.
For 2, I think you could make your own Path subclass. You could for example subclasss ABPath, and override CalculateStep so it refuses to traverse to nodes if the current combined length is over the threshold.
Grid graphs have a limited resolution. It won’t be able to represent things smaller than one node that well. I’d recommend that you make the diameter of your agent equal or smaller than the width of a node.
You might want to check out recast graphs which can represent the world with more precision and still use less memory.
For 2. Take a look at this thread: How to limit searched for path length
When using the approach in that thread the path will fail if it would have been too long. You can make it return the path to the best node instead by setting the path.calculatePartial field to true.
As for 3. A 1000x1000 grid graph uses on the order of a few hundred megabytes. I don’t have the exact numbers here unfortunately.
