// ____ _ __ // / __ )____ _____ | | / /___ ___________ // / __ / __ \/ ___/ | | /| / / __ `/ ___/ ___/ // / /_/ / /_/ (__ ) | |/ |/ / /_/ / / (__ ) // /_____/\____/____/ |__/|__/\__,_/_/ /____/ // // A futuristic real-time strategy game. // This file is part of Bos Wars. // /**@name pathfinder.cpp - The path finder routines. */ // // I use breadth-first. // // (c) Copyright 1998-2007 by Lutz Sammer, Russell Smith // // 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; only version 2 of the License. // // 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. // //@{ /*---------------------------------------------------------------------------- -- Includes ----------------------------------------------------------------------------*/ #include "stratagus.h" #include "map.h" #include "unittype.h" #include "unit.h" #include "pathfinder.h" /*---------------------------------------------------------------------------- -- Variables ----------------------------------------------------------------------------*/ /** ** The matrix is used to generated the paths. ** ** 0: Nothing must check if usable. ** 1-8: Field on the path 1->2->3->4->5... ** 88: Marks the possible goal fields. ** 98: Marks map border, for faster limits checks. */ static unsigned char Matrix[(MaxMapWidth + 2) * (MaxMapHeight + 3) + 2]; /// Path matrix static int STDCALL CostMoveTo(int x, int y, void *data); /*---------------------------------------------------------------------------- -- Functions ----------------------------------------------------------------------------*/ /** ** Init the pathfinder */ void InitPathfinder() { InitAStar(Map.Info.MapWidth, Map.Info.MapHeight, CostMoveTo); } /** ** Free the pathfinder */ void FreePathfinder() { FreeAStar(); } /** ** Initialize a matrix ** ** @note Double border for ships/flyers. ** ** 98 98 98 98 98 ** 98 98 98 98 98 ** 98 98 ** 98 98 ** 98 98 98 98 98 */ static void InitMatrix(unsigned char *matrix) { unsigned i; unsigned w; unsigned h; unsigned e; w = Map.Info.MapWidth + 2; h = Map.Info.MapHeight; i = w + w + 1; memset(matrix, 98, i); // +1 for ships! memset(matrix + i, 0, w * h); // initialize matrix for (e = i + w * h; i < e;) { // mark left and right border matrix[i] = 98; i += w; matrix[i - 1] = 98; } memset(matrix + i, 98, w + 1); // +1 for ships! } /** ** Create empty movement matrix. */ unsigned char *CreateMatrix(void) { InitMatrix(Matrix); return Matrix; } /** ** Allocate a new matrix and initialize */ unsigned char *MakeMatrix(void) { unsigned char *matrix; matrix = new unsigned char[(Map.Info.MapWidth + 2) * (Map.Info.MapHeight + 3) + 2]; InitMatrix(matrix); return matrix; } /*---------------------------------------------------------------------------- -- PATH-FINDER USE ----------------------------------------------------------------------------*/ /** ** Can the unit 'src' reach the place x,y. ** ** @param src Unit for the path. ** @param x Map X tile position. ** @param y Map Y tile position. ** @param w Width of Goal ** @param h Height of Goal ** @param minrange min range to the tile ** @param range Range to the tile. ** ** @pre The unit's field flags must have been marked ** on the map; see MarkUnitFieldFlags. ** ** @return Distance to place. */ int PlaceReachable(const CUnit *src, int x, int y, int w, int h, int minrange, int range) { // Please do not use UnmarkUnitFieldFlags and MarkUnitFieldFlags // around PlaceReachable calls. Assert((Map.Field(src->X, src->Y)->Flags & src->Type->FieldFlags) != 0); UnmarkUnitFieldFlags(src); int i = AStarFindPath(src->X, src->Y, x, y, w, h, src->Type->TileWidth, src->Type->TileHeight, minrange, range, NULL, 0, (void *)src); MarkUnitFieldFlags(src); switch (i) { case PF_FAILED: case PF_UNREACHABLE: case PF_REACHED: i = 0; break; case PF_WAIT: Assert(0); i = 0; break; case PF_MOVE: break; default: break; } return i; } /** ** Can the unit 'src' reach the unit 'dst'. ** ** @param src Unit for the path. ** @param dst Unit to be reached. ** @param range Range to unit. ** ** @pre The unit's field flags must have been marked ** on the map; see MarkUnitFieldFlags. ** ** @return Distance to place. */ int UnitReachable(const CUnit *src, const CUnit *dst, int range) { int depth; // Please do not use UnmarkUnitFieldFlags and MarkUnitFieldFlags // around UnitReachable calls. Assert((Map.Field(src->X, src->Y)->Flags & src->Type->FieldFlags) != 0); // // Find a path to the goal. // depth = PlaceReachable(src, dst->X, dst->Y, dst->Type->TileWidth, dst->Type->TileHeight, 0, range); if (depth <= 0) { return 0; } return depth; } /** ** Compute the cost of crossing tile (dx,dy) ** ** @param data The CUnit * that wants to cross the tile. This is ** passed in as void * so that the low-level A* code ** need not know about CUnit. ** @param x X tile where to move. ** @param y Y tile where to move. ** ** @pre The unit's field flags must have been unmarked ** on the map; see UnmarkUnitFieldFlags. ** ** @return -1 -> impossible to cross. ** 0 -> no induced cost, except move ** >0 -> costly tile */ static int STDCALL CostMoveTo(int x, int y, void *data) { int i; int j; int flag; int cost = 0; CUnit *goal; const CUnit *unit = (const CUnit *)data; int mask = unit->Type->MovementMask; cost = 0; // Doesn't cost anything to move to ourselves :) // Used when marking goals mainly. Could cause speed problems if (unit->X == x && unit->Y == y) { return 0; } // verify each tile of the unit. for (i = x; i < x + unit->Type->TileWidth; ++i) { for (j = y; j < y + unit->Type->TileHeight; ++j) { flag = Map.Field(i, j)->Flags & mask; if (flag && (AStarKnowUnseenTerrain || Map.IsFieldExplored(unit->Player, i, j))) { if (flag & ~(MapFieldLandUnit | MapFieldAirUnit | MapFieldSeaUnit)) { // we can't cross fixed units and other unpassable things return -1; } goal = UnitOnMapTile(i, j, unit->Type->UnitType); if (!goal) { // Shouldn't happen, mask says there is something on this tile Assert(0); return -1; } // The unit must not be blocked by itself. // Please use UnmarkUnitFieldFlags and // MarkUnitFieldFlags around pathfinder calls. Assert(goal != unit); if (goal->Moving) { // moving unit are crossable cost += AStarMovingUnitCrossingCost; } else { // for non moving unit Always Fail // FIXME: Need support for moving a fixed unit to add cost return -1; //cost += AStarFixedUnitCrossingCost; } } // Add cost of crossing unknown tiles if required if (!AStarKnowUnseenTerrain && !Map.IsFieldExplored(unit->Player, i, j)) { // Tend against unknown tiles. cost += AStarUnknownTerrainCost; } if (unit->Type->UnitType != UnitTypeFly) { // Add tile movement cost cost += Map.Field(i, j)->Cost; } } } return cost; } /*---------------------------------------------------------------------------- -- REAL PATH-FINDER ----------------------------------------------------------------------------*/ /** ** Find new path. ** ** The destination could be a unit or a field. ** Range gives how far we must reach the goal. ** ** @note The destination could become negative coordinates! ** ** @param unit Path for this unit. ** ** @pre The unit's field flags must have been unmarked ** on the map; see UnmarkUnitFieldFlags. ** ** @return >0 remaining path length, 0 wait for path, -1 ** reached goal, -2 can't reach the goal. */ int NewPath(CUnit *unit) { int i; int gw; int gh; int gx; int gy; int minrange; int maxrange; char *path; // Please use UnmarkUnitFieldFlags and MarkUnitFieldFlags // around NewPath calls. Assert((Map.Field(unit->X, unit->Y)->Flags & unit->Type->FieldFlags) == 0); if (unit->Orders[0]->Goal) { gw = unit->Orders[0]->Goal->Type->TileWidth; gh = unit->Orders[0]->Goal->Type->TileHeight; gx = unit->Orders[0]->Goal->X; gy = unit->Orders[0]->Goal->Y; maxrange = unit->Orders[0]->Range; minrange = unit->Orders[0]->MinRange; } else { // Take care of non square goals :) // If goal is non square, range states a non-existant goal rather // than a tile. gw = unit->Orders[0]->Width; gh = unit->Orders[0]->Height; maxrange = unit->Orders[0]->Range; minrange = unit->Orders[0]->MinRange; // Large units may have a goal that goes outside the map, fix it here if (unit->Orders[0]->X + unit->Type->TileWidth - 1 >= Map.Info.MapWidth) { unit->Orders[0]->X = Map.Info.MapWidth - unit->Type->TileWidth; } if (unit->Orders[0]->Y + unit->Type->TileHeight - 1 >= Map.Info.MapHeight) { unit->Orders[0]->Y = Map.Info.MapHeight - unit->Type->TileHeight; } gx = unit->Orders[0]->X; gy = unit->Orders[0]->Y; } path = unit->Data.Move.Path; i = AStarFindPath(unit->X, unit->Y, gx, gy, gw, gh, unit->Type->TileWidth, unit->Type->TileHeight, minrange, maxrange, path, MAX_PATH_LENGTH, unit); if (i == PF_FAILED) { i = PF_UNREACHABLE; } // Update path if it was requested. Otherwise we may only want // to know if there exists a path. if (path != NULL) { if (i >= MAX_PATH_LENGTH) { unit->Data.Move.Length = MAX_PATH_LENGTH; } else { unit->Data.Move.Length = i; } if (unit->Data.Move.Length == 0) { ++unit->Data.Move.Length; } } return i; } /** ** Returns the next element of a path. ** ** @param unit Unit that wants the path element. ** @param pxd Pointer for the x direction. ** @param pyd Pointer for the y direction. ** ** @pre The unit's field flags must have been unmarked ** on the map; see UnmarkUnitFieldFlags. ** ** @return >0 remaining path length, 0 wait for path, -1 ** reached goal, -2 can't reach the goal. */ int NextPathElement(CUnit *unit, int *pxd, int *pyd) { int result; // Please use UnmarkUnitFieldFlags and MarkUnitFieldFlags // around NextPathElement calls. Assert((Map.Field(unit->X, unit->Y)->Flags & unit->Type->FieldFlags) == 0); // Attempt to use path cache // FIXME: If there is a goal, it may have moved, ruining the cache *pxd = 0; *pyd = 0; // Goal has moved, need to recalculate path or no cached path if (unit->Data.Move.Length <= 0 || (unit->Orders[0]->Goal && (unit->Orders[0]->Goal->X != unit->Orders[0]->X || unit->Orders[0]->Goal->Y != unit->Orders[0]->Y))) { result = NewPath(unit); if (result == PF_UNREACHABLE) { unit->Data.Move.Length = 0; return result; } if (result == PF_REACHED) { return result; } if (unit->Goal) { // Update Orders unit->Orders[0]->X = unit->Goal->X; unit->Orders[0]->Y = unit->Goal->Y; } } *pxd = Heading2X[(int)unit->Data.Move.Path[(int)unit->Data.Move.Length - 1]]; *pyd = Heading2Y[(int)unit->Data.Move.Path[(int)unit->Data.Move.Length - 1]]; result = unit->Data.Move.Length; unit->Data.Move.Length--; if (!UnitCanBeAt(unit, *pxd + unit->X, *pyd + unit->Y)) { // If obstructing unit is moving, wait for a bit. if (unit->Data.Move.Fast) { unit->Data.Move.Fast--; AstarDebugPrint("WAIT at %d\n" _C_ unit->Data.Move.Fast); result = PF_WAIT; } else { unit->Data.Move.Fast = 10; AstarDebugPrint("SET WAIT to 10\n"); result = PF_WAIT; } if (unit->Data.Move.Fast == 0 && result != 0) { AstarDebugPrint("WAIT expired\n"); result = NewPath(unit); if (result > 0) { *pxd = Heading2X[(int)unit->Data.Move.Path[(int)unit->Data.Move.Length - 1]]; *pyd = Heading2Y[(int)unit->Data.Move.Path[(int)unit->Data.Move.Length - 1]]; if (!UnitCanBeAt(unit, *pxd + unit->X, *pyd + unit->Y)) { // There may be unit in the way, Astar may allow you to walk onto it. result = PF_UNREACHABLE; *pxd = 0; *pyd = 0; } else { result = unit->Data.Move.Length; unit->Data.Move.Length--; } } } } if (result != PF_WAIT) { unit->Data.Move.Fast = 0; } return result; } //@}