# Dependencies:
deps := $(obj:.o=.d)
# Library archives:
-libs := $(addprefix lib/, libcommon.a libgen.a libglobal.a)
+libs := $(addprefix lib/, libcommon.a libas.a libgen.a libglobal.a)
# Programs:
util := $(addprefix src/util/, $(addsuffix $(EXEEXT), empdump empsched fairland files pconfig))
client := src/client/empire$(EXEEXT)
$(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))
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);
#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 *,
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);
/*
* src/lib/common/ *.c
*/
+/* bestpath.c */
+/* in path.h */
/* conftab.c */
extern int read_builtin_tables(void);
extern int read_custom_tables(void);
--- /dev/null
+(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)"
+
+-----
--- /dev/null
+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.
--- /dev/null
+/*
+ * 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 <stdio.h>
+#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
--- /dev/null
+/*
+ * 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 <config.h>
+
+#include <stdlib.h>
+#include <string.h>
+#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 */
+
+#ifdef AS_STATS
+unsigned as_cache_tries, as_cache_hits;
+#define as_cache_try() ((void)as_cache_tries++)
+#define as_cache_hit() ((void)as_cache_hits++)
+#else
+#define as_cache_try() ((void)0)
+#define as_cache_hit() ((void)0)
+#endif
+
+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;
+#ifdef AS_STATS
+ size_t index_sz = 0;
+ unsigned index_nb = 0, paths_nb = 0, paths = 0;
+#define stats_index(sz) ((void)(index_sz += (sz), index_nb++))
+#else
+#define stats_index(sz) ((void)0)
+#endif
+
+ /* 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 */
+#ifdef AS_STATS
+ {
+ struct as_path *pp;
+ for (pp = to->path; pp; pp = pp->next)
+ paths_nb++;
+ paths++;
+ }
+#endif
+ as_free_path(to->path);
+ /* Free this node */
+ free(to);
+ stats_index(sizeof(*to));
+ }
+ }
+ /* Now, free the list of lists */
+ free(from->tolist);
+ stats_index(WORLD_Y * sizeof(*from->tolist));
+ /* Save the next pointer */
+ from2 = from->next;
+ /* now, free this from node */
+ free(from);
+ stats_index(sizeof(*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));
+ stats_index(WORLD_Y * sizeof(*fromhead));
+#ifdef AS_STATS
+ fprintf(stderr, "as_cache %u searches, %u hits, %u entries,"
+ " index %zu bytes %u blocks, paths %zu bytes %u blocks\n",
+ as_cache_tries, as_cache_hits,
+ paths,
+ index_sz, index_nb,
+ paths_nb * sizeof(struct as_path), paths_nb);
+ as_cache_hits = as_cache_tries = 0;
+#endif
+}
+
+struct as_path *
+as_find_cachepath(coord fx, coord fy, coord tx, coord ty)
+{
+ struct as_frompath *from;
+ struct as_topath *to;
+
+ as_cache_try();
+ /* 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) {
+ as_cache_hit();
+ return to->path;
+ }
+ }
+ }
+ }
+ return NULL;
+}
--- /dev/null
+/*
+ * 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 <config.h>
+
+#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;
+}
--- /dev/null
+/*
+ * 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 <config.h>
+
+#include <stdlib.h>
+#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);
+}
--- /dev/null
+/*
+ * 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 <config.h>
+
+#include <stdlib.h>
+#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;
+}
--- /dev/null
+/*
+ * 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 <config.h>
+
+#include <stdlib.h>
+#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;
+ }
+}
--- /dev/null
+/*
+ * 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 <config.h>
+
+#include <stdlib.h>
+#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;
+}
--- /dev/null
+/*
+ * 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 <config.h>
+
+#include <stdlib.h>
+#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;
+}
--- /dev/null
+/*
+ * 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 <config.h>
+
+#include <stdlib.h>
+#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;
+ }
+}
--- /dev/null
+/*
+ * 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 <config.h>
+
+#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_p;
+ int total_h;
+ size_t other;
+ struct as_queue *qp;
+ struct as_path *pp;
+ 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;
+ for (i = 0, pp = adp->path; pp; pp = pp->next)
+ i++;
+ total_p = i;
+ fprintf(fp, "path length: %d\n", total_p);
+ 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, "\tpath\t%d\n", (int)(total_p * sizeof(struct as_path)));
+ fprintf(fp, "\thash ents\t%d\n",
+ (int)(total_h * sizeof(struct as_hash)));
+ other = sizeof(struct as_data);
+ other += adp->maxneighbors * sizeof(struct as_coord);
+ other += (adp->maxneighbors + 1) * sizeof(struct as_node *);
+ other += adp->hashsize * sizeof(struct as_hash *);
+ fprintf(fp, "\tother\t%d\n", (int)other);
+ fprintf(fp, "\ttotal\t%d\n",
+ (int)(total_q * sizeof(struct as_queue) +
+ total_q * sizeof(struct as_node) +
+ total_p * sizeof(struct as_path) +
+ total_h * sizeof(struct as_hash) +
+ other));
+}
--- /dev/null
+/*
+ * 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 <config.h>
+
+#include <stdlib.h>
+#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;
+}
--- /dev/null
+/*
+ * Empire - A multi-player, client/server Internet based war game.
+ * Copyright (C) 1986-2011, Dave Pare, Jeff Bailey, Thomas Ruschak,
+ * Ken Stevens, Steve McClure, Markus Armbruster
+ *
+ * Empire 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 3 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, see <http://www.gnu.org/licenses/>.
+ *
+ * ---
+ *
+ * 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.
+ *
+ * ---
+ *
+ * bestpath.c: Find the best path between sectors
+ *
+ * Known contributors to this file:
+ * Steve McClure, 1998-2000
+ * Markus Armbruster, 2006
+ */
+
+/*
+ * IMPORTANT: These routines are very selectively used in the server.
+ *
+ * "bestownedpath" is only used to determine paths for ships and planes.
+ *
+ * Callers should not be calling these directly anymore. They should use
+ * the "BestShipPath", "BestAirPath", "BestLandPath" and "BestDistPath"
+ * functions. Note that those last two use the A* algorithms to find
+ * information.
+ */
+
+#include <config.h>
+
+#include "file.h"
+#include "misc.h"
+#include "nat.h"
+#include "optlist.h"
+#include "path.h"
+#include "prototypes.h"
+#include "sect.h"
+#include "xy.h"
+
+static int owned_and_navigable(char *, int, int, int);
+
+#define MAXROUTE 100
+#define valid(x,y) ((((x) ^ (y)) & 1) == 0)
+
+/*
+ * Ok, note that here we malloc some buffers. BUT, we never
+ * free them. Why, you may ask? Because we want to allocate
+ * them based on world size which is now (or soon to be) dynamic,
+ * but we don't want to allocate each and every time, since that
+ * would be slow. And, since world size only changes at init
+ * time, we can do this safely.
+ */
+static unsigned short *mapbuf;
+static unsigned short **mapindex;
+
+/*
+ * Find passable path from X, Y to EX, EY for nation OWN.
+ * BPATH is a buffer capable of holding at least MAXROUTE characters.
+ * If BIGMAP is null, all sectors are passable (useful for flying).
+ * Else it is taken to be a bmap.
+ * Sectors owned by or allied to OWN are then passable according to
+ * the usual rules.
+ * Other sectors are assumed to be passable when BIGMAP shows '.' or
+ * nothing.
+ * Return a path if found, else a null pointer.
+ * Wart: the path isn't terminated with 'h', except when if X,Y equals
+ * EX,EY.
+ */
+char *
+bestownedpath(char *bpath, char *bigmap,
+ int x, int y, int ex, int ey, int own)
+{
+ int i, j, tx, ty, markedsectors;
+ int minx, maxx, miny, maxy, scanx, scany;
+ unsigned routelen;
+
+ if (!mapbuf)
+ mapbuf = malloc(WORLD_X * WORLD_Y * sizeof(*mapbuf));
+ if (!mapbuf)
+ return NULL;
+ if (!mapindex) {
+ mapindex = malloc(WORLD_X * sizeof(*mapindex));
+ if (mapindex) {
+ /* Setup the map pointers */
+ for (i = 0; i < WORLD_X; i++)
+ mapindex[i] = &mapbuf[WORLD_Y * i];
+ }
+ }
+ if (!mapindex)
+ return NULL;
+
+ x = XNORM(x);
+ y = YNORM(y);
+ ex = XNORM(ex);
+ ey = YNORM(ey);
+
+ if (x == ex && y == ey)
+ return "h";
+
+ if (!valid(x, y) || !valid(ex, ey))
+ return NULL;
+ if (!owned_and_navigable(bigmap, ex, ey, own))
+ return NULL;
+
+ for (i = 0; i < WORLD_X; i++)
+ for (j = 0; j < WORLD_Y; j++)
+ mapindex[i][j] = 0xFFFF; /* clear the workspace */
+
+ routelen = 0; /* path length is now 0 */
+ mapindex[x][y] = 0; /* mark starting spot */
+ minx = x - 2; /* set X scan bounds */
+ maxx = x + 2;
+ miny = y - 1; /* set Y scan bounds */
+ maxy = y + 1;
+
+ do {
+ if (++routelen == MAXROUTE)
+ return NULL;
+ markedsectors = 0;
+ for (scanx = minx; scanx <= maxx; scanx++) {
+ x = XNORM(scanx);
+ for (scany = miny; scany <= maxy; scany++) {
+ y = YNORM(scany);
+ if (!valid(x, y))
+ continue;
+ if (((mapindex[x][y] & 0x1FFF) == routelen - 1)) {
+ for (i = DIR_FIRST; i <= DIR_LAST; i++) {
+ tx = x + diroff[i][0];
+ ty = y + diroff[i][1];
+ tx = XNORM(tx);
+ ty = YNORM(ty);
+ if (mapindex[tx][ty] == 0xFFFF) {
+ if (owned_and_navigable(bigmap, tx, ty, own)) {
+ if (CANT_HAPPEN(i < DIR_FIRST || i > DIR_LAST))
+ i = DIR_STOP;
+ mapindex[tx][ty] =
+ ((i - DIR_FIRST + 1) << 13) + routelen;
+ markedsectors++;
+ }
+ }
+ if (tx == ex && ty == ey) {
+ bpath[routelen] = 0;
+ while (routelen--) {
+ i = (mapindex[tx][ty] >> 13)
+ - 1 + DIR_FIRST;
+ bpath[routelen] = dirch[i];
+ tx = tx - diroff[i][0];
+ ty = ty - diroff[i][1];
+ tx = XNORM(tx);
+ ty = YNORM(ty);
+ }
+ return bpath;
+ }
+ }
+ }
+ }
+ }
+ miny--;
+ maxy++;
+ minx -= 2;
+ maxx += 2;
+ } while (markedsectors);
+
+ return NULL; /* no route possible */
+}
+
+/*
+ * Return non-zero if sector X, Y is passable.
+ * If BIGMAP is null, all sectors are passable (useful for flying).
+ * Else it is taken to be a bmap.
+ * Sectors owned by or allied to OWN are checked according to the
+ * usual rules, and the result is correct.
+ * Other sectors are assumed to be passable when BIGMAP shows '.' or
+ * nothing.
+ */
+static int
+owned_and_navigable(char *bigmap, int x, int y, int own)
+{
+ char mapspot;
+ struct sctstr sect;
+
+ if (!bigmap)
+ return 1;
+
+ /* Owned or allied sector? Check the real sector. */
+ getsect(x, y, §);
+ if (sect.sct_own && relations_with(sect.sct_own, own) == ALLIED) {
+ /* FIXME duplicates shp_check_nav() logic */
+ switch (dchr[sect.sct_type].d_nav) {
+ case NAVOK:
+ return 1;
+ case NAV_CANAL:
+ /* FIXME return 1 when all ships have M_CANAL */
+ return 0;
+ case NAV_02:
+ return sect.sct_effic >= 2;
+ case NAV_60:
+ return sect.sct_effic >= 60;
+ default:
+ return 0;
+ }
+ }
+
+ /* Can only check bigmap */
+ mapspot = bigmap[sect.sct_uid];
+ return mapspot == '.' || mapspot == ' ' || mapspot == 0;
+}
* 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 <config.h>
#include <string.h>
+#include "../as/as.h"
#include "file.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,
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 */
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
}
+#ifdef USE_PATH_FIND
static int
distcmp(const void *p, const void *q)
{
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 */
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 */
}