source/libr2c2/trainroutemetric.cpp

   1 #include <list>
   2 #include "track.h"
   3 #include "trackchain.h"
   4 #include "trainroutemetric.h"
   5
   6 using namespace std;
   7
   8 namespace R2C2 {
   9
  10 TrainRouteMetric::TrainRouteMetric(const TrackChain &tc, TrackChain::Direction dir)
  11 {
  12         vector<TrackIter> ends;
  13         if(dir==TrackChain::UNSPECIFIED)
  14         {
  15                 for(unsigned i=0; i<2; ++i)
  16                         if(TrackIter end = tc.get_end(i))
  17                                 ends.push_back(end);
  18         }
  19         else if(TrackIter end = tc.get_end(dir))
  20                 ends.push_back(end);
  21
  22         /* Initialize goals for the ends of the target chain.  We travel away from
  23         the goals in the search phase so the iters appear to point the wrong way. */
  24         for(vector<TrackIter>::const_iterator i=ends.begin(); i!=ends.end(); ++i)
  25         {
  26                 const TrackType::Endpoint &ep = i->endpoint();
  27                 unsigned nls = (*i)->get_n_link_slots();
  28                 for(unsigned j=0; j<nls; ++j)
  29                 {
  30                         TrackIter iter(i->track(), j);
  31                         if(ep.has_common_paths(iter.endpoint()))
  32                                 goals.push_back(iter);
  33                 }
  34         }
  35
  36         list<TrackIter> queue;
  37         for(vector<Goal>::iterator i=goals.begin(); i!=goals.end(); ++i)
  38         {
  39                 tracks[Key(i->track.track(), i->track.entry())] = Data(0, &*i);
  40                 queue.push_back(i->track);
  41         }
  42
  43         /* Use Dijkstra's algorithm to find the shortest distance from the goal to
  44         every reachable track in the layout.  Entry points here become exit points
  45         when looking up distances to the goal. */
  46         while(!queue.empty())
  47         {
  48                 TrackIter track = queue.front();
  49                 queue.pop_front();
  50                 const Data &data = tracks[Key(track.track(), track.entry())];
  51
  52                 const TrackType::Endpoint &ep = track.endpoint();
  53
  54                 float multiplier = get_travel_multiplier(*track, track.entry());
  55                 for(unsigned i=0; ep.paths>>i; ++i)
  56                         if(ep.has_path(i))
  57                         {
  58                                 TrackIter next = track.next(i);
  59                                 if(!next)
  60                                         continue;
  61
  62                                 Data &target = tracks[Key(next.track(), next.entry())];
  63                                 float dist = data.distance+track->get_type().get_path_length(i)*multiplier;
  64                                 if(target.distance<0 || target.distance>dist)
  65                                 {
  66                                         target = Data(dist, data.goal);
  67                                         queue.push_back(next);
  68                                 }
  69                         }
  70         }
  71 }
  72
  73 void TrainRouteMetric::chain_to(const TrainRouteMetric &metric)
  74 {
  75         for(vector<Goal>::iterator i=goals.begin(); i!=goals.end(); ++i)
  76                 i->base_distance = metric.get_distance_from(*i->track.track(), i->track.entry());
  77 }
  78
  79 float TrainRouteMetric::get_distance_from(const Track &track) const
  80 {
  81         map<Key, Data>::const_iterator i = tracks.lower_bound(Key(&track, 0));
  82         map<Key, Data>::const_iterator j = tracks.upper_bound(Key(&track, 255));
  83
  84         float result = -1;
  85         for(; i!=j; ++i)
  86         {
  87                 float d = i->second.distance+i->second.goal->base_distance;
  88                 if(result<0 || d<result)
  89                         result = d;
  90         }
  91
  92         return result;
  93 }
  94
  95 float TrainRouteMetric::get_distance_from(const Track &track, unsigned exit) const
  96 {
  97         map<Key, Data>::const_iterator i = tracks.find(Key(&track, exit));
  98         if(i==tracks.end())
  99                 return -1;
 100
 101         return i->second.distance+i->second.goal->base_distance;
 102 }
 103
 104 float TrainRouteMetric::get_travel_multiplier(const Track &track, unsigned exit) const
 105 {
 106         int pref = track.get_preferred_exit();
 107         if(pref>=0 && exit!=static_cast<unsigned>(pref))
 108                 return 5;
 109
 110         return 1;
 111 }
 112
 113
 114 TrainRouteMetric::Goal::Goal():
 115         base_distance(0)
 116 { }
 117
 118 TrainRouteMetric::Goal::Goal(const TrackIter &t):
 119         track(t),
 120         base_distance(0)
 121 { }
 122
 123
 124 TrainRouteMetric::Data::Data():
 125         distance(-1),
 126         goal(0)
 127 { }
 128
 129 TrainRouteMetric::Data::Data(float d, const Goal *g):
 130         distance(d),
 131         goal(g)
 132 { }
 133
 134 } // namespace R2C2