I have added some comments Diff comments:
> > === modified file 'src/logic/map_objects/tribes/ship.cc' > --- src/logic/map_objects/tribes/ship.cc 2019-05-27 14:28:34 +0000 > +++ src/logic/map_objects/tribes/ship.cc 2019-09-03 15:47:16 +0000 > @@ -736,22 +736,215 @@ > } > } > > +bool Ship::has_destination(EditorGameBase& egbase, const PortDock& pd) const > { > + for (const auto& pair : destinations_) { > + if (pair.first.get(egbase) == &pd) { > + return true; > + } > + } > + return false; > +} > + > /** > * Enter a new destination port for the ship. > * Call this after (un)loading the ship, for proper logging. > */ > -void Ship::set_destination(PortDock* pd) { > - destination_ = pd; > - if (pd) { > - molog("set_destination / sending to portdock %u (carrying %" > PRIuS " items)\n", pd->serial(), > - items_.size()); > - pd->ship_coming(true); > - } else { > - molog("set_destination / none\n"); > +void Ship::push_destination(Game& game, PortDock& pd) { > + for (auto it = destinations_.begin(); it != destinations_.end(); ++it) { for (const auto& pair : destinations_) { > + if (it->first.get(game) == &pd) { > + // We're already going there > + return; > + } > } > + destinations_.push_back(std::make_pair(OPtr<PortDock>(&pd), 1)); > + reorder_destinations(game); > + molog("push_destination(%u): rerouted to portdock %u (carrying %" PRIuS > " items)\n", > + pd.serial(), get_current_destination(game)->serial(), > items_.size()); > + pd.ship_coming(*this, true); > Notifications::publish(NoteShip(this, > NoteShip::Action::kDestinationChanged)); > } > > +void Ship::clear_destinations(Game& game) { > + while (!destinations_.empty()) { > + pop_destination(game, *destinations_.front().first.get(game)); > + } > +} > + > +/** > + * Remove this destination from the queue > + */ > +void Ship::pop_destination(Game& game, PortDock& pd) { > + pd.ship_coming(*this, false); > + for (auto it = destinations_.begin(); it != destinations_.end(); ++it) { > + if (it->first.get(game) == &pd) { > + destinations_.erase(it); > + reorder_destinations(game); > + if (destinations_.empty()) { > + molog("pop_destination(%u): no destinations and > %" PRIuS " items left\n", > + pd.serial(), items_.size()); > + } else { > + molog("pop_destination(%u): rerouted to > portdock %u (carrying %" PRIuS " items)\n", > + pd.serial(), > get_current_destination(game)->serial(), items_.size()); > + } > + return; > + } > + } > +} > + > +// Recursively find the best ordering for our destinations > +static inline float prioritised_distance(Path& path, uint32_t priority, > uint32_t items) { > + return static_cast<float>(path.get_nsteps() * items) / (priority * > priority); > +} > +using DestinationsQueue = std::vector<std::pair<PortDock*, uint32_t>>; > +static std::pair<DestinationsQueue, float> shortest_order(Game& game, > + Fleet& fleet, > + bool is_on_dock, > + void* start, > + const > DestinationsQueue& remaining_to_visit, > + const > std::map<PortDock*, uint32_t> shipping_items) { > + const size_t nr_dests = remaining_to_visit.size(); > + assert(nr_dests > 0); > + if (nr_dests == 1) { > + // Recursion break: Only one portdock left > + Path path; > + if (is_on_dock) { > + PortDock* p = static_cast<PortDock*>(start); > + if (p != remaining_to_visit[0].first) { > + fleet.get_path(*p, > *remaining_to_visit[0].first, path); > + } > + } else { > + static_cast<Ship*>(start)->calculate_sea_route(game, > *remaining_to_visit[0].first, &path); > + } > + return std::pair<DestinationsQueue, float>(remaining_to_visit, > prioritised_distance( > + path, remaining_to_visit[0].second, > shipping_items.at(remaining_to_visit[0].first))); > + } > + > + std::pair<DestinationsQueue, float> best_result; > + best_result.second = std::numeric_limits<float>::max(); > + for (const auto& pair : remaining_to_visit) { > + DestinationsQueue remaining; > + for (const auto& p : remaining_to_visit) { > + if (p.first != pair.first) { > + remaining.push_back(p); > + } > + } > + auto result = shortest_order(game, fleet, true, pair.first, > remaining, shipping_items); > + result.first.emplace(result.first.begin(), pair); > + Path path; > + if (is_on_dock) { We have the exact same if... else above. Is this worth pulling out a (lambda) function? > + PortDock* p = static_cast<PortDock*>(start); > + if (p != remaining_to_visit[0].first) { > + fleet.get_path(*static_cast<PortDock*>(start), > *pair.first, path); > + } > + } else { > + static_cast<Ship*>(start)->calculate_sea_route(game, > *pair.first, &path); > + } > + const float length = result.second + prioritised_distance(path, > pair.second, shipping_items.at(pair.first)); > + if (length < best_result.second) { > + best_result.first = result.first; > + best_result.second = length; > + } > + } > + assert(best_result.second < std::numeric_limits<float>::max()); > + assert(best_result.first.size() == nr_dests); > + return best_result; > +} > + > +void Ship::reorder_destinations(Game& game) { > + upcast(PortDock, pd, get_position().field->get_immovable()); > + size_t nr_dests = 0; > + DestinationsQueue old_dq; > + PortDock* fallback_dest = nullptr; > + std::map<PortDock*, uint32_t> shipping_items; > + for (const auto& pair : destinations_) { > + PortDock* p = pair.first.get(game); > + assert(p); > + uint32_t nr_items = 0; > + for (const auto& si : items_) { > + if (si.get_destination(game) == p) { > + ++nr_items; > + } > + } > + if (nr_items == 0 && p->count_waiting() == 0 && > !p->expedition_started() && (!pd || pd->count_waiting(p) == 0)) { > + fallback_dest = p; > + // We don't need to go there anymore > + p->ship_coming(*this, false); > + continue; > + } > + old_dq.push_back(std::make_pair(p, pair.second)); > + ++nr_dests; > + shipping_items[p] = nr_items; > + } > + if (nr_dests <= 1) { > + destinations_.clear(); > + if (nr_dests > 0) { > + destinations_.push_back(old_dq[0]); > + } else if (fallback_dest) { > + > destinations_.push_back(std::make_pair(OPtr<PortDock>(fallback_dest), 1)); > + fallback_dest->ship_coming(*this, true); > + } > + return; > + } > + > + const OPtr<PortDock> old_dest = destinations_.front().first; > + DestinationsQueue dq = shortest_order(game, *fleet_, pd, > + pd ? static_cast<void*>(pd) : static_cast<void*>(this), > old_dq, shipping_items).first; > + assert(dq.size() == nr_dests); > + > + std::vector<std::pair<OPtr<PortDock>, uint32_t>> old_destinations = > destinations_; > + const size_t nr_all_old_dests = old_destinations.size(); > + destinations_.clear(); > + size_t index = 0; > + for (const auto& pair : dq) { > + OPtr<PortDock> optr(pair.first); > + uint32_t priority = pair.second; > + size_t old_index = 0; > + for (;; ++old_index) { How about for (; old_destinations[old_index].first != optr; ++old_index) { This should also be restricted to debug builds, because it's only there for the assert. > + assert(old_index < nr_all_old_dests); > + if (old_destinations[old_index].first == optr) { > + break; > + } > + } > + if (old_index < index) { > + priority += index - old_index; > + } > + destinations_.push_back(std::make_pair(optr, priority)); > + ++index; > + } > + if (old_dest != destinations_.front().first) { > + send_signal(game, "wakeup"); > + } > +} > + > +/** > + * Returns an estimation for the time in arbitrary units from now until the > moment when > + * this ship will probably arrive at the given PortDock. This may change > later when > + * destinations are added or removed. > + * Returns -1 if we are not planning to visit this PortDock or if we are not > planning -1 would be clearer throughout if it was a named constexpr - you use this flag in one of the functions above too. > + * to visit the given intermediate portdock earlier than the destination. > + */ > +int32_t Ship::estimated_arrival_time(Game& game, const PortDock& dest, const > PortDock* intermediate) const { > + uint32_t time = 0; > + const PortDock* iterator = nullptr; > + for (const auto& pair : destinations_) { > + Path path; > + if (iterator) { This if... else appears multiple times. Function time? > + fleet_->get_path(*iterator, *pair.first.get(game), > path); > + } else { > + calculate_sea_route(game, *pair.first.get(game), &path); > + } > + iterator = pair.first.get(game); > + if (iterator == intermediate) { > + intermediate = nullptr; > + } > + time += path.get_nsteps(); > + if (iterator == &dest) { > + return intermediate ? -1 : time; > + } > + } > + return -1; > +} > + > void Ship::add_item(Game& game, const ShippingItem& item) { > assert(items_.size() < descr().get_capacity()); > -- https://code.launchpad.net/~widelands-dev/widelands/new-shipping/+merge/371155 Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/new-shipping. _______________________________________________ Mailing list: https://launchpad.net/~widelands-dev Post to : widelands-dev@lists.launchpad.net Unsubscribe : https://launchpad.net/~widelands-dev More help : https://help.launchpad.net/ListHelp