Differential D14 Diff 14406 source/simulation2/helpers/LongPathfinder.h

Changeset View

Standalone View

source/simulation2/helpers/LongPathfinder.h

/* Copyright (C) 2017 Wildfire Games.		/* Copyright (C) 2020 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 "Pathfinding.h"		#include "Pathfinding.h"
		vladislavbelovUnsubmitted Not Done Inline Actions Wrong order and empty line. 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 <mutex>

/**		/**
* Represents the 2D coordinates of a tile.		* Represents the 2D coordinates of a tile.
* The i/j components are packed into a single u32, since we usually use these		* The i/j components are packed into a single u32, since we usually use these
* objects for equality comparisons and the VC2010 optimizer doesn't seem to automatically		* objects for equality comparisons and the VC2010 optimizer doesn't seem to automatically
* compare two u16s in a single operation.		* compare two u16s in a single operation.
* TODO: maybe VC2012 will?		* TODO: maybe VC2012 will?
*/		*/
struct TileID		struct TileID
▲ Show 20 Lines • Show All 181 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;
		kilobugUnsubmitted Not Done Inline Actions Making 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…
		StanUnsubmitted Done Inline Actions Same here. Stan: Same here.
		Kuba386Unsubmitted Done Inline Actions Yeah, 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…
		wraitiiAuthorUnsubmitted Not Done Inline Actions AFAIK 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