Exploit fast "multiple paths from same source" in distribution

Dijkstra's algorithm can find multiple paths from the same source.
This is much faster than starting from scratch for every path.

Make distribution path assembly work that way.  This speeds up runs of
distributions to the same center.  The next commit will reorder path
searches to maximize the length of these runs.  It also has benchmark
results.

Allocates four bytes per sector, actually uses only the first 4*n
bytes, where n is the number of distributing sectors.

diff --git a/src/lib/update/finish.c b/src/lib/update/finish.c
index c502ae6493eab6b981ce5951e42be624daaa9dd1..c8d85dbaee695da535f3820471b0ac6e0f3805ca 100644 (file)
--- a/src/lib/update/finish.c
+++ b/src/lib/update/finish.c
@@ -116,6 +116,7 @@ assemble_dist_paths(double *import_cost)
     struct sctstr *sp;
     struct sctstr *dist;
     int n;
+    coord dx = 1, dy = 0;      /* invalid */
 
     for (n = 0; NULL != (sp = getsectid(n)); n++) {
        import_cost[n] = -1;
@@ -126,9 +127,12 @@ assemble_dist_paths(double *import_cost)
            continue;
        if (sp->sct_own != dist->sct_own)
            continue;
-       import_cost[n] = path_find(sp->sct_dist_x, sp->sct_dist_y,
-                                  sp->sct_x, sp->sct_y,
-                                  dist->sct_own, MOB_MOVE);
+       if (sp->sct_dist_x != dx || sp->sct_dist_y != dy) {
+           dx = sp->sct_dist_x;
+           dy = sp->sct_dist_y;
+           path_find_from(dx, dy, dist->sct_own, MOB_MOVE);
+       }
+       import_cost[n] = path_find_to(sp->sct_x, sp->sct_y);
     }
     path_find_print_stats();
 }