widelands-dev team mailing list archive

[TiborB <tiborb95@xxxxxxxxx>]

TiborB has proposed merging lp:~widelands-dev/widelands/request_supply_opt into lp:widelands.

Requested reviews:
  Widelands Developers (widelands-dev)

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

This is small redesign of delivery of wares to requestors.
1. Engine now evenly distributes wares to all warehouses that are preferred for this type of ware (in other words, ware goes to a warehouse with lower stock of the material/worker)
2. Engine now test supplies in order starting from nearest one. This itself should lead to lesser computation. Additionaly I implemented a treshold (now 5) that test only 5 nearest supplies. The goal is to reduce CPU usage, especially on big maps. Routing is very expensive on long maps. 

This was discussed on forum and must be yet considered.
-- 
Your team Widelands Developers is requested to review the proposed merge of lp:~widelands-dev/widelands/request_supply_opt into lp:widelands.

=== modified file 'src/economy/economy.cc'
--- src/economy/economy.cc	2015-11-11 09:52:55 +0000
+++ src/economy/economy.cc	2015-12-10 20:19:31 +0000
@@ -38,6 +38,9 @@
 #include "logic/tribes/tribe_descr.h"
 #include "logic/warehouse.h"
 
+// To speed up searching for nearest supply, we check only n nearest supplies
+constexpr int kSuppliesToCheck = 5;
+
 namespace Widelands {
 
 Economy::Economy(Player & player) :
@@ -664,14 +667,38 @@
 	Route  * best_route  = nullptr;
 	int32_t  best_cost   = -1;
 	Flag & target_flag = req.target_flag();
+	Map & map = game.map();
+
+	available_supplies.clear();
 
 	for (size_t i = 0; i < m_supplies.get_nrsupplies(); ++i) {
 		Supply & supp = m_supplies[i];
 
-		// Check requirements
+		// Just skip if supply does not provide required ware
 		if (!supp.nr_supplies(game, req))
 			continue;
 
+		const uint32_t dist = map.calc_distance(
+			target_flag.get_position(),
+			supp.get_position(game)->base_flag().get_position());
+
+		// Inserting into 'queue'
+		if (available_supplies.count(dist) == 0) {
+			available_supplies[dist] = &m_supplies[i];
+		}
+	}
+
+	// Now available supplies are sorted by distance to requestor
+	// And we will check only first n (kSuppliesToCheck) from them
+	uint16_t counter = 0;
+	for (auto& supplypair : available_supplies) {
+
+		if (++counter > kSuppliesToCheck) {
+			break;
+		}
+
+		Supply & supp = *supplypair.second;
+
 		Route * const route =
 			best_route != &buf_route0 ? &buf_route0 : &buf_route1;
 		// will be cleared by find_route()
@@ -685,11 +712,17 @@
 			 	 req.get_type(),
 			 	 best_cost))
 		{
-			if (!best_route)
-			log ("Economy::find_best_supply: Error, COULD NOT FIND A ROUTE!");
+			if (!best_route) {
+				log ("Economy::find_best_supply: Error, COULD NOT FIND A ROUTE!");
+				// To help to debug this a bit:
+				log (" ... ware at: %3dx%3d, requestor at: %3dx%3d!",
+					supp.get_position(game)->base_flag().get_position().x,
+					supp.get_position(game)->base_flag().get_position().y,
+					target_flag.get_position().x,
+					target_flag.get_position().y);
+			}
 			continue;
 		}
-
 		best_supply = &supp;
 		best_route = route;
 		best_cost = route->get_totalcost();
@@ -813,7 +846,7 @@
 			 !_has_request(*rsp.request) ||
 			 !rsp.supply->nr_supplies(game, *rsp.request))
 		{
-			rsps.nexttimer = 200;
+			rsps.nexttimer = 250;
 			continue;
 		}
 
@@ -822,11 +855,12 @@
 
 		//  for multiple wares
 		if (rsp.request && _has_request(*rsp.request))
-			rsps.nexttimer = 200;
+			rsps.nexttimer = 250;
 	}
 
-	if (rsps.nexttimer > 0) //  restart the timer, if necessary
+	if (rsps.nexttimer > 0) { //  restart the timer, if necessary
 		_start_request_timer(rsps.nexttimer);
+	}
 }
 
 
@@ -1037,12 +1071,30 @@
 
 		bool haveprefer = false;
 		bool havenormal = false;
+
+		// One of preferred warehouses (if any) with lowest stock of ware/worker
+		Warehouse * preferred_wh = nullptr;
+		// Stock of particular ware in preferred warehouse
+		uint32_t preferred_wh_stock = std::numeric_limits<uint32_t>::max();
+
 		for (uint32_t nwh = 0; nwh < m_warehouses.size(); ++nwh) {
 			Warehouse * wh = m_warehouses[nwh];
 			Warehouse::StockPolicy policy = wh->get_stock_policy(type, ware);
 			if (policy == Warehouse::SP_Prefer) {
 				haveprefer = true;
-				break;
+
+				// Getting count of worker/ware
+				uint32_t current_stock;
+				if (type == WareWorker::wwWARE) {
+					current_stock = wh->get_wares().stock(ware);
+				} else {
+					current_stock = wh->get_workers().stock(ware);
+				}
+				// Stocks lower then in previous one?
+				if (current_stock < preferred_wh_stock) {
+					preferred_wh = wh;
+					preferred_wh_stock = current_stock;
+				}
 			}
 			if (policy == Warehouse::SP_Normal)
 				havenormal = true;
@@ -1050,17 +1102,22 @@
 		if (!havenormal && !haveprefer && type == wwWARE)
 			continue;
 
-		Warehouse * wh = find_closest_warehouse
-			(supply.get_position(game)->base_flag(), type, nullptr, 0,
-			 (!haveprefer && !havenormal)
-			 ?
-			 WarehouseAcceptFn()
-			 :
-			 boost::bind
-				(&accept_warehouse_if_policy,
-				 _1, type, ware,
-				 haveprefer ? Warehouse::SP_Prefer : Warehouse::SP_Normal));
-
+		// We either have one preferred warehouse picked up or walk on roads to find nearest one
+		Warehouse * wh = nullptr;
+		if (preferred_wh) {
+			wh = preferred_wh;
+		} else {
+			wh = find_closest_warehouse
+				(supply.get_position(game)->base_flag(), type, nullptr, 0,
+				 (!havenormal)
+				 ?
+				 WarehouseAcceptFn()
+				 :
+				 boost::bind
+					(&accept_warehouse_if_policy,
+					 _1, type, ware,
+					 Warehouse::SP_Normal));
+		}
 		if (!wh) {
 			log
 				("Warning: Economy::_handle_active_supplies "

=== modified file 'src/economy/economy.h'
--- src/economy/economy.h	2015-11-11 09:52:55 +0000
+++ src/economy/economy.h	2015-12-10 20:19:31 +0000
@@ -194,7 +194,7 @@
 	void _check_splits();
 	void _split(const std::set<OPtr<Flag> > &);
 
-	void _start_request_timer(int32_t delta = 200);
+	void _start_request_timer(int32_t delta = 500);
 
 	Supply * _find_best_supply(Game &, const Request &, int32_t & cost);
 	void _process_requests(Game &, RSPairStruct &);
@@ -237,6 +237,12 @@
 	static std::unique_ptr<Soldier> m_soldier_prototype;
 	UI::UniqueWindow::Registry m_optionswindow_registry;
 
+	// Map of Distance:Supply pairs
+	// Distance is meant map distance supply<->request
+	// Used to speed up _find_best_supply function, it is convenient to start testing routes from
+	// nearest supplies
+	std::map<uint32_t, Supply*> available_supplies;
+
 	DISALLOW_COPY_AND_ASSIGN(Economy);
 };