Changeset View
Changeset View
Standalone View
Standalone View
ps/trunk/source/simulation2/helpers/HierarchicalPathfinder.h
Show All 21 Lines | |||||
#include "renderer/TerrainOverlay.h" | #include "renderer/TerrainOverlay.h" | ||||
#include "Render.h" | #include "Render.h" | ||||
#include "graphics/SColor.h" | #include "graphics/SColor.h" | ||||
/** | /** | ||||
* Hierarchical pathfinder. | * Hierarchical pathfinder. | ||||
* | * | ||||
* It doesn't find shortest paths, but deals with connectivity. | * Deals with connectivity (can point A reach point B?). | ||||
* | * | ||||
* The navcell-grid representation of the map is split into fixed-size chunks. | * The navcell-grid representation of the map is split into fixed-size chunks. | ||||
* Within a chunk, each maximal set of adjacently-connected passable navcells | * Within a chunk, each maximal set of adjacently-connected passable navcells | ||||
* is defined as a region. | * is defined as a region. | ||||
* Each region is a vertex in the hierarchical pathfinder's graph. | * Each region is a vertex in the hierarchical pathfinder's graph. | ||||
* When two regions in adjacent chunks are connected by passable navcells, | * When two regions in adjacent chunks are connected by passable navcells, | ||||
* the graph contains an edge between the corresponding two vertexes. | * the graph contains an edge between the corresponding two vertexes. | ||||
* (There will never be an edge between two regions in the same chunk.) | * (There will never be an edge between two regions in the same chunk.) | ||||
▲ Show 20 Lines • Show All 88 Lines • ▼ Show 20 Lines | if (it != m_PassClassMasks.end()) | ||||
return it->second; | return it->second; | ||||
LOGERROR("Invalid passability class name '%s'", name.c_str()); | LOGERROR("Invalid passability class name '%s'", name.c_str()); | ||||
return 0; | return 0; | ||||
} | } | ||||
private: | private: | ||||
static const u8 CHUNK_SIZE = 96; // number of navcells per side | static const u8 CHUNK_SIZE = 96; // number of navcells per side | ||||
// TODO PATHFINDER: figure out best number. Probably 64 < n < 128 | // TODO: figure out best number. Probably 64 < n < 128 | ||||
struct Chunk | struct Chunk | ||||
{ | { | ||||
u8 m_ChunkI, m_ChunkJ; // chunk ID | u8 m_ChunkI, m_ChunkJ; // chunk ID | ||||
u16 m_NumRegions; // number of local region IDs (starting from 1) | std::vector<u16> m_RegionsID; // IDs of local regions, 0 (impassable) excluded | ||||
u16 m_Regions[CHUNK_SIZE][CHUNK_SIZE]; // local region ID per navcell | u16 m_Regions[CHUNK_SIZE][CHUNK_SIZE]; // local region ID per navcell | ||||
cassert(CHUNK_SIZE*CHUNK_SIZE/2 < 65536); // otherwise we could overflow m_NumRegions with a checkerboard pattern | cassert(CHUNK_SIZE*CHUNK_SIZE/2 < 65536); // otherwise we could overflow m_RegionsID with a checkerboard pattern | ||||
void InitRegions(int ci, int cj, Grid<NavcellData>* grid, pass_class_t passClass); | void InitRegions(int ci, int cj, Grid<NavcellData>* grid, pass_class_t passClass); | ||||
RegionID Get(int i, int j) const; | RegionID Get(int i, int j) const; | ||||
void RegionCenter(u16 r, int& i, int& j) const; | void RegionCenter(u16 r, int& i, int& j) const; | ||||
void RegionNavcellNearest(u16 r, int iGoal, int jGoal, int& iBest, int& jBest, u32& dist2Best) const; | void RegionNavcellNearest(u16 r, int iGoal, int jGoal, int& iBest, int& jBest, u32& dist2Best) const; | ||||
bool RegionNearestNavcellInGoal(u16 r, u16 i0, u16 j0, const PathGoal& goal, u16& iOut, u16& jOut, u32& dist2Best) const; | bool RegionNearestNavcellInGoal(u16 r, u16 i0, u16 j0, const PathGoal& goal, u16& iOut, u16& jOut, u32& dist2Best) const; | ||||
#ifdef TEST | #ifdef TEST | ||||
bool operator==(const Chunk& b) const | bool operator==(const Chunk& b) const | ||||
{ | { | ||||
return (m_ChunkI == b.m_ChunkI && m_ChunkJ == b.m_ChunkJ && m_NumRegions == b.m_NumRegions && memcmp(&m_Regions, &b.m_Regions, sizeof(u16) * CHUNK_SIZE * CHUNK_SIZE) == 0); | return (m_ChunkI == b.m_ChunkI && m_ChunkJ == b.m_ChunkJ && m_RegionsID.size() == b.m_RegionsID.size() && memcmp(&m_Regions, &b.m_Regions, sizeof(u16) * CHUNK_SIZE * CHUNK_SIZE) == 0); | ||||
} | } | ||||
#endif | #endif | ||||
}; | }; | ||||
typedef std::map<RegionID, std::set<RegionID> > EdgesMap; | typedef std::map<RegionID, std::set<RegionID> > EdgesMap; | ||||
void FindEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges); | void FindEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges); | ||||
Show All 11 Lines | #endif | ||||
const Chunk& GetChunk(u8 ci, u8 cj, pass_class_t passClass) const | const Chunk& GetChunk(u8 ci, u8 cj, pass_class_t passClass) const | ||||
{ | { | ||||
return m_Chunks.at(passClass).at(cj * m_ChunksW + ci); | return m_Chunks.at(passClass).at(cj * m_ChunksW + ci); | ||||
} | } | ||||
void FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid<u16>& grid) const; | void FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid<u16>& grid) const; | ||||
u16 m_W, m_H; | u16 m_W, m_H; | ||||
u16 m_ChunksW, m_ChunksH; | u8 m_ChunksW, m_ChunksH; | ||||
std::map<pass_class_t, std::vector<Chunk> > m_Chunks; | std::map<pass_class_t, std::vector<Chunk> > m_Chunks; | ||||
std::map<pass_class_t, EdgesMap> m_Edges; | std::map<pass_class_t, EdgesMap> m_Edges; | ||||
// Passability classes for which grids will be updated when calling Update | // Passability classes for which grids will be updated when calling Update | ||||
std::map<std::string, pass_class_t> m_PassClassMasks; | std::map<std::string, pass_class_t> m_PassClassMasks; | ||||
void AddDebugEdges(pass_class_t passClass); | void AddDebugEdges(pass_class_t passClass); | ||||
▲ Show 20 Lines • Show All 46 Lines • Show Last 20 Lines |
Wildfire Games · Phabricator