connect_flags.lua

use("aux", "set")

-- Connects "start_flag" and "end_flag" with a road with as many flags set as
-- possible. Returns true when a road is build, false on error. This is
-- implemented as a straightforward A* implementation.
function connect_flags(start_flag, end_flag)
   local start_field = start_flag.fields[1]
   local end_field = end_flag.fields[1]

   local closed_set = Set:new()
   local open_set = Set:new{start_field}
   local parent = Set:new()

   local sqr = function(a) return a*a end
   -- The distance heuristic function that distinguishes A* from dijkstra.
   local h = function(field1, field2)
      return math.sqrt(sqr(field1.x - field2.x) + sqr(field1.y - field2.y))
   end

   -- Some helpers to turn fields into unique hashes and back again. The
   -- problem is that Lua does not allow us to define a custom hash value for
   -- our Fields, so we have to cheat and keep track of them using strings.
   local hash = function(field)
      -- same as field.__hash, but we do not want to rely on its
      -- implementation.
      return ("%d_%d"):format(field.x, field.y)
   end
   local map = wl.Game().map
   local field = function(hash)
      local x, y = hash:match("(%d+)_(%d+)")
      return map:get_field(x, y)
   end

   local g_score = {
      [hash(start_field)] = 0
   }
   -- TODO: replace by a heap implementation
   local f_score = {
      [hash(start_field)] = 0 + h(start_field, end_field)
   }

   -- Returns the field that has the lowest f_score.
   local next_field_to_consider = function()
      local smallest_val, f = math.huge, nil
      for field in open_set:items() do
         local h = hash(field)
         if f_score[h] < smallest_val then
            smallest_val = f_score[h]
            f = field
         end
      end
      return f
   end

   -- Does the actual road building.
   local build_road = function(current)
      -- Construct the path, end to start
      local path = {end_field}
      while current ~= start_field do
         path[#path + 1] = current
         current = field(parent[hash(current)])
      end
      path[#path + 1] = current
      -- Now flip it.
      for i=1,math.floor(#path/2) do
         path[i], path[#path + 1 - i] = path[#path + 1 - i], path[i]
      end

      -- Convert the path into the commands for road building.
      local commands = {}
      for i=1,#path-1 do
         for idx, n in ipairs{"trn", "rn", "brn", "bln", "ln", "tln"} do
            if path[i][n] == path[i+1] then
               commands[#commands+1] = n:sub(0, #n-1)
            end
         end
      end
      start_flag.owner:place_road(start_flag, unpack(commands))

      -- Place as many flags as possible.
      for i=1,#path do
         if path[i]:has_caps("flag") then
            start_flag.owner:place_flag(path[i])
         end
      end
   end

   while open_set.size > 0 do
      local current = next_field_to_consider()
      if current == end_field then
         build_road(current)
         return true
      end

      open_set:discard(current)
      closed_set:add(current)

      for idx, n in ipairs{"trn", "rn", "brn", "bln", "ln", "tln"} do
         local neighbor = current[n]
         if not closed_set:contains(neighbor) and
            (neighbor:has_caps("walkable") or (neighbor.immovable and neighbor.immovable.name == "flag"))
         then
            -- TODO: could take steepness into account here. But h() must be change then too.
            local tentative_g_score = g_score[hash(current)] + 1

            if not open_set:contains(neighbor) or tentative_g_score < g_score[hash(neighbor)] then
               local nh = hash(neighbor)
               parent[nh] = hash(current)
               g_score[nh] = tentative_g_score
               f_score[nh] = g_score[nh] + h(neighbor, end_field)
               open_set:add(neighbor)
            end
         end
      end
   end
   return false
end