The International Simutrans Forum

 

Author Topic: [Bug?] private car routing information on a road tile is removed incorrectly  (Read 307 times)

0 Members and 1 Guest are viewing this topic.

Offline Phystam

  • Devotee
  • *
  • Posts: 490
  • Pak256.Ex developer
    • Pak256 wiki page
  • Languages: JP, EN, EO
I am confused about that. see the picture:

the north-headed way has a lot of information about the destinations, but south-headed way has less or no information.
But I remember that the south-headed way has been calculated destinations. so for some reason, all destinations are removed.
This issue may lead private cars in an incorrect direction and make the way congested.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 20207
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
May I ask how large that the map is? Calculating private car routes takes a long time. They can only be calculated in the background, with the working set swapped periodically for the live set. If the map is very large, it can take an extremely long time for this swapping to occur because of how computationally intensive that the routefinding algorithm is. Thus, it may take many in-game months for the route to refresh with new information. If, during a refresh, the route in question is not the optimum route (e.g. if one tile is missing, or there is a high level of congestion), then another route in that direction may be found, and it may take a long time, depending on the map size, for the more obvious route to recalculate itself again.

Offline Matthew

  • *
  • Posts: 386
    • Japan Railway Journal
  • Languages: EN, some ZH, DE & SQ
May I ask how large that the map is?

I know that's a rhetorical question, but it's one that I can answer:  ;D


Offline Phystam

  • Devotee
  • *
  • Posts: 490
  • Pak256.Ex developer
    • Pak256 wiki page
  • Languages: JP, EN, EO
However probably it is possible to keep the old data until the recalculation has been completed. And there’s no reason to delete all calculations on a tile...

EDIT:
Well, the situation of the first picture is like that:

This is a main route to the south area, so they must use this route when they want to go to the south area.
« Last Edit: September 03, 2020, 10:05:44 AM by Phystam »

Offline Phystam

  • Devotee
  • *
  • Posts: 490
  • Pak256.Ex developer
    • Pak256 wiki page
  • Languages: JP, EN, EO
Still I cannot understand this issue. see the picture below:


The narrow road from the city hall has 223 routes to other cities, but the main road has only 172 routes to the north, and there is no routes to the south ><
This shows the 51 routes to the south are accidentally removed.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 20207
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
The way in which the private car routing system works is to calculate all routes from one city at a time to all other cities. The game will slowly work its way through the various cities on the map and then start again. Because of this, it is possible for routes to be one directional only in circumstances where some cities but not others have completed their calculation.

Because the amount of time that the calculation takes for the whole map increases exponentially with the number of cities connected to each other by road, a map with >600 cities all connected to each other by road will take a truly extreme amount of time to complete its calculation, and thus there will be anomalies from a part finished calculation virtually indefinitely.

Unfortunately, to my knowledge, because of the inherent computational intensity of pathfinding, there is no way of doing this any faster other than multi-threading, which cannot at present be used for this process in multi-player games because the routes found by the path-finder from any given tile change for reasons that I have never been able to understand depending on what the ultimate start tile of the journey is (this was discussed early this year in some depth in the private car route finding thread, I believe). If anyone can find a way to make this pathfinding algorithm, ultimately inherited from Standard with some minor modifications, deterministic enough to use multi-threaded in a network game, then that would help somewhat (although the computation time would still be likely to be extreme with >600 interconnected cities).

Offline Phystam

  • Devotee
  • *
  • Posts: 490
  • Pak256.Ex developer
    • Pak256 wiki page
  • Languages: JP, EN, EO
I'm afraid that I could not say about the issue correctly.

I mean, the sum of the number of connected cities should be the same between one road tile and all its adjacent tiles. In the picture, the sum is different (223 and 172). the narrow road that has 223 routes shows that at least 223 routes from the city has already been calculated so far, but the wide road that has only 172 routes shows that at least 51 calculated routes are missing for some reason.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 20207
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
I'm afraid that I could not say about the issue correctly.

I mean, the sum of the number of connected cities should be the same between one road tile and all its adjacent tiles. In the picture, the sum is different (223 and 172). the narrow road that has 223 routes shows that at least 223 routes from the city has already been calculated so far, but the wide road that has only 172 routes shows that at least 51 calculated routes are missing for some reason.

I suspect that it will be virtually impossible to investigate any anomalies with individual tiles on a map of such size, as the amount of time that it takes before the code will reach the point where it deals with any given tile is likely to be extremely great.

If anyone is able to upload a reproduction case in a much smaller map (<50 cities, preferably <10 cities), that would be extremely helpful. If this cannot be reproduced in any smaller map, then it is likely the problem is directly related to the difficulty of computing such a large number of routes.