Merge lp:~widelands-dev/widelands/bug-1810062-territorial-calculations into lp:widelands

[Toni Förster]

Refactor initialization of win conditions:

- Separate optional "init" coroutine that is executed on the loading
  screen
- Shift calculations for territorial functions and Wood Gnome to C++
  to improve performance
- Add immovables to the table for territory calculation
- Expose port spaces and max caps to Lua interface
- Remove superfluous "postload" call from replay

This adds fields covered by trees, stones, artifacts and buildings to calculated territory.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 4379. State: passed. Details: https://travis-ci.org/widelands/widelands/builds/474645761.
Appveyor build 4171. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_bug_1810062_territorial_calculations-4171.

[Toni Förster (stonerl)]

This revision should also fix Galcier Lake and other maps.

Here is the idea: Fields that can have a small, medium, or big building on it will automatically be added. Big includes ports. Also fields that currently have immovables on it, like stones & trees are added as well, since they might cover fields that have one of the aforementioned building spaces.

For all other walkable fields, this includes fields with flags and mines, we evaluate whether they can be reached by certain types of buildings. If reachable within 6 fields by small, medium & big it is added since it can be reached at least by the smallest military building.

If within 8 field a medium and big building is buildable then it will be added as well. Also if within 12 fields a big building is buildable.

The calculation is done in x y, x -y, -x y & -x -y direction. On minor issue is that if we reach 0 on the xy-axes or the xy maximum the evaluation stops. Instead of starting by at the coordinate 1 or counting backwards from xy-max.

Here are the 100% that are calculated for different implementations on the Galcier Lake map, with the implementation in the merge request the size is reduced by ~30%.

6713: current implementation
4718: when counting up 12 fields from the field in question
4715: when counting up 8 fields from the field in question
4702: when counting up 6 fields from the field in question

For Oasis Triangle the size it reduced by 75%:
36064: current implementation
12646: when counting up 12 fields from the field in question
12612: when counting up 8 fields from the field in question
12490: when counting up 6 fields from the field in question

With the current merge request, up to 12 fields are checked. The other cases can be tested by commenting the elseifs out. As I said the before: there might be some shortcomings, but they are be negligible in my opinion.

Glacier Lake & Oasis Triangle seems playable when looking at the numbers. I also run a quick simulation with AIs and it seems to be fine. So please test as thoroughly as possible.

We could also only check for 6 fields to be on the safe side. But by looking at the numbers it is just a small difference between the 12 and 6 fields calculation (1.3% on Oasis Triangle & 0.3% on Glacier Lake) so it should be find to test for the whole 12 fields.

[Toni Förster (stonerl)]

A minor change. We don't assume that immovables can be added without checks. We need to test whether a field can be reached. This reduces the available size on Oasis from 12646 to 12395 fields and on Glacier from 4718 to 4697. We might miss some fields though...

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 4382. State: errored. Details: https://travis-ci.org/widelands/widelands/builds/475124699.
Appveyor build 4174. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_bug_1810062_territorial_calculations-4174.

[Toni Förster (stonerl)]

Revision 8961 should be more accurate no that hitting the map boarders don't stop the calculation. The number of fields have increased.

Glacier Lake might be on the edge of being playable in territorial. Also calculations might take some time "The Oasis Triangle" took about 30 seconds on my system, since it has so man empty fields.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 4384. State: passed. Details: https://travis-ci.org/widelands/widelands/builds/475608975.
Appveyor build 4176. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_bug_1810062_territorial_calculations-4176.

[kaputtnik (franku)]

30 seconds is definitely to long.

What about the idea mentioned in https://bugs.launchpad.net/widelands/+bug/1622307/comments/2 ? So we have a check in c++, which should be faster than lua. We can add an additional tag in the elemental file like we have for 'seafaring': When the map is saved, it will be checked for possibility to play territorial and the tag is added. This way we can also have a filter on the "Choose map" page, and exclude the winconditions from the list in the 'Launch Game' page. In my theory ;)

I think the map 'The Nile' is also affected.

[Toni Förster (stonerl)]

The checks here not only "minimize" a map. They also increase it. The map Astoria 2.R goes from 37602 to 42610 fields. 12% more fields that were covered by trees and stones before and weren't counted. Calculation time here is not really noticeable.

The Map the Nile already can be played in territorial. With the current implementation it has 56801 fields in total, and 55325 fields with this revision. This map is quite well designed. But calculations also take some time, because it has allot of mines and flag-only fields.

Regarding your idea for territorial checks in the Editor. I think we don't need that flag. Instead, the Editor should calculate the amount of fields for territorial and store this table in the map file. When starting a new game we then just need to load the table instead of calculation the fields.

(But this is beyond my current abilities, sadly)

If someone has a neat idea on how to speed this code here up... I guess math would help :-)

[kaputtnik (franku)]

> Instead, the Editor should calculate the amount of fields for territorial and store this table in the map file. When starting a new game we then just need to load the table instead of calculation the fields.

+1 :-)

[hessenfarmer (stephan-lutz)]

+1 for calculating these amounts in the editor but we should have this code as well to provide backwards compatibility for old maps without having to reedit them in the mapeditor.

as far as I understand this code the algorithm isn't exactly correct as it checks a quadratic pattern whether a building can be build there to calculate accesability but the conquer function is circular

so for the following pattern the o's will be falsely declared positive possibilities to reach the center field (c) with a conquer radius of 1.

  o x x o
   x c x
  o x x o

[kaputtnik (franku)]

> but we should have this code as well to provide backwards compatibility for old maps without having to reedit them in the mapeditor.

From my understanding the code for calculating the fields a player could reach is executed automatically whenever a map is saved. So loading and resaving all shipped maps would do the trick and there is no need to edit a map at all. Except external maps, like we have on the website.

Not sure what you meant with 'backwards compatibility'.

Anyway, we should discuss this on the bug report.

[hessenfarmer (stephan-lutz)]

in my installation the vast majority of available maps are such external maps (including S2 maps)

I explained this also in the bug.

While thinking about it I came along a possible solution for the long calculation time.
It might help to have the calculation in a parallel thread (e.g. running automatically after including theterritorial functions) delivering a global variable Valuable fields. Only thing we need to consider then is not calling the variable too early in the game (i.e. sending a status message) This can be achieved by sleeping the main loop probably.

By this we can start playing while the calculation is done in the background.

[Toni Förster (stonerl)]

>It might help to have the calculation in a parallel thread

This might help indeed. But first of all I try to get the current code to perform as fast as possible. As you pointed out, currently squares are calculated. Also I just realized that some coordinates are calculated twice. Getting rid of these unnecessary calculations would free allot of time (roughly up to 100 calculations per field).

I do have another idea in mind on how to avoid some more calculations, but these are only vague ideas.

[hessenfarmer (stephan-lutz)]

some more ideas to speed it up:
1. use the region lua command instead of going through the quadrant coordinates.
a) first it is working in a circular manner which reflects better the conquer radius.
b) Second it will not evaluate the superfluous corner fields (which are lot in a radius 12 case).
c) Third it can be used in tranches from the inside to the outside using r1 and r2 which will allow to break the calculation as soon as a nearby suitable building will be found.

2. we might reconsider which field is valuable (in my perspective just walkable fields are not valuable, only if there can be build a flag/road) which might reduce the number of fields to be calculated in total.

some problems of the algorithm to be suitable for every map:
1. taking seafaring into account currently all small islands will be counted as long as there are two building spots, although they won't be accessible due to no port.
2. same is for hidden valleys in the mountains or similar.

one question:
are you sure that an immovable on the map will hide a caps. in my understanding of the documentation f.immovable is independent of has_caps.

[Toni Förster (stonerl)]

>one question:
>are you sure that an immovable on the map will hide a caps. in my
>understanding of the documentation f.immovable is independent of has_caps.

Yes they are, try it yourself in the editor. Some do some don't.

Here are the ones that do:
- Wasteland Trees
- Palm Trees
- Deciduous Trees
- Coniferous Trees
- Rocks
- Standing Stones
- Artifacts
- The 4 Ruins building from Miscellaneous

Here are the ones that don't hide caps:
- Dead Trees
- Plants
- Miscellaneous

>(in my perspective just walkable fields are not valuable, only if there
>can be build a flag/road)

Every walkable field is buildable since it can hold a flag. That's why
"The 3 Oasis" and "Glaciers Lake" are so big when you only check for
f.buildable. Hence, we need to check whether the field is accessible within
a certain radius.

Also fields around immovables, or when the map has certain topographically
properties are walkable, but can only hold only a flag. When you remove the
immovable (chopping tree or rock) the field becomes buildable.

Of course, we cannot only check for walkable, we need to check for other
properties as well. But it helps to distinguish between swimmable and un-
walkable fields. Which are not considered valuable.

>some problems of the algorithm to be suitable for every map:
>1. taking seafaring into account currently all small islands will be
>counted as long as there are two building spots, although they won't be
>accessible due to no port.
>2. same is for hidden valleys in the mountains or similar.

These are the problems we face with "Glacier Lakes". It has hidden valleys
and one Island. But the current at least improves the situation, although
there are still false positives.

I just played around with the editor to get a better understanding.

[hessenfarmer (stephan-lutz)]

Ok thanks for the explanation about caps. I will recheck in the code and via debug console why this is the case. From my perspective an immovable shouldn't alter the build caps information,
cause this behaviour would mean that the check for reachability would be compromised as well.

regarding the issues of islands I fully recognize and appreciate that your code is a major improvement, I just wanted to point out that there is still room for improvement.

While thinking about this I once had the thought to start evaluating the fields from the starting positions and ports to check if they are reachable But I don't have a proper solution how to achieve this yet.

[kaputtnik (franku)]

I think it is very important that the build caps can change temporarily. Otherwise one can build a building/flag on a node where e.g. a tree stands on it or a farmers field was planted. The same goes for placed rocks, which could be used to block an area of a map until the rocks are removed by a stonemason. Do i misunderstand some thing?

Some of the immovables in 'Miscellaneous' are permanently changing build caps (they can not be removed), e.g. the 'Debris'-ones, which were massively used on the map Dolomites. Same goes for all immovables in 'Standing Stones'.

[hessenfarmer (stephan-lutz)]

Hm. Not sure about this thing currently I did some digging into the c++ Code but I don't understand yet when these Caps are calculated. I always thought they are calculated only once and reflect general properties of a field. In the code it is written that they only need to be recalculated when the Terrain has been altered (e.g. by scenario script) In the c++ Part there is the explicit possibility to calculate with or without taking immovable into account. But I couldn't find out which possibility is used by the lua Hook and for which purpose the different options are used.
Anyhow I think we need to understand these issues to be able to do the things 100% correct for every map. For the moment being I could easily live with the current state of accuracy as it is much better than before and will render 99% of the maps to be playable in territorial mode. Only thing is we need to do something about performance, as I agree 30 secs is to long if they are experienced by the user.

[Toni Förster (stonerl)]

>From my perspective an immovable shouldn't alter the build caps
>information, cause this behaviour would mean that the check for
>reachability would be compromised as well.

What kaputtnik said, they should do this temporarily otherwise one
could build on an immovable. The easiest would be to assume that would
could just add all fields with immovables...

>regarding the issues of islands I fully recognize and appreciate that
>your code is a major improvement, I just wanted to point out that there
>is still room for improvement.

Thank you. Sorry if sounded salty in my last comment, that wasn't my intention.

[hessenfarmer (stephan-lutz)]

okay did some further investigations.
The C++ function to calculate the nodecaps can be executed with or without taking immovable into account (you need to provide the bool "consider_Mobs" which defaults to true)

As far as I could see the only instance where Mobs are ignored is for calculating if a portspace is allowed on a field.

the lua Hook has_caps is using the default calculation with mobs considered.

From my perspective we need to adjust the lua Hook to use this bool "consider_mobs" parameter to get the max caps of a field instead of the current caps. As for the valuable fields calculation we should consider the possible building options after removing stones and trees.

I might try to implement this but I am not very skilled in C++.

with this information we could use Toni's algorithm to get very close to the optimum.

Only problem is I am short of time

[hessenfarmer (stephan-lutz)]

Hi
I figured out a solution to check the caps of a field without taking immovables into account.
Basicly I just added a lua hook and a new field property "max_caps".
This solution speeds up the algorithm because we don't have to take immovable fields into account for the accesibility loops.

Question is shall I push another revision to this branch with my changes or shall I push a new branch?

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 4425. State: failed. Details: https://travis-ci.org/widelands/widelands/builds/490531563.
Appveyor build 4213. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_bug_1810062_territorial_calculations-4213.

[GunChleoc (gunchleoc)]

Shifting this to C++ and pre-calculating would work like this:

1. Add a Bool to flag whether the fields have been calculated
2. Increase the map packet number and use it to add a condition to map loading
3. For older maps, calculate, for newer maps, pre-load

We should only save this to maps though once it has been well-tested.

I have a slow machine to test the performance of the current state.

[GunChleoc (gunchleoc)]

I'm getting a compile error on debug builds:

Building CXX object src/wui/CMakeFiles/wui_common_gamedetails.dir/load_or_save_game.cc.o
In file included from /home/bratzbert/sources/widelands/bug-1810062-territorial-calculations/src/logic/map.h:33:0,
                 from /home/bratzbert/sources/widelands/bug-1810062-territorial-calculations/src/logic/editor_game_base.h:29,
                 from /home/bratzbert/sources/widelands/bug-1810062-territorial-calculations/src/logic/game.h:28,
                 from /home/bratzbert/sources/widelands/bug-1810062-territorial-calculations/src/wui/load_or_save_game.h:25,
                 from /home/bratzbert/sources/widelands/bug-1810062-territorial-calculations/src/wui/load_or_save_game.cc:20:
/home/bratzbert/sources/widelands/bug-1810062-territorial-calculations/src/logic/field.h:261:1: error: static assertion failed: Field is not tightly packed.
 static_assert(sizeof(Field) == sizeof(void*) * 2 + 10, "Field is not tightly packed.");

[Toni Förster (stonerl)]

@hessenfarmer

I can't compile your changes, Travis isn't pleased as well.

/src/logic/field.h:261:1: error: static_assert failed "Field is not tightly packed."
static_assert(sizeof(Field) == sizeof(void*) * 2 + 10, "Field is not tightly packed.");
^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1 error generated.

review: Needs Fixing

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 4453. State: errored. Details: https://travis-ci.org/widelands/widelands/builds/491252805.
Appveyor build 4241. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_bug_1810062_territorial_calculations-4241.

[hessenfarmer (stephan-lutz)]

I didn't know about this as I use a MSYS2 Environment (like Appveyor) where it compiled and worked.
Unfortunately my C++ knowledge is very limited, so I am not sure how to fix this.

If anyone of you knows what is going on there feel free to correct it. I will try to do so as well tonight.

I believe this assert is to ensure minimal ressources consumption of a field object cause there are so many of them.

[hessenfarmer (stephan-lutz)]

The check that is failing is checking whether a field instance is tightly packed. (whatever that means)

However the reason for Linux failing while appveyor / MSYS2 not failing is that this check is defined different for a WIN32 system as for the other systems. The reason for this is unknown to me.
So I would propose to fix line 261 ff. of field.h and doing the check equally for all systems (i.e. deleting the if loop)

[GunChleoc (gunchleoc)]

The check under Windows is more strict, so unifying the check will not make the assert error go away. The roper fix is to understand what the problem is - I expect that there is a reason that somebody put that assert there and that there is a bug in the new code.

[hessenfarmer (stephan-lutz)]

the check for WIN32 is an ifndef check so in fact the check for Windows is less strict.

My code adds a new property to the field struct so I believe it is increased in size and therefore the check for all other Systems than Windows fail due to the more restrictive size check.
As these asserts are checking the size of field I can't see the reason why the assert is different for different OS.

As I haven't a Linux machine ready I'll try it the other way round by lowering the windows part as well and see if MSYS2 environment complains as well.

[hessenfarmer (stephan-lutz)]

Ok I tested it and it is a completely logical behaviour:

1. the assert tests the size of a field object to ensure the preprocessor command to pack this struct was successful
2. before my changes this object had 10 bytes + 2 times the standard address width (sizeof (void*))
3. I added a property as uint8 which needs another byte. so this results in 11 bytes + 2 times sizeof(void*)
4. the winows assert allowed for up to 11 bytes and did not complain, the other OS assert was checking the 10 bytes and complained logically.

so the solution (if we want to have this change) is indeed to adapt the assert to the new size of the field struct. I uploaded a new revision with the relevant changes.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 4461. State: passed. Details: https://travis-ci.org/widelands/widelands/builds/491840111.
Appveyor build 4249. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_bug_1810062_territorial_calculations-4249.

[GunChleoc (gunchleoc)]

Duh, I overlooked the n. Your solution sounds good to me.

[hessenfarmer (stephan-lutz)]

Ok but still this branch needs testing especially with regard to performance.

[GunChleoc (gunchleoc)]

Definitely. We should target it to Build 21 too.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 4468. State: errored. Details: https://travis-ci.org/widelands/widelands/builds/492822657.
Appveyor build 4256. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_bug_1810062_territorial_calculations-4256.

[kaputtnik (franku)]

This branch does not work for me on my poor laptop (Celeron 900 with 3,8Gb Memory). E.g. trying to load map Oasis Triangle will last forever while memory usage increases until no memory is available anymore. I have put a print statement at the beginning and the end of the function get_valuable_fields() and the output was:

Starting get_valuable_fields:
[some minutes gone]
ALSA lib pcm.c:8424:(snd_pcm_recover) underrun occurred
ALSA lib pcm.c:8424:(snd_pcm_recover) underrun occurred
ALSA lib pcm.c:8424:(snd_pcm_recover) underrun occurred
ALSA lib pcm.c:8424:(snd_pcm_recover) underrun occurred
ALSA lib pcm.c:8424:(snd_pcm_recover) underrun occurred
ALSA lib pcm.c:8424:(snd_pcm_recover) underrun occurred
ALSA lib pcm.c:8424:(snd_pcm_recover) underrun occurred
ALSA lib pcm.c:8424:(snd_pcm_recover) underrun occurred
...

I had to kill widelands then... Maybe this is the same issue as mentioned in comment 13 of bug 1651591

It is also annoying that the code is executed after the loading screen has finished. So one is staring at a black screen and nothing happens.

[kaputtnik (franku)]

Forgot to mention: Tested a release build.

Here the output for map Glacier Lake:

Starting get_valuable_fields:
get_valuable_fields took: 6410ms

6 seconds sitting in front of a black screen ;)

[hessenfarmer (stephan-lutz)]

confirmed this is killing old machines on oasis triangle.

How about just checking the map for fields with maximum buildcaps small, medium, big, port, and mine. this isn't exakt as well but far less consuming.

[hessenfarmer (stephan-lutz)]

we are getting better, at least my machine (Core2Duo T7500 6GB) is able to calculate oasis triangle with about 14000 valuable fields. Problem is it still took 20+ seconds.
I don't know the table beahviour in lua exactly, but if we could exclude/remove duplicates it would make sense to simply evaluate each field once and add all fields which could be conquered. I will work in this direction and see how far we could get.

Thanks anyway for implementig the region thing. I tdefinitly improves Glacier lake

[Toni Förster (stonerl)]

You're welcome. The question though, should we really evaluate big fields? We currently stop after 10 fields, because I think 12 is too far away and adds fields that are only accessible under extreme circumstances.

[Toni Förster (stonerl)]

I think I found the sweet-spot. It is a radius of 6 for medium and big buildings. Let me explain: Before hessenfarmer introduced the max_caps we had to calculate up to 12 fields to make sure the immovable was accessible. This isn't the case any more. Here are some maps I tested with different calculations on my system:

Glacier Lake:

 6 fields b/m: 0:07 min - 3598 fields
 6 fields all: 0:06 min - 5196 fields
 8 fields all: 0:08 min - 5464 fields
10 fields all: 0:08 min - 5829 fields

3598 fields is the perfect value all others are still to high.

The Oasis Triangle:

 6 fields b/m: 0:42 min - 10520 fields
 6 fields all: 0:39 min - 11910 fields
 8 fields all: 1:02 min - 13652 fields
10 fields all: 1:26 min - 14208 fields

The Nile:

 6 fields b/m: 0:59 min - 39551 fields
 6 fields all: 1:00 min - 39626 fields
 8 fields all: 1:10 min - 45474 fields
10 fields all: 1:36 min - 47766 fields

Astoria 2R:

 6 fields b/m: 0:15 min - 42535 fields
 6 fields all: 0:15 min - 42400 fields
 8 fields all: -:-- min - 42605 fields
10 fields all: -:-- min - 42610 fields

The first 3 are maps that are to big because they use wrong assets. Astoria on the other hand only suffered from fields with immovables not being counted.

The calculation time for big maps with vast wastelands is still high, but maybe we could move the calculation in a parallel thread as hessenfarmer suggested.

Or we could move the initial calculation to the load screen. With a message like: "Calculating win conditions...", if possible.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 4482. State: passed. Details: https://travis-ci.org/widelands/widelands/builds/494349394.
Appveyor build 4270. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_bug_1810062_territorial_calculations-4270.

[Toni Förster (stonerl)]

I think I had an eureka moment. get_valuable_fields() is in a coroutine and gets calculated in the background. The sleep time can be adjusted, but I think 50ms is a good value. I tested 25ms which cut the time in half but the game was a little choppy.

[hessenfarmer (stephan-lutz)]

I had a eureka moment as well. Here is my code which is very fast (just some seconds.)

function get_valuable_fields()
   local fields = {}
   local map = wl.Game().map
   for x=0, map.width-1 do
      for y=0, map.height-1 do
         local f = map:get_field(x,y)
         if f:has_max_caps("small") then
            local radius = f:region(6)
            for idx, fg in ipairs(radius) do
               local index = fg.x * 1000 + fg.y
               fields[index] = fg
            end
         elseif f:has_max_caps("medium") then
            local radius = f:region(8)
            for idx, fg in ipairs(radius) do
               local index = fg.x * 1000 + fg.y
               fields[index] = fg
            end
         elseif f:has_max_caps("big") then
            local radius = f:region(12)
            for idx, fg in ipairs(radius) do
               local index = fg.x * 1000 + fg.y
               fields[index] = fg
            end
         end
      end
   end
   local result = {}
   for idx,f in pairs(fields) do
      table.insert(result, f)
   end
   return result
end

of course we could discuss about the size of the regions. I will go through the lua files of all military buildings to see what might be good values.

[Toni Förster (stonerl)]

Awesome, your approach is so much more elegant. I pushed it to the branch.

[kaputtnik (franku)]

This is working nicely i think :) Some values with my Celeron 900:

Oasis Triangle:
Finished initial calculations after 21 minute(s) and 57 second(s).

The Nile:
Finished initial calculations after 21 minute(s) and 39 second(s).

Together we're strong:
Finished initial calculations after 14 minute(s) and 10 second(s).

Glacier Lake:
Finished initial calculations after 3 minute(s) and 24 second(s).

I have made also a small lan-game test on Glacier Lake until the first status message appears. All fine and working, and looking at the map it seems visually that i had conquered the half maps size.

review: Approve (testing)

[kaputtnik (franku)]

hm.. i was too slow... my comment was meant for r8970 of this branch...

[hessenfarmer (stephan-lutz)]

ok after agoing through all military buildings i think small = 6 medium = 8 and big = 10 are good values.

[Toni Förster (stonerl)]

I'm torn. I love hessenfarmers approach so much, since it is so blazingly fast. But the calculated areas are too large.

I think r8970 is better ATM, since the calculated areas are more suited for Territorial.

Could we somehow marry both approaches?

[Toni Förster (stonerl)]

I think this could be it. Fast calculations with appropriate sizes.

[hessenfarmer (stephan-lutz)]

Next try I have done is starting from the starting field and add all fields that can be conquered.

function get_valuable_fields()
   local fields = {}
   local check = {}
   local map = wl.Game().map
   local sf = map.player_slots[1].starting_field
   -- initilaize with the region around the startign field of P1
   for idx, fg in ipairs(sf:region(9)) do
      local index = fg.x * 1000 + fg.y
      fields[index] = fg
      check[index] = fg
   end
      local loop = true
      while loop do
         loop = false
         local new = {}
         -- checking the check region for buildcaps and add fields that can be conquered
         for idx, f in pairs(check) do
            if f:has_max_caps("big") then
               local radius = f:region(10)
               for idx, fg in ipairs(radius) do
                  local index = fg.x * 1000 + fg.y
                  if fields[index] == nil and check[index] == nil then
                     -- if new fields are discovered add them to the fields table and mark them for checking next loop
                     new[index] = fg
                     fields[index] = fg
                     loop = true
                  end
               end
            elseif f:has_max_caps("medium") then
               local radius = f:region(8)
               for idx, fg in ipairs(radius) do
                  local index = fg.x * 1000 + fg.y
                  if fields[index] == nil and check[index] == nil then
                     new[index] = fg
                     fields[index] = fg
                     loop = true
                  end
               end
            elseif f:has_max_caps("small") then
               local radius = f:region(6)
               for idx, fg in ipairs(radius) do
                  local index = fg.x * 1000 + fg.y
                  if fields[index] == nil and check[index] == nil then
                     new[index] = fg
                     fields[index] = fg
                     loop = true
                  end
               end
            end
         end
         check = new
      end
   local result = {}
   for idx,f in pairs(fields) do
      table.insert(result, f)
   end
   return result
end

Only thing left is to adapt this for seafaring i.e. doing the same thing for all port spaces as well.
Speed is still good I think.

[hessenfarmer (stephan-lutz)]

Sorry. for some reasons the comments didn't get updated on my machine.
My latest chunk of code is delivering all fields that could be reasonably conquered on a map.
with big = 10 and medium = 8 and small = 6 it delivers 4768 on Glacier lake.

So for me this value sounds reasonable.

for Oasis triangle it delivers somewhat 14xxx which sounds reasonable as well.

[hessenfarmer (stephan-lutz)]

Another thing which is supporting my latest trial is that the actual coverage of fields is calculated against the fields originally identified.

so the algorithm is player x owns yy fields of all fields identified as valuable.

so not only the number is relevant but it matters which fields are identifeid as valuable. Therefore it doesn't help if we only have 3xxx fields on glacier lake as we can't still reach a lot of them.

Furthermore not taking the small caps into account would deliver false results on maps where medium sized and big spots are very rare (the dolomites for example)

[Toni Förster (stonerl)]

Awesome! I pushed your second try.

[Toni Förster (stonerl)]

I'm fiddling around with the radius. Because Glacier is still a little too big and I think we shouldn't go to the extreme limits. What could be suitable values:

big: 8
medium: 6
small: 4

In Oasis this would result in 11655 fields, which is reasonable. 14000 Fields is way to many to get 50% I tested this yesterday.

In Glacier Lake this would be 4114 fields which is also way better. I'd prefer to have a little less then to many fields that are only accessible in edge cases.

But you do awesome work!

[Toni Förster (stonerl)]

BTW don't have port spaces also the big caps?

[GunChleoc (gunchleoc)]

Yes, port spaces also have big caps. I think the point was though if you have an island without a starting field and a port space, we need a field to seed calculation for that island.

[hessenfarmer (stephan-lutz)]

@ GunChleoc: exactly!

I will try to implement this tonight. At the moment I am busy watching my favourite football team so sorry for the delay

[hessenfarmer (stephan-lutz)]

ok done. Now we start our algorithm with all starting fields of all players and all port spaces.

the port space scan is a little consuming. (it doubles the scan time i think) but still i think it is ok.

I reduced the radiuses by one for each caps. (9, 7, 5) which is reasonable. I excluded unwalkable fields from being counted as well so we might have a good value now

[hessenfarmer (stephan-lutz)]

as the underlying bug is really a shortfall on some maps and it is ensured we are still delivering a properly indexed fields table I would think this is worth going into b20, as it is not introducing new functionality.

[kaputtnik (franku)]

Can you add a print statement like Toni did? Or something like:

print(("Counting valuable fields took: %dms, result is %d."):format(ticks() - start, #result))

For Glacier lake the output on my slow laptop is:

Counting valuable fields took: 803ms, result is 4015.

[hessenfarmer (stephan-lutz)]

I am afk until tonight. So please feel free to do so.

Perhaps you could post the value for Crossing the horizon where I tested the seafaring part.

Astoria2.R would also be interesting as it is really big, so I would expect about 4 seconds there

[GunChleoc (gunchleoc)]

Codereview done.

I disagree that this is not a new feature, the code changes are more than trivial. Yes, it does fix a bug, but it's an old bug, so I'm not sure that it is critical enough to risk introducing new bugs.

[hessenfarmer (stephan-lutz)]

In the end I would leave it to your decision. However I still would think it to be worth having it.
The glacier map bug is an old one but the second bug reported by Toni isn't. As the behaviour detected by Toni (immovables affecting the field count) is affecting a lot of maps where the values of "fields to be conquered" are mostly wrong (e.g crater) it will give some great benefit because the effect of the bug is bigger than only the glacier lake / oasis triangle effect.

The changes aren't that big as they appear in my opinion.
the c++ change is barely more than a copy of an existing property of a field (that's true because it is the way I have managed to do so - my knowledge/experience of c++ is very limited).
and the lua change is definitely only in one function which delivers its output formatted in the same way as its predecessor.
so the risk in lua is to have wrong values of "fields to conquer" again for different maps currently not tested. This is no change to the previous situation where the values were wrong for the maps tested.
the risk in c++ is to have a failing method/interface this risk is mitigated by it being a full copy of an existing method/interface.

So if you value risk against benefit you might rethink about having it in b20. But still your decision, I just wanted to made my point clear.

I have answered your review below.

[Toni Förster (stonerl)]

I'd also like to see this fix make it into build20, since the second bug renders this game mode almost useless. Hessenfarmer as eloquently described the benefit, but in the end, it is up to you GunChleoc.

[kaputtnik (franku)]

Sorry, my slow laptop is only available at weekends. I can test with an Athlon 4300 Quad core, but i think this is not useful :-)

I'd vote targeting this to build21. GunChleoc wants to add a new c++ function for the port spaces, so the new code will get more complex. But build 21 should be released much faster than build20 ;)

[GunChleoc (gunchleoc)]

I am done with my changes.

LuaField already had a __hash function, but I replaced it with a more efficient one. This means that we now need to test the Atlantean scenario and Trident of Fire on multiplayer.

The port spaces can be accessed like this:

   for index, value in ipairs(map.port_spaces) do
      print(index)
      print("x: " .. value["x"])
      print("y: " .. value["y"])
      for key, val in pairs(value) do
         print(key .. " " .. val)
      end
   end

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 4493. State: failed. Details: https://travis-ci.org/widelands/widelands/builds/495033189.
Appveyor build 4280. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_bug_1810062_territorial_calculations-4280.

[hessenfarmer (stephan-lutz)]

Just did a quick test of the territorial calculation.

it works as before on "Glacier Lakes" (4015) and "crossing the horizon" (8072 if I remember this correctly).
crossing the horizon still takes some time but this should be acceptable from my side.

I tried to add some logging but this doesn't work in my windows installation so I couldn't test it and therefore removed it.

Does anybody know how to log something from lua in a windows build?

Regression testing for atlanteans 1 and trident of fire still necessary (I didn't know at all about the scripting in trident of fire, perhaps one could add some hint to the map description and some tesxt to scripting that explains what will go on)

[kaputtnik (franku)]

Doesn't lua print statements work on windows? At least some output in the console (cmd window)?

[hessenfarmer (stephan-lutz)]

unfortunately they do not work nor in stdout.txt nor in the cmd window if started from there.
So I really would love to have some loggting possibility to stdout.txt for debugging purposes.

[GunChleoc (gunchleoc)]

1 remaining comment.

I am not planning any changes to the port spaces that would affect this function, so I'm not on the fence on whether to merge this into Build 20.

[kaputtnik (franku)]

On my usual machine:

Astoria2.r:
Counting valuable fields took: 29533ms, result is 48422.

Crossing the horizon:
Counting valuable fields took: 2853ms, result is 8072.

Wide World (Big map):
Counting valuable fields took: 5648ms, result is 21141.

Maybe the calculation should be done in a coroutine again?

[hessenfarmer (stephan-lutz)]

@ Gun: I tried to reply your comment, although I am not sure whether I understood it correctly.

@ kaputtnik: Yeah the values of Astoria might imply we should do it in a coroutine.

I just did some testing with trident of fire and it didn't crash although I hardly managed to conquer some land and did not see any map editing. will continue to do so.

[Toni Förster (stonerl)]

I compiled a list of 65 maps with the calculation times and the calculated fields.

https://fosuta.org/pics/Territorial_Times_r8978.ods

[hessenfarmer (stephan-lutz)]

kaputtnik, Toni:
Could you please try Revision 8975 to Computer the values of Computing time

[Toni Förster (stonerl)]

@kaputtnik I'm at it right now.

[Toni Förster (stonerl)]

Done, can be found here:

https://fosuta.org/pics/Territorial_Times_r8975_r8978.ods

On average r8975 is slower. Furthermore, on some maps it calculates fewer fields. I marked them yellow.

[hessenfarmer (stephan-lutz)]

@Toni: Thanks a lot for providing the tables. So we still have an issue on large maps. Sounds like we would need to run in a coroutine, although we should try to improve the algorithm any further

One interesting question for me is what have been the values in the current trunk without these changes? Although I hardly dare asking for another 2 columns in the table ;-)

BTW: What Machine are you computing these values on. and do you use a debug or a release build?

I have no explanation yet for the different values calculated.

[hessenfarmer (stephan-lutz)]

@GunChleoc: i checked your code suggestion from my perspective this won't work. see the comment below.

The mechanism is that we only check a certain area in each loop. Beginning with the initial seed we discover new fields to be checked. but we can't add them to check directly cause we will recheck them in the next loop. so we add them to a new table and make them the area to check in the next run.

[hessenfarmer (stephan-lutz)]

OFF Topic: It seems the latest appveyor build of this branch seems to be stuck

[hessenfarmer (stephan-lutz)]

Update:
I continued to playtest trident of fire and I saw a volcano eruption and saw it vanish again. So I assume the script still works with the new hash value

[Toni Förster (stonerl)]

@hessenfarmer You're welcome. :D

https://fosuta.org/pics/Territorial_Times_trunk_r8975_r8978.ods

BTW. We shouldn't let us fool by the numbers, because they say nothing about the "quality" of the calculated fields. The fields calculated with r8978 are accurate while the ones in trunk are not.

I used the Release-Build on a Late 2013 MacBook Pro with a 2,4Ghz Intel Core i5 (I5-4258U)

[Toni Förster (stonerl)]

I guess the difference in size for some maps between 8975 and 8978 is the way port spaces are evaluated. That is the main difference between the 2 revisions.

[GunChleoc (gunchleoc)]

Forget my last code tweak comment, I needed to look at this with code highlighting.

I have done some small tweaks to the code.

We should definitely stick this in a coroutine, because my screen will go black for a bit on Wide World, and my machine is fast.

[Toni Förster (stonerl)]

I think a found a good tweak. The main problem is the second for loop:

for idx, fg in ipairs(radius) do

Here we iterate through fields too many times. On a small map some million times.

I got Astoria 2.R down from 58 seconds to 23seconds. On some maps the calculated area is a little smaller(in Elven Forest 5 fields) but it is much faster. The idea is that with big and medium caps we can assume that the inner 7 or 5 fields are always accessible, so we don't need to iterate to through them again and again.

I made my comments in the code.

[Toni Förster (stonerl)]

I pushed my tweak as revision 8986. I'm currently do some testing with all the maps and it looks promising. Will post an updated list later on.

[hessenfarmer (stephan-lutz)]

I am on a business trip until Friday so I can't do much other than check this side.
@Toni: In principle you are right in perhaps98% of the maps but there are cornercases where you might miss a special building spot which is needed to reach a somewhat hidden valley or a big mountain. So I believe as we need to put it in a coroutine anyway (23 secs is still too long) we could calculate the exact value. In any case many thanks for the values so as trunk is the benchmark for time we would struggle to achieve this.
@all: I just came to an idea how we could avoid the effect that Toni described and which is truly consuming. I can't test it until Friday though.

[Toni Förster (stonerl)]

New calculations are up:

https://fosuta.org/pics/Territorial_Times_v4.ods

We are at least 50% faster in general. The fields are almost the same. Green Cells have 20 or less fields difference. Yellow 50. And red more than 50 (but these are only two maps).

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 4501. State: passed. Details: https://travis-ci.org/widelands/widelands/builds/496123226.
Appveyor build 4288. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_bug_1810062_territorial_calculations-4288.

[GunChleoc (gunchleoc)]

I think slightly underreporting is less critical than overreporting. Overreporting means that the game can't be won, underreporting means that it will be won somewhat faster.

I have now shifted the calculation to C++, because it is a lot faster. It also saves us from having to copy over the data structure at the end.

[GunChleoc (gunchleoc)]

I am now done - I also found and fixed some code duplication. Back to you guys. We should:

1. Find the balance between speed and accuracy.
   You can play with the inner_radius variable for that.
2. Stick the calculation in a coroutine

[Toni Förster (stonerl)]

@GunChleoc

Shifting this to C++ isn't 50% faster. It is ludicrously fast. We are now as fast as trunk, sometimes even faster. I'm going to test with an inner_radius of 1 for all caps and the 1/5/7 as it is in revision 8989 and see what the difference is in time and fields.

I'm convinced we don't need to move this into a coroutine any more.

Just one question regarding the code (see inline).

[kaputtnik (franku)]

> I'm convinced we don't need to move this into a coroutine any more.

I don't think so. On my usual machine:

'Trident of Fire':
Found 15124 valuable fields
Calculating valuable fields took 2094ms

'Astoria2.r':
Found 42605 valuable fields
Calculating valuable fields took 8847ms

We have to think about slow machines too.

Sorry that i couldn't find time to provide more values.

[Toni Förster (stonerl)]

New calculations are up:

https://fosuta.org/pics/Territorial_Times_v5.ods

I just added revision 8989. I tried to set the inner_radius variable to 1/1/1 just for testing but the result was, that time went up, but we didn't gain many fields. So it wasn't worth it.

@kaputtnik please heave a look at the table. We are faster than trunk for the majority of the maps. 18 are less than 100ms slower. 3 less than 200. 1 is 269 and another one 1787.

So we are better than before IMHO.

[Toni Förster (stonerl)]

From my understanding we can't put this in a coroutine, because:

wl.Game().map.valuable_fields

blocks the lua script, as long as it is calculating, and these
calculations eat up all available cpu.

With this

run(function()
    fields = wl.Game().map.valuable_fields
end)

it runs in a coroutine, but the game stalls until the calculations are
done.

It isn't a real coroutine either, because we need to call

coroutine.yield()

from within the coroutine to pause it. But we can't since the c++ part
blocks the script.

[Toni Förster (stonerl)]

@kaputtnik I think you ran the debug build of the game.

On my system:

'Astoria2.r':

Release: 416ms
Debug: 11214ms

'Trident of Fire':

Release: 131ms
Debug: 2778ms

[Toni Förster (stonerl)]

review: Approve (testing)

[kaputtnik (franku)]

Yes, it was a debug build...

[hessenfarmer (stephan-lutz)]

Hi,
As I am Bacck on my dev laptop I did some tests. first I found the reason for rev 8989 having less fields as rev 8978. In the c++ version non walkable fields are not added for port spaces and starting fields. These fields form the delta. especially in maps with a lot of adjacent port spaces (e.g. trident of fire) this is a better calculation as you would only conquer one port and not necessarily the others. By this we have implemented a general rule, that water isn't counting at all which is more congruent to the user. so I am very pleased with this change.

Furthermore I changed the lua version to the values in the c++ branch and they delivered the same results.
I modified the starting values and regions a bit. And still got the same results for some test maps. I believe this should be true for all maps.

The reason is that every building is blocking at least a radius of 1 for other buildings (only flags can be built there) so I think we could savely set the inner radius to 2 for every building which saves a lot of calculations. In lua f.e. Astoria 2R is down to around 10 seconds (handstopped with my watch). So I think we should try these values (using hollowregion with an inner radius of 2 for all fields including starting and port fields) before merging.

I really would love to see Tonis Table for these values.

I will playtest atlanteans 1 tonight just be sure we really do not have any issue with the hash code. If this is fine and the values for the changed regions are still good for the results I think we are finished.

Will report back later.

@ all and especially Toni: many many thanks for your contribution to fix this major bug in our winconditions.

[hessenfarmer (stephan-lutz)]

Another step forward did a full playtest of the first atlantean mission. No anomalies. Water was rising as intended.

So from my side we are ready. but we should try the inner radius of 2 before merging.

[Toni Förster (stonerl)]

New calculations are up:

https://fosuta.org/pics/Territorial_Times_v6.ods

Setting the inner radius to 2 doesn't bring allot to the table, but it doesn't hurt either. So I leave this up to you guys.

@hessenfarmer thanks allot for your kind words. :-)

[GunChleoc (gunchleoc)]

I am using HollowRegion for the init too now.

When loading the Nile, I get a black screen a lot longer than if I am starting a game in trunk.

I'll check how complicated it will be to add a loading screen here.

[GunChleoc (gunchleoc)]

I have now created a separate, optional initialization coroutine for the winconditions, so it can have a loading screen.

Also some refactoring in Artifacts and Wood Gnome.

This can go in after another round of testing.

review: Approve

[hessenfarmer (stephan-lutz)]

I did some testing with the latest version.

Regarding the values of calculating the valuable fields ist is only slightly better in a release build while I suspect it much better in development build (haven't tested this yet) However I would keep this hollowregion values anyway as it is a real representation of what can be reasonably conquered.

Unfortunately Gun's very appreciated change to have this in game initialisation unmasked a new bug which has been there all the time and was not apparent. After initialisation the game is saved. With a big map (lots of fields to be conquered) this save is stalling while trying to write scripting data.
The same behaviour arises if we try to save such a big map in territory mode in trunk. so it is not a bug introduced by this branch. So shal we have a differerent branch or fix it in this one as it is somewhat realted to territorial.
My guess about the reason is that there is some overflow in the map saving code.

review: Needs Fixing

[GunChleoc (gunchleoc)]

Which map is causing the problem?

[hessenfarmer (stephan-lutz)]

Magic Mountain at least. I'll test it with another big map as well.

[hessenfarmer (stephan-lutz)]

Europe1.1 has the same behaviour

[hessenfarmer (stephan-lutz)]

Lost islands works

[Toni Förster (stonerl)]

The "Writing Scripting Data" part is executed several times and takes some minutes to execute. On my system roughly 3 times 5minutes.

[hessenfarmer (stephan-lutz)]

Big Eden fails. so as Big eden and Lost Islands have the same map size but differ in fields (52k to 118k) it is definitly dependent on the size of fields.

[Toni Förster (stonerl)]

@hessenfarmer what do you mean by it fails? The games does load eventually. The saving part just takes ages and depending on your system can cause very big maps to take 10-20 minutes to load.

[hessenfarmer (stephan-lutz)]

southfall islands (102k fields) fails as well.

[hessenfarmer (stephan-lutz)]

@ Toni: the game doesn't react anymore no activity can be seen on the HDD

Maybe it is a systemissue I am on win 10 64bit.

However Lost islands has a lot of fields as well (63k in trunk) and it just takes some seconds to save. While with more fields around 100K it stalls completely.

But I will give it a chance and wait for some minutes.

[hessenfarmer (stephan-lutz)]

ok I have to correct myself it doesn't fail it just takes very long. (95 sec to save the data for magic Mountain once).

So I will invalidate the bug just created.

However if we keep this branch in the current version we will have a loading time of 3 - 5 minutes while having a black screen for max 4 seconds before. perhaps we can shift the loading screen to the end so we will save the game without the fields in the beginning and only have the issue while saving in game.

[GunChleoc (gunchleoc)]

I have testes this with an ASAN debug build any everything is fine. What happens here is that big maps take a long time to calculate. Also, when doing the initial save in trunk, the fields weren't part of the scripting packet yet. Now they are, so saving takes longer.

One thing we should still optimize is that the autosave interval gets triggered before the game has finished loading, so I have to wait for it to saveload twice. I'll take a look at that.

[hessenfarmer (stephan-lutz)]

Waiting for the saveload is the way to go. Calcualtion takes 4 seconds on my old machine for magic mountain while saving takes 90 seconds. So we should initialize the fields after the initial save.

[kaputtnik (franku)]

Saving Magic Mountain on my old Laptop takes ~18sec with a release build (r8998; Linux).

[hessenfarmer (stephan-lutz)]

I managed to load magic mountain. I took very long because of the multiple saves. I attach this log to the (now invalidated) bug.

[GunChleoc (gunchleoc)]

I managed to get rid of 1 of the saves. We are creating an extra temp file with a map save in EditorGameBase::postload() (thank you, Windows), and the postload was being called by the replay writer, which was completely superfluous.

[hessenfarmer (stephan-lutz)]

I tested the new version now. It is better of course as we have one writing cycyle less.
However it lasts still about 3:40 minutes from clicking start until the game finally starts for maps with a lot of fields.
As this was introduced to avoid a 4 (maybe 6) second black screen on big maps after the game started I am pretty unsure whether this is worth the pain. For me I'd rather accept a 6 second blackscreen and a game start after 40 seconds than having to wait 3:40 minutes. Perhaps we could display a message box from lua instead having this done in the game initialisation.
Of course we will suffer the same thing when saving a game but this could be circumvented by increasing the autosave interval.
Anyhow getting rid of the superfluos save is good in any way.

So what are your thoughts about this?

Another question I am interested in is whether this is a windows only behaviour and if so why?

[Toni Förster (stonerl)]

> Another question I am interested in is whether
> this is a windows only behaviour and if so why?

It happens on macOS as well. Don't know about Linux though.

> this could be circumvented by increasing the autosave interval.

But that does not solve the underlying issue.

> So what are your thoughts about this?

The question I't like to get answered is; why does it take
so long to write the save. Clearly here we have the CPU
bottlenecking the process. But why?

During Gameplay this is a problem as well, since the save might
take a minute or more depending on the CPU. I'd like to have
it the way it is in 8999 and investigate why it currently takes
so much time to save.

How does that affect network/internet games?

Here are some numbers for build 8999:

Lost Island has 51544 fields, with saving times:

Writing Scripting Data ... took 4944ms
Writing Scripting Data ... took 5062ms

Europe has 142137 fields, with saving times:

Writing Scripting Data ... took 38358ms
Writing Scripting Data ... took 41443ms

So Europe has 142% (2.7 times) more fields to save.
But the increase in time is 797% (8 times).

[GunChleoc (gunchleoc)]

That saving takes longer has nothing to do with the OS, I get it on Linux too.

I don't see how we can easily improve speed on writing the scripting packet, since that's mostly done by the eris backend. We do have substring calls in there though that might be made faster by using char pointers instead - no idea how much performance that would bring though.

We could look into tweaking more areas like I did for the statistics, which gave us a huge speed increase for the saveloading. The question is, do we need to do that right now - the problem is not new.

[hessenfarmer (stephan-lutz)]

I would vote for reverting to rev 8993 and deleting the superfluous write cycle.

Probably we should keep the woodgnome in c++ part as well.

So we would have a short black screen on very large maps but probably not longer than 4 secs.

That would be the best we can get for now, while fixing the wrong calculations.

we should improve saving and loading then for b21 and after this has been improved we should shift this again to the loading screen.

[Toni Förster (stonerl)]

Is it possible to get the maps name in lua?

like wl.Game().mape.name

Otherwise, since we know that this affects only some
larger maps why not do this for the time being:

   init = function()
      -- Get all valuable fields of the map
      if wl.Game().map.width <= 256 or (wl.Game().map.height <= 256) then
         fields = wl.Game().map.conquerable_fields
      end
   end,

      if wl.Game().map.width > 256 or (wl.Game().map.height > 256) then
         fields = wl.Game().map.conquerable_fields
      end

[Toni Förster (stonerl)]

Can you test r9000?

[GunChleoc (gunchleoc)]

-1 for hard-coding this to the maps' names. We cannot hard-code future maps uploaded to the website, and the list can get quite long.

I have found a way to shift the calculation past the initial saveloading cycle. We still get a black screen, but it has a message on it, so the player will know that something's happening.

With that change, I don't think that we will need the fix from r9000 any more?

[Toni Förster (stonerl)]

@GunChleoc a big thumbs up for your changes. I reverted the changes from r9000.

[hessenfarmer (stephan-lutz)]

@GunChleoc: You are my hero. This is working better than expected cause we don't have a black screen. We just have a little string in the lower left corner reading "initializing game".

So from my side I think we have got a very fine result now.

Thanks to everybody.

I think we are ready to merge, if CI is green.

review: Approve

[Toni Förster (stonerl)]

We need to merge trunk first. There seems to be a conflict.

[Toni Förster (stonerl)]

Just one question. In the general statistics for land differ from the actual valuable owned land, because it counts unwalkable and water. Should we leave it like it is or use the method we use for territorial?

[Toni Förster (stonerl)]

Just one question. In the general statistics for land differ from the actual valuable owned land, because it counts unwalkable (and ¿water?). Should we leave it like it is or use the method we use for territorials?

[GunChleoc (gunchleoc)]

I noticed that The Nile was a lot slower than Wide World, although The Nile is smaller. So, I have tweaked the algorithm further for performance.

The Nile before: 6552ms
The Nile after: 2716ms

General statistics is a good point. If we want to change those, we will have to do this field calculation in all games in order to be consistent. Alternatively, we could add a statistics hook for the win condition, just like we have for Wood Gnome and Collectors.

[bunnybot (widelandsofficial)]

Continuous integration builds have changed state:

Travis build 4523. State: errored. Details: https://travis-ci.org/widelands/widelands/builds/497984287.
Appveyor build 4310. State: success. Details: https://ci.appveyor.com/project/widelands-dev/widelands/build/_widelands_dev_widelands_bug_1810062_territorial_calculations-4310.

[hessenfarmer (stephan-lutz)]

Code looks very good. The effect is the bigger the more port spaces are available. As we had walked them probably twice before now we walk them only if they weren' touched. by the starting positions walk.

Thanks a lot for doing a great job.

If we want to count only walkable fields in the statistics this might be simply done by adding a maxcaps walkable check to line

https://bazaar.launchpad.net/~widelands-dev/widelands/bug-1810062-territorial-calculations/view/head:/src/logic/game.cc#L973

However in my opinion the stats should stay as they are, as I am trying sometimes to conquer the complete map and compare the value against the result of mapwidth * mapheight.

Only thing we could probably do is adding the term valuable to the territorial status messages to clearly distinguish that not all field are taken into account but only valuable fields.

[Toni Förster (stonerl)]

Would it somehow be feasible to have the stats win_condition dependent? So, only for Territorial have the max_caps check and for all others have it as it is now?

[GunChleoc (gunchleoc)]

Theoretically yes, but I am against this. The same button should always do the same thing for the user.

I'll add a statistics hook just like for Wood Gnome and Collectors.

[GunChleoc (gunchleoc)]

Adding a statistics hook is non-trivial, so I have created a bug for it:

https://bugs.launchpad.net/widelands/+bug/1817550

In the meantime, I expect that most players won't even notice the difference.

[hessenfarmer (stephan-lutz)]

Ok from my side.
So shall we have it then?

[GunChleoc (gunchleoc)]

Yes, let's have it.

@bunnybot merge

[hessenfarmer (stephan-lutz)]

Thanks again for the great work everybody. However travis si complaining about a missing newline in autogenerated rst files.

It might be the case we need to insert an empty line at this line
https://bazaar.launchpad.net/~widelands-dev/widelands/trunk/view/head:/src/scripting/lua_map.cc#L6612

[GunChleoc (gunchleoc)]

Thanks, should be fixed ow.

=== modified file 'data/scripting/win_conditions/artifacts.lua'
--- data/scripting/win_conditions/artifacts.lua	2018-04-15 09:11:29 +0000
+++ data/scripting/win_conditions/artifacts.lua	2019-02-26 05:56:29 +0000
@@ -15,10 +15,27 @@
 local wc_descname = _("Artifacts")
 local wc_version = 1
 local wc_desc = _ "Search for ancient artifacts. Once all of them are found, the team who owns most of them will win the game."
+
+-- Table of all artifacts to conquer
+local artifact_fields = {}
+
 return {
    name = wc_name,
    description = wc_desc,
    map_tags = { "artifacts" }, -- Map tags needed so that this win condition will be available only for suitable maps
+   init = function()
+      -- Find all artifacts
+      local map = wl.Game().map
+      for x=0, map.width-1 do
+         for y=0, map.height-1 do
+            local field = map:get_field(x,y)
+            if field.immovable and field.immovable:has_attribute("artifact") then
+               -- This assumes that the immovable has size small or medium, i.e. only occupies one field
+               table.insert(artifact_fields, map:get_field(x,y))
+            end
+         end
+      end
+   end,
    func = function()
       set_textdomain("win_conditions")
       -- set the objective with the game type for all players
@@ -33,22 +50,6 @@
          end
       end
 
-      local artifact_fields = {}
-      local map = wl.Game().map
-
-      local i = 1
-      -- find all artifacts
-      for x=0, map.width-1 do
-         for y=0, map.height-1 do
-            local field = map:get_field(x,y)
-            if field.immovable and field.immovable:has_attribute("artifact") then
-               -- this assumes that the immovable has size small or medium, i.e. only occupies one field
-               artifact_fields[i] = map:get_field(x,y)
-               i = i + 1
-            end
-         end
-      end
-
       local plrs = wl.Game().players
       if #artifact_fields == 0 then
          for idx, plr in ipairs(plrs) do

=== modified file 'data/scripting/win_conditions/territorial_functions.lua'
--- data/scripting/win_conditions/territorial_functions.lua	2019-02-12 17:30:21 +0000
+++ data/scripting/win_conditions/territorial_functions.lua	2019-02-26 05:56:29 +0000
@@ -14,27 +14,6 @@
 local wc_had_territory = _"%1$s had %2$3.0f%% of the land (%3$i of %4$i)."
 
 -- RST
--- .. function:: get_buildable_fields()
---
---    Collects all fields that are buildable
---
---    :returns: a table with the map's buildable fields
---
-function get_buildable_fields()
-   local fields = {}
-   local map = wl.Game().map
-   for x=0, map.width-1 do
-      for y=0, map.height-1 do
-         local f = map:get_field(x,y)
-         if f.buildable then
-            table.insert(fields, f)
-         end
-      end
-   end
-   return fields
-end
-
--- RST
 -- .. function:: count_owned_fields_for_all_players(fields, players)
 --
 --    Counts all owned fields for each player.
@@ -67,12 +46,10 @@
    return owned_fields
 end
 
-
 -- Used by calculate_territory_points keep track of when the winner changes
 local winning_players = {}
 local winning_teams = {}
 
-
 -- RST
 -- .. data:: territory_points
 --

=== modified file 'data/scripting/win_conditions/territorial_lord.lua'
--- data/scripting/win_conditions/territorial_lord.lua	2019-01-26 17:38:18 +0000
+++ data/scripting/win_conditions/territorial_lord.lua	2019-02-26 05:56:29 +0000
@@ -22,9 +22,17 @@
    "area. The winner will be the player or the team that is able to keep " ..
    "that area for at least 20 minutes."
 )
+
+-- Table of fields that are worth conquering
+local fields = {}
+
 return {
    name = wc_name,
    description = wc_desc,
+   init = function()
+      -- Get all valuable fields of the map
+      fields = wl.Game().map.conquerable_fields
+   end,
    func = function()
       local plrs = wl.Game().players
 
@@ -36,9 +44,6 @@
       -- time in secs, if == 0 -> victory
       territory_points.remaining_time = time_to_keep_territory
 
-      -- Get all valueable fields of the map
-      local fields = get_buildable_fields()
-
       local function _send_state()
          set_textdomain("win_conditions")
 

=== modified file 'data/scripting/win_conditions/territorial_time.lua'
--- data/scripting/win_conditions/territorial_time.lua	2019-01-26 17:38:18 +0000
+++ data/scripting/win_conditions/territorial_time.lua	2019-02-26 05:56:29 +0000
@@ -27,19 +27,22 @@
    "after 4 hours, whichever comes first."
 )
 
+-- Table of fields that are worth conquering
+local fields = {}
 
 return {
    name = wc_name,
    description = wc_desc,
+   init = function()
+      -- Get all valuable fields of the map
+      fields = wl.Game().map.conquerable_fields
+   end,
    func = function()
       local plrs = wl.Game().players
 
       -- set the objective with the game type for all players
       broadcast_objective("win_condition", wc_descname, wc_desc)
 
-      -- Get all valueable fields of the map
-      local fields = get_buildable_fields()
-
       -- variables to track the maximum 4 hours of gametime
       local remaining_max_time = 4 * 60 * 60 -- 4 hours
 

=== modified file 'data/scripting/win_conditions/wood_gnome.lua'
--- data/scripting/win_conditions/wood_gnome.lua	2019-02-09 07:51:55 +0000
+++ data/scripting/win_conditions/wood_gnome.lua	2019-02-26 05:56:29 +0000
@@ -20,9 +20,18 @@
 [[your territory than any other player. The game will end after 4 hours of ]] ..
 [[playing. The one with the most trees at that point will win the game.]])
 local wc_trees_owned = _"Trees owned"
+
+
+-- Table of terrestrial fields
+local fields = {}
+
 return {
    name = wc_name,
    description = wc_desc,
+   init = function()
+      -- Get all terrestrial fields of the map
+      fields = wl.Game().map.terrestrial_fields
+   end,
    func = function()
    local plrs = wl.Game().players
    local game = wl.Game()
@@ -33,21 +42,6 @@
    -- set the objective with the game type for all players
    broadcast_objective("win_condition", wc_descname, wc_desc)
 
-   -- Get all valueable fields of the map
-   local fields = {}
-   local map = wl.Game().map
-   for x=0,map.width-1 do
-      for y=0,map.height-1 do
-         local f = map:get_field(x,y)
-         if f then
-            -- add this field to the list as long as it has not movecaps swim
-            if not f:has_caps("swimmable") then
-               fields[#fields+1] = f
-            end
-         end
-      end
-   end
-
    -- The function to calculate the current points.
    local _last_time_calculated = -100000
    local _plrpoints = {}

=== modified file 'src/logic/field.h'
--- src/logic/field.h	2019-02-23 11:00:49 +0000
+++ src/logic/field.h	2019-02-26 05:56:29 +0000
@@ -92,6 +92,9 @@
 	NodeCaps nodecaps() const {
 		return static_cast<NodeCaps>(caps);
 	}
+	NodeCaps maxcaps() const {
+		return static_cast<NodeCaps>(max_caps);
+	}
 	uint16_t get_caps() const {
 		return caps;
 	}
@@ -237,6 +240,7 @@
 	BaseImmovable* immovable = nullptr;
 
 	uint8_t caps = 0U;
+	uint8_t max_caps = 0U;
 	uint8_t roads = 0U;
 
 	Height height = 0U;
@@ -254,9 +258,9 @@
 
 // Check that Field is tightly packed.
 #ifndef WIN32
-static_assert(sizeof(Field) == sizeof(void*) * 2 + 10, "Field is not tightly packed.");
+static_assert(sizeof(Field) == sizeof(void*) * 2 + 11, "Field is not tightly packed.");
 #else
-static_assert(sizeof(Field) <= sizeof(void*) * 2 + 11, "Field is not tightly packed.");
+static_assert(sizeof(Field) <= sizeof(void*) * 2 + 12, "Field is not tightly packed.");
 #endif
 }  // namespace Widelands
 

=== modified file 'src/logic/game.cc'
--- src/logic/game.cc	2019-02-23 11:00:49 +0000
+++ src/logic/game.cc	2019-02-26 05:56:29 +0000
@@ -314,13 +314,29 @@
 
 	// Check for win_conditions
 	if (!settings.scenario) {
-		std::unique_ptr<LuaTable> table(lua().run_script(settings.win_condition_script));
+		win_condition_script_ = settings.win_condition_script;
+		std::unique_ptr<LuaTable> table(lua().run_script(win_condition_script_));
 		table->do_not_warn_about_unaccessed_keys();
 		win_condition_displayname_ = table->get_string("name");
+		// We run the actual win condition from InteractiveGameBase::start() to prevent a pure black
+		// screen while the game is being started - we can display a message there.
+	} else {
+		win_condition_displayname_ = "Scenario";
+	}
+}
+
+void Game::run_win_condition() {
+	if (!win_condition_script_.empty()) {
+		std::unique_ptr<LuaTable> table(lua().run_script(win_condition_script_));
+		table->do_not_warn_about_unaccessed_keys();
+		// Run separate initialization function if it is there.
+		if (table->has_key<std::string>("init")) {
+			std::unique_ptr<LuaCoroutine> cr = table->get_coroutine("init");
+			cr->resume();
+		}
 		std::unique_ptr<LuaCoroutine> cr = table->get_coroutine("func");
 		enqueue_command(new CmdLuaCoroutine(get_gametime() + 100, std::move(cr)));
-	} else {
-		win_condition_displayname_ = "Scenario";
+		win_condition_script_ = "";
 	}
 }
 

=== modified file 'src/logic/game.h'
--- src/logic/game.h	2019-02-23 11:00:49 +0000
+++ src/logic/game.h	2019-02-26 05:56:29 +0000
@@ -176,6 +176,10 @@
 	void save_syncstream(bool save);
 	void init_newgame(UI::ProgressWindow* loader_ui, const GameSettings&);
 	void init_savegame(UI::ProgressWindow* loader_ui, const GameSettings&);
+
+	/// Run the win condition that is defined by win_condition_script_
+	void run_win_condition();
+
 	enum StartGameType { NewSPScenario, NewNonScenario, Loaded, NewMPScenario };
 
 	bool run(UI::ProgressWindow* loader_ui,
@@ -403,6 +407,7 @@
 
 	/// For save games and statistics generation
 	std::string win_condition_displayname_;
+	std::string win_condition_script_;
 	bool replay_;
 };
 

=== modified file 'src/logic/map.cc'
--- src/logic/map.cc	2019-02-23 11:00:49 +0000
+++ src/logic/map.cc	2019-02-26 05:56:29 +0000
@@ -28,6 +28,7 @@
 
 #include "base/log.h"
 #include "base/macros.h"
+#include "base/scoped_timer.h"
 #include "base/wexception.h"
 #include "build_info.h"
 #include "economy/flag.h"
@@ -43,6 +44,7 @@
 #include "logic/map_objects/world/terrain_description.h"
 #include "logic/map_objects/world/world.h"
 #include "logic/mapfringeregion.h"
+#include "logic/maphollowregion.h"
 #include "logic/objective.h"
 #include "logic/pathfield.h"
 #include "logic/player.h"
@@ -255,6 +257,109 @@
 		}
 }
 
+std::set<FCoords> Map::calculate_all_conquerable_fields() const {
+	std::set<FCoords> result;
+
+	std::set<FCoords> coords_to_check;
+
+	ScopedTimer timer("Calculating valuable fields took %ums");
+
+	// If we don't have the given coordinates yet, walk the map and collect conquerable fields,
+	// initialized with the given radius around the coordinates
+	const auto walk_starting_coords = [this, &result, &coords_to_check](
+	                                     const Coords& coords, int radius) {
+		FCoords fcoords = get_fcoords(coords);
+
+		// We already have these coordinates
+		if (result.count(fcoords) == 1) {
+			return;
+		}
+
+		// Add starting field
+		result.insert(fcoords);
+
+		// Add outer land coordinates around the starting field for the given radius
+		std::unique_ptr<Widelands::HollowArea<>> hollow_area(
+		   new Widelands::HollowArea<>(Widelands::Area<>(fcoords, radius), 2));
+		std::unique_ptr<Widelands::MapHollowRegion<>> map_region(
+		   new Widelands::MapHollowRegion<>(*this, *hollow_area));
+		do {
+			coords_to_check.insert(get_fcoords(map_region->location()));
+		} while (map_region->advance(*this));
+
+		// Walk the map
+		while (!coords_to_check.empty()) {
+			// Get some coordinates to check
+			const auto coords_it = coords_to_check.begin();
+			fcoords = *coords_it;
+
+			// Get region according to buildcaps
+			radius = 0;
+			int inner_radius = 2;
+			if ((fcoords.field->maxcaps() & BUILDCAPS_BIG) == BUILDCAPS_BIG) {
+				radius = 9;
+				inner_radius = 7;
+			} else if (fcoords.field->maxcaps() & BUILDCAPS_MEDIUM) {
+				radius = 7;
+				inner_radius = 5;
+			} else if (fcoords.field->maxcaps() & BUILDCAPS_SMALL) {
+				radius = 5;
+			}
+
+			// Check region and add walkable fields
+			if (radius > 0) {
+				hollow_area.reset(
+				   new Widelands::HollowArea<>(Widelands::Area<>(fcoords, radius), inner_radius));
+				map_region.reset(new Widelands::MapHollowRegion<>(*this, *hollow_area));
+				do {
+					fcoords = get_fcoords(map_region->location());
+
+					// We do the caps check first, because the comparison is faster than the container
+					// check
+					if ((fcoords.field->maxcaps() & MOVECAPS_WALK) && (result.count(fcoords) == 0)) {
+						result.insert(fcoords);
+						coords_to_check.insert(fcoords);
+					}
+				} while (map_region->advance(*this));
+			}
+
+			// These coordinates are done. We do not keep track of visited coordinates that didn't make
+			// the result, because the container insert operations are more expensive than the checks
+			coords_to_check.erase(coords_it);
+		}
+	};
+
+	// Walk the map from the starting field of each player
+	for (const Coords& coords : starting_pos_) {
+		walk_starting_coords(coords, 9);
+	}
+
+	// Walk the map from port spaces
+	if (allows_seafaring()) {
+		for (const Coords& coords : get_port_spaces()) {
+			walk_starting_coords(coords, 5);
+		}
+	}
+
+	log("Found %" PRIuS " valuable fields\n", result.size());
+	return result;
+}
+
+std::set<FCoords> Map::calculate_all_fields_excluding_caps(NodeCaps caps) const {
+	ScopedTimer timer("Calculating valuable fields took %ums");
+
+	std::set<FCoords> result;
+	for (MapIndex i = 0; i < max_index(); ++i) {
+		Field& field = fields_[i];
+		if (!(field.nodecaps() & caps)) {
+			result.insert(get_fcoords(field));
+		}
+	}
+
+	log("Found %" PRIuS " valuable fields\n", result.size());
+	return result;
+}
+
 /*
 ===============
 remove your world, remove your data
@@ -550,9 +655,9 @@
 }
 
 NodeCaps Map::get_max_nodecaps(const World& world, const FCoords& fc) const {
-	NodeCaps caps = calc_nodecaps_pass1(world, fc, false);
-	caps = calc_nodecaps_pass2(world, fc, false, caps);
-	return caps;
+	NodeCaps max_caps = calc_nodecaps_pass1(world, fc, false);
+	max_caps = calc_nodecaps_pass2(world, fc, false, max_caps);
+	return static_cast<NodeCaps>(max_caps);
 }
 
 /// \returns the immovable at the given coordinate
@@ -938,6 +1043,7 @@
 */
 void Map::recalc_nodecaps_pass1(const World& world, const FCoords& f) {
 	f.field->caps = calc_nodecaps_pass1(world, f, true);
+	f.field->max_caps = calc_nodecaps_pass1(world, f, false);
 }
 
 NodeCaps Map::calc_nodecaps_pass1(const World& world, const FCoords& f, bool consider_mobs) const {
@@ -1056,6 +1162,8 @@
 */
 void Map::recalc_nodecaps_pass2(const World& world, const FCoords& f) {
 	f.field->caps = calc_nodecaps_pass2(world, f, true);
+	f.field->max_caps =
+	   calc_nodecaps_pass2(world, f, false, static_cast<NodeCaps>(f.field->max_caps));
 }
 
 NodeCaps Map::calc_nodecaps_pass2(const World& world,

=== modified file 'src/logic/map.h'
--- src/logic/map.h	2019-02-23 11:00:49 +0000
+++ src/logic/map.h	2019-02-26 05:56:29 +0000
@@ -165,6 +165,12 @@
 	void recalc_whole_map(const World& world);
 	void recalc_for_field_area(const World& world, Area<FCoords>);
 
+	/// Calculates and returns a list of the fields that could be conquered by a player throughout a
+	/// game. Useful for territorial win conditions.
+	std::set<FCoords> calculate_all_conquerable_fields() const;
+	/// Calculates and returns a list of the fields that do not have the given caps.
+	std::set<FCoords> calculate_all_fields_excluding_caps(NodeCaps caps) const;
+
 	/***
 	 * Ensures that resources match their adjacent terrains.
 	 */

=== modified file 'src/logic/replay.cc'
--- src/logic/replay.cc	2019-02-23 11:00:49 +0000
+++ src/logic/replay.cc	2019-02-26 05:56:29 +0000
@@ -229,7 +229,6 @@
 		GameLoader gl(filename_ + kSavegameExtension, game);
 		gl.load_game();
 	}
-	game.postload();
 	log("Done reloading the game from replay\n");
 
 	game.enqueue_command(new CmdReplaySyncWrite(game.get_gametime() + kSyncInterval));

=== modified file 'src/scripting/lua_map.cc'
--- src/scripting/lua_map.cc	2019-02-23 11:00:49 +0000
+++ src/scripting/lua_map.cc	2019-02-26 05:56:29 +0000
@@ -71,6 +71,39 @@
 
 namespace {
 
+// Checks if a field has the desired caps
+bool check_has_caps(lua_State* L,
+                    const std::string& query,
+                    const FCoords& f,
+                    const NodeCaps& caps,
+                    const Widelands::Map& map) {
+	if (query == "walkable") {
+		return caps & MOVECAPS_WALK;
+	}
+	if (query == "swimmable") {
+		return caps & MOVECAPS_SWIM;
+	}
+	if (query == "small") {
+		return caps & BUILDCAPS_SMALL;
+	}
+	if (query == "medium") {
+		return caps & BUILDCAPS_MEDIUM;
+	}
+	if (query == "big") {
+		return (caps & BUILDCAPS_BIG) == BUILDCAPS_BIG;
+	}
+	if (query == "port") {
+		return (caps & BUILDCAPS_PORT) && map.is_port_space(f);
+	}
+	if (query == "mine") {
+		return caps & BUILDCAPS_MINE;
+	}
+	if (query == "flag") {
+		return caps & BUILDCAPS_FLAG;
+	}
+	report_error(L, "Unknown caps queried: %s!", query.c_str());
+}
+
 // Pushes a lua table with (name, count) pairs for the given 'ware_amount_container' on the
 // stack. The 'type' needs to be WARE or WORKER. Returns 1.
 int wares_or_workers_map_to_lua(lua_State* L,
@@ -1160,9 +1193,12 @@
 const PropertyType<LuaMap> LuaMap::Properties[] = {
    PROP_RO(LuaMap, allows_seafaring),
    PROP_RO(LuaMap, number_of_port_spaces),
+   PROP_RO(LuaMap, port_spaces),
    PROP_RO(LuaMap, width),
    PROP_RO(LuaMap, height),
    PROP_RO(LuaMap, player_slots),
+   PROP_RO(LuaMap, conquerable_fields),
+   PROP_RO(LuaMap, terrestrial_fields),
    {nullptr, nullptr, nullptr},
 };
 
@@ -1199,6 +1235,32 @@
 	lua_pushuint32(L, get_egbase(L).map().get_port_spaces().size());
 	return 1;
 }
+
+/* RST
+   .. attribute:: port_spaces
+
+      (RO) A list of coordinates for all port spaces on the map.
+
+      :returns: A table of port space coordinates,
+      like this: ``{{x = 0, y = 2}, {x = 54, y = 23}}``.
+*/
+int LuaMap::get_port_spaces(lua_State* L) {
+	lua_newtable(L);
+	int counter = 0;
+	for (const Coords& space : get_egbase(L).map().get_port_spaces()) {
+		lua_pushinteger(L, ++counter);
+		lua_newtable(L);
+		lua_pushstring(L, "x");
+		lua_pushint32(L, space.x);
+		lua_settable(L, -3);
+		lua_pushstring(L, "y");
+		lua_pushint32(L, space.y);
+		lua_settable(L, -3);
+		lua_settable(L, -3);
+	}
+	return 1;
+}
+
 /* RST
    .. attribute:: width
 
@@ -1237,6 +1299,42 @@
 	return 1;
 }
 
+/* RST
+   .. attribute:: conquerable_fields
+
+      (RO) Calculates and returns all reachable fields that a player could build on.
+
+      **Note:** This function is expensive, so call it seldom.
+*/
+int LuaMap::get_conquerable_fields(lua_State* L) {
+	lua_newtable(L);
+	int counter = 0;
+	for (const Widelands::FCoords& fcoords :
+	     get_egbase(L).map().calculate_all_conquerable_fields()) {
+		lua_pushinteger(L, ++counter);
+		to_lua<LuaMaps::LuaField>(L, new LuaMaps::LuaField(fcoords));
+		lua_settable(L, -3);
+	}
+	return 1;
+}
+
+/* RST
+   .. attribute:: terrestrial_fields
+
+      (RO) Calculates and returns all fields that are not swimmable.
+*/
+int LuaMap::get_terrestrial_fields(lua_State* L) {
+	lua_newtable(L);
+	int counter = 0;
+	for (const Widelands::FCoords& fcoords :
+	     get_egbase(L).map().calculate_all_fields_excluding_caps(MOVECAPS_SWIM)) {
+		lua_pushinteger(L, ++counter);
+		to_lua<LuaMaps::LuaField>(L, new LuaMaps::LuaField(fcoords));
+		lua_settable(L, -3);
+	}
+	return 1;
+}
+
 /*
  ==========================================================
  LUA METHODS
@@ -3798,7 +3896,11 @@
  PROPERTIES
  ==========================================================
  */
-// Hash is used to identify a class in a Set
+/* RST
+   .. attribute:: __hash
+
+      (RO) The map object's serial. Used to identify a class in a Set.
+*/
 int LuaMapObject::get___hash(lua_State* L) {
 	lua_pushuint32(L, get(L, get_egbase(L))->serial());
 	return 1;
@@ -5993,8 +6095,8 @@
 
 const char LuaField::className[] = "Field";
 const MethodType<LuaField> LuaField::Methods[] = {
-   METHOD(LuaField, __eq),     METHOD(LuaField, __tostring), METHOD(LuaField, region),
-   METHOD(LuaField, has_caps), {nullptr, nullptr},
+   METHOD(LuaField, __eq),     METHOD(LuaField, __tostring),   METHOD(LuaField, region),
+   METHOD(LuaField, has_caps), METHOD(LuaField, has_max_caps), {nullptr, nullptr},
 };
 const PropertyType<LuaField> LuaField::Properties[] = {
    PROP_RO(LuaField, __hash),
@@ -6038,10 +6140,13 @@
  PROPERTIES
  ==========================================================
  */
-// Hash is used to identify a class in a Set
+/* RST
+   .. attribute:: __hash
+
+      (RO) The hashed coordinates of the field's position. Used to identify a class in a Set.
+*/
 int LuaField::get___hash(lua_State* L) {
-	const std::string pushme = (boost::format("%i_%i") % coords_.x % coords_.y).str();
-	lua_pushstring(L, pushme.c_str());
+	lua_pushuint32(L, coords_.hash());
 	return 1;
 }
 
@@ -6458,45 +6563,51 @@
 
       Returns :const:`true` if the field has this caps associated
       with it, otherwise returns false.
+      Note: Immovables will hide the caps. If you want to have the caps
+      without immovables use has_max_caps instead
 
       :arg capname: can be either of
 
-      * :const:`small`: Can a small building be build here?
-      * :const:`medium`: Can a medium building be build here?
-      * :const:`big`: Can a big building be build here?
-      * :const:`mine`: Can a mine be build here?
-      * :const:`port`: Can a port be build here?
-      * :const:`flag`: Can a flag be build here?
+      * :const:`small`: Can a small building be built here?
+      * :const:`medium`: Can a medium building be built here?
+      * :const:`big`: Can a big building be built here?
+      * :const:`mine`: Can a mine be built here?
+      * :const:`port`: Can a port be built here?
+      * :const:`flag`: Can a flag be built here?
       * :const:`walkable`: Is this field passable for walking bobs?
       * :const:`swimmable`: Is this field passable for swimming bobs?
 */
 int LuaField::has_caps(lua_State* L) {
-	FCoords f = fcoords(L);
-	std::string query = luaL_checkstring(L, 2);
-
-	if (query == "walkable")
-		lua_pushboolean(L, f.field->nodecaps() & MOVECAPS_WALK);
-	else if (query == "swimmable")
-		lua_pushboolean(L, f.field->nodecaps() & MOVECAPS_SWIM);
-	else if (query == "small")
-		lua_pushboolean(L, f.field->nodecaps() & BUILDCAPS_SMALL);
-	else if (query == "medium")
-		lua_pushboolean(L, f.field->nodecaps() & BUILDCAPS_MEDIUM);
-	else if (query == "big")
-		lua_pushboolean(L, (f.field->nodecaps() & BUILDCAPS_BIG) == BUILDCAPS_BIG);
-	else if (query == "port") {
-		lua_pushboolean(
-		   L, (f.field->nodecaps() & BUILDCAPS_PORT) && get_egbase(L).map().is_port_space(f));
-	} else if (query == "mine")
-		lua_pushboolean(L, f.field->nodecaps() & BUILDCAPS_MINE);
-	else if (query == "flag")
-		lua_pushboolean(L, f.field->nodecaps() & BUILDCAPS_FLAG);
-	else
-		report_error(L, "Unknown caps queried: %s!", query.c_str());
-
-	return 1;
-}
-
+	const FCoords& f = fcoords(L);
+	std::string query = luaL_checkstring(L, 2);
+	lua_pushboolean(L, check_has_caps(L, query, f, f.field->nodecaps(), get_egbase(L).map()));
+	return 1;
+}
+
+/* RST
+   .. method:: has_max_caps(capname)
+
+      Returns :const:`true` if the field has this maximum caps (not taking immovables into account)
+      associated with it, otherwise returns false.
+
+      :arg capname: can be either of
+
+      * :const:`small`: Can a small building be built here?
+      * :const:`medium`: Can a medium building be built here?
+      * :const:`big`: Can a big building be built here?
+      * :const:`mine`: Can a mine be built here?
+      * :const:`port`: Can a port be built here?
+      * :const:`flag`: Can a flag be built here?
+      * :const:`walkable`: Is this field passable for walking bobs?
+      * :const:`swimmable`: Is this field passable for swimming bobs?
+*/
+int LuaField::has_max_caps(lua_State* L) {
+	const FCoords& f = fcoords(L);
+	std::string query = luaL_checkstring(L, 2);
+	lua_pushboolean(
+	   L, check_has_caps(L, luaL_checkstring(L, 2), f, f.field->maxcaps(), get_egbase(L).map()));
+	return 1;
+}
 /*
  ==========================================================
  C METHODS

=== modified file 'src/scripting/lua_map.h'
--- src/scripting/lua_map.h	2019-02-23 11:00:49 +0000
+++ src/scripting/lua_map.h	2019-02-26 05:56:29 +0000
@@ -88,9 +88,12 @@
 	 */
 	int get_allows_seafaring(lua_State*);
 	int get_number_of_port_spaces(lua_State*);
+	int get_port_spaces(lua_State*);
 	int get_width(lua_State*);
 	int get_height(lua_State*);
 	int get_player_slots(lua_State*);
+	int get_conquerable_fields(lua_State*);
+	int get_terrestrial_fields(lua_State*);
 
 	/*
 	 * Lua methods
@@ -1424,6 +1427,7 @@
 	int __eq(lua_State* L);
 	int region(lua_State* L);
 	int has_caps(lua_State*);
+	int has_max_caps(lua_State*);
 
 	/*
 	 * C methods

=== modified file 'src/wui/interactive_gamebase.cc'
--- src/wui/interactive_gamebase.cc	2019-02-23 11:00:49 +0000
+++ src/wui/interactive_gamebase.cc	2019-02-26 05:56:29 +0000
@@ -224,6 +224,8 @@
 }
 
 void InteractiveGameBase::start() {
+	game().run_win_condition();
+
 	// Multiplayer games don't save the view position, so we go to the starting position instead
 	if (is_multiplayer()) {
 		Widelands::PlayerNumber pln = player_number();

=== modified file 'test/maps/lua_testsuite.wmf/scripting/cfield.lua'
--- test/maps/lua_testsuite.wmf/scripting/cfield.lua	2016-07-10 19:03:33 +0000
+++ test/maps/lua_testsuite.wmf/scripting/cfield.lua	2019-02-26 05:56:29 +0000
@@ -8,12 +8,12 @@
    assert_equal(c.y, 32)
 end
 
-function field_tests:test_access_xistobig()
+function field_tests:test_access_xistoobig()
    assert_error("x should be too big", function()
       map:get_field(64, 23)
    end)
 end
-function field_tests:test_access_yistobig()
+function field_tests:test_access_yistoobig()
    assert_error("y should be too big", function()
       map:get_field(25, 80)
    end)
@@ -23,10 +23,10 @@
       map:get_field(64)
    end)
 end
-function field_tests:test_access_xisnegativ()
+function field_tests:test_access_xisnegative()
    assert_error("x is negativ", function() map:get_field(-12, 23) end)
 end
-function field_tests:test_access_yisnegativ()
+function field_tests:test_access_yisnegative()
    assert_error("y is negativ", function() map:get_field(25, -12) end)
 end
 function field_tests:test_direct_change_impossible()
@@ -34,7 +34,12 @@
    assert_error("c.y should be read only", function() c.y = 12 end)
 end
 function field_tests:test_hash()
-   assert_equal("25_40", map:get_field(25,40).__hash)
+   assert_equal(1638440, map:get_field(25,40).__hash)
+end
+function field_tests:test_coordinates()
+   local field = map:get_field(25,40);
+   assert_equal(25, field.x)
+   assert_equal(40, field.y)
 end
 
 function field_tests:test_r_neighbour()
@@ -212,6 +217,15 @@
    assert_equal(false, f:has_caps("swimmable"))
    assert_equal(true, f:has_caps("walkable"))
    assert_equal(false, f:has_caps("port"))
+
+   assert_equal(true, f:has_max_caps("small"))
+   assert_equal(true, f:has_max_caps("medium"))
+   assert_equal(true, f:has_max_caps("big"))
+   assert_equal(true, f:has_max_caps("flag"))
+   assert_equal(false, f:has_max_caps("mine"))
+   assert_equal(false, f:has_max_caps("swimmable"))
+   assert_equal(true, f:has_max_caps("walkable"))
+   assert_equal(false, f:has_max_caps("port"))
 end
 function field_caps_tests:test_flag_field_on_land()
    local f = map:get_field(1,53)
@@ -223,6 +237,15 @@
    assert_equal(false, f:has_caps("swimmable"))
    assert_equal(true, f:has_caps("walkable"))
    assert_equal(false, f:has_caps("port"))
+
+   assert_equal(false, f:has_max_caps("small"))
+   assert_equal(false, f:has_max_caps("medium"))
+   assert_equal(false, f:has_max_caps("big"))
+   assert_equal(true, f:has_max_caps("flag"))
+   assert_equal(false, f:has_max_caps("mine"))
+   assert_equal(false, f:has_max_caps("swimmable"))
+   assert_equal(true, f:has_max_caps("walkable"))
+   assert_equal(false, f:has_max_caps("port"))
 end
 function field_caps_tests:test_mine_field()
    local f = map:get_field(63,54)
@@ -234,6 +257,15 @@
    assert_equal(false, f:has_caps("swimmable"))
    assert_equal(true, f:has_caps("walkable"))
    assert_equal(false, f:has_caps("port"))
+
+   assert_equal(false, f:has_max_caps("small"))
+   assert_equal(false, f:has_max_caps("medium"))
+   assert_equal(false, f:has_max_caps("big"))
+   assert_equal(true, f:has_max_caps("flag"))
+   assert_equal(true, f:has_max_caps("mine"))
+   assert_equal(false, f:has_max_caps("swimmable"))
+   assert_equal(true, f:has_max_caps("walkable"))
+   assert_equal(false, f:has_max_caps("port"))
 end
 function field_caps_tests:test_field_on_water()
    local f = map:get_field(7,58)
@@ -245,6 +277,15 @@
    assert_equal(true, f:has_caps("swimmable"))
    assert_equal(false, f:has_caps("walkable"))
    assert_equal(false, f:has_caps("port"))
+
+   assert_equal(false, f:has_max_caps("small"))
+   assert_equal(false, f:has_max_caps("medium"))
+   assert_equal(false, f:has_max_caps("big"))
+   assert_equal(false, f:has_max_caps("flag"))
+   assert_equal(false, f:has_max_caps("mine"))
+   assert_equal(true, f:has_max_caps("swimmable"))
+   assert_equal(false, f:has_max_caps("walkable"))
+   assert_equal(false, f:has_max_caps("port"))
 end
 function field_caps_tests:test_port_field()
    local f = map:get_field(9,56)
@@ -256,15 +297,47 @@
    assert_equal(false, f:has_caps("swimmable"))
    assert_equal(true, f:has_caps("walkable"))
    assert_equal(true, f:has_caps("port"))
+
+   assert_equal(true, f:has_max_caps("small"))
+   assert_equal(true, f:has_max_caps("medium"))
+   assert_equal(true, f:has_max_caps("big"))
+   assert_equal(true, f:has_max_caps("flag"))
+   assert_equal(false, f:has_max_caps("mine"))
+   assert_equal(false, f:has_max_caps("swimmable"))
+   assert_equal(true, f:has_max_caps("walkable"))
+   assert_equal(true, f:has_max_caps("port"))
 end
 
+function field_caps_tests:test_field_with_immovable()
+   local field = map:get_field(1,53)
+   assert_equal(true, field:has_caps("flag"))
+   assert_equal(true, field:has_max_caps("flag"))
+
+   local flag = player1:place_flag(field, true)
+   assert_equal(false, field:has_caps("flag"))
+   assert_equal(true, field:has_max_caps("flag"))
+
+   flag:remove()
+   assert_equal(true, field:has_caps("flag"))
+   assert_equal(true, field:has_max_caps("flag"))
+ end
+
+
 function field_caps_tests:test_wrong_call()
    assert_error("Unknown caps", function()
       map:get_field(7,58):has_caps("blahfasel")
    end)
 end
 
+function field_caps_tests:test_conquerable_fields_does_not_crash()
+   local fields = map.conquerable_fields
+   assert_equal(false, fields[1] == nil)
+end
 
+function field_caps_tests:test_terrestrial_fields_does_not_crash()
+   local fields = map.terrestrial_fields
+   assert_equal(false, fields[1] == nil)
+end
 
 -- ===============
 -- owner/claimers

=== modified file 'test/maps/two_ponds.wmf/scripting/test_seafaring.lua'
--- test/maps/two_ponds.wmf/scripting/test_seafaring.lua	2018-04-11 06:55:01 +0000
+++ test/maps/two_ponds.wmf/scripting/test_seafaring.lua	2019-02-26 05:56:29 +0000
@@ -33,6 +33,14 @@
    map:recalculate_seafaring()
    assert_equal(true, map.allows_seafaring)
 
+   local port_spaces = map.port_spaces
+   assert_equal(port_spaces[1]["x"], 0)
+   assert_equal(port_spaces[1]["y"], 2)
+   assert_equal(port_spaces[2]["x"], 7)
+   assert_equal(port_spaces[2]["y"], 2)
+   assert_equal(port_spaces[3]["x"], 12)
+   assert_equal(port_spaces[3]["y"], 24)
+
   -- Remove the port space again
    assert_equal(true, map:set_port_space(0, 2, false))
    assert_equal(2, map.number_of_port_spaces)