News:

Simutrans Wiki Manual
The official on-line manual for Simutrans. Read and contribute.

Modelling private car traffic without breaking the CPU bank

Started by jamespetts, March 24, 2012, 12:16:18 AM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

inkelyad

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?

jamespetts

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...
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

inkelyad

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.

jamespetts

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"?
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

inkelyad

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.

jamespetts

#110
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.
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

inkelyad

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.

jamespetts

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?
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

inkelyad

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?

jamespetts

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.
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

inkelyad

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.


jamespetts

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?
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

inkelyad

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.

jamespetts

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?
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

inkelyad

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.

jamespetts

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?
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

inkelyad

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?

jamespetts

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?
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

prissi

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.

jamespetts

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... ;-) ).
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

sdog

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

ӔO

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.
My Sketchup open project sources
various projects rolled up: http://dl.dropbox.com/u/17111233/Roll_up.rar

Colour safe chart:

prissi

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.

dennosius

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?

jamespetts

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.
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

prissi

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.

jamespetts

Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

jamespetts

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;
}
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

prissi

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.

jamespetts

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?
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

prissi

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

jamespetts

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?
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

jamespetts

#137
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.
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

jamespetts

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...
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.

jamespetts

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.
Download Simutrans-Extended.

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

Follow Simutrans-Extended on Facebook.