Hi Aron,
I’m looking at doing some semi-advanced pathfinding. For example:
I just wanted to check, firstly are any of these things in your codebase and I missed them, or features you’re working on?
Secondly, is it cool basing them on your Pro version of the code (which I have purchased). If I come up with anything good I’m happy to show you.
DC
Hi
Influence maps are not directly pathfinding, so they are not included in the project. Support for penalties for walking on different nodes is included in the project.
An agent that doesn’t know the whole map to begin with is equivalent to treating the map as walkable and then updating the map as more information is known, here is a video using the A* Pathfinding System: https://www.youtube.com/watch?v=6HcMYCS08XQ
Hierarchical pathfinding is not included right now, but I have an alpha version of a quadtree graph in my dev version. Hierarchical can however be emulated using one detailed graph and a point graph as the hierarchical level.
Lazy pathfinding based on the hierarchy is of course not included since the above is not included.
One interesting thing I am working on right now is heuristic optimization.
Basically you select a few pivot nodes on the map and find the cost from those nodes to all other nodes. That information can be used to calculated high quality heuristics which can speed up pathfinding by an order of magnitude ( the speedup varies greatly, but I have tests which show more than an order of magnitude speedup ).
Sure, you can do whatever experimentation you want with the pro version.
I’d be very happy to know about what you come up with.
Thanks for the update! Both the quadtree and the heuristic sound cool.
I forgot to ask, does the system support unconventional edge types, e.g. teleporters? I would think they would require a different heuristic function because they are by nature non-Euclidean. Looking at the code I was considering using a delegate to calculate the H function - it would allow flexibility and may also speed up the inner loop because you wouldn’t need to switch every time.
I suspect that graph simplification may give nicer results than quadtree. A pure graph algorithm would probably handle unusual edge types like teleporting better. It could also suggest high quality nodes for your heuristic approach.
Hi
If teleporters exist, you cannot use a normal distance based heuristic function. However you could use the kind of heuristic optimization that I am developing since those rely on the true distance to every node instead of the distance between them.
A delegate would be slower than a switch I think. A delegate needs to evaluate some if statements as well just to invoke the method. The switch statement wouldn’t be very slow because there are basically only three if statements it needs to check and it will be extremely well predicted. If the jit is smart it will build a tiny lookup table and jump to the correct position with only two conditionals (which will be extremely well predicted as well).
But do implement it and profile if you think it is worth doing.
Okay, sounds like we’re thinking roughly the same thing about teleporting.
I had the urge to check it earlier in the day - timings for switch vs delegate were hard to separate for high numbers of iterations, at least in .NET 4.0. Not sure if the same applies for Mono. So… no big gains to be made, but likely no big losses for custom heuristics either.
Unrelatedly, a short time ago the forum was down, and I was seeing a setup page which I doubt that I was meant to see. It may have been some maintenance thing, but maybe something to watch out for security-wise. I have a screenshot if it’s relevant.
Unrelatedly, a short time ago the forum was down, and I was seeing a setup page which I doubt that I was meant to see. It may have been some maintenance thing, but maybe something to watch out for security-wise. I have a screenshot if it's relevant.
Yeah, I just upgraded to a newer version of the forum software and happened to leave out the config file for a few minutes, so a configuration dialog was shown.
The upgrade seems to have gone through correctly except that some posts have been reordered. Maybe the timezone settings have been changed or something, I will have to investigate.
If I wanted to add extra attributes to nodes, for example multiple costs to weight time cost vs effort cost, do you have any suggestions on the best approach? I’m not keen to add properties to your base objects as they wouldn’t apply to many situations, and would just bloat memory.
Hi
You could extend a node class using
public class MyGridNode : GridNode { public int myExtraStuff; }
You would also need to override the GridGraph to change the type of node it creates (assuming you are using a GridGraph) from GridNode to MyGridNode.
I have been thinking about adding a virtual CreateNode method on each graph type, that would allow you to only override a single tiny method to change the type of node a graph creates.
Okay, that sounds sensible. Extend your classes and use a factory pattern or similar to create the nodes.
One more question - given that I’m working with Heuristic functions, is there any sort of debug available, e.g. gizmos to show searched nodes, or just data you can access programmatically on the number of nodes searched etc?
Yes, if you go to A* Inspector -> Settings -> Debug you will find “Path Debug Mode” which you can set to show e.g the G score. You might need to adjust the range for it (i.e what G score will be completely red).
You can enable “Show Search Tree” to from each node, only draw a connection to the parent node in the search.
I suggest that you disable multithreading while testing this since otherwise some paths might not be shown since multiple paths can be calculated at the same time.