path finder usage & functioning

Discussion of Lua and LuaWML support, development, and ideas.

Moderators: Forum Moderators, Developers

Post Reply
denispir
Posts: 184
Joined: March 14th, 2013, 12:26 am

path finder usage & functioning

Post by denispir » November 5th, 2019, 10:19 am

[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 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
In the user interface, we occasionnaly see funny consequences of the presuppositions on which the engine path finder is based.

For instance, when moving a whole troop along a long way, we often have to adjust each turn unit stop positions individually, aside the path. The cause is that it does not compute an actual (good) path for this turn: so that each unit stops behind the previous one instead of passing aside if it has MPs for that --even on plain open ground! This is a little worse in a software usage because we won't adjust, so that all that looks quite silly in the UI...

This is far worse around the end of the route, where in a typical case 1 unit stands on the goal tile, and most or even all others may well queue one after the other on the computed path ;-). I'm am not just thinking in thin air: this is truely and exactly what happened in my code, at first usage of find_path (micro AI), and recently again at second usage (Lua action tag). However, this is a real, but minor issue, (far) less than ideal, and solvable in principle (but pretty hard IIUC: the solution may involve reinventing path-finding! although just for 1 turn move).

However, if I am right there is another issue, a far more serious one: because the path finder takes enemies into account, it gives us a wrong, and useless, path for further turn moves: just because those enemy units may move or die or even flee... while others may come and stand on the way in the meantime. Initially, I thought this means we get a path with wrong turn-arounds and sideways, albeit on a globally correct trajectory: just useless over-precision and over-computation.

But in fact it may well provide us with a totally wrong route. Imagine you play with trolls, and an enemy dwarf stands on a single-hex pass between 2 caves (think UtBS big battle), acting like a cork: the path finder may return nil or find another route, which may well be "infinitely" long... Human players just ignore it and just use their corkscrewer, namely their troop's firepower ;-). However, if we aren't aware of that, our code we control troops in a totally crazy manner (!).
And note that this is true for both use cases evoked above:
  1. To get info, explore, evaluate options.
  2. To actually move a unit or a group along a path toward a goal.
To sum up: A non-virtual path after the first turn is useless, wrong, and even dangerous for software. A non-actual path for 1st turn is problematic, since we are left with computing it ourselves.

-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).
  1. route_toward_for_move: actual route for 1st turn, then virtual
  2. route_to_for_plan: pure virtual path
However, a middle way is possible: In fact, it is not problematic if, for planning and such, we get an actual route for the first turn. Actually, it may often be better, since whenever we actually move unit(s), we already have the first turn move: no 2nd computation needed. Thus, practically instead of ideally, if I reason well the best solution may be a single path finder:
  1. 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
If I reason correctly, all of the following information is necessarily computed by the engine:

Information provided:
  • total path
  • global cost (n MPs)
Certainly useful information in some cases:
  • time (n turns)
  • distance (n tiles)
  • first turn path (list of locs)
  • stop locations on the whole path (list of locs)
Additional information:
  • cost of every step (from tile to tile)
  • cost of all turn moves
One way to deal with that is the function (or functions) to have a series of optional options telling if each additional information is needed. Since the function must return a table anyway... The base information, namely the path itself, may then reside in the array-part (super practical), and all others in string keys, for instance:

Code: Select all

path_info = {{x1,y1}, {x2,y2}, {x3,y3}...,
    time = n_turns,
    distance = n_tiles,
    cost = n_MPs,
    first_turn_path = {{x1,y1}, {x2,y2}, {x3,y3}}
    ...
}
(There are indeed several ways to record the path itself.)

User avatar
Celtic_Minstrel
Developer
Posts: 1569
Joined: August 3rd, 2012, 11:26 pm
Location: Canada
Contact:

Re: path finder usage & functioning

Post by Celtic_Minstrel » November 8th, 2019, 2:41 am

I'm not entirely sure what you're getting at here, but I have two related comments.

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.
Author of The Black Cross of Aleron campaign and Default++ era.
Maintainer of Steelhive.

denispir
Posts: 184
Joined: March 14th, 2013, 12:26 am

Re: path finder usage & functioning

Post by denispir » November 9th, 2019, 9:14 am

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.
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?)

User avatar
octalot
Developer
Posts: 422
Joined: July 17th, 2010, 7:40 pm

Re: path finder usage & functioning

Post by octalot » November 9th, 2019, 4:36 pm

[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.

User avatar
Celtic_Minstrel
Developer
Posts: 1569
Joined: August 3rd, 2012, 11:26 pm
Location: Canada
Contact:

Re: path finder usage & functioning

Post by Celtic_Minstrel » 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.
Author of The Black Cross of Aleron campaign and Default++ era.
Maintainer of Steelhive.

denispir
Posts: 184
Joined: March 14th, 2013, 12:26 am

Re: path finder usage & functioning

Post by denispir » November 10th, 2019, 8:57 am

Celtic_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.
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 core 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.

User avatar
octalot
Developer
Posts: 422
Joined: July 17th, 2010, 7:40 pm

Re: path finder usage & functioning

Post by octalot » November 10th, 2019, 11:05 am

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.

User avatar
Celtic_Minstrel
Developer
Posts: 1569
Joined: August 3rd, 2012, 11:26 pm
Location: Canada
Contact:

Re: path finder usage & functioning

Post by Celtic_Minstrel » November 10th, 2019, 6:00 pm

The pathfinder itself (roughly equivalent to 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.
Author of The Black Cross of Aleron campaign and Default++ era.
Maintainer of Steelhive.

denispir
Posts: 184
Joined: March 14th, 2013, 12:26 am

Re: path finder usage & functioning

Post by denispir » November 10th, 2019, 9:39 pm

Celtic_Minstrel wrote:
November 10th, 2019, 6:00 pm
The pathfinder itself (roughly equivalent to wesnoth.find_path) is implemented in C++, yes. The [find_path] tag is implemented in Lua.
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.
Thank you both very much!
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).
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.
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.)

May I ask about the reasons of the standard behavior of find_path:
  1. Take into account ennemies for the path after the first turn move (==> totally wrong path if some direct way is presently blocked).
  2. 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).
And what would be your remedy for issue 1 (I have a remedy for issue 2 and intend to share it when properly tested).

User avatar
Celtic_Minstrel
Developer
Posts: 1569
Joined: August 3rd, 2012, 11:26 pm
Location: Canada
Contact:

Re: path finder usage & functioning

Post by Celtic_Minstrel » November 11th, 2019, 12:30 am

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).
Author of The Black Cross of Aleron campaign and Default++ era.
Maintainer of Steelhive.

Post Reply