view release on metacpan or  search on metacpan

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

		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;
				$surr_node->{cost}   = $surr_cost;
				$surr_node->{inopen} = 1;
				$nodes->{$surr_id}   = $surr_node;
				$open->add($surr_node);
			}
			else {
				#otherwise it's already in the OPEN list
				#check to see if it's cheaper to go through the current
				#square compared to the previous path
				my $surr_node = $nodes->{$surr_id};
				my $currG     = $surr_node->{g};
				my $possG     = $G + $surr_cost;
				if ($possG < $currG) {
					#change the parent
					$surr_node->{parent} = $curr_node;
					$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);

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

	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/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) = @_;