TrainRouteMetric::TrainRouteMetric(const TrackChain &tc, TrackChain::Direction dir)
{
- const TrackChain::TrackSet &ctracks = tc.get_tracks();
- for(TrackChain::TrackSet::const_iterator i=ctracks.begin(); i!=ctracks.end(); ++i)
+ vector<TrackIter> ends;
+ if(dir==TrackChain::UNSPECIFIED)
{
- if(dir==TrackChain::UNSPECIFIED)
+ for(unsigned i=0; i<2; ++i)
+ if(TrackIter end = tc.get_end(i))
+ ends.push_back(end);
+ }
+ else if(TrackIter end = tc.get_end(dir))
+ ends.push_back(end);
+
+ /* Initialize goals for the ends of the target chain. We travel away from
+ the goals in the search phase so the iters appear to point the wrong way. */
+ for(vector<TrackIter>::const_iterator i=ends.begin(); i!=ends.end(); ++i)
+ {
+ const TrackType::Endpoint &ep = i->endpoint();
+ unsigned nls = (*i)->get_n_link_slots();
+ for(unsigned j=0; j<nls; ++j)
{
- unsigned nls = (*i)->get_n_link_slots();
- for(unsigned j=0; j<nls; ++j)
- if(Track *link = (*i)->get_link(j))
- if(!ctracks.count(link))
- goals.push_back(TrackIter(*i, j));
+ TrackIter iter(i->track(), j);
+ if(ep.has_common_paths(iter.endpoint()))
+ goals.push_back(iter);
}
- else if(TrackIter iter = tc.iter_for(**i, reverse_dir))
- goals.push_back(iter);
}
list<TrackIter> queue;
queue.push_back(i->track);
}
+ /* Use Dijkstra's algorithm to find the shortest distance from the goal to
+ every reachable track in the layout. Entry points here become exit points
+ when looking up distances to the goal. */
while(!queue.empty())
{
TrackIter track = queue.front();
const Data &data = tracks[Key(track.track(), track.entry())];
const TrackType::Endpoint &ep = track.endpoint();
+
+ float multiplier = get_travel_multiplier(*track, track.entry());
for(unsigned i=0; ep.paths>>i; ++i)
if(ep.has_path(i))
{
continue;
Data &target = tracks[Key(next.track(), next.entry())];
- float dist = data.distance+track->get_type().get_path_length(i);
+ float dist = data.distance+track->get_type().get_path_length(i)*multiplier;
if(target.distance<0 || target.distance>dist)
{
target = Data(dist, data.goal);
i->base_distance = metric.get_distance_from(*i->track.track(), i->track.entry());
}
+float TrainRouteMetric::get_distance_from(const Track &track) const
+{
+ map<Key, Data>::const_iterator i = tracks.lower_bound(Key(&track, 0));
+ map<Key, Data>::const_iterator j = tracks.upper_bound(Key(&track, 255));
+
+ float result = -1;
+ for(; i!=j; ++i)
+ {
+ float d = i->second.distance+i->second.goal->base_distance;
+ if(result<0 || d<result)
+ result = d;
+ }
+
+ return result;
+}
+
float TrainRouteMetric::get_distance_from(const Track &track, unsigned exit) const
{
map<Key, Data>::const_iterator i = tracks.find(Key(&track, exit));
return i->second.distance+i->second.goal->base_distance;
}
+float TrainRouteMetric::get_travel_multiplier(const Track &track, unsigned exit) const
+{
+ int pref = track.get_preferred_exit();
+ if(pref>=0 && exit!=static_cast<unsigned>(pref))
+ return 5;
+
+ return 1;
+}
+
TrainRouteMetric::Goal::Goal():
base_distance(0)