[Freeciv-Dev] Re: (PR#2370) Path finding

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Fri, Feb 21, 2003 at 04:24:28PM +0000, Gregory Berkolaiko wrote:
> Didn't do any code changes.  Only renaming, commenting and tidying things 
> up.
> 
> I think it's ready.  Please read and comment asap.

As usual some things have crept in which shouldn't have.

The diplomat code has nothing to do with the PF. It is _one_ user. It
should be separately committed.

> + Freeciv - Copyright (C) 2002 - The Freeciv Project

2003

> + *  - move cost (MC): move cost of a _single_ step.  Note that the BMC of a

Use of BMC.

> + *  FORMULAE:  
> + *  - calculating total_MC
> + *  in TM_NONE
> + *    total_MC = sum of MC
> + *  in TM_CAPPED
> + *    total_MC = sum of MIN(MC, move_rate)
> + *  in TM_*_TIME
> + *     total_MC = ((turn + 1) * move_rate - moves_left)

I don't know what "in TM" means here.

> +/* 
> + * Maximal MC. If exceeded, tile is randed unreachable.
> + */
> +#define PF_MAXCOST 2000

This wasn't there the last time. It should go.

> + * Specifies how total_MC, turn and moves_left are computed (for deatils

Spelling.

> +enum turn_mode {
> +  /* 
> +   * No turn numbers or moves_left are used at all. The fields "turn"
> +   * and "moves_left" will always be -1. 
> +   */
> +  TM_NONE,
> +
> +  /* 
> +   * Similar to TM_NONE. The MC, however, is capped at the move_rate.

Add The fields "turn" and "moves_left" will always be -1. 

> +   */
> +  TM_CAPPED,
> +
> +  /* 
> +   * Assumes that the unit is always lucky in the random rulings and
> +   * so yields the best travel time.
> +   */
> +  TM_BEST_TIME,
> +
> +  /* 
> +   * Assumes that the unit is never lucky in the random rulings and
> +   * so yields the worst travel time.
> +   */
> +  TM_WORST_TIME,
> +};
> +
> +/* 
> + * Full specification of a position and time to reach it.
> + */
> +struct pf_position {
> +  int x, y;                  /* Coordinates of the position */
> +  int turn, moves_left;              /* See definitions above */
> +  int MC_of_next_step;               /* MC of the next step */
> +
> +  int total_MC;                      /* Total MC to reach this point */
> +  int total_EC;                      /* Total EC to reach this point */
> +
> +  enum direction8 dir_to_next_pos;   /* Unsed only in struct_path */

> +  enum direction8 dir_to_here;       /* Where did we come from */

This wasn't there the last time. It introduces redundancy. But it can
stay.

> +/*
> + * Initial data for the path-finding.  Normally should use functions
> + * from pf_tools.[ch] to fill the parameter.
> + */
> +struct pf_parameter {
> +  int start_x, start_y;              /* Initial position */
> +  int moves_left_initially;
> +  int move_rate;             /* Move rate of the virtual unit */
> +
> +  struct player *owner;
> +
> +  bool zoc_used;             /* Do we care about zones of control? */
> +  bool omniscience;          /* Do we care if the tile is visible? */
> +
> +  enum turn_mode turn_mode;  /* See definitions. */
> +
> +  /* 
> +   * Callback to get MC of a move from (from_x, from_y) to

> +   * (to_x, to_y) and inthe direction dir.

Spelling.

> +   */
> +  int (*get_MC) (int from_x, int from_y, enum direction8 dir,
> +              int to_x, int to_y, void *);

We should also supply "known".

> +  void *get_MC_data;         /* Passed as last parameter to get_cost */

get_MC

> +  /*
> +   * Callback which determines the behavior of a tile. If NULL
> +   * TB_NORMAL is assumed. Parameters are x, y, known and
> +   * get_TB_data. It can be assumed that the implementation of
> +   * path_finding.h will cache this value.
> +   */
> +  enum tile_behavior (*get_TB) (int, int, enum known_type, void *);

> +  void *get_TB_data;         /* Passed as last parameter to get_cost */

get_TB.

> +  /*
> +   * Callback which can be used to provide extra costs depending on
> +   * the tile. Can be NULL. Parameters are x, y, known and
> +   * get_EC_data. It can be assumed that the implementation of
> +   * path_finding.h will cache this value.
> +   */
> +  int (*get_EC) (int, int, enum known_type, void *);

> +  void *get_EC_data;         /* Passed as last parameter to get_cost */

get_EC.

> +  /*
> +   * If this callback is non-NULL and returns TRUE this position is
> +   * dangerous. The unit will never end a turn at a dangerous
> +   * position. Can be NULL. Parameter are x, y and

> +   * is_position_dangerous_data.

is_pos_dangerous.

> +   */
> +   bool(*is_pos_dangerous) (int, int, void *);

> +  void *is_pos_dangerous_data;       /* Passed as last parameter to get_cost 
> */

is_pos_dangerous.

> +};
> +
> +/*
> + * The map itself.  Opaque type.
> + */
> +typedef struct pf_map *pf_map_t;
> +
> +/* ==================== Functions =================================== */
> +
> +/*
> + * Returns a map which can be used to query for paths or to iterate
> + * over all paths. Does not perform any computations itself, just sets
> + * everything up.
> + */
> +pf_map_t pf_get_map(const struct pf_parameter *const parameter);

> +/*
> + * Tries to find the best path in the given map to the given
> + * destination position. The path will be written in the given struct
> + * pf_path. The caller should test path->is_valid.
> + */
> +void pf_get_path(pf_map_t pf_map, int end_x, int end_y,
> +              struct pf_path *path);
> +
> +/* 
> + * Iterates the map until it reaches (x, y).  Then fills the info about
> + * it into pos.
> + * Returns FALSE if position is unreachable.  Contents of pos in this case
> + * is not defined.
> + */
> +bool pf_get_position(pf_map_t pf_map, int x, int y, struct pf_position *pos);

We should provide the same way to test for unreachable target. Either
add "is_valid" to position or change return type of pf_get_path to
bool. Since the first is ugly I'm for the second. ppath->is_valid will
then go.

Why did you remove get_known? It is required to handicap handling.

> +static int single_seamove(int x, int y, enum direction8 dir,
> +                       int x1, int y1, void *data)
> +{
> +  /* MOVE_COST_FOR_VALID_SEA_STEP means ships can move between */
> +  if (map_get_tile(x, y)->move_cost[dir]
> +      == MOVE_COST_FOR_VALID_SEA_STEP) {
> +    return SINGLE_MOVE;
> +  } else {
> +    return PF_MAXCOST;
> +  }
> +}

Now I see why you need PF_MAXCOST. This should be changed. get_MC
should look like this:

  bool (*get_MC) (int *dest_MC, int from_x, int from_y, enum direction8 dir,
                  int to_x, int to_y, void *);

> +  Must put owner into *data.

What about also giving the parameters to all callbacks?

> +  Alternatively,we can change the flow to
> +  if (ptile->terrain == T_OCEAN) {
> +    move_cost = PF_MAXCOST;
> +  } else if (terrain1 == T_OCEAN) {
> +    move_cost = SINGLE_MOVE;
> +  } else {
> +    move_cost = ptile->move_cost[dir];
> +  }
> +  which will achieve thesame without call-back.

Why didn't you done this?

> +/************************************************************ 
> +  Reversed LAND_MOVE cost function for a unit.

> +  Will be used. DO NOT REMOVE you pricks.

When will it be used?

> +/**********************************************************************

> +  Switch on one tile overlapping into the sea 

False since it also handles SEA_MOVING.

> diff -Nur -X freeciv/diff_ignore freeciv/common/aicore/pf_tools.h 
> freeciv_st/common/aicore/pf_tools.h
> --- freeciv/common/aicore/pf_tools.h  Thu Jan  1 01:00:00 1970
> +++ freeciv_st/common/aicore/pf_tools.h       Fri Feb 21 16:17:09 2003
> @@ -0,0 +1,53 @@
> +/********************************************************************** 
> + Freeciv - Copyright (C) 2002 - The Freeciv Project
> +   This program is free software; you can redistribute it and/or modify
> +   it under the terms of the GNU General Public License as published by
> +   the Free Software Foundation; either version 2, or (at your option)
> +   any later version.
> +
> +   This program is distributed in the hope that it will be useful,
> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> +   GNU General Public License for more details.
> +***********************************************************************/
> +#ifndef FC__PF_TOOLS_H
> +#define FC__PF_TOOLS_H
> +
> +#include "path_finding.h"
> +
> +void pft_fill_default_parameter(struct pf_parameter *parameter);
> +void pft_fill_unit_parameter(struct pf_parameter *parameter,
> +                          struct unit *punit);
> +void pft_fill_unit_overlap_param(struct pf_parameter *parameter,
> +                              struct unit *punit);
> +
> +#define unit_path_iterator(punit, position) {       \
> +  pf_map_t UPI_map;                                 \
> +  struct pf_parameter UPI_parameter;                \
> +  pft_fill_default_parameter(&UPI_parameter);       \
> +  pft_fill_unit_parameter(&UPI_parameter, punit);   \
> +  UPI_map = pf_get_map(&UPI_parameter);             \
> +  while (pf_next(UPI_map)) {                        \
> +    struct pf_position position;                    \
> +    pf_next_get_position(UPI_map, &position);
> +
> +#define unit_path_iterator_end                      \
> +  }                                                 \
> +  pf_destroy_map(UPI_map);                          \
> +}
> +
> +#define unit_overlap_path_iterator(punit, position) {       \
> +  pf_map_t UPI_map;                                         \
> +  struct pf_parameter UPI_parameter;                        \
> +  pft_fill_unit_overlap_param(&UPI_parameter, punit);       \
> +  UPI_map = pf_get_map(&UPI_parameter);                     \
> +  while (pf_next(UPI_map)) {                                \
> +    struct pf_position position;                            \
> +    pf_next_get_position(UPI_map, &position);
> +
> +#define unit_overlap_path_iterator_end                      \
> +  }                                                         \
> +  pf_destroy_map(UPI_map);                                  \
> +}

Why do we need pf_next_{x,y,cost} now that the main AI user of the PF
uses pf_next_get_position?

I still think that the above two macros should be prefixed with "ai",
"plain", "simple", "basic" or similar since there are the most plain
use of PF. There is no EC handling in them. Either users of PF want
this.



-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "SIGDANGER - The System is likely to crash soon"