Important notice regarding A* implementation

[Port]

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/10469301
Requires main.cs, lib/Array.cs and lib/HeapQueue.cs from https://github.com/portify/types

I'm going to be doing my own testing as soon as I have the chance to.

[Ad Bot]

[Port]

Example implementation of the heuristic (egh, need to get rid of the getWord calls though):

function manhattanDistance(%a, %b)
{
  return
    mAbs(getWord(%b, 0) - getWord(%a, 0)) +
    mAbs(getWord(%b, 1) - getWord(%a, 1)) +
    mAbs(getWord(%b, 2) - getWord(%a, 2));
}

[Port]

Here's an (also untested, sadly) example implementation of NodeGroup and Node classes that works with this:
https://gist.github.com/portify/10531206

[Port]

I ran a bit of simple testing on a network of 488 nodes with several zombies using this to find me, which had some very promising results. They were able to find both short and relatively long paths instantly with no noticeable impact on lag for clients, and this is with the iterative non-scheduled version.

[Port]

This version seems to work pretty much perfectly. The only current issue is scalability - having 10 bots repeatedly attempt to find paths to the other end of a really large build causes some pretty heavy lag, especially for the host. Remedying this isn't impossible though, and merely involves making a slightly scheduled-over-time version, or adding rate limiting globally.

[Greek2me]

Thanks for working on this.

This version seems to work pretty much perfectly. The only current issue is scalability - having 10 bots repeatedly attempt to find paths to the other end of a really large build causes some pretty heavy lag, especially for the host. Remedying this isn't impossible though, and merely involves making a slightly scheduled-over-time version, or adding rate limiting globally.

I worked around this problem by caching and then re-using paths. It'll run a little slowly at first but after that I don't have to calculate the paths again.

[Greek2me]

Actually I made similar modifications to Slayer's implementation a while ago.

https://bitbucket.org/Greek2me/slayer/src/3c5658351c11197b39d72f864a7517307f6a606f/server/support/Support_Pathing/?at=dev

Do you notice anything that I missed?

[Port]

Do you notice anything that I missed?

Compare:

     %score = %g[%node] + vectorDist(%node.position, %neighbor.position);
 
      if (%g[%neighbor] $= "" || %score < %g[%neighbor])
      {
        %parent[%neighbor] = %node;
 
        if (%h[%neighbor] $= "") // get rid of this function call
          %h[%neighbor] = call(%heuristic, %neighbor.position, %end.position);
 
        %g[%neighbor] = %score;
 
        if (%heap.contains(%neighbor))
          %heap.updateScore(%neighbor, %score + %h[%neighbor]);
        else
          %heap.push(%neighbor, %score + %h[%neighbor]);
      }

To:

         %this.from[%link] = %node;

         if (!%this.open.contains[%link]) {
            %this.score[%link] = %this.callHeuristic(%link.position, %this.b.position);
            %this.open.push(%link, %this.score[%link]);
         }

[RarwMuffinz]

Looks like this will come in handy, more than once!
 /Sticky