widelands-dev team mailing list archive

[ypopezios <ypopezios@xxxxxxxx>]

ypopezios has proposed merging lp:~widelands-dev/widelands/ship_scheduling_2 into lp:widelands.

Commit message:
Get windows builds and ask for testing.

Requested reviews:
  Widelands Developers (widelands-dev)

For more details, see:
https://code.launchpad.net/~widelands-dev/widelands/ship_scheduling_2/+merge/352335

See description of the branch:
https://code.launchpad.net/~widelands-dev/widelands/ship_scheduling_2
-- 
Your team Widelands Developers is requested to review the proposed merge of lp:~widelands-dev/widelands/ship_scheduling_2 into lp:widelands.

=== modified file 'src/economy/fleet.cc'
--- src/economy/fleet.cc	2018-04-07 16:59:00 +0000
+++ src/economy/fleet.cc	2018-08-04 06:22:49 +0000
@@ -637,9 +637,9 @@
 	act_pending_ = false;
 
 	if (!active()) {
-		// If we are here, most likely act() was called by a port with waiting wares or an expedition
-		// ready
-		// although there are still no ships. We can't handle it now, so we reschedule the act()
+		// If we are here, most likely act() was called by a port with waiting wares or
+		// with an expedition ready, although there are still no ships.
+		// We can't handle it now, so we reschedule the act()
 		schedule_act(game, 5000);  // retry in the next time
 		act_pending_ = true;
 		return;
@@ -647,212 +647,95 @@
 
 	molog("Fleet::act\n");
 
-	// we need to calculate what ship is to be send to which port
-	// for this we will have temporary data structure with format
-	// <<ship,port>,score>
-	// where ship and port are not objects but positions in ports_ and ships_
-	// this is to allow native hashing
-	std::map<std::pair<uint16_t, uint16_t>, uint16_t> scores;
-
-	// so we will identify all pairs: idle ship : ports, and score all such
-	// pairs. We consider
-	// - count of wares onboard, first ware (oldest) is counted as 8 (prioritization)
-	//   (counting wares for particular port only)
-	// - count wares waiting at the port/3
-	// - distance between ship and a port (0-10 points, the closer the more points)
-	// - is another ship heading there right now?
-
-	// at the end we must know if requrests of all ports asking for ship were addressed
-	// if any unsatisfied, we must schedule new run of this function
-	// when we send a ship there, the port is removed from list
+	// We need to calculate what ship is to be sent to which port,
+	// so we will score all pairs: idle ship : port.
+	// For the score of each pair, we consider:
+	// - count of wares onboard that ship for that port
+	// - count of wares waiting at that port
+	// - distance between that ship and that port
+
+	// At the end we must know if the request of any port for a ship
+	// is still unsatisfied, to schedule new run of this function.
+	// This list holds all waiting ports and we remove every port where we send a ship.
 	std::list<uint16_t> waiting_ports;
-
-	// this is just helper - first member of scores map
-	std::pair<uint16_t, uint16_t> mapping;  // ship number, port number
-
-	// first we go over ships - idle ones (=without destination)
-	// then over wares on these ships and create first ship-port
-	// pairs with score
-	for (uint16_t s = 0; s < ships_.size(); s += 1) {
-		if (ships_[s]->get_destination(game)) {
-			continue;
-		}
-		if (ships_[s]->get_ship_state() != Ship::ShipStates::kTransport) {
+	for (uint16_t pi = 0; pi < ports_.size(); ++pi) {
+		if (ports_[pi]->get_need_ship()) {
+			waiting_ports.push_back(pi);
+		}
+	}
+
+	for (Ship* s : ships_) {
+		if (s->get_destination(game)) {
+			continue; // has already destination
+		}
+		if (s->get_ship_state() != Ship::ShipStates::kTransport) {
 			continue;  // in expedition obviously
 		}
-
-		for (uint16_t i = 0; i < ships_[s]->get_nritems(); i += 1) {
-			PortDock* dst = ships_[s]->items_[i].get_destination(game);
-			if (!dst) {
-				// if wares without destination on ship without destination
-				// such ship can be send to any port, and should be sent
-				// to some port, so we add 1 point to score for each port
-				for (uint16_t p = 0; p < ports_.size(); p += 1) {
-					mapping.first = s;
-					mapping.second = p;
-					scores[mapping] += 1;
-				}
-				continue;
-			}
-
-			bool destination_found = false;  // Just a functional check
-			for (uint16_t p = 0; p < ports_.size(); p += 1) {
-				if (ports_[p] == ships_[s]->items_[i].get_destination(game)) {
-					mapping.first = s;
-					mapping.second = p;
-					scores[mapping] += (i == 0) ? 8 : 1;
-					destination_found = true;
-				}
-			}
-			if (!destination_found) {
-				// Perhaps the throw here is too strong
-				// we can still remove it before stable release if it proves too much
-				// during my testing this situation never happened
-				throw wexception("A ware with destination that does not match any of player's"
-				                 " ports, ship %u, ware's destination: %u",
-				                 ships_[s]->serial(),
-				                 ships_[s]->items_[i].get_destination(game)->serial());
-			}
-		}
-	}
-
-	// now opposite aproach - we go over ports to find out those that have wares
-	// waiting for ship then find candidate ships to satisfy the requests
-	for (uint16_t p = 0; p < ports_.size(); p += 1) {
-		PortDock& pd = *ports_[p];
-		if (!pd.get_need_ship()) {
-			continue;
-		}
-
-		// general stategy is "one ship for port is enough", but sometimes
-		// amount of ware waiting for ship is too high
-		if (count_ships_heading_here(game, &pd) * 25 > pd.count_waiting()) {
-			continue;
-		}
-
-		waiting_ports.push_back(p);
-
-		// scoring and entering the pair into scores (or increasing existing
-		// score if the pair is already there)
-		for (uint16_t s = 0; s < ships_.size(); s += 1) {
-
-			if (ships_[s]->get_destination(game)) {
-				continue;  // already has destination
-			}
-
-			if (ships_[s]->get_ship_state() != Ship::ShipStates::kTransport) {
-				continue;  // in expedition obviously
-			}
-
-			mapping.first = s;
-			mapping.second = p;
-			// following aproximately considers free capacity of a ship
-			scores[mapping] += ((ships_[s]->get_nritems() > 15) ? 1 : 3) +
-			                   std::min(ships_[s]->descr().get_capacity() - ships_[s]->get_nritems(),
-			                            ports_[p]->count_waiting()) /
-			                      3;
-		}
-	}
-
-	// Now adding score for distance
-	for (auto ship_port_relation : scores) {
-
-		// here we get distance ship->port
-		// possibilities are:
-		// - we are in port and it is the same as target port
-		// - we are in other port, then we use get_dock() function to fetch precalculated path
-		// - if above fails, we calculate path "manually"
-		int16_t route_length = -1;
-
-		PortDock* current_portdock =
-		   get_dock(game, ships_[ship_port_relation.first.first]->get_position());
-
-		if (current_portdock) {  // we try to use precalculated paths of game
-
-			// we are in the same portdock
-			if (current_portdock == ports_[ship_port_relation.first.second]) {
-				route_length = 0;
-			} else {  // it is different portdock then
-				Path tmp_path;
-				if (get_path(*current_portdock, *ports_[ship_port_relation.first.second], tmp_path)) {
-					route_length = tmp_path.get_nsteps();
-				}
-			}
-		}
-
-		// most probably the ship is not in a portdock (should not happen frequently)
-		if (route_length == -1) {
-			route_length = ships_[ship_port_relation.first.first]->calculate_sea_route(
-			   game, *ports_[ship_port_relation.first.second]);
-		}
-
-		// now we have length of route, so we need to calculate score
-		int16_t score_for_distance = 0;
-		if (route_length < 3) {
-			score_for_distance = 10;
-		} else {
-			score_for_distance = 8 - route_length / 50;
-		}
-		// must not be negative
-		score_for_distance = (score_for_distance < 0) ? 0 : score_for_distance;
-
-		scores[ship_port_relation.first] += score_for_distance;
-	}
-
-	// looking for best scores and sending ships accordingly
-	uint16_t best_ship = 0;
-	uint16_t best_port = 0;
-
-	// after sending a ship we will remove one or more items from scores
-	while (!scores.empty()) {
-		uint16_t best_score = 0;
-
-		// searching for combination with highest score
-		for (const auto& combination : scores) {
-			if (combination.second > best_score) {
-				best_score = combination.second;
-				best_ship = combination.first.first;
-				best_port = combination.first.second;
-			}
-		}
-		if (best_score == 0) {
-			// this is check of correctnes of this algorithm, this should not happen
-			throw wexception("Fleet::act(): No port-destination pair selected or its score is zero");
-		}
-
-		// making sure the winner has no destination set
-		assert(!ships_[best_ship]->get_destination(game));
-
-		// now actual setting destination for "best ship"
-		ships_[best_ship]->set_destination(game, *ports_[best_port]);
+		uint32_t const max_capacity = s->descr().get_capacity();
+		
+		float best_score = 0;
+		uint16_t best_pi; // best port's index
+
+		for (uint16_t pi = 0; pi < ports_.size(); ++pi) {
+			PortDock* p = ports_[pi];
+			if (!p->get_need_ship() && !s->get_nritems()) {
+				continue; // empty ship to empty port
+			}
+			
+			uint16_t items_count = 0;
+			for (uint16_t i = 0; i < s->get_nritems(); ++i) {
+				PortDock* dst = s->items_[i].get_destination(game);
+				if (p == dst) {
+					++items_count;
+				}
+			}
+
+			// here we get distance ship->port
+			// possibilities are:
+			// - we are in port and it is the same as target port
+			// - we are in other port, then we use get_dock() function to fetch precalculated path
+			// - if above fails, we calculate path "manually"
+			int16_t route_length = -1;
+
+			PortDock* current_portdock = get_dock(game, s->get_position());
+			if (current_portdock) {  // we try to use precalculated paths of game
+
+				if (current_portdock == p) {
+					// we are in the same portdock
+					route_length = 0;
+				} else {
+					// we are in a different portdock
+					Path tmp_path;
+					if (get_path(*current_portdock, *p, tmp_path)) {
+						route_length = tmp_path.get_nsteps();
+					}
+				}
+			}
+
+			if (route_length == -1) {
+				// most probably the ship is not in a portdock (should not happen frequently)
+				route_length = s->calculate_sea_route(game, *p);
+			}
+
+			float score = (items_count + 1) * (items_count + std::min(max_capacity, p->count_waiting()));
+			score = score * (1 - route_length / (score + route_length));
+			if (score > best_score) {
+				best_score = score;
+				best_pi = pi;
+			}
+		}
+
+		if (best_score <= 0) {
+			continue; // no need to move this ship
+		}
+
+		// now actual setting destination for ship
+		PortDock* best_port = ports_[best_pi];
+		s->set_destination(game, *best_port);
 		molog("... ship %u sent to port %u, wares onboard: %2d, the port is asking for a ship: %s\n",
-		      ships_[best_ship]->serial(), ports_[best_port]->serial(),
-		      ships_[best_ship]->get_nritems(), (ports_[best_port]->get_need_ship()) ? "yes" : "no");
-
-		// pruning the scores table
-		// the ship that was just sent somewhere cannot be send elsewhere :)
-		for (auto it = scores.cbegin(); it != scores.cend();) {
-
-			// decreasing score for target port as there was a ship just sent there
-			if (it->first.second == best_port) {
-				mapping.first = it->first.first;
-				mapping.second = it->first.second;
-				scores[mapping] /= 2;
-				// just make sure it is nonzero
-				scores[mapping] = (scores[mapping] == 0) ? 1 : scores[mapping];
-			}
-
-			// but removing all pairs where best ship is participating as it is not available anymore
-			// (because it was sent to "best port")
-			if (it->first.first == best_ship) {
-				scores.erase(it++);
-			} else {
-				++it;
-			}
-		}
-
-		// also removing the port from waiting_ports
-		waiting_ports.remove(best_port);
+		      s->serial(), best_port->serial(), s->get_nritems(), best_port->get_need_ship() ? "yes" : "no");
+
+		waiting_ports.remove(best_pi); // remove the port from waiting_ports. see right below
 	}
 
 	if (!waiting_ports.empty()) {