widelands-dev team mailing list archive

[GunChleoc <fios@xxxxxxxxxxxxxxxxxxx>]

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.