Differential D665 Diff 2696 source/simulation2/helpers/HierarchicalPathfinder.h

Changeset View

Standalone View

source/simulation2/helpers/HierarchicalPathfinder.h

Show All 18 Lines
#define INCLUDED_HIERPATHFINDER		#define INCLUDED_HIERPATHFINDER

#include "Pathfinding.h"		#include "Pathfinding.h"

#include "renderer/TerrainOverlay.h"		#include "renderer/TerrainOverlay.h"
#include "Render.h"		#include "Render.h"
#include "graphics/SColor.h"		#include "graphics/SColor.h"

		#include <unordered_set>

/**		/**
* Hierarchical pathfinder.		* Hierarchical pathfinder.
*		*
* It doesn't find shortest paths, but deals with connectivity.		* It doesn't find shortest paths, but deals with connectivity.
*		*
* 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.
Show All 34 Lines	struct RegionID
}		}

bool operator==(RegionID b) const		bool operator==(RegionID b) const
{		{
return ((ci == b.ci) && (cj == b.cj) && (r == b.r));		return ((ci == b.ci) && (cj == b.cj) && (r == b.r));
}		}
};		};

		struct RegionHash
		{
		inline size_t operator()(const RegionID& region) const
		{
		// Fowler-Noll-Vo hash function
		const unsigned char* p = reinterpret_cast<const unsigned char*>(&region);
		size_t h = 2166136261;

		for (unsigned int i = 0; i < sizeof(region); ++i)
		h = (h * 16777619) ^ p[i];

		return h;
		}
		};

HierarchicalPathfinder();		HierarchicalPathfinder();
~HierarchicalPathfinder();		~HierarchicalPathfinder();

void SetDebugOverlay(bool enabled, const CSimContext* simContext);		void SetDebugOverlay(bool enabled, const CSimContext* simContext);

// Non-pathfinding grids will never be recomputed on calling HierarchicalPathfinder::Update		// Non-pathfinding grids will never be recomputed on calling HierarchicalPathfinder::Update
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,
Show All 13 Lines	public:
* 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
* at the reachable navcell of the goal which is nearest to the starting navcell.		* at the reachable navcell of the goal which is nearest to the starting navcell.
*/		*/
void MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass);		void MakeGoalReachable(u16 i0, u16 j0, PathGoal& goal, pass_class_t passClass);

/**		/**
* Updates @p i, @p j (which is assumed to be an impassable navcell)		* Updates @p i, @p j (which is assumed to be an impassable navcell)
		FreagarachUnsubmitted Not Done Inline Actions -`.` Freagarach: -`.`
* to the nearest passable navcell.		* to the nearest passable navcell.
*/		*/
void FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass);		void FindNearestPassableNavcell(u16& i, u16& j, pass_class_t passClass);

/**		/**
* Generates the connectivity grid associated with the given pass_class		* Generates the connectivity grid associated with the given pass_class
*/		*/
Grid<u16> GetConnectivityGrid(pass_class_t passClass);		Grid<u16> GetConnectivityGrid(pass_class_t passClass);

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

pass_class_t GetPassabilityClass(const std::string& name) const		pass_class_t GetPassabilityClass(const std::string& name) const
{		{
auto it = m_PassClassMasks.find(name);		auto it = m_PassClassMasks.find(name);
		wraitiiAuthorUnsubmitted Not Done Inline Actions Is there a reason why you moved this above? wraitii: Is there a reason why you moved this above?
		causativeUnsubmitted Done Inline Actions Making it public. However, I don't need to use it if I use GetGlobalRegion. causative: Making it public. However, I don't need to use it if I use GetGlobalRegion.
if (it != m_PassClassMasks.end())		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:
Show All 18 Lines	struct Chunk

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

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

void FindReachableRegions(RegionID from, std::set<RegionID>& reachable, pass_class_t passClass);		void FindPassableRegions(std::unordered_set<RegionID, RegionHash>& regions, pass_class_t passClass);

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

/**		/**
* 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);		void FindNearestNavcellInRegions(const std::unordered_set<RegionID, RegionHash>& regions, u16& iGoal, u16& jGoal, pass_class_t passClass);

Chunk& GetChunk(u8 ci, u8 cj, pass_class_t passClass)		Chunk& GetChunk(u8 ci, u8 cj, pass_class_t passClass)
{		{
return m_Chunks[passClass].at(cj * m_ChunksW + ci);		return m_Chunks[passClass].at(cj * m_ChunksW + ci);
}		}

void FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid<u16>& grid);		void FillRegionOnGrid(const RegionID& region, pass_class_t passClass, u16 value, Grid<u16>& grid);

▲ Show 20 Lines • Show All 56 Lines • Show Last 20 Lines