From: <si...@us...> - 2010-01-25 06:23:38
|
Revision: 438 http://glestae.svn.sourceforge.net/glestae/?rev=438&view=rev Author: silnarm Date: 2010-01-25 06:23:30 +0000 (Mon, 25 Jan 2010) Log Message: ----------- the rest of the search_engine branch .. ?? Added Paths: ----------- branches/0.2.x/data/game/data/core/misc_textures/g04.bmp branches/0.2.x/data/game/data/core/misc_textures/g05.bmp branches/0.2.x/data/game/data/core/misc_textures/g06.bmp branches/0.2.x/data/game/data/core/misc_textures/g07.bmp branches/0.2.x/data/game/data/core/misc_textures/l04.bmp branches/0.2.x/data/game/data/core/misc_textures/l05.bmp branches/0.2.x/data/game/data/core/misc_textures/l06.bmp branches/0.2.x/data/game/data/core/misc_textures/l07.bmp branches/0.2.x/source/game/path_finder/cartographer.cpp branches/0.2.x/source/game/path_finder/cartographer.h branches/0.2.x/source/game/path_finder/cluster_map.cpp branches/0.2.x/source/game/path_finder/cluster_map.h branches/0.2.x/source/game/path_finder/influence_map.cpp branches/0.2.x/source/game/path_finder/influence_map.h branches/0.2.x/source/game/path_finder/node_map.cpp branches/0.2.x/source/game/path_finder/node_map.h branches/0.2.x/source/game/path_finder/node_pool.cpp branches/0.2.x/source/game/path_finder/node_pool.h branches/0.2.x/source/game/path_finder/route_planner.cpp branches/0.2.x/source/game/path_finder/route_planner.h branches/0.2.x/source/game/path_finder/search_engine.h branches/0.2.x/source/game/path_finder/search_functions.inl Removed Paths: ------------- branches/0.2.x/data/game/data/core/misc_textures/g04.bmp branches/0.2.x/data/game/data/core/misc_textures/g05.bmp branches/0.2.x/data/game/data/core/misc_textures/g06.bmp branches/0.2.x/data/game/data/core/misc_textures/g07.bmp branches/0.2.x/data/game/data/core/misc_textures/l04.bmp branches/0.2.x/data/game/data/core/misc_textures/l05.bmp branches/0.2.x/data/game/data/core/misc_textures/l06.bmp branches/0.2.x/data/game/data/core/misc_textures/l07.bmp Property Changed: ---------------- branches/0.2.x/ Property changes on: branches/0.2.x ___________________________________________________________________ Modified: svn:mergeinfo - /branches/0.2.12:314-343 /branches/merge_3.2.2:57-99 /branches/pathfinder:157-380 /branches/search_engine:380-436 /trunk:358,364-366 + /branches/0.2.12:314-343 /branches/merge_3.2.2:57-99 /branches/pathfinder:157-380 /branches/search_engine:380-437 /trunk:358,364-366 Deleted: branches/0.2.x/data/game/data/core/misc_textures/g04.bmp =================================================================== (Binary files differ) Copied: branches/0.2.x/data/game/data/core/misc_textures/g04.bmp (from rev 437, branches/search_engine/data/game/data/core/misc_textures/g04.bmp) =================================================================== (Binary files differ) Deleted: branches/0.2.x/data/game/data/core/misc_textures/g05.bmp =================================================================== (Binary files differ) Copied: branches/0.2.x/data/game/data/core/misc_textures/g05.bmp (from rev 437, branches/search_engine/data/game/data/core/misc_textures/g05.bmp) =================================================================== (Binary files differ) Deleted: branches/0.2.x/data/game/data/core/misc_textures/g06.bmp =================================================================== (Binary files differ) Copied: branches/0.2.x/data/game/data/core/misc_textures/g06.bmp (from rev 437, branches/search_engine/data/game/data/core/misc_textures/g06.bmp) =================================================================== (Binary files differ) Deleted: branches/0.2.x/data/game/data/core/misc_textures/g07.bmp =================================================================== (Binary files differ) Copied: branches/0.2.x/data/game/data/core/misc_textures/g07.bmp (from rev 437, branches/search_engine/data/game/data/core/misc_textures/g07.bmp) =================================================================== (Binary files differ) Deleted: branches/0.2.x/data/game/data/core/misc_textures/l04.bmp =================================================================== (Binary files differ) Copied: branches/0.2.x/data/game/data/core/misc_textures/l04.bmp (from rev 437, branches/search_engine/data/game/data/core/misc_textures/l04.bmp) =================================================================== (Binary files differ) Deleted: branches/0.2.x/data/game/data/core/misc_textures/l05.bmp =================================================================== (Binary files differ) Copied: branches/0.2.x/data/game/data/core/misc_textures/l05.bmp (from rev 437, branches/search_engine/data/game/data/core/misc_textures/l05.bmp) =================================================================== (Binary files differ) Deleted: branches/0.2.x/data/game/data/core/misc_textures/l06.bmp =================================================================== (Binary files differ) Copied: branches/0.2.x/data/game/data/core/misc_textures/l06.bmp (from rev 437, branches/search_engine/data/game/data/core/misc_textures/l06.bmp) =================================================================== (Binary files differ) Deleted: branches/0.2.x/data/game/data/core/misc_textures/l07.bmp =================================================================== (Binary files differ) Copied: branches/0.2.x/data/game/data/core/misc_textures/l07.bmp (from rev 437, branches/search_engine/data/game/data/core/misc_textures/l07.bmp) =================================================================== (Binary files differ) Copied: branches/0.2.x/source/game/path_finder/cartographer.cpp (from rev 437, branches/search_engine/source/game/path_finder/cartographer.cpp) =================================================================== --- branches/0.2.x/source/game/path_finder/cartographer.cpp (rev 0) +++ branches/0.2.x/source/game/path_finder/cartographer.cpp 2010-01-25 06:23:30 UTC (rev 438) @@ -0,0 +1,328 @@ +// ============================================================== +// This file is part of Glest (www.glest.org) +// +// Copyright (C) 2009 James McCulloch +// +// You can redistribute this code and/or modify it under +// the terms of the GNU General Public License as published +// by the Free Software Foundation; either version 2 of the +// License, or (at your option) any later version +// ============================================================== + +// Does not use pre-compiled header because it's optimized in debug build. + +#include <algorithm> + +#include "game_constants.h" +#include "cartographer.h" + +#include "search_engine.h" +#include "cluster_map.h" + +#include "map.h" +#include "game.h" +#include "unit.h" +#include "unit_type.h" +#include "world.h" + +#include "leak_dumper.h" + +using namespace std; +using namespace Shared::Graphics; +using namespace Shared::Util; + +namespace Glest { namespace Game { namespace Search { + +/** Construct Cartographer object. Requires game settings, factions & cell map to have been loaded. + */ +Cartographer::Cartographer(World *world) + : world(world), routePlanner(0), cellMap(0) { + theLogger.add("Cartographer", true); + + cellMap = world->getMap(); + int w = cellMap->getW(), h = cellMap->getH(); + + routePlanner = world->getRoutePlanner(); + + nodeMap = new NodeMap(w, h); + nmSearchEngine = new SearchEngine<NodeMap, GridNeighbours>(nodeMap, true); + nmSearchEngine->setStorage(nodeMap); + nmSearchEngine->setInvalidKey(Vec2i(-1)); + GridNeighbours::setSearchSpace(SearchSpace::CELLMAP); + + masterMap = new AnnotatedMap(world); + + clusterMap = new ClusterMap(masterMap, this); + + // team search and visibility maps + set<int> teams; + for (int i=0; i < world->getFactionCount(); ++i) { + const Faction *f = world->getFaction(i); + int team = f->getTeam(); + if (teams.find(team) == teams.end()) { + teams.insert(team); + // AnnotatedMap needs to be 'bound' to explored status + explorationMaps[team] = new ExplorationMap(cellMap); + //teamMaps[team] = new AnnotatedMap(world, explorationMaps[team]); + } + } + + // Todo: more preprocessing. Discover all harvester units, + // check field, harvest reange and resource types... + // + // find and catalog all resources... + for (int x=0; x < cellMap->getTileW() - 1; ++x) { + for (int y=0; y < cellMap->getTileH() - 1; ++y) { + const Resource * const r = cellMap->getTile(x,y)->getResource(); + if (r) { + resourceLocations[r->getType()].push_back(Vec2i(x,y)); + } + } + } + + const TechTree *tt = world->getTechTree(); + for (int i=0; i < tt->getResourceTypeCount(); ++i) { + const ResourceType *rt = tt->getResourceType(i); + if (rt->getClass() == ResourceClass::TECHTREE || rt->getClass() == ResourceClass::TILESET) { + Rectangle rect(0, 0, cellMap->getW() - 2, cellMap->getH() - 2); + PatchMap<1> *pMap = new PatchMap<1>(rect, 0); + initResourceMap(rt, pMap); + resourceMaps[rt] = pMap; + } + } +} + +/** Destruct */ +Cartographer::~Cartographer() { + delete masterMap; + delete clusterMap; + delete nmSearchEngine; + + // Team Annotated Maps + /*map<int,AnnotatedMap*>::iterator aMapIt = teamMaps.begin(); + for ( ; aMapIt != teamMaps.end(); ++aMapIt ) { + delete aMapIt->second; + } + teamMaps.clear();*/ + + // Exploration Maps + map<int,ExplorationMap*>::iterator eMapIt = explorationMaps.begin(); + for ( ; eMapIt != explorationMaps.end(); ++eMapIt ) { + delete eMapIt->second; + } + explorationMaps.clear(); + + // Resource Maps + for (ResourceMaps::iterator rmIt = resourceMaps.begin(); rmIt != resourceMaps.end(); ++rmIt) { + delete rmIt->second; + } + resourceMaps.clear(); + + // Store Maps + for (StoreMaps::iterator smIt = storeMaps.begin(); smIt != storeMaps.end(); ++smIt) { + delete smIt->second; + } + storeMaps.clear(); + +} + +void Cartographer::initResourceMap(const ResourceType *rt, PatchMap<1> *pMap) { +/* + static char buf[512]; + char *ptr = buf; + ptr += sprintf(ptr, "Initialising resource map : %s.\n", rt->getName().c_str()); + int64 time_millis = Chrono::getCurMillis(); + int64 time_micros = Chrono::getCurMicros(); +*/ + pMap->zeroMap(); + vector<Vec2i>::iterator it = resourceLocations[rt].begin(); + for ( ; it != resourceLocations[rt].end(); ++it) { + Resource *r = world->getMap()->getTile(*it)->getResource(); + assert(r); + + r->Depleted.connect(this, &Cartographer::onResourceDepleted); + + Vec2i pos = *it * Map::cellScale; + Vec2i tl = pos + OrdinalOffsets[OrdinalDir::NORTH_WEST]; + Vec2i tr = pos + OrdinalOffsets[OrdinalDir::EAST] + OrdinalOffsets[OrdinalDir::NORTH_EAST]; + Vec2i bl = pos + OrdinalOffsets[OrdinalDir::SOUTH] + OrdinalOffsets[OrdinalDir::SOUTH_WEST]; + Vec2i br = pos + OrdinalOffsets[OrdinalDir::SOUTH_EAST] * 2; + + int n = tr.x - tl.x; + for (int i=0; i <= n; ++i) { + Vec2i top(tl.x + i, tl.y); + Vec2i bot(tl.x + i, bl.y); + if (world->getMap()->isInside(top) && masterMap->canOccupy(top, 1, Field::LAND)) { + pMap->setInfluence(top, 1); + } + if (world->getMap()->isInside(bot) && masterMap->canOccupy(bot, 1, Field::LAND)) { + pMap->setInfluence(bot, 1); + } + } + for (int i=1; i <= n - 1; ++i) { + Vec2i left(tl.x, tl.y + i); + Vec2i right(tr.x, tl.y + i); + if (world->getMap()->isInside(left) && masterMap->canOccupy(left, 1, Field::LAND)) { + pMap->setInfluence(left, 1); + } + if (world->getMap()->isInside(right) && masterMap->canOccupy(right, 1, Field::LAND)) { + pMap->setInfluence(right, 1); + } + } + } +/* + time_millis = Chrono::getCurMillis() - time_millis; + time_micros = Chrono::getCurMicros() - time_micros; + if (time_millis >= 3) { + ptr += sprintf(ptr, "Took %dms\n", (int)time_millis); + } else { + ptr += sprintf(ptr, "Took %dms (%dus)\n", (int)time_millis, (int)time_micros); + } + theLogger.add(buf); +*/ +} + +void Cartographer::onResourceDepleted(Vec2i pos) { + const ResourceType *rt = cellMap->getTile(pos/Map::cellScale)->getResource()->getType(); + Vec2i tl = pos + OrdinalOffsets[OrdinalDir::NORTH_WEST]; + Vec2i br = pos + OrdinalOffsets[OrdinalDir::SOUTH_EAST] * 2; + resDirtyAreas[rt].push_back(pair<Vec2i,Vec2i>(tl,br)); +} + +void Cartographer::fixupResourceMap(const ResourceType *rt, const Vec2i &tl, const Vec2i &br) { + PatchMap<1> *pMap = resourceMaps[rt]; + assert(pMap); + Vec2i junk; + for (int y = tl.y; y <= br.y; ++y) { + for (int x = tl.x; x <= br.x; ++x) { + Vec2i pos(x,y); + if (!world->getMap()->isInside(pos)) continue; + if (masterMap->canOccupy(pos, 1, Field::LAND) + && cellMap->isResourceNear(pos, rt, junk)) { + pMap->setInfluence(pos, 1); + } else { + pMap->setInfluence(pos, 0); + } + } + } +} + +void Cartographer::onStoreDestroyed(Unit *unit) { + delete storeMaps[unit]; + storeMaps.erase(unit); +} + +PatchMap<1>* Cartographer::buildStoreMap(Unit *unit) { + const UnitType* const &ut = unit->getType(); + + unit->Died.connect(this, &Cartographer::onStoreDestroyed); + Vec2i pos = unit->getPos(); + const int sx = pos.x; + const int sy = pos.y; + pos += OrdinalOffsets[OrdinalDir::NORTH_WEST]; + Rectangle rect(pos.x, pos.y, unit->getSize() + 2, unit->getSize() + 2); + PatchMap<1> *pMap = new PatchMap<1>(rect, 0); + pMap->zeroMap(); + + for (int y = sy; y < sy + unit->getSize(); ++y) { + for (int x = sx; x < sx + unit->getSize(); ++x) { + if (!ut->hasCellMap() || ut->getCellMapCell(x-sx, y-sy)) { + for (OrdinalDir d(0); d < OrdinalDir::COUNT; ++d) { + Vec2i goalPos = Vec2i(x,y) + OrdinalOffsets[d]; + if (masterMap->canOccupy(goalPos, 1, Field::LAND) + && !pMap->getInfluence(goalPos)) { + pMap->setInfluence(goalPos, 1); + assert(pMap->getInfluence(goalPos)); + } + } + } + } + } + storeMaps[unit] = pMap; + return pMap; +} + +void Cartographer::tick() { + if (clusterMap->isDirty()) { + clusterMap->update(); + } + map<const ResourceType*, AreaList>::iterator it = resDirtyAreas.begin(); + for ( ; it != resDirtyAreas.end(); ++it) { + if (!it->second.empty()) { + AreaList::iterator alIt = it->second.begin(); + for ( ; alIt != it->second.end(); ++alIt) { + fixupResourceMap(it->first, alIt->first, alIt->second); + } + it->second.clear(); + } + } +} + +/** Initialise annotated maps for each team, call after initial units visibility is applied */ +void Cartographer::initTeamMaps() { + map<int, ExplorationMap*>::iterator it = explorationMaps.begin(); + for ( ; it != explorationMaps.end(); ++it ) { + AnnotatedMap *aMap = getAnnotatedMap(it->first); + ExplorationMap *eMap = it->second; + + } +} + +/** Custom Goal function for maintaining the exploration maps */ +class VisibilityMaintainerGoal { +private: + float range; /**< range of entity sight */ + ExplorationMap *eMap; /**< exploration map to adjust */ + bool inc; /**< true to increment, false to decrement */ +public: + /** Construct goal function object + * @param range the range of visibility + * @param eMap the ExplorationMap to adjust + * @param inc true to apply visibility, false to remove + */ + VisibilityMaintainerGoal(float range, ExplorationMap *eMap, bool inc) + : range(range), eMap(eMap), inc(inc) {} + + /** The goal function + * @param pos position to test + * @param costSoFar the cost of the shortest path to pos + * @return true when range is exceeded. + */ + bool operator()(const Vec2i &pos, const float costSoFar) const { + if ( costSoFar > range ) { + return true; + } + if ( inc ) { + eMap->incVisCounter(pos); + } else { + eMap->decVisCounter(pos); + } + return false; + } +}; + +/** Maintains visibility on a per team basis. Adds or removes a unit's visibility + * to (or from) its team exploration map, using a Dijkstra search. + * @param unit the unit to remove or add visibility for + * @param add true to add this units visibility to its team map, false to remove + */ +void Cartographer::maintainUnitVisibility(Unit *unit, bool add) { + + /* This might be too expensive using Dijkstra... + + // set up goal function + VisibilityMaintainerGoal goalFunc((float)unit->getSight(), explorationMaps[unit->getTeam()], add); + // set up search engine + GridNeighbours::setSearchSpace(SearchSpace::TILEMAP); + nmSearchEngine->setNodeLimit(-1); + nmSearchEngine->reset(); + nmSearchEngine->setOpen(Map::toTileCoords(unit->getCenteredPos()), 0.f); + // zap + nmSearchEngine->aStar<VisibilityMaintainerGoal,DistanceCost,ZeroHeuristic> + (goalFunc,DistanceCost(),ZeroHeuristic()); + // reset search space + GridNeighbours::setSearchSpace(SearchSpace::CELLMAP); + */ +} + +}}} Copied: branches/0.2.x/source/game/path_finder/cartographer.h (from rev 437, branches/search_engine/source/game/path_finder/cartographer.h) =================================================================== --- branches/0.2.x/source/game/path_finder/cartographer.h (rev 0) +++ branches/0.2.x/source/game/path_finder/cartographer.h 2010-01-25 06:23:30 UTC (rev 438) @@ -0,0 +1,173 @@ +// ============================================================== +// This file is part of Glest (www.glest.org) +// +// Copyright (C) 2009 James McCulloch <silnarm at gmail> +// +// You can redistribute this code and/or modify it under +// the terms of the GNU General Public License as published +// by the Free Software Foundation; either version 2 of the +// License, or (at your option) any later version +// ============================================================== + + +#ifndef _GLEST_GAME_CARTOGRAPHER_H_ +#define _GLEST_GAME_CARTOGRAPHER_H_ + +#include "game_constants.h" +#include "influence_map.h" +#include "annotated_map.h" +#include "world.h" +#include "config.h" +#include "search_engine.h" +#include "sigslot.h" + +namespace Glest { namespace Game { namespace Search { + +class ClusterMap; +class RoutePlanner; + +/** A map containing a visility counter and explored flag for every map tile. */ +class ExplorationMap { +# pragma pack(push, 2) + struct ExplorationState { /**< The exploration state of one tile for one team */ + uint16 visCounter : 15; /**< Visibility counter, the number of team's units that can see this tile */ + uint16 explored : 1; /**< Explored flag */ + }; // max 32768 units per _team_ +# pragma pack(pop) + ExplorationState *state; /**< The Data */ + Map *cellMap; +public: + ExplorationMap(Map *cMap) : cellMap(cMap) { /**< Construct ExplorationMap, sets everything to zero */ + state = new ExplorationState[cellMap->getTileW() * cellMap->getTileH()]; + memset(state, 0, sizeof(ExplorationState) * cellMap->getTileW() * cellMap->getTileH()); + } + /** @param pos cell coordinates @return number of units that can see this tile */ + int getVisCounter(const Vec2i &pos) const { return state[pos.y * cellMap->getTileH() + pos.x].visCounter; } + /** @param pos tile coordinates to increase visibilty on */ + void incVisCounter(const Vec2i &pos) const { state[pos.y * cellMap->getTileH() + pos.x].visCounter ++; } + /** @param pos tile coordinates to decrease visibilty on */ + void decVisCounter(const Vec2i &pos) const { state[pos.y * cellMap->getTileH() + pos.x].visCounter --; } + /** @param pos tile coordinates @return true if explored. */ + bool isExplored(const Vec2i &pos) const { return state[pos.y * cellMap->getTileH() + pos.x].explored; } + /** @param pos coordinates of tile to set as explored */ + void setExplored(const Vec2i &pos) const { state[pos.y * cellMap->getTileH() + pos.x].explored = 1; } + +}; + +// +// Cartographer: 'Map' Manager +// +class Cartographer : public sigslot::has_slots<> { + /** Master annotated map, always correct */ + AnnotatedMap *masterMap; + + /*/* Team annotateded maps, 'foggy' */ + //map< int, AnnotatedMap* > teamMaps; + + /** The ClusterMap (Hierarchical map abstraction) */ + ClusterMap *clusterMap; + + typedef const ResourceType* rt_ptr; + typedef pair<Vec2i, Vec2i> PosPair; + typedef vector<PosPair> AreaList; + + typedef map<rt_ptr, PatchMap<1>*> ResourceMaps; + typedef map<const Unit*, PatchMap<1>*> StoreMaps; + + // Resources + /** The locations of each and every resource on the map */ + map<rt_ptr, vector<Vec2i> > resourceLocations; + + /** areas where resources have been depleted and updates are required */ + map<rt_ptr, AreaList> resDirtyAreas; + + /** Goal Maps for each tech & tileset resource */ + ResourceMaps resourceMaps; + + StoreMaps storeMaps; + + // Exploration + /** Exploration maps for each team */ + map< int, ExplorationMap* > explorationMaps; + + // A* stuff + NodeMap *nodeMap; + SearchEngine<NodeMap,GridNeighbours> *nmSearchEngine; + + World *world; + Map *cellMap; + RoutePlanner *routePlanner; + + void initResourceMap(const ResourceType *rt, PatchMap<1> *pMap); + void fixupResourceMap(const ResourceType *rt, const Vec2i &tl, const Vec2i &br); + + PatchMap<1>* buildStoreMap(Unit *unit); + + // slots + void onResourceDepleted(Vec2i pos); + void onStoreDestroyed(Unit *unit); + + void onUnitBorn(Unit *unit); + void onUnitMoved(Unit *unit); + void onUnitMorphed(Unit *unit, const UnitType *type); + void onUnitDied(Unit *unit); + + void maintainUnitVisibility(Unit *unit, bool add); + +public: + Cartographer(World *world); + virtual ~Cartographer(); + + SearchEngine<NodeMap,GridNeighbours>* getSearchEngine() { return nmSearchEngine; } + RoutePlanner* getRoutePlanner() { return routePlanner; } + + /** @return the number of units of team that can see a tile + * @param team team index + * @param pos the co-ordinates of the <b>tile</b> of interest. */ + int getTeamVisibility(int team, const Vec2i &pos) { return explorationMaps[team]->getVisCounter(pos); } + /** Adds a unit's visibility to its team's exploration map */ + void applyUnitVisibility(Unit *unit) { maintainUnitVisibility(unit, true); } + /** Removes a unit's visibility from its team's exploration map */ + void removeUnitVisibility(Unit *unit) { maintainUnitVisibility(unit, false); } + + void initTeamMaps(); + + /** Update the annotated maps when an obstacle has been added or removed from the map. + * Unconditionally updates the master map, updates team maps if the team can see the cells, + * or mark as 'dirty' if they cannot currently see the change. @todo implement team maps + * @param pos position (north-west most cell) of obstacle + * @param size size of obstacle */ + void updateMapMetrics(const Vec2i &pos, const int size) { + masterMap->updateMapMetrics(pos, size); + // who can see it ? update their maps too. + // set cells as dirty for those that can't see it + } + + void tick(); + + PatchMap<1>* getResourceMap(const ResourceType* rt) { + return resourceMaps[rt]; + } + + PatchMap<1>* getStoreMap(const Unit *unit) { + StoreMaps::iterator it = storeMaps.find(unit); + if (it != storeMaps.end()) { + return it->second; + } + return buildStoreMap(const_cast<Unit*>(unit)); + } + + ClusterMap* getClusterMap() const { return clusterMap; } + + AnnotatedMap* getMasterMap() const { return masterMap; } + AnnotatedMap* getAnnotatedMap(int team ) { return masterMap;/*teamMaps[team];*/ } + AnnotatedMap* getAnnotatedMap(const Faction *faction) { return getAnnotatedMap(faction->getTeam()); } + AnnotatedMap* getAnnotatedMap(const Unit *unit) { return getAnnotatedMap(unit->getTeam()); } +}; + +//class Surveyor { +//}; + +}}} + +#endif Copied: branches/0.2.x/source/game/path_finder/cluster_map.cpp (from rev 437, branches/search_engine/source/game/path_finder/cluster_map.cpp) =================================================================== --- branches/0.2.x/source/game/path_finder/cluster_map.cpp (rev 0) +++ branches/0.2.x/source/game/path_finder/cluster_map.cpp 2010-01-25 06:23:30 UTC (rev 438) @@ -0,0 +1,653 @@ +// ============================================================== +// This file is part of Glest (www.glest.org) +// +// Copyright (C) 2009 James McCulloch <silnarm at gmail> +// +// You can redistribute this code and/or modify it under +// the terms of the GNU General Public License as published +// by the Free Software Foundation; either version 2 of the +// License, or (at your option) any later version +// ============================================================== + +#include "pch.h" + +#include <algorithm> + +#include "search_engine.h" +#include "cluster_map.h" +#include "cartographer.h" +#include "search_engine.h" +#include "route_planner.h" + +#if _GAE_DEBUG_EDITION_ +# include "debug_renderer.h" +#endif + +namespace Glest { namespace Game { namespace Search { + +int Edge::numEdges[Field::COUNT]; +int Transition::numTransitions[Field::COUNT]; + + +#if SILNARM_HAS_DEFINED_SOME_CRAZY_PREPROCESSOR_SYMBOL +# define WRITE_AND_FLUSH(x) { cout << x, cout.flush(); } +#else +# define WRITE_AND_FLUSH(x) {} +#endif + +void Edge::zeroCounters() { + for (Field f(0); f < Field::COUNT; ++f) { + numEdges[f] = 0; + } +} + +void Transition::zeroCounters() { + for (Field f(0); f < Field::COUNT; ++f) { + numTransitions[f] = 0; + } +} + +ClusterMap::ClusterMap(AnnotatedMap *aMap, Cartographer *carto) + : aMap(aMap) , carto(carto), dirty(false) { + w = aMap->getWidth() / clusterSize; + h = aMap->getHeight() / clusterSize; + vertBorders = new ClusterBorder[(w-1)*h]; + horizBorders = new ClusterBorder[w*(h-1)]; + // init Borders (and hence inter-cluster edges) & evaluate clusters (intra-cluster edges) + + Edge::zeroCounters(); + Transition::zeroCounters(); + + theLogger.setClusterCount(w * h); +/* + static char buf[512]; + char *ptr = buf; + ptr += sprintf(ptr, "Initialising cluster map.\n"); + int64 time_millis = Chrono::getCurMillis(); +*/ + for (int i = h - 1; i >= 0; --i) { + for (int j = w - 1; j >= 0; --j) { + Vec2i cluster(j, i); + WRITE_AND_FLUSH( "Cluster " << cluster << endl ) + initCluster(cluster); + WRITE_AND_FLUSH( "Cluster " << cluster << "initialised.\n" ) + evalCluster(cluster); + WRITE_AND_FLUSH( "Cluster " << cluster << "evaluated.\n" ) + theLogger.clusterInit(); + } + } + + /* + time_millis = Chrono::getCurMillis() - time_millis; + ptr += sprintf(ptr, "\ttook %dms\n", (int)time_millis); + theLogger.add(buf); + */ +} + +ClusterMap::~ClusterMap() { + delete [] vertBorders; + delete [] horizBorders; + for (Field f(0); f < Field::COUNT; ++f) { + assert(Edge::NumEdges(f) == 0); + assert(Transition::NumTransitions(f) == 0); + if (Edge::NumEdges(f) != 0 || Transition::NumTransitions(f) != 0) { + throw runtime_error("memory leak"); + } + } +} + +void ClusterMap::assertValid() { + bool valid[Field::COUNT]; + bool inUse[Field::COUNT]; + int numNodes[Field::COUNT]; + int numEdges[Field::COUNT]; + + for (Field f(0); f < Field::COUNT; ++f) { + typedef set<const Transition *> TSet; + TSet tSet; + + typedef pair<Vec2i, bool> TKey; + typedef map<TKey, const Transition *> TKMap; + + TKMap tkMap; + + valid[f] = true; + numNodes[f] = 0; + numEdges[f] = 0; + inUse[f] = aMap->maxClearance[f] != 0; + if (f == Field::AIR) inUse[f] = false; + if (!inUse[f]) { + continue; + } + + // collect all transitions, checking for membership in tSet and tkMap (indicating an error) + // and filling tSet and tkMap + for (int i=0; i < (w - 1) * h; ++i) { + ClusterBorder *b = &vertBorders[i]; + for (int j=0; j < b->transitions[f].n; ++j) { + const Transition *t = b->transitions[f].transitions[j]; + if (tSet.find(t) != tSet.end()) { + cout << "single transition on multiple borders.\n"; + valid[f] = false; + } else { + tSet.insert(t); + TKey key(t->nwPos, t->vertical); + if (tkMap.find(key) != tkMap.end()) { + cout << "seperate transitions of same orientation on same cell.\n"; + valid[f] = false; + } else { + tkMap[key] = t; + } + } + ++numNodes[f]; + } + + } + for (int i=0; i < w * (h - 1); ++i) { + ClusterBorder *b = &horizBorders[i]; + for (int j=0; j < b->transitions[f].n; ++j) { + const Transition *t = b->transitions[f].transitions[j]; + if (tSet.find(t) != tSet.end()) { + cout << "single transition on multiple borders.\n"; + valid[f] = false; + } else { + tSet.insert(t); + TKey key(t->nwPos, t->vertical); + if (tkMap.find(key) != tkMap.end()) { + cout << "seperate transitions of same orientation on same cell.\n"; + valid[f] = false; + } else { + tkMap[key] = t; + } + } + ++numNodes[f]; + } + } + + // with a complete collection, iterate, check all dest transitions + for (TSet::iterator it = tSet.begin(); it != tSet.end(); ++it) { + const Edges &edges = (*it)->edges; + for (Edges::const_iterator eit = edges.begin(); eit != edges.end(); ++eit) { + TSet::iterator it2 = tSet.find((*eit)->transition()); + if (it2 == tSet.end()) { + cout << "Invalid edge.\n"; + valid[f] = false; + } else { + if (*it == *it2) { + cout << "self referential transition.\n"; + valid[f] = false; + } + } + ++numEdges[f]; + } + } + } + cout << "\nClusterMap::assertValid()"; + cout << "\n=========================\n"; + for (Field f(0); f < Field::COUNT; ++f) { + if (!inUse[f]) { + cout << "Field::" << FieldNames[f] << " not in use.\n"; + } else { + cout << "Field::" << FieldNames[f] << " in use and " << (!valid[f]? "NOT " : "") << "valid.\n"; + cout << "\t" << numNodes[f] << " transitions inspected.\n"; + cout << "\t" << numEdges[f] << " edges inspected.\n"; + } + } +} + +/** Entrance init helper class */ +class InsideOutIterator { +private: + int centre, incr, end; + bool flip; + +public: + InsideOutIterator(int low, int high) + : flip(false) { + centre = low + (high - low) / 2; + incr = 0; + end = ((high - low) % 2 != 0) ? low - 1 : high + 1; + } + + int operator*() const { + return centre + (flip ? incr : -incr); + } + + void operator++() { + flip = !flip; + if (flip) ++incr; + } + + bool more() { + return **this != end; + } +}; + +void ClusterMap::addBorderTransition(EntranceInfo &info) { + assert(info.max_clear > 0 && info.startPos != -1 && info.endPos != -1); + WRITE_AND_FLUSH( + "\t\tEntrance from (" << info.endPos << ", " << info.pos << ") to (" + << info.startPos << ", " << info.pos << ")" << endl + ) + if (info.run < 12) { + // find central most pos with max clearance + InsideOutIterator it(info.endPos, info.startPos); + while (it.more()) { + if (eClear[info.startPos - *it] == info.max_clear) { + Transition *t; + if (info.vert) { + t = new Transition(Vec2i(info.pos, *it), info.max_clear, true, info.f); + } else { + t = new Transition(Vec2i(*it, info.pos), info.max_clear, false, info.f); + } + WRITE_AND_FLUSH( "\t\t\tadding Entrance at " << t->nwPos << "\n" ) + info.cb->transitions[info.f].add(t); + return; + } + ++it; + } + WRITE_AND_FLUSH( "\t\t\tno pos with clearance == max_clear found!!!! WTF!!!" ) + assert(false); + } else { + // look for two, as close as possible to 1/4 and 3/4 accross + int l1 = info.endPos; + int h1 = info.endPos + (info.startPos - info.endPos) / 2 - 1; + int l2 = info.endPos + (info.startPos - info.endPos) / 2; + int h2 = info.startPos; + InsideOutIterator it(l1, h1); + int first_at = -1; + while (it.more()) { + if (eClear[info.startPos - *it] == info.max_clear) { + first_at = *it; + break; + } + ++it; + } + if (first_at != -1) { + it = InsideOutIterator(l2, h2); + int next_at = -1; + while (it.more()) { + if (eClear[info.startPos - *it] == info.max_clear) { + next_at = *it; + break; + } + ++it; + } + if (next_at != -1) { + Transition *t1, *t2; + if (info.vert) { + t1 = new Transition(Vec2i(info.pos, first_at), info.max_clear, true, info.f); + t2 = new Transition(Vec2i(info.pos, next_at), info.max_clear, true, info.f); + } else { + t1 = new Transition(Vec2i(first_at, info.pos), info.max_clear, false, info.f); + t2 = new Transition(Vec2i(next_at, info.pos), info.max_clear, false, info.f); + } + WRITE_AND_FLUSH( "\t\t\tadding Entrance at " << t1->nwPos << "\n" ) + WRITE_AND_FLUSH( "\t\t\tadding Entrance at " << t2->nwPos << "\n" ) + info.cb->transitions[info.f].add(t1); + info.cb->transitions[info.f].add(t2); + return; + } + } + // failed to find two, just add one... + it = InsideOutIterator(info.endPos, info.startPos); + while (it.more()) { + if (eClear[info.startPos - *it] == info.max_clear) { + Transition *t; + if (info.vert) { + t = new Transition(Vec2i(info.pos, *it), info.max_clear, true, info.f); + } else { + t = new Transition(Vec2i(*it, info.pos), info.max_clear, false, info.f); + } + WRITE_AND_FLUSH( "\t\t\tadding Entrance at " << t->nwPos << "\n" ) + info.cb->transitions[info.f].add(t); + return; + } + ++it; + } + WRITE_AND_FLUSH( "\t\t\tno pos with clearance == max_clear found!!!! WTF!!!" ) + assert(false); + } +} + +void ClusterMap::initClusterBorder(const Vec2i &cluster, bool north) { + WRITE_AND_FLUSH( "\tInit " << (north ? "north" : "west") << " border [cluster=" << cluster << "]\n" ) + ClusterBorder *cb = north ? getNorthBorder(cluster) : getWestBorder(cluster); + EntranceInfo inf; + inf.cb = cb; + inf.vert = !north; + if (cb != &sentinel) { + int pos = north ? cluster.y * clusterSize - 1 : cluster.x * clusterSize - 1; + inf.pos = pos; + int pos2 = pos + 1; + bool clear = false; // true while evaluating a Transition, false when obstacle hit + inf.max_clear = -1; // max clearance seen for current Transition + inf.startPos = -1; // start position of entrance + inf.endPos = -1; // end position of entrance + inf.run = 0; // to count entrance 'width' + for (Field f(0); f < Field::COUNT; ++f) { + if (!aMap->maxClearance[f] || f == Field::AIR) continue; +# if _GAE_DEBUG_EDITION_ + if (f == Field::LAND) { + for (int i=0; i < cb->transitions[f].n; ++i) { + PathfinderClusterOverlay::entranceCells.erase( + cb->transitions[f].transitions[i]->nwPos + ); + } + } +# endif + cb->transitions[f].clear(); + clear = false; + inf.f = f; + inf.max_clear = -1; + for (int i=0; i < clusterSize; ++i) { + int clear1, clear2; + if (north) { + clear1 = aMap->metrics[Vec2i(POS_X,pos)].get(f); + clear2 = aMap->metrics[Vec2i(POS_X,pos2)].get(f); + } else { + clear1 = aMap->metrics[Vec2i(pos, POS_Y)].get(f); + clear2 = aMap->metrics[Vec2i(pos2, POS_Y)].get(f); + } + int local = min(clear1, clear2); + if (local) { + if (!clear) { + clear = true; + inf.startPos = north ? POS_X : POS_Y; + } + eClear[inf.run++] = local; + inf.endPos = north ? POS_X : POS_Y; + if (local > inf.max_clear) { + inf.max_clear = local; + } + } else { + if (clear) { + addBorderTransition(inf); + inf.run = 0; + inf.startPos = inf.endPos = inf.max_clear = -1; + clear = false; + } + } + } // for i < clusterSize + if (clear) { + addBorderTransition(inf); + inf.run = 0; + inf.startPos = inf.endPos = inf.max_clear = -1; + clear = false; + } + }// for each Field +# if _GAE_DEBUG_EDITION_ + for (int i=0; i < cb->transitions[Field::LAND].n; ++i) { + PathfinderClusterOverlay::entranceCells.insert( + cb->transitions[Field::LAND].transitions[i]->nwPos + ); + } +# endif + } // if not sentinel + WRITE_AND_FLUSH( "\tDone Init " << (north ? "north" : "west") << " border [cluster=" << cluster << "]\n" ) +} + +float ClusterMap::aStarPathLength(Field f, int size, const Vec2i &start, const Vec2i &dest) { + if (start == dest) { + return 0.f; + } + SearchEngine<NodeStore> *se = carto->getRoutePlanner()->getSearchEngine(); + MoveCost costFunc(f, size, aMap); + DiagonalDistance dd(dest); + se->setNodeLimit(clusterSize * clusterSize); + se->setStart(start, dd(start)); + AStarResult res = se->aStar<PosGoal,MoveCost,DiagonalDistance>(PosGoal(dest), costFunc, dd); + Vec2i goalPos = se->getGoalPos(); + if (res != AStarResult::COMPLETE || goalPos != dest) { + return numeric_limits<float>::infinity(); + } + return se->getCostTo(goalPos); +} + +void ClusterMap::getTransitions(const Vec2i &cluster, Field f, Transitions &t) { + ClusterBorder *b = getNorthBorder(cluster); + for (int i=0; i < b->transitions[f].n; ++i) { + t.push_back(b->transitions[f].transitions[i]); + } + b = getEastBorder(cluster); + for (int i=0; i < b->transitions[f].n; ++i) { + t.push_back(b->transitions[f].transitions[i]); + } + b = getSouthBorder(cluster); + for (int i=0; i < b->transitions[f].n; ++i) { + t.push_back(b->transitions[f].transitions[i]); + } + b = getWestBorder(cluster); + for (int i=0; i < b->transitions[f].n; ++i) { + t.push_back(b->transitions[f].transitions[i]); + } +} + +void ClusterMap::disconnectCluster(const Vec2i &cluster) { + //cout << "Disconnecting cluster " << cluster << endl; + for (Field f(0); f < Field::COUNT; ++f) { + if (!aMap->maxClearance[f] || f == Field::AIR) continue; + Transitions t; + getTransitions(cluster, f, t); + set<const Transition*> tset; + for (Transitions::iterator it = t.begin(); it != t.end(); ++it) { + tset.insert(*it); + } + //int del = 0; + for (Transitions::iterator it = t.begin(); it != t.end(); ++it) { + Transition *t = const_cast<Transition*>(*it); + Edges::iterator eit = t->edges.begin(); + while (eit != t->edges.end()) { + if (tset.find((*eit)->transition()) != tset.end()) { + delete *eit; + eit = t->edges.erase(eit); + //++del; + } else { + ++eit; + } + } + } + //cout << "\tDeleted " << del << " edges in Field = " << FieldNames[f] << ".\n"; + } + +} + +void ClusterMap::update() { + //cout << "ClusterMap::update()" << endl; + for (set<Vec2i>::iterator it = dirtyNorthBorders.begin(); it != dirtyNorthBorders.end(); ++it) { + if (it->y > 0 && it->y < h) { + dirtyClusters.insert(Vec2i(it->x, it->y)); + dirtyClusters.insert(Vec2i(it->x, it->y - 1)); + } + } + for (set<Vec2i>::iterator it = dirtyWestBorders.begin(); it != dirtyWestBorders.end(); ++it) { + if (it->x > 0 && it->x < w) { + dirtyClusters.insert(Vec2i(it->x, it->y)); + dirtyClusters.insert(Vec2i(it->x - 1, it->y)); + } + } + for (set<Vec2i>::iterator it = dirtyClusters.begin(); it != dirtyClusters.end(); ++it) { + //cout << "cluster " << *it << " dirty." << endl; + disconnectCluster(*it); + } + for (set<Vec2i>::iterator it = dirtyNorthBorders.begin(); it != dirtyNorthBorders.end(); ++it) { + //cout << "cluster " << *it << " north border dirty." << endl; + initClusterBorder(*it, true); + } + for (set<Vec2i>::iterator it = dirtyWestBorders.begin(); it != dirtyWestBorders.end(); ++it) { + //cout << "cluster " << *it << " west border dirty." << endl; + initClusterBorder(*it, false); + } + for (set<Vec2i>::iterator it = dirtyClusters.begin(); it != dirtyClusters.end(); ++it) { + evalCluster(*it); + } + + dirtyClusters.clear(); + dirtyClusters.clear(); + dirtyWestBorders.clear(); + dirty = false; +} + +/** compute intra-cluster path lengths */ +void ClusterMap::evalCluster(const Vec2i &cluster) { + GridNeighbours::setSearchCluster(cluster); + Transitions transitions; + for (Field f(0); f < Field::COUNT; ++f) { + if (!aMap->maxClearance[f] || f == Field::AIR) continue; + transitions.clear(); + getTransitions(cluster, f, transitions); + Transitions::iterator it = transitions.begin(); + for ( ; it != transitions.end(); ++it) { + Transition *t = const_cast<Transition*>(*it); + Vec2i start = t->nwPos; + Transitions::iterator it2 = transitions.begin(); + for ( ; it2 != transitions.end(); ++it2) { + const Transition* &t2 = *it2; + if (t == t2) continue; + Vec2i dest = t2->nwPos; + float cost = aStarPathLength(f, 1, start, dest); + if (cost == numeric_limits<float>::infinity()) continue; + Edge *e = new Edge(t2, f); + t->edges.push_back(e); + e->addWeight(cost); + int size = 2; + int maxClear = t->clearance > t2->clearance ? t2->clearance : t->clearance; + while (size <= maxClear) { + cost = aStarPathLength(f, size, start, dest); + if (cost == numeric_limits<float>::infinity()) { + break; + } + e->addWeight(cost); + assert(size == e->maxClear()); + ++size; + } + } + } + } // for each Field + GridNeighbours::setSearchSpace(SearchSpace::CELLMAP); +} + +// ======================================================== +// class TransitionNodeStorage +// ======================================================== + +TransitionAStarNode* TransitionNodeStore::getNode() { + if (nodeCount == size) { + //assert(false); + return NULL; + } + return &stock[nodeCount++]; +} + +void TransitionNodeStore::insertIntoOpen(TransitionAStarNode *node) { + if (openList.empty()) { + openList.push_front(node); + return; + } + list<TransitionAStarNode*>::iterator it = openList.begin(); + while (it != openList.end() && (*it)->est() <= node->est()) { + ++it; + } + openList.insert(it, node); +} + +bool TransitionNodeStore::assertOpen() { + if (openList.size() < 2) { + return true; + } + set<const Transition*> seen; + list<TransitionAStarNode*>::iterator it1, it2 = openList.begin(); + it1 = it2; + seen.insert((*it1)->pos); + for (++it2; it2 != openList.end(); ++it2) { + if (seen.find((*it2)->pos) != seen.end()) { + theLogger.add("open list has cycle... that's bad."); + cout << "open list has cycle... that's bad." << endl; + return false; + } + seen.insert((*it2)->pos); + if ((*it1)->est() > (*it2)->est() + 0.0001f) { // stupid inaccurate fp + theLogger.add("open list is not ordered correctly."); + cout << "Open list corrupt: it1.est() == " << (*it1)->est() + << " > it2.est() == " << (*it2)->est() << endl; + return false; + } + } + set<const Transition*>::iterator it = open.begin(); + for ( ; it != open.end(); ++it) { + if (seen.find(*it) == seen.end()) { + theLogger.add("node marked open not on open list."); + cout << "node marked open not on open list." << endl; + return false; + } + } + it = seen.begin(); + for ( ; it != seen.end(); ++it) { + if (open.find(*it) == open.end()) { + theLogger.add("node on open list not marked open."); + cout << "node on open list not marked open." << endl; + return false; + } + } + return true; +} + +Transition* TransitionNodeStore::getBestSeen() { + assert(false); + return NULL; +} + +bool TransitionNodeStore::setOpen(const Transition* pos, const Transition* prev, float h, float d) { + assert(open.find(pos) == open.end()); + assert(closed.find(pos) == closed.end()); + + //REMOVE + //assert(assertOpen()); + + TransitionAStarNode *node = getNode(); + if (!node) return false; + node->pos = pos; + node->prev = prev; + node->distToHere = d; + node->heuristic = h; + open.insert(pos); + insertIntoOpen(node); + listed[pos] = node; + + //REMOVE + //assert(assertOpen()); + + return true; +} + +void TransitionNodeStore::updateOpen(const Transition* pos, const Transition* &prev, const float cost) { + assert(open.find(pos) != open.end()); + assert(closed.find(prev) != closed.end()); + + //REMOVE + //assert(assertOpen()); + + TransitionAStarNode *prevNode = listed[prev]; + TransitionAStarNode *posNode = listed[pos]; + if (prevNode->distToHere + cost < posNode->distToHere) { + openList.remove(posNode); + posNode->prev = prev; + posNode->distToHere = prevNode->distToHere + cost; + insertIntoOpen(posNode); + } + + //REMOVE + //assert(assertOpen()); +} + +const Transition* TransitionNodeStore::getBestCandidate() { + if (openList.empty()) return NULL; + TransitionAStarNode *node = openList.front(); + const Transition *best = node->pos; + openList.pop_front(); + open.erase(open.find(best)); + closed.insert(best); + return best; +} + +}}} \ No newline at end of file Copied: branches/0.2.x/source/game/path_finder/cluster_map.h (from rev 437, branches/search_engine/source/game/path_finder/cluster_map.h) =================================================================== --- branches/0.2.x/source/game/path_finder/cluster_map.h (rev 0) +++ branches/0.2.x/source/game/path_finder/cluster_map.h 2010-01-25 06:23:30 UTC (rev 438) @@ -0,0 +1,314 @@ +// ============================================================== +// This file is part of Glest (www.glest.org) +// +// Copyright (C) 2009 James McCulloch <silnarm at gmail> +// +// You can redistribute this code and/or modify it under +// the terms of the GNU General Public License as published +// by the Free Software Foundation; either version 2 of the +// License, or (at your option) any later version +// ============================================================== + +#ifndef _GLEST_GAME_CLUSTER_MAP_H_ +#define _GLEST_GAME_CLUSTER_MAP_H_ + +#include "game_constants.h" + +using std::set; + +namespace Glest { namespace Game { + +class DebugRenderer; + +namespace Search { + +class AnnotatedMap; +class Cartographer; +struct Transition; + +static const int clusterSize = 16; + +/** uni-directional edge, is owned by the source transition, contains pointer to dest */ +struct Edge { +private: + static int numEdges[Field::COUNT]; + + const Transition *dest; + vector<float> weights; + + Field f; // for diagnostics... remove this one day + +public: + Edge(const Transition *t, Field f) : f(f) { + dest = t; + ++numEdges[f]; + } + + ~Edge() { + --numEdges[f]; + } + + void addWeight(const float w) { weights.push_back(w); } + const Transition* transition() const { return dest; } + float cost(int size) const { return weights[size-1]; } + int maxClear() { return weights.size(); } + + static int NumEdges(Field f) { return numEdges[f]; } + static void zeroCounters(); +}; +typedef list<Edge*> Edges; + +/** */ +struct Transition { +private: + static int numTransitions[Field::COUNT]; + Field f; + +public: + int clearance; + Vec2i nwPos; + bool vertical; + Edges edges; + + Transition(Vec2i pos, int clear, bool vert, Field f) + : nwPos(pos), clearance(clear), vertical(vert), f(f) { + ++numTransitions[f]; + } + ~Transition() { + deleteValues(edges.begin(), edges.end()); + --numTransitions[f]; + } + + static int NumTransitions(Field f) { return numTransitions[f]; } + static void zeroCounters(); +}; + +typedef vector<const Transition*> Transitions; + +struct TransitionCollection { + Transition *transitions[clusterSize/2]; + unsigned n; + + TransitionCollection() { + n = 0; + memset(transitions, 0, sizeof(Transition*) * clusterSize / 2); + } + + void add(Transition *t) { + assert(n < clusterSize / 2); + transitions[n++] = t; + } + + void clear() { + for (int i=0; i < n; ++i) { + delete transitions[i]; + } + n = 0; + } + +}; + +struct ClusterBorder { + TransitionCollection transitions[Field::COUNT]; + + ~ClusterBorder() { + for (Field f(0); f < Field::COUNT; ++f) { + transitions[f].clear(); + } + } +}; + +/** NeighbourFunc, describes abstract search space */ +class TransitionNeighbours { +public: + void operator()(const Transition* pos, vector<const Transition*> &neighbours) const { + for (Edges::const_iterator it = pos->edges.begin(); it != pos->edges.end(); ++it) { + neighbours.push_back((*it)->transition()); + } + } +}; + +/** cost function for searching cluster map */ +class TransitionCost { + Field field; + int size; + +public: + TransitionCost(Field f, int s) : field(f), size(s) {} + float operator()(const Transition *t, const Transition *t2) const { + Edges::const_iterator it = t->edges.begin(); + for ( ; it != t->edges.end(); ++it) { + if ((*it)->transition() == t2) { + break; + } + } + if (it == t->edges.end()) { + throw runtime_error("bad connection in ClusterMap."); + } + if ((*it)->maxClear() >= size) { + return (*it)->cost(size); + } + return numeric_limits<float>::infinity(); + } +}; + +/** goal function for search on cluster map */ +class TransitionGoal { + set<const Transition*> goals; +public: + TransitionGoal() {} + set<const Transition*>& goalTransitions() {return goals;} + bool operator()(const Transition *t, const float d) const { + return goals.find(t) != goals.end(); + } +}; + +#define POS_X ((cluster.x + 1) * clusterSize - i - 1) +#define POS_Y ((cluster.y + 1) * clusterSize - i - 1) + +class ClusterMap { +#if _GAE_DEBUG_EDITION_ + friend class DebugRenderer; +#endif +private: + int w, h; + ClusterBorder *vertBorders, *horizBorders, sentinel; + Cartographer *carto; + AnnotatedMap *aMap; + + set<Vec2i> dirtyClusters; + set<Vec2i> dirtyNorthBorders; + set<Vec2i> dirtyWestBorders; + bool dirty; + + int eClear[clusterSize]; + +public: + ClusterMap(AnnotatedMap *aMap, Cartographer *carto); + ~ClusterMap(); + + int getWidth() const { return w; } + int getHeight() const { return h; } + + static Vec2i cellToCluster (const Vec2i &cellPos) { + return Vec2i(cellPos.x / clusterSize, cellPos.y / clusterSize); + } + // ClusterBorder getters + ClusterBorder* getNorthBorder(Vec2i cluster) { + return ( cluster.y == 0 ) ? &sentinel : &horizBorders[(cluster.y - 1) * w + cluster.x ]; + } + ClusterBorder* getEastBorder(Vec2i cluster) { + return ( cluster.x == w - 1 ) ? &sentinel : &vertBorders[cluster.y * (w - 1) + cluster.x ]; + } + ClusterBorder* getSouthBorder(Vec2i cluster) { + return ( cluster.y == h - 1 ) ? &sentinel : &horizBorders[cluster.y * w + cluster.x]; + } + ClusterBorder* getWestBorder(Vec2i cluster) { + return ( cluster.x == 0 ) ? &sentinel : &vertBorders[cluster.y * (w - 1) + cluster.x - 1]; + } + ClusterBorder* getBorder(Vec2i cluster, CardinalDir dir) { + switch (dir) { + case CardinalDir::NORTH: + return getNorthBorder(cluster); + case CardinalDir::EAST: + return getEastBorder(cluster); + case CardinalDir::SOUTH: + return getSouthBorder(cluster); + case CardinalDir::WEST: + return getWestBorder(cluster); + default: + throw runtime_error("ClusterMap::getBorder() passed dodgey direction"); + return 0; // keep compiler quiet + } + } + void getTransitions(const Vec2i &cluster, Field f, Transitions &t); + + bool isDirty() { return dirty; } + void update(); + + void setClusterDirty(const Vec2i &cluster) { dirty = true; dirtyClusters.insert(cluster); } + void setNorthBorderDirty(const Vec2i &cluster) { dirty = true; dirtyNorthBorders.insert(cluster); } + void setWestBorderDirty(const Vec2i &cluster) { dirty = true; dirtyWestBorders.insert(cluster); } + + void assertValid(); + +private: + struct EntranceInfo { + ClusterBorder *cb; + Field f; + bool vert; + int pos, max_clear, startPos, endPos, run; + }; + void addBorderTransition(EntranceInfo &info); + void initClusterBorder(const Vec2i &cluster, bool north); + + /** initialise/re-initialise cluster (evaluates north and west borders) */ + void initCluster(const Vec2i &cluster) { + initClusterBorder(cluster, true); + initClusterBorder(cluster, false); + } + + void evalCluster(const Vec2i &cluster); + + float aStarPathLength(Field f, int size, const Vec2i &start, const Vec2i &dest); + + void disconnectCluster(const Vec2i &cluster); +}; + +struct TransitionAStarNode { + const Transition *pos, *prev; + float heuristic; /**< estimate of distance to goal */ + float distToHere; /**< cost from origin to this node */ + float est() const { /**< estimate, costToHere + heuristic */ + return distToHere + heuristic; + } +}; + +// ======================================================== +// class TransitionNodeStorage +// ======================================================== +// NodeStorage template interface +class TransitionNodeStore { +private: + list<TransitionAStarNode*> openList; + set<const Transition*> open; + set<const Transition*> closed; + map<const Transition*, TransitionAStarNode*> listed; + + int size, nodeCount; + TransitionAStarNode *stock; + + TransitionAStarNode* getNode(); + void insertIntoOpen(TransitionAStarNode *node); + bool assertOpen(); + +public: + TransitionNodeStore(int size) : stock(NULL), size(size) { + stock = new TransitionAStarNode[size]; + reset(); + } + ~TransitionNodeStore() { + delete [] stock; + } + + void reset() { nodeCount = 0; open.clear(); closed.clear(); openList.clear(); listed.clear(); } + void setMaxNodes(int limit) { } + + bool isOpen(const Transition* pos) { return open.find(pos) != open.end(); } + bool isClosed(const Transition* pos) { return closed.find(pos) != closed.end(); } + + bool setOpen(const Transition* pos, const Transition* prev, float h, float d); + void updateOpen(const Transition* pos, const Transition* &prev, const float cost); + const Transition* getBestCandidate(); + Transition* getBestSeen(); + + float getHeuristicAt(const Transition* &pos) { return listed[pos]->heuristic; } + float getCostTo(const Transition* pos) { return listed[pos]->distToHere; } + float getEstimateFor(const Transition* pos) { return listed[pos]->est(); } + const Transition* getBestTo(const Transition* pos) { return listed[pos]->prev; } +}; + + +}}} + +#endif Copied: branches/0.2.x/source/game/path_finder/influence_map.cpp (from rev 437, branches/search_engine/source/game/path_finder/influence_map.cpp) =================================================================== --- branches/0.2.x/source/game/path_finder/influence_map.cpp (rev 0) +++ branches/0.2.x/source/game/path_finder/influence_map.cpp 2010-01-25 06:23:30 UTC (rev 438) @@ -0,0 +1,18 @@ +// ============================================================== +// This file is part of Glest (www.glest.org) +// +// Copyright (C) 2009 James McCulloch +// +// You can redistribute this code and/or modify it under +// the terms of the GNU General Public License as published +// by the Free Software Foundation; either version 2 of the +// License, or (at your option) any later version +// ============================================================== + +#include "pch.h" +#include "influence_map.h" + +namespace Glest { namespace Game { namespace Search { + +}}} + Copied: branches/0.2.x/source/game/path_finder/influence_map.h (from rev 437, branches/search_engine/source/game/path_finder/influence_map.h) =================================================================== --- branches/0.2.x/source/game/path_finder/influence_map.h (rev 0) +++ branches/0.2.x/source/game/path_finder/influence_map.h 2010-01-25 06:23:30 UTC (rev 438) @@ -0,0 +1,240 @@ +// ============================================================== +// This file is part of Glest (www.glest.org) +// +// Copyright (C) 2009 James McCulloch +// +// You can redistribute this code and/or modify it under +// the terms of the GNU General Public License as published +// by the Free Software Foundation; either version 2 of the +// License, or (at your option) any later version +// ============================================================== + + +#ifndef _GAME_SEARCH_INLUENCE_MAP_H_ +#define _GAME_SEARCH_INLUENCE_MAP_H_ + +#include "vec.h" +#include <algorithm> + +namespace Glest { namespace Game { namespace Search { + +using Shared::Platform::uint32; + +typedef Shared::Math::Vec2i Point; + +struct Rectangle { + Rectangle () : x(0), y(0), w(0), h(0) {} + Rectangle (int x, int y, int w, int h) : x(x), y(y), w(w), h(h) {} + int x, y, w, h; +}; +/* +ostream& operator<<(ostream &lhs, Point &rhs) { + lhs << "(" << rhs.x << "," << rhs.y << ")"; + return lhs; +}*/ + +const Point invalidPos(-1,-1); + +// ===================================================== +// class InfluenceMap +// ===================================================== +template<typename iType, typename MapType> class InfluenceMap { +public: + InfluenceMap(Rectangle b, iType def) : x(b.x), y(b.y), w(b.w), h(b.h), def(def) {} + + iType getInfluence(Point pos) { + pos = translate(pos); + if ( pos != invalidPos ) { + return static_cast<MapType*>(this)->get(pos); + } + return def; + } + bool setInfluence(Point pos, iType val) { + pos = translate(pos); + if ( pos != invalidPos ) { + static_cast<MapType*>(this)->set(pos,val); + return true; + } + return false; + } + Point translate(Point p) { + const int nx = p.x - x; + const int ny = p.y - y; + if ( nx >= 0 && ny >=0 && nx < w && ny < h ) { + return Point(nx,ny); + } + return invalidPos; + } +protected: + iType def; + int x,y,w,h; +}; + +// ===================================================== +// class TypeMap +// ===================================================== +template<typename type = float> class TypeMap : public InfluenceMap<type, TypeMap<type> > { + friend class InfluenceMap<type, TypeMap<type> >; +public: + TypeMap(Rectangle b, type def) : InfluenceMap<type, TypeMap<type> >(b,def) { + data = new type[b.w*b.h]; + } + void zeroMap() { memset(data, 0, sizeof(type) * this->w * this->h); } + void clearMap(type val) { fill_n(data, this->w * this->h, val); } + +private: + type get(Point p) { return data[p.y * this->w + p.x]; } + void set(Point p, type v) { data[p.y * this->w + p.x] = v; } + type *data; +}; + +// ===================================================== +// class PatchMap +// ===================================================== +/** bit packed InfluenceMap, values are bit packed into 32 bit 'sections' (possibly padded) + * Not usefull for bits >= 7, just use TypeMap<uint8>, TypeMap<uint16> etc... + * bit wastage: + * bits == 1, 2 or 4: no wastage in full sections + * bits == 3, 5 or 6: 2 bits wasted per full section + */ +template<int bits> class PatchMap : public InfluenceMap<uint32, PatchMap<bits> > { + friend class InfluenceMap<uint32, PatchMap<bits> >; +public: + PatchMap(Rectangle b, uint32 def) : InfluenceMap<uint32,PatchMap<bits> >(b,def) { + //cout << "PatchMap<" << bits << "> max_value = "<< max_value <<", [width = " << b.w << " height = " << b.h << "]\n"; + sectionsPerRow = b.w / sectionSize + 1; + //cout << "section size = " << sectionSize << ", sections per row = " << sectionsPerRow << endl; + data = new uint32[b.h * sectionsPerRow]; + } + void zeroMap() { memset(data, 0, sizeof(uint32) * sectionsPerRow * this->h); } + void clearMap(uint32 val) { +// assert(val < max_value); + data[0] = 0; + for ( int i=0; i < sectionSize - 1; ++i) { + data[0] |= val; + data[0] <<= bits; + } + data[0] |= val; + for ( int i=1; i < sectionsPerRow; ++i ) { + data[i] = data[0]; + } + const int rowSize = sectionsPerRow * sizeof(uint32); + for ( int i=1; i < this->h; ++i ) { + uint32 *ptr = &data[i * sectionsPerRow]; + memcpy(ptr, data, rowSize); + } + } +private: + uint32 get(Point p) { + int sectionNdx = p.y * sectionsPerRow + p.x / sectionSize; + int subSectionNdx = p.x % sectionSize; + uint32 val = (data[sectionNdx] >> (subSectionNdx * bits)) & max_value; + //cout << "get(" << p.x << "," << p.y << "). section=" << sectionNdx + // << ", subsection=" << subSectionNdx << " = " << val <<endl; + return val; + } + void set(Point p, uint32 v) { + if (v > max_value) { //clamp? + v = max_value; + } + int sectionNdx = p.y * sectionsPerRow + p.x / sectionSize; + int subSectionNdx = p.x % sectionSize; + uint32 val = v << bits * subSectionNdx; + uint32 mask = max_value << bits * subSectionNdx; + data[sectionNdx] &= ~mask; // blot out old value + data[sectionNdx] |= val; // put in the new value + }/* + void logSection(int s) { + cout << "["; + for ( int j = 31; j >= 0; --j ) { + uint32 bitmask = 1 << j; + if ( data[s] & bitmask ) cout << "1"; + else cout << "0"; + if ( j && j % bits == 0 ) cout << " "; + } + cout << "]" << endl; + }*/ + static const uint32 max_value = (1 << bits) - 1; + static const int sectionSize = 32 / bits; + int sectionsPerRow; + uint32 *data; +}; + +// ===================================================== +// class FlowMap +// ===================================================== +/** bit packed 'offset' map, where offset is of the form -1 <= x <= 1 && -1 <= y <= 1 */ +class FlowMap : public InfluenceMap<Point, FlowMap> { + friend class InfluenceMap<Point, FlowMap>; +private: + Point expand(uint32 v) { + Point res(0,0); + if ( v & 8 ) { res.x = -1; } + else if ( v & 4 ) { res.x = 1; } + if ( v & 2 ) { res.y = -1; } + else if ( v & 1 ) { res.y = 1; } + return res; + } + uint32 pack(Point v) { + uint32 res = 0; + if ( v.x ) { res = 1 << (v.x > 0 ? 2 : 3); } + if ( v.y ) { res |= 1 << (v.y > 0 ? 0 : 1); } + return res; + } +public: + FlowMap(Rectangle b, Point def) : InfluenceMap<Point,FlowMap>(b,def) { + blocksPerRow = b.w / 8 + 1; + data = new uint32[b.h * blocksPerRow]; + } + void zeroMap() { memset(data, 0, sizeof(uint32) * blocksPerRow * h); } + void clearMap(Point val) { + uint32 v = pack(val); + data[0] = 0; + for ( int i=0; i < 7; ++i ) { + data[0] |= v; + data[0] <<= 4; + } + data[0] |= v; + for ( int i=1; i < blocksPerRow; ++i ) { + data[i] = data[0]; + } + const int rowSize = block... [truncated message content] |