[Freeciv-Dev] find_the_shortest_path()

[Jason Dorje Short <jshort@xxxxxxxxxxxxx>]

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


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. 
AFAICT create_goto_map is used to create the goto vectors used by the
client (those shown when you manually do a "goto" with a unit), and it
looks like the preferred direction of travel (in case there are several
equally good ones) is pretty much arbitrary.


[1] http://www.freeciv.org/lxr/source/server/gotohand.c#L605
[2] http://www.freeciv.org/lxr/source/server/gotohand.c#L697
[3] http://www.freeciv.org/lxr/source/server/gotohand.c#L748
[4] http://www.freeciv.org/lxr/source/server/gotohand.c#L815
[5] http://www.freeciv.org/lxr/source/server/gotohand.c#L857
[6] http://www.freeciv.org/lxr/source/client/goto.c#L305


jason