[freeciv-ai] Re: [Freeciv-Dev] Re: [Patch] [RFC] Path finding version 14

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

At 03:55 PM 02/09/13 +0000, Per I. Mathisen wrote:
>On Fri, 13 Sep 2002, Raimar Falke wrote:
>> > But if you wish to use this in your agent code there are no objections.
>>
>> > Hopefully it will never be used in the core AI routines where speed and
>> > flexibility are stronger requirements.
>>
>> Per thinks about using the path finding for the server AI.
>
>I don't think speed is a big issue.

I think warmap generation which is indicative of the AI usage needs for
pathfinding is the biggest single CPU hog at the present time, no?

> If we use the iterator to restrict the
>range of the search, we often need to generate smaller maps. We can also
>cache more aggressively with Raimar's new toy than the warmap does now.

Both of these are probably true, but they are also true for any 
pathfinding implementation, such as one that is much more modular and
hence faster/flexible in its approach. To date, I believe that the 
profiling does not favour Raimar's implementation, no?

>My biggest complaint about the path finding is and has been the API. I
>will submit a few change request to it when I get the time, mostly
>renaming stuff.

The API clearly does not separate the constant base code algorithm
from the variable user movecost and termination conditions providing
modular way to easily setup new sets of conditions on demand in user
supplied code. Its current selection should be pruned into a set of
individual modules which can be pre-selected in tailored subsets along
with any new elements future developers think are needed. One should
never have to include or do any work to skip over modular elements
that are not required, wich includes presetting any parameter blocks
of input data that is not going to be used, and certainly one needs
to preset things only once at initialization and pass minimal key data
elements on any single iterative step.

>In any case, I plan to make a wrapper set for the path finding code for
>the server AI where the use of ferries is included in some
>functions/macros. Here is a draft suggestion for such wrappers:

The wrapper concept sounds like a reasonable way to maintain some 
level of control over the cancerous spread of any implementation.

But if you look at your examples, there is a lot of trivial overlap
between these that is being obscured, and you are liable to end up 
with an insane proliferation of duplicate code if you are not careful.

>void ai_unit_do_goto(punit, x, y) {
>        moves a unit to (x, y) and finds a ferry if necessary (this is
>        both a replacement for current ai_military_gothere(), which is
>        unfortunately completely unsalvagable code, and for all
>        do_unit_goto() calls.
>}

I would like to see the pseudo code breakdown of the generalized goto
algorithm. This is mostly to see how many optional elements or branching
possibilities there might be. If it is close to a single straightforward
flow, then a single algorithm for all may be fine. 

The other aspect here is how useful caching is in generating the path(s)
or how long (in turns) cached data may be valid. There may be a need to
expose more of the innards here, or maintain a "goto-state" block that
allows for multi-turn updates and corrections to an initial path selection.

One should develop the scenarios/pseudo flow and think about such aspects
first before ending up with yet-another-unsalvagable-implementation, at
least in the eyes of the next programmer to try and use it.

>simple_city_path_iterator(punit, x, y, movecost) {
>        simple danger calculation iterator (we should also make a more
>        advanced version that looks at enemy ferries and looks where they
>        could beachhead, the current AI doesn't)
>} simple_city_path_iterator_end;
>
>simple_unit_path_iterator(punit, x, y, movecost) {
>        simple target selection iterator
>} simple_unit_path_iterator_end;
>
>unit_path_iterator(punit, x, y, movecost) {
>        unlike the iterator above, this will have to use higher-level AI
>        code to report wild ass goto guesstimates for ferries as well,
>        leaning towards worst-case, and calculating in stuff like ferry
>        time, how long it will take to acquire a ferry, etc. It should
>        give a rough idea of the time it will take, not precise time.
>} unit_path_iterator_end;

I like the iterator approach, especially if it comes with well-defined
ways to interact with the underlying state or augment the initial module
selection for added user conditions or movecost elements. 

Defined iterators should provide most common selections of things, but
easy tweaking to add that one extra special element rather than define a 
completely new iterator would help manage the proliferation issue. One
hopefully will be able to see the code flow in the iterator clearly in
context rather than key details being hidden in an inscrutable monster 
function call. This means defining certain parts of the iterator macro
as parts of the interface, i.e. a contract that this will not be changed
except as a major update and thus embedded user code can use it safely.

>If we wrap the use of path finding in the server AI behind a good and
>limited set of functions and macros, then we can easily change the path
>finding implementation behind them if someone produces a faster/better one
>in the future. Or if we decide - heavens forbid - to go back to warmaps.

This is partly true. It depends on how similar the implementation
interfaces are and how limited the restrictions or flexibility is on the 
exposed interface in a lowest common denominator sense.

A bad implementation can set the initial wrapper development back a long
ways, or result in even more ponderous and heavyweight solutions.

>In any case, I don't want the server-AI to use the API of the new path
>finding code directly. We need some mediating code.

I generally agree with the maxim that "all problems can be solved by an
extra level of indirection" :-)

We should see what Gregory comes up with as a first pass at taming 
Raimar's pathfinding monster before too much effort is expended. 

For my part, I've puttered with his initial dynamic warmap patches from 
last November, and don't think that was too far off the more modular
approach, but just needed a bit of framework and specific module examples
to make it more systemmatic. This works fine for iteratively growing the
path space including any test termination conditions. Once you have the
computed data or cached warmap, there are some processing tools that would 
be useful to extract additional information such as a single specified 
path sequence (i.e. backtrack and output a list of the path segments).

It would be nice if caching and reuse of the low-level generated data
in relatively lightweight post-processing steps became the general
approach. A city or possibly arbitrary (warcamp) location could hold
onto such cached data for a turn or more, meaning any units or types
of actions that were compatible with the existing data would not need
to recompute it. This is the sort of direction I hoped things might go,
i.e. clear separation of the low-level and output algorithms from the
well-defined but modular conditions used to construct the working data.
Once you have and can identify cached data, the final output should 
depend only on the data, and not how it was generated, thus you don't
necessarily have to generate it each time.

>Yours
>Per

Cheers,
RossW
=====