widelands-dev team mailing list archive

[Teppo Mäenpää <tm@xxxxxx>]

Teppo Mäenpää has proposed merging lp:~widelands-dev/widelands/bug-1574379-forester-wit into lp:widelands.

Requested reviews:
  Widelands Developers (widelands-dev)
Related bugs:
  Bug #1574379 in widelands: "Forester plants trees where probability to grow is nearly zero"
  https://bugs.launchpad.net/widelands/+bug/1574379

For more details, see:
https://code.launchpad.net/~widelands-dev/widelands/bug-1574379-forester-wit/+merge/336068

Previously, forester picked a random free spot at his work area, and attempted to plant a tree there.

After the change, the forester picks n free slots (the number n can be selected separately for each tribe), and plants a tree to the spot which is best suited for the three that grows best at that spot.

In short: foresters favor areas which are suitable for forestation.
-- 
Your team Widelands Developers is requested to review the proposed merge of lp:~widelands-dev/widelands/bug-1574379-forester-wit into lp:widelands.

=== modified file 'data/tribes/workers/atlanteans/forester/init.lua'
--- data/tribes/workers/atlanteans/forester/init.lua	2017-02-12 09:10:57 +0000
+++ data/tribes/workers/atlanteans/forester/init.lua	2018-01-13 09:57:39 +0000
@@ -41,7 +41,7 @@
 
    programs = {
       plant = {
-         "findspace size:any radius:5 avoid:field",
+         "findspace size:any radius:5 avoid:field saplingsearches:12",
          "walk coords",
          "animation dig 2000", -- Play a planting animation
          "animation planting 1000", -- Play a planting animation

=== modified file 'data/tribes/workers/barbarians/ranger/init.lua'
--- data/tribes/workers/barbarians/ranger/init.lua	2017-02-12 09:10:57 +0000
+++ data/tribes/workers/barbarians/ranger/init.lua	2018-01-13 09:57:39 +0000
@@ -41,7 +41,7 @@
 
    programs = {
       plant = {
-         "findspace size:any radius:5 avoid:field",
+         "findspace size:any radius:5 avoid:field saplingsearches:5",
          "walk coords",
          "animation dig 2000",
          "animation planting 1000",

=== modified file 'data/tribes/workers/empire/forester/init.lua'
--- data/tribes/workers/empire/forester/init.lua	2017-02-12 09:10:57 +0000
+++ data/tribes/workers/empire/forester/init.lua	2018-01-13 09:57:39 +0000
@@ -41,7 +41,7 @@
 
    programs = {
       plant = {
-         "findspace size:any radius:5 avoid:field",
+         "findspace size:any radius:5 avoid:field saplingsearches:8",
          "walk coords",
          "animation dig 2000",
          "animation planting 1000",

=== modified file 'src/logic/game.h'
--- src/logic/game.h	2017-12-19 07:12:18 +0000
+++ src/logic/game.h	2018-01-13 09:57:39 +0000
@@ -251,6 +251,10 @@
 	void accept_trade(int trade_id);
 	void cancel_trade(int trade_id);
 
+	// TODO(kxq): The lifetime of game-instance is okay for this, but is this the right spot?
+	// TODO(kxq): I should find the place where LUA changes map, and clear this whenever that happens.
+	std::vector<int16_t> forester_cache_;
+
 private:
 	void sync_reset();
 

=== modified file 'src/logic/map_objects/tribes/worker.cc'
--- src/logic/map_objects/tribes/worker.cc	2017-11-12 08:59:45 +0000
+++ src/logic/map_objects/tribes/worker.cc	2018-01-13 09:57:39 +0000
@@ -419,6 +419,82 @@
 }
 
 /**
+ * findspace_helper_for_forester
+ *
+ * Making the run_findspace routine shorter, by putting one special case into its own function.
+ * This gets called many times each time the forester searches for a place for a sapling.
+ * Since this already contains three nested for-loops, I dedided to cache the values for a
+ * cpu/memory tradeoff (hint: Widelands is pretty heavy on my oldish PC).
+ * Since the implementation details of double could vary between platforms, I decided to
+ * quantize the terrain goodness into int16_t. This lowers the footprint of the caching,
+ * and also makes desyncs caused by different floats horribly unlikely.
+ *
+ * At the moment of writing, map changing is really infrequent (only in two scenarios)
+ * and even those do not affect this. However, since map changes are possible, this
+ * checks the reliability of the cached value with a small probability (~1%), If a
+ * disparency is found, the entire cache is nuked.
+ *
+ * If somebody in the future makes a scenario, where the land first is barren, and then
+ * spots of eden show up, the foresters will not immediately notice (because of the cache).
+ * They will eventually notice, and since the instance is shared between tribes,
+ * all foresters notice this at the same moment. I hope this is okay.
+ *
+ */
+
+int16_t Worker::findspace_helper_for_forester(const Coords& pos, const Map& map, Game& game) {
+
+	const MapIndex mi = map.get_index(pos, map.get_width());
+	const FCoords fpos = map.get_fcoords(pos);
+	const unsigned vecsize = 1 + unsigned(map.max_index());
+	// This if-statement should be true only once per game.
+	if (vecsize != game.forester_cache_.size()) {
+		game.forester_cache_.resize (vecsize, -1);
+	}
+	bool x_check = false;
+	if (-1 < game.forester_cache_[mi]) {
+		if (0 == ((game.logic_rand()) & 0xfc)) {
+			// Cached value found, but exceptionally not trusted.
+			x_check = true;
+		} else {
+			// Found the terrain forestability, no more work to do
+			return game.forester_cache_[mi];
+		}
+	}
+
+	// Okay, I do not know whether this terrain suits. Let's obtain the value (and then cache it)
+
+	const DescriptionMaintainer<ImmovableDescr>& immovables = game.world().immovables();
+
+	// TODO(kxq): could the tree_sapling come from config? Currently, there is only one sparam..
+	const uint32_t attribute_id = ImmovableDescr::get_attribute_id("tree_sapling");
+
+	double best = 0;
+	for (DescriptionIndex i = 0; i < immovables.size(); ++i) {
+		const ImmovableDescr& immovable_descr = immovables.get(i);
+		if (!immovable_descr.has_attribute(attribute_id)) {
+			continue;
+		}
+		if (immovable_descr.has_terrain_affinity()) {
+			double probability = probability_to_grow(
+			immovable_descr.terrain_affinity(), fpos, map, game.world().terrains());
+			if (probability > best) {
+				best = probability;
+			}
+		}
+	}
+	// quantize the obtained value
+        const int16_t correct_val = (std::numeric_limits<int16_t>::max() -1) * best;
+
+	if (x_check && (correct_val != game.forester_cache_[mi])) {
+		game.forester_cache_.clear();
+		game.forester_cache_.resize (vecsize, -1);
+	}
+	game.forester_cache_[mi] = correct_val;
+	return game.forester_cache_[mi];
+}
+
+
+/**
  * findspace key:value key:value ...
  *
  * Find a node based on a number of predicates.
@@ -557,6 +633,22 @@
 	// Pick a location at random
 	state.coords = list[game.logic_rand() % list.size()];
 
+	// Special case: forester checks multiple locations instead of one.
+	if (1 < action.iparam6) {
+		// In the bug comments, somebody asked for unequal quality for the foresters of various tribes to find the best spot.
+		// Here stubborness is the number of slots to consider.
+		int stubborness = action.iparam6;
+		int16_t best = findspace_helper_for_forester(state.coords, map, game);
+		while (1 < stubborness--) {
+			const Coords altpos = list[game.logic_rand() % list.size()];
+			const int16_t alt_pos_goodness = findspace_helper_for_forester(altpos, map, game);
+			if (alt_pos_goodness > best) {
+				best = alt_pos_goodness;
+				state.coords = altpos;
+			}
+		}
+	}
+
 	++state.ivar1;
 	schedule_act(game, 10);
 	return true;
@@ -728,6 +820,7 @@
 	// multiplayer.
 	std::set<std::tuple<double, DescriptionIndex>> best_suited_immovables_index;
 
+
 	// Checks if the 'immovable_description' has a terrain_affinity, if so use it. Otherwise assume
 	// it
 	// to be 1. (perfect fit). Adds it to the best_suited_immovables_index.

=== modified file 'src/logic/map_objects/tribes/worker.h'
--- src/logic/map_objects/tribes/worker.h	2017-11-26 14:44:23 +0000
+++ src/logic/map_objects/tribes/worker.h	2018-01-13 09:57:39 +0000
@@ -65,6 +65,7 @@
 		int32_t iparam3;
 		int32_t iparam4;
 		int32_t iparam5;
+		int32_t iparam6;
 		std::string sparam1;
 
 		std::vector<std::string> sparamv;
@@ -258,6 +259,9 @@
 	bool run_play_sound(Game&, State&, const Action&);
 	bool run_construct(Game&, State&, const Action&);
 
+	// helper function
+	int16_t findspace_helper_for_forester(const Coords& pos, const Map& map, Game& game);
+  
 	OPtr<PlayerImmovable> location_;   ///< meta location of the worker
 	Economy* economy_;                 ///< economy this worker is registered in
 	OPtr<WareInstance> carried_ware_;  ///< ware we are carrying

=== modified file 'src/logic/map_objects/tribes/worker_program.cc'
--- src/logic/map_objects/tribes/worker_program.cc	2017-08-30 11:58:41 +0000
+++ src/logic/map_objects/tribes/worker_program.cc	2018-01-13 09:57:39 +0000
@@ -423,6 +423,7 @@
  * iparam3 = whether the "space" flag is set
  * iparam4 = whether the "breed" flag is set
  * iparam5 = Immovable attribute id
+ * iparam6 = Forester retries
  * sparam1 = Resource
  */
 void WorkerProgram::parse_findspace(Worker::Action* act, const std::vector<std::string>& cmd) {
@@ -434,6 +435,7 @@
 	act->iparam3 = 0;
 	act->iparam4 = 0;
 	act->iparam5 = -1;
+	act->iparam6 =  1;
 	act->sparam1 = "";
 
 	// Parse predicates
@@ -476,6 +478,13 @@
 			act->iparam3 = 1;
 		} else if (key == "avoid") {
 			act->iparam5 = MapObjectDescr::get_attribute_id(value);
+		} else if (key == "saplingsearches") {
+			int ival = strtol(value.c_str(), nullptr, 10);
+			if (1 != act->iparam6 || 1 > ival) {
+				throw wexception("Findspace: Failed to reuse iparam5 %d %d %s", act->iparam5, ival, value.c_str());
+			} else {
+				act->iparam6 = ival;
+		 	}
 		} else
 			throw wexception("Bad findspace predicate %s:%s", key.c_str(), value.c_str());
 	}