diff --git a/simutrans/trunk/boden/wege/runway.cc b/simutrans/trunk/boden/wege/runway.cc index 995dc69..9399a5a 100644 --- a/simutrans/trunk/boden/wege/runway.cc +++ b/simutrans/trunk/boden/wege/runway.cc @@ -56,3 +56,164 @@ void runway_t::rdwr(loadsave_t *file) set_desc(desc); } } + +/** +* True, if there are no reservations of other convoys scheduled for the given period. +*/ +bool runway_t::can_schedule_reservation(const reservation_schedule_item_t& item) const +{ + for (reservation_schedule_t::const_iterator i = reservations.begin(); i != reservations.end(); ++i) + { + if (item.convoy == i->convoy || !i->convoy.is_bound()) + // ignore my own and stale reservations + continue; + + if (item.departure <= i->arrival) + { + // can insert before this reservation + return true; + } + if (item.arrival < i->departure) + { + // intersects this reservation + return false; + } + } + return true; +} + +/** +* Schedule reservation no matter if there are concurrent reservations. +* All other reservations of the convoy for this way are removed before the new reservation is inserted. +*/ +void runway_t::schedule_reservation(const reservation_schedule_item_t & item) +{ + // iterate through complete schedule to + // - remove existing items of the convoy, + // - remove items of stale convoys and + // - insert given item before the first item scheduled for a later time. + reservation_schedule_t::iterator i = reservations.begin(); + + // loop part 1: (terminates at end() or the first *i scheduled for a later time than item) + while (i != reservations.end() && *i < item) + if (i->convoy == item.convoy || !i->convoy.is_bound()) + // remove previous or stale reservation + i = reservations.erase(i); + else + ++i; + + // insert item before *i (appends if i == end()). + i = reservations.insert(i, item); + ++i; + + // loop part 2: continue loop until end() + while (i != reservations.end()) + if (i->convoy == item.convoy || !i->convoy.is_bound()) + // remove previous or stale reservation + i = reservations.erase(i); + else + ++i; +} + +/** +* Get reservation of given convoy. +* @author B.Gabriel +*/ +const reservation_schedule_item_t * runway_t::get_reservation_of(const convoihandle_t & convoy) +{ + if (!reservations.empty()) + for (reservation_schedule_t::iterator i = reservations.begin(); i != reservations.end(); ++i) + if (i->convoy == convoy) + return &*i; + return NULL; +} + +/** +* Remove all reservations of given convoy. +* @author B.Gabriel +*/ +void runway_t::remove_reservations(const convoihandle_t & convoy) +{ + if (!reservations.empty()) + for (reservation_schedule_t::iterator i = reservations.begin(); i != reservations.end(); ) + { + if (i->convoy == convoy || !i->convoy.is_bound()) + // remove previous or stale reservation + i = reservations.erase(i); + else + ++i; + } +} + +bool runway_t::can_reserve(convoihandle_t c) const +{ + if (reserved.is_bound()) + return c == reserved; + + if (!reservations.empty()) + { + // c can reserve only, if c is late or is scheduled for now or no other convoy is scheduled for now. + + uint32 now = welt->get_ticks(); + for (reservation_schedule_t::const_iterator i = reservations.begin(); i != reservations.end(); ++i) + { + if (!i->convoy.is_bound()) + // ignore reservations of stale convoys + continue; + + if (i->convoy == c) + // c's reservation. c can reserve. + break; + + if (now < i->arrival) + // first entry in the future. c can reserve. + break; + + if (now < i->departure) + // another convoy's reservation at now. c must not reserve. + return false; + } + } + return true; +} + +bool runway_t::reserve(convoihandle_t c, ribi_t::ribi dir) +{ + if (can_reserve(c)) { + reserved = c; + + // remove from schedule + remove_reservations(c); + + /* for threeway and fourway switches we may need to alter graphic, if + * direction is a diagonal (i.e. on the switching part) + * and there are switching graphics + */ + if (ribi_t::is_threeway(get_ribi_unmasked()) && ribi_t::is_bend(dir) && get_desc()->has_switch_image()) { + mark_image_dirty(get_image(), 0); + mark_image_dirty(get_front_image(), 0); + set_images(image_switch, get_ribi_unmasked(), is_snow(), (dir == ribi_t::northeast || dir == ribi_t::southwest)); + set_flag(obj_t::dirty); + } + if (schiene_t::show_reservations) { + set_flag(obj_t::dirty); + } + return true; + } + // reserve anyway ... + return false; +} + +bool runway_t::unreserve(convoihandle_t c) +{ + // is this tile reserved by us? + remove_reservations(c); + if (reserved.is_bound() && reserved == c) { + reserved = convoihandle_t(); + if (schiene_t::show_reservations) { + set_flag(obj_t::dirty); + } + return true; + } + return false; +} diff --git a/simutrans/trunk/boden/wege/runway.h b/simutrans/trunk/boden/wege/runway.h index e9a8979..0fd22fd 100644 --- a/simutrans/trunk/boden/wege/runway.h +++ b/simutrans/trunk/boden/wege/runway.h @@ -10,6 +10,60 @@ #include "schiene.h" +#include "../../tpl/vector_tpl.h" + +struct reservation_schedule_item_t +{ + convoihandle_t convoy; + uint32 arrival; // in ticks + uint32 departure; // in ticks + + reservation_schedule_item_t() + : arrival(0) + , departure(0) + {} + + reservation_schedule_item_t( + const convoihandle_t& convoy, + uint32 arrival, + uint32 departure) + : convoy(convoy) + , arrival(arrival) + , departure(departure) + {} + + bool operator < (const reservation_schedule_item_t& that) const + { + if (arrival < that.arrival) + return true; + if (arrival == that.arrival) + return departure < that.departure; + return false; + } +}; + +/** +* A list of convoys that intend to use the way at a given time period. +* The list is build by schedule_reservation() sorted by operator < of the items. +* +* Reservation scheduling avoids air traffic congestion: +* air_vehicle::get_cost() penalises use of reserved runways with high costs. +* Thus alterative runways are preferred. +*/ +class reservation_schedule_t : public vector_tpl +{ +public: + + /** insert data at a certain pos */ + iterator insert(const iterator& i, const reservation_schedule_item_t& elem) + { + uint32 pos = i - begin(); + insert_at(pos, elem); + return begin() + pos; + } +}; + +//BG, 03-Oct-2017: end of insertions for reservation scheduling avoids air traffic congestion. /** @@ -20,6 +74,7 @@ */ class runway_t : public schiene_t { + reservation_schedule_t reservations; public: static const way_desc_t *default_runway; @@ -35,6 +90,47 @@ public: inline waytype_t get_waytype() const {return air_wt;} void rdwr(loadsave_t *file); + + /** + * True, if there are no reservations of other convoys scheduled for the given period. + */ + bool can_schedule_reservation(const reservation_schedule_item_t & item) const; + + /** + * Schedule reservation no matter if there are concurrent reservations. + * All other reservations of the convoy for this way are removed before the new reservation is inserted. + */ + void schedule_reservation(const reservation_schedule_item_t & item); + + /** + * Get reservation of given convoy: + */ + const reservation_schedule_item_t* get_reservation_of(const convoihandle_t& convoy); + + /** + * Remove all reservations of this convoy. + */ + void remove_reservations(const convoihandle_t& convoy); + + /** + * Get reservation schedule. + */ + const reservation_schedule_t& get_reservations() const { return reservations; } + + /** + * True, if this rail can be reserved. + */ + bool can_reserve(convoihandle_t c) const; + + /** + * True, if this rail has been reserved. + */ + bool reserve(convoihandle_t c, ribi_t::ribi dir); + + /** + * Releases all reservations of given convoy. + */ + bool unreserve(convoihandle_t c); }; #endif diff --git a/simutrans/trunk/boden/wege/schiene.cc b/simutrans/trunk/boden/wege/schiene.cc index 5466afc..cf90f2f 100644 --- a/simutrans/trunk/boden/wege/schiene.cc +++ b/simutrans/trunk/boden/wege/schiene.cc @@ -68,6 +68,10 @@ void schiene_t::info(cbuffer_t & buf) const } } +bool schiene_t::can_reserve(convoihandle_t c) const +{ + return !reserved.is_bound() || c == reserved; +} /** * true, if this rail can be reserved @@ -77,6 +81,7 @@ bool schiene_t::reserve(convoihandle_t c, ribi_t::ribi dir ) { if(can_reserve(c)) { reserved = c; + /* for threeway and fourway switches we may need to alter graphic, if * direction is a diagonal (i.e. on the switching part) * and there are switching graphics @@ -122,20 +127,20 @@ bool schiene_t::unreserve(convoihandle_t c) * releases previous reservation * @author prissi */ -bool schiene_t::unreserve(vehicle_t *) +bool schiene_t::unreserve(vehicle_t *v) { // is this tile empty? if(!reserved.is_bound()) { return true; } -// if(!welt->lookup(get_pos())->suche_obj(v->get_typ())) { + if (reserved.get_rep() == v->get_convoi()) { reserved = convoihandle_t(); if(schiene_t::show_reservations) { set_flag( obj_t::dirty ); } return true; -// } -// return false; + } + return false; } diff --git a/simutrans/trunk/boden/wege/schiene.h b/simutrans/trunk/boden/wege/schiene.h index 216ff49..bbb4ff4 100644 --- a/simutrans/trunk/boden/wege/schiene.h +++ b/simutrans/trunk/boden/wege/schiene.h @@ -29,7 +29,6 @@ protected: * @author prissi */ convoihandle_t reserved; - public: static const way_desc_t *default_schiene; @@ -55,7 +54,7 @@ public: * true, if this rail can be reserved * @author prissi */ - bool can_reserve(convoihandle_t c) const { return !reserved.is_bound() || c==reserved; } + bool can_reserve(convoihandle_t c) const; /** * true, if this rail can be reserved diff --git a/simutrans/trunk/simworld.cc b/simutrans/trunk/simworld.cc index 3c7807a..b506901 100644 --- a/simutrans/trunk/simworld.cc +++ b/simutrans/trunk/simworld.cc @@ -3456,6 +3456,7 @@ void karte_t::sync_list_t::clear() list.clear(); currently_deleting = NULL; sync_step_running = false; + round_robin = 0; } void karte_t::sync_list_t::sync_step(uint32 delta_t) @@ -3463,8 +3464,9 @@ void karte_t::sync_list_t::sync_step(uint32 delta_t) sync_step_running = true; currently_deleting = NULL; - for(uint32 i=0; isync_step(delta_t)) { case SYNC_OK: break; @@ -3475,11 +3477,13 @@ void karte_t::sync_list_t::sync_step(uint32 delta_t) /* fall-through */ case SYNC_REMOVE: ss = list.pop_back(); - if (i < list.get_count()) { - list[i] = ss; + if (j < list.get_count()) { + list[j] = ss; } } } + if (list.get_count()) + round_robin = (round_robin + 1) % list.get_count(); sync_step_running = false; } diff --git a/simutrans/trunk/simworld.h b/simutrans/trunk/simworld.h index e215f6f..5707506 100644 --- a/simutrans/trunk/simworld.h +++ b/simutrans/trunk/simworld.h @@ -1547,7 +1547,7 @@ public: class sync_list_t { friend class karte_t; public: - sync_list_t() : currently_deleting(NULL), sync_step_running(false) {} + sync_list_t() : currently_deleting(NULL), sync_step_running(false), round_robin(0) {} void add(sync_steppable *obj); void remove(sync_steppable *obj); private: @@ -1558,6 +1558,7 @@ public: vector_tpl list; ///< list of sync-steppable objects sync_steppable* currently_deleting; ///< deleted durign sync_step, safeguard calls to remove bool sync_step_running; + uint32 round_robin; }; sync_list_t sync; ///< vehicles, transformers, traffic lights diff --git a/simutrans/trunk/vehicle/simvehicle.cc b/simutrans/trunk/vehicle/simvehicle.cc index 8dd54b2..a473acb 100644 --- a/simutrans/trunk/vehicle/simvehicle.cc +++ b/simutrans/trunk/vehicle/simvehicle.cc @@ -3323,6 +3323,24 @@ ribi_t::ribi air_vehicle_t::get_ribi(const grund_t *gr) const return ribi_t::none; } +//BG, 03-Oct-2017: reservation scheduling avoids air traffic congestion. +// estimate_reservation_schedule() returns a reservation_schedule_item_t with the estimated reservation timing for the convoi arriving at ziel +// while it is distance_to_ziel tiles away from ziel and ziel has a length of length_of_ziel tiles. +reservation_schedule_item_t air_vehicle_t::estimate_reservation_schedule(const koord3d & distance_to_ziel, sint32 max_speed_of_ziel, sint32 length_of_ziel) const +{ + convoi_t* cnv = get_convoi(); + + koord d(distance_to_ziel.x >= 0 ? distance_to_ziel.x : -distance_to_ziel.x, distance_to_ziel.y >= 0 ? distance_to_ziel.y : -distance_to_ziel.y); + uint32 diagonal = min(d.x, d.y); + uint32 straight = d.x + d.y - (diagonal << 1); + uint32 distance = straight + diagonal * get_diagonal_vehicle_steps_per_tile() / VEHICLE_STEPS_PER_TILE; + uint32 speed = cnv->get_min_top_speed(); + uint32 ticks = (1 << YARDS_PER_TILE_SHIFT) / speed; + uint32 arrival = welt->get_ticks() + distance * ticks; + uint32 duration = length_of_ziel ? length_of_ziel * (1 << YARDS_PER_TILE_SHIFT) / max_speed_of_ziel : 0; + + return reservation_schedule_item_t(cnv->self, arrival, arrival + duration); +} // how expensive to go here (for way search) // author prissi @@ -3345,11 +3363,40 @@ int air_vehicle_t::get_cost(const grund_t *, const weg_t *w, const sint32, ribi_ // only, if not flying ... assert(w); - if(w->get_desc()->get_styp()==type_flat) { - costs += 3; - } - else { - costs += 2; + switch (w->get_desc()->get_styp()) + { + case type_flat: + costs += 3; + break; + + case type_runway: + { + costs += 2; + + //BG, 03-Oct-2017: is runway available when convoy presumably will arrive there + const runway_t* sch = static_cast(w); + switch (state) + { + case taxiing_to_halt: + { + reservation_schedule_item_t rsi = estimate_reservation_schedule(get_pos() - w->get_pos(), kmh_to_speed(w->get_max_speed()), 6 /* twice the minimum runway length */); + if (sch->can_schedule_reservation(rsi)) + // there is a time slot for this convoy + break; + // no break! + } + case taxiing: + // encourage using runway with least schedules reservations: + costs += 100 * sch->get_reservations().get_count(); + break; + default: ; + } + break; + } + + default: + costs += 2; + break; } } @@ -3365,7 +3412,10 @@ bool air_vehicle_t::check_next_tile(const grund_t *bd) const case taxiing_to_halt: case looking_for_parking: //DBG_MESSAGE("check_next_tile()","at %i,%i",bd->get_pos().x,bd->get_pos().y); - return (bd->hat_weg(air_wt) && bd->get_weg(air_wt)->get_max_speed()>0); + { + const weg_t *w = bd->get_weg(air_wt); + return w && w->get_max_speed() > 0; + } case landing: case departing: @@ -3387,6 +3437,7 @@ bool air_vehicle_t::is_target(const grund_t *gr,const grund_t *) const if(state!=looking_for_parking || !target_halt.is_bound()) { // search for the end of the runway const weg_t *w=gr->get_weg(air_wt); + if(w && w->get_desc()->get_styp()==type_runway) { // ok here is a runway ribi_t::ribi ribi= w->get_ribi_unmasked(); @@ -3501,7 +3552,7 @@ bool air_vehicle_t::calc_route(koord3d start, koord3d ziel, sint32 max_speed, ro target_halt = halthandle_t(); // no block reserved const weg_t *w=welt->lookup(start)->get_weg(air_wt); - bool start_in_the_air = (w==NULL); + bool start_in_the_air = (w==NULL) || flying_height > 0; bool end_in_air=false; searchforstop = takeoff = touchdown = 0x7ffffffful; @@ -3544,7 +3595,7 @@ bool air_vehicle_t::calc_route(koord3d start, koord3d ziel, sint32 max_speed, ro } // second: find target runway end - + flight_state old_state = state; state = taxiing_to_halt; // only used for search #ifdef USE_DIFFERENT_WIND @@ -3555,8 +3606,8 @@ bool air_vehicle_t::calc_route(koord3d start, koord3d ziel, sint32 max_speed, ro //DBG_MESSAGE("aircraft_t::calc_route()","search runway target near %i,%i,%i in corners %x",ziel.x,ziel.y,ziel.z); #endif route_t end_route; - if(!end_route.find_route( welt, ziel, this, max_speed, ribi_t::all, welt->get_settings().get_max_choose_route_steps() )) { + // well, probably this is a waypoint if( grund_t *target = welt->lookup(ziel) ) { if( !target->get_weg(air_wt) ) { @@ -3583,6 +3634,13 @@ bool air_vehicle_t::calc_route(koord3d start, koord3d ziel, sint32 max_speed, ro if(!start_in_the_air) { takeoff = route->get_count()-1; koord start_dir(welt->lookup(search_start)->get_weg_ribi(air_wt)); + + //BG, 06-Oct-2017: schedule reservation. As we are interested in the number of reservations only, speed and length of ziel are irrelevant. + // We do not use the schedule to control the convoy order as it is better to serve them in order of arrival at the runway! + const koord3d& schedule_pos = search_start; + runway_t* sch = (runway_t*)(welt->lookup(schedule_pos)->get_weg(air_wt)); + sch->schedule_reservation(estimate_reservation_schedule(schedule_pos - start, 0, 0)); + if(start_dir!=koord(0,0)) { // add the start ribi_t::ribi start_ribi = ribi_t::backward(ribi_type(start_dir)); @@ -3629,12 +3687,14 @@ bool air_vehicle_t::calc_route(koord3d start, koord3d ziel, sint32 max_speed, ro // init with current pos (in air ... ) route->clear(); route->append( start ); - state = flying; + //state = flying; + state = old_state; if(flying_height==0) { flying_height = 3*TILE_HEIGHT_STEP; } takeoff = 0; - target_height = ((sint16)get_pos().z+3)*TILE_HEIGHT_STEP; + if (state != circling || target_height == 0) + target_height = ((sint16)get_pos().z+3)*TILE_HEIGHT_STEP; } //DBG_MESSAGE("aircraft_t::calc_route()","take off ok"); @@ -3711,6 +3771,11 @@ bool air_vehicle_t::calc_route(koord3d start, koord3d ziel, sint32 max_speed, ro // now the route reach point (+1, since it will check before entering the tile ...) searchforstop = route->get_count()-1; + //BG, 03-Oct-2017: schedule reservation + const koord3d& schedule_pos = route->at(searchforstop); + runway_t* sch = (runway_t*)(welt->lookup(schedule_pos)->get_weg(air_wt)); + sch->schedule_reservation(estimate_reservation_schedule(schedule_pos - start, sch->get_max_speed(), searchforstop - touchdown + 1)); + // now we just append the rest for( int i=end_route.get_count()-2; i>=0; i-- ) { route->append(end_route.at(i)); @@ -3757,7 +3822,17 @@ bool air_vehicle_t::block_reserver( uint32 start, uint32 end, bool reserve ) con // we un-reserve also nonexistent tiles! (may happen during deletion) if(reserve) { start_now = true; + + // BG, 06-Oct-2017: avoid air traffic congestions: + // This additional reservation code is needed to (re-)start the reservation scheduling after loading a saved game. + // If scheduling data will be saved some day, it will still be needed to start the reservation scheduling of older saved games. + // Otherwise unscheduled convoys may never land or take off as scheduled convoys are preferred. + if (i == searchforstop) + if (!sch1->get_reservation_of(cnv->self)) + sch1->schedule_reservation(estimate_reservation_schedule(sch1->get_pos() - this->get_pos(), sch1->get_max_speed(), searchforstop - touchdown + 1)); + if( !sch1->reserve(cnv->self,ribi_t::none) ) { + // unsuccessful => must un-reserve all success = false; end = i; @@ -3845,6 +3920,16 @@ bool air_vehicle_t::can_enter_tile(const grund_t *gr, sint32 &restart_speed, uin runway_t *rw = (runway_t *)gr->get_weg(air_wt); // next tile a not runway => then unreserve if( rw == NULL || rw->get_desc()->get_styp() != type_runway || gr->is_halt() ) { + + //// check, if tile occupied by a plane on ground + //for (uint8 i = 1; iget_top(); i++) { + // obj_t *obj = gr->obj_bei(i); + // if (obj->get_typ() == obj_t::air_vehicle && ((air_vehicle_t *)obj)->is_on_ground()) { + // restart_speed = 0; + // return false; + // } + //} + block_reserver( touchdown, searchforstop+1, false ); } } diff --git a/simutrans/trunk/vehicle/simvehicle.h b/simutrans/trunk/vehicle/simvehicle.h index 374134a..ff30053 100644 --- a/simutrans/trunk/vehicle/simvehicle.h +++ b/simutrans/trunk/vehicle/simvehicle.h @@ -749,6 +749,11 @@ public: // return valid direction virtual ribi_t::ribi get_ribi(const grund_t* ) const; + //BG, 03-Oct-2017: reservation scheduling avoids air traffic congestion. + // estimate_reservation_schedule() returns a reservation_schedule_item_t with the estimated reservation timing for the convoi arriving at ziel + // while it is distance_to_ziel tiles away from ziel and ziel has a length of length_of_ziel tiles. + struct reservation_schedule_item_t estimate_reservation_schedule(const koord3d& distance_to_ziel, sint32 max_speed_of_ziel, sint32 length_of_ziel) const; + // how expensive to go here (for way search) virtual int get_cost(const grund_t *gr, const weg_t *w, const sint32 max_speed, ribi_t::ribi from) const;