Okay, I guess I'm responsible for getting this party started.
Our autopilot algorithm needs to return two pieces of information, a flight
path (since the game needs to draw it) and a travel time. The inputs it needs
are the explored area of the map, the speed of the ship, the number of movement
points it has left during the current turn, the starting point, and the
destination.
For the purposes of this computation, there are six different types of map
squares:
1. Owned planets -- docking a ship at a planet, or launching from one, takes
ZERO movement. Any smart autopilot should take advantage of this. Note that
it doesn't matter if the planet is temporarily impassable due to having 10
ships -- you can launch one of those ten ships, move our protagonist through,
then dock that launched ship. You can only launch into ordinary space, though.
There is a boundary case involving a destination planet stocked with 10 ships
and surrounded entirely by asteroids and other launch preventers, where the
destination is effectively a pure obstacle, but the algorithm below handles
that case in an acceptable manner by default.
2. Explored ordinary space (empty, or with friendly ships)
3. Explored anomalies (in the sense that you can see it on the map, not that
it has already been harvested), if we're moving a survey ship. The only
difference between an anomaly square and explored ordinary space is that you
can't launch into it.
4. Explored asteroids -- ends movement for the current turn, and reduces
movement allowance to one next turn.
5. Explored pure obstacles (enemy ships, unowned planets, anomalies if
we aren't moving a survey ship)
6. Unexplored space. Though unexplored stars and planets that are visible on
the minimap should probably be treated as explored pure obstacles.
Let's assume this information is provided to us in a straightforward
two-dimensional array.
There are two sets of clearly subjective decisions to be made. The first deals
with unexplored space. I'll break this down into two cases:
1. The destination is explored and there is at least one valid explored path,
but it's possible that a path passing through unexplored space may be shorter
than all paths passing through explored space. Well, tough luck, if you want a
friggin' autopilot to take full advantage of a strategic batch of space,
explore it already! All unexplored space will be treated the same way as
explored pure obstacles.
2. All paths must pass through unexplored space. (Either the destination
itself is in an unexplored area, or a ship passed through a wormhole at some
point, or a line of enemy ships is blocking all the normally available explored
paths.) Then provisionally assume all unexplored space is explored ordinary
space, and chart some minimal path under that assumption.
The second deals with the issue of how the function should behave if there is
provably no path from the origin to the destination under the standard
assumptions (either the destination itself is an obstacle, or it is surrounded
by them). My choice is to treat a pure obstacle destination square as if it's
explored ordinary space (this simplifies the case of moving a colony ship to
its target planet, among other things), and to return an error value if there
is an impenetrable obstacle barrier between the origin and the destination.
The rest of this problem can be exhaustively solved, given enough computation
time. That is the sort of solution (breadth-first search) I'll present here.
As a result, I expect this solution to be too slow to be used by the game (A*
is more commonly used in the game industry for a reason...), but we've got to
start somewhere, right? Then some Stardock guy or gal can point out how many
times faster they need the algorithm to be sped up, and we can look for good
optimizations and some speed/accuracy tradeoffs.
I'll write this in C (using some common library functions), since that's the
programming language this dinosaur is most familiar with. Warning: no attempt
has been made to compile this yet, and I've only written one or two fairly
short programs in the last 2.5 years. But hopefully this is at least concrete
enough to build off of.
enum {MAXMAPHEIGHT = 242};
enum {MAXMAPWIDTH = 242};
enum {MAXPATHLENGTH = 28681};
enum {MAXMAPSQUARES = 57600};
enum {TIEBREAKBITS = 11};
enum {NUMDIRECTIONS = 8};
int dirX[NUMDIRECTIONS] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dirY[NUMDIRECTIONS] = {-1, -1, -1, 0, 0, 1, 1, 1};
enum {PLANET = 1, SPACE, ANOMALY, ASTEROID, OBSTACLE, UNEXPLORED};
int Autopilot (int mapHeight, mapWidth, map[MAXMAPHEIGHT][MAXMAPWIDTH],
maxMove, curMove,
origX, origY, destX, destY,
pathX[MAXPATHLENGTH], pathY[MAXPATHLENGTH],
int* pFlightTime) {
/* map is a mapHeight by mapWidth zero-based array filled with integers from 1
to 6, according to the six types of map squares. The boundary of the
map is assumed to be filled with 5's, to avoid array overflow errors.
maxMove is the ship's total movement allowance, curMove is the number of
moves left this turn. This information is necessary to handle asteroids
optimally.
origX and origY are the X- and Y- coordinates of the origin, ditto for
destX and destY for the destination. We assume that the origin and
destination aren't identical.
pathX and pathY are zero-based arrays where the function returns the X- and
Y- coordinates of the path, backwards. pathX[0] is set to destX,
pathY[0] is always destY.
*pFlightTime is the rounded number of TENTHS OF weeks of travel time. E.g.
if we want the shell to display 3.2 wks, we set *pFlightTime = 32.
The function return value is 0 if no path was found, otherwise it is the
length of the path, in the sense that pathX[return value] = startX,
pathY[return value] = startY. (Thus, it is actually one less than the
number of elements stored in each path array.)
*/
unsigned int dist[MAXMAPHEIGHT][MAXMAPWIDTH];
int prevX[MAXMAPHEIGHT][MAXMAPWIDTH], prevY[MAXMAPHEIGHT][MAXMAPWIDTH],
curX[MAXMAPSQUARES], curY[MAXMAPSQUARES], curCount,
nextX[MAXMAPSQUARES], nextY[MAXMAPSQUARES], nextCount,
astX[MAXMAPSQUARES], astY[MAXMAPSQUARES], astStart, astMid, astEnd,
curDist, nextAstNum,
explore,
i, j, k, m, n, p, q;
/* dist keeps track of the minimum number of movement units needed to get from
the designated map square to the origin. The most significant 21 bits
store the actual movement count, the least significant 11 bits store the
number of zero-movement opportunities used for tiebreaking purposes.
prevX and prevY are arrays that store the last step of a shortest path from
the origin to the designated map square. They allow reconstruction of a
full shortest path.
curX and curY are queues of X/Y coordinates of map squares to be
investigated soon. curCount keeps track of the length of the queue.
nextX and nextY are queues of X/Y coordinates of ordinary space or anomaly
map squares to be investigated after the curX/curY queues are cleared.
nextCount keeps track of length.
astX and astY is a "rotating" queue of asteroid map squares to be
investigated, indexed by astStart and astEnd. Elements from astStart to
(astMid - 1) inclusive correspond to squares you can escape from this
turn, astMid to (astEnd - 1) inclusive correspond to squares you have to
wait til next turn to escape from.
curDist keeps track of the current movement radius. nextAstNum keeps track
of the next movement radius which may involve getting unstuck from an
asteroid.
explore is a flag that, if set, indicates that unexplored space should be
treated as explored ordinary space.
i, j, k, m, n, p, and q are general-purpose indices.
*/
memset (dist, 0x7F, sizeof(dist));
/* no need to initialize subDist */
dist[startY][startX] = 0;
curX[0] = origX;
curY[0] = origY;
curCount = 1;
astStart = astMid = astEnd = 0;
if (curMove == 0) {
nextAstNum = maxMove - 1;
} else {
nextAstNum = curMove - 1;
}
curDist = 0;
/* if it isn't okay to change the map array, then make a local copy, or
check all squares surrounding the destination for arrival on every
iteration of the main while loop. */
if (map[destY][destX] == OBSTACLE) {
map[destY][destX] = SPACE;
}
for (explore = 0; explore < 2; explore++) {
while (curCount != 0) {
nextCount = 0;
for (i = 0; i < curCount; i++) {
j = nextX[i];
k = nextY[i];
if (map[k][j] == PLANET) {
q = dist[k][j] + 1;
for (m = 0; m < NUMDIRECTIONS; m++) {
n = j + dirX[m];
p = k + dirY[m];
/* there will never be unexplored space next to an owned planet */
if (map[p][n] == SPACE) {
if (dist[p][n] > q) {
if (dist[p][n] == 0x7F7F7F7F) {
curX[curCount] = n;
curY[curCount] = p;
curCount++;
}
dist[p][n] = q;
prevX[p][n] = j;
prevY[p][n] = k;
}
}
}
} else {
for (m = 0; m < NUMDIRECTIONS; m++) {
n = j + dirX[m];
p = k + dirY[m];
q = dist[k][j];
if (dist[p][n] > (q + 1)) {
if (map[p][n] == PLANET) {
if (dist[p][n] == 0x7F7F7F7F) {
curX[curCount] = n;
curY[curCount] = p;
curCount++;
}
dist[p][n] = q + 1;
prevX[p][n] = j;
prevY[p][n] = k;
} else if (map[p][n] < ASTEROID) {
q += (1 << TIEBREAKBITS);
if (dist[p][n] > q) {
if (dist[p][n] == 0x7F7F7F7F) {
nextX[nextCount] = n;
nextY[nextCount] = p;
nextCount++;
}
dist[p][n] = q;
prevX[p][n] = j;
prevY[p][n] = k;
}
} else if (map[p][n] == ASTEROID) {
q = ((nextAstNum + maxMove) << TIEBREAKBITS) |
(q & ((1 << TIEBREAKBITS) - 1));
if (dist[p][n] > q) {
if (dist[p][n] == 0x7F7F7F7F) {
astX[astEnd] = n;
astY[astEnd] = p;
astEnd++;
}
dist[p][n] = q;
prevX[p][n] = j;
prevY[p][n] = k;
}
}
}
}
}
}
if (dist[destY][destX] != 0x7F7F7F7F) {
pathX[0] = i = destX;
pathY[0] = j = destY;
k = 0;
while ((i != startX) || (j != startY)) {
k++;
pathX[k] = prevX[j][i];
pathY[k] = prevY[j][i];
i = pathX[k];
j = pathY[k];
}
*pFlightTime = ((curDist * 20) + maxMove) / (maxMove * 2);
return k;
}
if (nextAstNum == curDist) {
nextAstNum += maxMove;
}
memcpy (curX, nextX, nextCount * sizeof(int));
memcpy (curY, nextY, nextCount * sizeof(int));
curCount = nextCount;
if (nextAstNum == curDist + 1) {
i = (astMid - astStart) * sizeof(int);
if (i != 0) {
memcpy (&(curX[curCount]), &(astX[astStart]), i);
memcpy (&(curY[curCount]), &(astY[astStart]), i);
curCount += i;
astStart = astMid;
}
astMid = astEnd;
}
curDist++;
}
/* if it isn't okay to change the map array, then change the (map[p][n] <
ASTEROID) check in the main loop */
if (!explore) {
i = mapHeight - 1;
j = mapWidth - 1;
for (k = 1; k < i; k++) {
for (m = 1; m < j; m++) {
if (map[k][m] == UNEXPLORED) {
map[k][m] = SPACE;
}
}
}
}
}
return 0;
}
