This replaces the cost penalty for routing steps. In the penalty approach
it was possible to get two or more steps with the same penalty, which
would then race with each other. In the new approach, all other steps are
sorted by their unpenalized cost and only the preferred one gets special
treatment.
TrainRoutePlanner::TrainRoutePlanner(Layout &layout):
goal(0),
TrainRoutePlanner::TrainRoutePlanner(Layout &layout):
goal(0),
+ path_switch_bias(15*Time::sec),
timeout(10*Time::sec),
result(PENDING),
thread(0)
timeout(10*Time::sec),
result(PENDING),
thread(0)
{
list<RoutingStep> new_steps;
step.create_successors(new_steps);
{
list<RoutingStep> new_steps;
step.create_successors(new_steps);
+ if(new_steps.empty())
+ return;
+
+ if(!queue.empty() && new_steps.front().cost_estimate<queue.front().cost_estimate+path_switch_bias)
+ new_steps.front().preferred = true;
queue.merge(new_steps);
}
queue.merge(new_steps);
}
TrainRoutePlanner::RoutingStep::RoutingStep():
TrainRoutePlanner::RoutingStep::RoutingStep():
prev(0)
{ }
TrainRoutePlanner::RoutingStep::RoutingStep(const RoutingStep *p):
time(p->time),
prev(0)
{ }
TrainRoutePlanner::RoutingStep::RoutingStep(const RoutingStep *p):
time(p->time),
cost_estimate(p->cost_estimate),
cost_estimate(p->cost_estimate),
trains(p->trains),
prev(p)
{ }
trains(p->trains),
prev(p)
{ }
create_successor(next, train_index, i, new_steps);
}
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
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
void TrainRoutePlanner::RoutingStep::update_estimate()
{
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;
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
{
bool TrainRoutePlanner::RoutingStep::operator<(const RoutingStep &other) const
{
+ if(preferred!=other.preferred)
+ return preferred>other.preferred;
return cost_estimate<other.cost_estimate;
}
return cost_estimate<other.cost_estimate;
}
struct RoutingStep
{
Msp::Time::TimeDelta time;
struct RoutingStep
{
Msp::Time::TimeDelta time;
- Msp::Time::TimeDelta penalty;
Msp::Time::TimeDelta cost_estimate;
Msp::Time::TimeDelta cost_estimate;
std::vector<TrainRoutingState> trains;
const RoutingStep *prev;
std::vector<TrainRoutingState> trains;
const RoutingStep *prev;
std::list<RoutingStep> steps;
std::list<RoutingStep> queue;
const RoutingStep *goal;
std::list<RoutingStep> steps;
std::list<RoutingStep> queue;
const RoutingStep *goal;
+ Msp::Time::TimeDelta path_switch_bias;
Msp::Time::TimeDelta timeout;
Result result;
PlanningThread *thread;
Msp::Time::TimeDelta timeout;
Result result;
PlanningThread *thread;