AI::Pathfinding::AStar - Perl implementation of the A* pathfinding algorithm

NAME

AI::Pathfinding::AStar - Perl implementation of the A* pathfinding algorithm

SYNOPSIS

  use AI::Pathfinding::AStar qw(findPath)
  my $path = &findPath($map_obj, $start, $target);
  print join(', ', @$path), "\n";

DESCRIPTION

This module implements the A* pathfinding algorithm. It attempts to be as generally useful as possible by leaving the determination of legal moves and heuristic calculations to an external map object.

This object can export a single function, &findPath, and requires the following parameters:

Map Object
AI::Pathfinding::AStar assumes that the user has created a Perl object representing the given playing field. A reference to this object must be passed. This object must implement a method by the name &astar_surrounding which accepts an identifier for a node on your map as well as an identifier for the target node. This method must return a reference to an array containing references to sub-arrays each describing the nodes adjacent to the given node. Each sub-array should have 3 elements:
Node ID
Cost to enter that node
Heuristic

Basically you should return a reference like this: return [ [$node1, $cost1, $h1], [$node2, $cost2, $h2], [...], ...]; I know this sounds confusing. Please refer to the ExampleMap.pm sourcefile for a very basic example of a conforming map object.

Starting Node ID
Target Node ID
AI::Pathfinding::AStar of course needs to know from where you're starting and where you're heading. The AStar routine does not care really what format you choose for your Node IDs. As long as they are unique and can be recognized by Perl's exists $hash{$nodeid} then they will work.

This routine then returns a reference to an array of Node IDs representing the least expensive path to your target node.

PREREQUISITES

This module requires Heap::Simple to function.

SEE ALSO

Heap::Simple, http://www.policyalmanac.org/games/aStarTutorial.htm This distribution contains an example map object and test script in the examples directory that may be of assistance.

AUTHOR

Aaron Dalton - acdalton@cpan.org This is my very first CPAN contribution and I am not a professional programmer. Any feedback you may have, even regarding issues of style, would be greatly appreciated. I hope it is of some use to somebody.

COPYRIGHT AND LICENSE

Copyright 2003 by Aaron Dalton

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

 AI::Pathfinding::AStar - Perl implementation of the A* pathfinding algorithm