X-Git-Url: http://git.tdb.fi/?a=blobdiff_plain;f=source%2Flibr2c2%2Ftrainrouteplanner.cpp;h=c115d924bed8e0603436c0705a0a4bd46deab364;hb=19274ec3b805af126e562c805e0c14baa14c5833;hp=809bb3e5c665967a9a6d6d890d7eb58f582c6e15;hpb=055d7e80b68c8f77ebf226ffd48c37a7e504940c;p=r2c2.git diff --git a/source/libr2c2/trainrouteplanner.cpp b/source/libr2c2/trainrouteplanner.cpp index 809bb3e..c115d92 100644 --- a/source/libr2c2/trainrouteplanner.cpp +++ b/source/libr2c2/trainrouteplanner.cpp @@ -38,123 +38,17 @@ void TrainRoutePlanner::plan() break; } - if(update_states(*i)) - { - int next_train = find_next_train(*i); - if(next_train>=0) - add_steps(*i, next_train); - } + add_steps(*i); } if(goal) create_routes(*goal); } -bool TrainRoutePlanner::update_states(RoutingStep &step) -{ - RoutingStep next(&step); - bool changes = false; - for(vector::iterator i=next.trains.begin(); i!=next.trains.end(); ++i) - { - TrainState old_state = i->state; - if(i->state==BLOCKED) - i->state = MOVING; - - TrackIter next_track = i->track.next(i->path); - if(!next_track) - return false; - - for(vector::iterator j=next.trains.begin(); j!=next.trains.end(); ++j) - if(j!=i) - { - if(j->track.track()==next_track.track()) - { - unsigned other_exit = j->track.reverse(j->path).entry(); - if(next_track.entry()==other_exit) - return false; - } - else if(!j->is_occupied(*next_track)) - continue; - - i->state = BLOCKED; - } - - if(i->state!=old_state) - changes = true; - } - - if(changes) - { - list::iterator i; - for(i=steps.begin(); (i!=steps.end() && !(next<*i)); ++i) ; - steps.insert(i, next); - } - - return !changes; -} - -int TrainRoutePlanner::find_next_train(RoutingStep &step) -{ - Time::TimeDelta min_dt; - int next_train = -1; - for(unsigned i=0; i 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; - 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; - new_steps.push_back(wait); - } - } - + step.create_successors(new_steps); new_steps.sort(); steps.merge(new_steps); } @@ -239,7 +133,8 @@ TrainRoutePlanner::TrainRoutingState::TrainRoutingState(TrainRoutingInfo &inf): occupied_tracks(0), state(MOVING), delay(info->router->get_departure_delay()), - waypoint(info->router->get_n_waypoints() ? 0 : -1) + waypoint(info->router->get_n_waypoints() ? 0 : -1), + blocked_by(-1) { const Vehicle *veh = &info->train->get_vehicle(0); // TODO margins @@ -272,7 +167,8 @@ TrainRoutePlanner::TrainRoutingState::TrainRoutingState(const TrainRoutingState back_offset(other.back_offset), state(other.state), delay(other.delay), - waypoint(other.waypoint) + waypoint(other.waypoint), + blocked_by(other.blocked_by) { ++occupied_tracks->refcount; } @@ -297,6 +193,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; @@ -340,6 +256,129 @@ TrainRoutePlanner::RoutingStep::RoutingStep(RoutingStep *p): prev(p) { } +void TrainRoutePlanner::RoutingStep::create_successors(list &new_steps) +{ + 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; + for(vector::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(unsigned i=0; i(i)) + return true; + } + + return false; +} + +int TrainRoutePlanner::RoutingStep::get_occupant(Track &track) const +{ + for(unsigned i=0; i::const_iterator i=trains.begin(); i!=trains.end(); ++i) + if(i->state==MOVING) + return true; + + return false; +} + bool TrainRoutePlanner::RoutingStep::is_goal() const { for(vector::const_iterator i=trains.begin(); i!=trains.end(); ++i)