AI-Pathfinding-SMAstar

 view release on metacpan or  search on metacpan

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

##################################################
# SMAstar constructor 
##################################################
sub new {
    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/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),

lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm  view on Meta::CPAN

$max_forgotten_nodes = 0;


##################################################
## the Phrase constructor 
##################################################
sub new {
    my $invocant = shift;
    my $class   = ref($invocant) || $invocant;
    my $self = {
	_word_list               => undef,
	_words_w_cands_list      => undef,
	_dictionary              => undef,
	_dictionary_rev          => undef,
	_start_word              => undef,  # remainder on cand for antecedent of this obj
	_word                    => undef,
	_cand                    => undef,  # cand found for the antecedent of this obj
	_predecessor             => undef,
	_dir                     => 0,
	_repeated_pal_hash_ref   => {},
        _match_remainder_left    => undef,  
	_match_remainder_right   => undef,
	_letters_seen            => undef,  # letters seen, up to/including antecedent
	_cost                    => undef,  # cost used for heuristic search
	_cost_so_far             => undef,
	_num_chars_so_far        => undef,  # cummulative cost used for heuristic
	_num_new_chars           => undef,
	_no_match_remainder      => undef,  # flag specifying whether there was a remainder
	_phrase                  => undef,
	_depth                   => 0,
	_f_cost                  => undef,
	@_,    # Override previous attributes
    };

    return bless $self, $class;
 
}

##############################################
## methods to access per-object data        
##                                    

lib/AI/Pathfinding/SMAstar/Examples/WordObj.pm  view on Meta::CPAN

package AI::Pathfinding::SMAstar::Examples::WordObj;
use strict;

##################################################
## the object constructor (simplistic version)  ##
##################################################
sub new {
    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.         ##

lib/AI/Pathfinding/SMAstar/PairObj.pm  view on Meta::CPAN

package AI::Pathfinding::SMAstar::PairObj;
use strict;

##################################################
# PairObj constructor
##################################################
sub new {
    my $invocant = shift;
    my $class   = ref($invocant) || $invocant;
    my $self = {
	_key    => undef,
        _value  => undef,      
        @_,  # Override previous attributes
    };
    return bless $self, $class;
}

##############################################
# accessors
##############################################
sub value {
    my $self = shift;

lib/AI/Pathfinding/SMAstar/Path.pm  view on Meta::CPAN

##################################################
# Path constructor 
##################################################
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
	_forgotten_nodes_num     => 0,

	_forgotten_nodes_offsets => {},

	_depth                   => 0,     # depth used for memory-bounded search
	_descendants_produced    => [],
	_descendant_index        => undef,	
	_descendant_fcosts       => [],
	_descendants_on_queue    => 0,

	_descendands_deleted     => 0,
	_is_completed            => 0,
	_num_successors          => undef,
	_num_successors_in_mem   => 0,
	_is_on_queue             => 0,
	_iterator_index          => 0,      # to remember index of iterator for descendants
	_need_fcost_change       => 0,      # boolean

	@_,    # attribute override
    };

    return bless $self, $class;
        

lib/AI/Pathfinding/SMAstar/Path.pm  view on Meta::CPAN

		else{
		    $i++;
		}


		if($descendants_found == $num_successors){
                    # setting completed to 1.
		    $self->is_completed(1);
		}	

		$next_descendant = undef;  # found this one in list, so undef next descendant.
		
	    }
	    else{	    	
		# did not find descendant in descendant's list 

		if($i < $self->{_iterator_index} && $self->{_forgotten_nodes_num} != 0){
                    # did not find descendant in list, but may have already produced this 
		    # descendant since this node was created.
		    $i++;
		    $descendants_deleted++;

lib/AI/Pathfinding/SMAstar/PriorityQueue.pm  view on Meta::CPAN

	    while($compare_func->($obj, $best) || $compare_func->($obj, $succ) || $obj->has_descendants_in_memory()){		
		
		if($queue_key = $queue_keys_iterator->()){					    
		    $obj = $queue->lookup_by_key($queue_key);		
	       
		}
		else{
		    # need a new least_depth.  check if there are any more queues with non-zero depth in this tree.
		    # if not, need a new highest_cost_key.
		    $obj = undef;

		    my $next_smallest = $depth_keys_iterator->();
		    if(!defined($next_smallest)){
			last;
		    }
		    else{
			$least_depth = $next_smallest;
			$queue = $$avltree->get_queue($least_depth);  # get the queue at least_depth		
			$queue_keys_iterator = $queue->get_keys_iterator();
			$queue_key = $queue_keys_iterator->(); # burn the first value from the iterator		

lib/AI/Pathfinding/SMAstar/TreeOfQueues.pm  view on Meta::CPAN

use AI::Pathfinding::SMAstar::AVLQueue;


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

t/AI-Pathfinding-SMAstar.t  view on Meta::CPAN

diag("reading dictionary '$dictionary_file'");
eval{

    ($num_words, @words) = AI::Pathfinding::SMAstar::Examples::PalUtils::read_dictionary_filter_by_density($dictionary_file, $sparsity);
};
is( $@, '', '$@ is not set after object insert' );

diag("loaded words: '$num_words'");
isnt( $num_words, undef, 'num_words is $num_words');



%letter_freq = AI::Pathfinding::SMAstar::Examples::PalUtils::find_letter_frequencies(@words);


foreach my $w (@words){
    my $length = length($w);
    if($length > $max_word_length){
	$max_word_length = $length;