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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Sat, Jun 29, 2002 at 09:23:01PM +0100, Gregory Berkolaiko wrote:
> > Ok here is the version 11 with a sample implementation. Changes to the
> > interface:
> >  - remove enum turn_index
> >  - rename the user data arguments
> >  - make the arrays turn and remaining_move_points scalar values
> > 
> > Changes in the implementation: 
> >  - exchange the hash with a 2D array
> >  - exchange the list with a heap
> >  - cache tile pointer
> >  - add ptile->move_cost2
> 
> Random comments:
> 
> 1. Why not use move_cost?

tile_move_cost_ai contains very weird code that isn't needed.

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

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

> 4. Instead of rebuilding the heap, I just pile everything in.  To keep 
> integrity I have to store priorities in the heap as well.  I am not sure 
> what is faster.

The cost field _is_ the priority.

> 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 would like that we agree upon an interface and let the two
> > implementations run in parallel to catch the remaining bugs. Parallel
> > to this I would implement the famous is_position_dangerous if I get
> > the time. I expect that this will require some work to get right.
> 
> 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?

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

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.

> > struct pf_path {
> >   bool found_a_valid;
> 
> (1) "is_valid" is a better sounding name IMO

Ok.

> >   struct pf_position {
> >     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.

> >     enum direction8 direction_for_next_position;
> >   } positions[MAX_PATH_LENGTH + 1];
> > };
> 
> Now the most important bit,
> 
> > struct pf_parameter {
> >   int start_x, start_y;
> >   int moves_left_initially;
> >   struct player *owner;
> 
> (5+) Most of the below can go if we do BMC call-back
> 
> >   enum unit_move_type move_type;
> 
> die!
> 
> >   /* only F_IGZOC and F_IGTER are used currently */
> >   enum unit_flag_id flags;
> 
> die!
> 
> >   int move_rate;
> >   bool move_backward;
> 
> die!
> 
> >
> >   enum turn_mode turn_mode;
> >
> >   enum known_type (*get_known) (int, int, struct player *);
> >
> >   enum goto_move_restriction restriction;
> 
> die!
> 
> >  /*
> >   * 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.

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

> >   void *is_position_dangerous_data;
> >   bool(*is_position_dangerous) (int, int, enum known_type, void *);
> 
> not implemented -> no comment.  but passing the map instead of the last 
> two args is preferable.

See above.

> >  void *get_cop_data;
> >  int (*get_cop) (int, int, int, int, void *);
> >};
> 
> See above.
> 
> > /*
> >  * Called only once per executable start.
> >  */
> > void pf_init(void);
> 
> Very useful function.  But hard to implement ;)
> 
> > pf_map_t pf_get_map(const struct pf_parameter *const parameter);
> > void pf_get_path(pf_map_t pf_map, int end_x, int end_y,
> >              struct pf_path *path);
> > void pf_construct_path(pf_map_t pf_map, struct pf_path *path,
>                      const pf_location_t location);
> 
> Fine.
> 
> > /*
> >  * 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.

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

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Last year, out in California, at a PC users group, there was a demo of
  smart speech recognition software. Before the demonstrator could begin
  his demo, a voice called out from the audience: "Format c, return. Yes,
  return." Damned short demo, it was.