This patch introduces the (currently unused) function bool
fpathCheck(Vector2i, Vector2i) that checks whether a path is
theoretically possible in O(1) time. It does this by doing lookups a
pre-calculated continents table that is created on map load using a
non-recursive flood fill algorithm. It is intended to be used in the
AI scripts to avoid attempting to send units where they cannot
possibly go, like sending tracked droids over water to another
continent. I am not sure how to add new script functions, so I'll need
some help with that from someone else.
Please give feedback. Sending it directly to the list since the
trac->list gateway is apparently down.
- Per
Index: src/display.c
===================================================================
--- src/display.c (revision 6596)
+++ src/display.c (working copy)
@@ -2192,14 +2192,14 @@
audio_PlayTrack( ID_SOUND_SELECT );
}
- if(godMode && (mouseTileX >= 0) && (mouseTileX < (SDWORD)mapWidth) &&
- (mouseTileY >= 0) && (mouseTileY < (SDWORD)mapHeight))
+ if (getDebugMappingStatus() && tileOnMap(mouseTileX, mouseTileY))
{
- DBCONPRINTF(ConsoleString,(ConsoleString,"Tile Coords : %d,%d (%d,%d)", mouseTileX,mouseTileY,
- mouseTileX*TILE_UNITS + TILE_UNITS/2, mouseTileY*TILE_UNITS + TILE_UNITS/2));
+ MAPTILE *psTile = mapTile(mouseTileX, mouseTileY);
+
+ DBCONPRINTF(ConsoleString, (ConsoleString, "Tile Coords : %d, %d [%d, %d] continent(l%d, h%d)",
+ mouseTileX, mouseTileY, world_coord(mouseTileX), world_coord(mouseTileY),
+ (int)psTile->limitedContinent, (int)psTile->hoverContinent));
}
-
- //addConsoleMessage("Droid ordered to new location",DEFAULT_JUSTIFY,SYSTEM_MESSAGE);
}
driveDisableTactical();
Index: src/map.c
===================================================================
--- src/map.c (revision 6596)
+++ src/map.c (working copy)
@@ -50,6 +50,12 @@
#include "fpath.h"
#include "levels.h"
+struct ffnode
+{
+ struct ffnode *next;
+ int x, y;
+};
+
//scroll min and max values
SDWORD scrollMinX, scrollMaxX, scrollMinY, scrollMaxY;
@@ -301,6 +307,9 @@
scrollMaxX = mapWidth;
scrollMaxY = mapHeight;
+ /* Set continents. This should ideally be done in advance by the map editor. */
+ mapFloodFillContinents();
+
return true;
}
@@ -1546,3 +1555,125 @@
fprintf(stdout, "\tMap self-test: PASSED\n");
}
+
+// Convert a direction into an offset.
+// dir 0 => x = 0, y = -1
+#define NUM_DIR 8
+static const Vector2i aDirOffset[NUM_DIR] =
+{
+ { 0, 1},
+ {-1, 1},
+ {-1, 0},
+ {-1,-1},
+ { 0,-1},
+ { 1,-1},
+ { 1, 0},
+ { 1, 1},
+};
+
+// Flood fill a "continent". Note that we reuse x, y inside this function.
+static void mapFloodFill(int x, int y, int continent, PROPULSION_TYPE propulsion)
+{
+ struct ffnode *open = NULL;
+ int i;
+
+ do
+ {
+ MAPTILE *currTile = mapTile(x, y);
+
+ // Add accessible neighbouring tiles to the open list
+ for (i = 0; i < NUM_DIR; i++)
+ {
+ // rely on the fact that all border tiles are inaccessible to avoid checking explicitly
+ Vector2i npos = { x + aDirOffset[i].x, y + aDirOffset[i].y };
+ MAPTILE *psTile;
+ bool limitedTile = (propulsion == PROPULSION_TYPE_PROPELLOR || propulsion == PROPULSION_TYPE_WHEELED);
+
+ if (!tileOnMap(npos.x, npos.y))
+ {
+ continue;
+ }
+ psTile = mapTile(npos.x, npos.y);
+
+ if (!fpathBlockingTile(x, y, propulsion) && ((limitedTile && psTile->limitedContinent == 0) || (!limitedTile && psTile->hoverContinent == 0)))
+ {
+ struct ffnode *node = malloc(sizeof(*node));
+
+ node->next = open; // add to beginning of open list
+ node->x = npos.x;
+ node->y = npos.y;
+ open = node;
+ }
+ }
+
+ // Set continent value
+ if (propulsion == PROPULSION_TYPE_PROPELLOR || propulsion == PROPULSION_TYPE_WHEELED)
+ {
+ currTile->limitedContinent = continent;
+ }
+ else
+ {
+ currTile->hoverContinent = continent;
+ }
+
+ // Pop the first open node off the list for the next iteration
+ if (open)
+ {
+ struct ffnode *tmp = open;
+
+ x = open->x;
+ y = open->y;
+ open = open->next;
+ free(tmp);
+ }
+ } while (open);
+}
+
+void mapFloodFillContinents()
+{
+ int x, y, limitedContinents = 0, hoverContinents = 0;
+
+ /* Clear continents */
+ for (x = 0; x < mapWidth; x++)
+ {
+ for (y = 0; y < mapHeight; y++)
+ {
+ MAPTILE *psTile = mapTile(x, y);
+
+ psTile->limitedContinent = 0;
+ psTile->hoverContinent = 0;
+ }
+ }
+
+ /* Iterate over the whole map, looking for unset continents */
+ for (x = 0; x < mapWidth; x++)
+ {
+ for (y = 0; y < mapHeight; y++)
+ {
+ MAPTILE *psTile = mapTile(x, y);
+
+ if (psTile->limitedContinent == 0 && !fpathBlockingTile(x, y, PROPULSION_TYPE_WHEELED))
+ {
+ mapFloodFill(x, y, limitedContinents++, PROPULSION_TYPE_WHEELED);
+ }
+ else if (psTile->limitedContinent == 0 && !fpathBlockingTile(x, y, PROPULSION_TYPE_PROPELLOR))
+ {
+ mapFloodFill(x, y, limitedContinents++, PROPULSION_TYPE_PROPELLOR);
+ }
+ }
+ }
+ debug(LOG_MAP, "Found %d limited continents", (int)limitedContinents);
+ for (x = 0; x < mapWidth; x++)
+ {
+ for (y = 0; y < mapHeight; y++)
+ {
+ MAPTILE *psTile = mapTile(x, y);
+
+ if (psTile->hoverContinent == 0 && !fpathBlockingTile(x, y, PROPULSION_TYPE_HOVER))
+ {
+ mapFloodFill(x, y, hoverContinents++, PROPULSION_TYPE_HOVER);
+ }
+ }
+ }
+ debug(LOG_MAP, "Found %d hover continents", (int)hoverContinents);
+}
Index: src/map.h
===================================================================
--- src/map.h (revision 6596)
+++ src/map.h (working copy)
@@ -90,6 +90,8 @@
float level;
BASE_OBJECT *psObject; // Any object sitting on the location (e.g. building)
PIELIGHT colour;
+ char limitedContinent; /** For land or sea limited propulsion types */
+ char hoverContinent; /** For hover type propulsions */
// TYPE_OF_TERRAIN type; // The terrain type for the tile
} MAPTILE;
@@ -347,6 +349,8 @@
//scroll min and max values
extern SDWORD scrollMinX, scrollMaxX, scrollMinY, scrollMaxY;
+void mapFloodFillContinents(void);
+
extern void mapTest(void);
#endif // __INCLUDED_SRC_MAP_H__
Index: src/fpath.c
===================================================================
--- src/fpath.c (revision 6596)
+++ src/fpath.c (working copy)
@@ -679,3 +679,31 @@
assert(firstJob == NULL);
assert(firstResult == NULL);
}
+
+bool fpathCheck(Vector2i orig, Vector2i dest, PROPULSION_TYPE propulsion)
+{
+ MAPTILE *origTile = mapTile(orig.x, orig.y);
+ MAPTILE *destTile = mapTile(dest.x, dest.y);
+
+ ASSERT(propulsion != PROPULSION_TYPE_NUM, "Bad propulsion type");
+ ASSERT(origTile != NULL && destTile != NULL, "Bad tile parameter");
+
+ switch (propulsion)
+ {
+ case PROPULSION_TYPE_PROPELLOR:
+ case PROPULSION_TYPE_WHEELED:
+ case PROPULSION_TYPE_TRACKED:
+ case PROPULSION_TYPE_LEGGED:
+ case PROPULSION_TYPE_SKI: // ?!
+ case PROPULSION_TYPE_HALF_TRACKED:
+ return origTile->limitedContinent == destTile->limitedContinent;
+ case PROPULSION_TYPE_HOVER:
+ return origTile->hoverContinent == destTile->hoverContinent;
+ case PROPULSION_TYPE_JUMP:
+ case PROPULSION_TYPE_LIFT:
+ return true; // FIXME: This is not entirely correct for all possible maps. - Per
+ case PROPULSION_TYPE_NUM:
+ break;
+ }
+ return true; // should never get here
+}
Index: src/fpath.h
===================================================================
--- src/fpath.h (revision 6596)
+++ src/fpath.h (working copy)
@@ -73,6 +73,10 @@
/** Clean up path jobs and results for a droid. Function is thread-safe. */
extern void fpathRemoveDroidData(int id);
+/** Quick O(1) test of whether it is theoretically possible to go from origin to destination
+ * using the given propulsion type. */
+bool fpathCheck(Vector2i orig, Vector2i dest, PROPULSION_TYPE propulsion);
+
/** Unit testing. */
void fpathTest(int x, int y, int x2, int y2);
_______________________________________________
Warzone-dev mailing list
Warzone-dev@gna.org
https://mail.gna.org/listinfo/warzone-dev
