FindPathExplanation - Revision history

Octalot: Update after merging the nearest_by PR

2019-09-11T09:41:59Z

Update after merging the nearest_by PR

← Older revision		Revision as of 09:41, 11 September 2019
Line 27:		Line 27:
	== Which village will '''[find_path]''' choose? ==		== 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.		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 an 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.		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]''':~~		{{DevFeature1.15\|2}} the option '''nearest_by''' chooses between "movement_cost" (default), "steps" and "hexes".
	'''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.

Octalot: Add the proposed nearest_by key

2019-07-27T09:30:04Z

Add the proposed nearest_by key

← Older revision		Revision as of 09:30, 27 July 2019
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.

Pentarctagon at 11:49, 22 July 2019

2019-07-22T11:49:19Z

← Older revision		Revision as of 11:49, 22 July 2019
Line 1:		Line 1:
	An illustrated example of the '''[[InternalActionsWML#.5Bfind_path.5D\|[find_path]]]''' WML tag's results.		An illustrated example of the '''[[InternalActionsWML#.5Bfind_path.5D\|[find_path]]]''' WML tag's results.

	~~https~~:~~//user~~-~~images.githubusercontent.com/101462/61628440-92323280-ac82-11e9-87b3~~-~~a6fc4e5442cc~~.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 9MP and needs 3MP for each shallow water tile, so it can reach every village without needing a multi-turn move.

Octalot: Illustration of [find_path]'s results, with image hotlinked from Github

2019-07-22T11:32:18Z

Illustration of [find_path]'s results, with image hotlinked from Github

New page

An illustrated example of the '''[[InternalActionsWML#.5Bfind_path.5D|[find_path]]]''' WML tag's results.

https://user-images.githubusercontent.com/101462/61628440-92323280-ac82-11e9-87b3-a6fc4e5442cc.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.

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
* "spur" is 5 hexes, 5 MP and 6 steps away
* "u_turn" is 2 hexes, 8 MP and 9 steps away

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.