Difference between revisions of "FindPathExplanation"

From The Battle for Wesnoth Wiki
(Add the proposed nearest_by key)
Line 3: Line 3:
 
[[File:Find-path-demo.png]]
 
[[File:Find-path-demo.png]]
  
Imagine an Elvish Scout standing on the Player 1 start, this unit has 9MP and needs 3MP for each shallow water tile, so it can reach every village without needing a multi-turn move.
+
Imagine an Elvish Scout standing on the Player 1 start, this unit has 9 MP and needs 3 MP for each shallow water tile, so it can reach every village without needing a multi-turn move. Each of the villages might be considered to be the "nearest", because:
 
 
If '''[find_path]''' is used with a terrain filter that matches villages, each of these villages might be considered to be the "nearest":
 
  
 
* "lake" is 3 hexes, 7 MP and 4 steps away
 
* "lake" is 3 hexes, 7 MP and 4 steps away
 
* "spur" is 5 hexes, 5 MP and 6 steps away
 
* "spur" is 5 hexes, 5 MP and 6 steps away
 
* "u_turn" is 2 hexes, 8 MP and 9 steps away
 
* "u_turn" is 2 hexes, 8 MP and 9 steps away
 +
 +
The '''movement_cost''' is how many movement points the unit will need to get to that hex.
  
 
The '''hexes''' is best explained by the U-turn village - although it needs a lot of movement points, the village is only 2 hexes away from Player 1's start.
 
The '''hexes''' is best explained by the U-turn village - although it needs a lot of movement points, the village is only 2 hexes away from Player 1's start.
  
The '''steps''' is the length of the path.step array, which always includes the starting hex.
+
The '''steps''' is the length of the path.step array. This always includes the starting hex.
 +
 
 +
== Multi-turn moves ==
 +
 
 +
If the unit needs more than one turn to reach the destination, the cost includes any wasted MP at the end of a turn.
 +
 
 +
Consider an Elvish Archer instead of an Elvish Scout. This unit has 5 MP, so to get to the "lake" village it needs 2 turns, the first turn it moves on to first water hex but must end turn there, and the second turn is a water hex and a grass hex, for a total of 9 MP.
 +
 
 +
Consider the same Elvish Archer, but first we move 1 hex south, and then back to the starting point. '''[find_path]''' will now say that the path costs 7 MP, because the elf is already reduced to 0 MP before it ends the first turn.
 +
 
 +
The cost doesn't take account of capturing the village using up the unit's remaining movement.
 +
 
 +
== Which village will '''[find_path]''' choose? ==
 +
 
 +
If '''[find_path]''' is used with a Standard Location Filter that matches multiple hexes, it will return a path to one of them. For example, when using a SLF that matches villages there are 3 possible destination hexes, and each one is "nearest" by one type of measurement.
 +
 
 +
In 1.14, it's unclear which of the three will be chosen.
 +
 
 +
[[https://github.com/wesnoth/wesnoth/pull/4189 Proposal for 1.15]]: add an optional key to '''[find_path]''':
 +
'''nearest_by''': possible values "movement_cost" (default), "steps", "hexes". If the [destination] SLF matches multiple hexes, the one that would need the least movement points to reach may not be the one that's closest as measured by '''hexes''', or closest as measured by steps, from the starting point.

Revision as of 09:30, 27 July 2019

An illustrated example of the [find_path] WML tag's results.

Find-path-demo.png

Imagine an Elvish Scout standing on the Player 1 start, this unit has 9 MP and needs 3 MP for each shallow water tile, so it can reach every village without needing a multi-turn move. Each of the villages might be considered to be the "nearest", because:

  • "lake" is 3 hexes, 7 MP and 4 steps away
  • "spur" is 5 hexes, 5 MP and 6 steps away
  • "u_turn" is 2 hexes, 8 MP and 9 steps away

The movement_cost is how many movement points the unit will need to get to that hex.

The hexes is best explained by the U-turn village - although it needs a lot of movement points, the village is only 2 hexes away from Player 1's start.

The steps is the length of the path.step array. This always includes the starting hex.

Multi-turn moves

If the unit needs more than one turn to reach the destination, the cost includes any wasted MP at the end of a turn.

Consider an Elvish Archer instead of an Elvish Scout. This unit has 5 MP, so to get to the "lake" village it needs 2 turns, the first turn it moves on to first water hex but must end turn there, and the second turn is a water hex and a grass hex, for a total of 9 MP.

Consider the same Elvish Archer, but first we move 1 hex south, and then back to the starting point. [find_path] will now say that the path costs 7 MP, because the elf is already reduced to 0 MP before it ends the first turn.

The cost doesn't take account of capturing the village using up the unit's remaining movement.

Which village will [find_path] choose?

If [find_path] is used with a Standard Location Filter that matches multiple hexes, it will return a path to one of them. For example, when using a SLF that matches villages there are 3 possible destination hexes, and each one is "nearest" by one type of measurement.

In 1.14, it's unclear which of the three will be chosen.

[Proposal for 1.15]: add an optional key to [find_path]: nearest_by: possible values "movement_cost" (default), "steps", "hexes". If the [destination] SLF matches multiple hexes, the one that would need the least movement points to reach may not be the one that's closest as measured by hexes, or closest as measured by steps, from the starting point.