+ 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;