2 * Empire - A multi-player, client/server Internet based war game.
3 * Copyright (C) 1986-2004, Dave Pare, Jeff Bailey, Thomas Ruschak,
4 * Ken Stevens, Steve McClure
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 * See the "LEGAL", "LICENSE", "CREDITS" and "README" files for all the
23 * related information and legal notices. It is expected that any future
24 * projects/authors will amend these files as needed.
28 * bestpath.c: Find the best path between sectors
30 * Known contributors to this file:
31 * Steve McClure, 1998-2000
35 * IMPORTANT: These routines are very selectively used in the server.
37 * "bestpath" is now obsolete (and removed)
38 * "bestownedpath" is only used to determine paths for ships and planes.
40 * Callers should not be calling these directly anymore. They should use
41 * the "BestShipPath", "BestAirPath", "BestLandPath" and "BestDistPath"
42 * functions. Note that those last two use the A* algorithms to find
54 static int owned_and_navigable(s_char *, int, int, s_char *, int);
56 #define MAXROUTE 100 /* return '?' if path longer than this */
57 #define valid(x,y) (((x^y)&1)==0)
59 /* ________________________________________________________________
61 ** bestpath(x1,y1,x2,y2,(s_char *)terrain);
63 ** Calculate routing string to get from sector [x1,y1] to sector [x2,y2]
64 ** via a specified type of terrain.
68 ** x1,y1 starting coordinates
70 ** x2,y2 destination coordinates
72 ** terrain ptr to string showing the types of sectors that
73 ** we're allowed to pass through:
75 ** A null string enables routing through any kind of
76 ** sector (useful for airplanes).
78 ** A string that begins with an 'R' ensures that
79 ** the source and destination sectors also match
80 ** the specified type of terrain.
82 ** A string that begins with a '~' (after the 'R',
83 ** if necessary) specifies that we can pass through
84 ** any kind of sector EXCEPT those in the remainder
89 ** "R~.^" all sectors along route must be
90 ** non-ocean, non-mountain
92 ** "+" all sectors between start and end
95 ** "h. " all sectors along route must be
96 ** harbor, water, or unmapped
98 ** 'bestpath' returns a pointer to a route string containing either:
100 ** yugjbn - string of normal routing characters if route possible
101 ** ? - if route is longer than MAXROUTE characters
102 ** \0 - (null string) if no route possible
103 ** h - if start and end points are the same sector
104 ** ________________________________________________________________
107 s_char *dirchar = "juygbn";
108 int dx[6] = { 2, 1, -1, -2, -1, 1 };
109 int dy[6] = { 0, -1, -1, 0, 1, 1 };
112 * Ok, note that here we malloc some buffers. BUT, we never
113 * free them. Why, you may ask? Because we want to allocate
114 * them based on world size which is now (or soon to be) dynamic,
115 * but we don't want to allocate each and every time, since that
116 * would be slow. And, since world size only changes at init
117 * time, we can do this safely.
118 * We also share these buffers between "bestpath" and "bestownedpath"
119 * since you can never be in both functions at the same time. If that
120 * did happen, we'd already be so broken that it won't matter.
122 static unsigned int *mapbuf = (unsigned int *)0;
123 static unsigned int **mapindex = (unsigned int **)0;
126 bestownedpath(s_char *bpath,
128 int x, int y, int ex, int ey, s_char *terrain, int own)
130 int i, j, tx, ty, markedsectors, restr2;
131 int minx, maxx, miny, maxy, scanx, scany;
132 unsigned int routelen;
135 mapbuf = (unsigned int *)malloc((WORLD_X * WORLD_Y) *
136 sizeof(unsigned int));
138 return ((s_char *)0);
141 (unsigned int **)malloc(WORLD_X * sizeof(unsigned int *));
143 /* Setup the map pointers */
144 for (i = 0; i < WORLD_X; i++)
145 mapindex[i] = &mapbuf[WORLD_Y * i];
149 return ((s_char *)0);
152 if (0 != (restr2 = (*terrain == 'R')))
160 if (x == ex && y == ey) {
163 return ((s_char *)bpath);
166 if (!valid(x, y) || !valid(ex, ey))
167 return ((s_char *)0);
169 if (restr2 && (!owned_and_navigable(bigmap, x, y, terrain, own) ||
170 !owned_and_navigable(bigmap, x, y, terrain, own)))
171 return ((s_char *)0);
173 for (i = 0; i < WORLD_X; i++)
174 for (j = 0; j < WORLD_Y; j++)
175 mapindex[i][j] = 0xFFFF; /* clear the workspace */
177 routelen = 0; /* path length is now 0 */
178 mapindex[x][y] = 0; /* mark starting spot */
179 markedsectors = 1; /* source sector marked */
180 minx = x - 2; /* set X scan bounds */
182 miny = y - 1; /* set Y scan bounds */
186 if (++routelen == MAXROUTE) {
189 return ((s_char *)bpath);
192 for (scanx = minx; scanx <= maxx; scanx++) {
194 for (scany = miny; scany <= maxy; scany++) {
197 if ((((mapindex[x][y]) & 0x1FFF) == (routelen - 1))) {
198 for (i = 0; i < 6; i++) {
203 if (mapindex[tx][ty] == 0xFFFF) {
204 if (owned_and_navigable(bigmap, tx, ty,
206 || (tx == ex && ty == ey && !restr2)) {
208 ((i + 1) << 13) + routelen;
212 if (tx == ex && ty == ey) {
215 i = ((mapindex[tx][ty]) >> 13) - 1;
216 bpath[routelen] = dirchar[i];
222 return ((s_char *)bpath);
233 } while (markedsectors);
236 return ((s_char *)0); /* no route possible */
239 /* return TRUE if sector is passable */
241 owned_and_navigable(s_char *map, int x, int y, s_char *terrain, int own)
245 s_char mapspot; /* What this spot on the bmap is */
250 /* No terrain to check? Everything is navigable! (this
251 probably means we are flying) */
255 /* Are we checking this map? */
257 /* Do we know what this sector is? If not, we assume it's ok,
258 since otherwise we'll never venture anywhere */
259 mapspot = map[sctoff(x, y)];
260 if (mapspot == ' ' || mapspot == 0)
263 /* Now, is it marked with a 'x' or 'X'? If so, avoid it! */
264 if (mapspot == 'x' || mapspot == 'X')
267 /* We don't know what it is since we have no map, so return ok! */
271 /* Now, check this bmap entry to see if it is one of the
286 /* We found it, so we say it's bad since we are negating */
288 } else if (!negate && !*t) {
289 /* We didn't find it, so we say it's bad since we aren't negating */
293 /* According to our bmap, this sector is ok so far. */
295 /* Ok, we made it this far. Now get the sector */
296 sect = getsectp(x, y);
297 c = dchr[sect->sct_type].d_mnem;
298 /* Ok, now, check the owner if needed */
300 if (sect->sct_own != own) {
301 rel = getrel(getnatp(sect->sct_own), own);
302 /* We can't sail through deity sectors, but we can sail
304 if (rel < FRIENDLY && sect->sct_type != SCT_WATER)
308 /* Ok, now, check these two sector types */
309 /* check for bad harbors. */
310 if (c == 'h' && sect->sct_effic < 2)
312 /* check for bad bridges */
313 if (c == '=' && sect->sct_effic < 60)
315 /* Woo-hoo, it's ok! */