// ____ _ __ // / __ )____ _____ | | / /___ ___________ // / __ / __ \/ ___/ | | /| / / __ `/ ___/ ___/ // / /_/ / /_/ (__ ) | |/ |/ / /_/ / / (__ ) // /_____/\____/____/ |__/|__/\__,_/_/ /____/ // // A futuristic real-time strategy game. // This file is part of Bos Wars. // /**@name ai_building.cpp - AI building functions. */ // // (c) Copyright 2001-2009 by Lutz Sammer // // 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 #include #include "stratagus.h" #include "unit.h" #include "unittype.h" #include "map.h" #include "pathfinder.h" #include "ai_local.h" #include "player.h" /*---------------------------------------------------------------------------- -- Types ----------------------------------------------------------------------------*/ enum { AiBuildingPlaceTried = 0x01, // tried to place a building there AiBuildingPlaceBlock = 0x02, // worker cannot walk there AiBuildingPlaceWalked = 0x04, // worker can walk there AiBuildingPlaceEdge = 0x62 // = 98, which InitMatrix uses }; /*---------------------------------------------------------------------------- -- Functions ----------------------------------------------------------------------------*/ /** ** Check if the surroundings are free. Depending on the value of flag, it will check: ** 0: the building will not block any way ** 1: all surrounding is free ** ** @param worker Worker to build. ** @param type Type of building. ** @param x X map tile position for the building. ** @param y Y map tile position for the building. ** @param backupok Location can be used as a backup ** ** @return True if the surrounding is free, false otherwise. ** ** @note Can be faster written. */ static int AiCheckSurrounding(const CUnit *worker, const CUnitType *type, int x, int y, bool &backupok) { static int dirs[5][2] = {{1,0},{0,1},{-1,0},{0,-1},{0,0}}; int surrounding[1024]; // Max circumference for building int surroundingnb; int x0, y0, x1, y1; int i; int lastval; int dir; int obstacle; x0 = x - 1; y0 = y - 1; x1 = x0 + type->TileWidth + 1; y1 = y0 + type->TileWidth + 1; x = x0; y = y0; dir = -1; surroundingnb = 0; while (dir < 4) { if (x >= 0 && x < Map.Info.MapWidth && y >= 0 && y < Map.Info.MapHeight && (Map.Field(x, y)->Flags & (MapFieldUnpassable | MapFieldBuilding)) == 0) { surrounding[surroundingnb++] = 1; } else { surrounding[surroundingnb++] = 0; } if ((x == x0 || x == x1) && (y == y0 || y == y1)) { dir++; } x += dirs[dir][0]; y += dirs[dir][1]; } lastval = surrounding[surroundingnb - 1]; obstacle = 0; for (i = 0 ; i < surroundingnb; ++i) { if (lastval && !surrounding[i]) { ++obstacle; } lastval = surrounding[i]; } if (obstacle == 0) { obstacle = !surrounding[0]; } if (!type->ShoreBuilding) { backupok = obstacle < 5; } else { // Shore building have at least 2 obstacles : sea->ground & ground->sea backupok = obstacle < 3; } return obstacle == 0; } /** ** Try to place a building in each position within a rectangle, ** except positions that have already been tried in earlier calls. ** ** @param worker Worker to build building. ** @param type Type of building. ** @param matrix Origin in a 2d array that shows which positions ** have already been tried. ** @param minx Smallest X position to try building ** @param miny Smallest Y position to try building ** @param maxx Greatest X position to try building ** @param maxy Greatest Y position to try building ** @param chosenx Pointer for good X position returned. ** @param choseny Pointer for good Y position returned. ** @param backupx Pointer for worse X position returned. ** @param backupx Pointer for worse Y position returned. ** ** @return True if good position found, false if not found. ** ** This function ignores TileWidth and TileHeight of the building, ** so the caller should adjust maxx and maxy accordingly. */ static inline bool AiTryBuildingPlacesRect(const CUnit *worker, const CUnitType* type, unsigned char *matrix, int mwidth, int minx, int miny, int maxx, int maxy, int *chosenx, int *choseny, int *backupx, int *backupy) { for (int y = miny; y <= maxy; y++) { for (int x = minx; x <= maxx; x++) { unsigned char *ptr = matrix + x + y * mwidth; if (!(*ptr & AiBuildingPlaceTried)) { CUnit *ontop = CanBuildUnitType(worker, type, x, y, 1); if (ontop) { bool backupok; if ((ontop != (CUnit *)1 && ontop != worker) || AiCheckSurrounding(worker, type, x, y, backupok)) { *chosenx = x; *choseny = y; return true; } else if (backupok && *backupx == -1) { *backupx = x; *backupy = y; } } *ptr |= AiBuildingPlaceTried; } // if not tried } // for x } // for y return false; } /** ** Find free building place. (flood fill version) ** ** @param worker Worker to build building. ** @param type Type of building. ** @param ox Original X position to try building ** @param oy Original Y position to try building ** @param dx Pointer for X position returned. ** @param dy Pointer for Y position returned. ** ** @return True if place found, false if no found. */ static int AiFindBuildingPlace2(const CUnit *worker, const CUnitType *type, int ox, int oy, int *dx, int *dy) { static const int xoffset[] = { 0, -1, +1, 0, -1, +1, -1, +1 }; static const int yoffset[] = { -1, 0, 0, +1, -1, -1, +1, +1 }; struct p { unsigned short X; unsigned short Y; } *points; int size; int x; int y; int rx; int ry; int mask; int wp; int rp; int ep; int i; int w; unsigned char *m; unsigned char *matrix; int backupx = -1; int backupy = -1; bool backupok; CUnit *ontop; int minoffx; int minoffy; int maxoffx; int maxoffy; size = Map.Info.MapWidth * Map.Info.MapHeight / 4; points = new p[size]; x = ox; y = oy; // // Look if we can build at current place. // if ((ontop = CanBuildUnitType(worker, type, x, y, 1))) { if ((ontop != (CUnit *)1 && ontop != worker) || AiCheckSurrounding(worker, type, x, y, backupok)) { *dx = x; *dy = y; delete[] points; return 1; } else if (backupok) { backupx = x; backupy = y; } } // // Make movement matrix. // matrix = CreateMatrix(); w = Map.Info.MapWidth + 2; mask = worker->Type->MovementMask; // Ignore all possible mobile units. mask &= ~(MapFieldLandUnit | MapFieldAirUnit | MapFieldSeaUnit); points[0].X = x; points[0].Y = y; // also use the bottom right if ((type->TileWidth > 1 || type->TileHeight > 1) && x + type->TileWidth - 1 < Map.Info.MapWidth && y + type->TileHeight - 1 < Map.Info.MapHeight) { points[1].X = x + type->TileWidth - 1; points[1].Y = y + type->TileHeight - 1; ep = wp = 2; // start with two points } else { ep = wp = 1; // start with one point } matrix += w + w + 2; rp = 0; matrix[x + y * w] = 1; // mark start point if (mask & ~type->MovementMask || !type->BuildingRules.empty()) { // The worker cannot move to some types of tiles where // the building can be built. For example, the worker // can only walk on land and the building needs to be // built in water. // // Or, the building type has some BuildingRules. // Some of them might be BuildRestrictionOnTop, // which implies there already is a building that // would block the worker. minoffx = -type->TileWidth; minoffy = -type->TileHeight; maxoffx = 1; maxoffy = 1; } else { minoffx = 0; minoffy = 0; maxoffx = 0; maxoffy = 0; } // // Pop a point from stack, push all neighbours which could be entered. // for (;;) { while (rp != ep) { rx = points[rp].X; ry = points[rp].Y; for (i = 0; i < 8; ++i) { // mark all neighbors x = rx + xoffset[i]; y = ry + yoffset[i]; m = matrix + x + y * w; if (*m & (AiBuildingPlaceWalked | AiBuildingPlaceBlock)) { // already checked continue; } if (!CanMoveToMask(x, y, mask)) { // unreachable *m |= AiBuildingPlaceBlock; continue; } // // Look if we can build here and no enemies nearby. // if (!AiEnemyUnitsInDistance(worker->Player, NULL, x, y, 8) && AiTryBuildingPlacesRect( worker, type, matrix, w, std::max(x + minoffx, 0), std::max(y + minoffy, 0), std::min(x + maxoffx, Map.Info.MapWidth - type->TileWidth), std::min(y + maxoffy, Map.Info.MapHeight - type->TileHeight), dx, dy, &backupx, &backupy)) { delete[] points; return 1; } *m |= AiBuildingPlaceWalked; points[wp].X = x; // push the point points[wp].Y = y; if (++wp >= size) { // round about wp = 0; } } // for i if (++rp >= size) { // round about rp = 0; } } // // Continue with next frame. // if (rp == wp) { // unreachable, no more points available break; } ep = wp; } delete[] points; if (backupx != -1) { *dx = backupx; *dy = backupy; return 1; } return 0; } /** ** Find free building place. ** ** @param worker Worker to build building. ** @param type Type of building. ** @param dx Pointer for X position returned. ** @param dy Pointer for Y position returned. ** ** @return True if place found, false if no found. ** ** @todo Better and faster way to find building place of oil ** platforms Special routines for special buildings. */ int AiFindBuildingPlace(const CUnit *worker, const CUnitType *type, int *dx, int *dy) { DebugPrint("Want to build a %s(%s)\n" _C_ type->Ident.c_str() _C_ type->Name.c_str()); return AiFindBuildingPlace2(worker, type, worker->X, worker->Y, dx, dy); } //@}