AI-Pathfinding-AStar

 view release on metacpan or  search on metacpan

README  view on Meta::CPAN

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";
  
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,

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

sub _init {
    my $self = shift;
    croak "no getSurrounding() method defined" unless $self->can("getSurrounding");

    return $self->SUPER::_init(@_);
}

sub doAStar
{
	my ($map, $target, $open, $nodes, $max) = @_;

	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);
				$surr_node->{parent} = $curr_node;

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

					$surr_node->{g}      = $possG;
					$open->decrease_key($surr_node);
				}
			}
		}
	}
}

sub fillPath
{
	my ($map,$open,$nodes,$target) = @_;
	my $path = [];

        my $curr_node = (exists $nodes->{$target}) ? $nodes->{$target} : $open->top();
	while (defined $curr_node) {
		unshift @$path, $curr_node->{id};
		$curr_node = $curr_node->{parent};
	}
	return $path;
}


sub findPath {
	my ($map, $start, $target) = @_;

	my $nodes = {};
	my $curr_node = undef;

	my $open = Heap::Binomial->new;
	#add starting square to the open list
	$curr_node = AI::Pathfinding::AStar::AStarNode->new($start,0,0);  # AStarNode(id,g,h)
	$curr_node->{parent} = undef;
	$curr_node->{cost}   = 0;
	$curr_node->{g}      = 0;
	$curr_node->{h}      = 0;
	$curr_node->{inopen} = 1;
	$nodes->{$start}     = $curr_node;
	$open->add($curr_node);

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

	my $path = $map->fillPath($open,$nodes,$target);

	return wantarray ? @{$path} : $path;
}

sub findPathIncr {
	my ($map, $start, $target, $state, $max) = @_;

	my $open = undef;
	my $curr_node = undef;;
	my $nodes = {};
        if (defined($state)) {
		$nodes = $state->{'visited'};
		$open  = $state->{'open'};
        }
	else {
		$open = Heap::Binomial->new;

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

		$curr_node = AI::Pathfinding::AStar::AStarNode->new($start,0,0);  # AStarNode(id,g,h)
		$curr_node->{parent} = undef;
		$curr_node->{cost}   = 0;
		$curr_node->{g}      = 0;
		$curr_node->{h}      = 0;
		$curr_node->{inopen} = 1;
       		$nodes->{$start} = $curr_node;
		$open->add($curr_node);
	}

	$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;
}

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

  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

t/01_AI-Pathfinding-AStar.t  view on Meta::CPAN

use Test::More tests => 6;
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++)
	{
		for(my $y=1; $y<=5; $y++)
			{$self->{map}->{$x.'.'.$y} = 1;}
	}
	$self->{map}->{'4.2'} = 0;
	$self->{map}->{'4.3'} = 0;
	$self->{map}->{'4.4'} = 0;

    return $self;
}

#some support routines

#get orthoganal neighbours
sub getOrth
{
	my ($source) = @_;

t/01_AI-Pathfinding-AStar.t  view on Meta::CPAN

	my ($x2, $y2) = split(/\./, $target);

	return (abs($x1-$x2) + abs($y1-$y2));
}

#the routine required by AI::Pathfinding::AStar
sub getSurrounding
{
	my ($self, $source, $target) = @_;

	my %map = %{$self->{map}};
	my ($src_x, $src_y) = split(/\./, $source);

	my $surrounding = [];

	#orthogonal moves cost 10, diagonal cost 140
	foreach my $node (getOrth($source))
	{
		if ( (exists $map{$node}) && ($map{$node}) )
			{push @$surrounding, [$node, 10, calcH($node, $target)];}
	}
	foreach my $node (getDiag($source))
	{
		if ( (exists $map{$node}) && ($map{$node}) )
			{push @$surrounding, [$node, 140, calcH($node, $target)];}
	}

	return $surrounding;
}

my $g;

ok($g = AI::Pathfinding::AStar::Test->new(), 'new()');
isa_ok($g, AI::Pathfinding::AStar, 'isa');