[Freeciv-Dev] (PR#7282) connect as orders and PF extension

["Gregory Berkolaiko" <Gregory.Berkolaiko@xxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=7282 >

On Sun, 16 May 2004, Jason Short wrote:

> <URL: http://rt.freeciv.org/Ticket/Display.html?id=7282 >
> 
> Here's an updated version of the patch.  It may actually now be 
> complete.  Certainly it's now ready for testing and review.
> 
> Greg said I should set the MC (move cost) to 1 and put the construction 
> time into the EC (extra cost).  This would choose the path with the 
> shortest number of moves, which is ideal for roads (but not for rail, 
> and certainly not for irrigation).  The EC is used only as a tiebreaker 
> for equal-MC paths, so the shortest-construction-time would be the 
> secondary consideration.
> 
> The problem with this is that the construction time includes the move 
> time, and there is no way to reliably calculate the move time as part of 
> the EC since the extra cost is calculated only per-tile, not per-move. 
> (That is to say, the EC function is given only a single tile, not a 
> source and destination tile.)

By the way, you can pass the "standard move time" to the more complicated 
"constructions time" callback via parameter->data.  I.e. instead of
+  if (hover_state == HOVER_CONNECT) {
+    original_MC = parameter->get_MC;
+    parameter->get_MC = get_connect_MC;
+  }
you'd have 
paramater->data = parameter->get_MC;

Anyway, attached is a small patch extending PF to be able to accept extra 
cost which depends on a move rather than just target tile.  Maybe I am 
being overzealos in optimizing with pf_map->extras field, have a look.

Another (quite tricky) solution would be to
1. Turn off caching of extra-costs
2. Make get_connect_MC compute the extra cost (it has enough info with its 
parameters) and put it into parameter->data
3. Make get_connect_EC read the parameter->data

I have a feeling that Ross was advising doing something along these lines
and more:  having in PF just one callback which would be expected to set
all possible costs and extra costs.  This callback would then subcontract
parts of it's duties to other callbacks (so that one can get various
combinations), do it's own caching but all this would be done outwith main
PF.

This would be a fine alternative to trying to predict and hardwire every 
possible degree freedom into the main PF module.

G.

? test.gz
? ttt.gz
Index: common/aicore/path_finding.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/path_finding.c,v
retrieving revision 1.19
diff -u -r1.19 path_finding.c
--- common/aicore/path_finding.c        15 May 2004 18:15:46 -0000      1.19
+++ common/aicore/path_finding.c        18 May 2004 22:47:02 -0000
@@ -107,6 +107,7 @@
   struct pf_node *lattice;      /* Lattice of nodes */
   utiny_t *status;             /* Array of node statuses 
                                 * (enum pf_node_status really) */
+  bool extras;                  /* Are any extra-cost callbacks supplied? */
   struct pqueue *danger_queue; /* Dangerous positions go there */
   struct danger_node *d_lattice;       /* Lattice with danger stuff */
 };
@@ -307,11 +308,18 @@
       /* Total cost at xy1.  Cost may be negative; see get_turn(). */
       cost += node->cost;
 
-      /* Evaluate the extra cost of the destination,
-       * if it's relevant */
-      if (pf_map->params->get_EC) {
-       extra = node1->extra_tile;
-       extra += node->extra_cost;
+      /* Evaluate the extra cost if it's relevant */
+      if (pf_map->extras) {
+        extra = node->extra_cost;
+        if (pf_map->params->get_EC) {
+          /* Add the cached value */
+          extra += node1->extra_tile;
+        }
+        if (pf_map->params->get_moveEC) {
+          /* This one cannot be cached */
+          extra += pf_map->params->get_moveEC(pf_map->x, pf_map->y, dir, 
+                                              x1, y1, pf_map->params);
+        }
       }
 
       /* Update costs and add to queue, if we found a better route to xy1. */
@@ -410,6 +418,9 @@
     pf_map->d_lattice[pf_map->index].step = 0;
   }
 
+  pf_map->extras = (parameter->get_EC != NULL 
+                    || parameter->get_moveEC != NULL);
+
   return pf_map;
 }
 
Index: common/aicore/path_finding.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/path_finding.h,v
retrieving revision 1.7
diff -u -r1.7 path_finding.h
--- common/aicore/path_finding.h        27 Nov 2003 14:30:03 -0000      1.7
+++ common/aicore/path_finding.h        18 May 2004 22:47:02 -0000
@@ -324,6 +324,11 @@
   int (*get_EC) (int x, int y, enum known_type known,
                 struct pf_parameter * param);
 
+  /* Same as above but this extra cost may depend on both origin and target
+   * tiles. Can be NULL. */
+  int (*get_moveEC) (int from_x, int from_y, enum direction8 dir,
+                     int to_x, int to_y, struct pf_parameter * param);
+
   /* Although the rules governing ZoC are universal, the amount of
    * information available at server and client is different. To 
    * compensate for it, we might need to supply our own version 
Index: common/aicore/pf_tools.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/pf_tools.c,v
retrieving revision 1.13
diff -u -r1.13 pf_tools.c
--- common/aicore/pf_tools.c    29 Apr 2004 19:59:21 -0000      1.13
+++ common/aicore/pf_tools.c    18 May 2004 22:47:02 -0000
@@ -511,6 +511,7 @@
   parameter->turn_mode = TM_CAPPED;
   parameter->get_TB = NULL;
   parameter->get_EC = NULL;
+  parameter->get_moveEC = NULL;
   BV_CLR_ALL(parameter->unit_flags);
   parameter->omniscience = TRUE;