Page MenuHomeWildfire Games
Differential D1832 Diff 7781 source/simulation2/helpers/HierarchicalPathfinder.h

Changeset View

Standalone View

View Options

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 region, without 0
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