Start refactoring TrainRoutePlanner

[r2c2.git] / source / libr2c2 / trainrouteplanner.cpp

diff --git a/source/libr2c2/trainrouteplanner.cpp b/source/libr2c2/trainrouteplanner.cpp
index 809bb3e5c665967a9a6d6d890d7eb58f582c6e15..f517afd0fd142785ac83cbfa8240cda2507f2de7 100644 (file)
--- a/source/libr2c2/trainrouteplanner.cpp
+++ b/source/libr2c2/trainrouteplanner.cpp
@@ -40,7 +40,7 @@ void TrainRoutePlanner::plan()
 
                if(update_states(*i))
                {
-                       int next_train = find_next_train(*i);
+                       int next_train = i->find_next_train();
                        if(next_train>=0)
                                add_steps(*i, next_train);
                }
@@ -53,62 +53,16 @@ void TrainRoutePlanner::plan()
 bool TrainRoutePlanner::update_states(RoutingStep &step)
 {
        RoutingStep next(&step);
-       bool changes = false;
-       for(vector<TrainRoutingState>::iterator i=next.trains.begin(); i!=next.trains.end(); ++i)
-       {
-               TrainState old_state = i->state;
-               if(i->state==BLOCKED)
-                       i->state = MOVING;
-
-               TrackIter next_track = i->track.next(i->path);
-               if(!next_track)
-                       return false;
-
-               for(vector<TrainRoutingState>::iterator j=next.trains.begin(); j!=next.trains.end(); ++j)
-                       if(j!=i)
-                       {
-                               if(j->track.track()==next_track.track())
-                               {
-                                       unsigned other_exit = j->track.reverse(j->path).entry();
-                                       if(next_track.entry()==other_exit)
-                                               return false;
-                               }
-                               else if(!j->is_occupied(*next_track))
-                                       continue;
-
-                               i->state = BLOCKED;
-                       }
+       if(!next.update_states())
+               return true;
+       if(next.check_deadlocks())
+               return false;
 
-               if(i->state!=old_state)
-                       changes = true;
-       }
-
-       if(changes)
-       {
-               list<RoutingStep>::iterator i;
-               for(i=steps.begin(); (i!=steps.end() && !(next<*i)); ++i) ;
-               steps.insert(i, next);
-       }
+       list<RoutingStep>::iterator i;
+       for(i=steps.begin(); (i!=steps.end() && !(next<*i)); ++i) ;
+       steps.insert(i, next);
 
-       return !changes;
-}
-
-int TrainRoutePlanner::find_next_train(RoutingStep &step)
-{
-       Time::TimeDelta min_dt;
-       int next_train = -1;
-       for(unsigned i=0; i<step.trains.size(); ++i)
-               if(step.trains[i].state==MOVING)
-               {
-                       Time::TimeDelta dt = step.trains[i].get_time_to_next_track();
-                       if(dt<min_dt || next_train<0)
-                       {
-                               min_dt = dt;
-                               next_train = i;
-                       }
-               }
-
-       return next_train;
+       return false;
 }
 
 void TrainRoutePlanner::add_steps(RoutingStep &step, unsigned train_index)
@@ -143,7 +97,8 @@ void TrainRoutePlanner::add_steps(RoutingStep &step, unsigned train_index)
                        if(next_entry_ep.has_path(i))
                        {
                                next.trains[train_index].path = i;
-                               new_steps.push_back(next);
+                               if(next.is_viable())
+                                       new_steps.push_back(next);
                        }
 
                if(next_entry_ep.paths!=next_track->get_type().get_paths())
@@ -151,7 +106,8 @@ void TrainRoutePlanner::add_steps(RoutingStep &step, unsigned train_index)
                        RoutingStep wait(&step);
                        wait.advance(dt);
                        wait.trains[train_index].state = WAITING;
-                       new_steps.push_back(wait);
+                       if(wait.is_viable())
+                               new_steps.push_back(wait);
                }
        }
 
@@ -239,7 +195,8 @@ TrainRoutePlanner::TrainRoutingState::TrainRoutingState(TrainRoutingInfo &inf):
        occupied_tracks(0),
        state(MOVING),
        delay(info->router->get_departure_delay()),
-       waypoint(info->router->get_n_waypoints() ? 0 : -1)
+       waypoint(info->router->get_n_waypoints() ? 0 : -1),
+       blocked_by(-1)
 {
        const Vehicle *veh = &info->train->get_vehicle(0);
        // TODO margins
@@ -272,7 +229,8 @@ TrainRoutePlanner::TrainRoutingState::TrainRoutingState(const TrainRoutingState
        back_offset(other.back_offset),
        state(other.state),
        delay(other.delay),
-       waypoint(other.waypoint)
+       waypoint(other.waypoint),
+       blocked_by(other.blocked_by)
 {
        ++occupied_tracks->refcount;
 }
@@ -340,6 +298,80 @@ TrainRoutePlanner::RoutingStep::RoutingStep(RoutingStep *p):
        prev(p)
 { }
 
+bool TrainRoutePlanner::RoutingStep::update_states()
+{
+       bool changes = false;
+       for(vector<TrainRoutingState>::iterator i=trains.begin(); i!=trains.end(); ++i)
+       {
+               if(i->state==ARRIVED)
+                       continue;
+
+               TrainState old_state = i->state;
+
+               TrackIter next_track = i->track.next(i->path);
+               if(next_track)
+               {
+                       i->blocked_by = get_occupant(*next_track);
+                       if(i->blocked_by>=0)
+                               i->state = BLOCKED;
+                       else if(i->state==BLOCKED)
+                               i->state = MOVING;
+               }
+               else
+                       i->state = BLOCKED;
+
+               if(i->state!=old_state)
+                       changes = true;
+       }
+
+       return changes;
+}
+
+bool TrainRoutePlanner::RoutingStep::check_deadlocks() const
+{
+       for(unsigned i=0; i<trains.size(); ++i)
+       {
+               const TrainRoutingState &train = trains[i];
+               if(train.state!=BLOCKED)
+                       continue;
+
+               if(train.blocked_by<0)
+                       return true;
+
+               if(trains[train.blocked_by].blocked_by==static_cast<int>(i))
+                       return true;
+       }
+
+       return false;
+}
+
+int TrainRoutePlanner::RoutingStep::get_occupant(Track &track) const
+{
+       for(unsigned i=0; i<trains.size(); ++i)
+               if(trains[i].is_occupied(track))
+                       return i;
+
+       return -1;
+}
+
+int TrainRoutePlanner::RoutingStep::find_next_train() const
+{
+       Time::TimeDelta min_dt;
+       int next_train = -1;
+       for(unsigned i=0; i<trains.size(); ++i)
+               if(trains[i].state==MOVING)
+               {
+                       Time::TimeDelta dt = trains[i].get_time_to_next_track();
+                       if(dt<min_dt || next_train<0)
+                       {
+                               min_dt = dt;
+                               next_train = i;
+                       }
+               }
+
+       return next_train;
+}
+
 void TrainRoutePlanner::RoutingStep::advance(const Time::TimeDelta &dt)
 {
        time += dt;
@@ -357,6 +389,15 @@ void TrainRoutePlanner::RoutingStep::advance(const Time::TimeDelta &dt)
        }
 }
 
+bool TrainRoutePlanner::RoutingStep::is_viable() const
+{
+       for(vector<TrainRoutingState>::const_iterator i=trains.begin(); i!=trains.end(); ++i)
+               if(i->state==MOVING)
+                       return true;
+
+       return false;
+}
+
 bool TrainRoutePlanner::RoutingStep::is_goal() const
 {
        for(vector<TrainRoutingState>::const_iterator i=trains.begin(); i!=trains.end(); ++i)