Changeset View
Changeset View
Standalone View
Standalone View
source/simulation2/helpers/LongPathfinder.h
/* Copyright (C) 2017 Wildfire Games. | /* Copyright (C) 2019 Wildfire Games. | ||||
* This file is part of 0 A.D. | * This file is part of 0 A.D. | ||||
* | * | ||||
* 0 A.D. is free software: you can redistribute it and/or modify | * 0 A.D. is free software: you can redistribute it and/or modify | ||||
* it under the terms of the GNU General Public License as published by | * it under the terms of the GNU General Public License as published by | ||||
* the Free Software Foundation, either version 2 of the License, or | * the Free Software Foundation, either version 2 of the License, or | ||||
* (at your option) any later version. | * (at your option) any later version. | ||||
* | * | ||||
* 0 A.D. is distributed in the hope that it will be useful, | * 0 A.D. is distributed in the hope that it will be useful, | ||||
* but WITHOUT ANY WARRANTY; without even the implied warranty of | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||||
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||||
* GNU General Public License for more details. | * GNU General Public License for more details. | ||||
* | * | ||||
* 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 <mutex> | |||||
vladislavbelov: Wrong order and empty line. | |||||
#include "Pathfinding.h" | #include "Pathfinding.h" | ||||
#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/PriorityQueue.h" | #include "simulation2/helpers/PriorityQueue.h" | ||||
/** | /** | ||||
▲ Show 20 Lines • Show All 188 Lines • ▼ Show 20 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 | // Static and thread-local - we don't support threading debug code. | ||||
// and they do not change the behavioural const-ness of the pathfinder. | static thread_local LongOverlay* m_DebugOverlay; | ||||
mutable LongOverlay* m_DebugOverlay; | static thread_local PathfindTileGrid* m_DebugGrid; | ||||
mutable PathfindTileGrid* m_DebugGrid; | static thread_local u32 m_DebugSteps; | ||||
mutable u32 m_DebugSteps; | static thread_local double m_DebugTime; | ||||
mutable double m_DebugTime; | static thread_local PathGoal m_DebugGoal; | ||||
mutable PathGoal m_DebugGoal; | static thread_local WaypointPath* m_DebugPath; | ||||
mutable WaypointPath* m_DebugPath; | static thread_local pass_class_t m_DebugPassClass; | ||||
mutable pass_class_t m_DebugPassClass; | |||||
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 25 Lines | private: | ||||
/** | /** | ||||
* Generate a passability map, stored in the 16th bit of navcells, based on passClass, | * Generate a passability map, stored in the 16th bit of navcells, based on passClass, | ||||
* but with a set of impassable circular regions. | * but with a set of impassable circular regions. | ||||
*/ | */ | ||||
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. | |||||
// This is thread-safe as it is order independent (no change in the output of the function for a given set of params). | static thread_local 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. | |||||
// 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. | |||||
mutable std::map<pass_class_t, shared_ptr<JumpPointCache> > m_JumpPointCache; | |||||
}; | }; | ||||
/** | /** | ||||
* Terrain overlay for pathfinder debugging. | * Terrain overlay for pathfinder debugging. | ||||
* Renders a representation of the most recent pathfinding operation. | * Renders a representation of the most recent pathfinding operation. | ||||
*/ | */ | ||||
class LongOverlay : public TerrainTextureOverlay | class LongOverlay : public TerrainTextureOverlay | ||||
{ | { | ||||
▲ Show 20 Lines • Show All 84 Lines • Show Last 20 Lines |
Wildfire Games · Phabricator
Wrong order and empty line.