The previous version which has been used by various projects is
extremely inefficient (uses string manipulation for lists and
O(n) best node finding) and
outright wrong. It does not guaranteedly return the shortest path, however something
similar to the shortest path depending on the order of which neighbors are defined. This affects Slayer, ZAMB and several other projects.
I've written a new version which addresses all of these issues, however I haven't tested it yet. I was originally going to run it through some rigorous testing before posting this however as Slayer is going to officially release it's bots (which used that), I didn't really have time to do that. Feel free to test it as much as you want and please point out any issues you might find.
What you'll need to do differently if you used the old version:
- The findPath() method now takes a %heuristic argument. Pass the name of a function that takes two positions and returns an estimate of the distance (not vectorDist). A good example of this is Manhattan distance.
- Nodes are expected to have a neighbors field which refers to an Array object instance (or one which implements the same interface). Previously, this just expected linkCount and link[n] attributes.
- An Array object instance is now returned (or 0 on failure) rather than a space-separated list of nodes. Make sure to delete it when you're done with it.
Additionally, I can greatly recommend modifying the function however you want to address custom needs (different node weights, different neighbor lookup, etc.). However,
please name your version of the function differently to prevent overwriting.
Full code:
https://gist.github.com/portify/10469301Requires main.cs, lib/Array.cs and lib/HeapQueue.cs from
https://github.com/portify/typesI'm going to be doing my own testing as soon as I have the chance to.