Differential D14 Diff 11702 source/simulation2/helpers/VertexPathfinder.cpp

Changeset View

Standalone View

source/simulation2/helpers/VertexPathfinder.cpp

Show All 36 Lines
#include "lib/timer.h"		#include "lib/timer.h"
#include "ps/Profile.h"		#include "ps/Profile.h"
#include "renderer/Scene.h"		#include "renderer/Scene.h"
#include "simulation2/components/ICmpObstructionManager.h"		#include "simulation2/components/ICmpObstructionManager.h"
#include "simulation2/helpers/PriorityQueue.h"		#include "simulation2/helpers/PriorityQueue.h"
#include "simulation2/helpers/Render.h"		#include "simulation2/helpers/Render.h"
#include "simulation2/system/SimContext.h"		#include "simulation2/system/SimContext.h"


		thread_local std::vector<SOverlayLine> VertexPathfinder::m_DebugOverlayShortPathLines;
		thread_local std::mutex VertexPathfinder::m_DebugMutex;
		thread_local std::vector<Edge> VertexPathfinder::m_EdgesUnaligned;
		thread_local std::vector<EdgeAA> VertexPathfinder::m_EdgesLeft;
		thread_local std::vector<EdgeAA> VertexPathfinder::m_EdgesRight;
		thread_local std::vector<EdgeAA> VertexPathfinder::m_EdgesBottom;
		thread_local std::vector<EdgeAA> VertexPathfinder::m_EdgesTop;
		thread_local std::vector<Vertex> VertexPathfinder::m_Vertexes;
		thread_local std::vector<Edge> VertexPathfinder::m_Edges;
		thread_local std::vector<Square> VertexPathfinder::m_EdgeSquares;

/* Quadrant optimisation:		/* Quadrant optimisation:
* (loosely based on GPG2 "Optimizing Points-of-Visibility Pathfinding")		* (loosely based on GPG2 "Optimizing Points-of-Visibility Pathfinding")
*		*
* Consider the vertex ("@") at a corner of an axis-aligned rectangle ("#"):		* Consider the vertex ("@") at a corner of an axis-aligned rectangle ("#"):
*		*
* TL : TR		* TL : TR
* :		* :
* ####@ - - -		* ####@ - - -
▲ Show 20 Lines • Show All 385 Lines • ▼ Show 20 Lines	static void AddTerrainEdges(std::vector<Edge>& edges, std::vector<Vertex>& vertexes,
}		}
}		}

static void SplitAAEdges(const CFixedVector2D& a,		static void SplitAAEdges(const CFixedVector2D& a,
const std::vector<Edge>& edges,		const std::vector<Edge>& edges,
const std::vector<Square>& squares,		const std::vector<Square>& squares,
std::vector<Edge>& edgesUnaligned,		std::vector<Edge>& edgesUnaligned,
std::vector<EdgeAA>& edgesLeft, std::vector<EdgeAA>& edgesRight,		std::vector<EdgeAA>& edgesLeft, std::vector<EdgeAA>& edgesRight,
std::vector<EdgeAA>& edgesBottom, std::vector<EdgeAA>& edgesTop)		std::vector<EdgeAA>& edgesBottom, std::vector<EdgeAA>& edgesTop)
		StanUnsubmitted Not Done Inline Actions Couldn't we pass an object/ struct here instead ? Stan: Couldn't we pass an object/ struct here instead ?
{		{

for (const Square& square : squares)		for (const Square& square : squares)
{		{
if (a.X <= square.p0.X)		if (a.X <= square.p0.X)
edgesLeft.emplace_back(EdgeAA{ square.p0, square.p1.Y });		edgesLeft.emplace_back(EdgeAA{ square.p0, square.p1.Y });
if (a.X >= square.p1.X)		if (a.X >= square.p1.X)
edgesRight.emplace_back(EdgeAA{ square.p1, square.p0.Y });		edgesRight.emplace_back(EdgeAA{ square.p1, square.p0.Y });
▲ Show 20 Lines • Show All 135 Lines • ▼ Show 20 Lines	for (size_t i = 0; i < squares.size(); ++i)
CFixedVector2D hd1(squares[i].hw + pathfindClearance + EDGE_EXPAND_DELTA, -(squares[i].hh + pathfindClearance + EDGE_EXPAND_DELTA));		CFixedVector2D hd1(squares[i].hw + pathfindClearance + EDGE_EXPAND_DELTA, -(squares[i].hh + pathfindClearance + EDGE_EXPAND_DELTA));

// Check whether this is an axis-aligned square		// Check whether this is an axis-aligned square
bool aa = (u.X == fixed::FromInt(1) && u.Y == fixed::Zero() && v.X == fixed::Zero() && v.Y == fixed::FromInt(1));		bool aa = (u.X == fixed::FromInt(1) && u.Y == fixed::Zero() && v.X == fixed::Zero() && v.Y == fixed::FromInt(1));

Vertex vert;		Vertex vert;
vert.status = Vertex::UNEXPLORED;		vert.status = Vertex::UNEXPLORED;
vert.quadInward = QUADRANT_NONE;		vert.quadInward = QUADRANT_NONE;
vert.quadOutward = QUADRANT_ALL;		vert.quadOutward = QUADRANT_ALL;

		StanUnsubmitted Not Done Inline Actions @vladislavbelov Good usage for clamp below, no ? Stan: @vladislavbelov Good usage for clamp below, no ?
vert.p.X = center.X - hd0.Dot(u);		vert.p.X = center.X - hd0.Dot(u);
vert.p.Y = center.Y + hd0.Dot(v);		vert.p.Y = center.Y + hd0.Dot(v);
if (aa)		if (aa)
{		{
vert.quadInward = QUADRANT_BR;		vert.quadInward = QUADRANT_BR;
vert.quadOutward = (~vert.quadInward) & 0xF;		vert.quadOutward = (~vert.quadInward) & 0xF;
}		}
if (vert.p.X >= rangeXMin && vert.p.Y >= rangeZMin && vert.p.X <= rangeXMax && vert.p.Y <= rangeZMax)		if (vert.p.X >= rangeXMin && vert.p.Y >= rangeZMin && vert.p.X <= rangeXMax && vert.p.Y <= rangeZMax)
▲ Show 20 Lines • Show All 239 Lines • ▼ Show 20 Lines	WaypointPath VertexPathfinder::ComputeShortPath(const ShortPathRequest& request, CmpPtr<ICmpObstructionManager> cmpObstructionManager) const

return path;		return path;
}		}

void VertexPathfinder::DebugRenderGoal(const CSimContext& simContext, const PathGoal& goal) const		void VertexPathfinder::DebugRenderGoal(const CSimContext& simContext, const PathGoal& goal) const
{		{
if (!m_DebugOverlay)		if (!m_DebugOverlay)
return;		return;
		std::lock_guard<std::mutex> lock(m_DebugMutex);

m_DebugOverlayShortPathLines.clear();		m_DebugOverlayShortPathLines.clear();

// Render the goal shape		// Render the goal shape
m_DebugOverlayShortPathLines.push_back(SOverlayLine());		m_DebugOverlayShortPathLines.push_back(SOverlayLine());
m_DebugOverlayShortPathLines.back().m_Color = CColor(1, 0, 0, 1);		m_DebugOverlayShortPathLines.back().m_Color = CColor(1, 0, 0, 1);
switch (goal.type)		switch (goal.type)
{		{
Show All 17 Lines	switch (goal.type)
}		}
}		}
}		}

void VertexPathfinder::DebugRenderGraph(const CSimContext& simContext, const std::vector<Vertex>& vertexes, const std::vector<Edge>& edges, const std::vector<Square>& edgeSquares) const		void VertexPathfinder::DebugRenderGraph(const CSimContext& simContext, const std::vector<Vertex>& vertexes, const std::vector<Edge>& edges, const std::vector<Square>& edgeSquares) const
{		{
if (!m_DebugOverlay)		if (!m_DebugOverlay)
return;		return;
		std::lock_guard<std::mutex> lock(m_DebugMutex);

#define PUSH_POINT(p) STMT(xz.push_back(p.X.ToFloat()); xz.push_back(p.Y.ToFloat()))		#define PUSH_POINT(p) STMT(xz.push_back(p.X.ToFloat()); xz.push_back(p.Y.ToFloat()))
// Render the vertexes as little Pac-Man shapes to indicate quadrant direction		// Render the vertexes as little Pac-Man shapes to indicate quadrant direction
for (size_t i = 0; i < vertexes.size(); ++i)		for (size_t i = 0; i < vertexes.size(); ++i)
{		{
m_DebugOverlayShortPathLines.emplace_back();		m_DebugOverlayShortPathLines.emplace_back();
m_DebugOverlayShortPathLines.back().m_Color = CColor(1, 1, 0, 1);		m_DebugOverlayShortPathLines.back().m_Color = CColor(1, 1, 0, 1);

▲ Show 20 Lines • Show All 81 Lines • ▼ Show 20 Lines	void VertexPathfinder::DebugRenderEdges(const CSimContext& UNUSED(simContext), bool UNUSED(visible), CFixedVector2D UNUSED(curr), CFixedVector2D UNUSED(npos)) const
*/		*/
}		}

void VertexPathfinder::RenderSubmit(SceneCollector& collector)		void VertexPathfinder::RenderSubmit(SceneCollector& collector)
{		{
if (!m_DebugOverlay)		if (!m_DebugOverlay)
return;		return;

		std::lock_guard<std::mutex> lock(m_DebugMutex);
for (size_t i = 0; i < m_DebugOverlayShortPathLines.size(); ++i)		for (size_t i = 0; i < m_DebugOverlayShortPathLines.size(); ++i)
collector.Submit(&m_DebugOverlayShortPathLines[i]);		collector.Submit(&m_DebugOverlayShortPathLines[i]);
		StanUnsubmitted Not Done Inline Actions Do you need to lock more than the swap? Same question for the functions above Stan: Do you need to lock more than the swap? Same question for the functions above
		wraitiiAuthorUnsubmitted Done Inline Actions Yes, or the multiple vertex pathfinders will muck it up. The lock is really not that necessary for the swap. Not that it matters, it only locks if m_DebugOverlay, so it's usually trivially fast. wraitii: Yes, or the multiple vertex pathfinders will muck it up. The lock is really not that necessary…
}		}