[Freeciv-Dev] Re: find_the_shortest_path()

[Jason Dorje Short <jshort@xxxxxxxxxxxxx>]

Raimar Falke wrote:
> 
> On Tue, Sep 18, 2001 at 03:38:15AM -0400, Jason Dorje Short wrote:
> > Raimar Falke wrote:
> > >
> > > 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.
> >
> > That may be possible (although I assume the implementation of the
> > algorithm will prevent it by looking at the fewest-step path first; I
> > have not checked), but it does not make the comment any more correct.
> >
> > The comment claims that some checking for RR paths is done.
> 
> > In fact no such checking is done, as the later comment attests -
> > things just work out because Dijkstra's algorithm already takes care
> > of this problem.
> 
> In a mathematical and formal way there is no shortest path if there
> are edges in the graph which have no cost. IMHO a clean solution is to
> create a compound cost which is (normal_move_cost,
> rail_road_steps_taken). IMHO it wrong to trust this property of the
> Dijkstra algorithm.

There is no single shortest path, correct.  There are infinitely many
equally short shortest paths; the only reason to prefer one with fewer
steps is elegance.

Dijkstra's algorithm does assure you will never go in a loop; this is a
trustworthy property.  You are always guaranteed to find one position on
the loop before you find the loop itself.  However, if there is more
than one shortest path there is no guarantee that you will find the path
with the fewest steps.

Introducing a second measurement of path cost would solve this, but I
think "number of steps taken" is a much more valid measurement than
"number of railroad steps taken".  The implementation probably already
tends to do this simply because it uses a queue, so I don't think it
should be much of a problem.

> > As for the rest, I think a lot of cleanup could be done to this code -
> > but it will be difficult to guarantee the correctness of the new code
> > without a full understanding of the current code, which will take some
> > time.  A simple replacement of parts of the code with function calls
> > should be easy enough, though.
> 
> IMHO it can and should be rewritten from scratch. I see no problem of
> replacing the current implementation if a certain amount of people can
> assure that the replacement is correct in the mathematical way. But it
> is your time you invest in this.

Ugh.

Well, here's a start.

jason

Index: server/gotohand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/gotohand.c,v
retrieving revision 1.115
diff -u -r1.115 gotohand.c
--- server/gotohand.c   2001/09/15 15:31:26     1.115
+++ server/gotohand.c   2001/09/18 08:29:24
@@ -599,11 +599,6 @@
 The restrictions GOTO_MOVE_CARDINAL_ONLY and GOTO_MOVE_STRAIGHTEST are
 currently only used for settlers building irrigation and roads.
 
-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.
-
 At one point we used dir_ok to test if we were going in the right direction,
 but the cost of the dir_ok call was too high in itself, and the penalty
 sometimes lead to suboptimal paths chosen. The current implementation have
@@ -636,6 +631,9 @@
   int straight_dir = 0;        /* init to silence compiler warning */
   static unsigned char local_vector[MAP_MAX_WIDTH][MAP_MAX_HEIGHT];
   struct unit *pcargo;
+  /* Land/air units use warmap.cost while sea units use warmap.seacost.
+     Don't ask me why.  --JDS */
+  unsigned char **warmap_cost = (move_type == SEA_MOVING) ? warmap.seacost : 
warmap.cost;
 
   orig_x = punit->x;
   orig_y = punit->y;
@@ -751,23 +749,7 @@
        if (restriction == GOTO_MOVE_STRAIGHTEST && dir == straight_dir)
          move_cost /= SINGLE_MOVE;
 
-       /* 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);
-          }
-        }
        break;
 
       case SEA_MOVING:
@@ -821,22 +803,6 @@
                  punit->goto_dest_x, punit->goto_dest_y);
        }
 
-       /* 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);
-         }
-       }
        break;
 
       case AIR_MOVING:
@@ -864,23 +830,7 @@
        if ((restriction == GOTO_MOVE_STRAIGHTEST) && (dir == straight_dir))
          move_cost /= SINGLE_MOVE;
 
-       /* 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);
-         }
-       }
        break;
 
       default:
@@ -889,6 +839,23 @@
        abort();
        break;
       } /****** end switch ******/
+
+      /* Add the route to our warmap if it is worth keeping */
+      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);
+       }
+      }
 
       if (x1 == dest_x && y1 == dest_y && maxcost > total_cost) {
        freelog(LOG_DEBUG, "Found path, cost = %d", total_cost);