The International Simutrans Forum

Simutrans Extended => Simutrans-Extended development => Topic started by: jamespetts on March 24, 2012, 12:16:18 AM

Title: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on March 24, 2012, 12:16:18 AM
Edit: This thread was originally titled, "Bug fix uncovers performance issue. Ideas for solution sought". Renamed to clarify more expansive recent discussion. Re-titled 2nd of January 2013.

I have been working on fixes to some of the bugs in 10.10, including the bug that has stopped the server game for the time being, and found an additional bug whereby road connexions between towns were never updated as they should be once they were put into the database in the first place. Once I fixed that bug and re-tested with the saved game from the server, I found that the amount of re-checking of road connexions between cities overwhelmed even my fairly powerful i7 such as to make the game unresponsive. I had thought all along that that the road checking was not causing performance problems, but it transpires that this was only because it was not, in fact, happening at all after the first check.

The issue is related to the number of cities. In the server game, there are 675 cities. 675 ^ 2 = 455,625. Because the game will assume that routes are bidirectional, the number of computations are halved, making 227,812. Further, these are spread over twelve months, one twelfth of cities being re-checked every month, making 18,984 re-checks that must be run every month if the road network is updated in any way. This is just for cities - routes must also be found to attractions and industries.

(By way of comparison, in a game with 128 cities, there would be just 683 re-checks every month, and in a game with 64 cities, there would be only 171 re-checks).

This is a rather tricky issue. Without the checking mechanism, there is no way of telling which cities are connected to each other (or attractions) by road. One conceivable solution would be to have some very sophisticated pathfinding mechanism similar to that which Knightly wrote for the routing of goods, but that is beyond my capabilities. A simpler, although somewhat less satisfactory solution, would be to find a mechanism of spreading the number of re-checks evenly so that one can specify in simuconf.tab a maximum number of re-checks that may be performed every X ticks, although even implementing that would be really rather tricky.

If anyone has any ideas to offer by way of assistance, I should be very grateful indeed.

Edit: A crude timing test shows that each road check operation takes between less than 1ms and well over 100ms each. Assuming an average of 50ms per operation, performing 18,984 re-checks would take 949.2 seconds, or 15.82 minutes (that is not counting any other operation that the computer might be performing during that time - the actual time to complete the re-checks would therefore be considerably greater).
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: ӔO on March 24, 2012, 01:15:20 AM
Just a question, but how hard would it be to multithread the route calculator?
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 24, 2012, 01:19:12 AM
I don't know. I suspect very hard. Simutrans generally is not multi-threaded at all. C++ has no built-in support for multi-threading, so a different implementation for every target platform would be required. I suspect that much work would be necessary to make multi-threading work in Simutrans. If anyone would like to try, however, I shan't be complaining!
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: transporter on March 24, 2012, 04:57:58 AM
Idea 1:
I'm not sure if software is able to do this, much less if it's even possible, but what about doing the checks only after a player makes a change to the roadways?  I'm assuming that any changes made by the public service player will not affect how cities are connected since I haven't seen any times that the public service player has deleted ways. Then the game would be able to assume that connections haven't changed since the last check. So maybe a possible cue to check is if an active human player makes a change to the map.

Idea 2:
Maybe the checks can only be performed on a section of map at a time. This could maybe be a changeable variable in the settings page to be customized to your computer or server. Or it could be based automatically on map size and city distance. For example, for a 100x100 map, it would take the top left 30x30, then move over 20 units each time to overlap 30x30 for a continuous check for the rest of the map, then when it gets to the edge of the map it moves down 20 and either just moves the other way or starts back on one side.

Idea 3:
A sort of combination of the 2 where the checks occur whenever the player makes a change to the map, but the checks happen within a certain area of the change itself. Using the same rules as stated above.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: inkelyad on March 24, 2012, 08:13:42 AM
You don't need check connection for every pair. It is very slow indeed. You only need to run some kind of flood algorithm to mark connected components (http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29) of road network. In fact, i think said algorithm already exists somewhere in simutrans code. Ask Standard development team about it.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 24, 2012, 11:08:27 AM
Transporter - thank you for your thoughts. Idea 1 is already implemented - the checks will only be run if somebody changes the road network somewhere. That is not much help, though, as the game becomes unresponsive when anyone does change the road networks. Idea 2 is interesting, although this is just another form of staggering, one form of which is already achieved by the system of allocating each city a month in which its road connexions are to be checked. I could spread this out further, but it would have to be so spread out, I think, to avoid causing problems on really large maps that it would take many, many game years for road connexions to refresh fully.

Inkelyad - thank you likewise for your suggestion. The problem is that we need to find not just the answer to the binary question of whether a city is connected at all, but the quantitative answer as to what the quality of the connexion is. A connexion by a meandering dirt track should attract far less traffic than a connexion by a motorway.

Edit: I do wonder whether multi-threading might be the only possible answer here. That would be a great amount of work - certainly not suitable for a bugfix release. I might well just have to release 10.11 as it is, and set the server game to "assume_everywhere_connected_by_road" for the time being. The trouble with multi-threading, though, is that it would be enormously difficult to synchronise accross the network. The only way that I can think to do it reliably is for the server only in a network game to run a private car route finding thread (a single thread dedicated for the purpose running constantly), and for it to push the results of its updating work to all of the clients as it goes. That way, on server games, only the server itself would have to have a multi-processor machine in order to get acceptable performance.

Edit 2: What do people think of OpenMP (http://en.wikipedia.org/wiki/OpenMP)?
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: inkelyad on March 24, 2012, 11:33:29 AM
Quote from: jamespetts on March 24, 2012, 11:08:27 AM
The problem is that we need to find not just the answer to the binary question of whether a city is connected at all, but the quantitative answer as to what the quality of the connexion is. A connexion by a meandering dirt track should attract far less traffic than a connexion by a motorway.
Pick a city as start point. Flood road network  with "journey_time to start point" values. For each city in connected component store value from flood to where you need it. There is no need to repeat this via calc_route for each pair.

Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: kierongreen on March 24, 2012, 11:48:34 AM
There's some discussion elsewhere about multithreading in simutrans at the moment. There's limited scope for it but many functions need to be carried out in a single threaded manner as it stands at present.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 24, 2012, 12:15:38 PM
Kieron - interesting. Is this discussion on one of the public boards? If so, I should be interested to see it.

Inkelyad - hmm, perhaps I am being dim, but I do not quite follow. What do you mean by "store value from flood to where you need it"? What I had imagined that you meant was a system that produced a binary answer to the question, "is city A connected to city B?" by inferring in some cases that, if city A is connected to city C and city C is connected to city B, then city A must be connected to city B. This method is not useful, as there might be a faster route between city A and city B than via city C, and we need to know the journey time of the route. If this is not what you meant, apologies for having understood you incorrectly - clarification would be much appreciated!
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: inkelyad on March 24, 2012, 02:11:20 PM
Dijkstra's algorithm where cost of edge == journey time.
Then you can build private car routes from resulting tree.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: chicken on March 24, 2012, 04:31:03 PM
You shouldn't need to worry about synchronization with the rest of Simutrans when writing a parallel algorithm -- you just use parallelization to speed up that particular computation, then return the answer when it is done. OpenMP is one particular way of doing this, it is good at fork-join style parallelization. You should probably consider it. There is an associated library (GNU OpenMP) and a compiler flag (-fopenmp) to help support it in GCC. Bear in mind, not every graph algorithm is amenable to parallelization, and don't be surprised if your initial attempts make things worse.

Other things to consider: dynamic updates to SP problem. http://www.cs.uwaterloo.ca/~epfchan/publication/sptdg.pdf (http://www.cs.uwaterloo.ca/~epfchan/publication/sptdg.pdf)
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: chicken on March 24, 2012, 05:41:18 PM
Looking at the source a bit, it seems that you are doing A* search tile-by-tile and running that for every (unordered) city pair. If that's the case, then there ought to be significant opportunities to trade off space for time, as there should be overlap between many different routes.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: kierongreen on March 24, 2012, 05:58:17 PM
Summary of discussion:
* What slows down simutrans is not generally one run through a particular algorithm, it is the cumulative time taken by repeated runs. Almost always these runs must be made in the same order (even more so for network code). So performance increases through multithreading are quite difficult to achieve.
* There also tend to be unforeseen consequences of multithreading as almost all operation in simutrans are connected to other parts of the code.
* Multithreading does not help all platforms equally, even where multiple cores are present. Memory bandwidth can often be a limiting factor.

That said, I've managed to get certain operations (rotation for example) to go faster through multithreading, but these are relatively few and far between.

In this case I doubt multithreading will help as you still need 15 minutes of processing time (on a relatively powerful machine), so you will have to change to a more sophisticated algorithm, or simplify the code which currently requires it.  15 minutes divided by 7 (8 cores minus one being used for rest of game) for example is still 2 minutes per game year - still hugely excessive for one algorithm.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 24, 2012, 11:57:45 PM
Thank you for all the suggestions and information - most helpful. Inkelyad - I don't see how Dijkstra's algorithm could assist here, as there would be no way of knowing (as far as I can tell) whether, for any given city pair, there was not a direct route that did not pass through any other cities that was shorter than any other route without doing the very same A* search between each city pair as is done already.

As to multithreading, it would, as Kieron points out, be very hard to synchronise without it being done exclusively on the server as I propose (and I worry slightly that doing it that way would greatly increase network traffic). The problem is that different clients' worker threads would finish any given element of the task at a different point in the execution of the main thread to each other, which would cause different clients to behave differently, causing network desyncs.

If there was one thread just for the private car routes on a powerful multi-core server updating all the routes in the background in a game in which only the server had to perform this work (and simply push the updated results to the clients when they are ready), the fact that it takes quite a long time should not matter too much, especially in a game where the length of each month is quite long, although I accept that it is not ideal. If there was some way to optimise the algorithm, that would be the best option, although I'm not sure what it might be yet, unless I have misunderstood the suggestion relating to Dijkstra's algorithm somehow.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: chicken on March 25, 2012, 12:37:40 AM
Parallelism is entirely deterministic. If you're not seeing that behavior, then either there's a bug in your code, or you've actually implemented a "concurrent" algorithm. But kierongreen is right that at best, you will only see a constant speed-up which is not sufficient.

I think ultimately you need to find ways to avoid repeating work (e.g. use dynamic programming). I also think that there must be some way of taking advantage of your relatively simple representation of maps and road networks; either through partitioning or heuristics such as the one that A* uses already.

Speaking of the heuristic, I have a slight concern about its current implementation. If I'm understanding correctly (and I don't know German), you are using straight line distance as the heuristic (a natural choice for maps). However, it is possible that this heuristic is non-monotonic. Following it one step could lead you to a situation where you have more difficulty reaching your end goal (lower speed limits) than before.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 25, 2012, 12:53:49 AM
I haven't written any multithreading code for Simutrans yet - what I write above is based on what I understand of how multithreading works, although I have never looked very deeply into it, so forgive me if my understanding is incorrect. I do not know the exact meaning of a "concurrent" algorithm, but suspect that that is what I had in mind, in that there would be a thread created at the start of the game and persisting thereafter working its way through updating road connexions marked as stale by the main thread and unmarking them stale, only interacting with the main thread to lock the variables that it updates at the moments that it writes to them. A system that requires the main thread to wait for the road connexions thread to reach a certain point before continuing would not really help much in terms of speed, I don't think.

As to the A* algorithm, this comes from Standard, and is the same algorithm used for player vehicles finding their way about the map: I have not altered this at all. If you can think of any way of making it faster, I should be most interested, and the Standard developers might be interested, too.

As to dynamic programming - can you elaborate?
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: chicken on March 25, 2012, 02:17:11 AM
Yes, that is a concurrent algorithm. Generally speaking, if you start thinking about locks, communication, or interleaving, you're dealing with concurrency. Parallel threads, on the other hand, have no interaction with each other. For example, OpenMP provides a construct that allows you to execute the iterations of a "for loop" in parallel. In order to use it safely, you must not write code which touches the data other iteration steps are using (pseudo-syntax):


parallelfor(i=0; i<10; i++)
array[i]++; // OK



parallelfor(i=1; i<10; i++)
array[i] += array[i-1]; // bad!


Dynamic programming is the method of breaking down a problem into subproblems in order to solve it -- in particular, most people think of overlapping subproblems -- so that the solution to one subproblem can be stored and used later when it is needed again.

Shortest path algorithms tend to fall into this category. For example, suppose you had already computed the best route from Chicago to San Francisco. Now you are working on the best route from New York to San Francisco, and you find yourself at Chicago. Great! You already know the answer from here, so you look it up and are done.

The general shortest path problem is usually broken down into categories: Single-source, Multi-source, and All-pairs. The Bellman-Ford algorithm was one of the first single-source algorithms, and also one of the first examples of dynamic programming. Dijkstra is as well, and faster for graphs with non-negative edge weights. A* is single-source using an admissible heuristic to guide breadth-first search. Some famous examples of all-pairs shortest path are Floyd-Warshall and Johnson's algorithm. These also happen to be easily parallelizable.

Although you are trying to solve shortest paths for all pairs of cities, since you are working tile-to-tile, the all-pairs algorithms are too computationally and memory intensive to be used. Instead, you want to solve it between a (relatively) small subset of the vertices. That's why I suggested some kind of dynamic programming solution. Suppose you are searching for the best path between cities A and C, and you expand a vertex that is on the already-computed path between B and C. Then you can reuse that portion of the path. I think this will come up a lot because the intercity roads are probably used by many different paths in most games.

That still leaves an awful lot of data to store. You need to put some kind of indication on each vertex to say what paths it belongs to. One possibility to reduce this overhead might be to only do it periodically, instead of for every vertex. Or you could try to identify road hierarchies (e.g. determine which roads are intercity highways and which ones are local roads).
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: isidoro on March 25, 2012, 02:33:38 AM
Just a quick idea to deal with some cases.

Prerequisite: you have a table with pair distances for every pair of cities.

Somebody breaks your network at C (erases a tile there).

Calculate all possible distances from C to all cities.

Now we will select all cities that are affected by point C (mark them dirty):
  repeat for every pair of cities not dirty at the moment A and B
    if distance(A,B)=distance(A,C)+distance(C,B), mark dirty A and B

Rebuild your table with your present algorithm, bun only for dirty cities.


Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: kierongreen on March 25, 2012, 09:16:44 AM
QuoteIn order to use it safely, you must not write code which touches the data other iteration steps are using
And simtrans does this, many times, in many places. Short of a complete code rewrite there's not a lot that can be done about this. So while a pathfinding routine might be safe to run in parallel threads on it's own, it is not with the rest of the simutrans code.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: isidoro on March 25, 2012, 10:57:18 AM
Well, there is much to be said about all that of multithreading...  In fact, I work on that myself.

Generally speaking, multithreaded programming is much, much more difficult that single threaded and requires some expertise.  A lot of unexpected errors may happen and, worst of all, those errors are erratic (some times the application works, some times it doesn't) because there is a factor we don't control: thread scheduling.  Either parallel threads don't use the same data (or the state is irrelevant, which is nearly always not the case) or you have to build critical sections among them.  But in that case, a dreadful threat arises too: deadlocks...

Not to mention problems with compatibility among systems.  For instance, I don't know a portable way for separate threads to deal with GUI input for each separate window apart from the trivial one that one thread takes all and delivers messages to the other by other means...

In a big, running project like this, I would advise you not to go into this field unless you know very well what you are doing...

Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: chicken on March 25, 2012, 04:28:44 PM
Quote from: kierongreen on March 25, 2012, 09:16:44 AM
And simtrans does this, many times, in many places. Short of a complete code rewrite there's not a lot that can be done about this. So while a pathfinding routine might be safe to run in parallel threads on it's own, it is not with the rest of the simutrans code.

It wouldn't be running concurrently with the rest of Simutrans code. It would be replacing what is now done serially. As long as each parallel thread does not trample on the data the other threads are using at that moment, then there will be no difference to the rest of the system, and it will only be noticeable by the way it uses more than 100% CPU.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 25, 2012, 04:59:27 PM
Update: I have released version 10.11 as it is for the time being, and set assume_everywhere_connected_by_road=1 on the server game while a further solution is sought. This issue is clearly one that can only be solved with considerable work, and in a major release.

Chicken - do you think that a concurrent algorithm is the right approach for this scenario, or is there some advantage to using a parallel approach here? Isidoro - would the concurrent approach that I suggest (pushing updated data to the road connexion tables on all the clients simultaneously) circumvent the difficulties that you enumerate above?

As to optimisation, things are not as simple as one might imagine: if the program has already found a shortest path between City A and City B, and is looking for a path from City C to City A, if it has reached somewhere in the city limits of City B, that will not necessarily assist in re-calculating the part of the route from City B to City A, as the routes are calculated from one particular tile in each city to the equivalent tile in each other city (the road tile immediately outside the town hall), so, unless the best route happened to pass through that particular tile, the method that you suggest above would not assist in this case (and, overall, would probably have only a very limited impact).

Isidoro - the problem with simply checking for breaks in the network is that this does not account for the (important) possibility that the existing route is left entirely intact whilst a new and better route is built between the cities. This is why I implemented a periodic re-check algorithm instead of a system that looks specifically for broken links.

Thank you all for your input so far!
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: chicken on March 25, 2012, 05:16:40 PM
Either may help, but a concurrent algorithm is subject to all the ordering and synchronization problems you have brought up. Carefully applied parallelism can bring some constant factor speed-up to certain algorithms in the code, but that doesn't sound like it's enough.

Recall that in order to find the shortest path between City A and City B, you also had to find the shortest path to City B on all the tiles that lie in between (this is called 'optimal substructure' by the way). So I'm proposing to hold onto that information in some form. This is the trade-off between space and time. We could save a lot of time by remembering paths that have been computed recently, and reusing them whenever possible, but storing all this information could also lead to an extreme blow-up in memory size. So it is likely that some compromises will need to be made. For example, you could only store path information on vertices with degree at least 3.


A ---------+----------- B
           |
           |
           C




Since you have computed A-to-B, when working on C-to-B you find that at the '+' you already know the shortest path to B, so you are done. Also, since we're working bidirectionally, you now know the shortest path C-to-A.


Perhaps that is still too much memory, in which case, you could consider some sort of road classification system based on certain criteria. For example, it may be possible to identify "intercity" roads and only save information about degree-3 nodes while traversing them.

Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: kierongreen on March 25, 2012, 06:07:58 PM
Well, I think optimal memory usage I think you can hope for is to store direction from each tile to proceed to a particular city. This requires 3 bits per tile (2 for direction, 1 to indicate if it is possible). If you store that for all tiles that is mapsize_x*mapsize_y*(3*number_cities/8) bytes - for a 1024x1024 map with 200 cities this would be 75MB, but 2048x2048 with 800 cities would be 1.2GB. So you would have to store it for road tiles only somehow. Storing a value like this would instantly allow you to check when deleting a tile whether this broke an existing connection, however the stored route might become stale (not the fastest) over time without refreshing.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 25, 2012, 06:58:08 PM
I had considered using fragmentation in the past, but it strikes me as extremely difficult to implement reliably. One idea would be simply to store routes, but this might lead to very high memory consumption given the number of possible routes as calculated above. Kieron's idea about storing optimum directions is interesting, although is still possibly subject to the problem that the data might become stale by the implementation of a faster route somewhere else that makes the correct direction on any given tile different to the previous optimal direction in a way that can only be tested by a complete recalculation of the whole route without the aid of the previously stored directions, and this sort of recalculation would have to be done frequently if better routes were not to be missed for a long time, so it seems on the face of it that this cannot be optimised further by this method.

I should be interested in any other thoughts on optimisation, however, that are able to surmount the perennial issue that there might be a completely different and faster route built at any moment.

As to a concurrent algorithm, in the example of the particular concurrent algorithm that I suggested, where does the possibility for deadlocks, etc., arise? If all that the private car routes thread does is work its way through a list of stale connexions to be recalculated in the order that they became stale, recalculate them (which would not itself require changing the state of anything on the heap), then interrupt the main thread to push the new results (which, if the main thread were running on a server, it would then push to the clients: the clients would not run their own private cars thread), where is the possibility for deadlocks, race conditions or desynchronisation between client and server?
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: isidoro on March 25, 2012, 07:12:28 PM
@James:  I agree with chicken that running some threads would not benefit the problem very much.  You can only get rid of the unresponsiveness somehow.  But there may be not enough time to keep the roads connections statistics updated if the city number is big.

Regarding the algorithm I proposed, it is only an example of possible optimizations.  The rationale behind them is that most modifications in the road network will surely not affect but some of the cities and you recalculates all of them.  And time of calculations depends much on the city number.

Another optimizations can play with physical distance in the map (based on coordinates) vs. distances by road, since the latter will always be greater than the former.

You can extend my idea to adding new roads too.  In that case, you would have:

Prerequisite: you have a table with pair distances for every pair of cities.

Somebody joins your network from points D to E.

Mark dirty all new connected cities

Calculate all possible distances from D to all cities.
Calculate all possible distances from E to all cities.

Now we will select all cities that are affected by point D and E (mark them dirty):
  repeat for every pair of cities not dirty at the moment A and B
    if distance(A,D)+distance(D,E)+distance(E,B)<distance(A,B) or
       distance(A,E)+distance(E,D)+distance(D,A)<distance(A,B), mark dirty A and B

Rebuild your table with your present algorithm, bun only for dirty cities.

Edit: you have posted while I was posting...  You can have problems in the following scenario:
The last may not apply to the current network model of ST.  I don't know how network mode is implemented.  So, the last points may not make sense...
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 25, 2012, 07:20:31 PM
Isidoro,

that's an interesting idea - a sort of radius effect? The complexity there is that different roads might have different speed limits, so the existing connexion might be the shortest but not the fastest, so there would have to be a margin of latitude, and then a method of calculating the margin of latitude, but in principle it should be possible to say: if a change to the road network occurs, only mark as stale connexions to and from any cities within X radius of the change (and then only update the cities connexions in their assigned months). One problem with this might be that the addition of a new city road by a city is (and needs to be) enough of a change to a road network to make an existing route that could possibly go through that tile possibly stale, and city roads are being updated automatically all the time, so, in a well developed game with fast growing cities, this method might well produce only marginal savings. I assume, incidentally, that you had imagined this being done in addition to the multi-threading?
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: chicken on March 25, 2012, 07:24:19 PM
I wasn't proposing to store the data long-term, only until the current recalculation is complete. The point is to avoid redundantly computing the same path over and over again by memoizing intermediate results.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: isidoro on March 25, 2012, 07:24:38 PM
Again, we have crossed our postings again...  :D I have to go now (to the movies).  I'll keep the conversation later.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 25, 2012, 07:30:31 PM
Isidoro - it was for this reason that I proposed using the server to push the results to the clients rather than simultaneously calculating the results on server and client (as is done for everything else in Simutrans). Would this not suffice to solve the problem?

Chicken - hmm: what exactly would count as "the current calculation" here? The current system, and so far all imagined alternatives, comprise in effect a constant rolling recalculation.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: kierongreen on March 25, 2012, 07:37:52 PM
Using directions we can use the following to recalculate directions when a road section is built :

how many existing road sections is the new road connected to?

0:
set all directions to unconnected

1:
set all directions to the connection if this is connected

2 or more:
loop over each connection counting weight to destination - if no connection then discount this connection. if no connections left set new route as unconnected

test to see if any tiles in these routes overlap (even if it is destination tile) - if so we have a route "triangle" with sides 1:weight(connection a->overlap), 2:weight(connection b->overlap) and 3:weight( connection a->connection b) - if side 1+side 3<side 2 or side 2+side 3<side 1 then we need to recalculate either side 1 or 2. To recalculate we work out the crossover point (where the route along sides 1 and 3 equals that along side 2) and point all directions closer than that to new route. We then discount this connection from further calculations in the step below

then for each tile in the new section choose direction leading to lowest (weight tile to connection)+(weight connection to destination)

Since each tile already knows the fastest route to the destination calculating the route weighting should be relatively quick. Upgrading an existing way would be slower, as you would first have to simulate breaking the connection, then re-adding it.

Edit: we need a final step, if we have connected a connected and unconnected connection - in this case we work back along unconnected connection setting directions toward us (if any of these happen to meet then we will need to compare weightings and set directions appropriately)
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: chicken on March 25, 2012, 07:38:33 PM
Well, for example, you take 12 months to recompute the data, so any stored information could be considered stale 12 months after it is calculated.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: Vladki on March 25, 2012, 07:45:00 PM
Hi all,

I'm not sure I understand the background of this problem, so excuse me if I'm totally wrong. I think it's worthless to calculate connections for each pair of city - complexity of n^2. It should be enough to check (and store) direct connections from each city. Just follow the roads leading out of the city and stop in the first city you get to. Then the complexity is n*m (where n - is number of cities, and m is number of roads leading out of the town - usually less then 10). Indirect connections then can be derived from stored direct connections much easily.

And of course the recalculation should happen only if there is some new city (attraction, factory). If some road modifications happened in the area od some city then recalculation is needed only for direct connections of the affected city, not the whole map.

Multithreading will not help much - reducing complexity is needed.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: isidoro on March 25, 2012, 10:56:46 PM
Vladki, your post makes sense to me at first sight.

Quote from: jamespetts on March 25, 2012, 07:30:31 PM
Isidoro - it was for this reason that I proposed using the server to push the results to the clients rather than simultaneously calculating the results on server and client (as is done for everything else in Simutrans). Would this not suffice to solve the problem?

I think that I answered before, but we were crossposting then...  The problem may arise if the new information doesn't arrive at the same simulation time in all nodes and happens that some of them use the old values and some of them use the new values.  As I said before, with concurrency there are always problems lurking around at unexpected places...
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 25, 2012, 11:13:35 PM
Isidoro - by "nodes", do you mean network clients?

Edit:

Kieron - how does this get around the issue of it not being helpful to know the directions in the event that a new, faster route has come into existence and that it is rarely possible to know that a new, faster route has not come into existence?

Vladki - thank you for joining the conversation! New ideas always appreciated. The problem here, though, is that, although we are discussing things in terms of connexions between cities, that is slightly imprecise: the actual routes are calculated between a specific road tile in one city and a specific road tile in another city (the road tile immediately outside the town hall). So, if we get the direct connexions from City A as going to City B and City C, and we are looking for a connexion from City A to City D, which has a direct connexion to city C, the fastest route from City D to city A might well go through City C (as in, through the city limits of City C), but not go through the town hall road tile in City C. In some cases, this difference might be trivial, but in other cases it might be very great - by orders of magnitude of journey time in the right circumstances.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: kierongreen on March 26, 2012, 05:58:59 AM
That algorithm should update the directions whenever a faster route is built. With all directions across the map known it should then be quick to calculate route weightings when required.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: inkelyad on March 26, 2012, 06:51:21 AM
Quote from: jamespetts on March 25, 2012, 11:13:35 PM
the actual routes are calculated between a specific road tile in one city and a specific road tile in another city (the road tile immediately outside the town hall).
Quote from: jamespetts on March 25, 2012, 11:13:35 PM
but not go through the town hall road tile in City C. In some cases, this difference might be trivial, but in other cases it might be very great - by orders of magnitude of journey time in the right circumstances.

Do we really need to be that precise?
We have all this troubles only for 'find private car traffic density', right?
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: isidoro on March 26, 2012, 12:55:10 PM
@James:  yes.  Nodes=clients.  Clients would desync if you don't mark the same simulation time in which the information generated by the server may be used by the clients.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: Vladki on March 26, 2012, 07:57:34 PM
jamespetts: Could you please enlighten me why is this calculation done in the first place? What are the results used for? Maybe then I can come up with something smart :)
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 26, 2012, 09:16:58 PM
Kieron - ahh, perhaps I had misunderstood exactly how what you were proposing was to work. Might I ask you to elaborate a little, in that case? I can't immediately visualise how things would fit together at present - apologies if I am being dim.

Isidoro - this could be solved fairly easily by treating results from the private car pathing thread in much the same way as the (even more undeterministic) player input, could it not, and simply using the standard method in simwerkz.cc to issue a queued command to clients to update their private car routing tables? The possible problem from this is that it might involve a lot more data transmission over the network - some calculations would be required as to how much that this would generate to see whether ordinary home ADSL connexions could cope.

Inkelyad and Vladki - the purpose of the system is to simulate as accurately as possible within the constraints of what can be achieved in Simutrans the competition between private cars and public (player) transport. The system reads from a configuration file the proportion of people in any given year with access to a private car, randomly assigns (based on the weighting factor given by the percentage of car ownership at the present time) packets of passengers generated to having or not having a private car, and, for those who do, compare the private car journey (if the destination is reachable by private car) with the public transport journey (if that is available) to determine which of the two options that passengers take. That decision is based on part on the relative journey times of the two methods. (The full method of selection can be found in stadt_t::step_passigere() in simcity.cc). If the passengers can use public transport, but either do not have access to a private car or have access but the journey time of the private car is outside their tolerance, then, provided that the journey time for the public transport is within their tolerance, they will always take the public transport. Conversely, if players have access to a private car and the private car journey time is within their tolerance and there is no available public transport route (or no available public transport route within their time tolerance), they will always take the private car. If there is no journey to the destination available at all, or all journeys exceed the passengers' journey time tolerance, they will not travel.

Each private car trip is logged in the origin and destination city (or, if travel is within a city, in that city), and these numbers go into making the "traffic" figure seen in the city and world graphs (world statistics can be accessed from the city list window). The city version of the statistics are used to determine congestion (see the algorithm in simcity.cc for more details: congestion is calculated based on the number of private car trips and the size of the city). Congestion has two effects in the game: (1) it slows the growth of towns (stopping growth completely if congestion is at or above 100); and (2) makes passengers travelling to, from or within congested cities more likely to use public transport instead of private cars in proportion to the congestion.

I hope that this clarifies matters! Thank you all for your very helpful input.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: kierongreen on March 26, 2012, 10:28:49 PM
The idea is that each roadtile stores the direction of the neighbouring roadtile which is closer to a particular destination. By looping over this you can construct a route to the destination (but much quicker than search for a route). Think of it as storing a signpost on each tile with the direction to every city (but no distance).
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: isidoro on March 26, 2012, 10:45:58 PM
Quote from: jamespetts on March 26, 2012, 09:16:58 PM
[...]
Isidoro - this could be solved fairly easily by treating results from the private car pathing thread in much the same way as the (even more undeterministic) player input, could it not,
[...]

Sure.  They are one and the same problem.  So, if that is solved in the present code, I have no objection to your approach.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 26, 2012, 10:53:47 PM
Quote from: kierongreen on March 26, 2012, 10:28:49 PM
The idea is that each roadtile stores the direction of the neighbouring roadtile which is closer to a particular destination. By looping over this you can construct a route to the destination (but much quicker than search for a route). Think of it as storing a signpost on each tile with the direction to every city (but no distance).

Hmm - how would this interact with updating directions whenever a faster route is built? In other words, I cannot imagine any circumstances in which a route would need to be rebuilt, but the existing directions data are still valid: the only circumstances that I can think of that would trigger a route rebuild are ones that would also invalidate the directions data - does that make sense? Have I missed something?

Edit: Incidentally, has any consideration been given to putting the sync_step() methods into a different thread to the step() methods? Was it decided that this was not possible because sync_step() and step() methods both need to alter the same variables (if this is so)?
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: inkelyad on March 27, 2012, 05:50:33 AM
Quote from: jamespetts on March 26, 2012, 09:16:58 PM
... compare the private car journey (if the destination is reachable by private car) with the public transport journey (if that is available) to determine which of the two options that passengers take.
So we don't need routes. Only distance (in minutes).

Once per month run flood from each city to find distance and reachability for each road tile. Average that to 8x8 tiles grid. Store and use in passenger decision.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: sdog on March 27, 2012, 05:57:01 AM
assumptions:
- with time road infrastructure improves if there is not a major geographical barrier preventing it.
- player action reducing interconnectedness is limited

form groups of connected cities while checking

build first database:
- start with a random ungrouped city and assign it to the group n
- check ungrouped city if connected add to same group, repeat for all cities

During game only check
- if a random city in group n is connected to group m, if yes join groups
- if cities are connected to at least k>1 cities of their group, if not create new group (choose k very small)

this does not cover groups of connected cities breaking up again, but single cities becoming isolated
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 27, 2012, 06:34:08 AM
Briefly, and for the moment not responding to the above as I am short on time, I omitted one important aspect of the description of the system above, which is this: journey times are calculated by taking the journey time for the distance from the city hall in one city to the city hall in another city (the exact method of calculating the journey time can be found in simcity.cc, but it is based on the average speed of available cars and the maximum speed of each road tile through which the route passes), then using that combined with the straight line distance between one city hall and the next to get a journey time per straight line tile value, which is extrapolated to calculate the journey times of all other journeys between any given specific point in the origin city and any given specific point in the destination city, as, in Simutrans, journeys are always made from and to specific buildings. Attractions and industries are also included in this.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: isidoro on March 27, 2012, 01:03:39 PM
Quote from: jamespetts on March 26, 2012, 10:53:47 PM
[...]
Edit: Incidentally, has any consideration been given to putting the sync_step() methods into a different thread to the step() methods? Was it decided that this was not possible because sync_step() and step() methods both need to alter the same variables (if this is so)?

Yes.  If you are not careful enough you can get race conditions, deadlocks, etc.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: kierongreen on March 27, 2012, 01:37:49 PM
sync_step and step cannot run at the same time, I'm playing around at the moment with multithreading in step, but it is quite tricky!
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: isidoro on March 27, 2012, 01:47:35 PM
Small OT:  Before going multithreading, I would try to solve this issue that puzzles me a lot: what on earth is ST doing while in pause mode with a rather small map (320x256) to eat up 25% of my CPU time on a quite decent machine?

I would expect a consumption near 0% in a paused game, wouldn't I?

Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 27, 2012, 05:03:29 PM
Kieron - may I ask: what multithreading architecture are you using? OpenMP or something else?

Isidoro - is this just in Experimental, or is this also in Standard?
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: isidoro on March 27, 2012, 06:11:06 PM
Sorry, OT then.  In Linux, Standard, I observe that...  What do you observe in Windows Experimental?  What is the CPU consumption in pause mode?

Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: Carl on March 27, 2012, 07:22:09 PM
(I too find that pausing in Experimental only halves the CPU load. Doesn't eliminate it entirely.)
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: kierongreen on March 27, 2012, 09:44:08 PM
pthread
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on March 28, 2012, 10:34:13 PM
Kieron - may I ask, was there a particular reason for using pthread?

Inkelyad (above - that I did not have time to answer before): I am not very familiar with the flood algorithms, and so am having trouble understanding how what you propose would work. Is this much different to finding a route from everywhere to everywhere (which would take more time, not less)? How would this produce a journey time figure (or, at least, a journey time per straight line tile figure) from a start point to an end point? Apologies if I am being dim...

Sdog,

if I understand you correctly, your system would produce a binary answer to the question "Is city A connected to city B", whereas what we really need is a journey time from any arbitrary point within city A to any arbitrary point within city B (which can be abstracted, as now, by using journey time per straight line tile figures for each city connexion). It is important that the extent to which people use cars between particular cities is affected by the quality of the road network between those cities.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: inkelyad on March 29, 2012, 05:41:45 AM
Quote from: jamespetts on March 28, 2012, 10:34:13 PM
Inkelyad (above - that I did not have time to answer before): I am not very familiar with the flood algorithms
I have habit to to use 'Dijkstra's algorithm' and 'flood algorithm' as synonymes.
Quote
Is this much different to finding a route from everywhere to everywhere (which would take more time, not less)? How would this produce a journey time figure (or, at least, a journey time per straight line tile figure) from a start point to an end point? Apologies if I am being dim...
There is difference between "find distance from this point to everywhere" for each destination point (that is, running pathfinding algorithm for each destination point) and finding it in one big sweep.

Unfortunately, we are trying to solve problem on flow network (http://en.wikipedia.org/wiki/Flow_network). This is hard and cpu-hungry. You will find a lot of computer science if you just google "flow algorithms".
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: prissi on March 29, 2012, 07:25:23 AM
In those cases, a regional pathfinder may help. I.e. the pathfinder finds first a path between citys and then from those points in the city to the place which where actually in question. This may result on bad routing for vehicles (i.e. driving forward and backward the same way for a short time) but provides much faster answers. I did a regional pathfinder for ships once, but due to this problems it was never included. You find the remains in experimental-hierachical-patchfinder.diff in the patches subdirectory of the SVN.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: kierongreen on March 29, 2012, 05:59:24 PM
QuoteKieron - may I ask, was there a particular reason for using pthread?
Because it works, seems quite simple and doesn't add any dependencies!
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: sdog on March 29, 2012, 06:05:31 PM
James, you only need to run the actual path finding for cities that are connected, and only do it once until this state changes. You can also do test calculations between two groups of cities from time to time, if the time changes fundamentally, you can re-calculate.

The idea here is to reduce the time you need to run this algorithm as much as possible to get enough data necessary for a good enough model of car ownership through the assumption of a well behaved game. (that is players trying to break it artificially)
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: chicken on March 30, 2012, 02:01:02 AM
pthreads isn't a library for parallelism, it's an API for creating and managing threads. You would have to implement the desired notion of parallelism using the low-level functionality of pthreads. GNU OpenMP, for example, may be implemented using pthreads on Linux. pthreads is extremely low level, whereas something like OpenMP provides abstractions that are relatively high level.

If you are going to work at the level of pthreads, there isn't a notion of "choice" involved here. POSIX threads are simply part of the operating system interface (hence, no dependencies). Sure, you could probably get by using Linux-specific functions like "__clone" but who'd want to?

I still think you'll get more mileage from caching paths and avoiding redundant work.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: Vladki on March 30, 2012, 06:43:24 PM
I still think about the city distance calculations and private/public transport decision. If I understand it correctly the calculated distance is used only as a factor in deciding whether to use private car or public transport. In real world you also decide on approximate information from road map (google maps are here only last few years). So for initial guess it would be enough to use distance between city halls of neighbor cities, and ignore the fact that there may be a shortcut through the suburbs. I suppose that if a private car trip is chosen, its routing is done independently of the discussed calculation. But it would be worth to record the real trip time in some table to continually improve the data. So then you would have tho tables of trip times between cities based on real times. But like in real world you would make decision on sometimes obsolete data - roads get repaired, closed, new highways are built, bus lines change, and so on. So sometimes you decide badly, simutrans citizens would also make such mistakes. So, would this be feasible?
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: merry on April 03, 2012, 12:47:00 PM
HI Guys,

Been reading through the thread, and i'd like to suggest some algorithmic ideas which may - or may not - be of use. I'll include some from other posters because it's good stuff, and fits in. Yes, it's a condensation of much of the above discussion, but I hope it helps clarity.

1. Calculation of routes & timings for citycars is taking too much time.
In common with many posters, I'd expect brute-force routing to all places from all places will be very (prohibitively!?) intensive.
So the idea of maintaining connectivity charts seems highly sensible, and only making changes to the table when the route network changes.
What seems to be the most likely to work is to maintain in each city, or nodal point (if that works better), a table of directly connected destinations. For each of these (by cascade/tree link) the indirect links possible through these can be obtained. This will yield a list with all possible destinations (and distance/time) but would not require brute-force calculation of anything but direct links for time & distance.
The result would likely be a number of mini-tables which contain the same destination with differing distance/time values. The list could be re-sorted into a single table to indicate the best route from one city to another city. Although a sort takes time, it's worth it because it does not happen often, and can be consulted often. And maintaining mini-tables for each city exit adds value: only the mini-table is recalculated when a route changes, and then the mini-tables collated into the master table as a combination-and-sort (not calculate) operation. Other mini-tables remain unchanged and if the master table contains tags of the mini-table a route came out of, only those particular entries need be updated (althoguh whether that would save time is questionable!)

2. The high rate of change in city road nets is a problem, as is cross-city transit time.
I suggest that each link out of a city (ie a place where a road crosses the city limits) be considered the point where routing is calculated from / to, not the city hall. For each of these boundary points, there is a (probably small) table of directly and indirectly connected cities, and an 'add-on' distance to the local city hall, and maybe a table of cross-city distances to other intercity routes to allow better through-traffic data. Thus the inter-city times are affected only by inter-city route net changes, and intra-city changes only affect local data. If cross-city distances/times only change a bit, there is no need to update other connected cities with the transit time as it's inconsequential on a long journey.
One benefit of this is that we will know the shortest route from the city boundary to the next city, which will generally be on the closest side, and avoids the problem of the city hall being much further from or closer to the starting point than the route out of the city!

3. Only update those links that change
And cascade the data up the tree at a controlled rate, as a background task, ie in a part of the program that is not time critical and can be freely interrupted. After all, signage to other cities will not be changed instantly in the real world when a distant route changes.

As James points out, connected industries, attractions, etc are similarly treated as cities.
this does much increase the number of conneted nodes, and I hope that the 'tree' approach above would reduce the amount of calculation made for routing.

As i think was noted earlier, a citycar probably has to calculate it's own way out of the city. This is consistent with finding one's way to the main road out of town, or to the long-distance public transport stop/station. My one concern is that this will possibly add much time to routefinding, but i suppose the approximate time/distance can be taken from the city hall for decision-making purposes. Doesn't work so well for a starting point on the outskirts of a large city, but maybe we can live with that? Lots of people don't work out the distance very accurately before they start a journey! Perhaps this aspect of the problem deserves some more attention, but I would suggest it is a small part of the total result, and not be allowed to drag the complute time out very far.
Actually, here's a simple solution to the issue: calculate the distance to the city hall and to the exit route point  (straight line/euclidian) and route to the nearer of the two from your start point (and do the same from the destiantoin city entry to the destination point). This might be a tolerable approximatoin for timing, if you use the mean city traffic speed.

Hope this helps, afraid I can't do the detail code stuff (never got my head round C let alone C++, let alone having time to do it) but this looks more like algorithmic problem-solving so far. Respect to those who can actually code the algorithms to make it work!
TTFN
Merry.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on April 03, 2012, 11:27:15 PM
Merry,

thank you for your contribution - some interesting ideas. I don't have time presently to respond fully, but one or two brief questions, if I may: firstly, what exactly do you intend counting as a "direct" connexion - one that does not pass through another city at all (even peripherally), or one that does not pass through a certain point in another city? Secondly, there is much to be said for the idea of separating intra-city and inter-city routing, but this also has drawbacks, the most prominent of which is the frequency with which city borders change. Can you think of a sensible way to deal with the rapidity of the change in city boundaries in a growing city?

Finally, a more general point: currently, the route finding system is quite basic in its functionality, as it just enables educated guesses as to the journey time between two given points on the map based on an average journey time per tile value. What I'd ideally like to do at some point (and have wanted to do for some time) is to map actual routes for private cars, and have the private car objects in the game actually follow these routes, and calculate congestion, not at present using a somewhat approximate model based on counting the number of cars in a city and considering the size and density of the city, but actually measuring how long that any given road tile has stationary traffic on it in any given month, and calculating congestion by individual road tile, as is done in Sim City, then using that congestion data as a cost in routing calculations for both private cars and player vehicles. Those congestion data could also be used to calculate a city's overall congestion level to use when determining a city's growth, as well as being used to determine the particular likelihood of passengers using their car for the particular trip, given the overall congestion level of the best route.

Obviously, it would not be possible to calculate entire routes from every building on the map to every other building on the map (as already demonstrated, this is not even possible for whole cities), but a system that calculated routes within cities separately to calculating routes between cities, and then glued together three routes for every inter-city trip (from the origin point within the origin city to the boundary, from the boundary of the origin city to the boundary of the destination city, and from the boundary of the destination city to the destination point) might be feasible.

The difficulty is that this would be a very, very large amount of work to implement overall. (I also worry a little about memory usage). Ideally, what would be good is a system that I could implement now to do the same work as the current system does, and to which I could add later a system that deals with individual routes. Suggestions that go to that aim would be particularly welcomed.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: merry on April 04, 2012, 11:34:24 AM
HI all,

Well, let's address the points in turn:
What's a direct connection?
One which starts at a city boundary, and ends at another city boundary.
Any route which passes through a city is 'indirect' in that the route has more hops.
An indirect route is made up of multiple direct routes plus cross-city links. The links are approximated as a euclidian distance (at least initially) and stored in each port's data.
Each city maintains a list of the 'ports' (i.e. exit tile) by which it links to other cities, and a list of the destinations reachable, with the port to use. Rather like an ethernet switch I suppose! The beauty of this is that the city route table can refer to the ports by some kind of pointer - meaning that if a port location moves, the central table does not need update unless distances change.

What about city growth?
Well, if a city expands, then the ports move - but only a few tiles outwards (usually). So a minor recalculation would be in order, probably by deducting the change from routes through that port. A full route recalculation would only be needed if the new city boundary subsumed a divergence of routes.  Interestingly, (and this is quite helpful i think) that would not affect the total distance from city to city, as the distance deducted from the direct link is added to the intra-city link, so the routing table stays constant, still pointing to the port, and the port data is updated to note the new location and distances. Some computation is needed, but not much I think. Occasionally, there will be a total distance change of over 1 tile and that should trigger a 'route changed' mechanism but this won't be often.

How about the rapid change of intra-city routes?
This method is probably best initially implemented by calculating a rough distance from city hall  to each boundary port, as a Manhattan distance (thinking about it that seems most likely to be accurate given city roads). There is no need to calculate exact intra-city routes.
Later, the same method could be used to calculate distance from origin to the relevant boundary port. More time, but still quick enough.
For accuracy, perhaps the best method is for a citycar to report the distance travelled from origin to port when it goes that way, and find some algorithm to aggregate such data by city area? Not sure how to handle the really detailed solution per vehicle - but if you chose to do this calculation exactly, at least it would only be from origin to boundary port and a repeat at the destination city. To be honest, for decision making, I do not think it ever necessary to go to that level of detail; it seems just too much.

How to calculate congestion?
Can you record the number of vehicles (city or player) passing over a tile per month? That gives traffic rate data, and is an extra task only when entering a tile so not every step. For the true congestion , recording the 'stopped time' for a vehicle and adding this to a counter on tile exit seems a limited-overhead solution, although both of these could be an awful lot of extra data to store.
If a city has lots of congested or busy tiles, then it would be 'felt' congested/busy by the passengers and they can be expected to use private cars less. 

What about the added complexity?

This is intended to simplify the routing method. Initially, the system can build the city connection tree iteratively.
let's see, the build method might be :
For each boundary port, identify the directly connected cities & other destinations (call them all 'cities' for now). Record the port to use, distance and/or time.
Do this for all cities.
For each connected city, identify the other connected cities reachable via that one. Add to the table and include cross-city links at that stage.
Ignore cities already linked unless the distance is less.
Repeat until destination tree limits reached, i.e. no new destinations found.
Sort the table by destination city and order results by distance/time to that city.

This should be easier than the brute force method used now. It is also more easily and quickly updated.
When a route changes, update only the affected city ports and resort the routing table if the sort order becomes wrong. Cascade the changes upstream if the table changes order, until the table ceases to change in a city.
Do all these updates in non-time-critical routines; it does not matter if routing tables are only updated a little behind reality.
Compared to calculating every route directly, this has to be less computational effort.

Hope this helps clarify a possible approach (I bet you will find some other issues when building the algorithm in more detail, let's hope they are not prohibitive).
I recognise that the algorithm implies a number of data structures that could use significant memory, but look-up tables that might be the price to pay for lower per-route computation.

Merry
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: prissi on April 04, 2012, 02:59:03 PM
Each way already counts the number of vehicles passed this months, and the total number of the previous month. That is there already.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: kierongreen on April 04, 2012, 03:25:15 PM
Traffic passing per month is not quite the same as congestion level (two roads with differing speed limits may have the same number of buses passing per month, with the faster one being free flowing, the slower having a traffic jam).
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: inkelyad on April 04, 2012, 04:09:24 PM
Quote from: kierongreen on April 04, 2012, 03:25:15 PM
Traffic passing per month is not quite the same as congestion level (two roads with differing speed limits may have the same number of buses passing per month, with the faster one being free flowing, the slower having a traffic jam).
speed limit <-> maximum throughput (in vehicles per month). It is not straightforward, but should be easy.
congestion level = Traffic per month/maximum throughput.

And I more and more want to hit the books. Something like "Network Flows: Theory, Algorithms, and Applications" (well, Russian equivalent of it).
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: merry on April 04, 2012, 04:59:14 PM
Aha! not true.
One vehicle per month can be extreme congestion on a 100kph road, if it hasn't moved.
Congestion is surely how long the vehicle spends in the tile, vs the expected time. Ratio of 1=free-flowing.

Hmm. I have been thinking about another aspect of this issue. I wonder by how much the exact link distance varies from the manhattan distance between city boundary ports. or between city halls. Given the road-cuilder may try to build shortest route, wil it not often end up quite close to manhattan? (OK, there are sometimes diagonal roads, but usually built by players).
So a good approximatoin to inter-city link distance, where a direct route exists, may indeed be the manhattan distance. It's a starting measurement at the very least, if we want to work out travel decisions quickly (and it might then be computatoinally cheaper to just calcualte the distance every time rahter than have the complexity of lookup tables). I know this goes against the grain for Experimental (James & others do like accuracy, quite rightly most of the time), but I do wonder how much is to be gained by extreme precision in this particular decision?

Merry.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: isidoro on April 04, 2012, 07:07:12 PM
I don't think that the important final issue is the measure of an abstract congestion, but real average speed on a tile: a quite congested highway may be better than a solitary dirt road...

Maybe if you account for time spent in that tile of all vehicles in a month and does: n_vehicles/time_spent you could have a good measure of the above, but now I realize that some vehicles simply don't go at top speed allowed by the road because their top speed is lower: for instance, an ****-driven cart.

For practical purposes, manhattan distance would suffice, imho.  Specially if you are interested in travel time.  It depends much more on congestion.

Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: sdog on April 04, 2012, 08:57:13 PM
i think the reason james uses some route finding, is to check also the road type. the permitted speed varies greatly in different paks.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: merry on April 04, 2012, 10:16:47 PM
Isidoro & sdog. I suspect you are both right.
The speed limit and congestion (or mean travel time) being per-tile is a serious point: the routine has to iterate over all tiles on the route to find an overall value, even for the speed limit (and hence ideal journey time). Would there be a need to (somehow) log the speed limit changes vs distance on a particular route to make a calculation valid for a particular speed limit vehicle? If so, could the most complex necessary method be a serial representation of distance and speed limit sections as a serial string of values that can be stepped through, in the style of d10s50d30s90 where d=distance, s=speed (but something simpler might suffice)?

The above is only true out-of-city - all city roads are whatever the pak specifies unless non-standard roads have been built. We might safely ignore the latter for calculations of time/distance from origin to boundary! 
City transit data for boundary-boundary route segments might benefit from real routes being found, as those could be stored in a lookup with benefit (fewer combinations to consider).

Let's hope this is all leading to a workable (and codeable) solution.
Merry
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on April 04, 2012, 11:47:26 PM
Thank you all for your prolific input - this is most welcome! I don't have time to reply fully, but one or two additional points of consideration/questions for Merry. Firstly, what of the situation where the "ports" as you describe them change through players building extra roads, or deleting roads, or doing some combination of both near city boundaries? Exactly what would trigger a recalculation of ports, and exactly how (in abstract algorithmic terms) would a city check for ports?

Secondly, how would a system like this evolve to be able to have the in-game representations of citycars actually following a route from their origin to their destination?

Thirdly (this, I think, has been touched on by others), how would the principle of using Manhattan distances in cities accommodate the possible differing levels of congestion in cities (and on different roads in cities) and the different speed limits of different roads in cities?
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: sdog on April 05, 2012, 12:19:08 AM
QuoteSecondly, how would a system like this evolve to be able to have the in-game representations of citycars actually following a route from their origin to their destination?
the best way? by not having vehicle follow it, but generate random city cars based on the trafic density at that spot.
Normalize the city population to the largest city. For every connection you get add the sum of the normalized city populations of both ends of the journey. That way you get the distribution of vehicles on the different ways. (This also provides you with a congestion index, if you want so) From the distribution of trafic, you can get traffic densities you can base the number of private cars represented on. This is however, i think, still way too much for something very cosmetic. Actually routing private cars would be a complete waste of resources.

In general i think, a much much simplified model for this whole problem has to be found. Most approaches are quite overkill. Most likely for any "well behaved" scenario a global statistical approach would provide the same result for reduced ridership.*


What you can do there, is to just test this. Use the routines very heavy on computing on a model system and compare the car rider preference to the public transport use.


(You remember the discussion on complex systems we had a while ago on google or facebook? This is one of those examples, where one would try to get the simple mechanism describing the overall effect of a system which is microscopically highly complex.)



*This gets even more problematic, as we don't have any idea if the basic assumption, that a part of the car owners prefer to take the train when it is faster than their car journey is even viable. (i have some doubts there) But we had this discussion already a year or two ago, i think.





A different approach, in line with what i said before. The idea is to get a global factor for ridership reduction based on car ownership or for a more refined approach a time the public transport has to compete with.


Pick randomly,  weighted with relative city size, two cities.
Calculate the distance.
Put it into distance classes, from your pax destination generation.
Run routefinder and get the time it would take.
provide the avg speed for the class.
do this a few dozen times and average the speed for each distance class.


Compare avg speed of a line with the car owner average speed. If that is too small, recalculate.




This might be even more realistic than the more refined method. If i should consider to go from Munich to Hamburg by car, i'd divide 1000 km by 130 km/h and get 7.7 hours. The former is the distance i assume and the latter my expected value for the speed.
I am not a fully informed market participant. If i was more careful i'd go to google maps, this tells me it is actually 780 km and takes 7.3 hours.


(fyi the train takes 5.6 hours, does anyone have ridership numbers?)
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on April 05, 2012, 12:32:22 AM
Sdog,

again, quickly for the moment, a normalised model will not work, as we need absolute numbers to generate realistic traffic congestion levels: the number of private cars for any given level of usage should have a realistic and determinate relationship to the number of 'buses required. Further, following routes is important because only that model will generate the right amount of traffic congestion (measured in terms of stationary vehicles) in the right places: if vehicles do not go to the right places, they will not block up the right roads. The public player's task in designing a good road network must be meaningful: the idea is for this to be as much a part of the game and transport design as the private players' 'bus or train networks. This is why I don't agree with the idea of radical simplification of this: certainly, we don't need a model that is any more simple than Sim City 4, for example.

As to the *ed point, there is no general assumption that private car owners take the train when it is faster: the decision as to whether to use a private car or public transport is a multi-faceted decision, of which only one element is the relative journey times of both modes. This is realistic.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: sdog on April 05, 2012, 12:57:45 AM
Quoteagain, quickly for the moment, a normalised model will not work, as we need absolute numbers to generate realistic traffic congestion levels: the number of private cars for any given level of usage should have a realistic and determinate relationship to the number of 'buses required. [...]
James, that is exactly what the system i described provides. It does not matter for this if the car went all the way or was generated around the corner. Only important for this is that there are eg. 20 cars per minute on the road between Shrewsbury and Telford.

Same holds for the congestion caused. If you spawn vehicles for each section of road with the same rate as the utilization would be if they would go straigth, you get exactly the same number of vehicles on the road as if they would drive the whole way. It would matter if there was only one car, as soon as we have plenty of cars, they become indistinguished objects.

QuoteAs to the *ed point, there is no general assumption that private car owners take the train when it is faster: the decision as to whether to use a private car or public transport is a multi-faceted decision, of which only one element is the relative journey times of both modes. This is realistic.
I know you are not doing the comparison right away. But we are doing this whole thing in a rather arbitrary way, this is absolutely ok ... But having a very simple and rough theoretical model on one side, and having massive effort to calculate something for it in a second step is usually not a very good practice in simulation.

ps.: i've added quite a bit to my previous post.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: ӔO on April 05, 2012, 01:27:33 AM
Sorry if I missed it, but wouldn't it be simpler to calculate average speed over roads if there is a table of values that the calculator can refer to?

There is only so much a road that is X wide with Y speed will be able to throughput before its top speed comes to a crawl due to congestion. Faster roads will have more capacity and slower roads will have less, so it shouldn't be too hard to come up with a chart that the route calculator can use to tally up total times between two points, instead of calculating from scratch.

With my GPS, it gives three options. Shortest, fastest and economical(?). Obviously, we're only concerned with the first two. I should say, most people don't take the fastest route and instead just take the most direct that uses major roads.

I live on such a street and there may be something like 1 person who takes a bypass through residential street for every 15~20 that will just stay there, stuck in traffic. However, on some major highways with major roads running parallel, or another major highway running parallel, it's around 50:50 with a preference to highway.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: ӔO on April 12, 2012, 05:01:53 AM
what I'm finding, is that when the game is freshly loaded, it is quite responsive. It only eats around 60~80% of 1.86Ghz and only around 600MB of memory.

It then slowly becomes sluggish and unresponsive, as it starts to eat up more memory and more CPU power. At the end of the first month, it's not too bad, but at the end of the second month, it's quite bad. It seems to max out at around 660MB
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: Carl on April 12, 2012, 06:44:02 AM
That kind of change in memory usage is probably to be expected as point-to-point journey time hashtables (etc) are populated. But it shouldn't make for a difference between responsive and unresponsive, which is strange...
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on May 04, 2012, 12:51:26 AM
Having left this topic for a while, a few thoughts on the way forward.

Firstly, the problem is sufficiently complicated that it cannot be dealt with by the next major release. For the time being, server games or other large maps will have to have assume_everywhere_connected_by_road=1.

Secondly, any solution to this issue needs to take into account the eventual plan to have city cars actually driving along defined routes, and congestion being calculated by the proportion of a month that vehicles are stationary on any given road tile. That would enable per-tile congestion measuring, which would enable a more sophisticated means of measuring congestion in cities. It would also mean that the actual time that it takes to drive a particular route could be measured rather than guessed at, and that that measurement would take full account of congestion. The idea would be that all journeys originating in City A starting from a radius of X tiles around point Y and ending in city B use one and the same route (to a specific point in city B) for journey time per tile calculation and citycar routing purposes, but calculate their actual journey time using the existing system of journey time per straight line tile from the actual exact origin point to the actual exact end point.

Thirdly, this leads to a consideration of how to achieve this. There have been a large number of suggestions. I am currently leaning towards using Dijkstra's algorithm to find all routes from a given point in each city to a randomly selected point in each reachable destination city simultaneously, combined possibly with concurrent multithreading. This would take more computational effort than finding only a single route between cities (from a single point in each city to a single point in each city, rather than from multiple points in each city to a single point in each city), but that increase will be linear and, if the radius of the origin points is wide enough, then the increase will be relatively modest (perhaps on average 4 or 5 times the number of routes that need to be calculated for having a single route for each city pair).

However, for that, a number of things need to be considered, preferably before implementation. Firstly, just how computationally intensive will 5 or 6 one point to many Dijkstra's algorithm searches be compared to the existing city to city A* set of searches? I know that the use of a one to many Dijkstra's algorithm search will scale in its computational intensity linearly rather than exponentially with the number of cities, but does anyone have any idea whether even this will be manageable (especially with multiple origin points per city, and therefore multiple searches per city) for, say, 675 cities?

Further, there is the issue of network synchronisation. For concurrent multi-threading to work in network mode, as indicated above, the only workable solution is to have the server do all the work, and push the results to the clients in the same way that player interactions are pushed from server to client. However, this gives rise to the issue of whether this will be too bandwidth intensive. For the full private car routing, using multiple start points in a city and having private cars driving along defined routes to their destinations, the whole route would have to be transmitted from the server to the clients. This would be 32 bytes (2 x 16 for a koord object) per route tile, plus some overhead (including an 8 byte control character for the command, 32 bytes for each start and end tile, and, say, 192 bytes for general information about the number of vehicles using the route, when it was created, and, the journey time per tile and so forth, plus probably another 16 bytes worth of general overhead for each command. For a 256 tile route, this would be something in the order of 8,456 bytes per route. If each city, on average, generated 6 routes to each other city, a refresh for each city would amount to 50,736 bytes per destination city, or 34,246,800 bytes (32MiB) per full city refresh. Multiplied for all 675 cities, this would amount to 22,045MiB or 21.5GiB, which seems to be an awful lot, even spread over time. Do these calculations appear correct on the face of them? If so, is there any way, does anyone think, to mitigate this large amount of data? Or alternatively, will a single threaded Dijkstra's search suffice for performance? That will, I suppose, depend on just how much of a saving a one to many search is over many one to one searches.

Incidentally, running the calculations again for a Dijekstra's algorithm version of the current model, that is, without an actual route being transmitted (resulting in routes with an overhead of only about 264 bytes), the numbers are as follows: 1,584 bytes per destination city, 1,069,200 (approx 1MiB) bytes per refresh of a single city, or 721,710,000 bytes (approx. 688MiB) for a refresh of all cities. Even with the simpler system, therefore, this is far from ideal - a CD's worth of data would need to be sent for each time that every city on the map was refreshed (if my calculations are correct).

On reflection, perhaps this will only be practicable if the performance can work well single-threaded (or if there is some way of achieving parallel, rather than concurrent, multi-threading in the route-finding algorithm that achieves a substantial saving, but I am doubtful of that).

Any thoughts on this topic (both in relation to multi-threading and generally) would be most welcome.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: chicken on May 04, 2012, 01:49:25 AM
Surely a route could be encoded in a much smaller space. How about an initial koord, and then a sequence of bits, representing each step? 32 bytes + 2 bits * 256 + 16 bytes = 112 bytes.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on May 04, 2012, 09:44:39 AM
I'm not sure that I understand - how would that sequence of bits represent a tile in two dimensional space?
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: Combuijs on May 04, 2012, 10:41:59 AM
You start with a tile with full coordinates (might be 32 bytes?). Then you need 4 values (2 bits) that tell which tile is the next one: left, right, up or down, for each tile in your route (256*2) for a route that is 256 tiles long. Don't know what these 16 bytes are doing there at the end.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on May 04, 2012, 11:46:07 AM
Ahh, I see. However, given that even without any route information, refreshing a map's worth of cities will still require the transfer of a CD's worth of data to each client, this may not be a realistic solution in any case (if my calculations are correct).
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on May 04, 2012, 10:34:04 PM
I think that I have devised a way to multi-thread this without the server having to do all the work and push the results to the clients, by using a parallel multi-threading algorithm rather than a concurrent algorithm (although some consideraiton of the implementation details is still necessary, any thoughts on which would be much appreciated).

The basic idea would be for each city to begin a refresh of all of its routes in a separate thread, but keep the results (including interim results as all the various routes are found) in a separate set of hash-tables (or some sort of collection object) not actually used by the game. Only when all the routes for that city has been calculated on all clients do all clients simultaneously replace the live data with the fresh data in waiting generated by the latest refresh.

The tricky part would be how and where to check whether all clients have in fact completed the refresh. Perhaps something could be put in stadt_t::step() (and perhaps a mechanism to cause it to check only every 256 steps to reduce network overhead) to perform the checks. In a non-network game, the game would simply check whether the local route checking thread(s) had finished, which would be indicated by those threads having set some or other variable. (What might work is one thread from each origin point in the city, the number of threads being recorded, and each thread incrementing a counter when it has finished, which could be compared with a counter keeping track of the number of threads started). In a network game, each worker thread on the client would have to send a message to the server when it had finished, and the server would keep a record of all client threads and check to see whether all threads from all clients in a given city have completed, and, if so, send a command to the clients to swap the live data with the provisional data. The clients, in turn, would only swap the data in network mode when a command is received from the server, rather than checking for local threads having finished.

One complexity is how to handle the situation in which a client leaves or joins between a city refresh starting and all threads completing. A simple counter would be difficult, as it would not determine whether an exiting client was one that had or had not finished the refresh. It would not be possible to rely on the quitting client to tell the server whether it was one that had completed a refresh of any given city or not (so affecting whether the server subtracts 1 from the count of completed clients or not), as the client might disconnect due to a network error, local power outage, etc., and suddenly stop sending the server information at all. Any thoughts on how to deal with disconnecting clients would be appreciated.

As to joining clients, one option is for them to download the completed interim information from the server if the server itself has completed the refresh that is in progress on other clients (in which case, all the clients might as well download that data, too), but even this might be quite a download overhead. Alternatively, connecting clients could be told to start a refresh on those cities straight away, but in the meantime use the current live data, which is probably the best way of proceeding. I should be interested in whether anyone has any better ideas on this question, however.

Overall, this is quite a complicated if possibly powerful solution to the problem, and is a lower priority than economic balance, so might not be implemented for a while unless somebody would like to have a go at it. However, I think that it is very helpful to have these things planned. In the meantime, I should be very interested in any thoughts on this particular implementation, especially as to whether there might be a more efficient way of doing things, or whether there are likely to be problems which I have not foreseen in the above outline.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: kierongreen on May 05, 2012, 08:43:49 AM
A few points:
How will you deal with stale routes?
You might need checks and/or thread locking to ensure that grounds are not deleted by one thread while another is calculating a route across it.
If you have one thread continuously updating routes this means that simutrans will use significantly more CPU time - which may mean that on laptops for example battery life is adversely affected.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on May 05, 2012, 11:23:00 AM
Kieron,

thank you for your thoughts. To respond individually:

(1) stale routes will be marked as such, but will continue in use until the threads for replacing them (or, in a network game, all clients' threads for replacing them) have finished;
(2) I shall have to give this one further thought - thank you for pointing it out (do you or anyone have any suggestions?);
(3) this feature will inevitably be computationally expensive, although, if it works the goal will be most worthwhile - however, it will be able to be disabled by the always_assume_everywhere_connected_by_road=1 setting, as at present.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on December 10, 2012, 10:34:50 AM
I have not had the chance to work on this rather complicated issue since it was last discussed back in May of this year. However, I have recently come up with an idea which would allow a much quicker and simpler solution to be applied to network games, relying on multithreading. To recap, the problem with multithreading has been that, in online games, there is no reliable way to keep a multithreaded game synchronous if the threads are run in parallel on the client and on the server, and, if the background threads are run on the server alone, pushing data to the clients as they go, those data will quickly saturate the whole bandwidth.

The solution, I think, is a modified version of the second model - the threads to create the private car routes running only on the server. However, instead of pushing the data to clients as it goes, the server would store the updated data in unused shadow vectors until the game is next loaded/saved (for example, when a client joins). Then, the server would swap in the shadow data to the main running data immediately before saving, so that, on loading, those updated data are available to the clients and active on the server. The bandwidth would be used far more efficiently, as the data would be compressed, and only sent at intervals. Although this would result in some delay between a change to the road network and its recognition by the game for private car routes, this delay would not be great in proportion to the slow pace of game time, and, with the frequency of players joining/leaving, would not cause noticeable problems. Indeed, there is something to be said for autosaving every hour or two in any event by means of a command line shell script to prevent any server crashes from losing too much players' work.

On a single player game, multithreading could update the data immediately without delay.

The implementation of this would have to wait until the merge with 112.x has been finalised, as that is the version with the multithreading code, but I should be most interested in any views on this subject in advance of attempting to to implement. Also, does anyone know whether it is possible to set thread priorities using pthread? It would be useful to set the priority of the thread that finds private car routes lower than the priority of other threads on the system.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: prissi on December 10, 2012, 12:36:18 PM
But currently only one map is sent to the clients. You would need to transfer the map then to all clients connected. You would also need two independent random counter.

Additionally server usually have much weaker CPU than clients as CPUs are shared. Even if you have a single CPU, it could mean that this is rather a single core out of 16, and hence features like turbo boost and similar are disabled. If you can do a hard reset of your server, then the chances are high this is really and independent dedicated server. But those come still with a 100 EUR/$/GBP tag per month.

The display is anyway threaded and is not the largeast CPU consumer for developed games is standard and likely also exp.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on December 10, 2012, 07:37:19 PM
Quote from: prissi on December 10, 2012, 12:36:18 PM
But currently only one map is sent to the clients. You would need to transfer the map then to all clients connected. You would also need two independent random counter.

Hmm - I am not sure what you mean about one map being sent to clients. Obviously, only one saved game (including the map, etc.) is sent to each client; what I am proposing here does not need this to change. The idea is that the server would update its active private car routing table from the shadow private car routing table updated by the background thread(s) immediately before saving (indeed, called from each town's rdwr(file) method), and then transmit the whole saved game, including this updated table, to all the clients.

Or do you mean that the presently connected clients do not actually receive data from the server when a save/load is performed? If so, that is an interesting point. I wonder how easy that it would be to serialise and compress just the private car routing tables...?

As for the random counter, I don't think that this is affected, since the calculation of the private car routing tables does not need any random number generation.

QuoteAdditionally server usually have much weaker CPU than clients as CPUs are shared. Even if you have a single CPU, it could mean that this is rather a single core out of 16, and hence features like turbo boost and similar are disabled. If you can do a hard reset of your server, then the chances are high this is really and independent dedicated server. But those come still with a 100 EUR/$/GBP tag per month.

The display is anyway threaded and is not the largeast CPU consumer for developed games is standard and likely also exp.

I am not sure what most Simutrans servers are run on, but the Bridgewater-Brunel (http://www.bridgewater-brunel.me.uk) server currently runs on one of these (http://www.heartinternet.co.uk/vps/). I currently have it set up with one dedicated core, 50Gb of hard drive space and 3Gb of RAM, but I could add a second dedicated core for an extra £6/month.

Incidentally, do you know whether pthread allows one to set the priority of a background thread to a lower priority than the main thread? It would be useful to be able to have the private car route population thread(s) run in a lower priority.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: prissi on December 13, 2012, 01:25:04 PM
When another player joins, the map is only sent to the new player. The other clients just do a local save/load operation. If you have some hidden data on the server, this is no loanger possible, and all clients need to recieve at least this hidden data.

The VPS guaranteed performce is usually something around a pentium 600 or so. Just remember, current server processor have 16 core (when you count hyperthreading) per unit. Often those cores are not even exclusive, studies show that on avarage 40-60 virtual servers are typically joining one core, since most of them do nothing. (The hoster has some clever management to pair highly loaded with less loaded cores.)

But the VPS performance can strongly vary. In any case, it will not exceed an Intel Atom processor very much. At best relayable netbook perfomance.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on December 14, 2012, 01:20:59 AM
Thank you for this. I see the logic behind that way of doing things, but it does mean that my latest idea won't work. Hm - back to the drawing board on that one, I fear. If only Knightly were still working on Experimental...

As to VPS performance, I think that I get a dedicated core on a 16-core rack server. The server seems to cope very well with my very CPU-intensive network game with vast numbers of convoys each with unoptimised physics equations, so a second core could usefully do a lot of work calculating routes in the background. The difficulty would be how to transfer them to the client without clogging bandwidth excessively.
Title: Re: Bug fix uncovers performance issue. Ideas for solution sought
Post by: jamespetts on January 02, 2013, 05:05:37 PM
A somewhat fresh perspective on this set of problems occurs to me, although it provides no easy solution. I was looking at a book on transport economics last night, and was struck by the importance of transport for the pattern of developments, and the very precise relationship between density, urban development, passenger transport and distance between homes and workplaces (for reference, the book is "Applied transport economics" by Stuart Cole). It would be good to be able to model some of this in the town growth algorithm. One way of modelling this is by associating particular residential buildings with particular destination buildings as workplaces. We can calculate whether to build a workplace at a given point by whether there are spare workers living a transportable distance away, and calculate whether to build a home at a given point by whether there are workplaces needing workers a transportable distance away.

Putting aside the details of how we calculate what is within a transportable distance or not, what counts as "spare" jobs/workers and how we generate "spare" ones, modelling things in this way suggests a possible change in the basis of passenger generation from randomly assigning them destinations when the buildings are stepped to having each building with a pre-assigned list of destinations, a workplace, a leisure activity and a miscellaneous (shopping, going to the bank, etc.). Something similar is done in Sim City 4, where each building is assigned one or more destinations and the routes to/from it recalculated only periodically. If we make all trips return trips, we would potentially only need to step residential buildings for passenger generation (mail generation would be different, but would not need private car route calculation; query however, whether this would miss the realistic simulation of commercial to commercial passenger transport and, if so, whether that would be significant).

Using this model, we could in principle bypass the calculation of routes between cities entirely (which, I think, is an unhelpful abstraction in this context) and focus on calculating routes between buildings. Because we do not need a set of journeys for every possible pair of buildings to be calculated regularly, but just, say, two to five journeys from each residential building to its destination and a return journey (the return journey, in the case of private car routes, can simply be a mirror of the outward journey and not recalculated) per recalculation.

In the current Bridgewater-Brunel online game, I have estimated the current number of buildings overall as something in the region of 107,000 (by taking the population of one city, dividing it by the number of buildings, to get a figure close to 21.8, and then dividing the region population by that number). This game is still in the 1860s, so I should expect a greater number of buildings by the time that the game reaches the modern era. If we assume that we need to be working with a set of 250,000 buildings, we should have a solid basis for the calculation. Of those, perhaps half are residential buildings (they seem to number more than commercial or industrial buildings), giving a total of 125,000 buildings from which routes need to be calculated every calculation cycle. If we work on the basis that private car ownership, like destination, is pre-assigned per building, only circa 80% of those will, in the modern era, require private car route calculation, or something in the region of 100,000. This compares with a figure of in excess of 225,000 sets of private car route calculations required for the existing method on the previous Bridgewater-Brunel saved game. (The two are not exact comparisons by any means, as the latter had reached the 1970s at the time of writing the original post and had more cities, but it is significant that towns in later eras will increase their population in substantial part by increasing the level as well as the number of buildings, so the number of buildings increases less than the population as the game progresses, and the number of cities was far short of an order of magnitude different).

So, the fixed destination per building system has the potential to yield some significant reduction in the calculation overhead required whilst at the same time making the routes far more accurate and able to be followed by actual city car graphics, allowing per tile computation of congestion. Also, this method means that the increase in the number or size of cities will only increase the amount of private car route computation in a linear fashion rather than the exponential increase of the present all city pairs system.

However, this reduction is not by itself enough. 100,000 routes will still take an average of 5,000 seconds (100,000 x 50ms), or 83 1/3 minutes for a whole set recalculation, compared with 189 minutes for a full set recalculation with the number of pairs quoted in the original post (being 227,812). Using figures comparable with those given in the first post, if we assume an annual recalculation cycle, this equates to a computational time requirement of just under 7 minutes per game month, compared with around 15 for the original set - and this assumes a fast computer such as my i7. Furthermore, this is assuming only one route per building: if we want to have multiple routes (one to work, one for leisure, one for miscellaneous, for example), this will treble to 300,000 routes or 21 or so minutes - worse than the original example.

The task can be parallelised quite easily, as it happens, as the calculation of one private car route does not affect the calculation of any other private car route. So, every x number of steps (or perhaps every x number of ticks), the route recalculator could be called. It would calculate a pre-determined number of private car routes marked to be stale, then stop. During recalculation, it would set a number of threads running (perhaps 4 or so), each of which would calculate x number of routes each. The main thread would also be calculating routes during this time. Only when all running threads have finished would the main route recalculator method (itself running in the main thread) complete, allowing other parts of the program to execute. This would have the effect of preventing the recalculation mechanism from having an adverse performance impact on the game: taking an unacceptably long time would just make the private car routes all out of date rather than making the game unresponsive. However, the possibility of having out of date private car routes does not sit well with the system of having growth based on whether a site for a building can be found that is within reach of a workplace: indeed, I cannot see how that latter system can be made to work without always being able to have up to date private car routes (which would have to be calculated theoretically from an undeveloped tile before any development takes place, further increasing the number needing to be computed).

How often, then, in game time would routes end up being recalculated if we worked in this way? With 21 bits per month, about two game years tend to pass for every one real time day. 300,000 x 50ms = 4.17 hours: for every complete recalculation cycle, therefore, four hours and ten minutes would have to be spent by the server (and all clients connected at the relevant time), spread out over the whole day, or about 35% of the total computational time spent by the server if the routes were to be refreshed once per game year. Switching to 22 bits per month would reduce this to 17%, and having a second core in the server would reduce this further to 9%, but even this amount still seems somewhat excessive.

More efficient code is still necessary, therefore. This is where it gets tricky, as more efficient in this particular context means much more complicated. If we are storing routes in any event, we might as well add a reference back from a road tile to the route(s) that pass over it. This will add a vector of pointers per road tile worth of memory. This would make it possible to check at any given tile on an A* search whether there is already a route to the destination from that tile, preventing duplicating routes. However, I do not know how well that this works with A*, as, from what I understand, the algorithm can iterate over tiles on a sub-optimal route before finding the optimal route.

In any event, if the destination is a specific building, this will not save much in terms of execution time, as the chances of hitting another route for a specific building are quite slim. However, it is quite possible that the path finder would hit a route for a neighbouring building early in its search. The trouble is that it would be very difficult to find a reliable algorithm that could make use of this fact. What should count as "neighbouring"? How do we know whether the neighbouring building is anywhere near, in transport terms, our destination building (they may be opposite sides of a river, for instance)?

I cannot think in principle of any other type of optimisation over and above A* that will work for a building to building based search than, as mentioned above, a system that checks each tile over which it iterates for already calculated route(s) to the destination. (This also throws up the possibility that calculating some routes would be much shorter, whereas calculating others would take no less time, which would potentially reduce the possible gains by parallel multi-threading, as at least one of the threads could be stuck with a set of unoptimisable routes; this could only partially be solved by giving all threads more routes to find per parallel run). A Floyd-Warshall or other network explorer centralised all points to all points system would not, in my limited understanding, assist, since we need to calculate the paths between a far reduced set of nodes (unless running Floyd-Warshall (etc.) for the entire set of buildings for road connexions, giving a total of 11,449,000,000 (eleven point four American billion) total connexion pairs, is faster than running A* for a set of 300,000 connexions).

Can anyone suggest anything that may assist here? I am very keen to be able one day to have realistic traffic and development simulation in Simutrans, and I should like to know whether it can be achieved before we all have desktop computers powerful enough to run A* between hundreds of thousands of points within a reasonable time on a Simutrans map or whether it can be achieved through more efficient coding sooner rather than later. Any thoughts on (1) how much that a search for existing routes on each tile would help; (2) whether any other optimisations of which I have not thought might assist (and, if so, by how much); (3) whether the memory usage for storing around 300,000 private car routes would be excessive in any event; and any other connected matter that might be of assistance would very much be appreciated.

Edit: I have come up with a possible optimisation simple enough for even me to code, although I do not know whether it would provide enough of a saving when taking into account its own overhead.

For each route needing to be calculated, each tile would be checked to see whether it also contains a route to the destination building. If so, the routes (the current incomplete route to the tile with a route to the destination, and that part of the route from that tile to the destination) would be concatenated (by copying tiles, rather than by pointing from one to another). This would require storing on each tile not only a pointer to the route, but an integer representing which tile number in the route that that particular tile is, allowing for easy concatenation.

If there is no route to the destination building, check to see whether there is a route to the city in which the destination building is located if the straight line distance between the current tile and the town hall of the city in which the destination building is located is more than X times (perhaps 2) the distance from the town hall in which the destination building is located and the destination building. If these conditions are fulfilled and there is a route to the city in which the destination building is located, copy-concatenate the found route, iterating over each tile to check whether (1) that tile contains a route to the destination building; or (2) that tile is within the destination city. If it has a route to the destination building, stop copy-concatenating the first route, and apply the same procedure from there as in any other case where a route to the destination building is found. In the second case, if a tile within the city containing the destination building is reached, calculate a route from there to the destination building, again checking on each tile to see whether a route to the destination building can be found on that tile and copy-concatenating if so.

This would work in principle, I think, but what I don't know, and have no way of taking a sensible guess about, is whether the optimisation would suffice. Would all that checking for routes on each tile (iterating over all the routes on that tile in the process) take more CPU power than saved?  Would the whole thing take too much memory?

I should be extremely keen to hear from anyone with more programming experience than I as to whether this method would work to produce the optimisations sufficient to make the building to building private car route finding model described above workable.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jayem on January 02, 2013, 11:02:46 PM
Would it be possible to statistically hide the journeys for the lots of car journeys.  It would mean there might be some odd effects on a single journey but you should get congestion at the right places, and behaviour that looks right over several tiles.

You could model Factories/Shops and Attractions as absorbing cars (valleys of car potential), and Houses as (hills) emitting them to neighbouring roads.
In each cycle the 'car potential' of a road tile would be something between the previous-average of the surrounding tiles and it's previous value
   (slight care needed as cars don't get destroyed mid journey but road type should have some effect).

A graphical car would then move 'down hill' making a random choice based proportional to the gradients (and hence always getting nearer a destination).
An anti car (representing a return journey) would move uphill.
If a hill gets too high you need to build another factory, (or lose a house), if a valley gets too low you need to build another house (or lose a factory)

That would be O(N) time-wise and data-wise which would be good.  Although the constant factors might well be higher to spoil that.

I think it ought to behave moderately sensibly over simple complexes, although Factory-Town-Town-Factory would lead to little traffic between the towns.  You could possibly sort that by having houses and factories emmiting into random piles, so there's a chance one town has a surfeit of Traveller-A's and a deficit of Traveller-B's.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 02, 2013, 11:19:53 PM
Hmm, this would model congestion in a very similar way to the original Sim City (now open sourced as Micropolis). This is fine for a congestion modelling algorithm, and also suffices to check whether residential areas are connected to somewhere useful, but in Simutrans, we need to check whether people can get to the specific places that they want to go, rather than just anywhere. The private car routing system has to fulfil the function of determining "can the people from building A get to building B within their journey time tolerance by private car?", as well as the function, "how much congestion is there on road tile X?", and have a realistic set of feedback mechanisms/relationships between the two.

Bear in mind also that the passenger generation algorithm in Simutrans-Experimental needs to be able to run a check to see whether passengers can get to the specific place that they want to go by private car within their tolerance. Currently, on larger games, one has to enable the "assume_everywhere_connected_by_road" setting to have adequate performance, which will just check whether the particular packet of passengers has access to a private car and make assumptions about the journey time based on the speed of the private cars currently available in the game and the speed limit of the current default inter-city road (or intra-city road if the journey is entirely within a town). To be a step forward, a private car routing algorithm would have to give an accurate network based answer to the question, "can packet of passengers X get to its destination within its journey time tolerance?" rather than make assumptions. What is really desired is a system that will model private car transport in as much detail as transport by other means.

What I am most interested in at present is some idea of whether the model that I proposed in the thread above has a chance of doing this within reasonable parameters of performance. If you or anyone else has any ideas about that question, I should be most interested indeed.

Thank you very much for your input, though: it is most appreciated.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 03, 2013, 04:47:01 AM
Quote from: jayem on January 02, 2013, 11:02:46 PM
You could model Factories/Shops and Attractions as absorbing cars (valleys of car potential), and Houses as (hills) emitting them to neighbouring roads.
In other words:
Each attraction/factory is 'heat source', houses are (small) heat sink. Now we can use numerical heat transfer model. Such models are build for multiple processors.

Quote from: jamespetts on January 02, 2013, 11:19:53 PM
This is fine for a congestion modelling algorithm, and also suffices to check whether residential areas are connected to somewhere useful, but in Simutrans, we need to check whether people can get to the specific places that they want to go, rather than just anywhere.

Quote from: jamespetts on January 02, 2013, 11:19:53 PM
To be a step forward, a private car routing algorithm would have to give an accurate network based answer to the question, "can packet of passengers X get to its destination within its journey time tolerance?" rather than make assumptions.
It is quite possible. You need to model separate 'heat plate' for each attraction/factory.
As time go catchment area for factory will grow => more calculations.
But number of factores/attractions should go down too (factories tends to be bigger over time).
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 03, 2013, 10:49:14 AM
Quote from: inkelyad on January 03, 2013, 04:47:01 AM
It is quite possible. You need to model separate 'heat plate' for each attraction/factory.
As time go catchment area for factory will grow => more calculations.
But number of factores/attractions should go down too (factories tends to be bigger over time).

I am not sure that I fully understand. How would this integrate with the current passenger generation system which generates specific packets of passengers at specific buildings wanting to go to other specific buildings (often in other towns) and needing to know whether they can find a route there either by private car or player transport, and, if by both, which is preferable? We need to be able to simulate the exact same journeys that passengers make by player transport being made by private car if the passengers make the private car modal choice.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 03, 2013, 01:43:56 PM
Quote from: jamespetts on January 03, 2013, 10:49:14 AM
I am not sure that I fully understand. How would this integrate with the current passenger generation system which generates specific packets of passengers at specific buildings wanting to go to other specific buildings (often in other towns) and needing to know whether they can find a route there either by private car or player transport
Each cell has value 'how many(in month) passengers have reached to here from heat source(factory) by private car'. If it zero -> there is no path via private car or said path is too long.

It is same as 'can the people from building A get to building B within their journey time tolerance by private car?', where building B is factory.
Quote
, and, if by both, which is preferable? We need to be able to simulate the exact same journeys that passengers make by player transport being made by private car if the passengers make the private car modal choice.
Uhh... sorry, I was thinking about another decision function. Not 'which transport is faster?', but 'which transport give me better probability to reach destination in time?' It is not same.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 03, 2013, 02:28:07 PM
Quote from: inkelyad on January 03, 2013, 01:43:56 PM
Uhh... sorry, I was thinking about another decision function. Not 'which transport is faster?', but 'which transport give me better probability to reach destination in time?' It is not same.

Ahh, no, we need the former if the system is to integrate, as it must, into the passengers' decision making process about whether to take the car or player transport.

Do you have any thoughts on whether my posited optimisation of route-finding might work within acceptable limits of performance?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 03, 2013, 06:38:27 PM
Quote from: jamespetts on January 03, 2013, 02:28:07 PM
Do you have any thoughts on whether my posited optimisation of route-finding might work within acceptable limits of performance?
It might. But copy-paste of inter-city routes seems excessive and really memory-hungry. Just pre-calculate distance beetwen cities and use it in A* heuristic.

And it seems you are trying re-invent something like this: http://davis.wpi.edu/dsrg/Old/UMICH/t-gis2000.pdf (City == cluster inside network graph).
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 03, 2013, 06:49:54 PM
That paper looks interesting, having read the abstract. Is there any way of knowing (without incurring the incalculably vast amount of time required actually to code both versions from the ground up), or at least, making a sensibly educated guess as to, how pre-calculating the distance between cities per se will work as an A* heuristic? In all cases when using cities as an abstraction, we have to bear in mind what is in Simutrans (especially in the later game when cities have grown considerably) the not at all uncommon case of an origin point in one city being nearer the destination point in another city than either is to its own city hall (we must remember that measuring the distance between "cities" involves measuring the distance between a specific point in a city and a like point in another city); is this even an admissible heuristic given the possibility for these conditions? Will improving the heuristic really help in any event when we are still trying to perform hundreds of thousands of A* searches; and how will an improved heuristic help with memory consumption when we in any event have to store all the separate routes in order to run actual private cars along them and track how much that each of them is being used?

As to the paper, have you looked at it in any detail? The abstract mentions a number of different techniques; do you think any of them suitable for what we need for this purpose?

Edit: Hmm - I am not sure that this paper addresses the same problem:

Quote from: The paper
Since the size of the link table is often larger than the capacity of the main memory
bffer of a given GIS system, the link table may need to be stored on a secondary storage device,
typically on disk. While state-of-the-art database engines may attempt to cache the link table into
main memory during path evaluation, this will generally not be feasible due to size constraints.
3
In this case, many tuples links in the link table may need to be retrieved over and over again
from secondary storage and placed into the main memory buffer for evaluation. Given that such
I O operations on most modern computers are typically several 100-fold more expensive than CPU
operations, the I O costs are the dominant factor of path computation costs.

The high processing costs are thus incurred by the recursive nature of the graph traversal
component of path query computation. Resolving embedded constraints may further increase I O
costs significantly. For example, in a related e ort 17, 18, 22, 23, 19, 20 , we found that processing
spatial constraints see Q3 path query is very I O intensive. Thus such constraint resolution
competes with the path finding component of the search process for computational resources such
as the buffer space. This further motivates our research presented in this paper on optimizing the
path computation process by reducing I O activities.

The issue being discussed here is that the complete set of nodes and links for the sort of system discussed in the paper cannot be stored in memory at once, hence requiring frequent disc accesses. It also assumes a model of nodes being intersections and links being the roads between them, which is different to the Simutrans tile based model, in which every road tile is a node, and the connexions to its neighbouring tiles are the links.

In Simutrans-Experimental, the issue is not that each individual query takes a long time (what is described as the "spacial query" at Q3 is not relevant here because the links themselves do not have any special characteristics relative to one another) due to IO access, but that there are vast numbers of queries that have to be processed in a short time. The issue is CPU-intensiveness rather than memory size or bandwidth.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 03, 2013, 07:05:51 PM
Quote from: jamespetts on January 03, 2013, 06:49:54 PM
Is there any way of knowing (without incurring the incalculably vast amount of time required actually to code both versions from the ground up), or at least, making a sensibly educated guess as to, how pre-calculating the distance between cities per se will work as an A* heuristic?
In current implementation each road cell know about its distance to all cities halls?
Quote
not at all uncommon case of an origin point in one city being nearer the destination point in another city than either is to its own city hall
Yes, but 'distance to city hall'  heuristic usually points A* to right direction.
Quote
As to the paper, have you looked at it in any detail? The abstract mentions a number of different techniques; do you think any of them suitable for what we need for this purpose?
It is hard work. Usually I use such kind of papers for 'read referenced literature first'.

Edit:

Quote
The issue being discussed here is that the complete set of nodes and links for the sort of system discussed in the paper cannot be stored in memory at once, hence requiring frequent disc accesses. It also assumes a model of nodes being intersections and links being the roads between them, which is different to the Simutrans tile based model, in which every road tile is a node, and the connexions to its neighbouring tiles are the links.

In Simutrans-Experimental, the issue is not that each individual query takes a long time (what is described as the "spacial query" at Q3 is not relevant here because the links themselves do not have any special characteristics relative to one another) due to IO access, but that there are vast numbers of queries that have to be processed in a short time. The issue is CPU-intensiveness rather than memory size or bandwidth.
Yes, but we  can't store all paths 'cell A' -- 'cell B' into memory and must recalculate it.
So effect is same: path query is long operation.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 03, 2013, 07:35:00 PM
Ahh - do you imagine calculating and storing the distance to each city hall from each road tile? With 500 cities, that would be a very large amount of calculation - are you sure that this would help?

Indeed, perhaps I am missing something, but does a distance to the destination city hall heuristic actually add anything to the distance to the actual destination heuristic? Is it any better? Or is the point that the calculating of the distance to X from each tile is the part that takes most of the computational effort such that pre-calculating this once for every road tile would reduce the work of doing 300,000 A* searches enough to bring it within reasonable performance limits? If that is so, then would my system not do the same?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 03, 2013, 07:54:15 PM
Quote from: jamespetts on January 03, 2013, 07:35:00 PM
Ahh - do you imagine calculating and storing the distance to each city hall from each road tile? With 500 cities, that would be a very large amount of calculation - are you sure that this would help?
I can be wrong, but my memory tell me we already do this.  It is one fill from Dijkstra's algorithm for each city hall.
Quote
Indeed, perhaps I am missing something, but does a distance to the destination city hall heuristic actually add anything to the distance to the actual destination heuristic? Is it any better? Or is the point that the calculating of the distance to X from each tile is the part that takes most of the computational effort such that pre-calculating this once for every road tile would reduce the work of doing 300,000 A* searches enough to bring it within reasonable performance limits?

Pre-calculated distances to halls will lead A*  straight  to destination city ( first to to source city boundary, then to destination city via shortest  path). There will be no backtracking there.
Quote
If that is so, then would my system not do the same?
You need to find and copy stored inter-city path. It almost same as reconstruct it via A* with right heuristic.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 03, 2013, 07:58:57 PM
Quote from: inkelyad on January 03, 2013, 07:54:15 PM
I can be wrong, but my memory tell me we already do this.

I really don't think that this is done in Simutrans - where are these data stored, do you think?

QuoteIt is one fill from Dijkstra's algorithm for each city hall.

Might this not make placing new roads unresponsive on occasions if this has to be done every time that road tiles are laid, for every single tile?

QuotePre-calculated distances to halls will lead A*  straight  to destination city ( first to to source city boundary, then to destination city via shortest  path). There will be no backtracking there.You need to find and copy stored inter-city path. It almost same as reconstruct it via A* with right heuristic.

But, in this case, we have to keep in memory all the road to city hall distances on top of the complete set of routes, whereas, in the system that I proposed, we only need to keep the complete set of routes. Does your system not take more memory than mine...?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 03, 2013, 08:42:41 PM
Quote from: jamespetts on January 03, 2013, 07:58:57 PM
I really don't think that this is done in Simutrans - where are these data stored, do you think?
It just my memory. I remember that I used said distance one time.

Quote
Might this not make placing new roads unresponsive on occasions if this has to be done every time that road tiles are laid, for every single tile?
If we do it for every single tile, yes. But do we really need to?

Quote
But, in this case, we have to keep in memory all the road to city hall distances on top of the complete set of routes, whereas, in the system that I proposed, we only need to keep the complete set of routes. Does your system not take more memory than mine...?
It depends.
'each tile would be checked to see whether it also contains a route to the destination building.'
Each tile will be storing routes. It is not clear what will take more memory.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 03, 2013, 09:09:08 PM
Quote from: inkelyad on January 03, 2013, 08:42:41 PM
If we do it for every single tile, yes. But do we really need to?

What's the alternative?

Quote
It depends.
'each tile would be checked to see whether it also contains a route to the destination building.'
Each tile will be storing routes. It is not clear what will take more memory.

The tiles will store pointers to the routes together with an integer representing which step of the route that they are on - the routes need to be stored in any event. Indeed, it would be helpful for tiles to store pointers to the routes in any event in order to give statistics to users. That is, at worst, 96 bytes per tile on a 64-bit system and 64 bits per tile on a 32 bit system. This compares favourably with having to store pointers to and distances to each of 500 or so cities per road tile.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 03, 2013, 09:23:27 PM
Quote from: jamespetts on January 03, 2013, 09:09:08 PM
What's the alternative?
Recalculate it at next update cycle.

Quote
That is, at worst, 96 bytes per tile on a 64-bit system and 64 bits per tile on a 32 bit system.
I don't understand. Only one route per tile?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 03, 2013, 11:37:32 PM
Quote from: inkelyad on January 03, 2013, 09:23:27 PM
Recalculate it at next update cycle.

Ahh, do you imagine calculating the route table, calculating all the private car routes in one big go, then discarding the route table rather than calculating the private car routes periodically in the background? Wouldn't that need really lightning performance to be acceptable to the user for the number of connexions being calculated? I don't think that any method suggested by anyone so far will optimise it this much.

QuoteI don't understand. Only one route per tile?

Ahh, yes, you are right: I had forgotten that we need to store vectors of routes. Hmm...
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 04, 2013, 06:28:20 AM
Quote from: jamespetts on January 03, 2013, 11:37:32 PM
Ahh, do you imagine calculating the route table, calculating all the private car routes in one big go, then discarding the route table rather than calculating the private car routes periodically in the background?
Err..
1) Spread 'distance to hall' and private route calculations over month.
2) Don't take action on changes in road network. Use out-of date distance and route table.

For A* it can give you some temporary increase in backtracking. And you will have fadeout effect for private routes.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 04, 2013, 11:13:41 AM
Quote from: inkelyad on January 04, 2013, 06:28:20 AM
Err..
1) Spread 'distance to hall' and private route calculations over month.
2) Don't take action on changes in road network. Use out-of date distance and route table.

For A* it can give you some temporary increase in backtracking. And you will have fadeout effect for private routes.

Using out of date routes won't work, I'm afraid, as the idea is to have the actual city car graphics following the routes instead of wondering around aimlessly, so that congestion can actually be simulated directly rather than being guessed at. Cars wouldn't be able to float mid-air with no roads... The advantage of storing routes on individual tiles is that we know instantly when a route is broken and can re-calculate precisely those routes necessary immediately, whilst leaving updates due to new roads opening to the next instalment of the full refresh.

Do you imagine spreading all the calculations over a month? The current system spreads them over a year, and that's still too much to have acceptable performance.

By "backtracking", do you mean cars going one way, then turning back on themselves as part of their route? That wouldn't work if we are to have actual cars following the route.

What do you mean by a "fadeout effect"?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 04, 2013, 12:00:33 PM
Quote from: jamespetts on January 04, 2013, 11:13:41 AM
Using out of date routes won't work, I'm afraid, as the idea is to have the actual city car graphics following the routes instead of wondering around aimlessly, so that congestion can actually be simulated directly rather than being guessed at. Cars wouldn't be able to float mid-air with no roads...  The advantage of storing routes on individual tiles is that we know instantly when a route is broken and can re-calculate precisely those routes necessary immediately, whilst leaving updates due to new roads opening to the next instalment of the full refresh.
Why not? Players car do this: they follow calculated route and do route search if next tile is unavailable.

Quote
Do you imagine spreading all the calculations over a month? The current system spreads them over a year, and that's still too much to have acceptable performance.
Well, over acceptable period of time. You need to spread only calculation of 'distance/time to hall' tables. Route for private car can be calculated when car is created.

Quote
By "backtracking", do you mean cars going one way, then turning back on themselves as part of their route?
No, I mean backtracking part of A* algorithm. 'distance to hall' heuristic speed up route search (no backtracking, we check 'right' direction first). With outdated distance tables algorithm can return wrong answer (suboptimal path or wrong 'no path is found') but I think we can accept this. This is temporary condition.

Quote
What do you mean by a "fadeout effect"?
Exact opposite of what you think as advantage. Routes should not be changed immediately when player delete/place road tile. This is gradual process IRL.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 04, 2013, 12:15:15 PM
Quote from: inkelyad on January 04, 2013, 12:00:33 PM
Why not? Players car do this: they follow calculated route and do route search if next tile is unavailable.
Well, over acceptable period of time. You need to spread only calculation of 'distance/time to hall' tables. Route for private car can be calculated when car is created.

Interesting - you imagine the same route being calculated many times over, and this being more efficient than calculating it once and storing it? I should point out, however, that the private car route would need to be calculated many more times than when the actual car is generated, as the route is used in the passenger generation algorithm: for each packet of passengers that has access to a private car, the private car route has to be checked, even if it is not used, to see whether those passengers will travel by private car or not, so far more of these calculations are necessary than the numbers of private cars generated. By what margin do you think that using this route distance to town hall calculation will speed up the processing of these routes? It would have to be many, many orders of magnitude faster to be able to do it like this.

QuoteNo, I mean backtracking part of A* algorithm. 'distance to hall' heuristic speed up route search (no backtracking, we check 'right' direction first). With outdated distance tables algorithm can return wrong answer (suboptimal path or wrong 'no path is found') but I think we can accept this. This is temporary condition.
Exact opposite of what you think as advantage. Routes should not be changed immediately when player delete/place road tile. This is gradual process IRL.

This could work, I suppose - but the real issue is whether the basic algorithm can be made fast enough.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 04, 2013, 12:59:54 PM
Quote from: jamespetts on January 04, 2013, 12:15:15 PM
Interesting - you imagine the same route being calculated many times over, and this being more efficient than calculating it once and storing it?
No, straightforward cache for calculated routes will be faster. But you need way too much memory for it. My objection was that suggested optimisation (copy know part of route) is too excessive and complex.

Quote
I should point out, however, that the private car route would need to be calculated many more times than when the actual car is generated, as the route is used in the passenger generation algorithm: for each packet of passengers that has access to a private car, the private car route has to be checked, even if it is not used, to see whether those passengers will travel by private car or not, so far more of these calculations are necessary than the numbers of private cars generated.
You have 'distance/time to destination city hall' map. You can use it in decision. It is not same as actual route, but good alternative.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 04, 2013, 01:48:42 PM
Quote from: inkelyad on January 04, 2013, 12:59:54 PM
No, straightforward cache for calculated routes will be faster. But you need way too much memory for it. My objection was that suggested optimisation (copy know part of route) is too excessive and complex.

By "too excessive and complex", do you mean that it will overly burden the memory and/or CPU and/or memory bandwidth such as to make it too slow in practice? Which specific part would be the most troublesome, do you think?

I wonder - if that is so, would it work better if, instead of copying the parts of the routes, we separated the routes themselves from a sort of meta-route object, and had the meta-route object store a series of pointers to routes and start and end cell numbers for those routes so that private cars could follow a series of route fragments? We should have to work out how to deal with deleted routes and back-referencing of routes if that was the case, though, and I strongly suspect that this would be much harder to code and more prone to bugs; but would it be a workable optimisation, do you think?

QuoteYou have 'distance/time to destination city hall' map. You can use it in decision. It is not same as actual route, but good alternative.

Isn't this exactly the same as the system that we have now, except, instead of having this for every road tile, we just have this for each town hall road tile?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 04, 2013, 02:23:11 PM
Quote from: jamespetts on January 04, 2013, 01:48:42 PM
By "too excessive and complex", do you mean that it will overly burden the memory and/or CPU and/or memory bandwidth such as to make it too slow in practice?
Yes.
Quote
Which specific part would be the most troublesome, do you think?
Searching/copying 'known part of route'. It will be hard to find good memory/cpu-time tradeof.

Quote
I wonder - if that is so, would it work better if, instead of copying the parts of the routes, we separated the routes themselves from a sort of meta-route object, and had the meta-route object store a series of pointers to routes and start and end cell numbers for those routes so that private cars could follow a series of route fragments?
It will work if you interested in routes between "interesting" points. But you want to use routes from every residential cell -> you need route (spanning) tree for whole map.

Quote
Isn't this exactly the same as the system that we have now, except, instead of having this for every road tile, we just have this for each town hall road tile?
I don't understand this. What do we have how?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 04, 2013, 03:18:32 PM
Quote from: inkelyad on January 04, 2013, 02:23:11 PM
Yes.Searching/copying 'known part of route'. It will be hard to find good memory/cpu-time tradeof.

Hmm. I don't envisage any searching - unless you mean checking each of the route tiles when copying to see if there is a destination city...?

QuoteIt will work if you interested in routes between "interesting" points. But you want to use routes from every residential cell -> you need route (spanning) tree for whole map.

Hmm - how would this work?
Quote
I don't understand this. What do we have how?

Unless "assume_everywhere_connected_by_road" is on (which it needs to be for larger maps because of the performance issues), each town searches for a connexion to each other town (that hasn't already found a connexion to it) using the A* method with straight line distance as the heuristic. The start and end point for each search is the piece of road outside the town hall.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 04, 2013, 08:21:58 PM
Quote from: jamespetts on January 04, 2013, 03:18:32 PM
Hmm. I don't envisage any searching - unless you mean checking each of the route tiles when copying to see if there is a destination city...?
Yes. You need to search through known paths and check 'can I use this?'.

Quote
Hmm - how would this work?
It was bad wording.
I was trying to say that you want too many 'source' points (each residential tile). Number of pairs [some residential tile, some interesting destination] is just too big. Some crossroad tile on 'central' road can be reused in thousands routes.

Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 05, 2013, 01:14:33 AM
Quote from: inkelyad on January 04, 2013, 08:21:58 PM
Yes. You need to search through known paths and check 'can I use this?'.

Hmm, I see - and this would take so much effort as to vitiate any savings?

QuoteIt was bad wording.
I was trying to say that you want too many 'source' points (each residential tile). Number of pairs [some residential tile, some interesting destination] is just too big. Some crossroad tile on 'central' road can be reused in thousands routes.

Hmm, perhaps I am being very dim, but I do not follow. What do you mean here exactly?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 05, 2013, 02:33:09 PM
Quote from: jamespetts on January 05, 2013, 01:14:33 AM
Hmm, I see - and this would take so much effort as to vitiate any savings?
Yes, I really think so.

Quote
Hmm, perhaps I am being very dim, but I do not follow. What do you mean here exactly?
It seems my English is not adequate for what I trying to say. Sorry.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 05, 2013, 03:09:51 PM
Quote from: inkelyad on January 05, 2013, 02:33:09 PM
It seems my English is not adequate for what I trying to say. Sorry.

Would I find the answer if I were to research "spanning tree", or did you have some special implementation in mind?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 05, 2013, 03:44:34 PM
Quote from: jamespetts on January 05, 2013, 03:09:51 PM
Would I find the answer if I were to research "spanning tree", or did you have some special implementation in mind?
No, spanning tree term was bad wording here.
You should read/research about it anyway. It is fundamental term of graph theory so it will be useful one way or another. And it is not that hard.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 06, 2013, 10:59:07 AM
Quote from: inkelyad on January 05, 2013, 03:44:34 PM
No, spanning tree term was bad wording here.
You should read/research about it anyway. It is fundamental term of graph theory so it will be useful one way or another. And it is not that hard.

Thank you. Is there any way that I can try to work out what you did mean...?

Edit: In particular, it is this sentence that confuses me somewhat:

QuoteSome crossroad tile on 'central' road can be reused in thousands routes.

When you refer to "can be used", do you just mean that, in the system that I propose, it will end up being used for thousands of routes, making any route searches through that tile using my system too slow - or were you describing a new system?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: inkelyad on January 06, 2013, 12:49:32 PM
Quote
When you refer to "can be used", do you just mean that, in the system that I propose, it will end up being used for thousands of routes, making any route searches through that tile using my system too slow - or were you describing a new system?
It is about your system. Look at road tile near factory with big catchment area (later in game, when you have fast transport). How many routes from residential tiles go through it?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 22, 2013, 11:25:00 PM
I am increasingly resigned to the view that it will not be possible, without some great advance in processing power, to simulate full point to point journeys for all city buildings, and that I shall probably have to content myself with improving the existing abstracted method of calculating journey times between town hall roads of cities and calculating a journey time per tile and extrapolating individual journeys from that measure as in the current code.

With that in mind, am I right in supposing that using Dijkstra's Algorithm to search from each city to each other reachable city, factory and attraction is the best way of doing this? In a world of, say, 512 cities, 512 factories and 128 attractions, how much time is this likely to take?

Also, does anyone know whether the existing route_t::find_route() method is an implementation of Dijkstra's Algorithm that can be used here with slight modification so as not to end the search when a single target is found, or does it need more fundamental changes?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: prissi on January 23, 2013, 10:30:19 AM
THere is find route, which will stop the search as soon as your think this is a fine target.

Doing a route search between all stuff is fairly out of questions, even with 10 cities there are 54 connections. (n*(n-1)/2-1). For your example of 512+512+128=1152 destinations/origins it still would be 662977 choices. If each takes 10ms to compute the it would last 1h50m ...

The station code is much faster, since it only has a few nodes to check to get to a destination or not.

For those massively parallel searches you would need a quantum computer; or just calculating when needed and clever caching.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 24, 2013, 12:00:25 AM
Hmm - but with the version of Dijkstra's Algorithm that does not stop when it finds a route to a particular place, but carries on until it explores all nodes, returning the cost to each target node as it finds it (without reconstructing the route), this would surely be only 512 instances of the algorithm running? Even if they took 250ms each, this would be just 128 seconds, or just over 2 minutes. If the cities are only re-checked once every game year (or even game month), this would be within acceptable limits, and even more so if this could be multi-threaded so as to check more than one city in different threads at once.

Or am I misunderstanding something...?

When we all finally do get quantum computers, I shall look forward to modelling private car traffic between all buildings and all other buildings (and if this is more than about 35 years in the future, I shall have more time to work on it by virtue of being retired... ;-) ).
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: sdog on January 24, 2013, 05:55:55 AM
I was half expecting your answer to prissis post would be: "Then i shall go on and build a quantum computer first, and code the private car traffic next year."
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: ӔO on January 24, 2013, 06:34:43 AM
probably not a good solution for many computers and far too easily said than done, but how about GPGPU?

From my understanding, pathfinding isn't too different from password cracking, is it not? You have a given set of rules, with hundreds of thousands of possibilities that need to be computed at once.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: prissi on January 24, 2013, 09:24:06 AM
That is certainly possible. You can run find route and always return false. Then find_route itself has to make a copy of the route, whenever it reaches a suitable point. That could be indeed finished quite quickly. Maybe you want to make way tiles on those route as "used by citycars" and thus when deleting such a waytile start the recalc algorithm again. weg_t should have still some flags unused.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: dennosius on January 24, 2013, 06:52:40 PM
I wasn't able to read the full discussion so far, so sorry if I missed something.

Doing the job with full accuracy requires the number of pathfindings for n cities n*(n-1) (/2 assuming bi-directionality), and I don't think there can be any other way. Even interconnected cities (way from A via B to C) don't make that easier, because the shortest/fastest way from A to C via B may (highly probably) not  be via the one tile next to B's town hall.

Vladki's idea from the first page sounds good to me: remembering the time info (distance/speed) of all inter-city connections. And then add some good guess for crossing the city or reaching the city centre (I think we know the size of any city and can assume 50 kph for city roads). This is not accurate if there's a tunnel or elevated highway crossing the city, but it may be good enough. Or calculate the actual travel time between all roads leaving the city through the city and to that tile at the town hall. This will increase the number of calculations even (much) more, but it may be faster as routes are much shorter (how is CPU usage of pathfinding related to the number of pathfindings and the distance?).

One more approach could be excluding impossibly faster connections. If Simutrans knows the travelling time by public transportation, we can exclude all connections that cannot be faster by road even if connected directly (straight) and with the fastest road (offset to the one or other direction could be added).

One more thought, although only indirectly related to the topic: Does it really assume that on a 200 kph highway everyone would go 200 kph, although most city cars don't go this fast?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 24, 2013, 11:36:27 PM
The resolution so far, I think, is to use Dijkstra's Algorithm (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) simultaneously to find the shortest path between a given city and all other cities (where by "city" I mean the single road tile outside that a city hall), calculate a journey time per straight line tile, and then use this abstraction for all other journeys (for example: if the distance between city A and city B (in the above definition of "city") is 10km, and the journey time between the two is 20 minutes, then, at 125m/tile, this yields a journey time per tile of 0.25 minutes; for a journey of 25km between a point in city A and a point in city B (being a journey of 200 tiles), the journey time would be assumed to be 200 * 0.25 = 50 minutes).

As to the speed equation, a maximum speed of the minimum of (1) the average maximum speed of all current city cars; and (2) a proportion of the maximum speed of the way is used for each tile; I also plan to reduce this by a further amount to take into account congestion, on the basis that the congestion figures shown in the city information window represent the percentage extra journey time necessary to traverse any given distance in the city as compared to a non-congested base, in the same fashion as the TomTom Congestion Index (http://www.tomtom.com/en_gb/congestionindex/).
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: prissi on January 25, 2013, 01:23:50 PM
The cost of reaching a certain tile already gives you an indication of speed and congestion from the route calculation. No need to do this twice. You can made a special fahrer_t class to return fals for any target and gives a cost function customized to your need.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 25, 2013, 01:50:08 PM
This is a very useful suggestion - thank you!
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 28, 2013, 02:33:28 AM
Hmm - I am having some trouble implementing this: I think that I am misunderstanding the relationship between your suggestions and the way in which find_route and calc_route work. find_route does not seem to call the get_kosten function, whereas calc_route will always return false without checking any routes if the destination is not specified (for example, if it is koord::invalid). I had set up a system whereby the journey time for each tile was calculated in get_kosten, and this is summed (and the total number of tiles calculated) in is_zeil. is_zeil then checks whether a city has been reached, and, if it has, adds the accumulated journey time per tile divided by the number of tiles to the relevant hashtable (stored in 100ths of a minute to preserve precision). I am not sure how to make this fit in with either find_route or calc_route. Is this what you had intended, or have I misunderstood somewhere?

For reference, here is my is_zeil method:


bool private_car_destination_finder_t::ist_ziel(const grund_t* gr, const grund_t*)
{

   accumulated_cost += current_tile_cost;

   if(!gr)
   {
      return false;
   }

   const koord k = gr->get_pos().get_2d();
   const stadt_t* city = welt->get_city(k);

   if(!city)
   {
      // TODO: Check also for non-city attractions and industries.
      // Might be necessary to store connexion information in road
      // tiles, as it might take a long time to search each tile here.

   }
   else
   {
      if(city->get_townhall_road() == k && city != origin_city)
      {
         // We use a different system for determining travel speeds in the current city.
         origin_city->add_road_connexion(accumulated_cost / number_of_tiles, city);
      }
   }

   return false;
}


And here is my get_kosten method:


int private_car_destination_finder_t::get_kosten(const grund_t* gr, sint32 max_speed, koord from_pos)
{
   const weg_t *w = gr->get_weg(road_wt);
   if(!w)
   {
      return 0xFFFF;
   }

   const uint32 max_tile_speed = w->get_max_speed(); // This returns speed in km/h.

   uint32 speed = min(max_speed, max_tile_speed);
   const stadt_t* city = origin_city->get_welt()->get_city(gr->get_pos().get_2d());

   if(city)
   {
      // If this is in a city, take account of congestion when calculating
      // the speed.
      const uint32 congestion = (uint32)city->get_congestion();
      speed -= (speed * congestion) / 100;
   }

   // Time = distance / speed
   if(w->is_diagonal())
   {
      // Diagonals are a *shorter* distance.
      meters_per_tile_x100 = (meters_per_tile_x100 * 5) / 7;
   }

   // T = d / (1000 / h)
   // T = d / (h * 1000)
   // T = d / ((h / 60) * (1000 / 60)
   // m == h / 60
   // T = d / (m * 16.67)
   // (m / 100)
   // T = d / ((m / 100) * (16.67 / 100)
   // T = d / ((m / 100) * 0.167)
   // T = (d * 100) / (m * 16.67) -- 100THS OF A MINUTE PER TILE

   const int cost = (int)meters_per_tile_x100 / ((speed * 167) / 10);

   current_tile_cost = cost;
   return cost;
}
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: prissi on January 28, 2013, 01:00:28 PM
It should do that; maybe because when searching route it will not correctly see all corners, but still, the current implementation is not good. It should use its own binary queue and cost function too.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 28, 2013, 11:21:46 PM
Ahh - so the solution, you think, is to modify the find_route method to use a cost function (in fahrer_t ?)? Or would I be better off writing a new method specifically for this task, based on find_route, but modified?

Also, where do you think that the binary queue should be used?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: prissi on January 29, 2013, 01:28:54 PM
If you use it to travel all the map with a cost function, you must use the binary queue (or something else to get always the lowerst cost first).
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 29, 2013, 01:42:03 PM
Is the existing "HOT_queue_t" method an implementation of the binary queue, or does one not exist for Simutrans at present? The calc_route (A*) method uses the binary heap; is this what you had in mind?
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on January 30, 2013, 12:56:05 AM
I think that I have found a workable way of doing this, copying as much as I can from the A* system but removing the heuristic element. I am not set up to produce .patch files, but something along the same lines should work for Standard, too. The following changes are needed in simconvoi.cc:


@@ -5670,33 +5670,33 @@ public:
    {
       return master->get_waytype();
    };
    virtual bool ist_befahrbar( const grund_t* gr ) const
    {
       return master->ist_befahrbar(gr);
    };
    virtual bool ist_ziel( const grund_t* gr, const grund_t* )
    {
       return gr->get_depot() && gr->get_depot()->get_besitzer() == master->get_besitzer() && gr->get_depot()->get_tile()->get_besch()->get_enabled() & traction_type;
    };
    virtual ribi_t::ribi get_ribi( const grund_t* gr) const
    {
       return master->get_ribi(gr);
    };
-   virtual int get_kosten( const grund_t*, const sint32, koord from_pos)
+   virtual int get_kosten( const grund_t* gr, const sint32, koord from_pos)
    {
-      return 1;
+      return master->get_kosten(gr, 0, from_pos);
    };
};


And in route.cc:


@@ -191,168 +191,204 @@ uint8 route_t::GET_NODES(ANode **nodes)
    dbg->fatal("GET_NODE","called while list in use");
    return 0;
}

void route_t::RELEASE_NODES(uint8 nodes_index)
{
    if (!_nodes_in_use[nodes_index])
       dbg->fatal("RELEASE_NODE","called while list free");
    _nodes_in_use[nodes_index] = false;
}


/* find the route to an unknown location
  * @author prissi
  */
-bool route_t::find_route(karte_t *welt, const koord3d start, fahrer_t *fahr, const uint32 /*max_khm*/, uint8 start_dir, uint32 weight, uint32 max_depth)
+bool route_t::find_route(karte_t *welt, const koord3d start, fahrer_t *fahr, const uint32 max_khm, uint8 start_dir, uint32 weight, uint32 max_depth)
{
    bool ok = false;

    // check for existing koordinates
    const grund_t* g = welt->lookup(start);
-   if (g == NULL) {
+   if (g == NULL)
+   {
       return false;
    }

    const uint8 enforce_weight_limits = welt->get_settings().get_enforce_weight_limits();

    // some thing for the search
    const waytype_t wegtyp = fahr->get_waytype();

    // memory in static list ...
    if(!MAX_STEP)
    {
       INIT_NODES(welt->get_settings().get_max_route_steps(), welt->get_groesse_x(), welt->get_groesse_y());
    }

    INT_CHECK("route 227");

-   // arrays for A*/Dijkstra's Algorithm
-   //static
-   vector_tpl<ANode*> open;
-   vector_tpl<ANode*> close;
+   // nothing in lists
+   // NOTE: This will have to be reworked substantially if this algorithm
+   // is to be multi-threaded anywhere: a specific vector or hashtable will
+   // have to be used instead.
+   welt->unmarkiere_alle();
+
+   // there are several variant for maintaining the open list
+   // however, only binary heap and HOT queue with binary heap are worth considering
+#if defined(tpl_HOT_queue_tpl_h)
+    // static
+   HOT_queue_tpl <ANode *> queue;
+#elif defined(tpl_binary_heap_tpl_h)
+    //static
+   binary_heap_tpl <ANode *> queue;
+#elif defined(tpl_sorted_heap_tpl_h)
+    //static
+   sorted_heap_tpl <ANode *> queue;
+#else
+    //static
+   prioqueue_tpl <ANode *> queue;
+#endif

    // nothing in lists
-   open.clear();
+   queue.clear();

    // we clear it here probably twice: does not hurt ...
    route.clear();

    // first tile is not valid?!?
-   if(  !fahr->ist_befahrbar(g)  ) {
+   if(!fahr->ist_befahrbar(g))
+   {
       return false;
    }

    ANode *nodes;
    uint8 ni = GET_NODES(&nodes);

    uint32 step = 0;
    ANode* tmp = &nodes[step++];
    if (route_t::max_used_steps < step)
+   {
       route_t::max_used_steps = step;
+   }
    tmp->parent = NULL;
    tmp->gr = g;
    tmp->count = 0;
+  tmp->g = 0;

    // start in open
-   open.append(tmp);
+   queue.insert(tmp);

//DBG_MESSAGE("route_t::find_route()","calc route from %d,%d,%d",start.x, start.y, start.z);
    const grund_t* gr;
-   do {
+   do
+   {
       // Hajo: this is too expensive to be called each step
-      if((step & 127) == 0) {
+      if((step & 127) == 0)
+      {
          INT_CHECK("route 264");
       }

-      tmp = open[0];
-      open.remove_at( 0 );
+      ANode *test_tmp = queue.pop();

-      close.append(tmp);
+      // already in open or closed (i.e. all processed nodes) list?
+      if(welt->ist_markiert(test_tmp->gr))
+      {
+         // we were already here on a faster route, thus ignore this branch
+         // (trading speed against memory consumption)
+         continue;
+      }
+
+      tmp = test_tmp;
       gr = tmp->gr;
+      welt->markiere(gr);

-//DBG_DEBUG("add to close","(%i,%i,%i) f=%i",gr->get_pos().x,gr->get_pos().y,gr->get_pos().z,tmp->f);
       // already there
-      if(  fahr->ist_ziel( gr, tmp->parent==NULL ? NULL : tmp->parent->gr )  ) {
+      if(fahr->ist_ziel(gr, tmp->parent == NULL ? NULL : tmp->parent->gr))
+      {
          // we added a target to the closed list: check for length
          break;
       }

       // testing all four possible directions
-      const ribi_t::ribi ribi =  fahr->get_ribi(gr);
-      for(  int r=0;  r<4;  r++  ) {
+      const ribi_t::ribi ribi = fahr->get_ribi(gr);
+      for(int r = 0; r < 4; r++)
+      {
          // a way goes here, and it is not marked (i.e. in the closed list)
          grund_t* to;
-         if(  (ribi & ribi_t::nsow[r] & start_dir)!=0  // allowed dir (we can restrict the first step by start_dir)
-            && koord_distance(start.get_2d(),gr->get_pos().get_2d()+koord::nsow[r])<max_depth   // not too far away
+         if((ribi & ribi_t::nsow[r] & start_dir) != 0  // allowed dir (we can restrict the first step by start_dir)
+            && koord_distance(start.get_2d(),gr->get_pos().get_2d()+koord::nsow[r]) < max_depth   // not too far away
             && gr->get_neighbour(to, wegtyp, ribi_t::nsow[r])  // is connected
             && fahr->ist_befahrbar(to)   // can be driven on
-         ) {
-            // already in open list?
-            if (is_in_list(open,  to)) continue;
-            // already in closed list (i.e. all processed nodes)
-            if (is_in_list(close, to)) continue;
+            && !welt->ist_markiert(to) // Not in the closed list
+         )
+         {

             weg_t* w = to->get_weg(fahr->get_waytype());
             
             if (enforce_weight_limits && w != NULL)
             {
                // Bernd Gabriel, Mar 10, 2010: way limit info
                const uint32 way_max_weight = w->get_max_weight();
                max_weight = min(max_weight, way_max_weight);

                if(enforce_weight_limits == 2 && weight > way_max_weight)
                {
                   // Avoid routing over ways for which the convoy is overweight.
                   continue;
                }
             }

             // not in there or taken out => add new
             ANode* k = &nodes[step++];
             if (route_t::max_used_steps < step)
+            {
                route_t::max_used_steps = step;
+            }

             k->parent = tmp;
             k->gr = to;
-            k->count = tmp->count+1;
+           k->count = tmp->count + 1;
+           k->g = tmp->g + fahr->get_kosten(to, max_khm, gr->get_pos().get_2d());

-//DBG_DEBUG("insert to open","%i,%i,%i",to->get_pos().x,to->get_pos().y,to->get_pos().z);
             // insert here
-            open.append(k);
+            queue.insert(k);
          }
       }

       // ok, now no more restrains
       start_dir = ribi_t::alle;

-   } while(  !open.empty()  &&  step < MAX_STEP  &&  open.get_count() < max_depth  );
+   } while(!queue.empty()  &&  step < MAX_STEP  &&  queue.get_count() < max_depth);

    INT_CHECK("route 330");

//DBG_DEBUG("reached","");
    // target reached?
-   if(!fahr->ist_ziel(gr,tmp->parent==NULL?NULL:tmp->parent->gr)  ||  step >= MAX_STEP) {
-      if(  step >= MAX_STEP  ) {
+   if(!fahr->ist_ziel(gr, tmp->parent == NULL ? NULL : tmp->parent->gr) || step >= MAX_STEP)
+   {
+      if(  step >= MAX_STEP  )
+      {
          dbg->warning("route_t::find_route()","Too many steps (%i>=max %i) in route (too long/complex)",step,MAX_STEP);
       }
    }
-   else {
+   else
+   {
       // reached => construct route
       route.clear();
       route.resize(tmp->count+16);
-      while(tmp != NULL) {
+      while(tmp != NULL)
+      {
          route.store_at( tmp->count, tmp->gr->get_pos() );
//DBG_DEBUG("add","%i,%i",tmp->pos.x,tmp->pos.y);
          tmp = tmp->parent;
       }
       ok = !route.empty();
    }

    RELEASE_NODES(ni);
    return ok;
}


I also recommend the following changes in route.h for consistency, although they are not essential:


@@ -39,35 +39,37 @@ protected:
private:

    // Bernd Gabriel, Mar 10, 2010: weight limit info
    uint32 max_weight;
public:
    // this class save the nodes during route search
    class ANode {
    public:
       ANode * parent;
       const grund_t* gr;
       uint32  f, g;
       uint8 dir;
       uint16 count;

       inline bool operator <= (const ANode &k) const { return f==k.f ? g<=k.g : f<=k.f; }
-      // next one only needed for sorted_heap_tpl
+#if defined(tpl_sorted_heap_tpl_h)
       inline bool operator == (const ANode &k) const { return f==k.f  &&  g==k.g; }
-      // next two only needed for HOT-queues
-      //inline bool is_matching(const ANode &l) const { return gr==l.gr; }
-      //inline uint32 get_distance() const { return f; }
+#endif
+#if defined(tpl_HOT_queue_tpl_h)
+      inline bool is_matching(const ANode &l) const { return gr==l.gr; }
+      inline uint32 get_distance() const { return f; }
+#endif
    };

private:
    static const uint8 MAX_NODES_ARRAY = 2;
    static ANode *_nodes[MAX_NODES_ARRAY];
    static bool _nodes_in_use[MAX_NODES_ARRAY]; // semaphores, since we only have few nodes arrays in memory


This should suffice for it to work in Standard, I think. Do let me know if there are any queries or if you think that anything should be done differently.

Edit: My implementation of Dijkstra's algorithm above contained an error (failing to add the cost of the last node), which I have now corrected.
Edit 2: Another error in the implementation: I had forgotten to initialise tmp->g. This is now corrected above.
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on February 03, 2013, 09:33:07 PM
I have now produced a working implementation of this for cities and factories: after some optimisation, I am getting 50-60ms per city on an optimised release build, which is not bad. If I add some sort of scheduler so that it doesn't do all the towns together at once at the beginning of a month, I should be able to get decent performance out of this, even on a very large map. I have still not been able to work out how to mark connected attractions, however: any help (http://forum.simutrans.com/index.php?topic=11414.new#new) would be appreciated.

I wonder whether, in theory, it would be possible to use a similar technique to run a Floyd-Warshall search from every building to every other (connected) building, although whether that would consume too much memory/memory bandwidth/CPU time is another matter entirely, and is probably a project for another day...
Title: Re: Modelling private car traffic without breaking the CPU bank
Post by: jamespetts on February 15, 2013, 11:53:08 PM
I have now succeeded in checking all the tiles of an attraction, and this system is now working properly. Also, I have discovered and fixed a further error in the implementation of Dikjstra's Algorithm outlined above, which is that I had previously failed to initialise tmp->g in the first node, which lead to too high a cost.