Author Topic: A* Search Algorithm  (Read 4795 times)

Offline chaos

  • BFF
  • ***
  • Posts: 291
  • Job, school, social life, sleep. Pick 2.5.
    • View Profile
    • Lost Souls
A* Search Algorithm
« on: May 14, 2007, 06:29:17 PM »
Greetings; Chaos of Lost Souls (lostsouls.org) here.  I recently had reason to make an as-general-as-possible module implementing the A* search algorithm (best known as a pretty much optimal pathfinding routine, if you're not familiar with it), and decided to make a public release of it.  Since it exceeds the maximum message length for the forum, you can find it at http://lostsouls.org/grimoire_astar.  Any updates will appear there as well.  It was written under LDmud, so I'm quite interested in knowing about portability issues encountered with other drivers.  I attempted to make it completely mudlib-agnostic, but it's possible that some Lost Souls local flavor crept in, which I'd also like to know about if so.  Hope it helps someone out!

Offline Tricky

  • BFF
  • ***
  • Posts: 189
  • I like what I code and I code what I like!
    • View Profile
Re: A* Search Algorithm
« Reply #1 on: May 14, 2007, 07:04:45 PM »
 :D

You might want to check this thread out.

I recoded that very algorithm found in the LDMud distribution to use binary trees about 3 or so years ago to work on the H7 Avatar lib. Recently I recoded it to work under MudOS and the LPUni Lib, although I suspect is will work under any other mudlib (using MudOS) with minor changes.

I'll have a look-see at your code to see how you tackled it.  8)

Tricky

Offline cratylus

  • Your favorite and best
  • Administrator
  • ***
  • Posts: 1020
  • Cratylus@Dead Souls <ds> np
    • View Profile
    • About Cratylus
Re: A* Search Algorithm
« Reply #2 on: May 14, 2007, 07:54:17 PM »
Unusually large posts now are accepted.

-Crat

Offline chaos

  • BFF
  • ***
  • Posts: 291
  • Job, school, social life, sleep. Pick 2.5.
    • View Profile
    • Lost Souls
Re: A* Search Algorithm
« Reply #3 on: May 14, 2007, 09:44:23 PM »
Ah, thanks.  I tried to search for posts like that on here, but I was unable to come up with a variant on A* that didn't just wind up searching on the letter A.  Should've used "astar".

Looking at your implementation, my immediate thought is that I need to add support for varying costs.  Probably attaching the cost to the edge rather than the vertex.

I'd certainly like to hear any thoughts you have about how I did it.

Embedding the code since the forum will accept it now:

Code: [Select]
// A* Search Algorithm Module
//
// Provides a fairly general implementation of the A* search algorithm that can be configured
// to search arbitrary problem spaces.  A* search is a modification of best-first search that
// assigns a cost to each potential path, generally based on coordinate-space distance from
// the path endpoint to the goal, and searches the lowest-cost paths preferentially.  It is
// commonly regarded as the best general algorithm for pathfinding within a Cartesian space.
//
// You may do anything you like with this code so long as these two lines, the eight preceding
// and the two following are retained intact.
//
// 2007-05-11, Chaos of Lost Souls, http://www.lostsouls.org/

// In order to work properly with A* search, your situation needs to be describable in terms
// of a few crucial concepts.
//
// The first concept is 'loci': there need to be things resembling locations, states,
// what-have-you that can be represented in some consistent fashion.  One common kind of locus
// is a point in a Cartesian coordinate space, an X, Y or X, Y, Z location; another is a MUD
// room filename.  You should be able to generally figure out some sort of distance between
// two loci without any other information, which a Cartesian space works well for.  It's okay
// if there are some loci you can find a distance for and some you can't, as with a MUD area
// that has some rooms on a Cartesian grid and some off of it -- the algorithm is set up to
// deal with that -- but if you can't find a distance for anything, you're not getting any
// benefit out of the A* algorithm and may as well just do an exhaustive search.
//
// The second concept is 'deltas': there need to be quantifiable ways to move between adjacent
// loci.  These might be simply lists of offsets in the coordinate space, e.g. ({ 0, 1, 0 }),
// or they may be directions like "north" or commands like "enter portal".
//
// The information you *must* be able to provide the algorithm in order for it to function is
// the answers to the questions "which loci are adjacent to this locus and how do I get to
// them from here?" and "how far is it from this locus to this one?"
//
// A sample implementation might look like this:
//
// inherit "/mod/algorithm/astar";           // this module
//
// #define Map_Min_X    1
// #define Map_Max_X    20
// #define Map_Min_Y    1
// #define Map_Max_Y    10
// #define X            0
// #define Y            1
//
// // Neighbors rule produces loci and deltas for the points adjacent to us.
//
// mixed array astar_neighbors_rule(int array locus) {
//     mixed array out = ({});
//     if(locus[X] > Map_Min_X)
//         out += ({({
//             ({ locus[X] - 1, locus[Y] }), // Adjacent locus
//             ({ -1, 0 }),                  // Delta to adjacent locus
//         })});
//     if(locus[X] < Map_Max_X)
//         out += ({({
//             ({ locus[X] + 1, locus[Y] }), // Adjacent locus
//             ({ 1, 0 }),                   // Delta to adjacent locus
//         })});
//     if(locus[Y] > Map_Min_Y)
//         out += ({({
//             ({ locus[X], locus[Y] - 1 }), // Adjacent locus
//             ({ 0, -1 }),                  // Delta to adjacent locus
//         })});
//     if(locus[Y] < Map_Max_Y)
//         out += ({({
//             ({ locus[X], locus[Y] + 1 }), // Adjacent locus
//             ({ 0, 1 }),                   // Delta to adjacent locus
//         })});
//     return out;
// }
//
// // Distance rule calculates the distance between two points.  Using the Pythagorean
// // Theorem, yo.
//
// float astar_distance_rule(int array a, int array b) {
//     int x_dist = a[X] - b[X];
//     int y_dist = a[Y] - b[Y];
//     return sqrt(x_dist * x_dist + y_dist * y_dist);
// }
//
// // Locus key rule gives us a unique value correspoding to a locus that can be reliably
// // used as a mapping key.  Since we're using arbitrary two-element arrays as loci, we
// // need to use this so the algorithm can tell where it's been.
//
// int astar_locus_key_rule(int array locus) {
//     return (locus[X] << 16) | locus[Y];
// }
//
// // Run limit rule tells the algorithm when to stop running and continue on a call_out.
//
// status astar_run_limit_rule(descriptor from, descriptor to, closure validate,
//         closure validate_delta, closure callback, mixed array callback_extra,
//         mixed array paths, mapping visited) {
//     return get_eval_cost() < __MAX_EVAL_COST__ / 2;
// }
//
// // Set up the A* module.
//
// void create() {
//     set_astar_neighbors_rule(#'astar_neighbors_rule);
//     set_astar_distance_rule(#'astar_distance_rule);
//     set_astar_locus_key_rule(#'astar_locus_key_rule);
//     set_astar_run_limit_rule(#'astar_run_limit_rule);
//     set_astar_caching(1);
// }
//
// // This is our callback when pathfinding completes (for better or worse); it displays
// // the path to this_player().
//
// void end_random_pathfind(mixed array path) {
//     if(path) {
//         mixed array loci = path[Astar_Path_Loci];
//         write("Path from " + loci[0][X] + "," + loci[0][Y] + " to " + loci[<1][X] +
//             "," + loci[<1][Y] + ":\n");
//         foreach(mixed array locus : loci)
//             write("    " + locus[X] + "," + locus[Y] + "\n");
//     } else {
//         write("Cannot find path.\n");
//     }
// }
//
// // Picks two random points in our coordinate space and pathfinds between them.
//
// void start_random_pathfind() {
//     int array start = ({ Map_Min_X + random(Map_Max_X - Map_Min_X + 1),
//         Map_Min_Y + random(Map_Max_Y - Map_Min_Y + 1) });
//     int array target = ({ Map_Min_X + random(Map_Max_X - Map_Min_X + 1),
//         Map_Min_Y + random(Map_Max_Y - Map_Min_Y + 1) });
//     astar_find_path(start, target, 0, #'end_random_pathfind);
// }

// Macros for the data structure tracking path information; for implementations to
// work effectively and maintainably with results from this code you will generally
// want to place these macros in an appropriate header file, e.g. astar.h

// The list of loci making up the path.
#define Astar_Path_Loci                        0
// The deltas between loci in the path.  Each delta in the list represents the
// change necessary to move from the locus in the corresponding position in the
// list of loci to the next locus.
#define Astar_Path_Deltas                      1
// The path's distance from its target.
#define Astar_Path_Distance                    2
// The cost of the path: its distance plus its length.
#define Astar_Path_Cost                        3

#define Astar_Path_Fields                      4

// SECTION: Instance configuration
//
// These configuration functions are used by an application of the astar module to
// configure its behavior and give it the methods it needs to retrieve the information
// it works with.

// Neighbors rule
//
// The neighbors rule is used to retrieve all loci adjacent to a specified one and the
// deltas used to reach them.  It is called with one argument, the locus to retrieve
// neighbors for.  The return value needed is an array of two-element arrays in which
// the first element is a locus and the second element is the delta used to reach it.
// Required.

private closure neighbors_rule;

void set_astar_neighbors_rule(closure val) {
    neighbors_rule = val;
}

closure query_astar_neighbors_rule() {
    return neighbors_rule;
}

// Distance rule
//
// The distance rule is used to determine the distance between loci.  It is called
// with two arguments, the loci to find the distance between.  The return value needed
// is a int/float value indicating the distance, or -1 if the distance cannot be
// determined.  Required.

private closure distance_rule;

void set_astar_distance_rule(closure val) {
    distance_rule = val;
}

closure query_astar_distance_rule() {
    return distance_rule;
}

// Locus rule
//
// The locus rule is used to convert the representation of a locus into the form you
// want.  If, for instance, the pathfinder routine might wind up called with a string
// filename or an object for its loci, and you want to use the filename for how you're
// going to work with loci internally, you can define this hook in order to perform
// the conversion.  The return value needed is the final desired representation for
// the locus.  Optional.

private closure locus_rule;

void set_astar_locus_rule(closure val) {
    locus_rule = val;
}

closure query_astar_locus_rule() {
    return locus_rule;
}

// Locus key rule
//
// The locus key rule is used to represent a locus for purposes of checking whether
// it has been visited.  You will usually need to use this if your loci as normally
// represented as pointers (arrays or mappings), unless the pointers for a given locus
// can be guaranteed to always be the same.  Otherwise, the system can't tell which
// loci it's visited.  The return value needed is the "flat" representation to use for
// the locus, most typically a string or int.  Optional.

private closure locus_key_rule;

void set_astar_locus_key_rule(closure val) {
    locus_key_rule = val;
}

closure query_astar_locus_key_rule() {
    return locus_key_rule;
}

// Run limit rule
//
// The run limit rule is used to check whether the algorithm has run for too long and
// should be rescheduled or aborted.  It is called with the same argument list as
// astar_find_path() is called with (starting locus, target locus, locus validation
// rule, callback, array of extra callback arguments), plus an array of the current
// paths being examined, a mapping of the locus keys for the loci that have been
// visited, and an integer representing how many times the pathfinding has continued
// via call_out.  The return value needed is any true value if the run limit has been
// exceeded, false if not.  Optional.

private closure run_limit_rule;

void set_astar_run_limit_rule(closure val) {
    run_limit_rule = val;
}

closure query_astar_run_limit_rule() {
    return run_limit_rule;
}

// Caching
//
// The cache retains the pathfinding results that have been obtained so they do not
// have to be recalculated after being requested once, at the cost of some memory usage.
// One would use set_astar_caching(1) in the instance to turn on caching.

private mapping cache;

void set_astar_caching(status val) {
    if(val)
        cache = ([]);
    else
        cache = 0;
}

status query_astar_caching() {
    return cache && 1;
}

// Validate key rule
//
// The validate key rule is only meaningful if you have caching turned on.  It can be
// used to provide mapping-key-usable representations of 'validate' closures passed to
// astar_find_path().  A common way to construct the rule is to return the to_string()
// of the closure; this implies that a particular 'validate' closure will always return
// the same way for a particular locus.  This is used for caching pathfinding results
// with 'validate' rules.  This means that if you cannot guarantee consistent results
// for a 'validate' function, you should return 0 so that the system knows not to cache
// the path using it.  If this rule is not defined, paths generated with 'validate'
// rules will not be cached.  The validate key rule is called with one argument, the
// 'validate' rule, and should return the representation to use, usually a string or
// int.  Optional.

private closure validate_key_rule;

void set_astar_validate_key_rule(closure val) {
    validate_key_rule = val;
}

closure query_astar_validate_key_rule() {
    return validate_key_rule;
}

// SECTION: Internal support functions
//
// These are functions used by the A* module.  Instances do not need to interact with them.

// astar_path_sort()
//
// Sorting function for paths, based on their cost.  Sorts low-cost paths to the end of
// the list.

private int astar_path_sort(mixed array a, mixed array b) {
    float cost_a = a[Astar_Path_Cost];
    float cost_b = b[Astar_Path_Cost];
    if(cost_a > cost_b)
        return -1;
    else if(cost_a < cost_b)
        return 1;
    else
        return 0;
}

// astar_distance()
//
// Distance retrieval process.  The distance rule is allowed to return -1 if, for whatever
// reason, it doesn't know how far it is between loci; the cost of the new path is set to be
// one greater than the cost of the path it extends.

private float astar_distance(mixed from, mixed to, mixed array path) {
    mixed res = funcall(distance_rule, from, to, path[Astar_Path_Loci],
        path[Astar_Path_Deltas]);
    if(res == -1)
        return path[Astar_Path_Distance] + 1.0;
    else
        return res;
}

// astar_key()
//
// Locus key retrieval process.  Finds the representation to use for the locus in checking
// visited status.

private mixed astar_key(mixed locus) {
    return locus_key_rule ? funcall(locus_key_rule, locus) : locus;
}

// astar_cached_path()
//
// Cached path retrieval.

private mixed astar_cached_path(mixed from, mixed to, closure validate) {
    if(!cache)
        return 0;
    mixed validate_key = validate && validate_key_rule &&
        funcall(validate_key_rule, validate);
    if(!validate || validate_key) {
        mapping validate_cache = cache[validate_key];
        if(validate_cache) {
            mixed from_key = astar_key(from);
            mapping from_cache = validate_cache[from_key];
            if(from_cache) {
                mixed to_key = astar_key(to);
                mixed path = from_cache[to_key];
                if(path)
                    return path;
            }
        }
    }
    return 0;
}

// astar_pathfinder()
//
// Performs the actual work of path calculation.  This is separated from astar_find_path(),
// below, so that it's call_out re-entrant.

private mixed astar_pathfinder(mixed from, mixed to, closure validate, closure callback,
        mixed array callback_extra, mixed array paths, mapping visited, int iteration) {
    if(iteration) {
        mixed path = astar_cached_path(from, to, validate);
        if(path) {
            if(path == -1)
                path = 0;
            if(callback)
                apply(callback, path, callback_extra);
            return path;
        }
    }
    mixed to_key = astar_key(to);
    for(;;) {
        if(run_limit_rule && funcall(run_limit_rule, from, to, validate, callback,
            callback_extra, paths, visited, iteration)) {
            if(callback)
                call_out(#'astar_pathfinder, 2, from, to, validate, callback,
                    callback_extra, paths, visited, iteration + 1);
            return 0;
        }
        mixed array extended = ({});
        // Sort the paths on their distance from the target; we only want to
        // deal with the closest paths out of the ones we have
        paths = sort_array(paths, #'astar_path_sort);
        // Get the cost of the best path on hand; we only want paths with this
        // cost
        float cost = paths[<1][Astar_Path_Cost];
        int ix;
        // Check for possible extensions on as many paths as we have that are
        // at our best cost
        for(ix = sizeof(paths) - 1; ix >= 0 &&
            paths[ix][Astar_Path_Cost] <= cost; ix--) {
            mixed path = paths[ix];
            mixed last_locus = path[Astar_Path_Loci][<1];
            // Retrieve the list of neighbor loci and deltas to reach them
            mixed array neighbors = funcall(neighbors_rule, last_locus);
            if(!pointerp(neighbors))
                raise_error("Invalid return value from neighbors rule");
            foreach(mixed array neighbor : neighbors) {
                mixed locus = neighbor[0];
                mixed delta = neighbor[1];
                // If we've already been here, never mind
                mixed key = astar_key(locus);
                if(visited[key])
                    continue;
                // Okay, then, now we've been here
                visited[key] = 1;
                // If we have a validation rule for loci, check against it
                if(validate && !funcall(validate, locus, delta, last_locus, from,
                    to, path))
                    continue;
                // Otherwise, it's a valid extension.  Assemble the extended path
                // with this locus added to it, and calculate the distance and cost
                mixed array ext_path = copy(path);
                ext_path[Astar_Path_Loci] += ({ locus });
                ext_path[Astar_Path_Deltas] += ({ delta });
                ext_path[Astar_Path_Distance] =
                    astar_distance(locus, to, path);
                ext_path[Astar_Path_Cost] =
                    ext_path[Astar_Path_Distance] +
                    sizeof(ext_path[Astar_Path_Loci]);
                // If the locus we just reached is the target, we're done
                if(key == to_key) {
                    if(callback)
                        apply(callback, ext_path, callback_extra);
                    if(cache) {
                        mixed validate_key = validate && validate_key_rule &&
                            funcall(validate_key_rule, validate);
                        if(!validate || validate_key) {
                            mapping validate_cache = cache[validate_key] ||= ([]);
                            mixed from_key = astar_key(from);
                            mapping from_cache = validate_cache[from_key] ||= ([]);
                            from_cache[to_key] = ext_path;
                        }
                    }
                    return ext_path;
                }
                // Keep track of the extended path
                extended += ({ ext_path });
            }
        }
        // Get rid of the paths that we extended, and add the newly extended paths
        // to our list
        paths = paths[0 .. ix] + extended;
        // If we no longer have any paths to examine, we're out of luck
        if(!sizeof(paths)) {
            if(callback)
                apply(callback, 0, callback_extra);
            if(cache) {
                mixed validate_key = validate && validate_key_rule &&
                    funcall(validate_key_rule, validate);
                if(!validate || validate_key) {
                    mapping validate_cache = cache[validate_key] ||= ([]);
                    mixed from_key = astar_key(from);
                    mapping from_cache = validate_cache[from_key] ||= ([]);
                    from_cache[to_key] = -1;
                }
            }
            return 0;
        }
    }
}

// SECTION: Operational interface

// astar_find_path()
//
// Performs pathfinding starting with the 'from' locus, searching for the 'to' locus.
//
// 'validate' can be used to provide a closure that checks whether a locus is valid to
// include in the path; it is called with arguments of the locus being examined, the
// delta to reach it, the previous locus in the path, the starting locus, the target
// locus, and the entire path so far.  It should return true if the locus being examined
// should be included in the path.
//
// 'callback' can be used to provide a closure to be called at the completion of
// pathfinding.  The first argument to it will be the path found, if pathfinding was
// successful, or 0 if no path could be found.  Providing a callback allows pathfinding
// to be carried out across call_outs; if no callback is provided, then pathfinding
// will execute until it reaches the run limit defined by the instance, if any, or it
// hits the eval limit.  With a callback, pathfinding runs until it reaches the run
// limit, then continues via call_out two seconds later, continuing in this fashion
// until a path is found or all possible paths have been searched.
//
// Any additional arguments sent after 'callback' become subsequent arguments to be
// passed to 'callback' after the path argument.
//
// The return value is an A* path structure (as defined by the Astar_Path_* macros
// above) if pathfinding was successful immediately, or 0 if either the run limit was
// encountered or pathfinding failed.

varargs mixed astar_find_path(mixed from, mixed to, closure validate, closure callback,
    varargs mixed array callback_extra) {
    // Constrain our representation of our 'from' and 'to' loci
    if(locus_rule) {
        from = funcall(locus_rule, from);
        to = funcall(locus_rule, to);
    }
    mixed path = astar_cached_path(from, to, validate);
    if(path) {
        if(path == -1)
            path = 0;
        if(callback)
            apply(callback, path, callback_extra);
        return path;
    }
    // Set up our starting point based on the 'from' locus
    mixed array start = allocate(Astar_Path_Fields);
    start[Astar_Path_Loci] = ({ from });
    start[Astar_Path_Deltas] = ({});
    start[Astar_Path_Distance] = astar_distance(from, to, start);
    // Starting point becomes our path list, mapping to track where we've
    // visited starts out populated with starting locus
    return astar_pathfinder(from, to, validate, callback, callback_extra, ({ start }),
        ([ astar_key(from) : 1 ]), 0);
}

// astar_clear_cache()
//
// Clears out the contents of the cache.  This can be useful for allowing caching in
// spaces that you otherwise couldn't use caching with because some sort of dynamicism
// in them (changing exits, shifting graph connectivity, etc.) would invalidate cached
// paths.  Using this, you can call astar_clear_cache() when changes occur, so that no
// outdated paths will be returned.

void astar_clear_cache() {
    if(!cache)
        raise_error("astar_clear_cache() called with caching off");
    cache = ([]);
}

Offline chaos

  • BFF
  • ***
  • Posts: 291
  • Job, school, social life, sleep. Pick 2.5.
    • View Profile
    • Lost Souls
Re: A* Search Algorithm
« Reply #4 on: May 14, 2007, 11:08:55 PM »
Okay, I've added support for varying costs on deltas (edges) to my implementation.  Updated version at URL above, or:

Code: [Select]
// A* Search Algorithm Module
//
// Provides a fairly general implementation of the A* search algorithm that can be configured
// to search arbitrary problem spaces.  A* search is a modification of best-first search that
// assigns a cost to each potential path, generally based on coordinate-space distance from
// the path endpoint to the goal, and searches the lowest-cost paths preferentially.  It is
// commonly regarded as the best general algorithm for pathfinding within a Cartesian space.
//
// You may do anything you like with this code so long as these two lines, the eight preceding
// and the two following are retained intact.
//
// 2007-05-11, Chaos of Lost Souls, http://www.lostsouls.org/

// In order to work properly with A* search, your situation needs to be describable in terms
// of a few crucial concepts.
//
// The first concept is 'loci': there need to be things resembling locations, states,
// what-have-you that can be represented in some consistent fashion.  One common kind of locus
// is a point in a Cartesian coordinate space, an X, Y or X, Y, Z location; another is a MUD
// room filename.  You should be able to generally figure out some sort of distance between
// two loci without any other information, which a Cartesian space works well for.  It's okay
// if there are some loci you can find a distance for and some you can't, as with a MUD area
// that has some rooms on a Cartesian grid and some off of it -- the algorithm is set up to
// deal with that -- but if you can't find a distance for anything, you're not getting any
// benefit out of the A* algorithm and may as well just do an exhaustive search.
//
// The second concept is 'deltas': there need to be quantifiable ways to move between adjacent
// loci.  These might be simply lists of offsets in the coordinate space, e.g. ({ 0, 1, 0 }),
// or they may be directions like "north" or commands like "enter portal".
//
// The third concept is 'costs'.  Deltas have an associated cost; the lower the cost of the
// delta, the more desirable it is to use it.  This may represent relative difficulty of
// terrain, varying time delays between exits, etc.  If all deltas are equally desirable,
// just use 1 for their cost.
//
// The information you *must* be able to provide the algorithm in order for it to function is
// the answers to the questions "which loci are adjacent to this locus and how do I get to
// them from here?" and "how far is it from this locus to this one?"
//
// A sample implementation might look like this:
//
// inherit "/mod/algorithm/astar";           // this module
//
// #define Map_Min_X    1
// #define Map_Max_X    20
// #define Map_Min_Y    1
// #define Map_Max_Y    10
// #define X            0
// #define Y            1
//
// // Neighbors rule produces loci and deltas for the points adjacent to us.
//
// mixed array astar_neighbors_rule(int array locus) {
//     mixed array out = ({});
//     if(locus[X] > Map_Min_X)
//         out += ({({
//             ({ locus[X] - 1, locus[Y] }), // Adjacent locus
//             ({ -1, 0 }),                  // Delta to adjacent locus
//             1,                            // Cost of delta
//         })});
//     if(locus[X] < Map_Max_X)
//         out += ({({
//             ({ locus[X] + 1, locus[Y] }), // Adjacent locus
//             ({ 1, 0 }),                   // Delta to adjacent locus
//             1,                            // Cost of delta
//         })});
//     if(locus[Y] > Map_Min_Y)
//         out += ({({
//             ({ locus[X], locus[Y] - 1 }), // Adjacent locus
//             ({ 0, -1 }),                  // Delta to adjacent locus
//             1,                            // Cost of delta
//         })});
//     if(locus[Y] < Map_Max_Y)
//         out += ({({
//             ({ locus[X], locus[Y] + 1 }), // Adjacent locus
//             ({ 0, 1 }),                   // Delta to adjacent locus
//             1,                            // Cost of delta
//         })});
//     return out;
// }
//
// // Distance rule calculates the distance between two points.  Using the Pythagorean
// // Theorem, yo.
//
// float astar_distance_rule(int array a, int array b) {
//     int x_dist = a[X] - b[X];
//     int y_dist = a[Y] - b[Y];
//     return sqrt(x_dist * x_dist + y_dist * y_dist);
// }
//
// // Locus key rule gives us a unique value correspoding to a locus that can be reliably
// // used as a mapping key.  Since we're using arbitrary two-element arrays as loci, we
// // need to use this so the algorithm can tell where it's been.
//
// int astar_locus_key_rule(int array locus) {
//     return (locus[X] << 16) | locus[Y];
// }
//
// // Run limit rule tells the algorithm when to stop running and continue on a call_out.
//
// status astar_run_limit_rule(int array from, int array to, closure validate,
//         closure callback, mixed array extra, mixed array paths, mapping visited,
//         int iteration) {
//     return get_eval_cost() < __MAX_EVAL_COST__ / 2;
// }
//
// // Set up the A* module.
//
// void create() {
//     set_astar_neighbors_rule(#'astar_neighbors_rule);
//     set_astar_distance_rule(#'astar_distance_rule);
//     set_astar_locus_key_rule(#'astar_locus_key_rule);
//     set_astar_run_limit_rule(#'astar_run_limit_rule);
//     set_astar_caching(1);
// }
//
// // This is our callback when pathfinding completes (for better or worse); it displays
// // the path to this_player().
//
// void end_random_pathfind(mixed array path) {
//     if(path) {
//         mixed array loci = path[Astar_Path_Loci];
//         write("Path from " + loci[0][X] + "," + loci[0][Y] + " to " + loci[<1][X] +
//             "," + loci[<1][Y] + ":\n");
//         foreach(mixed array locus : loci)
//             write("    " + locus[X] + "," + locus[Y] + "\n");
//     } else {
//         write("Cannot find path.\n");
//     }
// }
//
// // Picks two random points in our coordinate space and pathfinds between them.
//
// void start_random_pathfind() {
//     int array start = ({ Map_Min_X + random(Map_Max_X - Map_Min_X + 1),
//         Map_Min_Y + random(Map_Max_Y - Map_Min_Y + 1) });
//     int array target = ({ Map_Min_X + random(Map_Max_X - Map_Min_X + 1),
//         Map_Min_Y + random(Map_Max_Y - Map_Min_Y + 1) });
//     astar_find_path(start, target, 0, #'end_random_pathfind);
// }

// Macros for the data structure tracking path information; for implementations to
// work effectively and maintainably with results from this code you will generally
// want to place these macros in an appropriate header file, e.g. astar.h

// The list of loci making up the path.
#define Astar_Path_Loci                        0
// The deltas between loci in the path.  Each delta in the list represents the
// change necessary to move from the locus in the corresponding position in the
// list of loci to the next locus.
#define Astar_Path_Deltas                      1
// The path's distance from its target.
#define Astar_Path_Distance                    2
// The cost of the path: its distance plus its length.
#define Astar_Path_Cost                        3

#define Astar_Path_Fields                      4

// SECTION: Instance configuration
//
// These configuration functions are used by an application of the astar module to
// configure its behavior and give it the methods it needs to retrieve the information
// it works with.

// Neighbors rule
//
// The neighbors rule is used to retrieve all loci adjacent to a specified one and the
// deltas used to reach them.  It is called with a first argument of the locus to
// retrieve neighbors for; any additional arguments are the extra arguments that
// astar_find_path() was called with.  The return value it should provide is an array
// of three-element arrays in which the first element is a locus, the second element
// is the delta used to reach it, and the third element is the cost of the delta.
// Required.

private closure neighbors_rule;

void set_astar_neighbors_rule(closure val) {
    neighbors_rule = val;
}

closure query_astar_neighbors_rule() {
    return neighbors_rule;
}

// Distance rule
//
// The distance rule is used to determine the distance between loci.  It is called
// with two arguments, the loci to find the distance between.  The return value needed
// is a int/float value indicating the distance, or -1 if the distance cannot be
// determined.  Required.

private closure distance_rule;

void set_astar_distance_rule(closure val) {
    distance_rule = val;
}

closure query_astar_distance_rule() {
    return distance_rule;
}

// Locus rule
//
// The locus rule is used to convert the representation of a locus into the form you
// want.  If, for instance, the pathfinder routine might wind up called with a string
// filename or an object for its loci, and you want to use the filename for how you're
// going to work with loci internally, you can define this hook in order to perform
// the conversion.  The return value needed is the final desired representation for
// the locus.  Optional.

private closure locus_rule;

void set_astar_locus_rule(closure val) {
    locus_rule = val;
}

closure query_astar_locus_rule() {
    return locus_rule;
}

// Locus key rule
//
// The locus key rule is used to represent a locus for purposes of checking whether
// it has been visited.  You will usually need to use this if your loci as normally
// represented as pointers (arrays or mappings), unless the pointers for a given locus
// can be guaranteed to always be the same.  Otherwise, the system can't tell which
// loci it's visited.  The return value needed is the "flat" representation to use for
// the locus, most typically a string or int.  Optional.

private closure locus_key_rule;

void set_astar_locus_key_rule(closure val) {
    locus_key_rule = val;
}

closure query_astar_locus_key_rule() {
    return locus_key_rule;
}

// Run limit rule
//
// The run limit rule is used to check whether the algorithm has run for too long and
// should be rescheduled or aborted.  It is called with the same argument list as
// astar_find_path() is called with (starting locus, target locus, locus validation
// rule, callback, array of extra callback arguments), plus an array of the current
// paths being examined, a mapping of the locus keys for the loci that have been
// visited, and an integer representing how many times the pathfinding has continued
// via call_out.  The return value needed is any true value if the run limit has been
// exceeded, false if not.  Optional.

private closure run_limit_rule;

void set_astar_run_limit_rule(closure val) {
    run_limit_rule = val;
}

closure query_astar_run_limit_rule() {
    return run_limit_rule;
}

// Caching
//
// The cache retains the pathfinding results that have been obtained so they do not
// have to be recalculated after being requested once, at the cost of some memory usage.
// One would use set_astar_caching(1) in the instance to turn on caching.
//
// If your neighbors rule does not always return the same results for a given locus,
// for instance if you use extra arguments to provide varying results as with terrain
// difficulty varies by the person traversing it, then you should generally not turn
// on caching, because the cached paths may not remain valid and could be returned
// in inappropriate circumstances.

private mapping cache;

void set_astar_caching(status val) {
    if(val)
        cache = ([]);
    else
        cache = 0;
}

status query_astar_caching() {
    return cache && 1;
}

// Validate key rule
//
// The validate key rule is only meaningful if you have caching turned on.  It can be
// used to provide mapping-key-usable representations of 'validate' closures passed to
// astar_find_path().  A common way to construct the rule is to return the to_string()
// of the closure; this implies that a particular 'validate' closure will always return
// the same way for a particular locus.  This is used for caching pathfinding results
// with 'validate' rules.  This means that if you cannot guarantee consistent results
// for a 'validate' function, you should return 0 so that the system knows not to cache
// the path using it.  If this rule is not defined, paths generated with 'validate'
// rules will not be cached.  The validate key rule is called with one argument, the
// 'validate' rule, and should return the representation to use, usually a string or
// int.  Optional.

private closure validate_key_rule;

void set_astar_validate_key_rule(closure val) {
    validate_key_rule = val;
}

closure query_astar_validate_key_rule() {
    return validate_key_rule;
}

// SECTION: Internal support functions
//
// These are functions used by the A* module.  Instances do not need to interact with them.

// astar_path_sort()
//
// Sorting function for paths, based on their cost.  Sorts low-cost paths to the end of
// the list.

private int astar_path_sort(mixed array a, mixed array b) {
    float cost_a = a[Astar_Path_Cost];
    float cost_b = b[Astar_Path_Cost];
    if(cost_a > cost_b)
        return -1;
    else if(cost_a < cost_b)
        return 1;
    else
        return 0;
}

// astar_distance()
//
// Distance retrieval process.  The distance rule is allowed to return -1 if, for whatever
// reason, it doesn't know how far it is between loci; the cost of the new path is set to be
// one greater than the cost of the path it extends.

private float astar_distance(mixed from, mixed to, mixed array path) {
    mixed res = funcall(distance_rule, from, to, path[Astar_Path_Loci],
        path[Astar_Path_Deltas]);
    if(res == -1)
        return path[Astar_Path_Distance] + 1.0;
    else
        return res;
}

// astar_key()
//
// Locus key retrieval process.  Finds the representation to use for the locus in checking
// visited status.

private mixed astar_key(mixed locus) {
    return locus_key_rule ? funcall(locus_key_rule, locus) : locus;
}

// astar_cached_path()
//
// Cached path retrieval.

private mixed astar_cached_path(mixed from, mixed to, closure validate) {
    if(!cache)
        return 0;
    mixed validate_key = validate && validate_key_rule &&
        funcall(validate_key_rule, validate);
    if(!validate || validate_key) {
        mapping validate_cache = cache[validate_key];
        if(validate_cache) {
            mixed from_key = astar_key(from);
            mapping from_cache = validate_cache[from_key];
            if(from_cache) {
                mixed to_key = astar_key(to);
                mixed path = from_cache[to_key];
                if(path)
                    return path;
            }
        }
    }
    return 0;
}

// astar_pathfinder()
//
// Performs the actual work of path calculation.  This is separated from astar_find_path(),
// below, so that it's call_out re-entrant.

private mixed astar_pathfinder(mixed from, mixed to, closure validate, closure callback,
        mixed array extra, mixed array paths, mapping visited, int iteration) {
    if(iteration) {
        mixed path = astar_cached_path(from, to, validate);
        if(path) {
            if(path == -1)
                path = 0;
            if(callback)
                apply(callback, path, extra);
            return path;
        }
    }
    mixed to_key = astar_key(to);
    for(;;) {
        if(run_limit_rule && funcall(run_limit_rule, from, to, validate, callback,
            extra, paths, visited, iteration)) {
            if(callback)
                call_out(#'astar_pathfinder, 2, from, to, validate, callback,
                    extra, paths, visited, iteration + 1);
            return 0;
        }
        mixed array extended = ({});
        // Sort the paths on their cost; we only want to deal with the lowest-cost
        // paths out of the ones we have
        paths = sort_array(paths, #'astar_path_sort);
        // Get the cost of the best path on hand; we only want paths with this
        // cost
        float cost = paths[<1][Astar_Path_Cost];
        int ix;
        // Check for possible extensions on as many paths as we have that are
        // at our best cost
        for(ix = sizeof(paths) - 1; ix >= 0 &&
            paths[ix][Astar_Path_Cost] <= cost; ix--) {
            mixed path = paths[ix];
            mixed last_locus = path[Astar_Path_Loci][<1];
            // Retrieve the list of neighbor loci and deltas to reach them
            mixed array neighbors = funcall(neighbors_rule, last_locus);
            if(!pointerp(neighbors))
                raise_error("Invalid return value from neighbors rule");
            foreach(mixed array neighbor : neighbors) {
                mixed locus = neighbor[0];
                mixed delta = neighbor[1];
                mixed cost = neighbor[2];
                // If we've already been here, never mind
                mixed key = astar_key(locus);
                if(visited[key])
                    continue;
                // Okay, then, now we've been here
                visited[key] = 1;
                // If we have a validation rule for loci, check against it
                if(validate && !funcall(validate, locus, delta, cost, last_locus,
                    from, to, path))
                    continue;
                // Otherwise, it's a valid extension.  Assemble the extended path
                // with this locus added to it, and calculate the distance and cost
                mixed array ext_path = copy(path);
                ext_path[Astar_Path_Loci] += ({ locus });
                ext_path[Astar_Path_Deltas] += ({ delta });
                ext_path[Astar_Path_Distance] = astar_distance(locus, to, path);
                // The cost of the extended path is its distance from the target
                // locus, plus the portion of the base path's cost that is not based
                // on its distance, plus the cost of the delta.
                ext_path[Astar_Path_Cost] =
                    path[Astar_Path_Cost] - path[Astar_Path_Distance] +
                    ext_path[Astar_Path_Distance] + cost;
                // If the locus we just reached is the target, we're done
                if(key == to_key) {
                    if(callback)
                        apply(callback, ext_path, extra);
                    if(cache) {
                        mixed validate_key = validate && validate_key_rule &&
                            funcall(validate_key_rule, validate);
                        if(!validate || validate_key) {
                            mapping validate_cache = cache[validate_key] ||= ([]);
                            mixed from_key = astar_key(from);
                            mapping from_cache = validate_cache[from_key] ||= ([]);
                            from_cache[to_key] = ext_path;
                        }
                    }
                    return ext_path;
                }
                // Keep track of the extended path
                extended += ({ ext_path });
            }
        }
        // Get rid of the paths that we extended, and add the newly extended paths
        // to our list
        paths = paths[0 .. ix] + extended;
        // If we no longer have any paths to examine, we're out of luck
        if(!sizeof(paths)) {
            if(callback)
                apply(callback, 0, extra);
            if(cache) {
                mixed validate_key = validate && validate_key_rule &&
                    funcall(validate_key_rule, validate);
                if(!validate || validate_key) {
                    mapping validate_cache = cache[validate_key] ||= ([]);
                    mixed from_key = astar_key(from);
                    mapping from_cache = validate_cache[from_key] ||= ([]);
                    from_cache[to_key] = -1;
                }
            }
            return 0;
        }
    }
}

// SECTION: Operational interface

// astar_find_path()
//
// Performs pathfinding starting with the 'from' locus, searching for the 'to' locus.
//
// 'validate' can be used to provide a closure that checks whether a locus is valid to
// include in the path; it is called with arguments of the locus being examined, the
// delta to reach it, the cost of the delta, the previous locus in the path, the
// starting locus, the target locus, and the path data structure for the entire path
// so far.  It should return true if the locus being examined should be included in the
// path.
//
// 'callback' can be used to provide a closure to be called at the completion of
// pathfinding.  The first argument to it will be the path found, if pathfinding was
// successful, or 0 if no path could be found.  Providing a callback allows pathfinding
// to be carried out across call_outs; if no callback is provided, then pathfinding
// will execute until it reaches the run limit defined by the instance, if any, or it
// hits the eval limit.  With a callback, pathfinding runs until it reaches the run
// limit, then continues via call_out two seconds later, continuing in this fashion
// until a path is found or all possible paths have been searched.
//
// Any additional arguments sent after 'callback' become subsequent arguments to be
// passed to 'callback' after the path argument and to the neighbors rule after the
// locus.
//
// The return value is an A* path structure (as defined by the Astar_Path_* macros
// above) if pathfinding was successful immediately, or 0 if either the run limit was
// encountered or pathfinding failed.

varargs mixed astar_find_path(mixed from, mixed to, closure validate, closure callback,
    varargs mixed array extra) {
    // Constrain our representation of our 'from' and 'to' loci
    if(locus_rule) {
        from = funcall(locus_rule, from);
        to = funcall(locus_rule, to);
    }
    mixed path = astar_cached_path(from, to, validate);
    if(path) {
        if(path == -1)
            path = 0;
        if(callback)
            apply(callback, path, extra);
        return path;
    }
    // Set up our starting point based on the 'from' locus
    mixed array start = allocate(Astar_Path_Fields);
    start[Astar_Path_Loci] = ({ from });
    start[Astar_Path_Deltas] = ({});
    start[Astar_Path_Distance] = astar_distance(from, to, start);
    start[Astar_Path_Cost] = start[Astar_Path_Distance];
    // Starting point becomes our path list, mapping to track where we've
    // visited starts out populated with starting locus
    return astar_pathfinder(from, to, validate, callback, extra, ({ start }),
        ([ astar_key(from) : 1 ]), 0);
}

// astar_clear_cache()
//
// Clears out the contents of the cache.  This can be useful for allowing caching in
// spaces that you otherwise couldn't use caching with because some sort of dynamicism
// in them (changing exits, shifting graph connectivity, etc.) would invalidate cached
// paths.  Using this, you can call astar_clear_cache() when changes occur, so that no
// outdated paths will be returned.

void astar_clear_cache() {
    if(!cache)
        raise_error("astar_clear_cache() called with caching off");
    cache = ([]);
}

Offline chaos

  • BFF
  • ***
  • Posts: 291
  • Job, school, social life, sleep. Pick 2.5.
    • View Profile
    • Lost Souls
Re: A* Search Algorithm
« Reply #5 on: July 09, 2007, 08:27:09 PM »
I've lately published a revision of this with various improvements (mostly to do with tracking internal state in a unified data structure) at http://lostsouls.org/grimoire_astar.

Offline chaos

  • BFF
  • ***
  • Posts: 291
  • Job, school, social life, sleep. Pick 2.5.
    • View Profile
    • Lost Souls
Re: A* Search Algorithm
« Reply #6 on: August 30, 2013, 07:54:36 PM »
This is available on Github now too: https://github.com/chaosprime/lpc-astar

The current version uses standard graph theory terminology (nodes and edges) instead of completely random-ass nomenclature of my own specification.