widelands-dev team mailing list archive

[Benedikt Straub <benedikt-straub@xxxxxx>]

Thanks for reviewing :)
Implemented or replied to your comments.

I´ve been playing so far on Dust In The Wind where I didn´t notice performance problems (owning ~ half the islands). A big map with many many ports would be great for testing though.

This is sort of like the TSP with additional rules like "dynamic route lengths" (priority weights, esp. numbers of items). But since ships that already have destinations are highly penalized, they will be sifted out quickly and only ships with few destinations will be chosen; so although the recursion call is exponential, the recursion depth should likely always be shallow. (If you have just one ship for a hundred ports, new requests will be ignored for a while rather than assigned in a suboptimal way if your ship already has lots of destinations.)

> * be carefull not to use (local) timings as this depends on the CPU and may rsult in desyncs
I don´t understand, what do you mean by local timings?

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
> @@ -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;
> +	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);
> +	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) {
> +		Path path;
> +		get_path(from_port, *destpair.first, path);

This is already done like that, paths are calculated only the first time they´re needed

> +		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);

Yes, that´s the approximate number of ships needed. It is not accurate since it doesn´t account for ship capacity, free capacity etc. I inherited this code and it is working fairly well, so I didn´t change its logic…

> +	return (waiting_.size() + (expedition_ready_ ? 20 : 0)) / (ships_coming_.size() + 1);
>  }
>  
>  /**


-- 
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.