3 #include "trackchain.h"
4 #include "trainroutemetric.h"
10 TrainRouteMetric::TrainRouteMetric(const TrackChain &tc, TrackChain::Direction dir)
12 vector<TrackIter> ends;
13 if(dir==TrackChain::UNSPECIFIED)
15 for(unsigned i=0; i<2; ++i)
16 if(TrackIter end = tc.get_end(i))
19 else if(TrackIter end = tc.get_end(dir))
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)
26 const TrackType::Endpoint &ep = i->endpoint();
27 unsigned nls = (*i)->get_n_link_slots();
28 for(unsigned j=0; j<nls; ++j)
30 TrackIter iter(i->track(), j);
31 if(ep.has_common_paths(iter.endpoint()))
32 goals.push_back(iter);
36 list<TrackIter> queue;
37 for(vector<Goal>::iterator i=goals.begin(); i!=goals.end(); ++i)
39 tracks[Key(i->track.track(), i->track.entry())] = Data(0, &*i);
40 queue.push_back(i->track);
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. */
48 TrackIter track = queue.front();
50 const Data &data = tracks[Key(track.track(), track.entry())];
52 const TrackType::Endpoint &ep = track.endpoint();
54 float multiplier = get_travel_multiplier(*track, track.entry());
55 for(unsigned i=0; ep.paths>>i; ++i)
58 TrackIter next = track.next(i);
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)
66 target = Data(dist, data.goal);
67 queue.push_back(next);
73 void TrainRouteMetric::chain_to(const TrainRouteMetric &metric)
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());
79 float TrainRouteMetric::get_distance_from(const Track &track) const
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));
87 float d = i->second.distance+i->second.goal->base_distance;
88 if(result<0 || d<result)
95 float TrainRouteMetric::get_distance_from(const Track &track, unsigned exit) const
97 map<Key, Data>::const_iterator i = tracks.find(Key(&track, exit));
101 return i->second.distance+i->second.goal->base_distance;
104 float TrainRouteMetric::get_travel_multiplier(const Track &track, unsigned exit) const
106 int pref = track.get_preferred_exit();
107 if(pref>=0 && exit!=static_cast<unsigned>(pref))
114 TrainRouteMetric::Goal::Goal():
118 TrainRouteMetric::Goal::Goal(const TrackIter &t):
124 TrainRouteMetric::Data::Data():
129 TrainRouteMetric::Data::Data(float d, const Goal *g):