view release on metacpan or  search on metacpan

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

#-----------------------------------------------------------------------------
sub get_descendants_iterator_smastar
{
    my ($self) = @_;
    
    my $depth = $self->{_depth};
    my $iterator;
    my $num_successors = 0;
    my $next_descendant;

    # if we haven't counted the number of successors yet,
    # count and record the number, so we only have to do
    # this once.
    if(!defined($self->{_num_successors})){

	$num_successors = $self->get_num_successors();

	$self->{_num_successors} = $num_successors;	

	$#{$self->{_descendants_produced}}  = $num_successors;
	$#{$self->{_descendant_fcosts}}     = $num_successors;
	$#{$self->{_forgotten_node_fcosts}} = $num_successors;

	for (my $i = 0;  $i <= $num_successors; $i++){
	    $self->{_descendants_produced}->[$i] = 0;
	    $self->{_descendant_fcosts}->[$i] = -1;
	    $self->{_forgotten_node_fcosts}->[$i] = -1;
	}
    }
    else{
	# if number of successors has already been recorded, update 
	# num_successors variable with stored value.
	$num_successors = $self->{_num_successors};	
    }
	
    return sub{	
	my $i = 0;
	
        # entering get_descendants_iterator_smastar() sub	
	$iterator = $self->get_successors_iterator();

	my $descendants_deleted = 0;
	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};
	    
	    my $already_produced_p = $self->{_descendants_produced}->[$i] || ($self->{_descendant_fcosts}->[$i] != -1);
	    

	    if($already_produced_p){
		# have already produced this descendant
		$descendants_found++;
                # found descendant in tree\n";		

		if($i == $num_successors - 1 && $descendants_deleted){
		    # !!! resetting iterator index. descendants have been deleted. clearing forgotten_fcosts on next expansion.
		    $iterator = $self->get_successors_iterator();
		    $self->{_iterator_index} = 0;
		    $i = 0;		

                    # setting completed to 1 (true)
		    $self->is_completed(1);	    		    
		    next;
		}
		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++;
		    next;
		}		
                # did not find descendant in list, adding now.

				
		$next_descendant->{_descendant_index} = $i;
		$self->{_descendants_produced}->[$i] = 1;
                # new descendant's index is $i

		
		$self->{_iterator_index} = $i + 1;
		
		if($self->{_iterator_index} == $self->{_num_successors}){
		    $iterator = $self->get_successors_iterator();
		    $self->{_iterator_index} = 0;
		    $i = 0;
		    	

		    # node is completed, setting completed to 1\n";