AI-Pathfinding-SMAstar
view release on metacpan or search on metacpan
t/test8.lst
lib/AI/Pathfinding/SMAstar.pm
lib/AI/Pathfinding/SMAstar/Path.pm
lib/AI/Pathfinding/SMAstar/AVLQueue.pm
lib/AI/Pathfinding/SMAstar/PairObj.pm
lib/AI/Pathfinding/SMAstar/PriorityQueue.pm
lib/AI/Pathfinding/SMAstar/TreeOfQueues.pm
lib/AI/Pathfinding/SMAstar/Examples/PalUtils.pm
lib/AI/Pathfinding/SMAstar/Examples/WordObj.pm
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm
META.yml Module meta-data (added by MakeMaker)
# when called on a node, returns 1 if it is a goal
_state_goal_p_func => \&FrontierObj::goal_test,
# must return the number of successors of a node
_state_num_successors_func => \&FrontierObj::get_num_successors,
# must return *one* successor at a time
_state_successors_iterator => \&FrontierObj::get_successors_iterator,
# can be any suitable string representation
_state_get_data_func => \&FrontierObj::string_representation,
# gets called once per iteration, useful for showing algorithm progress
_show_prog_func => \&FrontierObj::progress_callback,
);
# you can start the search from multiple start-states
# Add the initial states to the smastar object before starting the search.
foreach my $frontierObj (@start_states){
$smastar->add_start_state($frontierObj);
}
* State successors iterator (_state_iterator above)
This function must return a *handle to a function* that returns next
successor of this node, i.e. it must return an iterator that produces
the successors of this node *one* at a time. This is
necessary to maintain the memory-bounded constraint of SMA* search.
* State get-data function (_state_get_data_func above)
This function returns a string representation of this node.
* State show-progress function (_show_prog_func above)
This is a callback function for displaying the progress of the
search. It can be an empty callback if you do not need this output.
state_num_successors_func()
Sets/gets the function that returns the number of successors of
this node.
state_successors_iterator()
Sets/gets the function that returns the next successor of
this node.
state_get_data_func()
Sets/gets the function that returns a string representation
of this node.
show_prog_func()
sets/gets the callback function for displaying the progress of the
search. It can be an empty callback if you do not need this output.
EXPORT
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
my $invocant = shift;
my $class = ref($invocant) || $invocant;
my $self = {
_priority_queue => AI::Pathfinding::SMAstar::PriorityQueue->new(),
_state_eval_func => undef,
_state_goal_p_func => undef,
_state_num_successors_func => undef,
_state_successors_iterator => undef,
_show_prog_func => undef,
_state_get_data_func => undef,
@_, # attribute override
};
return bless $self, $class;
}
sub state_eval_func {
my $self = shift;
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
if (@_) { $self->{_state_num_successors_func} = shift }
return $self->{_state_num_successors_func};
}
sub state_successors_iterator {
my $self = shift;
if (@_) { $self->{_state_successors_iterator} = shift }
return $self->{_state_successors_iterator};
}
sub state_get_data_func {
my $self = shift;
if (@_) { $self->{_state_get_data_func} = shift }
return $self->{_state_get_data_func};
}
sub show_prog_func {
my $self = shift;
if (@_) { $self->{_show_prog_func} = shift }
return $self->{_show_prog_func};
}
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
###################################################################
sub add_start_state
{
my ($self, $state) = @_;
my $state_eval_func = $self->{_state_eval_func};
my $state_goal_p_func = $self->{_state_goal_p_func};
my $state_num_successors_func = $self->{_state_num_successors_func},
my $state_successors_iterator = $self->{_state_successors_iterator},
my $state_get_data_func = $self->{_state_get_data_func};
# make sure required functions have been defined
if(!defined($state_eval_func)){
croak "SMAstar: evaluation function is not defined\n";
}
if(!defined($state_goal_p_func)){
croak "SMAstar: goal function is not defined\n";
}
if(!defined($state_num_successors_func)){
croak "SMAstar: num successors function is not defined\n";
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
croak "SMAstar: successor iterator is not defined\n";
}
# create a path object from this state
my $state_obj = AI::Pathfinding::SMAstar::Path->new(
_state => $state,
_eval_func => $state_eval_func,
_goal_p_func => $state_goal_p_func,
_num_successors_func => $state_num_successors_func,
_successors_iterator => $state_successors_iterator,
_get_data_func => $state_get_data_func,
);
my $fcost = AI::Pathfinding::SMAstar::Path::fcost($state_obj);
# check if the fcost of this node looks OK (is numeric)
unless(Scalar::Util::looks_like_number($fcost)){
croak "Error: f-cost of state is not numeric. Cannot add state to queue.\n";
}
$state_obj->f_cost($fcost);
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
# when called on a node, returns 1 if it is a goal
_state_goal_p_func => \&FrontierObj::goal_test,
# must return the number of successors of a node
_state_num_successors_func => \&FrontierObj::get_num_successors,
# must return *one* successor at a time
_state_successors_iterator => \&FrontierObj::get_successors_iterator,
# can be any suitable string representation
_state_get_data_func => \&FrontierObj::string_representation,
# gets called once per iteration, useful for showing algorithm progress
_show_prog_func => \&FrontierObj::progress_callback,
);
# You can start the search from multiple start-states.
# Add the initial states to the smastar object before starting the search.
foreach my $frontierObj (@start_states){
$smastar->add_start_state($frontierObj);
}
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
B<State successors iterator> (C<_state_iterator> above)
This function must return a I<handle to a function> that produces the next
successor of the argument object, i.e. it must return an iterator function that
produces the successors of this node *one* at a time. This is necessary
to maintain the memory-bounded constraint of SMA* search.
=item *
B<State get-data function> (C<_state_get_data_func> above)
This function returns a string representation of this node.
=item *
B<State show-progress function> (C<_show_prog_func> above)
This is a callback function for displaying the progress of the search.
It can be an empty callback if you do not need this output.
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
=head2 state_successors_iterator()
$smastar->state_successors_iterator(\&FrontierObj::get_successors_iterator);
Set/get the handle to the function that returns iterator that produces the
next successor of this node.
=head2 state_get_data_func()
$smastar->state_get_data_func(\&FrontierObj::string_representation);
Set/get the handle to the function that returns a string
representation of this node.
=head2 show_prog_func()
$smatar->show_prog_func(\&FrontierObj::progress_callback);
Sets/gets the callback function for displaying the progress of the search.
lib/AI/Pathfinding/SMAstar/AVLQueue.pm view on Meta::CPAN
# AVLQueue constructor
##################################################
sub new {
my $invocant = shift;
my $class = ref($invocant) || $invocant;
my $self = {
_key => undef, # for comparisons with other queues, etc.
_avltree => Tree::AVL->new(fcompare => \&AI::Pathfinding::SMAstar::AVLQueue::compare_obj_counters,
fget_key => \&AI::Pathfinding::SMAstar::AVLQueue::obj_counter,
fget_data => \&AI::Pathfinding::SMAstar::AVLQueue::obj_value),
_counter => 0,
_obj_counts_tree => Tree::AVL->new(fcompare => \&AI::Pathfinding::SMAstar::PairObj::compare_keys_numeric,
fget_key => \&AI::Pathfinding::SMAstar::PairObj::key,
fget_data => \&AI::Pathfinding::SMAstar::PairObj::val),
@_, # Override previous attributes
};
return bless $self, $class;
}
##############################################
# accessor
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
_depth => 0,
_f_cost => undef,
@_, # Override previous attributes
};
return bless $self, $class;
}
##############################################
## methods to access per-object data
##
## With args, they set the value. Without
## any, they only retrieve it/them.
##############################################
sub start_word {
my $self = shift;
if (@_) { $self->{_start_word} = shift }
return $self->{_start_word};
}
lib/AI/Pathfinding/SMAstar/Examples/WordObj.pm view on Meta::CPAN
my $invocant = shift;
my $class = ref($invocant) || $invocant;
my $self = {
_word => undef,
@_, # Override previous attributes
};
return bless $self, $class;
}
##############################################
## methods to access per-object data ##
## ##
## With args, they set the value. Without ##
## any, they only retrieve it/them. ##
##############################################
sub word {
my $self = shift;
if (@_) { $self->{_word} = shift }
return $self->{_word};
}
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
sub new {
my $invocant = shift;
my $class = ref($invocant) || $invocant;
my $self = {
_state => undef, # node in the search space
_eval_func => undef,
_goal_p_func => undef,
_num_successors_func => undef,
_successors_iterator => undef,
_get_data_func => undef,
###########################################
#
# path stuff
#
###########################################
_antecedent => undef, # pointer to the antecedent of this obj
_f_cost => undef, # g + h where g = cost so far, h = estimated cost to goal.
_forgotten_node_fcosts => [], # array to store fcosts of forgotten nodes
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
my $descendants_found = 0;
# loop over nodes returned by iterator
while(my $next_state = $iterator->()){
$next_descendant = AI::Pathfinding::SMAstar::Path->new(
_state => $next_state,
_eval_func => $self->{_eval_func},
_goal_p_func => $self->{_goal_p_func},
_get_data_func => $self->{_get_data_func},
_num_successors_func => $self->{_num_successors_func},
_successors_iterator => $self->{_successors_iterator},
_antecedent => $self,
_depth => $depth + 1,
);
my $start_word = $next_descendant->{_state}->{_start_word};
my $phrase = $next_descendant->{_state}->{_phrase};
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
# no next successor found
$self->is_completed(1);
}
return $next_descendant;
}
}
sub get_data
{
my ($self) = @_;
my $get_data_func = $self->{_get_data_func};
my $data = $get_data_func->($self->{_state});
return $data;
}
sub DESTROY
{
my ($self) = @_;
# antecedent is no longer pointing at this object, or else
# DESTROY would not have been called.
lib/AI/Pathfinding/SMAstar/PriorityQueue.pm view on Meta::CPAN
# PriorityQueue constructor
##################################################
sub new {
my $invocant = shift;
my $class = ref($invocant) || $invocant;
my $self = {
_hash_of_trees_ref => {},
_cost_min_max_tree => Tree::AVL->new( fcompare => \&fp_compare, # floating-point compare
fget_key => sub { $_[0] },
fget_data => sub { $_[0] },),
f_depth => \&AI::Pathfinding::SMAstar::Path::depth,
f_fcost => \&AI::Pathfinding::SMAstar::Path::fcost,
f_avl_compare => \&AI::Pathfinding::SMAstar::Path::compare_by_depth,
f_avl_get_key => \&AI::Pathfinding::SMAstar::Path::depth,
f_avl_get_data => \&AI::Pathfinding::SMAstar::Path::get_data,
_size => 0,
@_, # attribute override
};
return bless $self, $class;
}
################################################
# accessors
lib/AI/Pathfinding/SMAstar/PriorityQueue.pm view on Meta::CPAN
my $cost_hash_ref = $self->{_hash_of_trees_ref};
my $cost_hash_key_func = $self->{f_fcost};
my $cost_min_max_tree = $self->{_cost_min_max_tree};
my $depth_func = $self->{f_depth};
my $avl_compare_func = $self->{f_avl_compare};
my $avl_get_key_func = $self->{f_avl_get_key};
my $avl_get_data_func = $self->{f_avl_get_data};
my $cost_key = $pobj->$cost_hash_key_func();
my $data = $pobj->$avl_get_data_func();
# inserting pobj with key: $cost_key, data: $data
if(!$cost_hash_ref->{$cost_key}){
# no tree for this depth yet, so create one.
my $avltree = AI::Pathfinding::SMAstar::TreeOfQueues->new(
f_avl_compare => $avl_compare_func,
f_obj_get_key => $avl_get_key_func,
f_obj_get_data => $avl_get_data_func,
);
$avltree->insert($pobj);
$cost_hash_ref->{$cost_key} = \$avltree;
# insert the cost_key in the cost tree
$cost_min_max_tree->insert($cost_key);
}
else{
# there is already a tree at $cost_key, so inserting there
my $avltree = $cost_hash_ref->{$cost_key};
lib/AI/Pathfinding/SMAstar/PriorityQueue.pm view on Meta::CPAN
{
my ($self, $obj, $cmp_func) = @_;
my $cost_hash_ref = $self->{_hash_of_trees_ref};
my @cost_keys = (keys %$cost_hash_ref);
my $cost_min_max_tree = $self->{_cost_min_max_tree};
my $avl_get_data_func = $self->{f_avl_get_data};
my $cost_hash_key_func = $self->{f_fcost};
my $depth_func = $self->{f_depth};
my $cost_key = $obj->$cost_hash_key_func();
my $data = $obj->$avl_get_data_func();
if(!$cost_hash_ref->{$cost_key}){
# no tree for this cost_key
return;
}
else{
# found the tree at $cost_key, trying to remove obj from there
my $avltree = $cost_hash_ref->{$cost_key};
$$avltree->remove($obj, $cmp_func);
lib/AI/Pathfinding/SMAstar/PriorityQueue.pm view on Meta::CPAN
return $obj;
}
}
sub deepest_lowest_cost_leaf_dont_remove
{
my ($self) = @_;
my $avl_compare_func = $self->{f_avl_compare};
my $avl_get_key_func = $self->{f_avl_get_key};
my $avl_get_data_func = $self->{f_avl_get_data};
my $cost_hash_ref = $self->{_hash_of_trees_ref};
my @cost_keys = (keys %$cost_hash_ref);
my $cost_min_max_tree = $self->{_cost_min_max_tree};
if(!@cost_keys){
# queue is empty
lib/AI/Pathfinding/SMAstar/PriorityQueue.pm view on Meta::CPAN
if(!$cost_hash_ref->{$lowest_cost_key}){
# no tree for this cost.
return;
}
else{
my $avltree = $cost_hash_ref->{$lowest_cost_key};
# found tree at key $lowest_cost_key.
my $obj = $$avltree->largest_oldest(); # get the deepest one
my $cost_key = $obj->$avl_get_key_func();
my $data = $obj->$avl_get_data_func();
return $obj;
}
}
# Return the shallowest, highest-cost leaf
sub shallowest_highest_cost_leaf
{
my ($self, $best, $succ, $str_function) = @_;
lib/AI/Pathfinding/SMAstar/TreeOfQueues.pm view on Meta::CPAN
##################################################
# TreeOfQueues constructor
##################################################
sub new {
my $invocant = shift;
my $class = ref($invocant) || $invocant;
my $self = {
f_avl_compare => undef,
f_obj_get_key => undef,
f_obj_get_data => undef,
_avl_tree => Tree::AVL->new(fcompare => \&AI::Pathfinding::SMAstar::AVLQueue::compare,
fget_key => \&AI::Pathfinding::SMAstar::AVLQueue::key,
fget_data => \&AI::Pathfinding::SMAstar::AVLQueue::key),
@_, # attribute override
};
return bless $self, $class;
}
sub insert{
my ($self, $obj) = @_;
lib/AI/Pathfinding/SMAstar/TreeOfQueues.pm view on Meta::CPAN
sub print{
my ($self) = @_;
if($self->{_avl_tree}->is_empty()){
print "tree is empty\n";
}
my $get_key_func = $self->{f_obj_get_key};
my $get_data_func = $self->{f_obj_get_data};
my @queue_list = $self->{_avl_tree}->get_list();
foreach my $queue (@queue_list){
#print "queue is $queue\n";
my $queue_key = $queue->key();
#print "queue key: $queue_key\n";
my @objlist = $queue->get_list();
if(!@objlist){
print "queue at key $queue_key is empty\n";
}
print "queue at key $queue_key:\n";
foreach my $obj (@objlist){
my $key = $obj->$get_key_func;
my $word = $obj->$get_data_func;
print " key: $key, data: $word\n";
}
}
}
sub is_empty{
my ($self) = @_;
if($self->{_avl_tree}->is_empty()){
return 1;
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
$sparsity = 2;
$max_states_in_queue = 4;
diag("\ncreating AVL trees");
# create trees of WordObj objects, so that we can use
# WordObj::compare_up_to(), the 'relaxed' comparison function
my $avltree = Tree::AVL->new(
fcompare => \&AI::Pathfinding::SMAstar::Examples::WordObj::compare,
fget_key => \&AI::Pathfinding::SMAstar::Examples::WordObj::word,
fget_data => \&AI::Pathfinding::SMAstar::Examples::WordObj::word,
);
my $avltree_rev = Tree::AVL->new(
fcompare => \&AI::Pathfinding::SMAstar::Examples::WordObj::compare,
fget_key => \&AI::Pathfinding::SMAstar::Examples::WordObj::word,
fget_data => \&AI::Pathfinding::SMAstar::Examples::WordObj::word,
);
print STDERR "-" x 80 . "\n";
print STDERR "-" x 80 . "\n";
diag("reading dictionary '$dictionary_file'");
eval{
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
my @phrase_obj_list;
my $smastar;
ok(
$smastar = AI::Pathfinding::SMAstar->new(
_state_eval_func => AI::Pathfinding::SMAstar::Examples::Phrase::evaluate($min_letters),
_state_goal_p_func => AI::Pathfinding::SMAstar::Examples::Phrase::phrase_is_palindrome_min_num_chars($min_letters),
_state_num_successors_func => \&AI::Pathfinding::SMAstar::Examples::Phrase::get_num_successors,
_state_successors_iterator => \&AI::Pathfinding::SMAstar::Examples::Phrase::get_descendants_iterator,
_state_get_data_func => \&AI::Pathfinding::SMAstar::Examples::Phrase::roll_up_phrase,
_show_prog_func => sub{ },
#_show_prog_func => \&AI::Pathfinding::SMAstar::Examples::PalUtils::show_progress_so_far,
),
'created smastar');
diag("smastar object created");
foreach my $word (@words_w_cands){
( run in 0.337 second using v1.01-cache-2.11-cpan-8d75d55dd25 )