widelands-dev team mailing list archive
-
widelands-dev team
-
Mailing list archive
-
Message #17951
Re: [Merge] lp:~widelands-dev/widelands/new-shipping into lp:widelands
Did a first review, the code is ok, but some more comments
would help me to grasp me the semantics of some stuctures.
and please refactor out some of the bigger loops. (https://de.wikipedia.org/wiki/Refactoring)
Please check my inline comments.
Do you have an idea how big the perfomance impact may be for a Map with a lot of Ports.
e.g. two AI Players on the Nile or my new Map https://www.widelands.org/maps/unreal-waterflow/
You are solving a kind of https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden
or https://en.wikipedia.org/wiki/Travelling_salesman_problem
this has potential for exponential (or NP-Hard) complexity. So maybe we should
put in some limits so that we dod not stop the game dunring these calculations.
e.g.
* limit the number of ports on a route to 4/8/16?
* stop some calcualtions after a giiven mount of steps?
* be carefull not to use (local) timings as this depends on the CPU and may rsult in desyncs
Next I will run the regression tests.
Maybe its worth to design a big Map with a lot of Ports (128) to test this?
Diff comments:
> === modified file 'src/economy/fleet.cc'
> --- src/economy/fleet.cc 2019-04-24 15:11:23 +0000
> +++ src/economy/fleet.cc 2019-08-10 17:23:31 +0000
> @@ -699,6 +700,46 @@
> if (route_length == kRouteNotCalculated) {
> route_length = s->calculate_sea_route(game, *p);
> }
> + if (fallback) {
> + // This ship is employed transporting wares, lower its priority drastically
Please make this a function of its own add some more coments
> + const uint32_t real_length = route_length;
> + uint32_t malus = 1;
> + uint32_t index = 0;
As wee need an index anyway a "classic" loop would avoid inconsistencies when we add continue statements later?
> + PortDock* iterator = nullptr;
> + uint32_t shortest_detour = std::numeric_limits<uint32_t>::max();
> + uint32_t best_index;
> + for (const auto& pair : s->destinations_) {
> + PortDock* pd = pair.first.get(game);
> + Path path;
> + uint32_t detour;
> + if (iterator == p) {
> + detour = 0;
> + } else if (iterator) {
> + get_path(*iterator, *p, path);
> + detour = path.get_nsteps();
> + } else {
> + s->calculate_sea_route(game, *p, &path);
> + detour = path.get_nsteps();
> + }
> + if (p != pd) {
> + get_path(*p, *pd, path);
> + detour += path.get_nsteps();
> + }
> + if (detour < shortest_detour) {
> + shortest_detour = detour;
> + best_index = index;
> + }
> + malus += pair.second;
> + iterator = pd;
> + ++index;
> + }
> + route_length += shortest_detour * best_index;
> + if (route_length + shortest_detour > real_length * malus) {
> + // Unreasonably long detour
> + continue;
> + }
> + route_length *= malus;
> + }
>
> if (route_length < shortest_dist) {
> shortest_dist = route_length;
> @@ -744,107 +785,93 @@
> }
>
> if (closest_port) {
> - s->set_destination(closest_port);
> + s->push_destination(game, *closest_port);
> s->send_signal(game, "wakeup");
> }
> }
> }
>
> /**
> - * For the given three consecutive ports, decide if their path is favourable or not.
> - * \return true if the path from start to finish >= the path from middle to finish
> - */
> -bool Fleet::is_path_favourable(const PortDock& start,
> - const PortDock& middle,
> - const PortDock& finish) {
> - if (&middle != &finish) {
> - Path path_start_to_finish;
> - Path path_middle_to_finish;
> -#ifndef NDEBUG
> - assert(get_path(start, finish, path_start_to_finish));
> -#else
> - get_path(start, finish, path_start_to_finish);
> -#endif
> - if (get_path(middle, finish, path_middle_to_finish)) {
> - if (path_middle_to_finish.get_nsteps() > path_start_to_finish.get_nsteps()) {
> - return false;
> - }
> - }
> - }
> - return true; // default
> -}
> -
> -/**
> - * For the given ship, go through all ports of this fleet
> - * and find the one with the best score.
> - * \return that port
> - */
> -PortDock* Fleet::find_next_dest(Game& game, const Ship& ship, const PortDock& from_port) {
> - PortDock* best_port = nullptr;
> - float best_score = 0.0f;
> -
> - for (PortDock* p : ports_) {
> - if (p == &from_port) {
> - continue; // same port
> - }
> -
> - float score = 0.0f;
> - WareInstance* ware;
> - Worker* worker;
> -
> - // Score for wares/workers onboard that ship for that port
> - for (const ShippingItem& si : ship.items_) {
> - if (si.get_destination(game) == p) {
> - si.get(game, &ware, &worker);
> - if (ware) {
> - score += 1; // TODO(ypopezios): increase by ware's importance
> - } else { // worker
> - score += 4;
> - }
> - }
> - }
> -
> - // Score for wares/workers waiting at that port
> - for (const ShippingItem& si : from_port.waiting_) {
> - if (si.get_destination(game) == p) {
> - si.get(game, &ware, &worker);
> - if (ware) {
> - score += 1; // TODO(ypopezios): increase by ware's importance
> - } else { // worker
> - score += 4;
> - }
> - }
> - }
> -
> - if (score == 0.0f && p->get_need_ship() == 0) {
> - continue; // empty ship to empty port
> - }
> -
> - // Here we get distance ship->port
> - uint32_t route_length = kRouteNotCalculated;
> -
> - // Get precalculated distance if the ship is at a port
> - {
> - Path precalculated_path;
> - if (get_path(from_port, *p, precalculated_path)) { // try to use precalculated path
> - route_length = precalculated_path.get_nsteps();
> - }
> - }
> -
> - // Get distance for when the ship is not at a port (should not happen frequently)
> - if (route_length == kRouteNotCalculated) {
> - route_length = ship.calculate_sea_route(game, *p);
> - }
> -
> - score = (score + 1.0f) * (score + p->get_need_ship());
> - score = score * (1.0f - route_length / (score + route_length));
> - if (score > best_score) {
> - best_score = score;
> - best_port = p;
> - }
> - }
> -
> - return best_port;
> + * Tell the given ship where to go next. May push any number of destinations.
> + */
> +void Fleet::push_next_destinations(Game& game, Ship& ship, const PortDock& from_port) {
> + std::vector<std::pair<PortDock*, uint32_t>> destinations;
what semantic has this uint32_t for the Port? some priority?
> + uint32_t total_items = ship.get_nritems(); // All waiting and shipping items
> + uint32_t waiting_items = 0; // Items that have a destination which this ship is not currently planning to visit
> + for (auto& it : from_port.waiting_) {
> + if (PortDock* pd = it.destination_dock_.get(game)) {
> + ++total_items;
> + if (ship.has_destination(game, *pd)) {
> + continue;
> + }
> + ++waiting_items;
> + bool found = false;
> + for (auto& pair : destinations) {
> + if (pair.first == pd) {
> + ++pair.second;
> + found = true;
> + break;
> + }
> + }
> + if (!found) {
> + destinations.push_back(std::make_pair(pd, 1));
> + }
> + }
> + }
> + assert(waiting_items <= total_items);
Maybe assert(waiting_items <= total_items, "More Items waiting then total in stock")?
> + if (waiting_items == 0) {
> + // Nothing to do
> + return;
> + }
> + total_items -= waiting_items;
> + // For each destination, decide whether to tell the ship to visit it
> + // or whether it would be better to wait for another ship
> + for (const auto& destpair : destinations) {
Pleas make this loop a function of it own
> + Path path;
> + get_path(from_port, *destpair.first, path);
Would it be worth having a (global) cache ot pathes for the ports, smells like we will (re-)calcuate them quite ofen?
> + const uint32_t direct_route = path.get_nsteps();
> + assert(direct_route);
> + uint32_t malus = 1;
> + uint32_t shortest_detour = std::numeric_limits<uint32_t>::max();
> + uint32_t best_index;
> + if (ship.destinations_.empty()) {
> + best_index = 0;
> + malus = 0;
> + shortest_detour = 0;
> + } else {
> + const PortDock* iterator = &from_port;
> + uint32_t index = 0;
> + for (const auto& pair : ship.destinations_) {
> + const PortDock* pd = pair.first.get(game);
> + uint32_t base_length = 0;
> + uint32_t detour = 0;
> + if (iterator != pd) {
> + get_path(*iterator, *pd, path);
> + base_length = path.get_nsteps();
> + }
> + if (iterator != &from_port) {
> + get_path(*iterator, from_port, path);
> + detour = path.get_nsteps();
> + }
> + if (pd != &from_port) {
> + get_path(from_port, *pd, path);
> + detour += path.get_nsteps();
> + }
> + assert(detour >= base_length);
> + detour -= base_length;
> + if (detour < shortest_detour) {
> + shortest_detour = detour;
> + best_index = index;
> + }
> + malus += pair.second;
> + iterator = pd;
> + ++index;
> + }
> + }
> + if (shortest_detour * malus * best_index <= direct_route * destpair.second * total_items) {
> + ship.push_destination(game, *destpair.first);
> + }
> + }
> }
>
> void Fleet::log_general_info(const EditorGameBase& egbase) const {
>
> === modified file 'src/economy/portdock.cc'
> --- src/economy/portdock.cc 2019-07-01 14:58:07 +0000
> +++ src/economy/portdock.cc 2019-08-10 17:23:31 +0000
> @@ -118,7 +117,7 @@
> }
>
> uint32_t PortDock::get_need_ship() const {
> - return (waiting_.size() + (expedition_ready_ ? 20 : 0)) / (ships_coming_ + 1);
Would this be // Retunrm numer of ships needed to fullfill ports transportation requirements ?
And this magic 20 shoud perhpas be kExpedtionPriority or such?
> + return (waiting_.size() + (expedition_ready_ ? 20 : 0)) / (ships_coming_.size() + 1);
> }
>
> /**
> @@ -363,11 +370,55 @@
> }
> }
>
> - // Decide where the arrived ship will go next
> - PortDock* next_port = fleet_->find_next_dest(game, ship, *this);
> - if (next_port) {
> - // Unload any wares/workers onboard the departing ship which are not favored by next dest
> - ship.unload_unfit_items(game, *this, *next_port);
> + ship.pop_destination(game, *this);
> + fleet_->push_next_destinations(game, ship, *this);
> + if (ship.get_current_destination(game)) {
Please make this a function like pake_more_wares_into_Ship or such
> + uint32_t free_capacity = ship.descr().get_capacity() - ship.get_nritems();
> + std::unordered_map<const PortDock*, bool> destination_check;
> + for (auto it = waiting_.begin(); it != waiting_.end() && free_capacity;) {
> + const PortDock* dest = it->get_destination(game);
> + assert(dest);
> + assert(dest != this);
> + // Decide whether to load this item
> + bool load;
> + auto dc = destination_check.find(dest);
> + if (dc != destination_check.end()) {
> + load = dc->second;
> + } else {
> + int32_t time = ship.estimated_arrival_time(game, *dest);
> + Path direct_route;
> + fleet_->get_path(*this, *dest, direct_route);
> + if (time < 0) {
> + time = direct_route.get_nsteps();
> + }
> + for (Ship* s : ships_coming_) {
> + int32_t t = s->estimated_arrival_time(game, *dest, this);
> + if (t < 0) {
> + // The ship is not planning to go there yet, perhaps we can ask for a detour?
> + t = s->estimated_arrival_time(game, *this);
> + assert(t >= 0);
> + assert(s->count_destinations() >= 1);
> + if (time > t + static_cast<int32_t>(direct_route.get_nsteps() * s->count_destinations())) {
> + time = -1;
> + break;
> + }
> + } else if (t < time) {
> + // A ship is coming that is planning to visit the ware's destination sooner than this one
> + time = -1;
> + break;
> + }
> + }
> + load = time >= 0;
> + destination_check.emplace(dest, load);
> + }
> + if (load) {
> + ship.add_item(game, *it);
> + it = waiting_.erase(it);
> + --free_capacity;
> + } else {
> + ++it;
> + }
> + }
> }
> #ifndef NDEBUG
> else {
>
> === 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-08-10 17:23:31 +0000
> @@ -736,22 +736,214 @@
> }
> }
>
> +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) {
> + 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) {
> + 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_;
> + 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) {
> + assert(old_index < nr_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 arbitarry 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
> + * to visit the given intermediate portdock earlier thaan the destination.
typo
> + */
> +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) {
> + 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 requested to review the proposed merge of lp:~widelands-dev/widelands/new-shipping into lp:widelands.
References
