X-Git-Url: http://git.tdb.fi/?a=blobdiff_plain;f=source%2Flibr2c2%2Ftrainrouteplanner.cpp;h=22ac5400ea4fb050437ccdff14de77dbafc483e9;hb=b42a312323d36775ab550630b3ee818c3b948bf6;hp=f517afd0fd142785ac83cbfa8240cda2507f2de7;hpb=8c31771a3252f3717ce53fd33567c74003c7cd1a;p=r2c2.git diff --git a/source/libr2c2/trainrouteplanner.cpp b/source/libr2c2/trainrouteplanner.cpp index f517afd..22ac540 100644 --- a/source/libr2c2/trainrouteplanner.cpp +++ b/source/libr2c2/trainrouteplanner.cpp @@ -21,101 +21,47 @@ TrainRoutePlanner::TrainRoutePlanner(Layout &layout) routed_trains.push_back(info); } - steps.push_back(RoutingStep()); - RoutingStep &start = steps.back(); + queue.push_back(RoutingStep()); + RoutingStep &start = queue.back(); for(vector::iterator i=routed_trains.begin(); i!=routed_trains.end(); ++i) start.trains.push_back(TrainRoutingState(*i)); + start.update_estimate(); } void TrainRoutePlanner::plan() { - RoutingStep *goal = 0; - for(list::iterator i=steps.begin(); i!=steps.end(); ++i) + const RoutingStep *goal = 0; + while(!queue.empty()) { - if(i->is_goal()) + const RoutingStep &step = get_step(); + if(step.is_goal()) { - goal = &*i; + goal = &step; break; } - if(update_states(*i)) - { - int next_train = i->find_next_train(); - if(next_train>=0) - add_steps(*i, next_train); - } + add_steps(step); } if(goal) create_routes(*goal); } -bool TrainRoutePlanner::update_states(RoutingStep &step) +const TrainRoutePlanner::RoutingStep &TrainRoutePlanner::get_step() { - RoutingStep next(&step); - if(!next.update_states()) - return true; - if(next.check_deadlocks()) - return false; - - list::iterator i; - for(i=steps.begin(); (i!=steps.end() && !(next<*i)); ++i) ; - steps.insert(i, next); - - return false; + steps.splice(steps.end(), queue, queue.begin()); + return steps.back(); } -void TrainRoutePlanner::add_steps(RoutingStep &step, unsigned train_index) +void TrainRoutePlanner::add_steps(const RoutingStep &step) { - TrainRoutingState &train = step.trains[train_index]; - Time::TimeDelta dt = train.get_time_to_next_track(); - TrackIter next_track = train.track.next(train.path); - list new_steps; - - RoutingStep next(&step); - next.advance(dt); - TrainRouter &router = *train.info->router; - if(train.waypoint<0 && router.is_destination(*train.track) && !router.is_destination(*next_track)) - { - next.trains[train_index].state = ARRIVED; - new_steps.push_back(next); - } - else - { - if(train.waypoint>=0 && router.is_waypoint(train.waypoint, *train.track) && !router.is_waypoint(train.waypoint, *next_track)) - { - ++next.trains[train_index].waypoint; - if(next.trains[train_index].waypoint>=static_cast(router.get_n_waypoints())) - next.trains[train_index].waypoint = -1; - } - - next.trains[train_index].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)) - { - next.trains[train_index].path = i; - if(next.is_viable()) - new_steps.push_back(next); - } - - if(next_entry_ep.paths!=next_track->get_type().get_paths()) - { - RoutingStep wait(&step); - wait.advance(dt); - wait.trains[train_index].state = WAITING; - if(wait.is_viable()) - new_steps.push_back(wait); - } - } - + step.create_successors(new_steps); new_steps.sort(); - steps.merge(new_steps); + queue.merge(new_steps); } -void TrainRoutePlanner::create_routes(RoutingStep &goal) +void TrainRoutePlanner::create_routes(const RoutingStep &goal) { for(vector::iterator i=routed_trains.begin(); i!=routed_trains.end(); ++i) { @@ -124,9 +70,9 @@ void TrainRoutePlanner::create_routes(RoutingStep &goal) i->route->set_temporary(true); } - for(RoutingStep *i=&goal; i; i=i->prev) + for(const RoutingStep *i=&goal; i; i=i->prev) { - for(vector::iterator j=i->trains.begin(); j!=i->trains.end(); ++j) + for(vector::const_iterator j=i->trains.begin(); j!=i->trains.end(); ++j) { if(j->state==WAITING || j->state==BLOCKED) j->info->waits.push_front(&*j); @@ -137,8 +83,8 @@ void TrainRoutePlanner::create_routes(RoutingStep &goal) for(vector::iterator i=routed_trains.begin(); i!=routed_trains.end(); ++i) { i->router->set_route(i->route); - TrainRoutingState *current_wait = 0; - for(list::iterator j=i->waits.begin(); j!=i->waits.end(); ++j) + const TrainRoutingState *current_wait = 0; + for(list::const_iterator j=i->waits.begin(); j!=i->waits.end(); ++j) if(!current_wait || (*j)->track.track()!=current_wait->track.track()) { Block &block = (*j)->track.next()->get_block(); @@ -237,7 +183,7 @@ TrainRoutePlanner::TrainRoutingState::TrainRoutingState(const TrainRoutingState TrainRoutePlanner::TrainRoutingState::~TrainRoutingState() { - if(!--occupied_tracks->refcount) + if(occupied_tracks && !--occupied_tracks->refcount) delete occupied_tracks; } @@ -246,7 +192,7 @@ Time::TimeDelta TrainRoutePlanner::TrainRoutingState::get_time_to_next_track() c return ((track->get_type().get_path_length(path)-offset)/info->speed)*Time::sec+delay; } -bool TrainRoutePlanner::TrainRoutingState::is_occupied(Track &trk) const +bool TrainRoutePlanner::TrainRoutingState::is_occupying(Track &trk) const { OccupiedTrack *occ = occupied_tracks; for(unsigned n=occ->n_tracks; n>0; --n, occ=occ->next) @@ -255,6 +201,26 @@ bool TrainRoutePlanner::TrainRoutingState::is_occupied(Track &trk) const return false; } +bool TrainRoutePlanner::TrainRoutingState::check_arrival() +{ + TrainRouter &router = *info->router; + TrackIter next_track = track.next(path); + + if(waypoint<0 && router.is_destination(*track) && !router.is_destination(*next_track)) + { + state = ARRIVED; + return true; + } + else if(waypoint>=0 && router.is_waypoint(waypoint, *track) && !router.is_waypoint(waypoint, *next_track)) + { + ++waypoint; + if(waypoint>=static_cast(router.get_n_waypoints())) + waypoint = -1; + } + + return false; +} + void TrainRoutePlanner::TrainRoutingState::advance(float distance) { offset += distance; @@ -292,12 +258,61 @@ TrainRoutePlanner::RoutingStep::RoutingStep(): prev(0) { } -TrainRoutePlanner::RoutingStep::RoutingStep(RoutingStep *p): +TrainRoutePlanner::RoutingStep::RoutingStep(const RoutingStep *p): time(p->time), trains(p->trains), prev(p) { } +void TrainRoutePlanner::RoutingStep::create_successors(list &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; + 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; @@ -329,17 +344,24 @@ bool TrainRoutePlanner::RoutingStep::update_states() bool TrainRoutePlanner::RoutingStep::check_deadlocks() const { - for(unsigned i=0; i::const_iterator i=trains.begin(); i!=trains.end(); ++i) { - const TrainRoutingState &train = trains[i]; - if(train.state!=BLOCKED) + if(i->state!=BLOCKED) continue; - if(train.blocked_by<0) + if(i->blocked_by<0) return true; - if(trains[train.blocked_by].blocked_by==static_cast(i)) - 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; @@ -348,7 +370,7 @@ bool TrainRoutePlanner::RoutingStep::check_deadlocks() const int TrainRoutePlanner::RoutingStep::get_occupant(Track &track) const { for(unsigned i=0; i