AI-Pathfinding-SMAstar

 view release on metacpan or  search on metacpan

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

	) = @_;

    if(!defined($str_function)){
	croak "SMAstar start_search:  str_function is not defined.\n";
    }

    sma_star_tree_search(\($self->{_priority_queue}), 
                         \&AI::Pathfinding::SMAstar::Path::is_goal, 
                         \&AI::Pathfinding::SMAstar::Path::get_descendants_iterator_smastar,
                         \&AI::Pathfinding::SMAstar::Path::fcost,
			 \&AI::Pathfinding::SMAstar::Path::backup_fvals,
			 $log_function,
			 $str_function,
			 \&AI::Pathfinding::SMAstar::Path::progress,
                         $self->{_show_prog_func},
			 $max_states_in_queue,
                         $max_cost,
	);
}

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

#
#
#################################################################
sub sma_star_tree_search
{
   
    my ($priority_queue,
	$goal_p,
	$successors_func,
	$eval_func,
	$backup_func,
	$log_function, # debug string func;  represent state object as a string.
	$str_function,
	$prog_function,
	$show_prog_func,
	$max_states_in_queue,
	$max_cost,
	) = @_;
    
    my $iteration = 0;
    my $num_states_in_queue = $$priority_queue->size();

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

			$succ->{_f_cost} = $max_cost;                                                    
		    }                                                                             
		    else{                 
			# calling eval for comparison, and maintaining pathmax property		
			$succ->{_f_cost} = max($eval_func->($succ), $eval_func->($best));	
			my $descendant_index = $succ->{_descendant_index};
			$best->{_descendant_fcosts}->[$descendant_index] = $succ->{_f_cost};
		    }           
		}

		# determine if $best is completed, and if so backup values
		if($best->is_completed()){


		    # remove from queue first, back up fvals, then insert back on queue. 
		    # this way, it gets placed in its rightful place on the queue.		    
		    my $fval_before_backup = $best->{_f_cost};
		   
		    # STEPS:
		    # 1) remove best and all antecedents from queue, but only if they are 
		    #    going to be altered by backing-up fvals.    This is because 
		    #    removing and re-inserting in queue changes temporal ordering,
		    #    and we don't want to do that unless the node will be
		    #    placed in a new cost-bucket/tree.
		    # 2) then backup fvals
		    # 3) then re-insert best and all antecedents back on queue.


		    # Check if need for backup fvals		    
		    $best->check_need_fval_change();
		   
		    my $cmp_func = sub {
			my ($str) = @_;			
			return sub{
			    my ($obj) = @_;
			    my $obj_path_str = $str_function->($obj);
			    if($obj_path_str eq $str){
				return 1;
			    }

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

				$$priority_queue->remove($antecedent, $cmp_func->($path_str));  	
			    }
			    $antecedent = $antecedent->{_antecedent};
			    $i++;
			}
		    }
		    
	
		    #   Backup fvals
		    if($best->need_fval_change()){
			$best->$backup_func();			
		    }

		    
		    # Put everything back on the queue
		    if($best->need_fval_change()){
			$$priority_queue->insert($best);
			my $antecedent = $best->{_antecedent};
			my $i = 0;
			while($antecedent){
			    if($was_on_queue{$i} && $antecedent->need_fval_change()){  

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

#
# used for A* search.
#
sub evaluate
{    
    my ($min_num_letters) = @_;
    return sub{
		
	my ($self) = @_;

	# if fcost has already been calculated (or reassigned during a backup)
	# then return it.   otherwise calculate it
	my $fcost = $self->{_f_cost};
	if(defined($fcost)){	    
	    return $fcost;
	}

	my $word = $self->{_start_word};
	my $cost = $self->{_cost};
	my $cost_so_far = $self->{_cost_so_far};
	my $num_new_chars = $self->{_num_new_chars};

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

    
    return $iterator;    
}


    
    

#-----------------------------------------------------------------------------------------------
#
# Check whether we need to backup the fvals for a node when it is completed (recursive)
# Sets flags throughout path object's lineage, indicating whether fvals need to be updated.
#
#-----------------------------------------------------------------------------------------------
sub check_need_fval_change
{
    my ($self, $descendant_fcost, $descendant_ind) = @_;
 

    my $descendant_index = $self->{_descendant_index};

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

#-----------------------------------------------------------------------------------------------
#
# Backup the fvals for a node when it is completed.
#
#-----------------------------------------------------------------------------------------------
sub backup_fvals
{
    my ($self) = @_;
    
    while($self){
	
	if(!$self->is_completed()){
            # node not completed, return
	    return;
	}