From bf97fa9c9c822cf007c13f2bc0f2ef8f4dd2d634 Mon Sep 17 00:00:00 2001 From: Markus Armbruster Date: Mon, 21 Feb 2011 22:22:54 +0100 Subject: [PATCH] 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. --- src/lib/update/finish.c | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) diff --git a/src/lib/update/finish.c b/src/lib/update/finish.c index c502ae649..c8d85dbae 100644 --- 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(); } -- 2.43.0