From: Markus Armbruster Date: Sat, 26 Feb 2011 15:06:09 +0000 (+0100) Subject: Use the new path finder for land paths, drop old A* X-Git-Tag: v4.3.27~98 X-Git-Url: http://git.pond.sub.org/?p=empserver;a=commitdiff_plain;h=ffbbfcb25fd1e5ef1c03c0ece542c97f571ad51d Use the new path finder for land paths, drop old A* This gets rid of the memory leak mentioned in the previous commit. To get rid of the buffer overruns for long paths mentioned in the previous commit, make BestLandPath() fail when path length exceeds 1023 characters. assemble_dist_paths() and move_ground() pass buffers with a different size. Eliminate assemble_dist_paths()'s buffer. Update now works regardless of distribution distance (the distribute command still limits to 1023, to be fixed in a later commit). Enlarge move_ground()'s buffers. Doubles the length of paths accepted by explore, move, and transport. I use two test cases to benchmark the path finders: "continental" (Hvy Metal 2 updates) and "island" (Hvy Plastic 2 updates). The new path finder runs my tests around 3-4 times faster than the old A* without its caches. That's enough to meet its cached performance for "island", but it's only half as fast for "continental". Not for long; big speedups are coming. --- diff --git a/Make.mk b/Make.mk index 79adaa2f6..cc0863d3d 100644 --- a/Make.mk +++ b/Make.mk @@ -119,7 +119,7 @@ obj := $(csrc:.c=.o) $(filter %.o, $(ac:.c=.o)) # Dependencies: deps := $(obj:.o=.d) # Library archives: -libs := $(addprefix lib/, libcommon.a libas.a libgen.a libglobal.a) +libs := $(addprefix lib/, libcommon.a libgen.a libglobal.a) # Programs: util := $(addprefix src/util/, $(addsuffix $(EXEEXT), empdump empsched fairland files pconfig)) client := src/client/empire$(EXEEXT) @@ -291,7 +291,6 @@ $(client): $(filter src/client/%, $(obj)) src/lib/global/version.o $(util): $(libs) -lib/libas.a: $(filter src/lib/as/%, $(obj)) lib/libcommon.a: $(filter src/lib/common/%, $(obj)) lib/libgen.a: $(filter src/lib/gen/%, $(obj)) lib/libglobal.a: $(filter src/lib/global/%, $(obj)) diff --git a/include/path.h b/include/path.h index 7eb70ad5d..3b0cc495e 100644 --- a/include/path.h +++ b/include/path.h @@ -75,16 +75,12 @@ extern double path_find(coord, coord, coord, coord, natid, int); extern size_t path_find_route(char *, size_t, coord, coord, coord, coord); /* 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 *, double *, int); extern char *BestShipPath(char *, int, int, int, int, int); extern char *BestAirPath(char *, int, int, int, int); -extern double pathcost(struct sctstr *, char *, int); /* src/lib/subs/paths.c */ extern char *getpath(char *, char *, coord, coord, int, int, enum p_mode); diff --git a/src/lib/as/COPYRIGHT b/src/lib/as/COPYRIGHT deleted file mode 100644 index bf3e1ab9d..000000000 --- a/src/lib/as/COPYRIGHT +++ /dev/null @@ -1,41 +0,0 @@ -(Note that this copyright notice was changed with permission from Phil -Lapsley to a copyright that complies with the GNU GPL. The new -copyright is supplied here, along with the old copyright notice -below.) - ------ - - A* Search - A search library used in Empire to determine paths between - objects. - Copyright (C) 1990-1998 Phil Lapsley - - This program is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - ------ - -Old Copyright notice follows: - -"Copyright 1990 Phil Lapsley. All rights reserved. - -Redistribution and use in source and binary forms for noncommercial -purposes in support of BSD Empire are permitted provided that this -notice is preserved and that due credit is given to the copyright -holder. This software is provided ``as is'' without express or implied -warranty. Entities interested in other distribution of this software -should contact the copyright holder. - -(Phil is located at phil@east.berkeley.edu)" - ------ diff --git a/src/lib/as/README b/src/lib/as/README deleted file mode 100644 index 99b807612..000000000 --- a/src/lib/as/README +++ /dev/null @@ -1,300 +0,0 @@ -Tue Nov 13 11:50:24 PST 1990 Phil Lapsley phil@Berkeley.EDU - -This library implements a reasonably general version of the A* algorithm. -Basically, A* is like an ordered search, but with a heuristic that allows -it to make a better choices as to which path to take. The subdirectory -"test" has example code for using A* to search a weighted cartesian matrix. -The file "XXX//bestpath.c" has code to interface Empire to the A* -algorithms. - -This library is copyrighted; see the file COPYRIGHT for details. - -COMPILATION - -Do a "make" in this directory to make the library. Cd into "test" and -do a "make" there to make a test program, called (ta da) "test". - -LIBRARY USAGE - -Pretty much all the data that the user needs to communicate to the library -is stored in an "as_data" structure, which is created by a call to "as_init": - - struct as_data *adp; - - adp = as_init( ... ); - -The arguments to as_init specify a number of key things the algorithm will -use, and these are discussed below. - -Once you have an "as_data" structure, you can fill in its "from" and "to" -members, which specify the coordinates of the points between which you want -to go. The basic coordinate data structure is the "as_coord", which is -just an "x" integer and a "y" integer. So: - - adp->from.x = ...; - adp->from.y = ...; - adp->to.x = ...; - adp->to.y = ...; - -and then call as_search: - - as_search(adp); - -If the return value of as_search is 0, the algorithm found a path from -"from" to "to". The path is stored in the "path" member of the "as_data" -structure, and is just a linked list of coordinates ("as_coord" structs) -from "from" to "to". - -If the return value of as_search is -1, the algorithm couldn't find a -path from "from" to "to". If the return is -2, a system error occurred -(most probably malloc failed). - -After a call to as_search, lots of malloced data 'n' stuff will be -floating around, all pointed to by items in the "as_data" data structure. -If you call "as_search" again (presumably with new "from" and "to" -coordinates), the system will free these data structures and reallocate -new ones. If you no longer want the data structures at all (i.e., you -never intend to call "as_search" again), you can call: - - as_delete(adp); - -and this will free up all data associated with the as_data structure pointed -to by adp. - -ARGUMENTS TO AS_INIT - -"as_init" takes eight arguments, in the following order: - - maxneighbors The maximum number of neighboring sectors a - coordinate can have. On a cartesian grid, - this would be 8. On a hex map, it would be 6. - - hashsize The size of the hash table used to determine - if we've visited a particular coordinate. - - hashfunc A pointer to a function that takes an - "as_coord" as an argument and returns an - integer that will be used as a hash value. - If this is a NULL pointer, the as library - will assign its own hash function that just - adds the x and y coordinates together. - - neighborfunc A pointer to a function that takes a coordinate - (call it "c"), a pointer to an array of - coordinates of length "maxneighbors", and - a user data pointer (see below). This - function should figure out the coordinates - of all the neighbors of "c" and put them in - the array cp[0] ... cp[maxneighbors-1]. - It should then return the number of neighbors - found. - - lbcostfunc A pointer to a function that takes two - coordinates, call them "from" and "to", - and a user data pointer (see below). It - returns a double precision *LOWER BOUND* - on the cost to get from "from" to "to". - "from" and "to" may be separated by an - arbitrary distance. More on this below. - - realcostfunc A pointer to a function that takes two - coordinates, call them "from" and "to", - and a user data pointer (see below). It - returns a double precision value of - the *actual cost* to move from "from" to - "to". Note that "from" will never be more - than one sector away from "to". - - seccostfunc A pointer to a function that takes two - coordinates, call them "from" and "to", - and a user data pointer (see below). It - returns a double precision value that will - be used to break ties when two nodes have - the same lower bound to the target. An - example will be discussed below. - - userdata A (char *) that can be a pointer to - any kind of data you want. This will - be passed as the third argument to the - neighborfunc, lbcostfunc, realcostfunc, - and seccostfunc. - -Look in test/cart.c to see examples of these functions for cartesian -coordinates. - -NOTES ON THE LOWER BOUND FUNCTION - -"lbcostfunc" is *CRUCIAL* to the algorithm's performance. The entire -idea behind the A* algorithm is that, when considering whether to move -to a new coordinate, you know two things: - - (1) how much it's cost you to get to that coordinate so far, - - (2) a LOWER BOUND on how much it will cost to get to the - destination from that coordinate. - -If these two conditions are met, the algorithm will return the optimal -path to the destination. The closer the lower bound is to the actual -cost to get from one point to another, the quicker the algorithm will -find this path. HOWEVER, if the lower bound is ever violated, i.e., -if the so-called lower bound function returns a value that is greater -than the actual cost to get to the destination, then the algorithm will -not necessarily find the optimal path. - -Example: - -Assume that we're on a cartesian matrix, and the cost to move from one point -to another is just the distance between the two points, and that no -other costs are involved. In this case, the lower bound function could -be the same as the actual cost function, i.e., - - real cost = lower bound cost = sqrt(dx^2 + dy^2); - -In this case, the algorithm will find the destination as quickly as possible. - -Another example: - -Again assume we're on a cartesian matrix, and the cost to move from -one point to another is two things: (1) the distance between them, (2) some -arbitrary cost function we get off of a map. E.g., - - X - - 0 1 2 3 - 0 0 0 0 0 - 1 0 0 0 0 - Y 2 0 0 2 0 - 3 0 0 0 0 - -The real cost to move from (x,y) 0,0 to 1,0 is 1. That is, it's the distance -(1) plus the value of the map at (1,0), which is 0. The real cost to move -from (1,2) to (2,2) is 3: the distance (1) plus the map value at (2,2), which -is 2, totaling 3. - -In this case, the lower bound function could still be the distance between -the two points, since this WILL NEVER BE MORE than the actual cost, and -hence is a lower bound. I.e., - - real cost = sqrt(dx^2 + dy^2) + map costs - - lower bound cost = sqrt(dx^2 + dy^2) - - lower bound cost <= real cost for all coordinates - -This is what the the example in the "test" directory uses. - -A third example: - -You could make the lower bound function always return 0. This would be -a valid lower bound of the cost to move between any two points. In this -case, the A* algorithm will behave like a breadth-first search, and isn't -very much fun. - -SECONDARY COST FUNCTION - -The algorithm tries new coordinates in order of lowest lower-bound. -There can be cases where the lower-bound function for two (or more) -coordinates is the same, i.e., there is a tie. The algorithm uses -the secondary cost function (which does NOT have to be a lower bound) -to choose which coordinate to pick. A typical heuristic might be -to use Euclidian distance for this secondary cost function, on the -assumption that it's always better to move closer the destination. -The Empire code does just this. - -If you don't need a secondary cost function, just specify a NULL pointer -to the seccost argument to as_init, and the routines will use 0.0 for you. - -EMPIRE INTERFACE - -The interface code in "XXX/bestpath.c" is a rather complicated example -of A* interface code. What it does is based on some features of Empire -that are explained here. - -First, movement cost in Empire is based on a quantity called "mobility -cost", which is a property of every sector. As we trace a path from -source to destination, we add up mobility cost as we go. Once we're -there, we have a total mobility cost. This is what we'd like to -minimize. - -Second, Empire has highways, which are zero cost movement paths. This -hurts the A* algorithm, because it means that the lower bound cost -function is very weak. For example, think what happens if we move from -one side of the country to another: if the two sectors are attached via -a highway, the cost will be very small -- in fact, it will be the cost -to move out of the source sector, and the cost to move into the -destination sector. If, on the other hand, the two sectors aren't -connected by a highway, the cost could be quite large. Thus, the lower -bound is just the cost to move out of a sector plus the cost to move -into a sector. This is a pretty weak lower bound, and means that we -have to explore a lot of sectors. - -Third, the mobility costs tend to tie a lot, as explained in the -section above on secondary cost functions. Thus, we use the Empire -"mapdist" function as a secondary sort function to break ties. For -example, consider the case where a sector borders two highway sectors, -one on each side. The lower bound function will say that the two have -equal lower bound costs, since they're both highways and cost nothing -to move on. The secondary sort function is then used to break the tie -- -it says, "Take the one that moves you closer to the destination". - -Fourth, all of the information we need about a sector (its mobility -cost, who owns it, etc.) is stored in the sector file on disk. This -means that the getsect() function to get it off disk will do a read(), -which is VERY expensive. Because of the weak lower bound, A* ends up -checking lots of sectors, including sectors that it's seen before. -To avoid doing thousands of system calls per second, the bestpath.c file -has sector caching routines that store in memory copies of every -sector we read. (The function bp_getsect handles this). This means -we never read a sector from disk more than once, although at the expense -of using lots of memory. - -THEORY OF OPERATION - -The basic idea is as follows: - - 1. Add the start node to the head of a master queue. - 2. Is the head of the queue where we want to be? If so, stop. - 3. Make a list of all the neighbors coordinates around the - coordinate of the head. - - 4. For each neighbor coordinate, - - Compute the lower bound cost to the destination from here. - - If this coordinate is already on the either the - master queue or the "tried" queue: - - 4a. If it was on either the "master" queue or the - "tried" queue and the one on the queue has a - smaller lower-bound than the neighbor, ignore - this neighbor and go on to the next neighbor. - - 4b. If it was on the "master" queue and the new - neighbor has a smaller lower bound, - Move the one on the queue to a different - queue called "subsumed". - - 4c. If it was on the "tried" queue and the new - neighbor has a smaller lower bound, - Move the one on the "tried" queue to the - master queue, and update its lower bound - value to be as the new neighbor, and - update its backpointer appropriately. - - We now have a list of all neighbor coordinates that are either - not on the queue already, or are cheaper than the ones on the - queue. - - 5. Move the node at the head of the queue (the one whose neighbors - we now have in a list) onto a different queue called "tried". - - 6. Sort this list of neighbors, and merge it into the master queue, - keeping the master queue ordered by lower bound cost to destination. - - 7. Goto 2. - -My algorithm does all of this, plus a little more (the above doesn't really -mention backpointers except in passing), EXCEPT: I don't do step 4c. -I'm not convinced that this can ever occur if the lower bound rule isn't -broken, and I have yet to see it occur. However, if as_winnow returns -1, -this error has occurred. diff --git a/src/lib/as/as.h b/src/lib/as/as.h deleted file mode 100644 index c6817816e..000000000 --- a/src/lib/as/as.h +++ /dev/null @@ -1,195 +0,0 @@ -/* - * A* Search - A search library used in Empire to determine paths between - * objects. - * Copyright (C) 1990-1998 Phil Lapsley - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ -/* - * A* definitions. - * - * @(#)as.h 1.9 11/13/90 - */ -/* - * 11/09/98 - Steve McClure - * Added path list caching structures - */ - -#ifndef AS_H -#define AS_H - -#include -#include "types.h" - -/* - * Coordinate. - */ -struct as_coord { - int x, y; -}; - -/* - * Path, made up of a linked list of coordinates. - */ -struct as_path { - struct as_coord c; - struct as_path *next; -}; - -/* - * Basic node, used internally by A* algorithm. - */ -struct as_node { - struct as_coord c; /* our coordinate */ - double knowncost; /* cost so far */ - double lbcost; /* lower bound on cost to dest */ - double inclbcost; /* incremental lower bound cost */ - double seccost; /* used to break ties */ - int step; - int flags; - struct as_node *back; -}; -#define AS_TRIED 1 /* we've tried this node before */ - -/* - * Linked list of nodes, used internally by A* algorithm. - */ -struct as_queue { - struct as_node *np; - struct as_queue *next; - struct as_queue *prev; -}; - -/* - * Hash table entry, used to determine if we've seen a particular - * coordinate before. - */ -struct as_hash { - struct as_coord c; - struct as_queue *qp; - struct as_hash *next; -}; - -/* - * User's handle on A*, returned by as_init(). Some of the data here is - * used by A* internals. - */ -struct as_data { - int maxneighbors; /* max # of neighbors a cell can have */ - int hashsize; /* size of internal hash table */ - - /* hash function (coord -> int) */ - int (*hash)(struct as_coord); - /* function to find neighbors */ - int (*neighbor)(struct as_coord, struct as_coord *, void *); - /* function to give lower bound cost */ - double (*lbcost)(struct as_coord, struct as_coord, void *); - /* function to give real cost */ - double (*realcost)(struct as_coord, struct as_coord, void *); - /* function to secondary cost */ - double (*seccost)(struct as_coord, struct as_coord, void *); - void *userdata; /* user's data, passed to callbacks */ - struct as_coord from; /* from coordinate */ - struct as_coord to; /* to coordinate */ - struct as_path *path; /* solution */ - - /* below are "private" to as_ routines */ - struct as_queue *head; - struct as_queue *tried; - struct as_hash **hashtab; - struct as_queue *subsumed; - struct as_coord *neighbor_coords; - struct as_node **neighbor_nodes; -}; - -/* - * Added these for caching of paths as we stumble across them - */ - -struct as_topath { - coord x; - struct as_path *path; /* Path from holder of this list to here */ - struct as_topath *next; -}; - -struct as_frompath { - coord x; - struct as_topath **tolist; /* List of nodes we have a path to */ - struct as_frompath *next; -}; - -/* - * Some cheezy allocation macros. - */ -#define AS_NEW_ARRAY(p, type, n, err) \ - (p) = (type *)calloc((n), sizeof(*(p))); \ - if ((p) == NULL) \ - return err; \ - -#define AS_NEW(p, type, err) \ - AS_NEW_ARRAY((p), type, 1, err); - -#define AS_NEW_MALLOC(p, type, err) \ - (p) = (type *)malloc(sizeof(type)); \ - if ((p) == NULL) \ - return err; \ - -/* Functions that the user can call. */ - -extern struct as_data *as_init(int maxneighbors, int hashsize, - int (*hashfunc)(struct as_coord), - int (*neighborfunc)(struct as_coord, - struct as_coord *, - void *), - double (*lbcostfunc)(struct as_coord, - struct as_coord, - void *), - double (*realcostfunc)(struct as_coord, - struct as_coord, - void *), - double (*seccostfunc)(struct as_coord, - struct as_coord, - void *), - void *userdata); -extern int as_search(struct as_data *adp); -extern void as_delete(struct as_data *adp); -extern void as_reset(struct as_data *adp); -extern void as_stats(struct as_data *adp, FILE * fp); -extern struct as_path *as_find_cachepath(coord fx, coord fy, - coord tx, coord ty); - -/* Functions that are "private" to algorithm */ - -extern void as_add_cachepath(struct as_data *adp); -extern void as_clear_cachepath(void); -extern void as_enable_cachepath(void); -extern void as_disable_cachepath(void); - -extern void as_makepath(struct as_data *adp); -extern void as_free_path(struct as_path *pp); - -extern int as_costcomp(const void *, const void *); -extern struct as_queue *as_extend(struct as_data *adp); -extern struct as_queue *as_merge(struct as_data *adp, - struct as_queue *head, - struct as_node **neighbors); -extern struct as_queue *as_iscinq(struct as_data *adp, struct as_coord c); -extern void as_setcinq(struct as_data *adp, - struct as_coord c, struct as_queue *qp); -extern void as_free_hashtab(struct as_data *adp); -extern int as_winnow(struct as_data *adp, - struct as_coord *coords, int ncoords); - -#endif diff --git a/src/lib/as/as_cache.c b/src/lib/as/as_cache.c deleted file mode 100644 index d98e088ee..000000000 --- a/src/lib/as/as_cache.c +++ /dev/null @@ -1,198 +0,0 @@ -/* - * Empire - A multi-player, client/server Internet based war game. - * Copyright (C) 1986-2010, Dave Pare, Jeff Bailey, Thomas Ruschak, - * Ken Stevens, Steve McClure - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - * - * --- - * - * See files README, COPYING and CREDITS in the root of the source - * tree for related information and legal notices. It is expected - * that future projects/authors will amend these files as needed. - * - * --- - * - * as_cache.c: Routines used to create/delete caches of A* paths. - * - * Known contributors to this file: - * Steve McClure, 1998 - */ - -#include - -#include -#include -#include "as.h" -#include "optlist.h" - -/* The way this works is interesting. :) */ -/* We keep a pointer to a list of pointers. The index into this list - * is the y coordinate of the from sector. This member points to a list - * of from sectors on that y coordinate. So, we march that list checking - * the x value to find the from x,y we want. */ -/* Once we find the from x,y, that node has the same type of pointer to - * a list of pointers. The index into this list is the y coordinate of - * the to sector. This member points to a list of to sectors on that y - * coordinate. So, we march that list checking the x value to find the - * to x,y we want. */ -/* These lists are dynamically created since the world is dynamically sized. */ -/* See, I told you it was interesting. :) */ - -static struct as_frompath **fromhead = (struct as_frompath **)0; - -/* Note that we only want to cache during updates. Other times, it - * probably doesn't make much sense, but can be done. */ - -static int as_cachepath_on = 0; /* Default to off */ - -void -as_enable_cachepath(void) -{ - as_cachepath_on = 1; -} - -void -as_disable_cachepath(void) -{ - as_cachepath_on = 0; -} - -/* Note we want these to be as fast as possible */ - -void -as_add_cachepath(struct as_data *adp) -{ - struct as_frompath *from; - struct as_topath *to = (struct as_topath *)0; - struct as_node *np; - - /* Don't do anything if we aren't cacheing these */ - if (as_cachepath_on == 0) - return; - - /* Note we will only allocate this once. Afterwards, we just keep - * zeroing it since it's rather small and we don't need to re-allocate - * each time. */ - if (fromhead == NULL) { - fromhead = calloc(1, sizeof(struct as_frompath *) * WORLD_Y); - if (fromhead == NULL) - return; - } - - np = adp->head->np; - for (from = fromhead[adp->from.y]; from; from = from->next) - if (from->x == adp->from.x) - break; - if (from) { - for (to = from->tolist[np->c.y]; to; to = to->next) { - if (to->x == np->c.x) { - /* It is already here! Don't bother adding it again */ - return; - } - } - } else { - /* We must make a new one of these */ - from = malloc(sizeof(struct as_frompath)); - if (from == NULL) - return; - /* And set some stuff */ - from->x = adp->from.x; - /* Here we malloc a whole bunch of tolist pointers. */ - from->tolist = calloc(1, sizeof(struct as_topath *) * WORLD_Y); - /* Now, add from to the global list */ - from->next = fromhead[adp->from.y]; - fromhead[adp->from.y] = from; - } - if (!to) { - /* We must make a new one */ - to = malloc(sizeof(struct as_topath)); - /* We can't, sorry */ - if (to == NULL) - return; - /* Now set some stuff */ - to->x = np->c.x; - /* Now add it to the list we are in */ - to->next = from->tolist[np->c.y]; - from->tolist[np->c.y] = to; - } - /* Now, make the path */ - as_makepath(adp); - /* Now, take the path */ - to->path = adp->path; - /* And clear the path in the adp */ - adp->path = NULL; -} - -void -as_clear_cachepath(void) -{ - struct as_frompath *from, *from2; - struct as_topath *to, *to2; - int i, j; - - /* Cache not used yet :) */ - if (fromhead == NULL) - return; - - for (j = 0; j < WORLD_Y; j++) { - for (from = fromhead[j]; from; from = from2) { - for (i = 0; i < WORLD_Y; i++) { - for (to = from->tolist[i]; to; to = to2) { - to2 = to->next; - /* Free this path */ - as_free_path(to->path); - /* Free this node */ - free(to); - } - } - /* Now, free the list of lists */ - free(from->tolist); - /* Save the next pointer */ - from2 = from->next; - /* now, free this from node */ - free(from); - } - } - /* Note we don't free the fromhead here, we just zero it. That way, - we can use it next time without mallocing int */ - memset(fromhead, 0, (sizeof(struct as_frompath *) * WORLD_Y)); -} - -struct as_path * -as_find_cachepath(coord fx, coord fy, coord tx, coord ty) -{ - struct as_frompath *from; - struct as_topath *to; - - /* Is the cache on? if not, return NULL */ - if (as_cachepath_on == 0) - return NULL; - - /* Do we have any cached? */ - if (fromhead == NULL) - return NULL; - - /* Yes! */ - for (from = fromhead[fy]; from; from = from->next) { - if (from->x == fx) { - for (to = from->tolist[ty]; to; to = to->next) { - if (to->x == tx) - return to->path; - } - } - } - return NULL; -} diff --git a/src/lib/as/as_costcomp.c b/src/lib/as/as_costcomp.c deleted file mode 100644 index 2aa6e5b35..000000000 --- a/src/lib/as/as_costcomp.c +++ /dev/null @@ -1,50 +0,0 @@ -/* - * A* Search - A search library used in Empire to determine paths between - * objects. - * Copyright (C) 1990-1998 Phil Lapsley - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include - -#include "as.h" - -/* - * Compare the lower bound costs of two nodes. If the two nodes have - * equal lower bound costs, sort on the secondary field. - * Used as comparision function for qsort. - */ -int -as_costcomp(const void *p1, const void *p2) -{ - struct as_node *const *n1 = p1; - struct as_node *const *n2 = p2; - double diff; - - diff = (*n1)->lbcost - (*n2)->lbcost; - if (diff < -0.0001) - return -1; - if (diff > 0.0001) - return 1; - - /* equal, check secondary cost */ - diff = (*n1)->seccost - (*n2)->seccost; - if (diff < -0.0001) - return -1; - if (diff > 0.0001) - return 1; - return 0; -} diff --git a/src/lib/as/as_delete.c b/src/lib/as/as_delete.c deleted file mode 100644 index eab8b4be0..000000000 --- a/src/lib/as/as_delete.c +++ /dev/null @@ -1,85 +0,0 @@ -/* - * A* Search - A search library used in Empire to determine paths between - * objects. - * Copyright (C) 1990-1998 Phil Lapsley - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include - -#include -#include "as.h" - -static void as_free_queue(struct as_queue *queue); - -/* - * Free any dynamically allocated data stored in the as_data structure. - */ -void -as_reset(struct as_data *adp) -{ - as_free_queue(adp->head); - adp->head = NULL; - as_free_queue(adp->tried); - adp->tried = NULL; - as_free_queue(adp->subsumed); - adp->subsumed = NULL; - as_free_hashtab(adp); - as_free_path(adp->path); - adp->path = NULL; -} - -/* - * Free a queue (either the main, subsumed, or tried). - */ -static void -as_free_queue(struct as_queue *queue) -{ - struct as_queue *qp, *qp2; - - for (qp = queue; qp; qp = qp2) { - free(qp->np); - qp2 = qp->next; - free(qp); - } -} - -/* - * Free a path. - */ -void -as_free_path(struct as_path *pp) -{ - struct as_path *pp2; - - for (; pp; pp = pp2) { - pp2 = pp->next; - free(pp); - } -} - -/* - * Delete the as_data structure (which includes freeing its data). - */ -void -as_delete(struct as_data *adp) -{ - as_reset(adp); - free(adp->neighbor_coords); - free(adp->neighbor_nodes); - free(adp->hashtab); - free(adp); -} diff --git a/src/lib/as/as_extend.c b/src/lib/as/as_extend.c deleted file mode 100644 index 4c9e7e3a6..000000000 --- a/src/lib/as/as_extend.c +++ /dev/null @@ -1,71 +0,0 @@ -/* - * A* Search - A search library used in Empire to determine paths between - * objects. - * Copyright (C) 1990-1998 Phil Lapsley - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include - -#include -#include "as.h" - -/* - * Extend the queue by neighbors. This entails getting the - * coordinates of all the neighbors, figuring out their lower bound - * costs, throwing away ones that are more expensive than ones we - * already have, sorting, tand then merging into the queue. - */ -struct as_queue * -as_extend(struct as_data *adp) -{ - struct as_queue *qp; - int i; - struct as_queue *head; - - head = adp->head; - - /* Find the neighboring coordinates. */ - i = adp->neighbor(head->np->c, adp->neighbor_coords, adp->userdata); - if (i == 0) - return NULL; - /* - * Get rid of neighbors that are more costly than ones we already have, - * and sort the rest into an array of as_nodes. - */ - i = as_winnow(adp, adp->neighbor_coords, i); - if (i < 0) - return NULL; - if (i > 1) - qsort(adp->neighbor_nodes, i, - sizeof(*adp->neighbor_nodes), as_costcomp); - - /* remove old coord from head of queue and add to list of tried */ - qp = head; - head = head->next; - if (head) - head->prev = NULL; - if (adp->tried) { - adp->tried->prev = qp; - qp->next = adp->tried; - adp->tried = qp; - } else - adp->tried = qp; - adp->tried->np->flags |= AS_TRIED; - - head = as_merge(adp, head, adp->neighbor_nodes); - return head; -} diff --git a/src/lib/as/as_hash.c b/src/lib/as/as_hash.c deleted file mode 100644 index c211befca..000000000 --- a/src/lib/as/as_hash.c +++ /dev/null @@ -1,83 +0,0 @@ -/* - * A* Search - A search library used in Empire to determine paths between - * objects. - * Copyright (C) 1990-1998 Phil Lapsley - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include - -#include -#include "as.h" - -/* - * Return a pointer to the as_queue structure associated with - * this coordinate if the coordinate is in the queue. - */ -struct as_queue * -as_iscinq(struct as_data *adp, struct as_coord c) -{ - int hashval; - struct as_hash *hp; - - hashval = adp->hash(c) % adp->hashsize; - - for (hp = adp->hashtab[hashval]; hp; hp = hp->next) - if (hp->c.x == c.x && hp->c.y == c.y) - return hp->qp; - - return NULL; -} - -/* - * Set the queue structure associated with this coordinate. - */ -void -as_setcinq(struct as_data *adp, struct as_coord c, struct as_queue *qp) -{ - int hashval; - struct as_hash *hp; - struct as_hash *new; - - new = (struct as_hash *)malloc(sizeof(struct as_hash)); - new->c = c; - new->qp = qp; - - hashval = adp->hash(c) % adp->hashsize; - hp = adp->hashtab[hashval]; - - new->next = (hp) ? hp : NULL; - adp->hashtab[hashval] = new; -} - -/* - * Walk down the hash table array, freeing the chains and zeroing - * the chain pointers. - */ -void -as_free_hashtab(struct as_data *adp) -{ - int i; - struct as_hash *hp, *hp2; - - for (i = 0; i < adp->hashsize; i++) { - for (hp = adp->hashtab[i]; hp; hp = hp2) { - hp2 = hp->next; - free(hp); - } - adp->hashtab[i] = NULL; - } -} diff --git a/src/lib/as/as_init.c b/src/lib/as/as_init.c deleted file mode 100644 index 105140854..000000000 --- a/src/lib/as/as_init.c +++ /dev/null @@ -1,59 +0,0 @@ -/* - * A* Search - A search library used in Empire to determine paths between - * objects. - * Copyright (C) 1990-1998 Phil Lapsley - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include - -#include -#include "as.h" - -/* - * Return an as_data structure with the necessary fields filled in - * and space malloced. Return NULL if malloc fails. - */ -struct as_data * -as_init(int maxneighbors, - int hashsize, - int (*hashfunc)(struct as_coord), - int (*neighborfunc)(struct as_coord, struct as_coord *, void *), - double (*lbcostfunc)(struct as_coord, struct as_coord, void *), - double (*realcostfunc)(struct as_coord, struct as_coord, void *), - double (*seccostfunc)(struct as_coord, struct as_coord, void *), - void *userdata) -{ - struct as_data *adp; - - AS_NEW(adp, struct as_data, NULL); - AS_NEW_ARRAY(adp->neighbor_coords, struct as_coord, - maxneighbors, NULL); - AS_NEW_ARRAY(adp->neighbor_nodes, struct as_node *, - maxneighbors + 1, NULL); - AS_NEW_ARRAY(adp->hashtab, struct as_hash *, hashsize, NULL); - - adp->maxneighbors = maxneighbors; - adp->hashsize = hashsize; - adp->hash = hashfunc; - adp->neighbor = neighborfunc; - adp->lbcost = lbcostfunc; - adp->realcost = realcostfunc; - adp->seccost = seccostfunc; - adp->userdata = userdata; - - return adp; -} diff --git a/src/lib/as/as_merge.c b/src/lib/as/as_merge.c deleted file mode 100644 index ccd7b799a..000000000 --- a/src/lib/as/as_merge.c +++ /dev/null @@ -1,83 +0,0 @@ -/* - * A* Search - A search library used in Empire to determine paths between - * objects. - * Copyright (C) 1990-1998 Phil Lapsley - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include - -#include -#include "as.h" - -/* - * Merge neighbors into queue, keeping it sorted. "neighbors" is sorted, - * both by lower bound cost and then by secondary cost. - */ -struct as_queue * -as_merge(struct as_data *adp, struct as_queue *head, - struct as_node **neighbors) -{ - struct as_queue *qp; - struct as_queue *pp; /* previous pointer */ - struct as_queue *ip; /* insert pointer */ - struct as_node *np; - int i; - - qp = head; - pp = NULL; - for (i = 0; neighbors[i]; i++) { - np = neighbors[i]; - /* scan until qp points to a node we should go in front of */ - while (qp && (qp->np->lbcost < np->lbcost)) { - pp = qp; - qp = qp->next; - } - /* check for equal lower bounds, and use secondary cost if = */ - if (qp && qp->np->lbcost == np->lbcost) { - while (qp && (qp->np->lbcost == np->lbcost) && - (qp->np->seccost < np->seccost)) { - pp = qp; - qp = qp->next; - } - } - AS_NEW_MALLOC(ip, struct as_queue, NULL); - /* if there was such a node, insert us in front of it */ - if (qp) { - ip->prev = qp->prev; - if (ip->prev) - ip->prev->next = ip; - ip->next = qp; - qp->prev = ip; - if (qp == head) - head = ip; - } else { /* otherwise add us to end of queue */ - ip->next = NULL; - ip->prev = pp; - if (ip->prev) - ip->prev->next = ip; - else { - head = ip; - } - pp = ip; - } - ip->np = np; - as_setcinq(adp, np->c, ip); - np->step++; - } - - return head; -} diff --git a/src/lib/as/as_search.c b/src/lib/as/as_search.c deleted file mode 100644 index 724510857..000000000 --- a/src/lib/as/as_search.c +++ /dev/null @@ -1,146 +0,0 @@ -/* - * A* Search - A search library used in Empire to determine paths between - * objects. - * Copyright (C) 1990-1998 Phil Lapsley - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ -/* - * 11/09/98 - Steve McClure - * Added path list caching structures - */ - -#include - -#include -#include "as.h" - -/* - * Basic A* search function. "adp" should have been initialized by - * as_init (any previously allocated data will be freed by as_reset here), - * and adp->from and adp->to should be set accordingly. On success, - * returns 0, with adp->path set to a linked list of coordinates to target. - * If we can't find target, return -1; if malloc fails, return -2. - */ -int -as_search(struct as_data *adp) -{ - int iter = 0; - struct as_queue *head; - struct as_node *np; -#ifdef DEBUG - int i; - struct as_queue *qp; - struct as_path *pp; -#endif /* DEBUG */ - - as_reset(adp); - - /* - * Jump start the queue by making first element the zero-cost - * node where we start. - */ - AS_NEW_MALLOC(head, struct as_queue, -2); - adp->head = head; - head->next = head->prev = NULL; - AS_NEW(np, struct as_node, -2); - np->c = adp->from; - head->np = np; - as_setcinq(adp, head->np->c, adp->head); - - for (;;) { - iter++; - /* see if we're done, one way or another */ - if (head == NULL) - break; - -#ifdef DEBUG - fprintf(stderr, "Iteration %d, head at %d, %d\n", iter, - head->np->c.x, head->np->c.y); -#endif /* DEBUG */ - - /* Add it to the cache */ - as_add_cachepath(adp); - - if (head->np->c.x == adp->to.x && head->np->c.y == adp->to.y) - break; - - /* extend queue by neighbors */ -#ifdef DEBUG - fprintf(stderr, "\tExtending queue\n"); -#endif /* DEBUG */ - adp->head = head = as_extend(adp); - /* FIXME leaks when as_extend() returns NULL without adding to tried */ - -#ifdef DEBUG - fprintf(stderr, "queue:\n"); - i = 0; - for (qp = head; qp; qp = qp->next) { - fprintf(stderr, "\t%d, %d so far %f lb %f sec %f\n", - qp->np->c.x, qp->np->c.y, - qp->np->knowncost, qp->np->lbcost, qp->np->seccost); - i++; - } - fprintf(stderr, "\tqueue len %d\n", i); -#endif /* DEBUG */ - - } - - if (head == NULL) { -#ifdef DEBUG - fprintf(stderr, "Failed\n"); -#endif /* DEBUG */ - return -1; - } - - as_makepath(adp); - -#ifdef DEBUG - fprintf(stderr, "Succeeded, iter %d, cost %f!\n", iter, - head->np->knowncost); - fprintf(stderr, "Path:\n"); - for (pp = adp->path; pp; pp = pp->next) { - fprintf(stderr, "\t%d, %d\n", pp->c.x, pp->c.y); - } - fprintf(stderr, "Tried queue:\n"); - for (qp = adp->tried; qp; qp = qp->next) { - fprintf(stderr, "\t%d, %d\n", qp->np->c.x, qp->np->c.y); - } - fprintf(stderr, "Subsumed queue:\n"); - for (qp = adp->subsumed; qp; qp = qp->next) { - fprintf(stderr, "\t%d, %d\n", qp->np->c.x, qp->np->c.y); - } -#endif /* DEBUG */ - - return 0; -} - -/* - * Work backwards through the list of nodes (starting at head) - * to produce a path. - */ -void -as_makepath(struct as_data *adp) -{ - struct as_path *pp; - struct as_node *np; - - for (np = adp->head->np; np; np = np->back) { - pp = malloc(sizeof(struct as_path)); - pp->c = np->c; - pp->next = adp->path; - adp->path = pp; - } -} diff --git a/src/lib/as/as_stats.c b/src/lib/as/as_stats.c deleted file mode 100644 index cadc8dc4d..000000000 --- a/src/lib/as/as_stats.c +++ /dev/null @@ -1,73 +0,0 @@ -/* - * A* Search - A search library used in Empire to determine paths between - * objects. - * Copyright (C) 1990-1998 Phil Lapsley - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include - -#include "as.h" - -/* - * Print statistics on algorithm performance to the file pointer "fp". - */ -void -as_stats(struct as_data *adp, FILE * fp) -{ - int i; - int j; - int total_q; - int total_h; - struct as_queue *qp; - struct as_hash *hp; - - fprintf(fp, "Statistics:\n"); - - fprintf(fp, "queue lengths:\n"); - total_q = 0; - total_h = 0; - for (i = 0, qp = adp->head; qp; qp = qp->next) - i++; - fprintf(fp, "\tmain:\t%d\n", i); - total_q += i; - for (i = 0, qp = adp->tried; qp; qp = qp->next) - i++; - fprintf(fp, "\ttried:\t%d\n", i); - total_q += i; - for (i = 0, qp = adp->subsumed; qp; qp = qp->next) - i++; - fprintf(fp, "\tsubsumed:\t%d\n", i); - total_q += i; - fprintf(fp, "hash table statistics (size %d):\n", adp->hashsize); - for (i = 0; i < adp->hashsize; i++) { - for (j = 0, hp = adp->hashtab[i]; hp; hp = hp->next) - j++; - fprintf(fp, "\t%d\t%d\n", i, j); - total_h += j; - } - fprintf(fp, "\ttotal\t%d\n", total_h); - fprintf(fp, "approximate memory usage (bytes):\n"); - fprintf(fp, "\tqueues\t%d\n", - (int)(total_q * sizeof(struct as_queue))); - fprintf(fp, "\tnodes\t%d\n", (int)(total_q * sizeof(struct as_node))); - fprintf(fp, "\thash ents\t%d\n", - (int)(total_h * sizeof(struct as_hash))); - fprintf(fp, "\ttotal\t%d\n", - (int)(total_q * sizeof(struct as_queue) + - total_q * sizeof(struct as_node) + - total_h * sizeof(struct as_hash))); -} diff --git a/src/lib/as/as_winnow.c b/src/lib/as/as_winnow.c deleted file mode 100644 index 339b85dc9..000000000 --- a/src/lib/as/as_winnow.c +++ /dev/null @@ -1,174 +0,0 @@ -/* - * A* Search - A search library used in Empire to determine paths between - * objects. - * Copyright (C) 1990-1998 Phil Lapsley - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include - -#include -#include "as.h" - -static struct as_node *as_newnode(struct as_node *backp, struct as_coord c, - double inclbcost, double lbcost, - double knowncost, double seccost); - -/* - * Take a list of neighbor coordinates and winnow them down into - * an interesting list of neighbor nodes. This means: - * - * For each neighbor, - * Compute a lower bound on the total cost to target. - * If this neighbor is already in our queue, - * See if the new neighbor is cheaper. - * If so, add it to queue and move the - * old node to the subsumed list. - * If not, ignore this neighbor. - * If this neighbor isn't in the queue, add it. - */ -int -as_winnow(struct as_data *adp, struct as_coord *coords, int ncoords) -{ - int i = 0; - int fix_pointer; - double knowncost; - double incknowncost; - double lbcost; - double inclbcost; - double seccost; - struct as_coord *cp; - struct as_coord *end; - struct as_queue *qp; - struct as_node *np; - - for (cp = coords, end = coords + ncoords; cp < end; cp++) { - fix_pointer = 0; - incknowncost = adp->realcost(adp->head->np->c, *cp, adp->userdata); - knowncost = adp->head->np->knowncost + incknowncost; - /* - * If this neighbor is already in the queue, we can - * save some time. - */ - qp = as_iscinq(adp, *cp); - inclbcost = qp ? qp->np->inclbcost : - adp->lbcost(*cp, adp->to, adp->userdata); - if (inclbcost < 0.0) /* skip bad cases */ - continue; - lbcost = knowncost + inclbcost; -#ifdef DEBUG - fprintf(stderr, "\tneighbor %d, %d, lbcost %f ", cp->x, cp->y, - lbcost); -#endif /* DEBUG */ - /* - * If this neighbor is already in the queue, check to - * see which has the lower cost. If the one already in - * the queue is cheaper, skip this neighbor as bad. If - * the neighbor does, delete the one in the queue. - */ - if (qp) { - if (qp->np->lbcost <= lbcost) { -#ifdef DEBUG - fprintf(stderr, "old, loses to %f\n", qp->np->lbcost); -#endif /* DEBUG */ - continue; - } else { -#ifdef DEBUG - fprintf(stderr, "old, wins over %f\n", qp->np->lbcost); -#endif /* DEBUG */ - if (qp->np->flags & AS_TRIED) { - /* should "never happen" */ - return 0; - } - /* - * The neighbor is better than a previously visited coordinate; - * remove the old coordinate from the queue and add it to - * the subsumed nodes queue. To get here at - * all we can't be the head, thus qp->prev is defined. - */ - /* Delete from main queue */ - qp->prev->next = qp->next; - if (qp->next) - qp->next->prev = qp->prev; - - /* Add to subsumed queue */ - if (adp->subsumed) { - adp->subsumed->prev = qp; - qp->next = adp->subsumed; - } else { - qp->next = NULL; - } - adp->subsumed = qp; - adp->subsumed->prev = NULL; - fix_pointer = 1; - /* - * At this point, the as_iscinq code may contain bogus pointer - * refs. They'll be fixed when as_merge merges the new - * neighbors into the main queue. - */ - } - } -#ifdef DEBUG - else { - fprintf(stderr, "new\n"); - } -#endif /* DEBUG */ - - if (qp) - seccost = qp->np->seccost; - else - seccost = adp->seccost ? - adp->seccost(*cp, adp->to, adp->userdata) : 0.0; - np = as_newnode(adp->head->np, *cp, inclbcost, lbcost, - knowncost, seccost); - if (np == NULL) - return 0; - if (fix_pointer) { -#ifdef DEBUG - fprintf(stderr, "Fixing pointer for %d, %d\n", - adp->subsumed->np->c.x, adp->subsumed->np->c.y); -#endif - adp->subsumed->np->back = np; - } - adp->neighbor_nodes[i++] = np; - - } - adp->neighbor_nodes[i] = NULL; - - return i; -} - - -static struct as_node * -as_newnode(struct as_node *backp, struct as_coord c, - double inclbcost, double lbcost, double knowncost, - double seccost) -{ - struct as_node *np; - - /* Got an interesting coordinate; make a node for it. */ - AS_NEW_MALLOC(np, struct as_node, NULL); - np->flags = 0; - np->c = c; - np->inclbcost = inclbcost; - np->lbcost = lbcost; - np->knowncost = knowncost; - np->seccost = seccost; - np->step = backp->step; - np->back = backp; - - return np; -} diff --git a/src/lib/common/path.c b/src/lib/common/path.c index 04e9ddcc6..a5f18c731 100644 --- a/src/lib/common/path.c +++ b/src/lib/common/path.c @@ -24,314 +24,55 @@ * * --- * - * path.c: Empire/A* Interface code. - * Define AS_STATS for A* statistics. + * path.c: Path finding interface code * * Known contributors to this file: * Phil Lapsley, 1991 * Dave Pare, 1991 * Thomas Ruschak, 1993 * Steve McClure, 1997 + * Markus Armbruster, 2011 */ #include -#include -#include "../as/as.h" +#include #include "file.h" -#include "misc.h" #include "optlist.h" #include "path.h" -#include "prototypes.h" #include "sect.h" #include "xy.h" -#define BP_ASHASHSIZE 128 /* A* queue hash table size */ -#define BP_NEIGHBORS 6 /* max number of neighbors */ - -struct bestp { - int sctcache_hits; - int sctcache_misses; - 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) +char * +BestLandPath(char *path, + struct sctstr *from, + struct sctstr *to, double *cost, int mob_type) { - struct bestp *bp; + double c; + size_t len; - 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); + *cost = 0.0; + *path = 0; - if (bp->adp == NULL) + /* + * 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; - - if (neighsects == NULL) - neighsects = calloc(WORLD_SZ() * 6, sizeof(struct sctstr *)); - - 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; - - if (!mybestpath) - mybestpath = bp_init(); - adp = mybestpath->adp; - 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); -#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); -#endif /* BP_STATS */ - 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 = 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_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) -{ - as_enable_cachepath(); -} - -void -bp_disable_cachepath(void) -{ - as_disable_cachepath(); -} - -void -bp_clear_cachepath(void) -{ - as_clear_cachepath(); -} - -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; + 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 * @@ -342,24 +83,6 @@ BestDistPath(char *path, 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) { diff --git a/src/lib/common/pathfind.c b/src/lib/common/pathfind.c index ae71b6478..6536514d8 100644 --- a/src/lib/common/pathfind.c +++ b/src/lib/common/pathfind.c @@ -452,6 +452,9 @@ bufrotate(char *buf, size_t bufsz, size_t i) static double cost_land(natid actor, int uid, int mobtype) { + /* + * Non-negative cost must not depend on ACTOR, see BestLandPath(). + */ struct sctstr *sp = (void *)empfile[EF_SECTOR].cache; if (sp[uid].sct_own != actor) diff --git a/src/lib/subs/move.c b/src/lib/subs/move.c index 5ae391766..57abc7543 100644 --- a/src/lib/subs/move.c +++ b/src/lib/subs/move.c @@ -63,8 +63,8 @@ move_ground(struct sctstr *start, struct sctstr *end, int intcost; int takedam = *dam; int out = 0; - char bpath[512]; - char buf2[512]; + char bpath[1024]; + char buf2[1024]; char prompt[128]; char buf[1024]; diff --git a/src/lib/update/finish.c b/src/lib/update/finish.c index b621db547..8fc8af924 100644 --- a/src/lib/update/finish.c +++ b/src/lib/update/finish.c @@ -77,19 +77,7 @@ finish_sects(int etu) logerror("assembling paths...\n"); getrusage(RUSAGE_SELF, &rus1); - - /* First, enable the best_path cacheing */ - bp_enable_cachepath(); - - /* Now assemble the paths */ assemble_dist_paths(import_cost); - - /* Now disable the best_path cacheing */ - bp_disable_cachepath(); - - /* Now, clear the best_path cache that may have been created */ - bp_clear_cachepath(); - getrusage(RUSAGE_SELF, &rus2); logerror("done assembling paths %g user %g system", rus2.ru_utime.tv_sec + rus2.ru_utime.tv_usec / 1e6 @@ -125,27 +113,21 @@ finish_sects(int etu) static void assemble_dist_paths(double *import_cost) { - char *path; - double d; struct sctstr *sp; struct sctstr *dist; int n; - 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)) + 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; + import_cost[n] = path_find(sp->sct_dist_x, sp->sct_dist_y, + sp->sct_x, sp->sct_y, + dist->sct_own, MOB_MOVE); } }