diff --git a/simutrans/trunk/gui/simwin.cc b/simutrans/trunk/gui/simwin.cc index 2fbe30e..e6ea368 100644 --- a/simutrans/trunk/gui/simwin.cc +++ b/simutrans/trunk/gui/simwin.cc @@ -1683,11 +1683,11 @@ void win_display_flush(double konto) } #ifdef DEBUG if( env_t::verbose_debug>3 ) { - if( haltestelle_t::get_rerouting_status()==RECONNECTING ) { - info.append( " +" ); - } - else if( haltestelle_t::get_rerouting_status()==REROUTING ) { - info.append( " *" ); + switch(haltestelle_t::get_rerouting_status() ) { + case RECONNECTING: info.append( " +" ); break; + case REROUTING_TRANSFERS: info.append( " *" ); break; + case REROUTING: info.append( " o" ); break; + default: ; } if( skinverwaltung_t::compass_iso == NULL && wl->get_settings().get_rotation() ) { static const char *compass_dir[4] = { "North", "East", "South", "West" }; diff --git a/simutrans/trunk/simhalt.cc b/simutrans/trunk/simhalt.cc index 4de1354..cbcd57d 100644 --- a/simutrans/trunk/simhalt.cc +++ b/simutrans/trunk/simhalt.cc @@ -128,6 +128,9 @@ void haltestelle_t::step_all() // reconnecting finished, compute connected components in one sweep rebuild_connected_components(); // reroute in next call + status_step = REROUTING_TRANSFERS; + } + else if (status_step == REROUTING_TRANSFERS) { status_step = REROUTING; } else if (status_step == REROUTING) { @@ -879,8 +882,9 @@ bool haltestelle_t::step(uint8 what, sint16 &units_remaining) case RECONNECTING: units_remaining -= (rebuild_connections()/256)+2; break; + case REROUTING_TRANSFERS: case REROUTING: - if( !reroute_goods(units_remaining) ) { + if( !reroute_goods(units_remaining, status_step == REROUTING_TRANSFERS) ) { return false; } recalc_status(); @@ -925,7 +929,7 @@ void haltestelle_t::new_month() * returns true upon completion * @author Hj. Malthaner */ -bool haltestelle_t::reroute_goods(sint16 &units_remaining) +bool haltestelle_t::reroute_goods(sint16 &units_remaining, bool reroute_transfer) { if( last_catg_index==255 ) { last_catg_index = 0; @@ -933,6 +937,10 @@ bool haltestelle_t::reroute_goods(sint16 &units_remaining) for( ; last_catg_index this is not transfer halt + } else { all_links[i].is_transfer = true; @@ -1207,6 +1216,45 @@ sint32 haltestelle_t::rebuild_connections() return connections_searched; } +#define HALT_NOT_REGISTERED (0xffffu) +#define WEIGHT_INF (0xffffu) + +class connected_comp_t { + vector_tpl halts; + uint32 count; + uint16 id; +public: + connected_comp_t(uint16 id_) : count(0), id(id_) {} + uint16 register_halt(halthandle_t halt, bool is_transfer) + { + count ++; + if (is_transfer) { + halts.append(halt); + return halts.get_count() - 1; + } + else { + return HALT_NOT_REGISTERED; // ignore non-transfer halt + } + } + void unregister_halt(uint32 index) + { + if (index < halts.get_count()) { + halts[index] = halthandle_t(); + } + count --; + } + void fill_transfers(vector_tpl& transfers) + { + transfers.clear(); + FOR(vector_tpl, &h, halts) { + transfers.append(haltestelle_t::transfer_connection_t(h, WEIGHT_INF)); + } + } + + bool is_empty() const { return count == 0; } + uint32 get_count() const { return halts.get_count(); } + uint16 get_id() const { return id; } +}; void haltestelle_t::rebuild_linked_connections() { @@ -1224,18 +1272,37 @@ void haltestelle_t::rebuild_linked_connections() } -void haltestelle_t::fill_connected_component(uint8 catg_idx, uint16 comp) +void haltestelle_t::link_t::clear() +{ + transfers.clear(); + connections.clear(); + is_transfer = false; + if (catg_connected_component) { + if (index != HALT_NOT_REGISTERED) { + catg_connected_component->unregister_halt(index); + + if (catg_connected_component->is_empty()) { + delete catg_connected_component; + } + } + catg_connected_component = NULL; + } +} + +void haltestelle_t::fill_connected_component(uint8 catg_idx, connected_comp_t* comp) { - if (all_links[catg_idx].catg_connected_component != UNDECIDED_CONNECTED_COMPONENT) { + if (all_links[catg_idx].catg_connected_component != NULL) { // already connected return; } all_links[catg_idx].catg_connected_component = comp; + all_links[catg_idx].index = comp->register_halt(self, is_transfer(catg_idx)); FOR(vector_tpl, &c, all_links[catg_idx].connections) { c.halt->fill_connected_component(catg_idx, comp); // cache the is_transfer value c.is_transfer = c.halt->is_transfer(catg_idx); + } } @@ -1244,9 +1311,31 @@ void haltestelle_t::rebuild_connected_components() { for(uint8 catg_idx = 0; catg_idx, halt, alle_haltestellen) { - if (halt->all_links[catg_idx].catg_connected_component == UNDECIDED_CONNECTED_COMPONENT) { + if (halt->all_links[catg_idx].catg_connected_component == NULL) { + connected_comp_t *comp = new connected_comp_t(halt.get_id()); // start recursion - halt->fill_connected_component(catg_idx, halt.get_id()); + halt->fill_connected_component(catg_idx, comp); + } + } + // initialize routing cache + FOR(vector_tpl, halt, alle_haltestellen) { + link_t& link = halt->all_links[catg_idx]; + if (halt->is_transfer(catg_idx)) { + link.catg_connected_component->fill_transfers(link.transfers); + link.transfers[ link.index ].weight = 0; + FOR(vector_tpl, &c, link.connections) { + if (c.is_transfer && c.weight < 2*WEIGHT_MIN) { + link.transfers[ c.halt->all_links[catg_idx].index ].weight = c.weight; + } + } + } + else { + link.transfers.clear(); + FOR(vector_tpl, &c, link.connections) { + if (c.is_transfer) { + link.transfers.append(transfer_connection_t(c.halt, c.weight)); + } + } } } } @@ -1263,7 +1352,7 @@ sint8 haltestelle_t::is_connected(halthandle_t halt, uint8 catg_index) const if (linka.connections.empty() || linkb.connections.empty()) { return 0; // empty connections -> not connected } - if (linka.catg_connected_component == UNDECIDED_CONNECTED_COMPONENT || linkb.catg_connected_component == UNDECIDED_CONNECTED_COMPONENT) { + if (linka.catg_connected_component == NULL || linkb.catg_connected_component == NULL) { return -1; // undecided - try later } // now check whether both halts are in the same component @@ -1271,6 +1360,8 @@ sint8 haltestelle_t::is_connected(halthandle_t halt, uint8 catg_index) const } + + /** * Data for route searching */ @@ -1302,54 +1393,43 @@ uint8 haltestelle_t::last_search_ware_catg_idx = 255; * * @author Hj. Malthaner/prissi/gerw/Knightly */ -int haltestelle_t::search_route( const halthandle_t *const start_halts, const uint16 start_halt_count, const bool no_routing_over_overcrowding, ware_t &ware, ware_t *const return_ware ) +int haltestelle_t::search_route( const halthandle_t *const start_halts_, const uint16 start_halt_count, const bool no_routing_over_overcrowding, ware_t &ware, ware_t *const return_ware ) { const uint8 ware_catg_idx = ware.get_desc()->get_catg_index(); const uint8 ware_idx = ware.get_desc()->get_index(); + vector_tpl start_halts(start_halt_count); + for( uint16 s=0; s end_conn_comp(16); + end_conn_comp.clear(); + // since also the factory halt list is added to the ground, we can use just this ... const planquadrat_t *const plan = welt->access( ware.get_zielpos() ); const halthandle_t *const halt_list = plan->get_haltlist(); // but we can only use a subset of these static vector_tpl end_halts(16); end_halts.clear(); - // target halts are in these connected components - // we start from halts only in the same components - static vector_tpl end_conn_comp(16); - end_conn_comp.clear(); - // if one target halt is undefined, we have to start search from all halts - bool end_conn_comp_undefined = false; - for( uint32 h=0; hget_haltlist_count(); ++h ) { halthandle_t halt = halt_list[h]; if( halt.is_bound() && halt->is_enabled(ware_catg_idx) ) { // check if this is present in the list of start halts - for( uint16 s=0; s within walking distance - ware.set_ziel( start_halts[s] ); - ware.set_zwischenziel( halthandle_t() ); - if( return_ware ) { - return_ware->set_ziel( start_halts[s] ); - return_ware->set_zwischenziel( halthandle_t() ); - } - return ROUTE_WALK; + if (start_halts.is_contained(halt)) { + // destination halt is also a start halt -> within walking distance + ware.set_ziel( halt ); + ware.set_zwischenziel( halthandle_t() ); + if( return_ware ) { + return_ware->set_ziel( halt ); + return_ware->set_zwischenziel( halthandle_t() ); } + return ROUTE_WALK; } end_halts.append(halt); - - // check connected component of target halt - uint16 endhalt_conn_comp = halt->all_links[ware_catg_idx].catg_connected_component; - if (endhalt_conn_comp == UNDECIDED_CONNECTED_COMPONENT) { - // undefined: all start halts are probably connected to this target - end_conn_comp_undefined = true; - } - else { - // store connected component - if (!end_conn_comp_undefined) { - end_conn_comp.append_unique( endhalt_conn_comp ); - } - } + end_conn_comp.append_unique( halt->all_links[ware_catg_idx].catg_connected_component ); } } @@ -1363,6 +1443,15 @@ int haltestelle_t::search_route( const halthandle_t *const start_halts, const ui } return NO_ROUTE; } + // try to use the cached routing information + uint16 best_destination_weight = WEIGHT_INF; // best weight among all destinations + int res = search_route_cached(start_halts, end_halts, no_routing_over_overcrowding, ware, return_ware, best_destination_weight); + if (res != ROUTE_UNKNOWN) { + return res; + } + // use best_destination_weight as upper bound + // we only find better routes now + // invalidate search history last_search_origin = halthandle_t(); @@ -1376,7 +1465,7 @@ int haltestelle_t::search_route( const halthandle_t *const start_halts, const ui // initialisations for end halts => save some checking inside search loop FOR(vector_tpl, const e, end_halts) { uint16 const halt_id = e.get_id(); - halt_data[ halt_id ].best_weight = 65535u; + halt_data[ halt_id ].best_weight = WEIGHT_INF; halt_data[ halt_id ].destination = 1u; halt_data[ halt_id ].depth = 1u; // to distinct them from start halts markers[ halt_id ] = current_marker; @@ -1385,7 +1474,6 @@ int haltestelle_t::search_route( const halthandle_t *const start_halts, const ui uint16 const max_transfers = welt->get_settings().get_max_transfers(); uint16 const max_hops = welt->get_settings().get_max_hops(); uint16 allocation_pointer = 0; - uint16 best_destination_weight = 65535u; // best weight among all destinations open_list.clear(); @@ -1394,16 +1482,16 @@ int haltestelle_t::search_route( const halthandle_t *const start_halts, const ui for( ; allocation_pointerall_links[ware_catg_idx].catg_connected_component; + connected_comp_t* start_conn_comp = start_halt->all_links[ware_catg_idx].catg_connected_component; - if (!end_conn_comp_undefined && start_conn_comp != UNDECIDED_CONNECTED_COMPONENT && !end_conn_comp.is_contained( start_conn_comp )){ + if (!end_conn_comp.is_contained( start_conn_comp )){ // this start halt will not lead to any target continue; } open_list.insert( route_node_t(start_halt, 0) ); halt_data_t & start_data = halt_data[ start_halt.get_id() ]; - start_data.best_weight = 65535u; + start_data.best_weight = WEIGHT_INF; start_data.destination = 0; start_data.depth = 0; start_data.overcrowded = false; // start halt overcrowding is handled by routines calling this one @@ -1468,7 +1556,10 @@ int haltestelle_t::search_route( const halthandle_t *const start_halts, const ui // shortest path to the current halt has already been found earlier continue; } - + if( current_halt_data.depth == 0 ) { + //start node + current_halt_data.best_weight = 0; + } if( current_halt_data.depth > max_transfers ) { // maximum transfer limit is reached -> do not add reachable halts to open list continue; @@ -1568,30 +1659,220 @@ int haltestelle_t::search_route( const halthandle_t *const start_halts, const ui } -void haltestelle_t::search_route_resumable( ware_t &ware ) +struct transfer_link_t : public haltestelle_t::transfer_connection_t { + halthandle_t connected; ///< halt connected to transfer + + static uint8 ware_catg_idx; + // sort with respect to connected compenent, index into connected component + static bool cmp(const transfer_link_t& a, const transfer_link_t& b) + { + return haltestelle_t::cmp_transfer_connection(a, b, ware_catg_idx); + } + bool operator==(const transfer_link_t a) const + { + return haltestelle_t::cmp_transfer_connection(*this, a, ware_catg_idx) == 0; + } + transfer_link_t() {} + + transfer_link_t(halthandle_t h, uint16 w, halthandle_t c) : + haltestelle_t::transfer_connection_t(h, w), connected(c) {} +}; +uint8 transfer_link_t::ware_catg_idx; + +// sort first wrt connected component, then with respect to the index into the connected component +int haltestelle_t::cmp_transfer_connection(const transfer_connection_t& a, const transfer_connection_t& b, uint8 ware_catg_idx) +{ + int diff = (int)a.halt->all_links[ware_catg_idx].catg_connected_component->get_id() + - (int)b.halt->all_links[ware_catg_idx].catg_connected_component->get_id(); + if (diff == 0) { + diff = (int)a.halt->all_links[ware_catg_idx].index - (int)b.halt->all_links[ware_catg_idx].index; + } + return diff; +} + +void haltestelle_t::generate_transfer_list(vector_tpl& halts, vector_tpl& transfers, uint8 ware_catg_idx, bool back) +{ + transfer_link_t::ware_catg_idx = ware_catg_idx; + transfers.clear(); + FOR(vector_tpl, halt, halts) { + if (halt->is_transfer(ware_catg_idx)) { + transfer_link_t l(halt, 0, halt); + if (transfer_link_t* old = transfers.insert_unique_ordered(l, transfer_link_t::cmp)) { + if (old->weight > 0) { + *old = l; + } + } + continue; + } + // now loop over all transfers + FOR(vector_tpl, const& trc, halt->all_links[ ware_catg_idx ].transfers) { + // this is the weight of moving from halt to transfer + uint16 weight = trc.weight; + if (back) { + // get weight of moving from transfer to halt + FOR(vector_tpl, c, trc.halt->all_links[ware_catg_idx].connections) { + if (c.halt == halt) { + weight = c.weight; + break; + } + } + } + transfer_link_t l(trc.halt, weight, halt); + if (transfer_link_t* old = transfers.insert_unique_ordered(l, transfer_link_t::cmp)) { + if (old->weight > l.weight) { + *old = l; + } + } + } + } +} + +int haltestelle_t::search_route_cached(vector_tpl& start_halts, vector_tpl& target_halts, + bool no_routing_over_overcrowding, ware_t &ware, ware_t* return_ware, + uint16& best_destination_weight) { + if (start_halts.empty() || target_halts.empty()) { + return NO_ROUTE; + } + // during reconnecting the connected-components information is invalid + if (status_step == RECONNECTING) { + return ROUTE_UNKNOWN; + } + + // route search from start -> (transfer network) -> target + // assuming the all-pair shortest path problem is solved in the network + const uint8 ware_catg_idx = ware.get_desc()->get_catg_index(); + transfer_link_t::ware_catg_idx = ware_catg_idx; - // continue search if start halt and good category did not change - const bool resume_search = last_search_origin == self && ware_catg_idx == last_search_ware_catg_idx; + best_destination_weight = WEIGHT_INF; - if (!resume_search) { - last_search_origin = self; - last_search_ware_catg_idx = ware_catg_idx; - open_list.clear(); - // set current marker - ++current_marker; - if( current_marker==0 ) { - MEMZERON(markers, halthandle_t::get_size()); - current_marker = 1u; + // check if direct connection exists - there might be faster indirect connections, + // direct routes between non-transfer halts are not detected by the algorithm below + FOR(vector_tpl, sh, start_halts) { + + vector_tpl &start_connections = sh->all_links[ware_catg_idx].connections; + FOR(vector_tpl, th, target_halts) { + if (th->is_transfer(ware_catg_idx)) { + continue; + } + if (start_connections.is_contained(th)) { + uint32 i = start_connections.index_of(th); + if (start_connections[i].weight < best_destination_weight) { + best_destination_weight = start_connections[i].weight; + ware.set_ziel(th); + if (return_ware) { + return_ware->set_ziel(sh); + } + } + } + } + } + if (best_destination_weight < WEIGHT_INF) { + ware.set_zwischenziel(ware.get_ziel()); + if (return_ware) { + return_ware->set_zwischenziel(return_ware->get_ziel()); } } - // remember destination nodes, to reset them before returning - static vector_tpl dest_indices(16); - dest_indices.clear(); + // generate list of transfer stations connected to the start and target halts + vector_tpl target_transfers; + vector_tpl start_transfers; + + generate_transfer_list(start_halts, start_transfers, ware_catg_idx, false); + generate_transfer_list(target_halts, target_transfers, ware_catg_idx, true); + + // solve the routing problem: loop over all start and target transfers, + // find the best route + bool unexplored_path = false; + halthandle_t best_target_transfer; + bool best_over_crowded = false; + + FOR(vector_tpl const, stl, start_transfers) + { + if (!stl.halt.is_bound()) { + continue; + } + FOR(vector_tpl const, ttl, target_transfers) + { + if (!ttl.halt.is_bound()) { + continue; + } + if (ttl.halt->all_links[ware_catg_idx].catg_connected_component != stl.halt->all_links[ware_catg_idx].catg_connected_component) { + continue; // not in the same connected component + } + vector_tpl &stt = stl.halt->all_links[ ware_catg_idx ].transfers; + uint16 idx = ttl.halt->all_links[ ware_catg_idx ].index; + // stt[idx].weight is the weight of the shortest route from stl.halt to ttl.halt + if (stt[idx].weight == WEIGHT_INF) { + // unexplored, stop + unexplored_path = true; + break; + } + // total weight + uint16 weight = stl.weight + stt[idx].weight + ttl.weight; + if (weight < best_destination_weight) { + best_destination_weight = weight; + ware.set_ziel( ttl.connected ); + ware.set_zwischenziel( stl.halt != stl.connected ? stl.halt : stt[idx].halt ); + + assert(ware.get_zwischenziel() != stl.connected); + + if (return_ware) { + return_ware->set_ziel( stl.connected ); + } + best_target_transfer = ttl.halt; + if (no_routing_over_overcrowding) { + if (ttl.halt != ttl.connected) { + // check if target transfer is overcrowded (only if not target) + best_over_crowded |= ttl.halt->is_overcrowded(ware_catg_idx); + } + } + } + } + if (unexplored_path) { + break; + } + } + // there were still unexplored paths between start and target halts + if (unexplored_path) { + return ROUTE_UNKNOWN; + } + if (best_destination_weight == WEIGHT_INF) { + return NO_ROUTE; + } + // found best path + + // check for overcrowded transfers + if (no_routing_over_overcrowding && best_target_transfer.is_bound()) { + // go backward in the route + uint16 idx = best_target_transfer->all_links[ ware_catg_idx ].index; + halthandle_t transfer = ware.get_zwischenziel(); + while (!best_over_crowded && transfer != best_target_transfer) { + best_over_crowded = transfer->is_overcrowded(ware_catg_idx); + transfer = transfer->all_links[ ware_catg_idx ].transfers[idx].halt; + } + } + + // adjust returning packet + if (return_ware) { + if (ware.get_ziel()->is_transfer(ware_catg_idx) || return_ware->get_ziel()->is_transfer(ware_catg_idx)) { + vector_tpl &ttt = ware.get_ziel()->all_links[ ware_catg_idx ].transfers; + return_ware->set_zwischenziel(ttt.get_count() == 1 ? ttt[0].halt : halthandle_t() ); + } + else { + // there is a direct connection, already resolved above + } + } + return best_over_crowded ? ROUTE_OVERCROWDED : ROUTE_OK; +} - uint16 best_destination_weight = 65535u; + +void haltestelle_t::search_route_resumable( ware_t &ware ) +{ + const uint8 ware_catg_idx = ware.get_desc()->get_catg_index(); + + uint16 best_destination_weight = WEIGHT_INF; // reset next transfer and destination halt to null -> if they remain null after search, no route can be found ware.set_ziel( halthandle_t() ); @@ -1609,6 +1890,54 @@ void haltestelle_t::search_route_resumable( ware_t &ware ) } } + // we start in this connected component + connected_comp_t* const conn_comp = all_links[ ware_catg_idx ].catg_connected_component; + + // remember destination nodes, to reset them before returning + static vector_tpl target_halts; + target_halts.clear(); + // generate list of suitable target halts + for( uint8 h = 0; hget_haltlist_count(); ++h ) { + const halthandle_t halt = halt_list[h]; + if( halt.is_bound() && halt->is_enabled(ware_catg_idx) && halt->all_links[ ware_catg_idx ].catg_connected_component == conn_comp) { + target_halts.append(halt); + } + } + if (target_halts.empty()) { + return; + } + vector_tpl start_halts(1); + start_halts.append(self); + + switch(search_route_cached(start_halts, target_halts, false, ware, NULL, best_destination_weight)) { + case ROUTE_OK: + case NO_ROUTE: + return; + case ROUTE_UNKNOWN: + default: ; + } + + // --------------------- + // now resort to Dijsktra + // will use best routes between transfer nodes + bool store_best_transfer_weights = is_transfer(ware_catg_idx) && conn_comp!=NULL && (status_step != RECONNECTING); + vector_tpl &mytransfers = all_links[ ware_catg_idx ].transfers; + // --------------------- + // continue search if start halt and good category did not change + const bool resume_search = last_search_origin == self && ware_catg_idx == last_search_ware_catg_idx; + + if (!resume_search) { + last_search_origin = self; + last_search_ware_catg_idx = ware_catg_idx; + open_list.clear(); + // set current marker + ++current_marker; + if( current_marker==0 ) { + MEMZERON(markers, halthandle_t::get_size()); + current_marker = 1u; + } + } + // check explored connection if (resume_search) { for( uint8 h=0; hget_haltlist_count(); ++h ) { @@ -1620,7 +1949,7 @@ void haltestelle_t::search_route_resumable( ware_t &ware ) } } // for all halts with halt_data.weight < explored_weight one of the best routes is found - const uint16 explored_weight = open_list.empty() ? 65535u : open_list.front().aggregate_weight; + const uint16 explored_weight = open_list.empty() ? WEIGHT_INF : open_list.front().aggregate_weight; if (best_destination_weight <= explored_weight) { // we explored best route to this destination in last run @@ -1629,38 +1958,21 @@ void haltestelle_t::search_route_resumable( ware_t &ware ) return; } } - // we start in this connected component - uint16 const conn_comp = all_links[ ware_catg_idx ].catg_connected_component; // find suitable destination halt(s), if any - for( uint8 h=0; hget_haltlist_count(); ++h ) { - const halthandle_t halt = halt_list[h]; - if( halt.is_bound() && halt->is_enabled(ware_catg_idx) ) { - - // test for connected component - uint16 const dest_comp = halt->all_links[ ware_catg_idx ].catg_connected_component; - if (dest_comp != UNDECIDED_CONNECTED_COMPONENT && conn_comp != UNDECIDED_CONNECTED_COMPONENT && conn_comp != dest_comp) { - continue; - } + FOR(vector_tpl, halt, target_halts) { // initialisations for destination halts => save some checking inside search loop if( markers[ halt.get_id() ]!=current_marker ) { // first time -> initialise marker and all halt data markers[ halt.get_id() ] = current_marker; - halt_data[ halt.get_id() ].best_weight = 65535u; + halt_data[ halt.get_id() ].best_weight = WEIGHT_INF; halt_data[ halt.get_id() ].destination = true; } else { // initialised before -> only update destination bit set halt_data[ halt.get_id() ].destination = true; } - dest_indices.append(halt.get_id()); - } - } - - if( dest_indices.empty() ) { - // no destination halt found or current halt is the same as (all) the destination halt(s) - return; } uint16 const max_transfers = welt->get_settings().get_max_transfers(); @@ -1708,6 +2020,17 @@ void haltestelle_t::search_route_resumable( ware_t &ware ) // assert(current_halt_data.best_weight == current_weight); } + // we computed the best path to this transfer halt, store it, to + // speed up route search later + if (store_best_transfer_weights && current_node.halt->is_transfer(ware_catg_idx)) { + uint16 idx = current_node.halt->all_links[ ware_catg_idx ].index; + if (mytransfers[idx].weight > current_weight) { + assert(mytransfers[idx].weight == WEIGHT_INF); + mytransfers[idx].weight = current_weight; + mytransfers[idx].halt = current_halt_data.transfer; + } + } + if( current_halt_data.destination ) { // destination found ware.set_ziel( current_node.halt ); @@ -1774,9 +2097,10 @@ void haltestelle_t::search_route_resumable( ware_t &ware ) } // clear destinations since we may want to do another search with the same current_marker - FOR(vector_tpl, const i, dest_indices) { + FOR(vector_tpl, const halt, target_halts) { + uint16 i = halt.get_id(); halt_data[i].destination = false; - if (halt_data[i].best_weight == 65535u) { + if (halt_data[i].best_weight == WEIGHT_INF) { // not processed -> reset marker --markers[i]; } diff --git a/simutrans/trunk/simhalt.h b/simutrans/trunk/simhalt.h index a0f5816..252447c 100644 --- a/simutrans/trunk/simhalt.h +++ b/simutrans/trunk/simhalt.h @@ -30,7 +30,8 @@ #define RECONNECTING (1) -#define REROUTING (2) +#define REROUTING_TRANSFERS (2) +#define REROUTING (3) #define MAX_HALT_COST 8 // Total number of cost items #define MAX_MONTHS 12 // Max history @@ -55,6 +56,9 @@ class schedule_t; class player_t; class ware_t; +class connected_comp_t; +struct transfer_link_t; + // -------------------------- Haltestelle ---------------------------- /** @@ -242,10 +246,21 @@ public: bool is_transfer(const uint8 catg) const { return all_links[catg].is_transfer; } + /** + * store information about best paths between transfer halts + */ + struct transfer_connection_t + { + transfer_connection_t() : weight(0) {} + transfer_connection_t(halthandle_t h, uint16 w) : halt(h), weight(w) {} + halthandle_t halt; ///< best connection goes via this halt + uint16 weight; ///< weight of best path + }; + static int cmp_transfer_connection(const transfer_connection_t& a, const transfer_connection_t& b, uint8 catg_index); + private: slist_tpl tiles; - /** * Stores information about link to cargo network of a certain category */ @@ -254,6 +269,16 @@ private: vector_tpl connections; /** + * Best paths to all transfer halts. + * + * If this halt is a transfer halt: + * The list contains best path to all connected transfers. + * Index in the list determined by the the connected component. + * If this halt is not a transfer halt: + * The list contains the connected transfer halts. + */ + vector_tpl transfers; + /** * A transfer/interchange is a halt whereby ware can change line or lineless convoy. * Thus, if a halt is served by 2 or more schedules (of lines or lineless convoys) * for a particular ware type, it is a transfer/interchange for that ware type. @@ -265,24 +290,20 @@ private: /** * Id of connected component in link graph. * Two halts are connected if and only if they belong to the same connected component. - * Exception: if value == UNDECIDED_CONNECTED_COMPONENT, then we are in the middle of + * Exception: if value == NULL, then we are in the middle of * recalculating the link graph. * * The id of the component has to be equal to the halt-id of one of its halts. * This ensures that we always have unique component ids. */ - uint16 catg_connected_component; + connected_comp_t* catg_connected_component; -# define UNDECIDED_CONNECTED_COMPONENT (0xffff) + uint16 index; - link_t() { clear(); } + link_t(): catg_connected_component(NULL) { clear(); } + ~link_t() { clear(); } - void clear() - { - connections.clear(); - is_transfer = false; - catg_connected_component = UNDECIDED_CONNECTED_COMPONENT; - } + void clear(); }; /// All links to networks of all freight categories, filled by rebuild_connected_components. @@ -301,7 +322,7 @@ private: * @param catg category of cargo network * @param comp number of component */ - void fill_connected_component(uint8 catg, uint16 comp); + void fill_connected_component(uint8 catg, connected_comp_t* comp); // Array with different categories that contains all waiting goods at this stop @@ -376,7 +397,7 @@ public: * returns true upon completion * @author Hj. Malthaner */ - bool reroute_goods(sint16 &units_remaining); + bool reroute_goods(sint16 &units_remaining, bool reroute_transfer); /** * getter/setter for sortby @@ -503,8 +524,21 @@ private: */ static halthandle_t last_search_origin; static uint8 last_search_ware_catg_idx; + + + static int search_route_cached(vector_tpl& start_halts, vector_tpl& target_halts, + bool no_routing_over_overcrowding, ware_t &ware, ware_t* return_ware, + uint16& best_destination_weight); + static void generate_transfer_list(vector_tpl& halts, vector_tpl& transfers, uint8 ware_catg_idx, bool back); + public: - enum routing_result_flags { NO_ROUTE=0, ROUTE_OK=1, ROUTE_WALK=2, ROUTE_OVERCROWDED=8 }; + enum routing_result_flags { + NO_ROUTE = 0, + ROUTE_OK = 1, + ROUTE_WALK = 2, + ROUTE_OVERCROWDED = 8, + ROUTE_UNKNOWN = 16, + }; /** * Kann die Ware nicht zum Ziel geroutet werden (keine Route), dann werden