From 279f10b0dffc4b207b7998ac2761514b80d57780 Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Sat, 21 Feb 2015 00:46:46 +0200 Subject: [PATCH] Sprinkle some comments on the routing system --- source/libr2c2/trainroutemetric.cpp | 6 ++++++ source/libr2c2/trainrouteplanner.cpp | 28 ++++++++++++++++++++++++++++ 2 files changed, 34 insertions(+) diff --git a/source/libr2c2/trainroutemetric.cpp b/source/libr2c2/trainroutemetric.cpp index 7e4d485..469fc94 100644 --- a/source/libr2c2/trainroutemetric.cpp +++ b/source/libr2c2/trainroutemetric.cpp @@ -9,6 +9,9 @@ namespace R2C2 { TrainRouteMetric::TrainRouteMetric(const TrackChain &tc, TrackChain::Direction dir) { + /* Initialize goals for tracks in the target chain. We travel outwards from + the target in the search phase so the iters appear to point the wrong way. */ + TrackChain::Direction reverse_dir = (dir==TrackChain::DOWN ? TrackChain::UP : TrackChain::DOWN); const TrackChain::TrackSet &ctracks = tc.get_tracks(); for(TrackChain::TrackSet::const_iterator i=ctracks.begin(); i!=ctracks.end(); ++i) { @@ -31,6 +34,9 @@ TrainRouteMetric::TrainRouteMetric(const TrackChain &tc, TrackChain::Direction d queue.push_back(i->track); } + /* Use Dijkstra's algorithm to find the shortest distance from the goal to + every reachable track in the layout. Entry points here become exit points + when looking up distances to the goal. */ while(!queue.empty()) { TrackIter track = queue.front(); diff --git a/source/libr2c2/trainrouteplanner.cpp b/source/libr2c2/trainrouteplanner.cpp index 4186f47..7d1b0c2 100644 --- a/source/libr2c2/trainrouteplanner.cpp +++ b/source/libr2c2/trainrouteplanner.cpp @@ -167,6 +167,7 @@ void TrainRoutePlanner::finalize_plan() for(vector::const_iterator j=i->trains.begin(); j!=i->trains.end(); ++j) { Track **history = j->info->track_history; + // Don't process the same track again. if(j->track.track()==history[0]) continue; @@ -174,6 +175,8 @@ void TrainRoutePlanner::finalize_plan() bool start_new_route = true; if(!j->info->routes.empty()) { + /* If we already have a route and this track or any linked track is + in it, start a new one to avoid loops. */ route = j->info->routes.front(); start_new_route = route->has_track(*j->track); if(!start_new_route) @@ -192,6 +195,8 @@ void TrainRoutePlanner::finalize_plan() route = new Route(j->info->train->get_layout()); route->set_name("Router"); route->set_temporary(true); + /* Have the routes overlap by two tracks to ensure that turnout + paths can be deduced. */ for(unsigned k=0; (k<2 && history[k]); ++k) route->add_track(*history[k]); j->info->routes.push_front(route); @@ -205,6 +210,7 @@ void TrainRoutePlanner::finalize_plan() map::iterator k = sequenced_tracks.find(j->track.track()); if(k!=sequenced_tracks.end()) { + // Add a sequence point if another train uses this track afterwards. if(!k->second->preceding_train) { k->second->preceding_train = j->info->train; @@ -217,6 +223,8 @@ void TrainRoutePlanner::finalize_plan() } else if(waitable) { + /* Create a sequence point if it's possible to wait and let another + train past. */ j->info->sequence.push_front(TrainRouter::SequencePoint(j->track->get_block(), sequence)); sequenced_tracks[j->track.track()] = &j->info->sequence.front(); --sequence; @@ -362,6 +370,7 @@ bool TrainRoutePlanner::TrainRoutingState::check_arrival() { TrackIter next_track = track.next(path); + // Check if we're about the exit the current waypoint's tracks. const TrainRouter::Waypoint &wp = info->waypoints[waypoint]; if(wp.chain->has_track(*track) && !wp.chain->has_track(*next_track)) if(wp.direction==TrackChain::UNSPECIFIED || track==wp.chain->iter_for(*track, wp.direction)) @@ -375,6 +384,7 @@ bool TrainRoutePlanner::TrainRoutingState::check_arrival() } } + // If we're entering the first non-critical block, clear the critical flag. if(info->first_noncritical->has_track(*next_track)) critical = false; @@ -386,6 +396,7 @@ void TrainRoutePlanner::TrainRoutingState::advance(float distance) offset += distance; back_offset += distance; + // See if the tail end of the train has passed any sensors. unsigned count_to_free = 0; unsigned last_sensor_addr = 0; float distance_after_sensor = 0; @@ -408,6 +419,7 @@ void TrainRoutePlanner::TrainRoutingState::advance(float distance) occ = occ->next; } + // Free the last passed sensor and any tracks behind it. if(count_to_free && back_offset>distance_after_sensor) { back_offset -= distance_after_sensor; @@ -432,6 +444,7 @@ void TrainRoutePlanner::TrainRoutingState::advance(const Time::TimeDelta &dt) } float secs = dt/Time::sec; + // There may be negative delay remaining after previous step. if(delay) { secs -= delay/Time::sec; @@ -502,6 +515,8 @@ void TrainRoutePlanner::RoutingStep::create_successors(list &new_st 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); @@ -513,11 +528,14 @@ void TrainRoutePlanner::RoutingStep::create_successors(list &new_st 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); @@ -532,6 +550,8 @@ void TrainRoutePlanner::RoutingStep::create_successors(list &new_st 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; @@ -569,8 +589,13 @@ bool TrainRoutePlanner::RoutingStep::update_states() 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; + + /* 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) @@ -593,9 +618,12 @@ bool TrainRoutePlanner::RoutingStep::check_deadlocks() const 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) -- 2.45.2