AI-Pathfinding-SMAstar

 view release on metacpan or  search on metacpan

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

184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
        ) = @_;
 
    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

210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#
#
#################################################################
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

280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
        $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

340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
            $$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

232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
#
# 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

206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
      
    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

289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
 
 
 
 
 
#-----------------------------------------------------------------------------------------------
#
# 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;
        }