Differential D1835 Diff 8155 source/simulation2/helpers/HierarchicalPathfinder.h

Changeset View

Standalone View

source/simulation2/helpers/HierarchicalPathfinder.h

Show All 29 Lines
* Deals with connectivity (can point A reach point B?).		* 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.)		* By design, there can never be an edge between two regions in the same chunk.
		*
		* Those fixed-size chunks are used to efficiently compute "global regions" by effectively flood-filling.
		* Those can then be used to immediately determine if two reachables points are connected.
		*
		* The main use of this class is to convert an arbitrary PathGoal to a reachable navcell.
		* This happens in MakeGoalReachable.
*		*
* Since regions are typically fairly large, it is possible to determine
* connectivity between any two navcells by mapping them onto their appropriate
* region and then doing a relatively small graph search.
*/		*/

#ifdef TEST		#ifdef TEST
class TestCmpPathfinder;		class TestCmpPathfinder;
class TestHierarchicalPathfinder;		class TestHierarchicalPathfinder;
#endif		#endif

class HierarchicalOverlay;		class HierarchicalOverlay;
class SceneCollector;		class SceneCollector;

class HierarchicalPathfinder		class HierarchicalPathfinder
{		{
#ifdef TEST		#ifdef TEST
friend class TestCmpPathfinder;		friend class TestCmpPathfinder;
friend class TestHierarchicalPathfinder;		friend class TestHierarchicalPathfinder;
#endif		#endif
public:		public:
		typedef u32 GlobalRegionID;

struct RegionID		struct RegionID
{		{
u8 ci, cj; // chunk ID		u8 ci, cj; // chunk ID
u16 r; // unique-per-chunk local region ID		u16 r; // unique-per-chunk local region ID

RegionID(u8 ci, u8 cj, u16 r) : ci(ci), cj(cj), r(r) { }		RegionID(u8 ci, u8 cj, u16 r) : ci(ci), cj(cj), r(r) { }

bool operator<(const RegionID& b) const		bool operator<(const RegionID& b) const
Show All 25 Lines	public:
void Recompute(Grid<NavcellData>* passabilityGrid,		void Recompute(Grid<NavcellData>* passabilityGrid,
const std::map<std::string, pass_class_t>& nonPathfindingPassClassMasks,		const std::map<std::string, pass_class_t>& nonPathfindingPassClassMasks,
const std::map<std::string, pass_class_t>& pathfindingPassClassMasks);		const std::map<std::string, pass_class_t>& pathfindingPassClassMasks);

void Update(Grid<NavcellData>* grid, const Grid<u8>& dirtinessGrid);		void Update(Grid<NavcellData>* grid, const Grid<u8>& dirtinessGrid);

RegionID Get(u16 i, u16 j, pass_class_t passClass) const;		RegionID Get(u16 i, u16 j, pass_class_t passClass) const;

		GlobalRegionID GetGlobalRegion(u16 i, u16 j, pass_class_t passClass) const;
		GlobalRegionID GetGlobalRegion(RegionID region, pass_class_t passClass) const;

/**		/**
* Updates @p goal so that it's guaranteed to be reachable from the navcell		* Updates @p goal so that it's guaranteed to be reachable from the navcell
* @p i0, @p j0 (which is assumed to be on a passable navcell).		* @p i0, @p j0 (which is assumed to be on a passable navcell).
*		*
* If the goal is not reachable, it is replaced with a point goal nearest to		* If the goal is not reachable, it is replaced with a point goal nearest to
* the goal center.		* the goal center.
*		*
* In the case of a non-point reachable goal, it is replaced with a point goal		* In the case of a non-point reachable goal, it is replaced with a point goal
▲ Show 20 Lines • Show All 55 Lines • ▼ Show 20 Lines	#endif
};		};

typedef std::map<RegionID, std::set<RegionID> > EdgesMap;		typedef std::map<RegionID, std::set<RegionID> > EdgesMap;

void ComputeNeighbors(EdgesMap& edges, Chunk& a, Chunk& b, bool transpose, bool opposite) const;		void ComputeNeighbors(EdgesMap& edges, Chunk& a, Chunk& b, bool transpose, bool opposite) const;
void RecomputeAllEdges(pass_class_t passClass, EdgesMap& edges);		void RecomputeAllEdges(pass_class_t passClass, EdgesMap& edges);
void UpdateEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges);		void UpdateEdges(u8 ci, u8 cj, pass_class_t passClass, EdgesMap& edges);

		void UpdateGlobalRegions(const std::map<pass_class_t, std::vector<RegionID> >& needNewGlobalRegionMap);

void FindReachableRegions(RegionID from, std::set<RegionID>& reachable, pass_class_t passClass) const;		void FindReachableRegions(RegionID from, std::set<RegionID>& reachable, pass_class_t passClass) const;

void FindPassableRegions(std::set<RegionID>& regions, pass_class_t passClass) const;		void FindPassableRegions(std::set<RegionID>& regions, pass_class_t passClass) const;

		void FindGoalRegions(u16 gi, u16 gj, const PathGoal& goal, std::set<RegionID>& regions, pass_class_t passClass) const;

/**		/**
* Updates @p iGoal and @p jGoal to the navcell that is the nearest to the		* Updates @p iGoal and @p jGoal to the navcell that is the nearest to the
* initial goal coordinates, in one of the given @p regions.		* initial goal coordinates, in one of the given @p regions.
* (Assumes @p regions is non-empty.)		* (Assumes @p regions is non-empty.)
*/		*/
void FindNearestNavcellInRegions(const std::set<RegionID>& regions, u16& iGoal, u16& jGoal, pass_class_t passClass) const;		void FindNearestNavcellInRegions(const std::set<RegionID>& regions, u16& iGoal, u16& jGoal, pass_class_t passClass) const;

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;
u8 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;

		std::map<pass_class_t, std::map<RegionID, GlobalRegionID> > m_GlobalRegions;
		ItmsUnsubmitted Not Done Inline Actions `> >` Itms: `> >`
		GlobalRegionID m_NextGlobalRegionID;

// 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);
HierarchicalOverlay* m_DebugOverlay;		HierarchicalOverlay* m_DebugOverlay;
const CSimContext* m_SimContext; // Used for drawing the debug lines		const CSimContext* m_SimContext; // Used for drawing the debug lines

public:		public:
▲ Show 20 Lines • Show All 42 Lines • Show Last 20 Lines