[Freeciv-Dev] Re: [RFC] Path finding interface

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Wed, Apr 10, 2002 at 03:56:24AM -0400, Jason Short wrote:
> Raimar Falke wrote:
> > On Mon, Apr 08, 2002 at 10:09:03AM +0200, Raimar Falke wrote:
> > 
> >>On Mon, Apr 08, 2002 at 09:08:43AM +0200, Raimar Falke wrote:
> >>
> >>>Attached is my proposal to a unified path finding core. Although the
> >>>parameter list contains 14 elements I would call this interface
> >>>minimal and clean. It may be extended for performance reasons and if I
> >>>forgot something which can't be expressed with the callbacks.
> >>>
> >>>Also possible is the replacement of the static allocation of the
> >>>positions with a dynamic approach.
> >>
> >>It turns out that the interface wasn't minimal. Diff and version 2
> >>attached.
> > 
> > 
> > To allow city warmaps the interface was changed to allow the full
> > specification of all movement parameters. Diff and version 3 attached.
> 
> My understanding is that this path finding interface is to replace the 
> existing warmap code, correct?

Yes.

> "Path finding" isn't a very good name, but as you point out "warmap"
> isn't either.

The usual naming problem.

> As long as we're developing a new interface, we should consider the 
> underlying system itself.  The warmap system was a simple 
> implementation, but the authors learned something from it.  From 
> server/gotohand.c (above really_generate_warmap):
> 
> /***************************************************************
>    [....]
> This function is used by the AI in various cases when it is searching 
> for something to do with a unit. Maybe we could make a version that 
> processed the tiles in order after how many moves it took the unit to 
> get to them, and then gave them to the unit. This would achive 2 things:
> -The unit could stop the function the instant it found what it was 
> looking for, or when it had already found something reasonably close and 
> the distance to the tiles later being searched was reasoable big. In 
> both cases avoiding to build the full warmap.
> -The warmap would avoid examining a tile multiple times due to a series 
> of path with succesively smaller cost, since we would always have the 
> smallest possible cost the first time.
> This would be done by inserting the tiles in a list after their 
> move_cost as they were found.
> ****************************************************************/
> 
> A system like this makes fundamental sense to me, for several reasons:
> 
> - Under Dijikstra's algorithm, it should not increase the overhead of 
> the search at all.  For a generic example, what matter if we do:
> 
>    generate_warmap(...);
>    some_map_iterate(x, y) {
>      check_position_xy_for_something(x, y);
>    } some_map_iterate_end;
> 
> versus
> 
>    init_warqueue(...);
>    do {
>      pos = warqueue_pop();
>      check_position_xy_for_something(pos->x, pos->y);
>    while (position_is_relevant(pos));
> 
> ?
> 
> - An optimized AI may be able to short-circuit the logic, like the 
> comment says.  A good example is in find_nearest_friendly_port() in 
> aiunit.c, where the code can simply stop once it has found the nearest 
> friendly port [1].
> 
> 
> The only drawback I can see to such a system is that it makes automatic 
> caching of the warmap at the backend more difficult.  That, and it will 
> require substantial changes to the AI code, but you're going to get that 
> already.
> 
> With some thought, it might be possible to provide an interface that 
> allows both a warmap and a warqueue to be generated, and caches them 
> simultaneously.

Gregory has also noticed this and termed it iterators. I'm agree that
the current AI can benefit from it. Both Gregorys cost_map and my
path_finding support it:

  map = pf_get_map(parameter);
  do {
     struct pf_path path;

     pf_get_next_path_from_map(map, &path);

     if(!path.found_a_valid) {
       break;
     }

     check_position_xy_for_something(LAST_POSITION(&path));
  } while (position_is_relevant(path));

  pf_destroy_map(map);

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "USENET is *not* the non-clickable part of WWW!"