Flash pathfinding, again

Walk this wayAfter tons of help and suggestions by the critical eyes of tonypa at a GotoAndPlay forum thread, my original pathfinding algorithm has been optimized quite a bit and published at GotoAndPlay’s article/prototype library. The source for that Advance Wars-based map has also been published here; I forgot to do that before.

There has been quite a discussion on the subject on GotoAndPlay’s forum, and several tests done by tonypa comparing different types of pathfinding scripts. That’s some interesting stuff for people who’s looking for a way to use pathfinding routines in Flash games. Haha! Got it? Looking for a way. Gosh, I’m so funny.

  • I found an implementation for your ALLOW_DIAGONAL_CORNERING flag in the findPath function. You just have to add :
    && (ALLOW_DIAGONAL_CORNERING || j == nowY || k == nowX || (map[j][nowX] != 0 && map[nowY][k] != 0)) in your condition ….

    C ya 😉


  • And I forgot to thank you for your great path finder!!! I created one by myself with my own classes, and your source code helped me to understand the algorithm …

    So, thanks a lot again !!! 😀


  • zeh

    Thanks for that, LAlex. Like I told you on the gotoandplay forums, I’ll make a new version of the pathfinder soon and I will be sure to take your help into account.

  • larsman

    hi guys,
    i don’t know if you are still working on this topic but…
    i made a binary heap to keep track of the nodes in the open list.

    it uses the array ol as an open list and the nodes are object (with actually only one parameter f)

    the code is:

    // — add to open list
    enqueue= function( n ) {
    // add node to open list
    ol.push( { f: n } );

    // get pointer to new node
    var p= ol.length – 1;

    // put new node to correct position
    while( p ) {
    var pp= int( p >> 1 );
    if( ol[ p ].f = ol[ q ].f )
    pp= q;
    if( ol[ pp ].f >= ol[ q + 1 ].f )
    pp= q + 1;
    // only one child exists
    } else if( q = ol[ q ].f )
    pp= q;

    // parent is

    i made some tests against the simple search you use and is is faster when there are 40 or more elements in the open list.

    hope it helps


  • larsman

    hi again,

    sorry the code got messed up.
    you can find it here: