Merge lp:~widelands-dev/widelands/allows_seafaring_performance into lp:widelands

[GunChleoc]

Only recalculate whether a map allows seafaring when something has changed

- New function Map::recalculate_allows_seafaring()
- Map::allows_seafaring() is recalculated:
  - On map load
  - On editor save
  - When a port space is changed via Lua scripting
  - When it is triggered by LuaMap::recalculate_seafaring() or recalculate()
- Added test
- Some documentation tweaks to lua_map.cc.
- Fixed the check for invalid terrains in LuaField::get_terr.

Only recalculate whether a map allows seafaring when something has changed. This new design is a bit more fragile, but I think the performance gain is worth it, because the AI needs this function.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 3369. State: passed. Details: https://travis-ci.org/widelands/widelands/builds/364989186.
Appveyor build 3175. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_allows_seafaring_performance-3175.

[Klaus Halfmann (klaus-halfmann)]

This is a prerequisite for the smaller_building_statistics branch.
checking this out now ...

Code is reasonable.

As this change carries its own testcase it can go in
once the test works for me.

[GunChleoc (gunchleoc)]

Thanks for the review :)

Can you trigger the merge once your testing is done?

[Klaus Halfmann (klaus-halfmann)]

allows_seafaring_performance$ ./regression_test.py -b ./widelands
...
test/maps/two_ponds.wmf/scripting/test_seafaring.lua ...
  Running Widelands ... done.
  Loading savegame: port_spaces ... done.
ok
...
Ran 41 tests in 1204.108s

@bunnybot merge

review: Approve (review, compile, automated test)

[kaputtnik (franku)]

wow, finally i can play debug builds again without stuttering, even on big maps.

Thanks :-)

=== modified file 'src/logic/map.cc'
--- src/logic/map.cc	2018-04-07 16:59:00 +0000
+++ src/logic/map.cc	2018-04-11 07:16:58 +0000
@@ -70,7 +70,8 @@
      scenario_types_(NO_SCENARIO),
      width_(0),
      height_(0),
-     pathfieldmgr_(new PathfieldManager) {
+     pathfieldmgr_(new PathfieldManager),
+	  allows_seafaring_(false) {
 }
 
 Map::~Map() {
@@ -157,6 +158,7 @@
 			f = get_fcoords(Coords(x, y));
 			recalc_nodecaps_pass2(world, f);
 		}
+	recalculate_allows_seafaring();
 }
 
 void Map::recalc_default_resources(const World& world) {
@@ -278,6 +280,7 @@
 	objectives_.clear();
 
 	port_spaces_.clear();
+	allows_seafaring_ = false;
 
 	// TODO(meitis): should be done here ... but WidelandsMapLoader::preload_map calls
 	// this cleanup AFTER assigning filesystem_ in WidelandsMapLoader::WidelandsMapLoader
@@ -1316,7 +1319,7 @@
 	return port_spaces_.count(c);
 }
 
-bool Map::set_port_space(const World& world, const Coords& c, bool set, bool force) {
+bool Map::set_port_space(const World& world, const Coords& c, bool set, bool force, bool recalculate_seafaring) {
 	bool success = false;
 	if (set) {
 		success = force || is_port_space_allowed(world, get_fcoords(c));
@@ -1327,6 +1330,9 @@
 		port_spaces_.erase(c);
 		success = true;
 	}
+	if (recalculate_seafaring) {
+		recalculate_allows_seafaring();
+	}
 	return success;
 }
 
@@ -1973,10 +1979,16 @@
 }
 
 bool Map::allows_seafaring() const {
+	return allows_seafaring_;
+}
+
+// This check can become very expensive, so we only recalculate this on relevant map changes.
+void Map::recalculate_allows_seafaring() {
 
 	// There need to be at least 2 port spaces for seafaring to make sense
 	if (get_port_spaces().size() < 2) {
-		return false;
+		allows_seafaring_ = false;
+		return;
 	}
 
 	std::set<Coords> reachable_from_previous_ports;
@@ -2000,7 +2012,8 @@
 
 			// Found one
 			if (reachable_from_previous_ports.count(current_position) > 0) {
-				return true;
+				allows_seafaring_ = true;
+				return;
 			}
 
 			// Adding the neighbors to the list
@@ -2021,7 +2034,7 @@
 			reachable_from_previous_ports.insert(reachable_coord);
 		}
 	}
-	return false;
+	allows_seafaring_ = false;
 }
 
 void Map::cleanup_port_spaces(const World& world) {
@@ -2031,6 +2044,7 @@
 			continue;
 		}
 	}
+	recalculate_allows_seafaring();
 }
 
 bool Map::has_artifacts() {

=== modified file 'src/logic/map.h'
--- src/logic/map.h	2018-04-07 16:59:00 +0000
+++ src/logic/map.h	2018-04-11 07:16:58 +0000
@@ -408,7 +408,8 @@
 	/***
 	 * Changes the given triangle's terrain. This happens in the editor and might
 	 * happen in the game too if some kind of land increasement is implemented (like
-	 * drying swamps). The nodecaps need to be recalculated
+	 * drying swamps). The nodecaps need to be recalculated. If terrain was changed from
+	 * or to water, we need to recalculate_allows_seafaring too, depending on the situation.
 	 *
 	 * @return the radius of changes.
 	 */
@@ -448,14 +449,16 @@
 	/// 'force' sets the port space even if it isn't viable, and is to be used for map loading only.
 	/// Returns whether the port space was set/unset successfully.
 	bool
-	set_port_space(const World& world, const Widelands::Coords& c, bool set, bool force = false);
+	set_port_space(const World& world, const Widelands::Coords& c, bool set, bool force = false, bool recalculate_seafaring = false);
 	const PortSpacesSet& get_port_spaces() const {
 		return port_spaces_;
 	}
 	std::vector<Coords> find_portdock(const Widelands::Coords& c) const;
 
-	/// Check whether there are at least 2 port spaces that can be reached from each other by water
+	/// Return true if there are at least 2 port spaces that can be reached from each other by water
 	bool allows_seafaring() const;
+	/// Calculate whether there are at least 2 port spaces that can be reached from each other by water and set the allows_seafaring property
+	void recalculate_allows_seafaring();
 	/// Remove all port spaces that are not valid (Buildcap < big or not enough space for a
 	/// portdock).
 	void cleanup_port_spaces(const World& world);
@@ -518,6 +521,8 @@
 	std::unique_ptr<FileSystem> filesystem_;
 
 	PortSpacesSet port_spaces_;
+	bool allows_seafaring_;
+
 	Objectives objectives_;
 
 	MapVersion map_version_;

=== modified file 'src/map_io/s2map.cc'
--- src/map_io/s2map.cc	2018-04-07 16:59:00 +0000
+++ src/map_io/s2map.cc	2018-04-11 07:16:58 +0000
@@ -1065,4 +1065,5 @@
 			log("SUCCESS! Port buildspace set for (%i, %i) \n", fc.x, fc.y);
 		}
 	}
+	map_.recalculate_allows_seafaring();
 }

=== modified file 'src/scripting/lua_map.cc'
--- src/scripting/lua_map.cc	2018-04-07 16:59:00 +0000
+++ src/scripting/lua_map.cc	2018-04-11 07:16:58 +0000
@@ -1145,6 +1145,7 @@
 const char LuaMap::className[] = "Map";
 const MethodType<LuaMap> LuaMap::Methods[] = {
    METHOD(LuaMap, place_immovable), METHOD(LuaMap, get_field), METHOD(LuaMap, recalculate),
+	METHOD(LuaMap, recalculate_seafaring),
    METHOD(LuaMap, set_port_space),  {nullptr, nullptr},
 };
 const PropertyType<LuaMap> LuaMap::Properties[] = {
@@ -1170,8 +1171,7 @@
 /* RST
    .. attribute:: allows_seafaring
 
-      (RO) Whether the map currently allows seafaring. This will calculate a path between port spaces,
-		so it's more accurate but less efficient than :any:`number_of_port_spaces`.
+      (RO) Whether the map currently allows seafaring.
 
 		:returns: True if there are at least two port spaces that can be reached from each other.
 */
@@ -1182,9 +1182,7 @@
 /* RST
    .. attribute:: number_of_port_spaces
 
-      (RO) The amount of port spaces on the map. If this is >= 2, one can assume that the map
-      allows seafaring. This is checked very quickly and is more efficient than :any:`allows_seafaring`,
-      but it won't detect whether the port spaces can be reached from each other, so it's less accurate.
+      (RO) The amount of port spaces on the map.
 
       :returns: An integer with the number of port spaces.
 */
@@ -1312,9 +1310,9 @@
 /* RST
    .. method:: recalculate()
 
-      This map recalculates the whole map state: height of fields, buildcaps
-      and so on. You only need to call this function if you changed
-      Field.raw_height in any way.
+      This map recalculates the whole map state: height of fields, buildcaps,
+      whether the map allows seafaring and so on. You only need to call this
+      function if you changed :any:`raw_height` in any way.
 */
 // TODO(unknown): do we really want this function?
 int LuaMap::recalculate(lua_State* L) {
@@ -1324,6 +1322,18 @@
 }
 
 /* RST
+   .. method:: recalculate_seafaring()
+
+      This method recalculates whether the map allows seafaring.
+      You only need to call this function if you have been changing terrains to/from
+      water and wanted to defer recalculating whether the map allows seafaring.
+*/
+int LuaMap::recalculate_seafaring(lua_State* L) {
+	get_egbase(L).mutable_map()->recalculate_allows_seafaring();
+	return 0;
+}
+
+/* RST
    .. method:: set_port_space(x, y, allowed)
 
       Sets whether a port space is allowed at the coordinates (x, y).
@@ -1344,7 +1354,7 @@
 	const int y = luaL_checkint32(L, 3);
 	const bool allowed = luaL_checkboolean(L, 4);
 	const bool success = get_egbase(L).mutable_map()->set_port_space(
-	   get_egbase(L).world(), Widelands::Coords(x, y), allowed);
+	   get_egbase(L).world(), Widelands::Coords(x, y), allowed, false, true);
 	lua_pushboolean(L, success);
 	return 1;
 }
@@ -5932,7 +5942,9 @@
       (RW) The height of this field. The default height is 10, you can increase
       or decrease this value to build mountains. Note though that if you change
       this value too much, all surrounding fields will also change their
-      heights because the slope is constrained.
+      heights because the slope is constrained. If you are changing the height
+      of many terrains at once, use :attr:`raw_height` instead and then call
+      :any:`recalculate` afterwards.
 */
 int LuaField::get_height(lua_State* L) {
 	lua_pushuint32(L, fcoords(L).field->get_height());
@@ -5957,10 +5969,10 @@
 /* RST
    .. attribute:: raw_height
 
-      (RW The same as :attr:`height`, but setting this will not trigger a
+      (RW) The same as :attr:`height`, but setting this will not trigger a
       recalculation of the surrounding fields. You can use this field to
       change the height of many fields on a map quickly, then use
-      :func:`wl.map.recalculate()` to make sure that everything is in order.
+      :any:`recalculate` to make sure that everything is in order.
 */
 // UNTESTED
 int LuaField::get_raw_height(lua_State* L) {
@@ -6119,7 +6131,11 @@
       (RW) The terrain of the right/down triangle. This is a string value
       containing the name of the terrain as it is defined in the world
       configuration. You can change the terrain by simply assigning another
-      valid name to these variables.
+      valid name to these variables. If you are changing the terrain from or to
+      water, the map will not recalculate whether it allows seafaring, because
+      this recalculation can take up a lot of performance. If you need this
+      recalculated, you can do so by calling :any:`recalculate_seafaring` after
+      you're done changing terrains.
 */
 int LuaField::get_terr(lua_State* L) {
 	TerrainDescription& td = get_egbase(L).world().terrain_descr(fcoords(L).field->terrain_r());
@@ -6131,7 +6147,7 @@
 	EditorGameBase& egbase = get_egbase(L);
 	const World& world = egbase.world();
 	const DescriptionIndex td = world.terrains().get_index(name);
-	if (td == static_cast<DescriptionIndex>(-1))
+	if (td == static_cast<DescriptionIndex>(Widelands::INVALID_INDEX))
 		report_error(L, "Unknown terrain '%s'", name);
 
 	egbase.mutable_map()->change_terrain(world, TCoords<FCoords>(fcoords(L), TriangleIndex::R), td);

=== modified file 'src/scripting/lua_map.h'
--- src/scripting/lua_map.h	2018-04-07 16:59:00 +0000
+++ src/scripting/lua_map.h	2018-04-11 07:16:58 +0000
@@ -98,6 +98,7 @@
 	int place_immovable(lua_State*);
 	int get_field(lua_State*);
 	int recalculate(lua_State*);
+	int recalculate_seafaring(lua_State*);
 	int set_port_space(lua_State*);
 
 	/*

=== modified file 'test/maps/two_ponds.wmf/scripting/test_seafaring.lua'
--- test/maps/two_ponds.wmf/scripting/test_seafaring.lua	2017-11-08 15:53:57 +0000
+++ test/maps/two_ponds.wmf/scripting/test_seafaring.lua	2018-04-11 07:16:58 +0000
@@ -3,30 +3,42 @@
    -- not allow seafaring. One of the port spaces has trees on top of it.
    assert_equal(2, map.number_of_port_spaces)
    assert_equal(false, map.allows_seafaring)
+   map:recalculate_seafaring()
+   assert_equal(false, map.allows_seafaring)
 
    -- Now try to add a port space on a medium buildcap, it should fail
    assert_equal(false, map:set_port_space(11, 9, true))
    assert_equal(2, map.number_of_port_spaces)
    assert_equal(false, map.allows_seafaring)
+   map:recalculate_seafaring()
+   assert_equal(false, map.allows_seafaring)
 
    -- Now try to add a port space away from water, it should fail
    assert_equal(false, map:set_port_space(18, 9, true))
    assert_equal(2, map.number_of_port_spaces)
    assert_equal(false, map.allows_seafaring)
+   map:recalculate_seafaring()
+   assert_equal(false, map.allows_seafaring)
 
    -- Now add a connecting port space - it should succeed and we should have seafaring then
    assert_equal(true, map:set_port_space(0, 2, true))
    assert_equal(3, map.number_of_port_spaces)
    assert_equal(true, map.allows_seafaring)
+   map:recalculate_seafaring()
+   assert_equal(true, map.allows_seafaring)
 
    stable_save(game, "port_spaces")
    assert_equal(3, map.number_of_port_spaces)
    assert_equal(true, map.allows_seafaring)
+   map:recalculate_seafaring()
+   assert_equal(true, map.allows_seafaring)
 
   -- Remove the port space again
    assert_equal(true, map:set_port_space(0, 2, false))
    assert_equal(2, map.number_of_port_spaces)
    assert_equal(false, map.allows_seafaring)
+   map:recalculate_seafaring()
+   assert_equal(false, map.allows_seafaring)
 
    print("# All Tests passed.")
    wl.ui.MapView():close()