+void TrainRoutePlanner::RoutingStep::create_successors(list<RoutingStep> &new_steps) const
+{
+ RoutingStep next(this);
+ if(next.update_states() && next.check_deadlocks())
+ return;
+
+ int train_index = find_next_train();
+ if(train_index<0)
+ return;
+
+ TrainRoutingState &train = next.trains[train_index];
+
+ Time::TimeDelta dt = train.get_time_to_next_track();
+ next.advance(dt);
+
+ /* Check arrival after the train has advanced to the end of its current track
+ so travel time and occupied tracks will be correct. */
+ if(train.check_arrival())
+ {
+ new_steps.push_back(next);
+ return;
+ }
+
+ 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)
+ {
+ /* Only create a successor step matching the currently set path for a
+ critical track. */
+ unsigned critical_path = train.track->get_type().coerce_path(train.track.entry(), train.track->get_active_path());
+ create_successor(next, train_index, critical_path, new_steps);
+ }
+ else
+ {
+ // Create successor steps for all possible paths through the new track.
+ for(unsigned i=0; entry_ep.paths>>i; ++i)
+ if(entry_ep.has_path(i))
+ create_successor(next, train_index, i, new_steps);
+ }
+
+ 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
+ that doesn't pass through the entry endpoint. */
+ RoutingStep wait(this);
+ wait.advance(dt);
+ wait.trains[train_index].state = WAITING;
+
+ Time::TimeDelta estimated_wait = Time::day;
+ for(unsigned i=0; i<wait.trains.size(); ++i)
+ if(i!=static_cast<unsigned>(train_index) && wait.trains[i].state!=ARRIVED)
+ {
+ Time::TimeDelta ttp = wait.trains[i].get_time_to_pass(*train.track);
+ estimated_wait = min(estimated_wait, ttp);
+ }
+ wait.trains[train_index].estimated_wait = estimated_wait;
+
+ wait.update_estimate();
+ if(wait.is_viable())
+ new_steps.push_back(wait);
+ }
+}
+
+void TrainRoutePlanner::RoutingStep::create_successor(RoutingStep &next, unsigned train_index, unsigned path, list<RoutingStep> &new_steps)
+{
+ TrainRoutingState &train = next.trains[train_index];
+
+ train.set_path(path);
+ next.update_estimate();
+ if(next.is_viable())
+ new_steps.push_back(next);
+}
+
+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)
+ {
+ /* If the train is still traversing its last critical track, the
+ flag needs to be cleared here to pass viability test. */
+ 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;
+ }
+ else if(i->state==BLOCKED)
+ {
+ i->estimated_wait = Time::zero;
+ i->state = MOVING;
+ }
+ }
+ else
+ i->state = BLOCKED;
+
+ if(i->state!=old_state)
+ changes = true;
+ }
+
+ return changes;
+}
+
+bool TrainRoutePlanner::RoutingStep::check_deadlocks() const
+{
+ for(vector<TrainRoutingState>::const_iterator i=trains.begin(); i!=trains.end(); ++i)
+ {
+ if(i->state!=BLOCKED)
+ continue;
+
+ // A train blocked by end of track is always considered a deadlock.
+ if(i->blocked_by<0)
+ return true;
+
+ /* Use the tortoise and hare algorithm to check if trains are blocked
+ cyclically (A blocks B, which blocks ..., which blocks A). */
+ int slow = i->blocked_by;
+ int fast = trains[slow].blocked_by;
+ while(fast>=0 && trains[fast].blocked_by>=0)
+ {
+ if(fast==slow)
+ return true;
+
+ slow = trains[slow].blocked_by;
+ fast = trains[trains[fast].blocked_by].blocked_by;
+ }
+ }
+
+ return false;
+}
+
+int TrainRoutePlanner::RoutingStep::get_occupant(Track &track) const
+{
+ for(unsigned i=0; i<trains.size(); ++i)
+ if(trains[i].is_occupying(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;
+}
+