X-Git-Url: http://git.pond.sub.org/?p=empserver;a=blobdiff_plain;f=src%2Flib%2Fcommon%2Fpath.c;h=8e6be460efc4767b713e120b28870e1c1dab0495;hp=5cb2bc2183393ae7534a1a913acc51c5458a5bcc;hb=9b7adfbe;hpb=5f263a7753dc728809ff85c993af975f6c76e61e diff --git a/src/lib/common/path.c b/src/lib/common/path.c index 5cb2bc218..8e6be460e 100644 --- a/src/lib/common/path.c +++ b/src/lib/common/path.c @@ -62,39 +62,44 @@ /* XXX won't need sector hash when sect file is memory mapped */ -#define BP_SCTHASHSIZE 128 /* sector cache hash table size */ -#define BP_ASHASHSIZE 128 /* A* queue hash table size */ -#define BP_NEIGHBORS 6 /* max number of neighbors */ - -struct sctcache { - coord x, y; - struct sctstr *sp; - struct sctcache *next; +#define BP_SCTHASHSIZE 128 /* sector cache hash table size */ +#define BP_ASHASHSIZE 128 /* A* queue hash table size */ +#define BP_NEIGHBORS 6 /* max number of neighbors */ + +struct sctcache { + coord x, y; + struct sctstr *sp; + struct sctcache *next; }; struct bestp { - struct sctcache *sctcachetab[BP_SCTHASHSIZE]; - int sctcache_hits; - int sctcache_misses; - int bp_mobtype; - struct as_data *adp; + struct sctcache *sctcachetab[BP_SCTHASHSIZE]; + int sctcache_hits; + int sctcache_misses; + int bp_mobtype; + struct as_data *adp; }; #ifdef DO_EFF_MEM_CHECKING -static struct sctstr *bp_getsect(struct bestp *bp, coord x, coord y); -static struct sctstr *bp_sctcache_get(struct bestp *bp, coord x, coord y); -static void bp_sctcache_set(struct bestp *bp, coord x, coord y, struct sctstr *sp); -static void bp_sctcache_zap(struct bestp *bp); +static struct sctstr *bp_getsect(struct bestp *bp, coord x, coord y); +static struct sctstr *bp_sctcache_get(struct bestp *bp, coord x, coord y); +static void bp_sctcache_set(struct bestp *bp, coord x, coord y, + struct sctstr *sp); +static void bp_sctcache_zap(struct bestp *bp); #endif /* DO_EFF_MEM_CHECKING */ -static int bp_path(struct as_path *pp, s_char *buf); -static int bp_neighbors(struct as_coord c, struct as_coord *cp, s_char *pp); -static double bp_lbcost(struct as_coord from, struct as_coord to, s_char *pp); -static double bp_realcost(struct as_coord from, struct as_coord to, s_char *pp); -static double bp_seccost(struct as_coord from, struct as_coord to, s_char *pp); -static int bp_coord_hash(struct as_coord c); +static int bp_path(struct as_path *pp, s_char *buf); +static int bp_neighbors(struct as_coord c, struct as_coord *cp, + s_char *pp); +static double bp_lbcost(struct as_coord from, struct as_coord to, + s_char *pp); +static double bp_realcost(struct as_coord from, struct as_coord to, + s_char *pp); +static double bp_seccost(struct as_coord from, struct as_coord to, + s_char *pp); +static int bp_coord_hash(struct as_coord c); struct empfile *ep; @@ -105,24 +110,25 @@ struct sctstr **neighsects = (struct sctstr **)0; s_char * bp_init(void) { - struct bestp *bp; + struct bestp *bp; - ep = &empfile[EF_SECTOR]; + ep = &empfile[EF_SECTOR]; - bp = (struct bestp *) malloc(sizeof(*bp)); - bzero((s_char *)bp, sizeof(*bp)); - bp->adp = as_init(BP_NEIGHBORS, BP_ASHASHSIZE, bp_coord_hash, - bp_neighbors, bp_lbcost, bp_realcost, - bp_seccost, (s_char *)bp); + bp = (struct bestp *)malloc(sizeof(*bp)); + bzero((s_char *)bp, sizeof(*bp)); + bp->adp = as_init(BP_NEIGHBORS, BP_ASHASHSIZE, bp_coord_hash, + bp_neighbors, bp_lbcost, bp_realcost, + bp_seccost, (s_char *)bp); - if (bp->adp == NULL) - return NULL; + if (bp->adp == NULL) + return NULL; - if (neighsects == (struct sctstr **)0) - neighsects = (struct sctstr **)calloc(1, (sizeof(struct sctstr *) * - ((WORLD_X * WORLD_Y)/2)*6)); + if (neighsects == (struct sctstr **)0) + neighsects = (struct sctstr **)calloc(1, (sizeof(struct sctstr *) * + ((WORLD_X * WORLD_Y) / + 2) * 6)); - return (s_char *) bp; + return (s_char *)bp; } /* @@ -130,43 +136,44 @@ bp_init(void) * string in path. Return 0 on success, -1 on error. */ int -best_path(struct sctstr *from, struct sctstr *to, s_char *path, int mob_type) +best_path(struct sctstr *from, struct sctstr *to, s_char *path, + int mob_type) { - static struct bestp *mybestpath; - struct as_data *adp; - struct as_path *ap; + static struct bestp *mybestpath; + struct as_data *adp; + struct as_path *ap; - if (mybestpath == 0) - mybestpath = (struct bestp *)bp_init(); - adp = mybestpath->adp; + if (mybestpath == 0) + mybestpath = (struct bestp *)bp_init(); + adp = mybestpath->adp; #ifdef DO_EFF_MEM_CHECKING - bp_sctcache_zap(mybestpath); + bp_sctcache_zap(mybestpath); #endif - ap = as_find_cachepath(from->sct_x, from->sct_y, to->sct_x, to->sct_y); - 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; - - if (as_search(adp) < 0) - return -1; - ap = adp->path; - } - - if (bp_path(ap, path) < 0) - return -1; + ap = as_find_cachepath(from->sct_x, from->sct_y, to->sct_x, to->sct_y); + 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; + + if (as_search(adp) < 0) + return -1; + ap = adp->path; + } + + if (bp_path(ap, path) < 0) + return -1; #ifdef AS_STATS - as_stats(adp, stderr); + as_stats(adp, stderr); #endif /* AS_STATS */ #ifdef BP_STATS - fprintf(stderr, "best path %s\n", path); - fprintf(stderr, "cache hits/misses: %d/%d\n", - bp->sctcache_hits, bp->sctcache_misses); + fprintf(stderr, "best path %s\n", path); + fprintf(stderr, "cache hits/misses: %d/%d\n", + bp->sctcache_hits, bp->sctcache_misses); #endif /* BP_STATS */ - return 0; + return 0; } /* @@ -176,36 +183,36 @@ best_path(struct sctstr *from, struct sctstr *to, s_char *path, int mob_type) static int bp_path(struct as_path *pp, s_char *buf) { - struct as_path *np; - s_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; + struct as_path *np; + s_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; } /* @@ -218,71 +225,71 @@ static int bp_neighbors(struct as_coord c, struct as_coord *cp, s_char *pp) { #ifdef DO_EFF_MEM_CHECKING - struct bestp *bp = (struct bestp *) pp; + struct bestp *bp = (struct bestp *)pp; #endif /* DO_EFF_MEM_CHECKING */ - coord x, y; - coord nx, ny; - int n = 0, q; - struct sctstr *sp, *from, **ssp; - /* Six pointers, just in case our cache isn't there */ - struct sctstr *tsp[] = { 0, 0, 0, 0, 0, 0 }; - int sx, sy, offset; - - x = c.x; - y = c.y; + coord x, y; + coord nx, ny; + int n = 0, q; + struct sctstr *sp, *from, **ssp; + /* Six pointers, just in case our cache isn't there */ + struct sctstr *tsp[] = { 0, 0, 0, 0, 0, 0 }; + int sx, sy, offset; + + x = c.x; + y = c.y; #ifdef DO_EFF_MEM_CHECKING - if ((ep->flags & EFF_MEM) == 0) { - from = bp_getsect(bp, x, y); - } else { + if ((ep->flags & EFF_MEM) == 0) { + from = bp_getsect(bp, x, y); + } else { #endif /* DO_EFF_MEM_CHECKING */ - sx = XNORM(x); - sy = YNORM(y); - offset = (sy * WORLD_X + sx) / 2; - from = (struct sctstr *) (ep->cache + ep->size * offset); + sx = XNORM(x); + sy = YNORM(y); + offset = (sy * WORLD_X + sx) / 2; + from = (struct sctstr *)(ep->cache + ep->size * offset); #ifdef DO_EFF_MEM_CHECKING - } + } #endif /* DO_EFF_MEM_CHECKING */ - if (neighsects == (struct sctstr **)0) - ssp = (struct sctstr **)&tsp[0]; - else - ssp = (struct sctstr **)&neighsects[offset * 6]; - for (q = 1; q <= 6; q++, ssp++) { - if (*ssp == (struct sctstr *)0) { - /* We haven't cached this neighbor yet */ - nx = x + diroff[q][0]; - ny = y + diroff[q][1]; - sx = XNORM(nx); - sy = YNORM(ny); + if (neighsects == (struct sctstr **)0) + ssp = (struct sctstr **)&tsp[0]; + else + ssp = (struct sctstr **)&neighsects[offset * 6]; + for (q = 1; q <= 6; q++, ssp++) { + if (*ssp == (struct sctstr *)0) { + /* We haven't cached this neighbor yet */ + nx = x + diroff[q][0]; + ny = y + diroff[q][1]; + sx = XNORM(nx); + sy = YNORM(ny); #ifdef DO_EFF_MEM_CHECKING - if ((ep->flags & EFF_MEM) == 0) { - sp = bp_getsect(bp, nx, ny); - } else { + if ((ep->flags & EFF_MEM) == 0) { + sp = bp_getsect(bp, nx, ny); + } else { #endif /* DO_EFF_MEM_CHECKING */ - offset = (sy * WORLD_X + sx) / 2; - sp = (struct sctstr *) (ep->cache + ep->size * offset); - /* We can only save in our neighbor cache if the - sector file is in memory */ - *ssp = sp; + offset = (sy * WORLD_X + sx) / 2; + sp = (struct sctstr *)(ep->cache + ep->size * offset); + /* We can only save in our neighbor cache if the + sector file is in memory */ + *ssp = sp; #ifdef DO_EFF_MEM_CHECKING - } -#endif /* DO_EFF_MEM_CHECKING */ - } else { - sp = *ssp; - sx = XNORM(sp->sct_x); - sy = YNORM(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_mcst == 0) - continue; - if (sp->sct_own != from->sct_own) - continue; - cp[n].x = sx; - cp[n].y = sy; - n++; +#endif /* DO_EFF_MEM_CHECKING */ + } else { + sp = *ssp; + sx = XNORM(sp->sct_x); + sy = YNORM(sp->sct_y); } - return (n); + /* 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_mcst == 0) + continue; + if (sp->sct_own != from->sct_own) + continue; + cp[n].x = sx; + cp[n].y = sy; + n++; + } + return (n); } /* @@ -292,27 +299,27 @@ bp_neighbors(struct as_coord c, struct as_coord *cp, s_char *pp) static double bp_lbcost(struct as_coord from, struct as_coord to, s_char *pp) { - struct bestp *bp = (struct bestp *) pp; - struct sctstr *ts; - float cost; - int x, y, sx, sy, offset; + struct bestp *bp = (struct bestp *)pp; + struct sctstr *ts; + float cost; + int x, y, sx, sy, offset; #ifdef DO_EFF_MEM_CHECKING - if ((ep->flags & EFF_MEM) == 0) { - ts = bp_getsect(bp, (coord)to.x, (coord)to.y); - } else { + if ((ep->flags & EFF_MEM) == 0) { + ts = bp_getsect(bp, (coord)to.x, (coord)to.y); + } else { #endif /* DO_EFF_MEM_CHECKING */ - x = to.x; - y = to.y; - sx = XNORM(x); - sy = YNORM(y); - offset = (sy * WORLD_X + sx) / 2; - ts = (struct sctstr *)(ep->cache + ep->size * offset); + x = to.x; + y = to.y; + sx = XNORM(x); + sy = YNORM(y); + offset = (sy * WORLD_X + sx) / 2; + ts = (struct sctstr *)(ep->cache + ep->size * offset); #ifdef DO_EFF_MEM_CHECKING - } + } #endif /* DO_EFF_MEM_CHECKING */ - cost = sector_mcost(ts, bp->bp_mobtype); - return (cost); + cost = sector_mcost(ts, bp->bp_mobtype); + return (cost); } /* @@ -321,7 +328,7 @@ bp_lbcost(struct as_coord from, struct as_coord to, s_char *pp) static double bp_realcost(struct as_coord from, struct as_coord to, s_char *pp) { - return (bp_lbcost(from, to, pp)); + return (bp_lbcost(from, to, pp)); } /* @@ -332,8 +339,8 @@ bp_realcost(struct as_coord from, struct as_coord to, s_char *pp) static double bp_seccost(struct as_coord from, struct as_coord to, s_char *pp) { - return ((double) mapdist((coord)from.x, (coord)from.y, - (coord)to.x, (coord)to.y)); + return ((double)mapdist((coord)from.x, (coord)from.y, + (coord)to.x, (coord)to.y)); } #ifdef DO_EFF_MEM_CHECKING @@ -345,18 +352,18 @@ bp_seccost(struct as_coord from, struct as_coord to, s_char *pp) static struct sctstr * bp_getsect(struct bestp *bp, coord x, coord y) { - struct sctstr *sp; - - sp = bp_sctcache_get(bp, x, y); - if (sp == NULL) { - sp = (struct sctstr *) malloc(sizeof(*sp)); - getsect(x, y, sp); - bp_sctcache_set(bp, x, y, sp); - bp->sctcache_misses++; - } else { - bp->sctcache_hits++; - } - return (sp); + struct sctstr *sp; + + sp = bp_sctcache_get(bp, x, y); + if (sp == NULL) { + sp = (struct sctstr *)malloc(sizeof(*sp)); + getsect(x, y, sp); + bp_sctcache_set(bp, x, y, sp); + bp->sctcache_misses++; + } else { + bp->sctcache_hits++; + } + return (sp); } /* @@ -365,18 +372,18 @@ bp_getsect(struct bestp *bp, coord x, coord y) static struct sctstr * bp_sctcache_get(struct bestp *bp, coord x, coord y) { - int hashval; - struct as_coord c; - struct sctcache *hp; - - c.x = x; - c.y = y; - hashval = bp_coord_hash(c) % BP_SCTHASHSIZE; - for (hp = bp->sctcachetab[hashval]; hp; hp = hp->next) { - if (hp->x == x && hp->y == y) - return (hp->sp); - } - return (NULL); + int hashval; + struct as_coord c; + struct sctcache *hp; + + c.x = x; + c.y = y; + hashval = bp_coord_hash(c) % BP_SCTHASHSIZE; + for (hp = bp->sctcachetab[hashval]; hp; hp = hp->next) { + if (hp->x == x && hp->y == y) + return (hp->sp); + } + return (NULL); } /* @@ -385,19 +392,19 @@ bp_sctcache_get(struct bestp *bp, coord x, coord y) static void bp_sctcache_set(struct bestp *bp, coord x, coord y, struct sctstr *sp) { - int hashval; - struct as_coord c; - struct sctcache *hp; - - hp = (struct sctcache *) calloc(1, sizeof(*hp)); - hp->x = x; - hp->y = y; - hp->sp = sp; - c.x = x; - c.y = y; - hashval = bp_coord_hash(c) % BP_SCTHASHSIZE; - hp->next = bp->sctcachetab[hashval]; - bp->sctcachetab[hashval] = hp; + int hashval; + struct as_coord c; + struct sctcache *hp; + + hp = (struct sctcache *)calloc(1, sizeof(*hp)); + hp->x = x; + hp->y = y; + hp->sp = sp; + c.x = x; + c.y = y; + hashval = bp_coord_hash(c) % BP_SCTHASHSIZE; + hp->next = bp->sctcachetab[hashval]; + bp->sctcachetab[hashval] = hp; } /* @@ -406,20 +413,20 @@ bp_sctcache_set(struct bestp *bp, coord x, coord y, struct sctstr *sp) static void bp_sctcache_zap(struct bestp *bp) { - register struct sctcache *hp; - register struct sctcache *np; - register int i; - - for (i = 0; i < BP_SCTHASHSIZE; i++) { - for (hp = bp->sctcachetab[i]; hp; hp = np) { - np = hp->next; - free(hp->sp); - free(hp); - } - bp->sctcachetab[i] = NULL; + register struct sctcache *hp; + register struct sctcache *np; + register int i; + + for (i = 0; i < BP_SCTHASHSIZE; i++) { + for (hp = bp->sctcachetab[i]; hp; hp = np) { + np = hp->next; + free(hp->sp); + free(hp); } - bp->sctcache_hits = 0; - bp->sctcache_misses = 0; + bp->sctcachetab[i] = NULL; + } + bp->sctcache_hits = 0; + bp->sctcache_misses = 0; } #endif /* DO_EFF_MEM_CHECKING */ @@ -430,7 +437,7 @@ bp_sctcache_zap(struct bestp *bp) static int bp_coord_hash(struct as_coord c) { - return ((abs(c.x) + 1) << 3) ^ abs(c.y); + return ((abs(c.x) + 1) << 3) ^ abs(c.y); } void @@ -454,40 +461,38 @@ bp_clear_cachepath() double pathcost(struct sctstr *start, s_char *path, int mob_type) { - register int o; - register 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; - } - o = dirindex[(int)((*path) - 'a')]; - cx += diroff[o][0]; - cy += diroff[o][1]; - sx = XNORM(cx); - sy = YNORM(cy); - offset = (sy * WORLD_X + sx) / 2; - sp = (struct sctstr *)(ep->cache + ep->size * offset); - cost += sector_mcost(sp, mob_type); + register int o; + register 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; } - - return cost; + o = dirindex[(int)((*path) - 'a')]; + cx += diroff[o][0]; + cy += diroff[o][1]; + sx = XNORM(cx); + sy = YNORM(cy); + offset = (sy * WORLD_X + sx) / 2; + sp = (struct sctstr *)(ep->cache + ep->size * offset); + cost += sector_mcost(sp, mob_type); + path++; + } + + return cost; } -s_char * +s_char * BestDistPath(s_char *path, struct sctstr *from, - struct sctstr *to, - double *cost, - int mob_type) + struct sctstr *to, double *cost, int mob_type) { return BestLandPath(path, from, to, cost, mob_type); } @@ -495,9 +500,7 @@ BestDistPath(s_char *path, s_char * BestLandPath(s_char *path, struct sctstr *from, - struct sctstr *to, - double *cost, - int mob_type) + struct sctstr *to, double *cost, int mob_type) { int length; @@ -513,12 +516,7 @@ BestLandPath(s_char *path, } s_char * -BestShipPath(s_char *path, - int fx, - int fy, - int tx, - int ty, - int owner) +BestShipPath(s_char *path, int fx, int fy, int tx, int ty, int owner) { s_char *map; @@ -529,13 +527,8 @@ BestShipPath(s_char *path, } s_char * -BestAirPath(s_char *path, - int fx, - int fy, - int tx, - int ty) +BestAirPath(s_char *path, int fx, int fy, int tx, int ty) { return (bestownedpath(path, 0, fx, fy, tx, ty, "", -1)); - /* return (bestpath(path, fx, fy, tx, ty, ""));*/ + /* return (bestpath(path, fx, fy, tx, ty, "")); */ } -