[Freeciv-Dev] Re: [RFC] Path finding implementation.

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Sun, Jun 30, 2002 at 12:01:50AM +0100, Gregory Berkolaiko wrote:
> Raimar, did you notice that the only thing you actually agreed to was the 
> variable renaming?

No one said it would be easy.

> Well, only to be expected...  So I guess it's me who will have to be 
> flexible.
> 
> On Sat, 29 Jun 2002, Raimar Falke wrote:
> 
> > On Sat, Jun 29, 2002 at 09:23:01PM +0100, Gregory Berkolaiko wrote:
> > > Random comments:
> > > 
> > > 1. Why not use move_cost?
> > 
> > tile_move_cost_ai contains very weird code that isn't needed.
> 
> well fix it then

And break the existing gotohand.c? No.

> > > 2. I think railroad isn't really needed.  If you really want a 
> > > tie-breaker, use turns.
> > 
> > This was intended as a measure against loops. Not sure if it is
> > needed.
> 
> not needed.  see your own cmp_function.

I don't understand.

> > > 3. Inside the main loop, neighbour->type != IS_KNOWN should be an assert 
> > > really.  If it's broken, your Dijkstra is broken too.
> > 
> > main loop:
> > 
> >     neighbour = &pf_map->cells[x1][y1];
> >     if (neighbour->type == IS_UNINIT) {
> >       init_cell(pf_map, x1, y1);
> >     }
> > 
> >     if (neighbour->type == IS_KNOWN) {
> > ...
> >       continue;
> >     }
> > ...
> >     if (neighbour->type == IS_NONE) {
> >       copy_cell(neighbour, possible_neighbour);
> >       make_frontier(pf_map, neighbour);
> >     } else {
> >       assert(neighbour->type == IS_FRONTIER);
> > ...
> >     }
> > 
> > So every case is handled.
> 
> a) convert to switch

It was so in previous version. But you want to have the check for
IS_KNOWN very early in the code to avoid the other code.

> b) put "assert(0)" instead of "continue" above

No. Note that we are testing here neighbour and not the
current_cell. I agree that the latter should always be IS_KNOWN.

> > > Yes, interface. 
> > 
> > > The most important thing:  I really want the BMC as a call-back.  The 
> > > more 
> > > I think about it, the more I like it.  It gives you flexibility, cleans 
> > > up 
> > > the main loop, can be made aware of client vs server specifics etc.
> > 
> > This sounds like a problem. Please tell me why do you need this
> > flexibility. The last time we discussed this you brought the backward
> > idea up (which is needed for city centeric cases). So we added the
> > backwards flag. What else do you need?
> 
> I can come up with many things.  Submarines attacking ports, amphibious 
> units, estimating the time for a cavalry to go to a port and then being 
> ferried to New York...

Note that path_finding.c leaves attacking to the caller. It would add
another piece of complexity if we add this to path_finding.c

> 
> But actually, I am ready to agree to your implementation, provided there 
> is a possibility to put wrappers like 
>       pf_map_t pf_get_map_by_unit(struct unit)
> inside the path_finding.[ch]
> 
> No sane person should be forced to use parameter struct.

There is no arguing about this. I agree that only a few callers will
use the "raw" pf_get_map function.

However I'm not so sure if we are able to make a generic
pf_get_map_by_unit which only takes the unit. Because for example
there is no generic extra_cost1 callback which can be used by this
function.

The code in ai/ may provide such function. But then it would not be
placed in common/path_finding.

> > > Now, let's load the header file...
> > > Comments rated 1->5 reflecting strength of my feeling about them.
> > > 
> > > >  *  (which all have to be >=0)
> > > >  *  - cost of a path (COP) as returns by get_cop.
> > > >  *  - best path: a path which has the minimal COP. If two paths have
> > > >  *  equal COP the behavior is undefined.
> > > 
> > > (4) I don't like cops, but I can live with it, if you absolutely insist.
> > > I think 
> > >   time_to_dest * PF_IGNORE_COST + extra_cost_to_dest
> > > should be the universal cop.
> > 
> > PF_IGNORE_COST?
> > 
> > > > /*
> > > >  * The step is ignored completely if any extra cost or the sum EC is
> > > >  * larger than or equal to PF_IGNORE_COST.
> > > >  */
> > > > #define PF_IGNORE_COST  FC_INFINITY
> > > 
> > > (5) I'd like it to be finite.  You are using 100 in your_cop anyways.
> > 
> > It is finite ;) And 10^9 is a small number compared to other numbers
> > ;)
> 
> Very witty remark.  Now, can we have a number which is less than 10^9 
> please?

How large? And why?

> > The 100 is really just a number in this example. It doesn't have any
> > value. The factor will mostly influenced by a function similar to
> > access_danger.
> 
> what if somebody combines extra_cost which returns values up to 300 with a 
> COP function which uses the worthless number 100?

What should happen? The user has control over both and if the user
screws it up somehow the user has just screwed it up.

> > > >     int x, y;
> > > >     int turn, remaining_move_points;
> > > >     int BMC_of_next_step;
> > > > 
> > > >     /* Total BMC required to reach this position. */
> > > >     int total_BMC;
> > > 
> > > (3) Do you really need the total_BMC ?  Isn't turn + remaining_points 
> > > enough?  Causes some unnecessary problems with my implementation...
> > 
> > It was included to allow easy adoption of existing code. It is
> > basically the number calculated by gotohand.c. And it my be used to
> > get a rough turn estimation when you use TC_NONE.
> 
> Yep, sorry, I forgot that you always want 3 variables when you can do away 
> with one.  Let total_BMC stay, but it will only have meaning if TC_NONE is 
> used.  If something else is used, you can have turn + remaining_points. 
> Is that acceptable?

But total_BMC is computed in all cases. So in the TC_NONE case you
don't have a better metric. However in the non-TC_NONE you can still
access it.

> > > >  /*
> > > >   * Passed as last parameter to extra_cost1.
> > > >   */
> > > >  void *extra_cost1_data;
> > > >
> > > >  /*
> > > >   * Callback which can be used to provide extra costs depending on
> > > >   * the tile. Can be NULL. Parameters are x, y, known and
> > > >   * extra_cost1_data. It can be assumed that the implementation of
> > > >   * path_finding.h will cache this value.
> > > >   */
> > > >  int (*extra_cost1) (int, int, enum known_type, void *);
> > 
> > > (4) I would prefer the following form for the call-backs:
> > > 
> > > /* 
> > >  * Generic move cost function:
> > >  * (x,y) is the target tile, dir is the direction to the target tile.
> > >  */
> > > typedef int (COSTFN)(pf_map_t the_map, int x, int y, int dir);
> > > /* 
> > >  * Generic extra cost function:
> > >  * (x,y) is the target tile.
> > >  */
> > > typedef int (EXTRAFN)(pf_map_t the_map, int x, int y);
> > > 
> > > Do you plan any parameters to extra_cost that are not contained in pf_map?
> > 
> > The known state is cached and can be passed. A user can do not much
> > with the map argument. Note also that the callback can be called
> > everytime. And if you really want to use the map in some way you can
> > pass it via the user_data parameter.

> Do you want to trust extra_cost_fn to "a user"?

I don't understand. Do you ask if the function type should be public?

> Passing the map through parameter would be ugly, but I think I can live 
> with it.
> 
> > > >  void *extra_cost2_data;
> > > >
> > > >  /*
> > > >   * Callback which can be used to provide extra costs depending on
> > > >   * the path to this tile. Can be NULL. Parameters are path and
> > > >   * extra_cost2_data.
> > > >   */
> > > >  int (*extra_cost2) (const struct pf_path *, void *);
> > > 
> > > (2) A cost depending on the whole path ?!?!  That's quite exotic.  Please 
> > > justify.
> > 
> > I think (I don't have code yet) that this is needed if you want to
> > maximize the uncovered tiles/turn. Think auto explorer.
> 
> I think it's too much bother for very little gain, but let it be.
> 
> > > > /*
> > > >  * The last position of the next best path is written in the given
> > > >  * location. Returns FALSE if no more positions are available in this
> > > >  * map. Behavior is undefined after pf_get_path was called.
> > > >  */
> > > > bool pf_get_next_location(pf_map_t pf_map, pf_location_t * location);
> > > 
> > > (3) Scrap returning the location.  See below
> > > 
> > > > int pf_get_location_x(pf_map_t pf_map, const pf_location_t location);
> > > > int pf_get_location_y(pf_map_t pf_map, const pf_location_t location);
> > > 
> > > (3) I prefer my:
> > > int pf_get_current_x(const pf_map_t);
> > > int pf_get_current_y(const pf_map_t);
> > > int pf_get_current_cost(const pf_map_t);
> > > int pf_get_current_extra_cost(const pf_map_t);
> > 
> > This holds state in the object. I dislike this.
> 
> Oh, tell us about it!

> And your object doesn't hold the state?
> What's that on the top of yer heap then?

The heap isn't visible to the user.

> The second argument is gratuitous.  And if it's something that will take 
> clocks to compute, like pf_position, it's just plain wrong.
> 
> Yes, pf_get_turn(const pf_map_t) would be convenient too.

So we have to decide between an explicit object passed between
pf_get_next_location and the query functions. And whether there is one
query function (which can be merged with pf_get_next_location) or
multiple.

> > > Also should add:
> > > int pf_get(_extra)_cost(const pf_map, int x, int y);
> > 
> > And you may also want pf_get_turn(...) and one for remaining move
> > points. Instead of these what about
> > 
> >   bool pf_get_next_position(pf_map_t pf_map, struct pf_position * pos);
> > 
> > You may argue that the caller doesn't need all the information. But I
> > don't think that coping 7 values will be our biggest performance
> > problem.
> > 
> > However all this depends on what the caller really want.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "I do feel kind of sorry for Microsoft. Their attornies and marketing
  force must have tons of ulcers trying to figure out how to beat (not
  just co-exist with) a product that has no clearly defined (read
  suable) human owner, and that changes on an hourly basis like the
  sea changes the layout of the sand on a beach. Severely tough to
  fight something like that."
    -- David D.W. Downey at linux-kernel