Hi James,
I have checked and it is the following part of your code which should be called the relaxation phase, where next nodes are expanded :
while(iter.next() && iterations <= max_iterations)
{
const halthandle_t h = iter.get_current_key();
if(paths[category].get(h).journey_time != 65535)
{
// Only insert into the open list if the
// item is not already on the closed list.
continue;
}
connexion* current_connexion = iter.get_current_value();
path_node* new_node = &path_nodes[iterations++];
new_node->halt = h;
new_node->journey_time = current_connexion->journey_time + current_connexion->waiting_time + current_node->journey_time;
new_node->link = current_node;
open_list.insert(new_node);
}
And my suggestions above refer also to this part. Line/convoy switch check has to be done here (i.e., before new nodes are created) if you want to avoid all the toil as well as bloated memory consumption and unnecessary proliferation of nodes, as mentioned above. We should weigh this check against a series of actions : new node + node initialization + storing in heap + popping out of heap + checking in closed list. And this weighing should be considered in light of the frequency of nodes that could be discarded earlier by such check, and IMHO a fairly significant proportion of nodes would fall within this group.
You don't need to get the full sequence/path -- just follow the link of the current node back to its predecessor and find out the best line/convoy between them, and compare it against the best line/convoy from current node to the next node. In this way, all your paths will contain *real* transfer stations only.
You don't need to determine the best line/convoy of the previous connexion for every adjacent node of a current node. You can look up the best line/convoy *once* right before entering the relaxation iteration quoted above, and then reuse it in checking (i.e. comparing between previous best line/convoy and current best line/convoy) within the iteration. The checking itself should not be very expensive; it is determining the previous best line/convoy which is more expensive, but then it is performed *only once* per examined (current) node in my approach. As explained below, such determination of best line/convoy could be done more than once per examined node with your current implementation.
The reason why it is now much slower is because you try to determine line/convoy switch in the part of code which is originally intended for finding the next immediate transfer station in a path (relevant code below). Consider this scenario : A > B > C > D > E > F. A path ending at C would entail finding the best line/convoy between B > C and A > B; at D, between C > D, B > C and A > B; at E, between D > E, C > D, B > C and A > B; at F, between E > F, D > E, C > D, B > C and A > B. You can see clearly there are *numerous* redundant determination of best line/convoy as well as redundant checks. The deeper the search goes, the more serious the redundancy. Such redundancies could be avoided if you adopt my approach : for each edge between 2 nodes (current node examined and its predecessor), the best line/convoy is determined only once.
for(uint8 depth = 0; depth <= 255; depth ++)
{
if(track_node->halt.is_bound())
{
#define AVOID_ROGUE_VIAS
#ifdef AVOID_ROGUE_VIAS
if(track_node->link->halt.is_bound())
{
const quickstone_hashtable_tpl<haltestelle_t, haltestelle_t::connexion* > *tmp_table = track_node->halt->get_connexions(category);
const connexion* tmp_con = tmp_table->get(track_node->link->halt);
convoihandle_t tmp_convoy;
linehandle_t tmp_line;
if(tmp_con != NULL)
{
tmp_convoy = tmp_con->best_convoy;
tmp_line = tmp_con->best_line;
}
current_best_convoy = tmp_convoy;
current_best_line = tmp_line;
}
if(current_best_convoy != previous_best_convoy || current_best_line != previous_best_line)
{
// Prevent transfers within the same line or convoy.
#else
if(track_node->link->link == NULL)
{
#endif
paths[category].access(current_node->halt)->next_transfer = track_node->halt;
//path tmp = *paths[category].access(current_node->halt);
//tmp.next_transfer = track_node->halt;
//tmp = NULL;
}
if(track_node->link->link == NULL)
{
// End of search.
break;
}
previous_best_convoy = current_best_convoy;
previous_best_line = current_best_line;
}
track_node = track_node->link;
}
Actually this is not necessary if you have already incorporated line/convoy switch check in your path finding code, for all nodes on a path should now be *real* transfer stations already. My previous suggestion only targets v2.5.
As for the memory leak which I have spotted, I am glad to see that you have adopted my suggestion to clear the open list and delete the path_nodes as soon as the search is determined to be complete :
// If the code has reached here without returning, the search is complete.
search_complete = true;
open_list.clear();
delete[] path_nodes;
However, as I have also suggested to you, you will also need to check for search completeness here :
if(current_node->halt == goal)
{
// Abort the search early if the goal stop is found.
// Because the open list is stored on the heap, the search
// can be resumed where it left off if another goal, as yet
// not found, is searched for, unless the index is stale.
return;
}
It is possible that the successful target is found in the last possible iteration (as determined by max_iterations) or that it happens to be the last object in the open list. The resulting problem would be
(1) memory leak, if the open list has just exhausted and the path_nodes are displaced by newly allocated nodes when calculate_path() is called again;
(2) try to resume a completed search -- this is a relatively minor problem, but would still be better to fix it
So, I suggest to delete the path_nodes if open list is empty at that point; and clear both open list and path_nodes if max_iterations has been reached.
Finally, just 2 small optimization suggestions :
(1) Some local variables declared inside the loops could be declared before and outside the loops they reside, unless you think that it is a must to use const in variable delaration. E.g. current_node, current_connexions, current_connexion, new_node and even halthandle h (IMHO it is not necessary to declare h with const). If you declare them within the loop, they will go out of scope and be destroyed at the end of each iteration, and will get recreated in the next iteration. IMHO such unnecessary creation and destruction of the same variables should be avoided to save processing time -- they may seem trivial to you, but consider the number of such variables x the number of iterations done, the combined processing time involved might not be as trivial as you think.
(2) Temporary variables which are used only once may simply be dropped unless combining statements causes serious readibility problem. E.g. current_connexions in line 1491.
I hope you will seriously consider my suggestions above.
Edit : 2 quotations of James' previous post were previously misplaced and are now put back in the right place. There are also some additions and modifications to the text.
Topic: [New release] Simutrans-Experimental 2.4 (Read 10353 times)
previous topic - next topic
