TrainRoutePlanner::TrainRoutePlanner(Layout &layout):
goal(0),
+ path_switch_bias(15*Time::sec),
timeout(10*Time::sec),
result(PENDING),
thread(0)
{
list<RoutingStep> new_steps;
step.create_successors(new_steps);
+ if(new_steps.empty())
+ return;
+
new_steps.sort();
+ if(!queue.empty() && new_steps.front().cost_estimate<queue.front().cost_estimate+path_switch_bias)
+ new_steps.front().preferred = true;
queue.merge(new_steps);
}
TrainRoutePlanner::TrainRoutingInfo::TrainRoutingInfo(Train &t):
train(&t),
+ length(0),
speed(train->get_maximum_speed()),
first_noncritical(train->get_last_critical_block().next().block()),
router(train->get_ai_of_type<TrainRouter>()),
has_duration = router->get_trip_duration();
}
+ unsigned n_vehs = train->get_n_vehicles();
+ for(unsigned i=0; i<n_vehs; ++i)
+ length += train->get_vehicle(i).get_type().get_length();
+
// If no maximum speed is specified, use a sensible default
if(!speed)
speed = 20*train->get_layout().get_catalogue().get_scale();
distance_traveled(other.distance_traveled),
remaining_estimate(other.remaining_estimate),
wait_time(other.wait_time),
+ estimated_wait(other.estimated_wait),
blocked_by(other.blocked_by)
{
++occupied_tracks->refcount;
return ((track->get_type().get_path_length(path)-offset)/info->speed)*Time::sec+delay;
}
+Time::TimeDelta TrainRoutePlanner::TrainRoutingState::get_time_to_pass(Track &trk) const
+{
+ if(is_occupying(trk))
+ {
+ float passed_length = 0;
+ for(const OccupiedTrack *occ=occupied_tracks; (occ && occ->track!=&trk); occ=occ->next)
+ passed_length += occ->path_length;
+ return (max(info->length-passed_length, 0.0f)/info->speed)*Time::sec+delay;
+ }
+
+ for(unsigned wp=waypoint; wp<info->waypoints.size(); ++wp)
+ {
+ float distance = info->metrics[wp]->get_distance_from(trk);
+ if(distance>=0 && distance<remaining_estimate)
+ return ((remaining_estimate-distance+info->length)/info->speed)*Time::sec+delay;
+ }
+
+ return Time::day;
+}
+
bool TrainRoutePlanner::TrainRoutingState::is_occupying(Track &trk) const
{
if(state==ARRIVED && !duration && info->has_duration)
if(duration)
duration = max(duration-secs*Time::sec, Time::zero);
+ if(estimated_wait)
+ estimated_wait = max(estimated_wait-secs*Time::sec, Time::zero);
+
if(state==MOVING)
advance(info->speed*secs);
else if(state!=ARRIVED)
offset = 0;
}
+void TrainRoutePlanner::TrainRoutingState::set_path(unsigned p)
+{
+ path = p;
+ OccupiedTrack *next_occ = occupied_tracks->next;
+ if(!--occupied_tracks->refcount)
+ delete occupied_tracks;
+ occupied_tracks = new OccupiedTrack(*track, path, next_occ);
+ update_estimate();
+}
+
void TrainRoutePlanner::TrainRoutingState::update_estimate()
{
TrackIter iter = track.reverse(path);
TrainRoutePlanner::RoutingStep::RoutingStep():
+ preferred(false),
prev(0)
{ }
TrainRoutePlanner::RoutingStep::RoutingStep(const RoutingStep *p):
time(p->time),
- penalty(p->penalty),
cost_estimate(p->cost_estimate),
+ preferred(false),
trains(p->trains),
prev(p)
{ }
create_successor(next, train_index, i, new_steps);
}
- new_steps.sort();
- for(list<RoutingStep>::iterator i=new_steps.begin(); ++i!=new_steps.end(); )
- {
- i->penalty += 5*Time::sec;
- i->update_estimate();
- }
-
if(entry_ep.paths!=train.track->get_type().get_paths() && !train.critical)
{
/* Create a waiting state before the track if there's at least one path
RoutingStep wait(this);
wait.advance(dt);
wait.trains[train_index].state = WAITING;
- wait.penalty += 15*Time::sec;
+
+ Time::TimeDelta estimated_wait = Time::day;
+ for(unsigned i=0; i<wait.trains.size(); ++i)
+ if(i!=static_cast<unsigned>(train_index) && wait.trains[i].state!=ARRIVED)
+ {
+ Time::TimeDelta ttp = wait.trains[i].get_time_to_pass(*train.track);
+ estimated_wait = min(estimated_wait, ttp);
+ }
+ wait.trains[train_index].estimated_wait = estimated_wait;
+
wait.update_estimate();
if(wait.is_viable())
new_steps.push_back(wait);
{
TrainRoutingState &train = next.trains[train_index];
- train.path = path;
- train.update_estimate();
+ train.set_path(path);
next.update_estimate();
if(next.is_viable())
new_steps.push_back(next);
if(i->info->first_noncritical->has_track(*next_track))
i->critical = false;
+ if(i->state!=BLOCKED)
+ i->estimated_wait = trains[i->blocked_by].get_time_to_pass(*next_track);
+
/* Trains in the WAITING state will also transition to BLOCKED and
then to MOVING when the other train has passed. */
i->state = BLOCKED;
}
else if(i->state==BLOCKED)
+ {
+ i->estimated_wait = Time::zero;
i->state = MOVING;
+ }
}
else
i->state = BLOCKED;
void TrainRoutePlanner::RoutingStep::update_estimate()
{
- cost_estimate = penalty;
+ cost_estimate = Time::zero;
for(vector<TrainRoutingState>::const_iterator i=trains.begin(); i!=trains.end(); ++i)
if(i->remaining_estimate>=0)
- cost_estimate += i->wait_time+((i->distance_traveled+i->remaining_estimate)/i->info->speed)*Time::sec;
+ cost_estimate += i->wait_time+i->estimated_wait+((i->distance_traveled+i->remaining_estimate)/i->info->speed)*Time::sec;
}
bool TrainRoutePlanner::RoutingStep::is_viable() const
bool TrainRoutePlanner::RoutingStep::operator<(const RoutingStep &other) const
{
+ if(preferred!=other.preferred)
+ return preferred>other.preferred;
return cost_estimate<other.cost_estimate;
}