2 * Empire - A multi-player, client/server Internet based war game.
3 * Copyright (C) 1986-2008, 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 files README, COPYING and CREDITS in the root of the source
23 * tree for related information and legal notices. It is expected
24 * that future 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
32 * Markus Armbruster, 2006
36 * IMPORTANT: These routines are very selectively used in the server.
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
53 #include "prototypes.h"
57 static int owned_and_navigable(char *, int, int, int);
60 #define valid(x,y) ((((x) ^ (y)) & 1) == 0)
63 * Ok, note that here we malloc some buffers. BUT, we never
64 * free them. Why, you may ask? Because we want to allocate
65 * them based on world size which is now (or soon to be) dynamic,
66 * but we don't want to allocate each and every time, since that
67 * would be slow. And, since world size only changes at init
68 * time, we can do this safely.
70 static unsigned short *mapbuf;
71 static unsigned short **mapindex;
74 * Find passable path from X, Y to EX, EY for nation OWN.
75 * BPATH is a buffer capable of holding at least MAXROUTE characters.
76 * If BIGMAP is null, all sectors are passable (useful for flying).
77 * Else it is taken to be a bmap.
78 * Sectors owned by or allied to OWN are then passable according to
80 * Other sectors are assumed to be passable when BIGMAP shows '.' or
82 * Return a path if found, else a null pointer.
83 * Wart: the path isn't terminated with 'h', except when if X,Y equals
87 bestownedpath(char *bpath, char *bigmap,
88 int x, int y, int ex, int ey, int own)
90 int i, j, tx, ty, markedsectors;
91 int minx, maxx, miny, maxy, scanx, scany;
95 mapbuf = malloc(WORLD_X * WORLD_Y * sizeof(*mapbuf));
99 mapindex = malloc(WORLD_X * sizeof(*mapindex));
101 /* Setup the map pointers */
102 for (i = 0; i < WORLD_X; i++)
103 mapindex[i] = &mapbuf[WORLD_Y * i];
114 if (x == ex && y == ey)
117 if (!valid(x, y) || !valid(ex, ey))
119 if (!owned_and_navigable(bigmap, ex, ey, own))
122 for (i = 0; i < WORLD_X; i++)
123 for (j = 0; j < WORLD_Y; j++)
124 mapindex[i][j] = 0xFFFF; /* clear the workspace */
126 routelen = 0; /* path length is now 0 */
127 mapindex[x][y] = 0; /* mark starting spot */
128 markedsectors = 1; /* source sector marked */
129 minx = x - 2; /* set X scan bounds */
131 miny = y - 1; /* set Y scan bounds */
135 if (++routelen == MAXROUTE)
138 for (scanx = minx; scanx <= maxx; scanx++) {
140 for (scany = miny; scany <= maxy; scany++) {
144 if (((mapindex[x][y] & 0x1FFF) == routelen - 1)) {
145 for (i = DIR_FIRST; i <= DIR_LAST; i++) {
146 tx = x + diroff[i][0];
147 ty = y + diroff[i][1];
150 if (mapindex[tx][ty] == 0xFFFF) {
151 if (owned_and_navigable(bigmap, tx, ty, own)) {
152 if (CANT_HAPPEN(i < DIR_FIRST || i > DIR_LAST))
155 ((i - DIR_FIRST + 1) << 13) + routelen;
159 if (tx == ex && ty == ey) {
162 i = (mapindex[tx][ty] >> 13)
164 bpath[routelen] = dirch[i];
165 tx = tx - diroff[i][0];
166 ty = ty - diroff[i][1];
180 } while (markedsectors);
182 return NULL; /* no route possible */
186 * Return non-zero if sector X, Y is passable.
187 * If BIGMAP is null, all sectors are passable (useful for flying).
188 * Else it is taken to be a bmap.
189 * Sectors owned by or allied to OWN are checked according to the
190 * usual rules, and the result is correct.
191 * Other sectors are assumed to be passable when BIGMAP shows '.' or
195 owned_and_navigable(char *bigmap, int x, int y, int own)
203 /* Owned or allied sector? Check the real sector. */
204 getsect(x, y, §);
205 if (sect.sct_own == own
206 || (sect.sct_own && getrel(getnatp(sect.sct_own), own) == ALLIED)) {
207 /* FIXME duplicates shp_check_nav() logic */
208 switch (dchr[sect.sct_type].d_nav) {
212 /* FIXME return 1 when all ships have M_CANAL */
215 return sect.sct_effic >= 2;
217 return sect.sct_effic >= 60;
223 /* Can only check bigmap */
224 mapspot = bigmap[sect.sct_uid];
225 return mapspot == '.' || mapspot == ' ' || mapspot == 0;