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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Sat, Sep 14, 2002 at 11:52:52AM -0400, Ross W. Wetmore wrote:
> 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?

This is correct. It is also correct that people can't say which
function set the global warmap at a given point in code.

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

The implication is true for flexible but not for fast IMHO. IMHO you
can't do the same work faster by just moving the code around. Caching
stuff may help here.

> in its approach. 

> To date, I believe that the profiling does not favour Raimar's
> implementation, no?

There is no alternative implementation of the new interface yet. And
comparing it to the current warmap code is a bit unfair since the work
done isn't equal.

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

If I understand this right you want something like

struct pf_parameter {
  /*
   * Definition of the state of a virtual unit unit at the start.
   */
  int start_x, start_y;
  int moves_left_initially;
  int move_rate;

  void *get_BMC_data;

  /* 
   * x, y, get_BMC_data
   */
  int (*get_BMC) (int, int);

  /*
   * Determines how turns and moves_left are calculated.
   */
  enum turn_mode turn_mode;

  /*
   * Passed as last parameter to get_TB.
   */
  void *get_TB_data;

  /*
   * Callback which determines the behavior of a tile. If NULL
   * TB_NORMAL is assumed. Parameters are x, y, known and
   * get_TB_data. It can be assumed that the implementation of
   * path_finding.h will cache this value.
   */
  enum tile_behavior (*get_TB) (int, int, enum known_type, void *);

  /*
   * Passed as last parameter to get_ECOT.
   */
  void *get_ECOT_data;

  /*
   * Callback which can be used to provide extra costs depending on
   * the tile. Can be NULL. Parameters are x, y, known and
   * get_ECOT_data. It can be assumed that the implementation of
   * path_finding.h will cache this value.
   */
  int (*get_ECOT) (int, int, enum known_type, void *);

  /*
   * Passed as last parameter to is_position_safe.
   */
  void *is_position_dangerous_data;

  /*
   * If this callback is non-NULL and returns TRUE this position is
   * dangerous. The unit will never end a turn at a dangerous
   * position. Can be NULL. Parameter are x, y and
   * is_position_dangerous_data.
   */
   bool(*is_position_dangerous) (int, int, void *);

  /*
   * Passed as last parameter to get_cop.
   */
  void *get_COP_data;

  /*
   * If get_cop is NULL the default formula for COP is used. For
   * TC_NONE this is: COP = TEC + BMC. For non-TM_NONE it is COP = TEC +
   * (turn + 1) * move_rate - moves_left.
   * 
   * If get_cop is non-NULL the get_cop function will be called and
   * returns the COP. Parameter are the sum over all BMC of the path,
   * TEC, turns at the end of the path, moves_left at the end of the
   * path and get_cop_data.
   */
  int (*get_COP) (int, int, int, int, void *);
};

You get full control over the cost (get_BMC, get_ECOT) and the
termination condition (get_TB). You may want additionally to do the
moves_left and turn calculation by yourself. If the *_data stuff and
the comments are removed:

struct pf_parameter {
  int start_x, start_y;

  /* 
   * pointer to turn, pointer to moves_left, x, y, data
   */
  void (*update_turn_and_moves_left) (int *, int *, int, int);

  enum tile_behavior (*get_TB) (int, int, void *);

  int (*get_ECOT) (int, int, void *);

  bool(*is_position_dangerous) (int, int, void *);

  int (*get_COP) (int, int, int, int, void *);
};

This is quite minimal. Do you want this?

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

It would be nice if can reuse the data over multiple turn AND get
correct results. I don't see a solution which let the results stay
valid for a long time after creation but I see some possibilities to
cache immediate results. But this has nothing to do with the
interface.

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

This is about the server-AI interface and not about the core path
finding interface. So this isn't my problem.

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

He didn't found that much.

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

The new path finding interface and my implementation does this.

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

You have to generate the data if the start position changes. So if a
unit moves its map has to be recalculated. There are cases where the
inaccuracy doesn't matter and you can go on with the old one. And
there are cases where you need the exact map like triremes.

The map of a city "only" needs to be updated if:
 - terrain changes 
 - special changes
 - known type of a tile changes
 - enemy unit moves (ZOC)
 - some other events (like if the enemy has built Magellan)

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  reality.sys corrupt. Reboot Universe? (y,n,q)