AI-Pathfinding-AStar
view release on metacpan or search on metacpan
0.09 Sat Jun 16 19:00:00 2007
- I apologize. Revision number bumped due to distribution snafu.
0.08 Sat Jun 16 16:00:00 2007
- Major bug fixed that caused some paths to be incorrectly
determined due to an over-greedy implementation. Thanks, Flavio!
0.07 Tue Aug 08 07:00:00 2006
- Major changes introduced by Franc Carter which include:
- Speed optimizations by using a different Heap module and slightly restructured hash
- The welcome addition of a FindPathIncr() function that allows you to calculate paths in chunks
These are major changes about which I am very excited. Thank you again, Franc!
0.06 Mon Nov 28 19:00:00 2005
- no changes, CPAN refused to update the version number so I resubmitted
0.05 Fri Nov 25 09:30:00 2005
- fixed Makefile.PL to include a dependency on Heap::Simple::Perl to fix all the CPANTester reports
0.04 Mon Oct 17 17:30:00 2005
- finally made findpath() aware of the context in which it was called and it will now return either an array or array reference accordingly
- minor coding style tweaks
- minor documentation edits
0.03 Sat Oct 15 21:00:00 2005
- fixed a bug in the which successive calls of findPath() would fail to find an existing path
- made a few minor documentation changes to be a little more clear
0.02 Thu Aug 26 09:30:00 2004
- restructured the module to act as a base class - It is now actually useful!!
- reworked the documentation to be more clear
0.01 Sat Sep 10 11:20:23 2003
- original version uploaded to CPAN
# http://module-build.sourceforge.net/META-spec.html
#XXXXXXX This is a prototype!!! It will change in the future!!! XXXXX#
name: AI-Pathfinding-AStar
version: 0.10
version_from: lib/AI/Pathfinding/AStar.pm
installdirs: site
requires:
Heap::Binomial: 0
Heap::Elem: 0
Test::More: 0.11
distribution_type: module
generated_by: ExtUtils::MakeMaker version 6.30
#Or you can do it incrementally, say 3 nodes at a time
my $state = $map->findPathIncr($start, $target, undef, 3);
while ($state->{path}->[-1] ne $target) {
print join(', ', @{$state->{path}}), "\n";
$state = $map->findPathIncr($start, $target, $state, 3);
}
print "Completed Path: ", join(', ', @{$state->{path}}), "\n";
DESCRIPTION
This module implements the A* pathfinding algorithm. It acts as a base
class from which a custom map object can be derived. It requires from
the map object a subroutine named "getSurrounding" (described below) and
provides to the object two routines called "findPath" and "findPathIncr"
(also described below.) It should also be noted that
AI::Pathfinding::AStar defines two other subs ("calcF" and "calcG")
which are used only by the "findPath" routines.
AI::Pathfinding::AStar requires that the map object define a routine
named "getSurrounding" which accepts the starting and target node ids
for which you are calculating the path. In return it should provide an
array reference containing the following details about each of the
immediately surrounding nodes:
* Node ID
* Cost to enter that node
* Heuristic
Basically you should return an array reference like this: "[ [$node1,
$cost1, $h1], [$node2, $cost2, $h2], [...], ...];" For more information
on heuristics and the best ways to calculate them, visit the links
listed in the *SEE ALSO* section below. For a very brief idea of how to
write a getSurrounding routine, refer to the included tests.
As mentioned earlier, AI::Pathfinding::AStar provides two routines named
"findPath" and "findPathIncr". "findPath" requires as input the starting
and target node identifiers. It is unimportant what format you choose
for your node IDs. As long as they are unique, and can be distinguished
by Perl's "exists $hash{$nodeid}", then they will work. "findPath" then
returns an array (or reference) of node identifiers representing the
least expensive path to your target node. An empty array means that the
target node is entirely unreacheable from the given source.
"findPathIncr" on the other hand allows you to calculate a particularly
long path in chunks. "findPathIncr" also takes the starting and target
node identifiers but also accepts a "state" variable and a maxiumum
number of nodes to calculate before returning. "findPathIncr" then
returns a hash representing the current state that can then be passed
back in for further processing later. The current path can be found in
"$state-"{path}>.
PREREQUISITES
This module requires Heap (specifically Heap::Fibonacci and Heap::Elem)
to function.
SEE ALSO
<http://www.policyalmanac.org/games/aStarTutorial.htm>,
<http://xenon.stanford.edu/~amitp/gameprog.html>
AUTHOR
Aaron Dalton - aaron@daltons.ca 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.
COPYRIGHT AND LICENSE
Copyright (c) 2004 Aaron Dalton. All rights reserved. This library is
free software; you can redistribute it and/or modify it under the same
terms as Perl itself.
lib/AI/Pathfinding/AStar.pm view on Meta::CPAN
my $n = 0;
FLOOP: while ( (defined $open->top()) && ($open->top()->{id} ne $target) ) {
#allow incremental calculation
last FLOOP if (defined($max) and (++$n == $max));
my $curr_node = $open->extract_top();
$curr_node->{inopen} = 0;
my $G = $curr_node->{g};
#get surrounding squares
my $surr_nodes = $map->getSurrounding($curr_node->{id}, $target);
foreach my $node (@$surr_nodes) {
my ($surr_id, $surr_cost, $surr_h) = @$node;
#skip the node if it's in the CLOSED list
next if ( (exists $nodes->{$surr_id}) && (! $nodes->{$surr_id}->{inopen}) );
#add it if we haven't seen it before
if (! exists $nodes->{$surr_id}) {
my $surr_node = AI::Pathfinding::AStar::AStarNode->new($surr_id,$G+$surr_cost,$surr_h);
lib/AI/Pathfinding/AStar.pm view on Meta::CPAN
#Or you can do it incrementally, say 3 nodes at a time
my $state = $map->findPathIncr($start, $target, undef, 3);
while ($state->{path}->[-1] ne $target) {
print join(', ', @{$state->{path}}), "\n";
$state = $map->findPathIncr($start, $target, $state, 3);
}
print "Completed Path: ", join(', ', @{$state->{path}}), "\n";
=head1 DESCRIPTION
This module implements the A* pathfinding algorithm. It acts as a base class from which a custom map object can be derived. It requires from the map object a subroutine named C<getSurrounding> (described below) and provides to the object two routin...
AI::Pathfinding::AStar requires that the map object define a routine named C<getSurrounding> which accepts the starting and target node ids for which you are calculating the path. In return it should provide an array reference containing the followi...
=over
=item * Node ID
=item * Cost to enter that node
=item * Heuristic
=back
Basically you should return an array reference like this: C<[ [$node1, $cost1, $h1], [$node2, $cost2, $h2], [...], ...];> For more information on heuristics and the best ways to calculate them, visit the links listed in the I<SEE ALSO> section below...
As mentioned earlier, AI::Pathfinding::AStar provides two routines named C<findPath> and C<findPathIncr>. C<findPath> requires as input the starting and target node identifiers. It is unimportant what format you choose for your node IDs. As long a...
=head1 PREREQUISITES
This module requires Heap (specifically Heap::Binomial and Heap::Elem) to function.
=head1 SEE ALSO
L<http://www.policyalmanac.org/games/aStarTutorial.htm>, L<http://xenon.stanford.edu/~amitp/gameprog.html>
=head1 AUTHOR
Aaron Dalton - aaron@daltons.ca
This is my very first CPAN contribution and I am B<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.
=head1 COPYRIGHT AND LICENSE
Copyright (c) 2004 Aaron Dalton. All rights reserved.
This library is free software; you can redistribute it and/or modify
it under the same terms as Perl itself.
=cut
t/01_AI-Pathfinding-AStar.t view on Meta::CPAN
BEGIN {
use base AI::Pathfinding::AStar;
};
#########################
# Insert your test code below, the Test::More module is use()ed here so read
# its man page ( perldoc Test::More ) for help writing this test script.
#initialize a basic map
#This example module represents the following map:
#
# . . . . . . .
# . . . | . . .
# @ . . | . . *
# . . . | . . .
# . . . . . . .
#
#Where . represents open squares and | represents walls. The @ represents our
#starting square and the * the target square. This module assumes that
#orthogonal moves cost 10 points and diagonal moves cost 140. The heuristic
#used is Manhattan, which simply counts the orthogonal distance between any 2
#squares whilst disregarding any barriers.
sub new
{
my $invocant = shift;
my $class = ref($invocant) || $invocant;
my $self = bless {}, $class;
$self->{map} = {};
for(my $x=1; $x<=7; $x++)
{
( run in 0.500 second using v1.01-cache-2.11-cpan-49f99fa48dc )