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
