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();
delay(info->router->get_departure_delay()),
duration(info->router->get_trip_duration()),
waypoint(0),
+ distance_traveled(0),
blocked_by(-1)
{
const Vehicle *veh = &info->train->get_vehicle(0);
iter = iter.next();
}
+ travel_multiplier = info->metrics[waypoint]->get_travel_multiplier(*track, track.reverse(path).entry());
+
update_estimate();
}
delay(other.delay),
duration(other.duration),
waypoint(other.waypoint),
+ travel_multiplier(other.travel_multiplier),
distance_traveled(other.distance_traveled),
remaining_estimate(other.remaining_estimate),
wait_time(other.wait_time),
Time::TimeDelta TrainRoutePlanner::TrainRoutingState::get_time_to_next_track() const
{
- return ((track->get_type().get_path_length(path)-offset)/info->speed)*Time::sec+delay;
+ return ((occupied_tracks->path_length-offset)/info->speed)*Time::sec+delay;
}
Time::TimeDelta TrainRoutePlanner::TrainRoutingState::get_time_to_pass(Track &trk) const
{
if(is_occupying(trk))
- return Time::zero;
+ {
+ 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->speed)*Time::sec+delay;
+ return ((remaining_estimate-distance+info->length)/info->speed)*Time::sec+delay;
}
return Time::day;
occupied_tracks->n_tracks -= count_to_free;
}
- distance_traveled += distance;
- remaining_estimate -= distance;
+ distance_traveled += distance*travel_multiplier;
+ remaining_estimate -= distance*travel_multiplier;
}
void TrainRoutePlanner::TrainRoutingState::advance(const Time::TimeDelta &dt)
}
float secs = dt/Time::sec;
- // There may be negative delay remaining after previous step.
+ // There may be some delay remaining.
if(delay)
{
secs -= delay/Time::sec;
if(estimated_wait)
estimated_wait = max(estimated_wait-secs*Time::sec, Time::zero);
- if(state==MOVING)
+ float distance = info->speed*secs;
+ float remaining_on_track = occupied_tracks->path_length-offset;
+ if(state==MOVING || distance<remaining_on_track)
advance(info->speed*secs);
else if(state!=ARRIVED)
- wait_time += secs*Time::sec;
+ {
+ if(remaining_on_track>0)
+ {
+ advance(remaining_on_track);
+ wait_time += (secs-remaining_on_track/info->speed)*Time::sec;
+ }
+ else
+ wait_time += secs*Time::sec;
+ }
}
void TrainRoutePlanner::TrainRoutingState::advance_track(unsigned next_path)
{
float distance = occupied_tracks->path_length-offset;
+
track = track.next(path);
path = next_path;
occupied_tracks = new OccupiedTrack(*track, path, occupied_tracks);
+
advance(distance);
offset = 0;
+ travel_multiplier = info->metrics[waypoint]->get_travel_multiplier(*track, track.reverse(path).entry());
+}
+
+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);
- remaining_estimate = info->metrics[waypoint]->get_distance_from(*iter.track(), iter.entry());
+ const TrainRouteMetric *metric = info->metrics[waypoint];
+ remaining_estimate = metric->get_distance_from(*iter, iter.entry());
+ travel_multiplier = metric->get_travel_multiplier(*iter, iter.entry());
if(remaining_estimate>=0)
- remaining_estimate += track->get_type().get_path_length(path)-offset;
+ remaining_estimate += (occupied_tracks->path_length-offset)*travel_multiplier;
}
bool TrainRoutePlanner::TrainRoutingState::is_viable() const
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)
{ }
if(next.update_states() && next.check_deadlocks())
return;
- int train_index = find_next_train();
+ int train_index = next.find_next_train();
if(train_index<0)
return;
return;
}
- train.advance_track(0);
+ if(train.state==MOVING)
+ train.advance_track(0);
+ else
+ {
+ new_steps.push_back(next);
+ return;
+ }
const TrackType::Endpoint &entry_ep = train.track.endpoint();
if(train.critical)
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
{
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;
int TrainRoutePlanner::RoutingStep::find_next_train() const
{
+ /* Pick a moving train with the lowest time to next track. A train that
+ just became blocked can still travel until the end of its current track,
+ so consider those too. */
Time::TimeDelta min_dt;
int next_train = -1;
for(unsigned i=0; i<trains.size(); ++i)
- if(trains[i].state==MOVING)
+ if(trains[i].state==MOVING || (trains[i].state==BLOCKED && prev && prev->trains[i].state==MOVING))
{
Time::TimeDelta dt = trains[i].get_time_to_next_track();
if(dt<min_dt || next_train<0)
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->estimated_wait+((i->distance_traveled+i->remaining_estimate)/i->info->speed)*Time::sec;
bool TrainRoutePlanner::RoutingStep::operator<(const RoutingStep &other) const
{
+ if(preferred!=other.preferred)
+ return preferred>other.preferred;
return cost_estimate<other.cost_estimate;
}
projects / r2c2.git / blobdiff