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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

Raimar, did you notice that the only thing you actually agreed to was the 
variable renaming?  

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

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

> > 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
b) put "assert(0)" instead of "continue" above

> > 5. About definition of ZOC: a tile occupied by your ally is not your 
> > ZOC?  Very weird.
> 
> I hope I haven't made an error during the transformation.

I hope so too.  I just copied your implementation.

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

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.

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

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

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

> > >  /*
> > >   * 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"?
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 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.

> > 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.
> 
> > Our positions becoming closer! ;)
> 
> Hopefully.

I think I am living up to your hopes :)

G.