Difference between revisions of "LuaWML/Pathfinder"

From The Battle for Wesnoth Wiki
m (Vultraz moved page LuaWML:Pathfinder to LuaWML/Pathfinder)
(wesnoth.find_path)
(8 intermediate revisions by 2 users not shown)
Line 3: Line 3:
 
==== wesnoth.find_path ====
 
==== wesnoth.find_path ====
  
* '''wesnoth.find_path(''x1'', ''y1'', ''x2'', ''y2'', [''path_options'' | ''cost_function''])'''
+
* '''Wesnoth 1.14 and earlier: wesnoth.find_path(''x1'', ''y1'', ''x2'', ''y2'', [''path_options'' | ''cost_function''])'''
 +
* '''Wesnoth 1.15 and later: wesnoth.find_path(''x1'', ''y1'', ''x2'', ''y2'', [''path_options''])''' (the cost function has been moved into the ''path_options'' table)
 
* '''wesnoth.find_path(''x1'', ''y1'', ''x2'', ''y2'', ''cost_function'', ''width'', ''height'')''', in map generation code. (see [[MapGeneratorWML#The_lua_generator]])
 
* '''wesnoth.find_path(''x1'', ''y1'', ''x2'', ''y2'', ''cost_function'', ''width'', ''height'')''', in map generation code. (see [[MapGeneratorWML#The_lua_generator]])
  
 
Returns the shortest path from one location to another. The source location is given either by coordinates as two arguments x and y; there must be a unit at the source location when using the standard path calculator. The source location can also be given by a unit as a single argument (as returned by the functions from [[LuaWML:Units]]). The second location is given by its coordinates. The last argument is an optional table that can be used to parametrize the pathfinder. Its options are:
 
Returns the shortest path from one location to another. The source location is given either by coordinates as two arguments x and y; there must be a unit at the source location when using the standard path calculator. The source location can also be given by a unit as a single argument (as returned by the functions from [[LuaWML:Units]]). The second location is given by its coordinates. The last argument is an optional table that can be used to parametrize the pathfinder. Its options are:
 
* '''max_cost''': if set, the pathfinder will ignore paths longer than its value
 
* '''max_cost''': if set, the pathfinder will ignore paths longer than its value
* '''ignore_units''': if set, the path will go through units and ignore zones of control
+
* '''ignore_units''': if set, the path will go through units and ignore zones of control. Note: hidden enemies are always ignored, whether this parameter is set or not, unless viewing_side (below) is set to an invalid side.
 
* '''ignore_teleport''': if set, the teleport ability of the unit is ignored
 
* '''ignore_teleport''': if set, the teleport ability of the unit is ignored
* '''viewing_side''': if set to a valid side number, fog and shroud for this side will be taken into account; if set to an invalid number (e.g. 0), fog and shroud will be ignored; if left unset, the viewing side will be the unit side
+
* '''viewing_side''': if set to a valid side number, fog and shroud for this side will be taken into account; if set to an invalid number (e.g. 0), fog and shroud will be ignored and hidden units will be taken into account as well; if left unset, the viewing side will be the unit side
 +
* {{DevFeature1.15|0}} '''calculate''': a cost function to be passed to the pathfinder (see below). Having this as part of the table, instead of in place of it as it was before Wesnoth 1.15, means that the other options can be chosen as desired at the same time.
  
 
The path is returned as a table of coordinate pairs. It contains both the source and destination tile if a path was found. The total cost of the path is also available as a second return value, if needed.
 
The path is returned as a table of coordinate pairs. It contains both the source and destination tile if a path was found. The total cost of the path is also available as a second return value, if needed.
Line 25: Line 27:
 
  end
 
  end
  
Instead of a parameter table, a cost function can be passed to the pathfinder. It will be called for all the tiles the computed path may possibly go through. It receives three arguments. The first two are the coordinates of the tile, the last one is the current cost for reaching that tile. The function should return a floating-point value that is the cost for entering the given tile. This cost should be greater or equal to one.
+
As part of the parameter table (Wesnoth 1.15 and later) or instead of it (Wesnoth 1.14 and earlier), a '''cost function''' can be passed to the pathfinder. It is called for all the tiles the computed path may possibly go through. It receives three arguments. The first two are the coordinates of the tile, the last one is the current cost for reaching that tile. The function should return a floating-point value that is the cost for entering the given tile. This cost should be greater or equal to one.
  
 +
'''Cost function syntax Wesnoth 1.14 and earlier:'''
 
  -- Count how many turns it would take, assuming the worst case (3 movement points per tile)
 
  -- Count how many turns it would take, assuming the worst case (3 movement points per tile)
 
  local max_moves = wesnoth.get_units({ x = x1, y = y1 })[1].max_moves
 
  local max_moves = wesnoth.get_units({ x = x1, y = y1 })[1].max_moves
Line 35: Line 38:
 
         return current_cost + 3
 
         return current_cost + 3
 
     end)
 
     end)
 +
wesnoth.message(string.format("It would take %d turns.", math.ceil(cost / 3)))
 +
 +
'''Cost function syntax Wesnoth 1.15 and later:'''
 +
-- Count how many turns it would take, assuming the worst case (3 movement points per tile)
 +
local max_moves = wesnoth.get_units({ x = x1, y = y1 })[1].max_moves
 +
local path, cost = wesnoth.find_path(x1, y2, x2, y2, {
 +
    calculate = function(x, y, current_cost)
 +
        local remaining_moves = max_moves - (current_cost % max_moves)
 +
        if remaining_moves < 3 then current_cost = current_cost + remaining_moves end
 +
        return current_cost + 3
 +
    end })
 
  wesnoth.message(string.format("It would take %d turns.", math.ceil(cost / 3)))
 
  wesnoth.message(string.format("It would take %d turns.", math.ceil(cost / 3)))
  
Line 41: Line 55:
 
* '''wesnoth.find_vacant_tile(''x'', ''y'', [''unit''])'''
 
* '''wesnoth.find_vacant_tile(''x'', ''y'', [''unit''])'''
  
Returns the two coordinates of an empty tile the closest to the tile passed by coordinates. An optional unit (either a WML table or a proxy object) can be passed as a third argument; if so, the returned tile has terrain which is passable for the passed unit.
+
Returns the two coordinates of an empty tile the closest to the tile passed by coordinates. An optional unit (either a WML table or a proxy object) can be passed as a third argument; if so, the returned tile has terrain which is passable for the passed unit.  Note: hidden units are always seen by this function, no matter whether they are visible to the side of the passed unit.
  
 
  function teleport(src_x, src_y, dst_x, dst_y)
 
  function teleport(src_x, src_y, dst_x, dst_y)
Line 57: Line 71:
 
Returns all the locations reachable by a unit. The unit is given either by its two coordinates or by a proxy object.  The last argument is an optional table that can be used to parametrize the pathfinder. Its options are:
 
Returns all the locations reachable by a unit. The unit is given either by its two coordinates or by a proxy object.  The last argument is an optional table that can be used to parametrize the pathfinder. Its options are:
 
* '''additional_turns''': if set to an integer n, the pathfinder will consider tiles that can be reached in n+1 turns
 
* '''additional_turns''': if set to an integer n, the pathfinder will consider tiles that can be reached in n+1 turns
* '''ignore_units''': if set, the paths will go through units and ignore zones of control
+
* '''ignore_units''': if set, the paths will go through units and ignore zones of control. Note: hidden enemies are always ignored, whether this parameter is set or not, unless viewing_side (below) is set to an invalid side.
 
* '''ignore_teleport''': if set, the teleport ability of the unit is ignored
 
* '''ignore_teleport''': if set, the teleport ability of the unit is ignored
* '''viewing_side''': if set to a valid side number, fog and shroud for this side will be taken into account; if set to an invalid number (e.g. 0), fog and shroud will be ignored; if left unset, the viewing side will be the unit side
+
* '''viewing_side''': if set to a valid side number, fog and shroud for this side will be taken into account; if set to an invalid number (e.g. 0), fog and shroud will be ignored and hidden units will be taken into account as well; if left unset, the viewing side will be the unit side
 
The locations are stored as triples in an array. The first two elements of a triple are the coordinates of a reachable tile, the third one is the number of movement points left when reaching the tile.
 
The locations are stored as triples in an array. The first two elements of a triple are the coordinates of a reachable tile, the third one is the number of movement points left when reaching the tile.
  
Line 71: Line 85:
 
==== wesnoth.find_cost_map ====
 
==== wesnoth.find_cost_map ====
  
Builds a cost map for one, multiple units or unit types.
+
Builds a cost map for one unit, multiple units and/or one or multiple unit types.
 
In a cost map each hex is mapped to two values:
 
In a cost map each hex is mapped to two values:
 
a) The summed cost to reach this hex for all input units
 
a) The summed cost to reach this hex for all input units
 
b) A value which indicates how many units can reach this hex
 
b) A value which indicates how many units can reach this hex
 
The caller can divide a) with b) to get a average cost to reach this hex for the input units.
 
The caller can divide a) with b) to get a average cost to reach this hex for the input units.
The costs will consider movement lost during turn changes. (So with simple calculus it is possible to get the turns to reach a hex)
+
The costs consider movement lost during turn changes.
 
   
 
   
Input arguments:
+
'''Input arguments''':
* 1 + 2. A units location
+
* 1. The unit(s) for which to calculate the cost map.  This can be
* '''OR''' 1. A unit
+
** a proxy unit
* '''OR''' 1. A unit filter
+
** '''or''' a unit filter
* 2. (optional) A array of triples (coordinates + unit type as string)
+
** '''or''' a unit's coordinates (in this case this is actually 2 arguments)
 +
* 2. (optional) The unit type(s) for which to calculate the cost map.  This argument must be an array of quadruples, each with the following elements:
 +
** 1. + 2.: coordinates from which to calculate the cost map
 +
** 3.: side of the unit
 +
** 4.: unit type as a string
 +
** '''Note''':  If the array of unit types is given the units will be added to the first parameter. Use an empty filter or an invalid location for the first argument to add only unit types.
 
* 3. (optional) A table with options: ignore_units, ignore_teleport, viewing_side, debug, use_max_moves
 
* 3. (optional) A table with options: ignore_units, ignore_teleport, viewing_side, debug, use_max_moves
* 4. (optional) A [[StandardLocationFilter|Standard Location Filter]].
+
** '''Note''': unlike most other Wesnoth Lua functions, ignore_units defaults to true.
   
+
* 4. (optional) A [[StandardLocationFilter|Standard Location Filter]].  If given, the cost map will be calculated only for the locations satisfying this SLF.
If the array of unit types is given the units will be added to the first parameter. Use a empty filter or a invalid location to only add unit types.
+
 
+
'''Return value''':
Return value:
+
A array of quadruples (coordinates + summed cost + reach count).  The cost is set to -1 if not unit can reach the hex.
A array of quadruples (coordinates + a summed cost + reach count)
+
 
   
+
  local leader = wesnoth.get_units { side = wesnoth.current.side, canrecruit = 'yes' }[1]
A location set can be build by calling location.set.of_pairs(retval).
+
local cost_map = wesnoth.find_cost_map(leader)
 +
local cost_map = wesnoth.find_cost_map(19, 4)
 +
local cost_map = wesnoth.find_cost_map({ side = wesnoth.current.side, canrecruit = 'yes' })
 +
local cost_map = wesnoth.find_cost_map({ side = 999 }, { { 24, 7, wesnoth.current.side, "Vampire Bat" } })
  
 
==== helper.distance_between ====
 
==== helper.distance_between ====

Revision as of 16:31, 14 December 2020

This page describes the LuaWML functions and helpers for finding paths.

wesnoth.find_path

  • Wesnoth 1.14 and earlier: wesnoth.find_path(x1, y1, x2, y2, [path_options | cost_function])
  • Wesnoth 1.15 and later: wesnoth.find_path(x1, y1, x2, y2, [path_options]) (the cost function has been moved into the path_options table)
  • wesnoth.find_path(x1, y1, x2, y2, cost_function, width, height), in map generation code. (see MapGeneratorWML#The_lua_generator)

Returns the shortest path from one location to another. The source location is given either by coordinates as two arguments x and y; there must be a unit at the source location when using the standard path calculator. The source location can also be given by a unit as a single argument (as returned by the functions from LuaWML:Units). The second location is given by its coordinates. The last argument is an optional table that can be used to parametrize the pathfinder. Its options are:

  • max_cost: if set, the pathfinder will ignore paths longer than its value
  • ignore_units: if set, the path will go through units and ignore zones of control. Note: hidden enemies are always ignored, whether this parameter is set or not, unless viewing_side (below) is set to an invalid side.
  • ignore_teleport: if set, the teleport ability of the unit is ignored
  • viewing_side: if set to a valid side number, fog and shroud for this side will be taken into account; if set to an invalid number (e.g. 0), fog and shroud will be ignored and hidden units will be taken into account as well; if left unset, the viewing side will be the unit side
  • (Version 1.15.0 and later only) calculate: a cost function to be passed to the pathfinder (see below). Having this as part of the table, instead of in place of it as it was before Wesnoth 1.15, means that the other options can be chosen as desired at the same time.

The path is returned as a table of coordinate pairs. It contains both the source and destination tile if a path was found. The total cost of the path is also available as a second return value, if needed.

-- Display some items along the path from (x1,y1) to (x2,y2).
local u = wesnoth.get_units({ x = x1, y = y1 })[1]
local path, cost = wesnoth.find_path(u, x2, y2, { ignore_units = true, viewing_side = 0 })
if cost > u.moves then
    wesnoth.message("That's too far!")
else
    for i, loc in ipairs(path) do
        wesnoth.fire("item", { x = loc[1], y = loc[2], image = "items/buckler.png" })
    end
end

As part of the parameter table (Wesnoth 1.15 and later) or instead of it (Wesnoth 1.14 and earlier), a cost function can be passed to the pathfinder. It is called for all the tiles the computed path may possibly go through. It receives three arguments. The first two are the coordinates of the tile, the last one is the current cost for reaching that tile. The function should return a floating-point value that is the cost for entering the given tile. This cost should be greater or equal to one.

Cost function syntax Wesnoth 1.14 and earlier:

-- Count how many turns it would take, assuming the worst case (3 movement points per tile)
local max_moves = wesnoth.get_units({ x = x1, y = y1 })[1].max_moves
local path, cost = wesnoth.find_path(x1, y2, x2, y2,
    function(x, y, current_cost)
        local remaining_moves = max_moves - (current_cost % max_moves)
        if remaining_moves < 3 then current_cost = current_cost + remaining_moves end
        return current_cost + 3
    end)
wesnoth.message(string.format("It would take %d turns.", math.ceil(cost / 3)))

Cost function syntax Wesnoth 1.15 and later:

-- Count how many turns it would take, assuming the worst case (3 movement points per tile)
local max_moves = wesnoth.get_units({ x = x1, y = y1 })[1].max_moves
local path, cost = wesnoth.find_path(x1, y2, x2, y2, {
    calculate = function(x, y, current_cost)
        local remaining_moves = max_moves - (current_cost % max_moves)
        if remaining_moves < 3 then current_cost = current_cost + remaining_moves end
        return current_cost + 3
    end })
wesnoth.message(string.format("It would take %d turns.", math.ceil(cost / 3)))

wesnoth.find_vacant_tile

  • wesnoth.find_vacant_tile(x, y, [unit])

Returns the two coordinates of an empty tile the closest to the tile passed by coordinates. An optional unit (either a WML table or a proxy object) can be passed as a third argument; if so, the returned tile has terrain which is passable for the passed unit. Note: hidden units are always seen by this function, no matter whether they are visible to the side of the passed unit.

function teleport(src_x, src_y, dst_x, dst_y)
  local u = wesnoth.get_units({x = src_x, y = src_y })[1]
  local ut = u.__cfg
  dst_x, dst_y = wesnoth.find_vacant_tile(dst_x, dst_y, u)
  wesnoth.put_unit(src_x, src_y)
  wesnoth.put_unit(dst_x, dst_y, ut)
end

wesnoth.find_reach

  • wesnoth.find_reach(unit, [path_options])

Returns all the locations reachable by a unit. The unit is given either by its two coordinates or by a proxy object. The last argument is an optional table that can be used to parametrize the pathfinder. Its options are:

  • additional_turns: if set to an integer n, the pathfinder will consider tiles that can be reached in n+1 turns
  • ignore_units: if set, the paths will go through units and ignore zones of control. Note: hidden enemies are always ignored, whether this parameter is set or not, unless viewing_side (below) is set to an invalid side.
  • ignore_teleport: if set, the teleport ability of the unit is ignored
  • viewing_side: if set to a valid side number, fog and shroud for this side will be taken into account; if set to an invalid number (e.g. 0), fog and shroud will be ignored and hidden units will be taken into account as well; if left unset, the viewing side will be the unit side

The locations are stored as triples in an array. The first two elements of a triple are the coordinates of a reachable tile, the third one is the number of movement points left when reaching the tile.

-- overlay the number of turns needed to reach each tile
local t = wesnoth.find_reach(u, { additional_turns = 8 })
local m = u.max_moves
for i,l in ipairs(t) do
  wesnoth.fire("label", { x = l[1], y = l[2], text = math.ceil(9 - l[3]/m) })
end

wesnoth.find_cost_map

Builds a cost map for one unit, multiple units and/or one or multiple unit types. In a cost map each hex is mapped to two values: a) The summed cost to reach this hex for all input units b) A value which indicates how many units can reach this hex The caller can divide a) with b) to get a average cost to reach this hex for the input units. The costs consider movement lost during turn changes.

Input arguments:

  • 1. The unit(s) for which to calculate the cost map. This can be
    • a proxy unit
    • or a unit filter
    • or a unit's coordinates (in this case this is actually 2 arguments)
  • 2. (optional) The unit type(s) for which to calculate the cost map. This argument must be an array of quadruples, each with the following elements:
    • 1. + 2.: coordinates from which to calculate the cost map
    • 3.: side of the unit
    • 4.: unit type as a string
    • Note: If the array of unit types is given the units will be added to the first parameter. Use an empty filter or an invalid location for the first argument to add only unit types.
  • 3. (optional) A table with options: ignore_units, ignore_teleport, viewing_side, debug, use_max_moves
    • Note: unlike most other Wesnoth Lua functions, ignore_units defaults to true.
  • 4. (optional) A Standard Location Filter. If given, the cost map will be calculated only for the locations satisfying this SLF.

Return value: A array of quadruples (coordinates + summed cost + reach count). The cost is set to -1 if not unit can reach the hex.

local leader = wesnoth.get_units { side = wesnoth.current.side, canrecruit = 'yes' }[1]
local cost_map = wesnoth.find_cost_map(leader)
local cost_map = wesnoth.find_cost_map(19, 4)
local cost_map = wesnoth.find_cost_map({ side = wesnoth.current.side, canrecruit = 'yes' })
local cost_map = wesnoth.find_cost_map({ side = 999 }, { { 24, 7, wesnoth.current.side, "Vampire Bat" } })

helper.distance_between

  • helper.distance_between(x1, x2, y1, y2)

Returns the distance between two tiles given by their coordinates.

local d = distance_between(x1, y1, x2, y2)

helper.adjacent_tiles

  • helper.adjacent_tiles(x, y, [include_border])

Returns an iterator on the (at most six) tiles around a given location that are on the map. If the third argument is true, tiles on the map border are also visited.

-- remove all the units next to the (a,b) tile
for x, y in helper.adjacent_tiles(a, b) do
    wesnoth.put_unit(x, y)
end