Changeset View
Changeset View
Standalone View
Standalone View
source/simulation2/helpers/LongPathfinder.h
Show All 12 Lines | |||||
* | * | ||||
* You should have received a copy of the GNU General Public License | * You should have received a copy of the GNU General Public License | ||||
* along with 0 A.D. If not, see <http://www.gnu.org/licenses/>. | * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>. | ||||
*/ | */ | ||||
#ifndef INCLUDED_LONGPATHFINDER | #ifndef INCLUDED_LONGPATHFINDER | ||||
#define INCLUDED_LONGPATHFINDER | #define INCLUDED_LONGPATHFINDER | ||||
#include "Pathfinding.h" | #include "Pathfinding.h" | ||||
vladislavbelov: Wrong order and empty line. | |||||
#include "graphics/Overlay.h" | #include "graphics/Overlay.h" | ||||
#include "renderer/Scene.h" | #include "renderer/Scene.h" | ||||
#include "renderer/TerrainOverlay.h" | #include "renderer/TerrainOverlay.h" | ||||
#include "simulation2/helpers/Grid.h" | #include "simulation2/helpers/Grid.h" | ||||
#include "simulation2/helpers/PriorityQueue.h" | #include "simulation2/helpers/PriorityQueue.h" | ||||
#include <map> | #include <map> | ||||
▲ Show 20 Lines • Show All 119 Lines • ▼ Show 20 Lines | struct PathfinderState | ||||
// (there's no explicit closed list; it's encoded in PathfindTile) | // (there's no explicit closed list; it's encoded in PathfindTile) | ||||
PathfindTileGrid* tiles; | PathfindTileGrid* tiles; | ||||
Grid<NavcellData>* terrain; | Grid<NavcellData>* terrain; | ||||
PathCost hBest; // heuristic of closest discovered tile to goal | PathCost hBest; // heuristic of closest discovered tile to goal | ||||
u16 iBest, jBest; // closest tile | u16 iBest, jBest; // closest tile | ||||
JumpPointCache* jpc; | const JumpPointCache* jpc; | ||||
}; | }; | ||||
class LongOverlay; | class LongOverlay; | ||||
class HierarchicalPathfinder; | class HierarchicalPathfinder; | ||||
class LongPathfinder | class LongPathfinder | ||||
{ | { | ||||
public: | public: | ||||
LongPathfinder(); | LongPathfinder(); | ||||
~LongPathfinder(); | ~LongPathfinder(); | ||||
void SetDebugOverlay(bool enabled); | void SetDebugOverlay(bool enabled); | ||||
void SetDebugPath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) | void SetDebugPath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass) | ||||
{ | { | ||||
if (!m_DebugOverlay) | if (!m_Debug.Overlay) | ||||
return; | return; | ||||
SAFE_DELETE(m_DebugGrid); | SAFE_DELETE(m_Debug.Grid); | ||||
delete m_DebugPath; | delete m_Debug.Path; | ||||
m_DebugPath = new WaypointPath(); | m_Debug.Path = new WaypointPath(); | ||||
ComputePath(hierPath, x0, z0, goal, passClass, *m_DebugPath); | ComputePath(hierPath, x0, z0, goal, passClass, *m_Debug.Path); | ||||
m_DebugPassClass = passClass; | m_Debug.PassClass = passClass; | ||||
} | } | ||||
void Reload(Grid<NavcellData>* passabilityGrid) | void Reload(Grid<NavcellData>* passabilityGrid) | ||||
{ | { | ||||
m_Grid = passabilityGrid; | m_Grid = passabilityGrid; | ||||
ASSERT(passabilityGrid->m_H == passabilityGrid->m_W); | ASSERT(passabilityGrid->m_H == passabilityGrid->m_W); | ||||
m_GridSize = passabilityGrid->m_W; | m_GridSize = passabilityGrid->m_W; | ||||
Show All 30 Lines | public: | ||||
{ | { | ||||
GetDebugDataJPS(steps, time, grid); | GetDebugDataJPS(steps, time, grid); | ||||
} | } | ||||
Grid<NavcellData>* m_Grid; | Grid<NavcellData>* m_Grid; | ||||
u16 m_GridSize; | u16 m_GridSize; | ||||
// Debugging - output from last pathfind operation. | // Debugging - output from last pathfind operation. | ||||
// mutable as making these const would require a lot of boilerplate code | struct Debug | ||||
// and they do not change the behavioural const-ness of the pathfinder. | { | ||||
mutable LongOverlay* m_DebugOverlay; | // Atomic - used to toggle debugging. | ||||
mutable PathfindTileGrid* m_DebugGrid; | std::atomic<LongOverlay*> Overlay = nullptr; | ||||
mutable u32 m_DebugSteps; | // Mutable - set by ComputeJPSPath (thus possibly from different threads). | ||||
mutable double m_DebugTime; | // Synchronized via mutex if necessary. | ||||
mutable PathGoal m_DebugGoal; | mutable PathfindTileGrid* Grid = nullptr; | ||||
mutable WaypointPath* m_DebugPath; | mutable u32 Steps; | ||||
mutable pass_class_t m_DebugPassClass; | mutable double Time; | ||||
mutable PathGoal Goal; | |||||
WaypointPath* Path = nullptr; | |||||
pass_class_t PassClass; | |||||
} m_Debug; | |||||
private: | private: | ||||
PathCost CalculateHeuristic(int i, int j, int iGoal, int jGoal) const; | PathCost CalculateHeuristic(int i, int j, int iGoal, int jGoal) const; | ||||
void ProcessNeighbour(int pi, int pj, int i, int j, PathCost pg, PathfinderState& state) const; | void ProcessNeighbour(int pi, int pj, int i, int j, PathCost pg, PathfinderState& state) const; | ||||
/** | /** | ||||
* JPS algorithm helper functions | * JPS algorithm helper functions | ||||
* @param detectGoal is not used if m_UseJPSCache is true | * @param detectGoal is not used if m_UseJPSCache is true | ||||
Show All 28 Lines | private: | ||||
void GenerateSpecialMap(pass_class_t passClass, std::vector<CircularRegion> excludedRegions); | void GenerateSpecialMap(pass_class_t passClass, std::vector<CircularRegion> excludedRegions); | ||||
bool m_UseJPSCache; | bool m_UseJPSCache; | ||||
// Mutable may be used here as caching does not change the external const-ness of the Long Range pathfinder. | // Mutable may be used here as caching does not change the external const-ness of the Long Range pathfinder. | ||||
// This is thread-safe as it is order independent (no change in the output of the function for a given set of params). | // This is thread-safe as it is order independent (no change in the output of the function for a given set of params). | ||||
// Obviously, this means that the cache should actually be a cache and not return different results | // Obviously, this means that the cache should actually be a cache and not return different results | ||||
// from what would happen if things hadn't been cached. | // from what would happen if things hadn't been cached. | ||||
mutable std::map<pass_class_t, shared_ptr<JumpPointCache> > m_JumpPointCache; | mutable std::map<pass_class_t, shared_ptr<JumpPointCache> > m_JumpPointCache; | ||||
}; | }; | ||||
Not Done Inline ActionsMaking the cache thread local means that some computation will be done once per thread, instead of once in total. I'm not sure how many of those computations are concerned, and how expensive they are, but with 8 cores some may be done 7x. kilobug: Making the cache thread local means that some computation will be done once per thread, instead… | |||||
Done Inline ActionsSame here. Stan: Same here. | |||||
Done Inline ActionsYeah, it's just not trivial to address these problems, I need to get more familiar with both patch's and 0AD's codebase to understand it better. Kuba386: Yeah, it's just not trivial to address these problems, I need to get more familiar with both… | |||||
Not Done Inline ActionsAFAIK the jump point cache is unused, so it should be completely irrelevant. wraitii: AFAIK the jump point cache is unused, so it should be completely irrelevant. | |||||
/** | |||||
* Terrain overlay for pathfinder debugging. | |||||
* Renders a representation of the most recent pathfinding operation. | |||||
*/ | |||||
class LongOverlay : public TerrainTextureOverlay | |||||
{ | |||||
public: | |||||
LongPathfinder& m_Pathfinder; | |||||
LongOverlay(LongPathfinder& pathfinder) : | |||||
TerrainTextureOverlay(Pathfinding::NAVCELLS_PER_TILE), m_Pathfinder(pathfinder) | |||||
{ | |||||
} | |||||
virtual void BuildTextureRGBA(u8* data, size_t w, size_t h) | |||||
{ | |||||
// Grab the debug data for the most recently generated path | |||||
u32 steps; | |||||
double time; | |||||
Grid<u8> debugGrid; | |||||
m_Pathfinder.GetDebugData(steps, time, debugGrid); | |||||
// Render navcell passability | |||||
u8* p = data; | |||||
for (size_t j = 0; j < h; ++j) | |||||
{ | |||||
for (size_t i = 0; i < w; ++i) | |||||
{ | |||||
SColor4ub color(0, 0, 0, 0); | |||||
if (!IS_PASSABLE(m_Pathfinder.m_Grid->get((int)i, (int)j), m_Pathfinder.m_DebugPassClass)) | |||||
color = SColor4ub(255, 0, 0, 127); | |||||
if (debugGrid.m_W && debugGrid.m_H) | |||||
{ | |||||
u8 n = debugGrid.get((int)i, (int)j); | |||||
if (n == 1) | |||||
color = SColor4ub(255, 255, 0, 127); | |||||
else if (n == 2) | |||||
color = SColor4ub(0, 255, 0, 127); | |||||
if (m_Pathfinder.m_DebugGoal.NavcellContainsGoal(i, j)) | |||||
color = SColor4ub(0, 0, 255, 127); | |||||
} | |||||
*p++ = color.R; | |||||
*p++ = color.G; | |||||
*p++ = color.B; | |||||
*p++ = color.A; | |||||
} | |||||
} | |||||
// Render the most recently generated path | |||||
if (m_Pathfinder.m_DebugPath && !m_Pathfinder.m_DebugPath->m_Waypoints.empty()) | |||||
{ | |||||
std::vector<Waypoint>& waypoints = m_Pathfinder.m_DebugPath->m_Waypoints; | |||||
u16 ip = 0, jp = 0; | |||||
for (size_t k = 0; k < waypoints.size(); ++k) | |||||
{ | |||||
u16 i, j; | |||||
Pathfinding::NearestNavcell(waypoints[k].x, waypoints[k].z, i, j, m_Pathfinder.m_GridSize, m_Pathfinder.m_GridSize); | |||||
if (k == 0) | |||||
{ | |||||
ip = i; | |||||
jp = j; | |||||
} | |||||
else | |||||
{ | |||||
bool firstCell = true; | |||||
do | |||||
{ | |||||
if (data[(jp*w + ip)*4+3] == 0) | |||||
{ | |||||
data[(jp*w + ip)*4+0] = 0xFF; | |||||
data[(jp*w + ip)*4+1] = 0xFF; | |||||
data[(jp*w + ip)*4+2] = 0xFF; | |||||
data[(jp*w + ip)*4+3] = firstCell ? 0xA0 : 0x60; | |||||
} | |||||
ip = ip < i ? ip+1 : ip > i ? ip-1 : ip; | |||||
jp = jp < j ? jp+1 : jp > j ? jp-1 : jp; | |||||
firstCell = false; | |||||
} | |||||
while (ip != i || jp != j); | |||||
} | |||||
} | |||||
} | |||||
} | |||||
}; | |||||
#endif // INCLUDED_LONGPATHFINDER | #endif // INCLUDED_LONGPATHFINDER |
Wildfire Games · Phabricator
Wrong order and empty line.