path finder usage & functioning
Moderator: Forum Moderators
path finder usage & functioning
[I post here because it was with Lua that I stepped on these problems, but they are more general in fact.]
The way the path finder presently works is pretty weird in my view. I take it for granted that the one we access via
-1- How Information Fits Usage (or not)
There are two and a half variants of pathes:
* virtual path: ignoring units on the way
* actual path: taking into account all units
* engine path: ignoring ally units but taking into account enemies and ZoCs
I know about 2 kinds of usage, but there may be more:
* Actually moving a unit this turn on the way toward a goal (both human & software use): for this use, we need indeed an actual path for the first turn steps (see variants below); but we also absolutely need a purely virtual path for further turn moves (see details below)
* Vague and general route information for planning or evaluation/exploration (software only): for this use, IIUC, we also absolutely need a purely virtual path (ditto)
-2- How it May Be
I think that ideally, and also to avoid hard computation when unneeded there could be 2 path finders (or 2 lua funcs which under the hood may delegate some hard work to the same cpp func).
-3- More Useful Information
Also, for Lua usage (Lua action or micro AIs), we may occasionnally need some more information computed by the path finder but not provided back to us: in particular, I would need in some cases the list of steps for 1st turn move, and the list of stop tiles (at ends of turns) along the whole route. Obviously, in other cases, the total time (n turns) and the distance (n tiles) are pretty useful!
The way the path finder presently works is pretty weird in my view. I take it for granted that the one we access via
wesnoth.findpath
is the same as the one in the player interface; in any case, they show identical defaults (for my uses). If it is not the case, the reflexion remains valid --if it is valid at all. I see several issues, each requiring some explanation, so below I do my best to synthesize and give details in BBCode "openable" sections.-1- How Information Fits Usage (or not)
There are two and a half variants of pathes:
* virtual path: ignoring units on the way
* actual path: taking into account all units
* engine path: ignoring ally units but taking into account enemies and ZoCs
I know about 2 kinds of usage, but there may be more:
* Actually moving a unit this turn on the way toward a goal (both human & software use): for this use, we need indeed an actual path for the first turn steps (see variants below); but we also absolutely need a purely virtual path for further turn moves (see details below)
* Vague and general route information for planning or evaluation/exploration (software only): for this use, IIUC, we also absolutely need a purely virtual path (ditto)
usages & info
-2- How it May Be
I think that ideally, and also to avoid hard computation when unneeded there could be 2 path finders (or 2 lua funcs which under the hood may delegate some hard work to the same cpp func).
- route_toward_for_move: actual route for 1st turn, then virtual
- route_to_for_plan: pure virtual path
- route_toward: actual route for 1st turn, then purely virtual route
-3- More Useful Information
Also, for Lua usage (Lua action or micro AIs), we may occasionnally need some more information computed by the path finder but not provided back to us: in particular, I would need in some cases the list of steps for 1st turn move, and the list of stop tiles (at ends of turns) along the whole route. Obviously, in other cases, the total time (n turns) and the distance (n tiles) are pretty useful!
Get information computed by engine
- Celtic_Minstrel
- Developer
- Posts: 2290
- Joined: August 3rd, 2012, 11:26 pm
- Location: Canada
- Contact:
Re: path finder usage & functioning
I'm not entirely sure what you're getting at here, but I have two related comments.
First, I believe
Second, you might want to take a look at the
First, I believe
wesnoth.find_path
is little more than a vanilla A* algorithm, so you can provide a custom cost function that uses whatever criteria you want to determine how the pathing works; all three of your path types are probably replicable with a cost function. (I think they're also built-in, so you can avoid using a cost function and instead pass some flags in to use the engine's built-in cost function.)Second, you might want to take a look at the
[find_path]
WML tag, which I believe does most of what you're talking about in your third point.Re: path finder usage & functioning
Yes, thank you, I have seen that. But it seems the return value we get under Lua is not the same, or is it? (If it is, why does the doc say otherwise?)Celtic_Minstrel wrote: ↑November 8th, 2019, 2:41 am Second, you might want to take a look at the[find_path]
WML tag, which I believe does most of what you're talking about in your third point.
Re: path finder usage & functioning
[find_path]
is implemented in Lua (as are most WML tags), and it uses multiple calls to wesnoth.find_path
to generate the set of data returned to WML.- Celtic_Minstrel
- Developer
- Posts: 2290
- Joined: August 3rd, 2012, 11:26 pm
- Location: Canada
- Contact:
Re: path finder usage & functioning
To clarify, I meant to suggest that you should look at that tag's implementation in Lua, rather than the documentation for the tag.
Re: path finder usage & functioning
Oh, thank you! I wanted to do that, but in fact the pathfinder (as well as many other very useful funcs) seems to be in the coreCeltic_Minstrel wrote: ↑November 10th, 2019, 4:57 am To clarify, I meant to suggest that you should look at that tag's implementation in Lua, rather than the documentation for the tag.
wesnoth
module, implemented in cpp. I had a look at it for another reason and there, func only reuse element, data structures, and funcs implemented in cpp elsewhere. A hard and big job ahead just to know whether this or that...EDIT: The original cpp pathfinder module (see its header file here) holds several tools that could be very useful for lua coders (and even WML): for instance, search for the structs
emergency_path_calculator
and dummy_path_calculator
.Re: path finder usage & functioning
The tag's implementation is in
Not all WML tags have their own file, many are implemented in one of the large files in the parent directory.
data/lua/wml/find_path.lua
Not all WML tags have their own file, many are implemented in one of the large files in the parent directory.
- Celtic_Minstrel
- Developer
- Posts: 2290
- Joined: August 3rd, 2012, 11:26 pm
- Location: Canada
- Contact:
Re: path finder usage & functioning
The pathfinder itself (roughly equivalent to
EDIT: The two cost functions you mention look pretty trivial – you could probably just reimplement that logic as a Lua cost function if you wanted it.
wesnoth.find_path
) is implemented in C++, yes. The [find_path] tag is implemented in Lua.EDIT: The two cost functions you mention look pretty trivial – you could probably just reimplement that logic as a Lua cost function if you wanted it.
Re: path finder usage & functioning
Celtic_Minstrel wrote: ↑November 10th, 2019, 6:00 pm The pathfinder itself (roughly equivalent towesnoth.find_path
) is implemented in C++, yes. The [find_path] tag is implemented in Lua.
Thank you both very much!octalot wrote: The tag's implementation is in data/lua/wml/find_path.lua
Not all WML tags have their own file, many are implemented in one of the large files in the parent directory.
Actually I found
wesnoth.find_path
(the Lua func) in the meantime. Some mysterious complications I don't get yet (especially about the Lua-WML interface).You are right, actually I have done it before, for another usage, but just thought it would be useful for many. (I may propose a patch if/when I get better understanding of the Lua/WML interface.)Celtic_Minstrel wrote: ↑November 10th, 2019, 6:00 pm EDIT: The two cost functions you mention look pretty trivial – you could probably just reimplement that logic as a Lua cost function if you wanted it.
May I ask about the reasons of the standard behavior of find_path:
- Take into account ennemies for the path after the first turn move (==> totally wrong path if some direct way is presently blocked).
- Not take into account ally units even for the first turn move (=> we have to find the end-of-turn stop tile ourselves + in group move, funny phenomenon of units queueing).
- Celtic_Minstrel
- Developer
- Posts: 2290
- Joined: August 3rd, 2012, 11:26 pm
- Location: Canada
- Contact:
Re: path finder usage & functioning
The default cost function used by find_path (that is, the function used when you pass a table of options rather than a function) is the same cost function that's used by the game engine itself, as far as I know. To be more specific, it's the "shortest_path_calculator" (that's its name in the C++ code if you want to look it up).