3 #include "trackchain.h"
4 #include "trainroutemetric.h"
10 TrainRouteMetric::TrainRouteMetric(const TrackChain &tc, TrackChain::Direction dir)
12 /* Initialize goals for tracks in the target chain. We travel outwards from
13 the target in the search phase so the iters appear to point the wrong way. */
14 TrackChain::Direction reverse_dir = (dir==TrackChain::DOWN ? TrackChain::UP : TrackChain::DOWN);
15 const TrackChain::TrackSet &ctracks = tc.get_tracks();
16 for(TrackChain::TrackSet::const_iterator i=ctracks.begin(); i!=ctracks.end(); ++i)
18 if(dir==TrackChain::UNSPECIFIED)
20 unsigned nls = (*i)->get_n_link_slots();
21 for(unsigned j=0; j<nls; ++j)
22 if(Track *link = (*i)->get_link(j))
23 if(!ctracks.count(link))
24 goals.push_back(TrackIter(*i, j));
26 else if(TrackIter iter = tc.iter_for(**i, reverse_dir))
27 goals.push_back(iter);
30 list<TrackIter> queue;
31 for(vector<Goal>::iterator i=goals.begin(); i!=goals.end(); ++i)
33 tracks[Key(i->track.track(), i->track.entry())] = Data(0, &*i);
34 queue.push_back(i->track);
37 /* Use Dijkstra's algorithm to find the shortest distance from the goal to
38 every reachable track in the layout. Entry points here become exit points
39 when looking up distances to the goal. */
42 TrackIter track = queue.front();
44 const Data &data = tracks[Key(track.track(), track.entry())];
46 const TrackType::Endpoint &ep = track.endpoint();
47 for(unsigned i=0; ep.paths>>i; ++i)
50 TrackIter next = track.next(i);
54 Data &target = tracks[Key(next.track(), next.entry())];
55 float dist = data.distance+track->get_type().get_path_length(i);
56 if(target.distance<0 || target.distance>dist)
58 target = Data(dist, data.goal);
59 queue.push_back(next);
65 void TrainRouteMetric::chain_to(const TrainRouteMetric &metric)
67 for(vector<Goal>::iterator i=goals.begin(); i!=goals.end(); ++i)
68 i->base_distance = metric.get_distance_from(*i->track.track(), i->track.entry());
71 float TrainRouteMetric::get_distance_from(const Track &track) const
73 map<Key, Data>::const_iterator i = tracks.lower_bound(Key(&track, 0));
74 map<Key, Data>::const_iterator j = tracks.upper_bound(Key(&track, 255));
79 float d = i->second.distance+i->second.goal->base_distance;
80 if(result<0 || d<result)
87 float TrainRouteMetric::get_distance_from(const Track &track, unsigned exit) const
89 map<Key, Data>::const_iterator i = tracks.find(Key(&track, exit));
93 return i->second.distance+i->second.goal->base_distance;
97 TrainRouteMetric::Goal::Goal():
101 TrainRouteMetric::Goal::Goal(const TrackIter &t):
107 TrainRouteMetric::Data::Data():
112 TrainRouteMetric::Data::Data(float d, const Goal *g):