From: Mikko Rasa <tdb@tdb.fi>
Date: Mon, 23 Feb 2015 10:17:27 +0000 (+0200)
Subject: Follow the same path until another is significantly better
X-Git-Url: http://git.tdb.fi/?p=r2c2.git;a=commitdiff_plain;h=cac4176a9685e8b39147d1e18d969b3bee052b03

Follow the same path until another is significantly better

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.
---

diff --git a/source/libr2c2/trainrouteplanner.cpp b/source/libr2c2/trainrouteplanner.cpp
index e42e618..d9eedd2 100644
--- a/source/libr2c2/trainrouteplanner.cpp
+++ b/source/libr2c2/trainrouteplanner.cpp
@@ -16,6 +16,7 @@ namespace R2C2 {
 
 TrainRoutePlanner::TrainRoutePlanner(Layout &layout):
 	goal(0),
+	path_switch_bias(15*Time::sec),
 	timeout(10*Time::sec),
 	result(PENDING),
 	thread(0)
@@ -147,7 +148,12 @@ void TrainRoutePlanner::add_steps(const RoutingStep &step)
 {
 	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);
 }
 
@@ -518,13 +524,14 @@ 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)
 { }
@@ -570,13 +577,6 @@ void TrainRoutePlanner::RoutingStep::create_successors(list<RoutingStep> &new_st
 				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
@@ -719,7 +719,7 @@ void TrainRoutePlanner::RoutingStep::advance(const Time::TimeDelta &dt)
 
 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;
@@ -748,6 +748,8 @@ bool TrainRoutePlanner::RoutingStep::is_goal() const
 
 bool TrainRoutePlanner::RoutingStep::operator<(const RoutingStep &other) const
 {
+	if(preferred!=other.preferred)
+		return preferred>other.preferred;
 	return cost_estimate<other.cost_estimate;
 }
 
diff --git a/source/libr2c2/trainrouteplanner.h b/source/libr2c2/trainrouteplanner.h
index 79a6036..32c9dad 100644
--- a/source/libr2c2/trainrouteplanner.h
+++ b/source/libr2c2/trainrouteplanner.h
@@ -103,8 +103,8 @@ private:
 	struct RoutingStep
 	{
 		Msp::Time::TimeDelta time;
-		Msp::Time::TimeDelta penalty;
 		Msp::Time::TimeDelta cost_estimate;
+		bool preferred;
 		std::vector<TrainRoutingState> trains;
 		const RoutingStep *prev;
 
@@ -141,6 +141,7 @@ private:
 	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;