News:

Simutrans Tools
Know our tools that can help you to create add-ons, install and customize Simutrans.

[New release] Simutrans-Experimental 2.4

Started by jamespetts, April 19, 2009, 12:01:34 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

jamespetts

Thank you once again to all of the Simutrans-Experimental beta testers. This release focusses on fixes to the GUI, although also fixes a bug spotted by Knightly recently. Also, the latest (as of yesterday) version of Simutrans-Standard has been merged, with all of the fixes to the trunk now available in Simutrans-Experimental, too.

Changes


  • FIX: Goods and passengers are correctly grouped and sorted in the stop and convoy dialogue boxes
  • CHANGE: The "list of all goods" now reflects the new revenue system. (Known issue: the sorting by revenue does not always work properly).
  • FIX: The convoy dialogue boxes would resize incorrectly after the chart had been displayed and turned off again.
  • FIX: When starting from a depot, a convoy's average speed might be set incorrectly.

Feedback and testing

As ever, I should be very grateful for any feedback on this release; thank you to all those who have contributed feedback to previous releases. Although I have not answered all of the posts (because I have been focussing on the GUI fixes for this release), I will get around to that in due course. I should be particularly interested in feedback on the new routing system, the new revenue system and overall performance. Thank you again to the beta testers - your work is most invaluable.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

knightly

#1
Thanks for your great efforts, James :)

I noticed something strange : I started a new game, picked one town and set up a bus line with several stops and one bus. Since there was only one line in the whole map, there shouldn't be any pax transfer point. However, please see the attached image. Is this intended?

Edit 1 : Updated text and image

Edit 2 : The game crashed after a short while. Reloading save game eliminates the problem. This problem is probably caused by adding new stops to an existing line.




Edit 3 : Regarding replacing vehicles, "Full Replace" and "Replace but Stay" do not automatically send vehicles to depot when all pax are unloaded. Besides, when the vehicle enters the depot, the game crashes if its vehicle window is open.


z9999

Quote from: Knightly on April 19, 2009, 02:55:33 AM
I noticed something strange : I started a new game, picked one town and set up a bus line with several stops and one bus. Since there was only one line in the whole map, there shouldn't be any pax transfer point. However, please see the attached image. Is this intended?

I also have similar question about transfer station.
I made A-B-C-D-C-B-A for bus, and A-D for goods.
Then people want transfer at C ?
Information window tells so.

jamespetts

Thank you everyone for your prompt and very helpful replies and bug reports. I will deal with each issue in turn.

1. Vehicle replacing not working

This was caused by some missing code, and also affected "retiring" vehicles. I have now fixed that in my latest code, which should be incorporated into the next release.

2. Game crashes when the vehicle window is open and the vehicle is replaced

This is quite a hard one to solve: the problem originates because the vehicle window keeps updating the little map display in the top right hand corner showing where the vehicle is: once the vehicle goes into the depot to be replaced, the convoy is deleted, so the memory in which the position of the convoy would be stored is deallocated, and an access violation results when the window tries to read it. The difficult bit is finding a way of telling the window that the convoy has been deleted, and that it should close down. I shall have to look into that one further.

3. Adding new stops to an existing line causes crashes and freezes

I was able to reproduce this one: the exact cause of the problem was unclear: it seems as though there might be a bug with the included singly linked list iterator template class. In any event, refactoring the collection of all goods and passengers travelling on vehicles ("fracht") from a singly linked list to a vector solved this problem. The fix will be included in the next release.

4. Passengers and goods go via an intermediate stop when their destination is served by the the current convoy

This is a subtler problem than at first appears, but also it is less significant than first appears. What happens is that the route finding system tries to calculate the shortest route in terms of journey time from the origin to the destination. That takes into account both travelling time and waiting time. So, if, for example, you have three stops, A, B and C, and one line serving each of them, the following is possible:

Stop A
DESTINATION      TRAVELLING      WAITING
         B                    5mins           5mins                 
         C                    10mins         20mins

Stop B
DESTINATION      TRAVELLING      WAITING
        A                     5mins          10mins
        C                     5mins          5mins

The total travel time of going directly from A > C is therefore 30 minutes (10 travel plus 20 waiting). The total travel time of going from A > B > C is calculated at 20 minutes (5 waiting plus 5 travelling from A to B, plus 5 waiting plus 5 travelling from B to C). So, the route finding engine will record A > B > C as quicker than A > C, and route all goods/passengers going from A > C via B.

If there is only one line, one might ask, why are there different waiting times? The reason for that is that waiting times are counted from when each packet arrives at the stop. Because the arrival times are essentially random, the waiting times cannot be calculated precisely. Over time, they will tend to average towards a meaningful figure, but can be some way off if the stop is seldom used. I cannot simply aggregate all waiting times for a single line, since there might be cases in which going from A > C on line 1 is slower than going from A > B on line 1, and B > C on line 2 (for example, if line 1 takes a circuitous route - this result would not be achieved using the routing method from Simutrans-Standard). It is not possible easily to detect whether the goods/passengers will simply continue on the same convoy/line at the next stop, since it is only when they get to the next transfer that they check to see which line/convoy that they should be getting from there. It is quite possible that, in the meantime, things will have changed, and the goods will take a different convoy from B than they would have done if that were calculated when they boarded at A.

To reduce the impact of this, waiting times are automatically treated as half as long as travelling times (to take into account the fact that, in reality, there are timetables, and passengers are able to arrive mostly shortly before a service leaves, rather than turning up at random). Also, in the next version, I have set the minimum waiting time to 1 minute (rather than allowing it to be at 0 minutes as in 2.4) to reduce the chances of routing over intermediate stops when there is no time advantage of doing so.

The practical effect, however, of goods/passengers going from A > B > C on a single line rather than going from A > C on that line is not much different: they do not unload at B, but remain on the vehicle, and behave just as they would if they had gone from A > C directly. The only thing affected in that case is the appearance. For that reason, the problem is less significant than at first appears. In some marginal cases, the waiting times can be so high at infrequently served stops, that passengers or goods actually take detours on the same route because it is calculated as being quicker. I cannot immediately think of a way to alter the code to prevent that from happening, but it seems to occur mainly when there is a long route with many intermediate stops and an infrequent service.

I hope that this is helpful. Thank you all for testing this - it is very much appreciated.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

knightly

Thanks for your detailed explanation.

1) May I know whether travelling time and waiting time are calculated *per line* for each connection between 2 stops? And is travelling time affected only by those pax starting from X and ending at Y, but not by those whose route covers X and Y (i.e., pax who don't get on/off at X and/or Y)?

2) Since with your implementation, not only transfer stations, but also intermediary stops may get registered on the pre-calculated route, so when passengers arrive at the next immediate goal, how do they determine whether they should stay on the vehicle, or get off to wait for another vehicle of another line going to the same destination? If a line serves A > B > C and another line serves B > C but faster, such decision may be needed. And, if they get off and wait, how do they know which vehicle to get on later?  Is line info stored in each leg of the pre-calculated route?

3)
Quote from: jamespetts on April 19, 2009, 03:30:21 PM
The total travel time of going directly from A > C is therefore 30 minutes (10 travel plus 20 waiting). The total travel time of going from A > B > C is calculated at 20 minutes (5 waiting plus 5 travelling from A to B, plus 5 waiting plus 5 travelling from B to C). So, the route finding engine will record A > B > C as quicker than A > C, and route all goods/passengers going from A > C via B.

Isn't it that only waiting times at origin station and transfer stations should be counted? For A > B > C, if the route is achieved by a single line, the total journey time should be 15mins = (5min waiting at A + 5min travelling from A to B + 5min travelling from B to C).

4) I really hope that the "via stations" displayed are transfer stations just as before. It is useful to see how many pax want to route via those transfer stations, and info on how many pax "route" via the next intermediary stop isn't useful at all.

jamespetts

1. Travelling time is computed per convoy. Each convoy registers its arrival time at each stop. At the next stop, it checks to see how much time has elapsed, and how much distance is covered, and calculates the speed. This is then averaged together with all other such recorded speeds for that month, which can be seen on the average speed display on the convoy's graph. For lines, the average speed is aggregated for the convoys. So, if there are three convoys serving a line, with average speeds of 10, 15 and 20 respectively, the average speed for that line will be 15.

The journey time is, in turn, calculated by dividing the total route distance by the average speed of the line or convoy. The line or convoy with the lowest journey time is the one whose journey time is recorded and used for route finding purposes. Also, passengers or goods that care about their timings (i.e., those with a speed bonus rating of > 0%) will wait for a while to try to board that fastest line or convoy, and will not board other, slower lines or convoys, even though they will get them to their destination. After waiting for a while, however, they will board anything that will take them to where they are going.

The waiting time, however, is calculated differently. Each packet of goods and passengers registers an arrival time whenever it arrives at a station, either by being unloaded, or by arriving from a town or factory. Whenever that packet is merged with another packet, it calculates the total aggregate waiting time of the two. For example, if one packet of 10 passengers that arrived at 100 ticks is merged with another packet of 10 passengers that arrived at 200 ticks, there would be a new packet of 20 passengers deemed to have arrived at 150 ticks. Similarly, if one packet of 5 passengers arrived at 100 ticks, and another packet of 10 passengers arrived at 200 ticks, there would be a new packet of 15 passengers deemed to have arrived at 175 ticks.

Whenever a packet of goods or passengers boards transport, the total waiting time is added to a list of the last 16 waiting times for that cargo type to that destination. Whenever an average waiting time is needed, the last 16 waiting times are added together and divided by 16 to produce a mean average waiting time. All times are recorded in 10ths of minutes, although the display shows whole minutes only. As of the next version, the minimum waiting time will be fixed at 10 10ths of a minute (it is 0 10ths in version 2.4).

2. Although I had originally planned to have a whole list of transfers stored with each packet, I realised when I was implementing the system that that was not necessary, and it was perfectly possible to retain the current system. Therefore, the only stops of which any packet of goods or passengers knows is (1) its origin; (2) its destination; and (3) its next transfer.

When a packet arrives at the next transfer, goods are first unloaded, then loaded. Anything with a next transfer on the same line, therefore, is re-loaded straight away if the current convoy is the fastest way of getting them there. If it is not, then, as stated above, the fastest line or convoy to get to each next transfer is stored at each halt. So, if a different line or convoy will get passengers or goods there faster (and they are of a type that cares about speed), then they will wait for that one instead of getting straight back on the one on which they arrived.

3. It is only waiting times at origin stations and transfer stations that are counted. The system checks to see whether a journey to B  plus a journey to C has a less overall time (travel + waiting) than a journey straight to C. If it does, it decides that it should set B as the next transfer. It ignores intermediate stations that are not transfers.

4. It would indeed be good to be able to do this, but I cannot currently think of a sensible way of achieving this.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

knightly

#6
Thank you for your time in explaining.

The problem is, in your system, a "transfer station" may not necessarily mean a transfer station in the original sense where a switch of line or convoy is needed.

As in the case where there is only a single line serving 2 stops, an intermediary stop may also become a "transfer stop" in your implementation, and the waiting time at that "transfer stop" is also counted in your route search, because your route search probably does not check whether there is a switch of line or convoy -- please correct me if I am wrong in this conjecture.

As for getting off the vehicle and boarding it again for the same best line, apart from being unrealistic, I suppose not all the unloaded pax may be able to board this vehicle again, because there may be many more pax who has been waiting to board this vehicle at the stop. Probably you may want to check whether the next best line is the current line first before unloading those pax.

Since your system already have the best line/convoy registered alongside the shortest travel time, probably you can incorporate checking of line/convoy switch in your route search :

(A) For each node searched, store not only the accumulated journey time and predecessor node, but also the fastest line/convoy that connect this node and its predecessor node, as well as a transfer counter. Then any switch in line can be detected along route search, and increment the transfer counter. In this way your search can be limited to the transfer limit specified in simuconf.tab, and you will be able to identify the real transfer station for storage in ware_t.

(B) Besides, if X > Y and Y > Z are connected by the same best line, there is no need to perform relaxation on Z while processing Y -- X > Z will be considered anyway, so a route check from X via Y to Z is unnecessary. This completely avoids having an intermediary stop being treated as a transfer stop. In fact, if this is done, every next node must be connected with a different line/convoy, and thus the transfer count (which should be initialized to -1 at source node, and will become 0 at the next immediate node) can be incremented without further comparison between previous connections.

I don't how if this approach would adversely affect performance and menory consumption, but it is a plausible way to eliminate various problems with your current implementation.

jamespetts

Knightly,

thank you for your suggestions :-) What I think that I can try to do is, during the relaxation phase, check whether each link has the same best line or convoy as each previous link. Although that will undoubtedly impact on performance, the relaxation phase is far less processor intensive than the main search phase, and I am very reluctant to add any new fields to the nodes so as not to overdo the memory consumption.

That will not stop intermediate stops being used as transfers where the best convoy or line from B to C is different to that from A to B (but it should not do that in any event, since there are situations where, for example, passengers at a minor station will catch a local train to a nearby major station and then change for an express to the next major station, even though they could just remain on the local train for the whole journey, as the former is faster), but should prevent passengers immediately alighting and re-boarding the same convoy again as they do now. It should also remove the confusing "via"s in the convoy's dialogue box.

This may or may not work, and may or may not make it to the next version, but watch this space :-)
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

knightly

Thanks a lot for your consideration, James :)

If I do not get you wrong, you are saying that you can do the check for line/convoy switch without storing the line/convoy in the search node. If this can be done, that's great. ;) With this change, each node in the searched route will always be transfer stations, and the next node from source is always the next immediate transfer station (unless it is already the destination).

But probably, you won't be able to limit the max number of transfers without introducing any variable in the search node? There is merit to having this limit, as pax usually won't accept changing transport so many times to go to a certain destination. Thus, maybe you can reconsider adding a signed 8-bit integer to the search node for storing the number of transfers so far? As mentioned above, you only need to initialize it to -1 at source node, then increment it by 1 during the relaxation phase.

BTW, may I know what is actually stored in the hash tables of each halt? The whole route? Or just the next immediate transfer stop? And under what conditions will a searched route become stale? Thank you very much in advance for your patience!

jamespetts

I think that I can do it without storing the switch in the search node, yes. Setting a hard limit for maximum transfers is not possible without adding extra data to the nodes (or possibly a counter to the relaxation phase, but that would then require invalidating a route that has already been found): the "max transfers" setting is now instead used as a way to limit the search depth, performing its intended function as a way to limit the amount of CPU time spent on searching. The routes that it will produce will approximately tend to have that maximum number of transfers (being closer to that number the more equal that the journey times of each transfer is). Given that waiting times are counted in journey times, which will discourage unnecessary transfers, I do not think that there would be great benefit in making the search slower just to add a precise calculation of maximum transfers.

There is more than one table in each halt. There is a hashtable of "connexions", which stores each halt to which the present halt has a direct connexion, along with the best convoy or line, and the journey time. That data is used in the pathfinding algorithm, in displaying the "direct connexions" in the halt details window, and for checking the best line or convoy for arriving passengers or goods routing onwards. There is a hashtable of "paths", which stores each halt which is ultimately reachable from the halt in question, together with the next transfer and overall journey time (including waiting times at transfers). This is what each ware_t instance looks for when it tries to find a path. If there is no path in the hashtable and the search is not marked as complete, or the routes are marked as stale, the search algorithm will run again and check to see whether a path can be found.

Finally, there is a table of waiting times, one for each type of goods and next transfer, which contains a list of the last 16 waiting times of goods/passengers boarding transport bound for the transfer in question. Whenever the average waiting time needs to be computed, the 16 values will be added together and divided by 16 to produce a mean average.

Of all of those tables, only the waiting times are saved when the game is saved. The others are recalculated when the game is re-loaded, as they are deterministic.

Both the connexions and the paths can become stale. They can be set to be made stale in a number of different conditions. Firstly, after a lapse of time: paths and connexions are configured to become stale in alternating months, to ease the load on recalculation. Secondly, if a halt is deleted, all the connexions and paths need to be recalculated, since all references to the deleted halt need to be removed. If schedules are changed, all the paths and connexions served by both the old and new versions of the schedule need to be re-set.

The paths/connexions will not recalculate immediately on becoming stale, however: they will wait until the next time that they are requested before recalculating, to spread the load somewhat. Furthermore, the search algorithm will stop part-way through when it has found the stop for which the current packet is looking, but will remember its position, and resume where it left off if another packet wants another destination not already found by the algorithm. That way, the processing time for re-setting the connexions is spread as evenly as possible.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

knightly

#10
Thanks a lot for your detailed explanation. For max transfer, I agree with you that waiting times at transfer stations constitute a significant enough penalty as well as disincentive to creating networks with too many transfers.

I have spent some time to read your code in calculate_paths(). With your current implementation which does not check for a switch of line/convoy, there will really be an unneccessary proliferation of nodes (if you look into the binary heap during runtime, there will probably be many duplicated nodes from the same line, especially when there are many stops in the lines), causing many duplicated nodes to be created, stored in binary heap and processed.

If line/convoy switch check is implemented, quite some memory would be saved, processing iterations could be reduced, and searching would be much faster. IMHO, the savings in memory and processing time would likely outweigh the seemingly-expensive check of line/convoy switch. And we should not forget that it solves the various problems associated with treating intermediary stop as transfer stop, as mentioned above.

If one single change can enhance both underlying processing and player experience, IMHO it really worths to pay the extra cost of this change. After all, everything comes with a cost, and we can't always expect improvements without any sacrifice, can we?

Edit :

Not to mention bloated memory consumption, the total processing time incurred in creating path node, initializing, performing relaxation, adding to open list, popping out of open list, and checking against closed list, is far more than the processing time of a single check of line/convoy switch in the first place and abandon a meaningless path right away. And no matter how expensive such early check may seem, the processing time saved should more than compensate for the increase in processing time involved with the check. After all, a check has to be done in the end anyway, so why not perform the check earlier to save all the toil?

jamespetts

Knightly,

thank you very much for your helpful analysis and suggestion - I have incorporated that into the latest release, version 2.6, which is out now. I have also implemented the system for ensuring that there are no transfers on which goods or passengers take the same convoy out as they do in, which seems to work, although also seems to make the game run more slowly at the beginning of every other month when the routes are recalculated. I should be interested in your comments on this aspect of things.

I had to add that in the relaxation stage, however, since it is not possible during iteration through the open list to know what route will actually be selected: there is no way of getting a sequence in the open list until the destination is reached. In addition, adding extra checks at the open list stage would mean that the checks are called many times more often than they would be at the relaxation stage. If I have missed a possibility, however, do let me know; perhaps you could write the code and test it for speed against my version? If it works and it's faster, I'll use it.

Thank you again for all your helpful testing and suggestions - it has been most useful!
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

knightly

#12
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.

Quote from: jamespetts on April 23, 2009, 09:17:42 PM
I had to add that in the relaxation stage, however, since it is not possible during iteration through the open list to know what route will actually be selected: there is no way of getting a sequence in the open list until the destination is reached.

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.

Quote from: jamespetts on April 23, 2009, 09:17:42 PM
In addition, adding extra checks at the open list stage would mean that the checks are called many times more often than they would be at the relaxation stage.

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.

Quote from: jamespetts on April 23, 2009, 09:17:42 PM
although also seems to make the game run more slowly at the beginning of every other month when the routes are recalculated.

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;
      }


Quote from: jamespetts on April 23, 2009, 09:17:42 PM
I have also implemented the system for ensuring that there are no transfers on which goods or passengers take the same convoy out as they do in

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.

jamespetts

Knightly,

thank you very much for your detailed replies, and for your continuing efforts to help to optimise Simutrans-Experimental: I very much appreciate the effort. Apologies if I do not always respond fully or swiftly - there is a great deal of information to digest!

Firstly, thank you for your memory optimisation suggestions, which have been included, as you point out, in 2.6. I had not realised that you had also suggested checking for completeness on returning having found the goal: I shall have to put that in in the next version.

Secondly, I have been trying to understand how to implement the checking in the open list iteration portion as you suggest - I will have a go at doing that for the next version. My current version is very slow, so any possibility of optimisation ought be seized! I will use conditional compilation so that I can check each different set of code against the other to see which works the best. I will look into that when I next get a chance - probably to-morrow.

Incidentally, since you seem to have a rather thorough understanding of programming and the Simutrans-Experimental code, had you considered writing any of your suggestions yourself? It might be quicker to write the code in some cases than explain to me what to do! If you use Git to create one branch of the Simutrans-Experimental code on Github for every set of changes that you want to make, then I can merge your changes in to the main Simutrans-Experimental branch, make further changes if necessary, and then incorporate that code. Having a second developer on the project - especially one who seems to have a good understanding of the relevant sorts of programming - might be most worthwhile in itself, and contribute greatly to the future development of Simutrans-Experimental. (Indeed, anyone is welcome to make branches of the code on Github to add a new feature or optimisation which I can then add to the main branch).

Thank you also, incidentally, for the suggestion on local variables; I use const because it allows more compiler optimisation than non-const variables, but you might well be right that using the same variables many times is more optimal still. I will put this into the next version, too.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

knightly

#14
Hi James :)

Thank you very much for taking the time to read my posts and PMs, which are lengthy at times, and for considering my suggestions as you improve ST EXP.

Quote from: jamespetts on April 24, 2009, 01:56:56 PM
Secondly, I have been trying to understand how to implement the checking in the open list iteration portion as you suggest - I will have a go at doing that for the next version.

So, probably I still haven't made myself clear regarding the line/convoy switch check? Actually it is not complicated : maybe some pseudo-code can help to clarify. Starting at line 1492 of simhalt.cc :

Set previous_connexion to current_node->link->halt->get_connexions(ware_type)->get(current_node->halt)
Set previous_best_line to previous_connexion->best_line
Set previous_best_convoy to previous_connexion->best_convoy
For each iteration
  Set next_halt to current key
  If (next_halt is in closed list or previous best line/convoy == the best line/convoy to next halt)
    continue;
(... following code is the same ...)

Remember, the above is just rough pseudo code to illustrate my approach, and many details have been omitted.

Quote from: jamespetts on April 24, 2009, 01:56:56 PM
I will use conditional compilation so that I can check each different set of code against the other to see which works the best. I will look into that when I next get a chance - probably to-morrow.

Comparing among different approaches is good. Maybe you can set up the profiler mentioned by prissi and compare their profiling results?

Quote from: jamespetts on April 24, 2009, 01:56:56 PM
Incidentally, since you seem to have a rather thorough understanding of programming and the Simutrans-Experimental code, had you considered writing any of your suggestions yourself?

I think you have got me wrong here. :) I have not done programming for years (though I used to love programming very much), and I have forgotten most of what I have learnt about programming already. Besides, I only have a rather superficial understanding of the code of both ST STD and ST EXP -- there are many parts of the code which I haven't read and which I don't think I can easily understand, and some parts of code which I read I do not fully understand. I tried to follow your route searching code closely, thinking of the different possilibities or loopholes, mentally walking through your code, and that is the reason why I seem to have "thorough" understanding of programming and Simutrans code in your eyes :P

jamespetts

#15
Knightly,

when I started coding for what became Simutrans-Experimental in December, I'd never written C++ before in my life, apart from one extremely simple one-method console application that could be compiled as either C or C++ and would work the same. I knew a little C#, but had not done a great deal in it. What I have learned I have learned by adapting my knowledge of C#, by reading articles on the internet, by looking at the code, and by trial and error. If you are able to understand my code as well as you are, and find all the memory leaks that you have, no doubt you, too, could do the same.

As to the other point - I will have a go at implementing that and see how it goes. Thank you for your help :-)

Edit: I have now included all of your recent suggestions into the latest version 2.7 - try it to see whether it is any faster. It seems a little faster than 2.6 to me, but not much different from 2.5 (but the avoiding rogue vias using your system seems to work). Thank you very much for all of your suggestions - they are most helpful.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

knightly

#16
Quote from: jamespetts on April 24, 2009, 09:52:07 PM
If you are able to understand my code as well as you are, and find all the memory leaks that you have, no doubt you, too, could do the same.

Thanks a lot for your encouragement. I will think about it, but please forgive me, for currently I feel more comfortable reviewing and debuging code, than writing code of my own ::)

Quote from: jamespetts on April 24, 2009, 09:52:07 PM
It seems a little faster than 2.6 to me, but not much different from 2.5 (but the avoiding rogue vias using your system seems to work).

Sorry that my suggestion isn't faster than v2.5 :P I strongly suggest you to try profiling the different alternative approaches, because feelings are not very accurate -- at least not accurate enough to shed light on how to optimize the most critical algorithms.


jamespetts

Do think about it - you might find it very fun :-) As for reviewing and debugging - we all have to start somewhere, and your work so far is very useful. And no need to apologise - something with the speed of 2.5 and the function of 2.6 is a great improvement :-)

As to profiling - I shall have to look into that when I have time.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.