From 9976acc82d98c8aecde0152a72be8cc8882e35ff Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Thu, 5 Feb 2015 10:48:48 +0200 Subject: [PATCH] Penalize steps other than the fastest one This encourages the planner to follow a single chain of steps and avoids exploding the state tree too much. In the future this may be replaced by different speed limits on diverging paths of turnouts (reducing the ambiguity of fastest path) and an actual heuristic for potential wait time (giving wait states an implicit penalty). --- source/libr2c2/trainrouteplanner.cpp | 12 +++++++++++- source/libr2c2/trainrouteplanner.h | 1 + 2 files changed, 12 insertions(+), 1 deletion(-) diff --git a/source/libr2c2/trainrouteplanner.cpp b/source/libr2c2/trainrouteplanner.cpp index 163bb28..dbe6035 100644 --- a/source/libr2c2/trainrouteplanner.cpp +++ b/source/libr2c2/trainrouteplanner.cpp @@ -427,6 +427,7 @@ TrainRoutePlanner::RoutingStep::RoutingStep(): TrainRoutePlanner::RoutingStep::RoutingStep(const RoutingStep *p): time(p->time), + penalty(p->penalty), cost_estimate(p->cost_estimate), trains(p->trains), prev(p) @@ -473,11 +474,20 @@ void TrainRoutePlanner::RoutingStep::create_successors(list &new_st new_steps.push_back(next); } + new_steps.sort(); + for(list::iterator i=new_steps.begin(); ++i!=new_steps.end(); ) + { + i->penalty += 5*Time::sec; + i->update_estimate(); + } + if(next_entry_ep.paths!=next_track->get_type().get_paths()) { RoutingStep wait(this); wait.advance(dt); wait.trains[train_index].state = WAITING; + wait.penalty += 15*Time::sec; + wait.update_estimate(); if(wait.is_viable()) new_steps.push_back(wait); } @@ -573,7 +583,7 @@ void TrainRoutePlanner::RoutingStep::advance(const Time::TimeDelta &dt) void TrainRoutePlanner::RoutingStep::update_estimate() { - cost_estimate = Time::zero; + cost_estimate = penalty; for(vector::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; diff --git a/source/libr2c2/trainrouteplanner.h b/source/libr2c2/trainrouteplanner.h index fa97920..85a748c 100644 --- a/source/libr2c2/trainrouteplanner.h +++ b/source/libr2c2/trainrouteplanner.h @@ -98,6 +98,7 @@ private: struct RoutingStep { Msp::Time::TimeDelta time; + Msp::Time::TimeDelta penalty; Msp::Time::TimeDelta cost_estimate; std::vector trains; const RoutingStep *prev; -- 2.43.0