view release on metacpan or  search on metacpan

lib/AI/Pathfinding/AStar.pm  view on Meta::CPAN

	$map->doAStar($target,$open,$nodes,$max);

	my $path = $map->fillPath($open,$nodes,$target);
	$state = {
		'path'    => $path,
		'open'    => $open,
		'visited' => $nodes,
		'done'    => defined($nodes->{$target}),
	};

	return $state;
}

1;

__END__

=head1 NAME

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

=head1 SYNOPSIS

  package My::Map::Package;
  use base AI::Pathfinding::AStar;

  # Methods required by AI::Pathfinding::AStar
  sub getSurrounding { ... }

  package main;
  use My::Map::Package;

  my $map = My::Map::Package->new or die "No map for you!";
  my $path = $map->findPath($start, $target);
  print join(', ', @$path), "\n";
  
  #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