[Bug v3.8] IF conditions in haltestelle_t::calculate_paths()

[knightly]

2 minor bugs :

(1)
In the following parts of code :

   while(open_list.get_count() > 0 && iterations < max_iterations)
   {   
      current_node = open_list.pop();

and

         if(open_list.empty() || iterations == max_iterations)
         {
            open_list.clear();
            delete[] path_nodes;
            search_complete = true;
         }
         return;

as well as

   // If the code has reached here without returning, the search is complete.
   search_complete = true;
   
   open_list.clear();
   delete[] path_nodes;
}

The expressions/statements in blue should be dropped, because even if max_iterations is reached, the search is not complete yet, as the nodes in open_list should still be processed -- they might be valid routes which should be added to paths[c]. Max_iterations is only responsible for controlling the number of nodes created, and it is not needed for checking completeness of search. If no new nodes are created, the open_list will quickly become empty and the search will stop.


(2)
In the code below :

      while(iter.next() && iterations <= max_iterations)
      {
         next_halt = iter.get_current_key();
         if(paths[category].get(next_halt).journey_time != 65535)
         {
            // Only insert into the open list if the
            // item is not already on the closed list.
            continue;
         }

The green expression should be iterations < max_iterations instead, otherwise it is possible to walk past the upper boundary of path_nodes[].



Edit 1 :  Point (1)

Edit 2 :  As a side note, James, I have added 2 points in <a href="http://forum.simutrans.com/index.php?topic=2068.msg22024#msg22024">this thread</a>. Please take a look. Thanks!

[jamespetts]

Since, if I take your suggestion about memory pools in the other thread, some of this might well be changed, I'll keep this one on hold for now - but, as ever, thank you very much for spotting it!

[knightly]

James, I would suggest you to fix this bug first, for I suppose there won't be significant change to the logic flow of calculate_paths() itself. Besides, it's always a good idea to start implementing your new system from a version that contains as few bugs as possible, so that when you really need to make modifications, you can better determine how the change should be made. A bug in the old system can potentially mislead you into introducing a new bug in your new system.

[jamespetts]

One question about the first point - there are a number of places where you suggest removing the lines clearing the open list, but retaining the lines deleting path nodes. Would that not lead to errors if items in the open list ended up pointing to things that had been deleted?

[knightly]

James,

Regarding this :

         if(open_list.empty() || iterations == max_iterations)
         {
            open_list.clear();
            delete[] path_nodes;
            search_complete = true;
         }
         return;

open_list.clear() can be removed, because the body of IF will only be executed when open_list.empty(), since the 2nd expression will be deleted.


As for this :

   // If the code has reached here without returning, the search is complete.
   search_complete = true;
   
   open_list.clear();
   delete[] path_nodes;
}

This part of code will execute only when open_list is empty, because the check for max_iterations has already been removed (pls see the first code block in my 1st post above).

In both cases, it's redundant to clear an empty open list, isn't it?

[jamespetts]

Ahh, yes. You're right again