widelands-dev team mailing list archive

[Toni Förster <toni.foerster@xxxxxxxxx>]

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.

Diff comments:

> === 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-20 16:25:30 +0000
> @@ -14,24 +14,77 @@
>  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
> +-- .. function:: get_valuable_fields()
> +--
> +--    Collects all fields that are valuable
> +--
> +--    :returns: a table with the map's valuable fields
> +--
> +function get_valuable_fields()
> +
> +   local result = {}
> +
> +   print_loading_message("Counting valuable fields took", function()
> +
> +      local fields = {}
> +      local check = {}
> +      local starttime = ticks()
> +      local map = wl.Game().map
> +      local plrs = wl.Game().players
> +
> +      -- Initialize with starting fields and port spaces
> +      for idx, player in ipairs(plrs) do
> +         local sf = map.player_slots[idx].starting_field
> +      -- initialize the fields table and the check area with the regions around the starting field of each Player
> +         for idx, fg in ipairs(sf:region(9)) do
> +            fields[fg.__hash] = fg
> +            check[fg.__hash] = fg
> +         end
> +      end
> +      if map.allows_seafaring == true then
> +         -- add port spaces to the starting check area
> +         for idx, spaces in ipairs(map.port_spaces) do
> +            local f = map:get_field(spaces["x"],spaces["y"])
> +            for idx, fg in ipairs(f:region(5)) do
> +               fields[fg.__hash] = fg
> +               check[fg.__hash] = fg
> +            end
> +         end
> +      end
> +
> +      -- Walk the map
> +      repeat
> +         local no_new_fields = true
> +         local new = {}
> +         -- checking the check region for buildcaps and add fields that can be conquered
> +         for idx, f in pairs(check) do
> +            local radius ={}
> +            if f:has_max_caps("big") then
> +               radius = f:region(9)

radius = f:region(9,7)

> +            elseif f:has_max_caps("medium") then
> +               radius = f:region(7)

radius = f:region(7,5)

> +            elseif f:has_max_caps("small") then
> +               radius = f:region(5)
> +            end
> +            for idx, fg in ipairs(radius) do
> +               if check[fg.__hash] == nil and fields[fg.__hash] == nil and fg:has_max_caps("walkable") then
> +                  no_new_fields = false
> +                  new[fg.__hash] = fg
> +                  fields[fg.__hash] = fg
> +               end
> +            end
> +         end
> +         check = new
> +      until no_new_fields
> +
> +      -- as our fields table is not continuosly indexed we need to build a properly indexed table
> +      for idx,f in pairs(fields) do
> +         table.insert(result, f)
> +      end
> +   end)
> +
> +   print(('We found %d valuable fields'):format(#result))
> +   return result
>  end
>  
>  -- RST


-- 
https://code.launchpad.net/~widelands-dev/widelands/bug-1810062-territorial-calculations/+merge/361366
Your team Widelands Developers is subscribed to branch lp:~widelands-dev/widelands/bug-1810062-territorial-calculations.