From: Markus Armbruster Date: Tue, 12 Apr 2011 20:07:10 +0000 (+0200) Subject: Merge branch 'pathfind' into pathfind-test X-Git-Url: http://git.pond.sub.org/?p=empserver;a=commitdiff_plain;h=d8bef8e80603678ebf0d13bf64680b1769c210ef Merge branch 'pathfind' into pathfind-test Conflicts: src/lib/as/as_cache.c src/lib/as/as_stats.c src/lib/common/path.c Modified: modified: include/path.h modified: include/prototypes.h modified: src/lib/update/finish.c --- d8bef8e80603678ebf0d13bf64680b1769c210ef diff --cc include/path.h index e0ce6fce2,eb0d950ec..d1f2d4e5c --- a/include/path.h +++ b/include/path.h @@@ -64,13 -67,21 +67,27 @@@ extern int diroff[DIR_MAP+1][2] extern char dirch[DIR_MAP+2]; extern char *routech[DIR_LAST+1]; +/* src/lib/common/bestpath.c */ +extern char *bestownedpath(char *, char *, int, int, int, int, int); + + /* src/lib/common/findpath.c */ + extern void path_find_from(coord, coord, natid, int); + extern double path_find_to(coord, coord); + extern double path_find(coord, coord, coord, coord, natid, int); + extern size_t path_find_route(char *, size_t, coord, coord, coord, coord); + #ifdef PATH_FIND_DEBUG + extern void path_find_visualize(coord, coord, coord, coord); + #endif + #ifdef PATH_FIND_STATS + extern void path_find_print_stats(void); + #else + #define path_find_print_stats() ((void)0) + #endif + /* src/lib/common/path.c */ +extern void bp_enable_cachepath(void); +extern void bp_disable_cachepath(void); +extern void bp_clear_cachepath(void); extern char *BestDistPath(char *, struct sctstr *, struct sctstr *, double *); extern char *BestLandPath(char *, struct sctstr *, struct sctstr *, diff --cc src/lib/common/path.c index 10e1eb0ab,ecd91c304..e901d4850 --- a/src/lib/common/path.c +++ b/src/lib/common/path.c @@@ -31,369 -31,84 +31,456 @@@ * Dave Pare, 1991 * Thomas Ruschak, 1993 * Steve McClure, 1997 + * Markus Armbruster, 2011 */ +/* + * Define AS_STATS for A* statistics on stderr. + * + * Define AS_NO_PATH_CACHE to disable the path cache. The path cache + * saves a lot of work, but uses lots of memory. It should be a + * significant net win, unless you run out of memory. + * + * Define AS_NO_NEIGHBOR_CACHE to disable the neighbor cache. The + * neighbor cache trades a modest amount of memory to save a bit of + * work. In its current form, it doesn't really make a difference. + */ + #include - #include + #include +#include "../as/as.h" #include "file.h" - #include "misc.h" #include "optlist.h" #include "path.h" +#include "prototypes.h" #include "sect.h" #include "xy.h" ++#ifdef USE_PATH_FIND ++void ++bp_enable_cachepath(void) ++{ ++} ++ ++void ++bp_disable_cachepath(void) ++{ ++} ++ ++void ++bp_clear_cachepath(void) ++{ ++} ++ + char * + BestLandPath(char *path, + struct sctstr *from, + struct sctstr *to, double *cost, int mob_type) + { + double c; + size_t len; + + *cost = 0.0; + *path = 0; + + /* + * Note: passing from->sct_own for actor is funny, but works: its + * only effect is to confine the search to that nation's land. It + * doesn't affect mobility costs. The real actor is different for + * marching in allied land, and passing it would break path + * finding there. + */ + c = path_find(from->sct_x, from->sct_y, to->sct_x, to->sct_y, + from->sct_own, mob_type); + if (c < 0) + return NULL; + len = path_find_route(path, 1024, + from->sct_x, from->sct_y, + to->sct_x, to->sct_y); + if (len + 1 >= 1024) + return NULL; + strcpy(path + len, "h"); + *cost = c; + return path; + } + + char * + BestDistPath(char *path, + struct sctstr *from, + struct sctstr *to, double *cost) + { + return BestLandPath(path, from, to, cost, MOB_MOVE); + } + + char * + BestShipPath(char *path, int fx, int fy, int tx, int ty, int owner) + { + size_t len; + + if (path_find(fx, fy, tx, ty, owner, MOB_SAIL) < 0) + return NULL; + len = path_find_route(path, 100, fx, fy, tx, ty); + if (len >= 100) + return NULL; + if (len == 0) + strcpy(path, "h"); + return path; + } + + char * + BestAirPath(char *path, int fx, int fy, int tx, int ty) + { + size_t len; + + if (path_find(fx, fy, tx, ty, 0, MOB_FLY) < 0) + return NULL; + len = path_find_route(path, 100, fx, fy, tx, ty); + if (len >= 100) + return NULL; + if (len == 0) + strcpy(path, "h"); + return path; + } ++#else /* !USE_PATH_FIND */ +#define BP_ASHASHSIZE 128 /* A* queue hash table size */ +#define BP_NEIGHBORS 6 /* max number of neighbors */ + +struct bestp { + int bp_mobtype; + struct as_data *adp; +}; + +static int bp_path(struct as_path *pp, char *buf); +static int bp_neighbors(struct as_coord c, struct as_coord *cp, void *); +static double bp_lbcost(struct as_coord from, struct as_coord to, void *); +static double bp_realcost(struct as_coord from, struct as_coord to, void *); +static double bp_seccost(struct as_coord from, struct as_coord to, void *); +static int bp_coord_hash(struct as_coord c); + +/* We use this for caching neighbors. It never changes except + * at reboot time (maybe) so we never need to free it */ +static struct sctstr **neighsects; + +static struct bestp * +bp_init(void) +{ + struct bestp *bp; + + bp = malloc(sizeof(*bp)); + memset(bp, 0, sizeof(*bp)); + bp->adp = as_init(BP_NEIGHBORS, BP_ASHASHSIZE, bp_coord_hash, + bp_neighbors, bp_lbcost, bp_realcost, + bp_seccost, bp); + + if (bp->adp == NULL) + return NULL; + +#ifndef AS_NO_NEIGHBOR_CACHE + if (neighsects == NULL) + neighsects = calloc(WORLD_SZ() * 6, sizeof(struct sctstr *)); +#endif + + return bp; +} + +/* + * Find the best path from sector to to sector, and put the Empire movement + * string in path. Return 0 on success, -1 on error. + * FIXME unsafe by design: assumes path[] has space; buffer overrun + * when path gets long! + */ +static int +best_path(struct sctstr *from, struct sctstr *to, char *path, int mob_type) +{ + static struct bestp *mybestpath; + struct as_data *adp; + struct as_path *ap; + int res; + + if (!mybestpath) + mybestpath = bp_init(); + adp = mybestpath->adp; +#ifdef AS_NO_PATH_CACHE + ap = NULL; +#else + ap = as_find_cachepath(from->sct_x, from->sct_y, to->sct_x, to->sct_y); +#endif + if (ap == NULL) { + adp->from.x = from->sct_x; + adp->from.y = from->sct_y; + adp->to.x = to->sct_x; + adp->to.y = to->sct_y; + mybestpath->bp_mobtype = mob_type; + + res = as_search(adp); +#ifdef AS_STATS + as_stats(adp, stderr); +#ifndef AS_NO_NEIGHBOR_CACHE + fprintf(stderr, "neighbor cache %zu bytes\n", + WORLD_SZ() * 6 * sizeof(struct sctstr *)); +#endif +#endif + if (res < 0) + return -1; + ap = adp->path; + } + + if (bp_path(ap, path) < 0) + return -1; + return 0; +} + +/* + * Translate an A* path into an empire movement string. Return 0 on + * success, -1 on failure. + */ +static int +bp_path(struct as_path *pp, char *buf) +{ + struct as_path *np; + char *cp = buf; + int dx, dy; + int n; + + np = pp->next; + while (np) { + dx = np->c.x - pp->c.x; + /* deal with wraparound from non-neg coords */ + if (dx < -2) + dx += WORLD_X; + else if (dx > 2) + dx -= WORLD_X; + dy = np->c.y - pp->c.y; + if (dy < -1) + dy += WORLD_Y; + else if (dy > 1) + dy -= WORLD_Y; + for (n = 1; n <= 6; n++) + if (dx == diroff[n][0] && dy == diroff[n][1]) + break; + if (n > 6) + return -1; + + *cp++ = dirch[n]; + pp = np; + np = np->next; + } + *cp = '\0'; + return 0; +} + +/* + * Find coords neighboring this sector; return number of such + * coords, and coordinartes themselves in an array pointed + * to by *cpp. + * XXX need to check ownership, sector types, etc. + */ +static int +bp_neighbors(struct as_coord c, struct as_coord *cp, void *pp) +{ + struct sctstr *sectp = (void *)empfile[EF_SECTOR].cache; + struct bestp *bp = pp; + coord x, y; + coord nx, ny; + int n = 0, i; + struct sctstr *sp, *from, **ssp; + /* Six pointers, just in case our cache isn't there */ + struct sctstr *tsp[] = { NULL, NULL, NULL, NULL, NULL, NULL }; + int sx, sy, offset; + + x = c.x; + y = c.y; + sx = XNORM(x); + sy = YNORM(y); + offset = XYOFFSET(sx, sy); + from = §p[offset]; + + if (neighsects == NULL) + ssp = (struct sctstr **)&tsp[0]; + else + ssp = (struct sctstr **)&neighsects[offset * 6]; + for (i = 1; i <= 6; i++, ssp++) { + if (*ssp == NULL) { + /* We haven't cached this neighbor yet */ + nx = x + diroff[i][0]; + ny = y + diroff[i][1]; + sx = XNORM(nx); + sy = YNORM(ny); + offset = XYOFFSET(sx, sy); + sp = §p[offset]; + *ssp = sp; + } else { + sp = *ssp; + sx = sp->sct_x; + sy = sp->sct_y; + } + /* No need to calculate cost each time, just make sure we can + move through it. We calculate it later. */ + if (dchr[sp->sct_type].d_mob0 < 0) + continue; + if (bp->bp_mobtype == MOB_RAIL && !SCT_HAS_RAIL(sp)) + continue; + if (sp->sct_own != from->sct_own) + continue; + cp[n].x = sx; + cp[n].y = sy; + n++; + } + return n; +} + +/* + * Compute a lower-bound on the cost from "from" to "to". + */ +/*ARGSUSED*/ +static double +bp_lbcost(struct as_coord from, struct as_coord to, void *pp) +{ + struct sctstr *sectp = (void *)empfile[EF_SECTOR].cache; + struct bestp *bp = pp; + int x, y, sx, sy, offset; + + x = to.x; + y = to.y; + sx = XNORM(x); + sy = YNORM(y); + offset = XYOFFSET(sx, sy); + return sector_mcost(§p[offset], bp->bp_mobtype); +} + +/* + * Compute the real cost to move from "from" to "to". + */ +static double +bp_realcost(struct as_coord from, struct as_coord to, void *pp) +{ + return bp_lbcost(from, to, pp); +} + +/* + * Tie breaker secondary metric (only used when lower bound costs + * are equal). + */ +/*ARGSUSED*/ +static double +bp_seccost(struct as_coord from, struct as_coord to, void *pp) +{ + return mapdist((coord)from.x, (coord)from.y, + (coord)to.x, (coord)to.y); +} + +/* + * Hash a coordinate into an integer. + */ +static int +bp_coord_hash(struct as_coord c) +{ + return ((abs(c.x) + 1) << 3) ^ abs(c.y); +} + +void +bp_enable_cachepath(void) +{ +#ifndef AS_NO_PATH_CACHE + as_enable_cachepath(); +#endif +} + +void +bp_disable_cachepath(void) +{ +#ifndef AS_NO_PATH_CACHE + as_disable_cachepath(); +#endif +} + +void +bp_clear_cachepath(void) +{ +#ifndef AS_NO_PATH_CACHE + as_clear_cachepath(); +#endif +} + +double +pathcost(struct sctstr *start, char *path, int mob_type) +{ + struct sctstr *sectp = (void *)empfile[EF_SECTOR].cache; + unsigned i; + int o; + int cx, cy; + double cost = 0.0; + struct sctstr *sp; + int sx, sy, offset; + + cx = start->sct_x; + cy = start->sct_y; + + while (*path) { + if (*path == 'h') { + path++; + continue; + } + i = *path - 'a'; + if (CANT_HAPPEN(i >= sizeof(dirindex) / sizeof(*dirindex))) + break; + o = dirindex[i]; + if (CANT_HAPPEN(o < 0)) + break; + cx += diroff[o][0]; + cy += diroff[o][1]; + sx = XNORM(cx); + sy = YNORM(cy); + offset = XYOFFSET(sx, sy); + sp = §p[offset]; + cost += sector_mcost(sp, mob_type); + path++; + } + + return cost; +} + +char * +BestDistPath(char *path, + struct sctstr *from, + struct sctstr *to, double *cost) +{ + return BestLandPath(path, from, to, cost, MOB_MOVE); +} + +char * +BestLandPath(char *path, + struct sctstr *from, + struct sctstr *to, double *cost, int mob_type) +{ + int length; + + *path = 0; + *cost = 0.0; + if (best_path(from, to, path, mob_type) < 0) + return NULL; + *cost = pathcost(from, path, mob_type); + length = strlen(path); + path[length] = 'h'; + path[length + 1] = '\0'; + return path; +} + +char * +BestShipPath(char *path, int fx, int fy, int tx, int ty, int owner) +{ + char *map; + + map = ef_ptr(EF_BMAP, owner); + if (!map) + return NULL; + return bestownedpath(path, map, fx, fy, tx, ty, owner); +} + +char * +BestAirPath(char *path, int fx, int fy, int tx, int ty) +{ + return bestownedpath(path, NULL, fx, fy, tx, ty, -1); +} ++#endif /* !USE_PATH_FIND */ diff --cc src/lib/update/finish.c index b621db547,6ea7b7702..9da4a8873 --- a/src/lib/update/finish.c +++ b/src/lib/update/finish.c @@@ -122,30 -110,65 +122,90 @@@ finish_sects(int etu } ++#ifdef USE_PATH_FIND + static int + distcmp(const void *p, const void *q) + { + int a = *(int *)p; + int b = *(int *)q; + struct sctstr *sp = (void *)empfile[EF_SECTOR].cache; + int d; + + d = sp[b].sct_dist_y - sp[a].sct_dist_y; + if (d) + return d; + d = sp[b].sct_dist_x - sp[a].sct_dist_x; + if (d) + return d; + return b - a; + } ++#endif + static void assemble_dist_paths(double *import_cost) { struct sctstr *sp; struct sctstr *dist; int n; ++#ifdef USE_PATH_FIND + static int *job; + int uid, i; + coord dx = 1, dy = 0; /* invalid */ + + if (!job) + job = malloc(WORLD_SZ() * sizeof(*job)); + + n = 0; + for (uid = 0; NULL != (sp = getsectid(uid)); uid++) { + import_cost[uid] = -1; + if (sp->sct_dist_x == sp->sct_x && sp->sct_dist_y == sp->sct_y) + continue; + job[n++] = uid; + } + + #ifdef PATH_FIND_STATS + printf("dist path reuse %zu bytes, %d/%d used\n", + WORLD_SZ() * sizeof(*job), n, WORLD_SZ()); + #endif + + qsort(job, n, sizeof(*job), distcmp); + + for (i = 0; i < n; i++) { + uid = job[i]; + sp = getsectid(uid); + dist = getsectp(sp->sct_dist_x, sp->sct_dist_y); + if (CANT_HAPPEN(!dist)) + continue; + if (sp->sct_own != dist->sct_own) + continue; + 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[uid] = path_find_to(sp->sct_x, sp->sct_y); + } + path_find_print_stats(); ++#else /* !USE_PATH_FIND */ ++ char *path; ++ double d; + char buf[512]; + + for (n = 0; NULL != (sp = getsectid(n)); n++) { + import_cost[n] = -1; + if ((sp->sct_dist_x == sp->sct_x) && (sp->sct_dist_y == sp->sct_y)) + continue; + dist = getsectp(sp->sct_dist_x, sp->sct_dist_y); + if (CANT_HAPPEN(!dist)) + continue; + if (sp->sct_own != dist->sct_own) + continue; + /* Now, get the best distribution path over roads */ + /* Note we go from the dist center to the sector. This gives + us the import path for that sector. */ + path = BestDistPath(buf, dist, sp, &d); + if (path) + import_cost[n] = d; + } ++#endif /* !USE_PATH_FIND */ }