Hi James,
I have fixed some bugs and pushed the commit (K1) to my forked branch -- please review the changes when you have time.
2 of the fixed bugs are reported <a href="http://forum.simutrans.com/index.php?topic=2148.0">
here</a>. I also extended your approach to simline_t and simlinemgmt_t too.
Other bugs are :
(1)
In the original implementation in ST STD, calling
welt->set_schedule_counter() will rebuild destinations and re-route goods. Re-routing of goods has not been done in your new approach -- you only notify halts to reschedule and force paths stale, but you don't re-route existing ware packets. (See
convoi_t::set_schedule() if you are not sure what I mean.)
(2)
In the following part of code from
convoi_t::set_schedule() :
Quote
ITERATE_PTR(f, k)
{
tmp_halt = haltestelle_t::get_halt(welt, fpl->eintrag[k].pos, besitzer_p);
if(!tmp_halt.is_bound())
{
// Try a public player halt
spieler_t* sp = welt->get_spieler(0);
tmp_halt = haltestelle_t::get_halt(welt, fpl->eintrag[k].pos, sp);
}
if(tmp_halt.is_bound())
{
for(uint8 i = 0; i < anz_vehikel; i ++)
{
const uint8 catg_index = supported_categories;
tmp_halt->reschedule[catg_index] = true;
tmp_halt->force_paths_stale(catg_index);
}
}
}
You have mistakenly used
fpl instead of
f in the iteration body.
(3)
In the following part of code in
haltestelle_t::rebuild_connexions() :
Quote
// what goods can this convoy transport?
add_catg_index.clear();
for(uint i = 0; i < cnv->get_vehikel_anzahl(); i++)
{
// Only consider vehicles that really transport something
// this helps against routing errors through passenger
// trains pulling only freight wagons
const ware_besch_t* ware = cnv->get_vehikel(i)->get_fracht_typ();
if (cnv->get_vehikel(i)->get_fracht_max() == 0 || ware->get_catg_index() != category)
{
continue;
}
if(ware != warenbauer_t::nichts)
{
// now add the freights
add_connexion(ware, fpl, cnv, dummy_line);
if(!add_catg_index.is_contained(ware->get_catg_index()))
{
add_catg_index.append_unique(category);
}
}
}
add_catg_index[] is originally used in ST STD to prevent
hat_gehalten() [similar to
add_connexion() above] from being invoked on the same ware type more than once, by keeping track of what ware categories have been processed so far for the current convoy. But when you adapt the logic to your new pathing system, you have probably neglected its role, and have not checked against its contained categories before invoking
add_connexion(). So, if a convoy has 2 or more vehicles which can transport goods of the current
category,
add_connexion() will be invoked more than once with the same arguments.
I have added a
goods_catg_index[] array for convoi_t, much like in simline_t, to save the time of repeatedly iterating through the list of vehicles of a convoy to gather info regarding supported ware categories. With this change, I have also simplified
haltestelle_t::rebuild_connexions().
Besides, I have factored out the code for notifying halts to rebuild connexion, so that it now appears as a single function in haltestelle_t. This will make future modifications and maintenance of that code easier.
Edit : I have corrected a mistake and made another commit (K2).
Thank you for all of the code patches - they have now been incorporated into Simutrans-Experimental 3.12. I very much appreciate all the work!
At last, this problem (http://forum.simutrans.com/index.php?topic=1948.0) has been solved. Thank you Knightly.
Now we can compare Simutrans's routing and Simutrans Experimental's routing for the first time.
Hmm, Dante reports (here (http://forum.simutrans.com/index.php?topic=2301)) that 3.12 is a great deal slower than previous versions when making changes to stops and schedules, and I suspect that this patch is the cause. It might be necessary to give some consideration to letting any changes to paths/schedules wait until the next change of month to implement fully, or else it will be very frustrating for users on larger maps to have to wait seconds on end to be able to interact with the game after every change that triggers a recalculation...
James,
If my code works correctly (i.e. after applying the fixes), players should experience similar UI responsiveness as in v3.11 (except for lineless convoys), because in v3.11 changes to lines are made by calling welt->set_schedule_counter(), which means all connexions and all paths will be rebuilt upon any change to lines -- that is in fact even less efficient than in my code.
Personally, I object to any attempt to reduce the game's responsiveness to changes in transport network. What good is a pathing system which does not respond adequately to changes in transport network within a reasonable time frame? If I have to wait for 2 months to see the changes happen, I will not play ST EXP anymore. If you reduce responsiveness to tranport network changes because the game is running slowly, I would suggest you to revert to ST STD's pathing system instead.
It seems to me that you are trying to avoid the problem of slowness in path searching by doing it only bi-monthly and by thinking of reducing responsiveness to transport network changes, instead of tackling it. If the game becomes very slow during path searching, probably there aren't enough calls to INT_CHECK() in appropriate places in your path searching code. By path searching code, I mean not only calculate_paths(), but also get_path_to(), find_route() and any helper function. I think the proper direction is to make it such that even if all paths become stale and need to be recalculated, UI response will be acceptable to players while the game is performing intensive path searching. If you can't achieve that, I would suggest you to revert back to ST STD's pathing system.
Knightly,
if it is possible to have the level of UI responsiveness of 3.11 with the immediate routing accuracy of 3.12, that would indeed be the best of both worlds, and is to be preferred. However, the issue with Simutrans-Standard's routing was not that it responded slowly, but that the actual method for choosing a route did not depend on which route was the fastest, so it does not make sense to suggest that making things faster at the (limited) expense of short-term routing accuracy is equivalent to using the very different route searching system in Simutrans-Standard.
I did, as you may have noticed, add an interrupt check to the calculate paths routine - if you think that they should be added in other places to improve responsiveness during the path search, then I should be very interested in your views on that matter. Certainly, anything to improve responsiveness during the searching routine would be very much welcomed!
James,
What I mean by reverting back to ST STD's pathing system is not to eliminate the calculation for journey times, waiting times, etc. I only mean to drop Dijkstra's Algorithm and stop storing paths, and to calculate path whenever it is requested, just as in ST STD. Currently, ST STD's search algorithm only consider the number of transfers, but it can also be adapted to calculate journey time from origin.
But wouldn't the amount of processing power required to do that make the game too unresponsive if the results were not cached?