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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Thu, Apr 11, 2002 at 06:23:11AM -0400, Ross W. Wetmore wrote:
> At 03:56 AM 02/04/10 -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.
> 
> Interfaces which try to enumerate all possible details rather than
> providing hooks to add future details are usually not extensible or
> fun to use after the first simple case or two.

Have you looked at the interface? Judging from your response you
didn't. I wouldn't on the contrary be surprised if you would say that
the interface too general. Generality can cost performance.

> Most junior programmers, and many senior ones never learn this lesson
> though except by being burnt many times.
> 
> >>>>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.
> 
> You really should look at GB's dynamic warmap code before going off in
> this direction.
> 
> >My understanding is that this path finding interface is to replace the 
> >existing warmap code, correct?  "Path finding" isn't a very good name, 
> >but as you point out "warmap" isn't either.
> >
> >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):
> 
> Agreed ... heartily.
> 
> The warmap object and its operations are very simple and well defined.
> 
> The trick is to add extensible cost functions at the defined interface
> points to deal with all the complexity ... and not to change the warmap
> interface in the process.
> 
> Try looking at the "Visitor Pattern" in any good pattern book to get
> an idea of how to separate the elements with clean interfaces.
> 
> >/***************************************************************
> >   [....]
> >****************************************************************/
> >
> >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));
> 
> Try something like this replacement for some code in the explorer
> management. 
> 
> What is missing is a few functions to preset the warmap with the 
> things that are done hardcoded in a few places like the top of 
> find_a_direction(). All the deatils are isolated in cost functions
> and so do not need to be passed through the interface. Adding
> new cost functions is a very extensible solution.
> 
>   /*
>    * PART 1: Look for huts
>    * Non-Barbarian Ground units ONLY.
>    */
> 
>   if (!is_barbarian(pplayer)
>       && is_ground_unit(punit)) {
>     /* Desired destination */
>     int x1, y1, found = -1;
>     enum goto_result gotores = GR_FAILED;
> 
>     /* CPU-expensive but worth it -- Syela */
>     /* generate_warmap(map_get_city(x, y), punit); */
> 
>     /* We're iterating outward so that with two tiles with the same movecost
>      * the nearest is used. */
> 
>     /* Note, dynamic warmaps do this intrinsically and efficiently. */
>     for (warmap_initialize(map_get_city(x, y), punit, bestcost);
>          warmap_next_location(&x1, &y1);
>          warmap_process_location(x1, y1)) {
>       /* Look for huts */
>       if (map_has_special(x1, y1, S_HUT)
>           && (!ai_handicap(pplayer, H_HUTS) || map_get_known(x1, y1, pplayer))
>           && tile_is_accessible(punit, x1, y1)
>           && ai_fuzzy(pplayer, TRUE)) {
>         found = warmap.cost[x1][y1];
>         break;
>       }
>     }
>    
> 
>     /* If the warmap found something, now go there. */
>     if( found != -1 ) {  
>       ...
>                                                       
> >- 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].
> 
> Or maybe this code from the ferryboat section ...
> 
>   /* do cool stuff here */
> 
>   /*
>    * Try to steal some business.
>    * Iterate outwards (warmap-wise) looking for waiting passengers
>    */
>   {
>     struct tile *ptile;
>     int x1, y1;
>     /* Collection array for equivalent moves. Size not critical, but a
>      * maxmoves square border gives a reasonable set to pick from. */
>     int b[8*maxmoves][2], bc = 0, bcost = 0;
>     /* Initialize to bogus desired destination */
>     b[0][0] = -1, b[0][1] = -1, best = 0;
> 
>     /*
>      * Stop if passengers(s) found *and* at start of a new move cost cycle
>      * This avoids non-random patterns based on warmap search order.
>      */
>     for (warmap_initialize(NULL, punit, best);
>          warmap_next_location(&x1, &y1)
>            && (bc <= 0 || bcost >= warmap.costmap[x1][y1]);
>          warmap_process_location(x1,y1)) {
> 
>       bcost = warmap.costmap[x1][y1];
>       ptile = map_get_tile(x1, y1);
> 
>       unit_list_iterate(ptile->units, aunit) {
>     /*
>      * Find units awaiting passage whose assigned boat is furthest off
>      * 1) aunit has a boat ticket
>      * 2) aunit is not currently sailing
>      * 3) aunit's boat is still alive
>      * 4) aunit's boat is farther off than punit
>      * 5) aunit's boat is at least as far off as previous aunit's boat
>      * TODO: does -1 == any boat???  This would have distance 99.
>      */
>     int newdist = 99;
>     struct unit *curboat;
> 
>     if (aunit->ai.ferryboat != 0
>       && ground_unit_transporter_capacity(x1, y1, pplayer) <= 0
>       && ai_fuzzy(pplayer, TRUE)
>       && (!(curboat = find_unit_by_id(aunit->ai.ferryboat))
>        || ((newdist = real_map_distance(x1, y1, curboat->x, curboat->y))
>                     > real_map_distance(x1, y1, punit->x, punit->y)))
>       && best <= newdist) {
> 
>       /* found a passenger */
>       freelog(LOG_DEBUG, "Found a pickup %d@(%d, %d)", aunit->id, x1, y1);
>       if (best < newdist)
>           bc = 0, best = newdist;
>       b[bc][0] = x1, b[bc][1] = y1, bc++;
> 
>       if( bc >= 8*maxmoves ) {
>         /* that's all, folks ... */
>         break;
>       }
>     }
>       } unit_list_iterate_end;
>     } /* end warmap iteration */
> 
>     /* Any passengers? */
>     if (bc > 0) {
>       /* pick one */
>       bc = myrand(bc);
>        ...
> 
> >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.
> 
> You've got it mostly right here. There is some 6 month old code
> kicking around in GB's early prototypes that does most of this.
> 
> It is trivial to pass a warmap struct as the local handle to a given
> function as the first argument. If one calls the variable "warmap" one
> don't even need to update the code that currently uses the static global.
> 
> It is trivial to dynamically allocate or use a pre-allocated
> warmap struct. One would fall back to the static global if one doesn't
> want this. There are tonnes of library string handling routines that
> serve as examples of how to manage local memory objects. 
> 
> A smart solution would be to provide a get_warmap() that returned a
> new warmap but from a cache. When done, code does a put_warmap()
> to push it back into the cache pool. You could then have a manageable
> set of warmaps, but not often would you want more than 2 or 3 at a
> time. Typically this is one for a base search and one for any GOTO's
> that may happen along the way that need to reprocess the possible
> paths to a location in finer detail.

> Note, that the above for loops could be reentered without reinitting
> the warmap to continue the search pattern. Thus if you wanted to go
> to more than one location, you could just continue accessing more 
> warmap_locations until you had what you need. 

This describes pf_get_path_from_map pretty good.

> If you quit at a move_cost increase point as done in one case, then
> you guarantee the warmap contains all equal cost moves possible.

> It is trivial to backtrack the warmap to iterate all of these and
> generate a waypoint vector for a programmed goto.

To get a path.

> >jason
> 
> But this should really pay attention to Gregory's move_cost interface 
> and some of the things he is saying, and not go off on a separate and
> probably much poorer tangent with finding a direction as has often 
> been done in the past :-).

Ross, Gregory: our two proposals aren't this much different. Both
provide an interator interface which allow a lazy construction of the
cost map. Both provide extra hooks to change the cost function. Both
haven't found the ideal solution to the Trireme problem. Thinks I
dislike about Gregory's proposal are city maps (yes the current code
uses this concept but it is flawed in general IMO) and is lacking the
ability to get the number of turns.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Transported to a surreal landscape, a young girl kills the first woman
  she meets and then teams up with three complete strangers to kill again."
    -- TV listing for the Wizard of Oz in the Marin Independent Journal