[Freeciv-Dev] Re: find_the_shortest_path()

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Tue, Sep 18, 2001 at 02:41:55AM -0400, Jason Dorje Short wrote:
> I have several comments/questions on find_the_shortest_path() in
> server/gotohand.c.
> 
> 
> A comment [1] says:
> 
> /*
> To avoid RR loops (which may cause find_a_direction() to move a unit in
> cute little cycles forever and ever...), when we have more than one path
> to a tile and the second one is via RR (move_cost 0), we do NOT mark the
> extra path.
> */
> 
> However, Dijkstra's algorithm doesn't have this problem since any time
> the point is encountered a second time and the movement cost is no less
> it is not considered a second time.

You may have two paths to a certain position. These two paths have the
same move costs. The first path has 3 rail-road steps and the second
has 6544 rail road steps. You find the second path before the first.

> Later on [2] we have:
> 
>       if (warmap.cost[x1][y1] <= warmap.cost[x][y])
>         continue; /* No need for all the calculations. Note that this also
> excludes
>                      RR loops, ie you can't create a cycle with the same 
> move_cost
> */
> 
> which makes the first comment wrong (or at least misleading).
> 
> 
> Second, there is a lot of reptition in the function [3, 4 5]:
> 
>       /* Add the route to our warmap if it is worth keeping */
>       total_cost = move_cost + warmap.cost[x][y];
>       if (total_cost < maxcost) {
>           if (warmap.cost[x1][y1] > total_cost) {
>             warmap.cost[x1][y1] = total_cost;
>             add_to_mapqueue(total_cost, x1, y1);
>             local_vector[x1][y1] = 1 << DIR_REVERSE(dir);
>           freelog(LOG_DEBUG,
>                   "Candidate: %s from (%d, %d) to (%d, %d), cost %d",
>                   dir_get_name(dir), x, y, x1, y1, total_cost);
>           } else if (warmap.cost[x1][y1] == total_cost) {
>             local_vector[x1][y1] |= 1 << DIR_REVERSE(dir);
>           freelog(LOG_DEBUG,
>                   "Co-Candidate: %s from (%d, %d) to (%d, %d), cost %d",
>                   dir_get_name(dir), x, y, x1, y1, total_cost);
>           }
>         }
> 
>       /* Add the route to our warmap if it is worth keeping */
>       if (total_cost < maxcost) {
>         if (warmap.seacost[x1][y1] > total_cost) {
>           warmap.seacost[x1][y1] = total_cost;
>           add_to_mapqueue(total_cost, x1, y1);
>           local_vector[x1][y1] = 1 << DIR_REVERSE(dir);
>           freelog(LOG_DEBUG,
>                   "Candidate: %s from (%d, %d) to (%d, %d), cost %d",
>                   dir_get_name(dir), x, y, x1, y1, total_cost);
>         } else if (warmap.seacost[x1][y1] == total_cost) {
>           local_vector[x1][y1] |= 1 << DIR_REVERSE(dir);
>           freelog(LOG_DEBUG,
>                   "Co-Candidate: %s from (%d, %d) to (%d, %d), cost %d",
>                   dir_get_name(dir), x, y, x1, y1, total_cost);
>         }
>       }
> 
>       /* Add the route to our warmap if it is worth keeping */
>       total_cost = move_cost + warmap.cost[x][y];
>       if (total_cost < maxcost) {
>         if (warmap.cost[x1][y1] > total_cost) {
>           warmap.cost[x1][y1] = total_cost;
>           add_to_mapqueue(total_cost, x1, y1);
>           local_vector[x1][y1] = 1 << DIR_REVERSE(dir);
>           freelog(LOG_DEBUG,
>                   "Candidate: %s from (%d, %d) to (%d, %d), cost %d",
>                   dir_get_name(dir), x, y, x1, y1, total_cost);
>         } else if (warmap.cost[x1][y1] == total_cost) {
>           local_vector[x1][y1] |= 1 << DIR_REVERSE(dir);
>           freelog(LOG_DEBUG,
>                   "Co-Candidate: %s from (%d, %d) to (%d, %d), cost %d",
>                   dir_get_name(dir), x, y, x1, y1, total_cost);
>         }
>       }
> 
> These three code blocks are nearly identical, and could easily be
> replaced by a function add_route_to_warmap() or some such.

Feel free to do so.

> Finally, how exactly does find_the_shortest_path() differ from
> create_goto_map() in client/goto.c [6]?  Comments there indicate some
> differences, but nothing that is actually worth duplicating most of the
> code for.  A lot of the server's code is duplicated by the client, and
> there are no comments (here, at least) on why this is being done.

AFAIK one of the differences are different map access methods. Compare
"if (!pplayer->ai.control && !map_get_known(x1, y1, pplayer)) { " to
"if (pdesttile->terrain == T_UNKNOWN) {".

And yes it is a huge code duplication. IMHO also the interface isn't
the best one (looking at client/goto.h I have no clue how to use
it). If would be happy if somebody can bring this to an interface
like:

--------------------------------------
/*
 * Maximal number of steps in a path.
 */
#define MAX_PATH_LENGTH 100

struct ga_path {
    /*
     * Is this path a valid. Is set to 0 if there was no path found.
     */
    short int found_a_valid;
    /*
     * Number of positions used in the array "positions".
     */
  short int positions_used;

  struct ga_position {
      /*
       * x, y, turn and remaining_move_points describe a position in
       * place and time.
       */
    short int x, y, turn, remaining_move_points;
    short int direction_for_next_position;
  } positions[MAX_PATH_LENGTH + 1];
};

/*
 * Opaque type.
 */
typedef struct ga_map *ga_map_t;

/*
 * Returns a map which can be used to query for paths. The origin is
 * the current position of the unit.
 */
ga_map_t ga_get_map(int unit_id);

/*
 * Tries to find a path in the given map to the given destination
 * position. The path will be written in the given struct ga_path.
 * Caller should test path->found_a_valid. ga_get_path_from_map will
 * not change anything.
 */
void ga_get_path_from_map(ga_map_t map, int dest_x, int dest_y,
                          struct ga_path *path);

/*
 * After usage the map should be destroyed.
 */
void ga_destroy_map(ga_map_t map);

/*
 * ga_get_path is a one shot version. It combines ga_get_map,
 * ga_get_path_from_map and ga_destroy_map.
 */
void ga_get_path(int unit_id, int dest_x,int dest_y,struct ga_path *path);
--------------------------------------

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  The trick is to keep breathing.