The International Simutrans Forum

 

Author Topic: Modelling private car traffic without breaking the CPU bank  (Read 22504 times)

0 Members and 1 Guest are viewing this topic.

Offline inkelyad

  • Devotees (Inactive)
  • *
  • Posts: 482
  • Languages: EN, RU
Re: Modelling private car traffic without breaking the CPU bank
« Reply #105 on: January 03, 2013, 09:23:27 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?

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #106 on: January 03, 2013, 11:37:32 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.

Quote
I 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...

Offline inkelyad

  • Devotees (Inactive)
  • *
  • Posts: 482
  • Languages: EN, RU
Re: Modelling private car traffic without breaking the CPU bank
« Reply #107 on: January 04, 2013, 06:28:20 AM »
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.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #108 on: January 04, 2013, 11:13:41 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"?

Offline inkelyad

  • Devotees (Inactive)
  • *
  • Posts: 482
  • Languages: EN, RU
Re: Modelling private car traffic without breaking the CPU bank
« Reply #109 on: January 04, 2013, 12:00:33 PM »
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.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #110 on: January 04, 2013, 12:15:15 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.

Quote
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.
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.
« Last Edit: January 04, 2013, 12:51:19 PM by jamespetts »

Offline inkelyad

  • Devotees (Inactive)
  • *
  • Posts: 482
  • Languages: EN, RU
Re: Modelling private car traffic without breaking the CPU bank
« Reply #111 on: January 04, 2013, 12:59:54 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.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #112 on: January 04, 2013, 01:48:42 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?

Quote
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.

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?

Offline inkelyad

  • Devotees (Inactive)
  • *
  • Posts: 482
  • Languages: EN, RU
Re: Modelling private car traffic without breaking the CPU bank
« Reply #113 on: January 04, 2013, 02:23:11 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?

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #114 on: January 04, 2013, 03:18:32 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...?

Quote
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.

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.

Offline inkelyad

  • Devotees (Inactive)
  • *
  • Posts: 482
  • Languages: EN, RU
Re: Modelling private car traffic without breaking the CPU bank
« Reply #115 on: January 04, 2013, 08:21:58 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.


Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #116 on: January 05, 2013, 01:14:33 AM »
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?

Quote
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.

Hmm, perhaps I am being very dim, but I do not follow. What do you mean here exactly?

Offline inkelyad

  • Devotees (Inactive)
  • *
  • Posts: 482
  • Languages: EN, RU
Re: Modelling private car traffic without breaking the CPU bank
« Reply #117 on: January 05, 2013, 02:33:09 PM »
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.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #118 on: January 05, 2013, 03:09:51 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?

Offline inkelyad

  • Devotees (Inactive)
  • *
  • Posts: 482
  • Languages: EN, RU
Re: Modelling private car traffic without breaking the CPU bank
« Reply #119 on: January 05, 2013, 03:44:34 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.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #120 on: January 06, 2013, 10:59:07 AM »
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:

Quote
Some 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?

Offline inkelyad

  • Devotees (Inactive)
  • *
  • Posts: 482
  • Languages: EN, RU
Re: Modelling private car traffic without breaking the CPU bank
« Reply #121 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?

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #122 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?

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9556
  • Languages: De,EN,JP
Re: Modelling private car traffic without breaking the CPU bank
« Reply #123 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.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #124 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... ;-) ).

Offline sdog

  • Devotee
  • *
  • Posts: 2039
Re: Modelling private car traffic without breaking the CPU bank
« Reply #125 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."

Offline ӔO

  • Devotees (Inactive)
  • *
  • Posts: 2345
  • Hopefully helpful
  • Languages: en, jp
Re: Modelling private car traffic without breaking the CPU bank
« Reply #126 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.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9556
  • Languages: De,EN,JP
Re: Modelling private car traffic without breaking the CPU bank
« Reply #127 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.

Offline dennosius

  • *
  • Posts: 63
  • Languages: EN,DE
Re: Modelling private car traffic without breaking the CPU bank
« Reply #128 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?

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #129 on: January 24, 2013, 11:36:27 PM »
The resolution so far, I think, is to use Dijkstra's 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.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9556
  • Languages: De,EN,JP
Re: Modelling private car traffic without breaking the CPU bank
« Reply #130 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.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #131 on: January 25, 2013, 01:50:08 PM »
This is a very useful suggestion - thank you!

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #132 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:

Code: [Select]
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:

Code: [Select]
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;
}

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9556
  • Languages: De,EN,JP
Re: Modelling private car traffic without breaking the CPU bank
« Reply #133 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.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #134 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?

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9556
  • Languages: De,EN,JP
Re: Modelling private car traffic without breaking the CPU bank
« Reply #135 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).

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #136 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?

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #137 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:

Code: [Select]
@@ -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:

Code: [Select]
@@ -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:

Code: [Select]
@@ -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.
« Last Edit: February 15, 2013, 11:52:00 PM by jamespetts »

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #138 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 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...

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Modelling private car traffic without breaking the CPU bank
« Reply #139 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.