AI-Pathfinding-AStar

 view release on metacpan or  search on metacpan

README  view on Meta::CPAN

      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

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

		$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;
		#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,$max);

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

  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...

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

	my $proto = shift;
	my $class = ref($proto) || $proto;

	my ($id,$g,$h) = @_;

	my $self = {};
	$self->{id}     = $id;
	$self->{g}      = $g;
	$self->{h}      = $h;
	$self->{f}      = $g+$h;
	$self->{parent} = undef;
	$self->{cost}   = 0;
	$self->{inopen} = 0;
	$self->{heap} = undef;

	bless ($self, $class);
	return $self;
}

sub heap {
	my ($self, $val) = @_;
	$self->{heap} = $val if (defined $val);
	return $self->{heap};
}