[Developer discussion] Improving private car related performance

[jamespetts]

Continuing from the discussion here about the poor performance on SDog's large and well-developed saved game, the problem can be traced to the system in which cities check to see whether there is a connexion between them by road so as to calculate trips for private cars. This uses Simutrans's built-in A* routefinder (the same as vehicles use when they are trying to find a route to their destinations, and is quite computationally intensive.

This feature can be turned off by setting assume_everywhere_connected_by_road=1 in simuconf.tab, but then a useful feature of the game (viz. private cars not being used to places not connected by road, etc.) is lost. What is needed is a way to optimise this feature. The problem seems particularly acute after loading a saved game, since the connexions are not saved, and so they must all be recalculated from scratch when the game is loaded. This would be even more of a problem on an online game when the game needs to be reloaded whenever somebody joins.

The first step in improving the performance, therefore, would be to save the values with the saved games. Although this would increase the size of the saved games (and thus the time taken to transmit a game over a network), I suspect that the increase in this time would be more than compensated for by the lack of a performance penalty after loading. Indeed, probably a sensible thing to do would be not to load/save these values where "assume_everywhere_connected_by_road=1" is set. The data are currently stored in koordhashtables, and, as there is already a built-in mechanism for saving objects of the class "koord", this should not be too difficult.

The next issue is frequency of recalculation: the less often that cities have to re-check their road connexions, the better. Currently, each city will recheck its road connexions every month if there have been any changes in the road network: a bool flag in karte_t is triggered every time that a road is added or deleted, and, if this flag is set, cities will all recheck their connexions the next month then reset the flag.

A simple way of reducing the number of recalculations would be to spread out the calculation over a year: some cities in January, some in February, etc.. This could be achieved by assigning each city a month upon creation (or loading if a game saved before this feature is implemented is loaded), and only rechecking connexions if the month to which it is assigned matches that month in which the check is scheduled to take place. The problem with this, however, is that it means that it might take up to a year for a change in the road network to affect certain cities.

A more sophisticated solution would be to store the route used to get to and from each city in a "private_car_route" object, a derived class of route_t. This would store the actual route tiles, plus the start and end point. Each way tile on that route could be given a pointer back to that route so that the route could be set to be recalculated immediately one of those tiles is deleted. There would still have to be periodic checking, as that system would not by itself determine whether a new better route had been created, but it would then not be so much of a problem if the more general calculations were less frequent.

This system has another advantage: the route objects can then store some very useful information that could give rise to other features. For example, they could record the number of car trips over them in the last month. This information could be accessed by clicking on a road tile: it would then be possible to see the total number of vehicles (including player vehicles) using the route in the last month, and also the number of private vehicles using each individual route (number from city X, number from city Y, number going from city X to city Y, number going from city Y to city Z, etc.).

Furthermore, each road tile could then be assigned a monthly capacity. If that capacity is exceeded (player vehicles would count for this purpose), the road would be deemed to be congested, and the private car trips register as taking more time, which would then increase the tendency of residents of the cities on the route that use that road to use player transport.

More than that, the actual graphics representing the movement of cars could be made to follow the route. Currently, city car graphics wonder around the roads more or less aimlessly, as it would take far too much processor power to calculate an individual route for each of them. But, if all cars going between different towns were to be assigned the pre-stored route, they could all easily be set to follow that route without increasing computational load (cars whose start and end point are within the city would continue to wonder around aimlessly, as it would be too much to calculate all the routes within the city). That would have the additional benefit of giving players a visual representation of where the traffic is going from/to as well as actually make the roads that they use congested to the same extent as they should be, slowing players' vehicles as necessary in the process.

I'd be interested in any comments from developer-minded people as to these ideas generally, and whether there are any particular unforeseen problems in relation to any of the proposed ideas here.

[sdog]

You can check the connections much less freqently. Just assume every city connected until proven otherwise.
Also only test locally, if it is connected to their next neighbours. If those also are connected to enough next neighbours, it is good enough to consider them connected globally. This whole system doesn't has to be very accurate I think.

[jamespetts]

Sdog,

I'm not sure that I understand the first comment - why assume that they are connected rather than that they are not connected?

There is a good reason to have it fairly accurate, however: to model accurately the competition between the player's transport and private cars. Checking connexions through neighbours is not much use, as it would not give a good approximation of journey times if the journey via the neighbour was circuitous. The current system records more than a binary true/false flag as to whether towns are connected: it also records the average journey time per tile, which is then multiplied by the actual distance between the actual origin and the actual destination to get an approximated journey time, which is then compared with the journey time using player transport as part of the mechanism of determining whether private cars or player transport is used. The game would become far less interesting if all that was taken away.

[mopoona]

The decision weather a passenger chooses his private car rather than using a players network is already made when journey time tolerances are lower than the actual journey time of all public transport networks. The private car feature would affect the game very similar to this, but would need way to much cpu time.
I think it would be better to have different journey time tolerances for every year, so you could simulate higher private car usage over time.

I see another much smaller problem with the private cars in SE. I think there will be no city cars in network games. The payer won't be able to see private cars and its effects.

[jamespetts]

Mopoona,

I am not sure that I fully understand the point; the passengers still have to check whether the private car journey time is possible and within their tolerance even if the public transport connexion is not. I am not sure that I understand the historical basis for the suggestion of varying journey time tolerance by year; the varying of car ownership percentage by year is already implemented and works well.

As to network games, private cars are possible in network games, and they synchronise between servers and clients, so this ought not be a problem.

[sdog]

As i understand Mopoona wants to have the journey time tolerance depend on time (year). Having a proper model for this would already include the loss of passenger numbers due to increased car use. Both systems, your car ownership and the travel time tolerance has the same effect on the game, reduction of passenger numbers.

I don't think it's a good idea to implement the car ownership system as you suggest, at least until having a bit more thought on a model for the passenger behaviour. The basic concept of your model is that passengers compare journey times of both means of travel they have available. However people do not tend to do this in reality. First it is hardly possible for pax to anticipate the different times, unless they differ greatly. Then only great differences will outweigh extreme differences in comfort or costs. And last but not least people do not tend to do rational decissions on those matters. (just look at those car commuters standing in traffic jams, taking public transport is faster and cheaper, arguably more comfortable. High speed trains in europe can hardly be beaten in speed, cost and comfort, but there are still enough using the car instead.) Perhaps someone involved in urban planing like Vilvoh or transport simulation could point us to some relevant papers.

My second point is, that the whole car ownership problem will only become really relevant for large games. For small games, the player can easily beat the car ownership speeds, with a decent network. A non-decent network would drive him bancrupt anyway, so we don't need to cover that case. Furthermore to set the car ownership up to be competitive at a small map, would make it extremely hard to compete with at large networks. For large games however, with many towns and high population the whole problem can be treated statistically. This requires less computation and allows more complex and adequate models to be implemented.

My guess would be the biggest factor to cause cars to be prefered to public transport are number of transfers and overcrowding. Since those are the only occasion where comfort drops considerably below the comfort in cars. Congestion in the starting and arriving town should be major factors benefiting public transport, if not congested. Travel time tolerance already takes care of that caveat, as Moopona pointed out.

The advantage i see in your suggestion is that we could finaly get some park and ride system with it, but i don't think it's worth the cost. The intended effect should just average out, to something we could have had by statistics alone. With the exception of some exotic cases.

Modified after Moopona's reply
I think i go a bit too far by this, as i am not a dev, but still my advise would be to rest this for the moment, until a better model is developed. Also set 'everything_connected' to 1 for online games, to avoid this altogether until network game works.

[mopoona]

As I understand it, the private car feature was implemented to make the game easier at the beginning (where no private cars are used) and more difficult as the years go by.

From the perspective of the player, there are only those passengers that choose to use the players network or not. If they choose not to use it, than this is mostly related to high journey times of the players network. If private cars were fast enough doesn't matter to the player.
The tolerable journey speeds changed over time. At the beginning of rail transport, you made trips with passenger rail that took days. Today you expect to travel the same trips in just a few hours. Primarily this is related to private car ownership and the car journey times, but the way private car usage and journey time tolerances are affecting the players network is very similar. But the first one takes much more cpu time. Higher expected journey speed would force the player to make his network faster, just like the competition of private cars would do.

Another question: Since there is no human player who primarily plays the public player, who will build highways and other streets to make private car faster? Theres no option to make toll roads (or something like that) for every other player to benefit from a higher private car usage.

[jamespetts]

...I don't think it's a good idea to implement the car ownership system as you suggest...

I think that there has been some confusion here: the model of car ownership that I describe above has been in Simutrans in its current form since 8.0, and in a simplified form (more or less the form in which it works if one sets assume_everywhere_connected_by_road=1) since about version 4. It is not a proposal or suggestion: it is already there. The thing that changed in 8.0 was the addition of a system of checking to see whether there is a road connexion between the origin and destination for car traffic, which, it transpires, on large maps causes poor performance, especially when these values have to be recalculated from scratch as when a game is loaded. It was improving that performance issue at which this discussion was aimed. The idea of checking a road connexion between towns (and towns and industries and towns and attractions) is  that it was silly and unrealistic for players to have to compete with private car travel where there is, in fact, no road between the passengers' origin and destination, as on an island, for example. What is not yet present is the mechanism that I suggest for loading and saving the values, nor for saving the particular routes that the private cars take (rather than just the fact that there is a route and the average journey time per straight line tile).

The purpose of the private car model in the first place was not just to reduce the number of passengers as years go by: that would be too simplistic. The purpose was to simulate as realistically as possible the competition that a provider of public transport faces from the private car. The differences in car ownership as the years go by are intended to reflect that reality: indeed, the percentages are based on government statistics as to people who have access to a car (which is the relevant measure, rather than ownership in the strict sense). Altering the journey time tolerances as the years change would have a very different effect on the patterns of passenger travel than altering the percentage who have a private car.

As to the method that passengers use to determine whether to use a private car or the player's transport, the comparative speed is not the only (indeed, not even the most important factor) factor, but it is taken into account. The congestion (shown in the graph on the city window) of the origin and destination cities is a particularly heavily weighted factor, as is a weighted randomised car preference (different people are more attached to their cars than others), and there is a certain percentage of people who will insist on using their car if they can whatever the congestion levels.

Comparing the comfort of taking a private car with that of taking the player's transport is not possible because there is no system for computing the overall comfort of a journey. Although in some respects it would be desirable to have a model for computing the overall comfort of a journey and for passengers comparing this overall comfort of different journeys when considering which route to take, I strongly suspect that this would make the calculation of routes (one of the most CPU-intensive parts of the game) too computationally expensive, and so I have not implemented such a feature (which is a shame in a way, as comfort is a significant deciding factor as to the route that passengers take).

As to varying the journey time tolerance: I don't think that it's true that people's basic tolerance of journey times varies over the years. If it varies at all, it does only if and in so far as there are, in fact, methods of transport that will get people where they are going more quickly than in years past. People will not tolerate spending twelve hours to get from London to Scotland if there is a train that will get them there in five. But people still do tolerate journeys of twelve hours to get to Australia (and go to Australia now about as much as they went to Scotland when it took twelve hours to get there). Varying the journey time tolerance with the year, therefore, would make the game less realistic, not more.

Incidentally, on forcing the player to make the network faster as time goes by, there is an element which does this: the speed bonus. In Experimental, the speed bonus (which in Standard attaches to the maximum speed of the convoy in question) attaches to the average speed of the relevant convoy or line, and this, like in Standard, does vary with the years (I had considered making it depend instead on the overall average transport speeds, as in reality, t this factor is heavily dependant on competition, but this would have unfortunate effects in a game with only one player and would, for all its complexity, likely not have a significantly different effect from the existing system in other cases).

To answer Mopoona's final question, in a network game, I do anticipate the public (human) player building roads as time goes by: there is much to be said for a model where the public service player is not just an admin, but also a participant in the actual game, playing as the transport minister in Simunation's government, whose aim is to maximise the transportational quality/capacity of the whole map, whereas the individual players' objectives would be to maximise their profits. The interaction between the two could be very interesting indeed.

Another possibility is to have the game automatically build or upgrade roads between cities as time progresses, but this would not be an entirely simple thing to program if plausible results were to be achieved.

[mopoona]

My idea for different journey time tolerances was more related to actual journey speeds, and not to the way SE does handle the tolerances now. The easiest way (meaning less cpu load) to simulate competition from private cars would be to assume that everything is connected and to use some kind of average car journey time. This solves the problem with the public player and the existing features like car ownership and congestion can stimm be used.

By the way: What car journey times does the game calculate when using assume_everything_connected=1?

[jamespetts]

Mopoona,

when assume_everywhere_connected_by_road=1 is set, the road speed is calculated based on the speed limit of the current inter-city road and the average top speed of current city cars (adjusted to approximate for the fact that vehicles will not travel at top speed all the time and that the road will not be completely straight).

[sdog]

I think that there has been some confusion here: the model of car ownership that I describe above has been in Simutrans in its current form since 8.0, and in a simplified form (more or less the form in which it works if one sets assume_everywhere_connected_by_road=1) since about version 4. It is not a proposal or suggestion: it is already there.

Sorry for expressing this badly, i meant the changes you proposed on the system that is in place at the moment. The model does not really reflect reality, but

when assume_everywhere_connected_by_road=1 is set, the road speed is calculated based on the speed limit of the current inter-city road and the average top speed of current city cars (adjusted to approximate for the fact that vehicles will not travel at top speed all the time and that the road will not be completely straight).

We could hack one of my savegames to see if there is a difference in behaviour with assume_everywhere_connected_by_road=0 or 1. My hunch is we won't, at least if the above mentioned adjustment parameter is tweaked a bit.

omparing the comfort of taking a private car with that of taking the player's transport is not possible because there is no system for computing the overall comfort of a journey. Although in some respects it would be desirable to have a model for computing the overall comfort of a journey and for passengers comparing this overall comfort of different journeys when considering which route to take, I strongly suspect that this would make the calculation of routes (one of the most CPU-intensive parts of the game) too computationally expensive, and so I have not implemented such a feature (which is a shame in a way, as comfort is a significant deciding factor as to the route that passengers take).

This is true for the current model. However a much simpler model should be able to do so:

We can get the average comfort of the rolling stock of a line, the percentage of overcrowded vehicles, average speed. By introducing proper weighting factors we can get a score for this line. For every packet of passengers we can get congestion values of their origin and destination (ignore congestion in-between), average speed of private cars can be determined from the speed-bonus tab. Based on this a score can be generated to compare with the score for a line. When a packet of passsengers does it's route finding and selects the route the number of passengers is reduced by a percentage based on a function* with a maximum reduction equal to the car-ownership percentage.

This model would save the route computation for car trips and allows to model more relevant factors influencing passenger decision.

*Example function: Gauss error function (erf(l-c)+1)*o/2 with l the line score, c the criterium score and o the car ownership. The function is asymptotic to zero for l<<c and to the car ownership o for l>>c, if both are equal half the car owners take the train.

As to varying the journey time tolerance: I don't think that it's true that people's basic tolerance of journey times varies over the years. If it varies at all, it does only if and in so far as there are, in fact, methods of transport that will get people where they are going more quickly than in years past. People will not tolerate spending twelve hours to get from London to Scotland if there is a train that will get them there in five. But people still do tolerate journeys of twelve hours to get to Australia (and go to Australia now about as much as they went to Scotland when it took twelve hours to get there). Varying the journey time tolerance with the year, therefore, would make the game less realistic, not more.

Perhaps i'm mistaken here, but i thought the journey time tolerance is not based on the fastest available transport? As i understood it is a fixed set of values? A journey time tolerance that allows to move some passengers in 1800 over 1000 squares, with coaches and barges, will be irrelevant in 1900, the average speed will be 10 to 15 times higher.

[jamespetts]

I don't think that I quite follow: why is the private car model one that does not reflect reality? Journey times are in reality an important factor in people's choice of transport, and, for determining whether to use cars or not, an innate preference for using cars is already built in (which is substantially reduced in the case of congestion). I am also a little confused as to why car ownership should be relevant only in larger games; why are they distinct in that respect from smaller games? A (good) player might be able to get better speeds, but, as stated above, passengers in Simutrans-Experimental have an innate preference to use their car that speed alone cannot overcome (although it helps). As for balancing the levels of car ownership, that is done quite simply by using real figures.

In terms of comfort, it is not just a matter of getting the average comfort of the rolling stock of the line: it must be multiplied by capacity, overcrowding taken into account, and then the combined comfort of the whole journey calculated by taking the comfort of each leg, multiplying it by the journey time of that leg, and dividing the whole thing by the total journey time. If comfort is a relevant factor in choosing player transport over private cars, however, it seems rather arbitrary that it is not also used (where its use would be equally important) in deciding the best route to take (as the route-finding system for player transport currently works only on journey time). So, if it was implemented for cars but not for comparing modes of transport, a public transport option with a journey time of three hours and five minutes and an average comfort of 75 would be preferred to a public transport option of three hours and ten minutes with an average comfort of 145. It would be unfair on the player, then, if that three hour and five minute journey at comfort 75 would be the basis of comparing with car transport when there is a three hour and ten minute journey with a comfort of 145.

The ideal solution to that would be to include comfort in the process of selecting passenger journeys, not least because comfort was, in reality, an important source of competition: more comfortable rail vehicles were strategically deployed on lines with the greatest competition. The problem is that that would greatly increase the computational load of the routefinding system, one of the most CPU-intensive algorithms in the game. The problem is this: the route finder has to make lots of "is route X better than route Y?" decisions for every route calculated. All the possibilities have to be evaluated for every route found. With one variable, journey time, each comparison is a very simple check to see which of two integers (representing journey time) is larger in size. That is very simple for the computer.

If a second factor were to be added, this would not be so. There would have to be some intelligent means of balancing comfort and journey times; one simple idea would be for passengers to choose the most comfortable option where journey times are within a certain margin of each other: for example, choose the most comfortable out of all the journeys within 10% of the quickest. However, this would greatly increase the amount of computation to be done at each step. Firstly, the computer would have to work out exactly what 10% of the journey time in question is (and division is always the most time-consuming of the basic arithmetical operations in a computer). Secondly, it would have to iterate through all the possible routes found to see which was within 10% of it. It would then have to cache those results. Then, it would have to iterate through that cache of routes within 10% comparing the comfort of each of them with the most comfortable so far found. It would have to do this whole process many, many times for every single route calculated, and that is what is required for a very simple system: so simple that it may well produce arbitrary results: passengers would choose a 11 hour journey over a 10 hour journey for a minute difference in comfort, and, if one has that sort of arbitrary result, one might as well have the simpler journey time only system in the first place. Of course, it would be possible to compare the marginal difference in comfort with the marginal difference in journey time to reduce those perverse results, but that would increase by orders of magnitude the complexity of the calculation required for the simpler method (and, critically, involve numerous division operations to assess proportions).

[sdog]

I don't think that I quite follow: why is the private car model one that does not reflect reality? Journey times are in reality an important factor in people's choice of transport

Are you certain about this? Firstly the journey time is usually not transparent to the traveler. The train schedule is perhaps the most reliable part of it, but for the car and plane there can be only rough estimates. So this should matter, but only for large discrepancies. If journey time was the major factor, plane and car wouldn't matter for long distance travel in France or Germany.

Most passengers do not base their decision on ratio. This is similar to the 'homo oeconomicus'  models that were popular in the 1980s and '90s failing in economy.

A (good) player might be able to get better speeds, but, as stated above, passengers in Simutrans-Experimental have an innate preference to use their car that speed alone cannot overcome (although it helps).

But this second part who always prefer cars already is covered perfectly by reducing the available passengers for public transport by, lets say, half the percentage of car owners.
Don't missunderstand me, i do assume that the car ownership should and will be a major factor contributing to reduced ridership. What i doubt is that modeling it in detail, with calculating journeys would have a different effect than doing it based on a simpler statistical model.

The ideal solution to that would be to include comfort in the process of selecting passenger journeys, not least because comfort was, in reality, an important source of competition: more comfortable rail vehicles were strategically deployed on lines with the greatest competition.

You already have a factor doing this by basing the revenue on comfort. This is transparent to the players they will optimize it, and they have the means to do it. This also applies to the example. If the player fails to do the optimization, there will be quite a bit of lost profit anyway. (A "reservation only" button would help, to disable overcrowding for a line.)

If you want to introduce a comfort factor in way search might be interesting for competitive network play. Doing it for the car ownership model would be overkill though. If you want to do it, don't use two checks but create a composite score before you optimise. Optimisation problems for more than one variable are evil. In such a case it will hardly matter what and how many factors you include in the route search. You just have to tune your weighting parameters. I don't think this is something urgent at the moment, as the economic simulation doesn't provide a competitive game right now. (Moblet's suggestions are imho more important.)


So let me conclude this, i think the car ownership should have a massive influence on passenger numbers. I doubt that the high detail of the current implementation is adequate to the rough model behind it. A simple statistical approach would bring equally valid results with less effort. The statistical approach also allows to have a more detailed sociological model behind this system.

What the car ownership model does at the reducing the ridership based on a global factor. This reduction can be reduced somewhat, but not completely, by a fast service with travel times lower than the possible car travel times determined by the way-finder.

[jamespetts]

I am quite sure that journey times are a significant factor in people's choices of transportation method, not least because I have spoken to a senior civil servant in the Department for Transport about it! People do have a pretty good idea of how long that a journey will take by car, usually because they have done it before, or they speak to somebody who has. In any event, the relative journey times is not the major factor. It is a factor. Congestion is a more significant factor.

If the statistical model is no better than the current implementation, there is no need to change something that works. If the problem is performance, then, if the proposed changes to the route-finding for private cars discussed on the other thread do not suffice, then the simple answer would be for those playing on larger maps to set "assume_everywhere_connected_by_road=1". This would be unfortunate, however, as it would mean that towns on an island, for example, would be treated as if they were connected to the mainland, and players' boats or aircraft suffer disproportionately as a result.

The car ownership system does far more than reduce rider ship based on a global factor: it is intended to (and does) simulate the competition between private and public transport. That competition should reflect the relative merits of those two systems at a local level: if the player's trains are fast and frequent in a particular area, fewer people should use their cars; if the roads are particularly good in another area, fewer people should use the player's transport, and so on.

Can you expand on what you mean by the statistical approach allowing a more detailed sociological model which (presumably) is not permitted by the current system?

Edit: On your saved game from the other thread, have a look at Lowestoft, which is on an island with no other towns. There, you can see that the "traffic" graph shows a very low number in comparison to the "transported" graph, meaning that many more people take your boats compared to their private cars. Compare that with a similarly sized town, Ely, not on an island, but connected by road. There, nearly one and a half as many people take their private cars as your trains and 'buses (and boats).

[inkelyad]

My own profiling with sdog map shows:

Code Select Expand


-----------------------------------------------
index % time    self  children    called     name
               12.86  167.62    7987/7987        route_t::calc_route(karte_t*, koord3d, koord3d, fahrer_t*, int, unsigned int, unsigned int) [5]
[6]     82.5   12.86  167.62    7987         route_t::intern_calc_route(karte_t*, koord3d, koord3d, fahrer_t*, int, unsigned int, unsigned int) [6]
                3.95   50.37 129656502/135442437     grund_t::get_neighbour(grund_t*&, waytype_t, koord) const [13]
                2.71   31.84 128489416/128489416     road_destination_finder_t::ist_befahrbar(grund_t const*) const [17]
                1.46   19.68  264660/597691      interrupt_check() <cycle 2> [2562]
               13.36    3.61 64470809/64470809     binary_heap_tpl<route_t::ANode*>::pop() [28]
                0.60    9.22 194113961/194113961     karte_t::ist_markiert(grund_t const*) const [43]
                2.31    3.30 64491289/64491289     road_destination_finder_t::get_kosten(grund_t const*, int, koord) const [60]
                3.85    0.93 65109428/65109428     binary_heap_tpl<route_t::ANode*>::insert(route_t::ANode*) [61]
                0.41    4.23 60537559/60537559     road_destination_finder_t::get_ribi(grund_t const*) const [62]
                1.11    1.83 65102777/855480775     grund_t::get_weg(waytype_t) const [16]
                0.27    2.53 60995171/60995171     karte_t::markiere(grund_t const*) [76]
[SKIP]

82% for route_t::calc_route. Hmm. Where I can disable private cars completely? Just to test how much CPU it cost?

[jamespetts]

The calc_route function will not be called for private cars at all if assume_everywhere_connected_by_road=1. You can hack this value in a debugger.

Edit: I should have mentioned, incidentally, that that analysis is very helpful - thank you! I need to save the routes, I think.

[inkelyad]

I must be doing something wrong. With get_assume_everywhere_connected_by_road() hacked to return true:

Code Select Expand


-----------------------------------------------
               0.57    6.68   24108/24108       route_t::calc_route(karte_t*, koord3d, koord3d, fahrer_t*, int, unsigned int, unsigned int) [42]
[48]     3.7    0.57    6.68   24108         route_t::intern_calc_route(karte_t*, koord3d, koord3d, fahrer_t*, int, unsigned int, unsigned int) [48]
               0.16    2.04 5299502/20761764     grund_t::get_neighbour(grund_t*&, waytype_t, koord) const [39]
               0.29    0.74   53187/5329431     interrupt_check() <cycle 2> [810]
               0.06    0.60 2771504/3072064     automobil_t::ist_befahrbar(grund_t const*) const [182]
               0.36    0.09 2496000/2496000     binary_heap_tpl<route_t::ANode*>::pop() [223]
               0.05    0.30 1309162/1622708     waggon_t::ist_befahrbar(grund_t const*) const [233]
               0.04    0.23 7741129/7741129     karte_t::ist_markiert(grund_t const*) const [273]
               0.04    0.24 2244660/2841876     vehikel_t::get_ribi(grund_t const*) const [247]
               0.11    0.15 2782966/82818202     grund_t::get_weg(waytype_t) const [45]
               0.03    0.18 1439567/1439567     automobil_t::get_kosten(grund_t const*, int, koord) const [308]
               0.14    0.03 2799621/2799621     binary_heap_tpl<route_t::ANode*>::insert(route_t::ANode*) [350]
               0.02    0.09  696762/696762      waggon_t::get_kosten(grund_t const*, int, koord) const [433]
               0.08    0.02 2244661/2244661     get_next_dirs(koord, koord) [452]
               0.03    0.06 2775516/5144070     ribi_typ(koord, koord) [351]
               0.06    0.03 12182416/180789207     koord3d::get_2d() const [125]
               0.00    0.07 2268769/2268769     karte_t::markiere(grund_t const*) [523]

only 3%. But in this run there was more calls. 7987->24108. calc_route must be quite slow for private cars.
EDIT:
I think route calculations for private cars is overkill. Just extend weg_t to form several supply/demand fields (for passengers_to_capital/food/congestion/etc ) and slowly update it. Then we can do something creative with it.

[jamespetts]

My first attempt at implementing this idea is now available on a dedicated Github branch (note that this increases saved game versions to 10). This is not fully reliable yet, and  it's too late at night for me to test further, but I thought that I'd submit what I've done so far for others to have a look at. It's not clear yet whether any improvement in performance results.

[inkelyad]

I think you should use 'Workers live in' for industries. It will reduce number of routes.

And it looks a lot like road system in SimCity now

[Milko]

Hello

So .... if I understand it:
If assume_everywhere_connected_by_road = 1 there is no car ownership and citizens have no alternative to the use of public transport.
If assume_everywhere_connected_by_road = 0 there is the concept of car ownership and the citizens can choose whether to move their car or public transport, in this case the travel time using public transport is compared with that car ownership; citizens use the fastest (too slow = citiziens using car ownership?).
I understand you correctly?

Giuseppe

[inkelyad]

Quick and dirty visualisation
Click on town hall. Then open map window and select "PrivateRoute" mode.

How this work? There is no need to build route for every <city,city> pair.
We have one spanning tree for every city. It need only one run of path-search algorithm to build.
Every road tile will have "distance to city x" after that.

[jamespetts]

Inkelyad,

very interesting visualisation! There are still some bugs with deleting routes (Edit: to be clear - in my code) that I'll have to try to track down, but it's very interesting to see this in visual form.

I'm not sure that I understand what you mean about the spanning tree - is that used just for your visualisation, or did you intend that it be understood to be an alternative way of actually creating routes? If so, does it take into account the quality of the routes (i.e., the speed limits of the roads on the routes) in the way that my system does? That is an important aspect: two cities linked by a dirt road will have fewer private cars travelling between them than two cities at equivalent route distance linked with a motorway.

In due course, it could be possible to model congestion on the roads, and make inter-city journey time dependant on that congestion, which would require a more accurate route quality assessment still. There's no reason in theory, after all, why Simutrans should model private car transport any less accurately than any other form.

Edit: Forgot to answer Giuseppe.

Giuseppe,

that's not quite right. If you want there to be no private cars at all, what you'll have to do is set "car_ownership=1750,0" in privatecar.tab. That will set the ownership of private cars to 0% for 1750 and all subsequent and previous years.

Setting assume_everywhere_connected_by_road=1 in simuconf.tab simply prevents Simutrans from trying to determine whether there is a private car route between any given two points, and just assumes that there is a route, so passengers are more likely to use their private cars when assume_everywhere_connected_by_road=1 than not.

[inkelyad]

I'm not sure that I understand what you mean about the spanning tree - is that used just for your visualisation, or did you intend that it be understood to be an alternative way of actually creating routes? If so, does it take into account the quality of the routes (i.e., the speed limits of the roads on the routes) in the way that my system does?

Running Dijkstra's algorithm  for each city and store value 'there is n private cars here from city S' in way tile should take much less cpu time then running any kind pathfinding for each pair <city A, city B>.

There's no reason in theory, after all, why Simutrans should model private car transport any less accurately than any other form.

Memory footprint. storing n^2 routes and many-many pointers to them is bad.

I still think that something like 'finite elements heat transfer model' will be more then enough.

[jamespetts]

But does that account for the quality (i.e., the speed limit) of the particular roads, such that travel by private car between city pair A-B will take less time than travel between city pair X-Y even though the route distances are the same because the road between city pair A-B is better than that between X-Y?

[inkelyad]

route distances are the same because the road between city pair A-B is better than that between X-Y?

Path length in Dijkstra's algorithm can be travel time.

[jamespetts]

Hmm, so it'd compute the travelling time on each tile as it went, using a function of the minimum of the the road's speed limit and the average vehicles' maximum speed?

[inkelyad]

Yes. It must be done using float arithmetic.

[jamespetts]

Very interesting. Would this system allow the interesting statistical information about how many cars use a particular route being obtained by clicking on a tile, and allow the actual city car graphics to be assigned to the route in the same way as my system?

[inkelyad]

Err. I think not. But you still can build routes for private cars if you use pre-build spanning/Dijkstra tree.

Edit:
Theoretically, it(pre-buildinng routing trees) also good way to improve routing speed for all vehicles in game. but it will need a huge amounts of memory.

Do simutrans do route caching?

[jamespetts]

That's very interesting. Would the work of building the routes with the spanning tree not negate the advantage of using the spanning tree in the first place, though?

[inkelyad]

Spanning tree need rebuilding only when road network is changed. Then we can build routes from it very fast.

But now I think implementing route caching is more useful.

[jamespetts]

Ahh, but doesn't the road network change very frequently (i.e., every time that a city automatically builds a new road as part of its growth)?

[inkelyad]

It still much less often then we need to calculate new route.

[sdog]

Ahh, but doesn't the road network change very frequently (i.e., every time that a city automatically builds a new road as part of its growth)?

You can just ignore changes of roads inside city boundaries, and re-build the tree only for roads being built outside. Inside city boundaries it certainly should be enough to consider "everything is connected".

Don't forget our paradigm is that the city roads in game are just the major roads, and the network of smaler arterial roads is not displayed. for the lenght of this way you can use the direct point to point manhattan distance and a low average speed.

[jamespetts]

Inkelyad,

do you think that you can expand on your idea as to how it might work? I'm not sure that I fully understand the details (perhaps I'm being slow; if so - apologies). How would it be implemented?

[inkelyad]

1) Add map City->travel time from city to each strasse_t tile (Brr..)
2) fill it using Dijkstra's algorithm at road networks changes.
3) When you need route from tile a to city B just build route backward from a.
  (prepend tile where travel time is less then travel time in current tile).

[jamespetts]

Forgive me for being slow, just a question or two for clarification if I may: do you intend to store in each road tile in the map its journey time to each tile of town hall road? And does step (3) described above entail checking a route from any of those tiles to the destination townhall road tile by searching for tiles with a shorter distance to the that townhall road tile?

[inkelyad]

Forgive me for being slow, just a question or two for clarification if I may: do you intend to store in each road tile in the map its journey time to each tile of town hall road?

No, just to one. Do we really need to be that precise?

[jamespetts]

9.3 includes a simple improvement to the performance of games after loading: private car origin/destination/journey time per tile triplets are now saved with the saved game, and cities re-calculate annually rather than monthly (and on rotation, so that cities recalculate throughout the year, rather than all at once in January). I have not resorted to the more sophisticated system of storing actual routes for the time being. I should be interested in people's views on post-loading performance in 9.3 on large games in eras when private car ownership is high.

[sdog]

much faster now

[jamespetts]

Excellent! Thank you for testing.