+void TrainRoutePlanner::RoutingStep::create_successors(list<RoutingStep> &new_steps) const
+{
+ RoutingStep next(this);
+ if(next.update_states())
+ {
+ if(next.check_deadlocks())
+ return;
+
+ new_steps.push_back(next);
+ 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);
+
+ if(train.check_arrival())
+ {
+ new_steps.push_back(next);
+ return;
+ }
+
+ TrackIter next_track = train.track.next(train.path);
+ train.advance_track(0);
+
+ const TrackType::Endpoint &next_entry_ep = next_track.endpoint();
+ for(unsigned i=0; next_entry_ep.paths>>i; ++i)
+ if(next_entry_ep.has_path(i))
+ {
+ train.path = i;
+ train.update_estimate();
+ next.update_estimate();
+ if(next.is_viable())
+ new_steps.push_back(next);
+ }
+
+ if(next_entry_ep.paths!=next_track->get_type().get_paths())
+ {
+ RoutingStep wait(this);
+ wait.advance(dt);
+ wait.trains[train_index].state = WAITING;
+ if(wait.is_viable())
+ new_steps.push_back(wait);
+ }
+}
+
+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(vector<TrainRoutingState>::const_iterator i=trains.begin(); i!=trains.end(); ++i)
+ {
+ if(i->state!=BLOCKED)
+ continue;
+
+ if(i->blocked_by<0)
+ return true;
+
+ 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;
+}
+