VertexPathfinder.cpp File Reference

Vertex-based algorithm for CCmpPathfinder. More...

#include "precompiled.h"
#include "VertexPathfinder.h"
#include "lib/timer.h"
#include "ps/Profile.h"
#include "renderer/Scene.h"
#include "simulation2/components/ICmpObstructionManager.h"
#include "simulation2/helpers/Grid.h"
#include "simulation2/helpers/PriorityQueue.h"
#include "simulation2/helpers/Render.h"
#include "simulation2/system/SimContext.h"
#include <mutex>

Include dependency graph for VertexPathfinder.cpp:

Classes
struct	SquareSort
	Functor for sorting edge-squares by approximate proximity to a fixed point. More...
struct	UnalignedEdgesSort
	Functor for sorting unaligned edges by approximate proximity to a fixed point. More...

Namespaces
namespace	anonymous_namespace{VertexPathfinder.cpp}

Macros
#define	PUSH_POINT(p)   STMT(xz.push_back(p.X.ToFloat()); xz.push_back(p.Y.ToFloat()))

Typedefs
typedef PriorityQueueHeap< u16, fixed, fixed >	VertexPriorityQueue

Functions
static bool	CheckVisibility (const CFixedVector2D &a, const CFixedVector2D &b, const std::vector< Edge > &edges)
	Check whether a ray from 'a' to 'b' crosses any of the edges. More...
static bool	CheckVisibilityLeft (const CFixedVector2D &a, const CFixedVector2D &b, const std::vector< EdgeAA > &edges)
static bool	CheckVisibilityRight (const CFixedVector2D &a, const CFixedVector2D &b, const std::vector< EdgeAA > &edges)
static bool	CheckVisibilityBottom (const CFixedVector2D &a, const CFixedVector2D &b, const std::vector< EdgeAA > &edges)
static bool	CheckVisibilityTop (const CFixedVector2D &a, const CFixedVector2D &b, const std::vector< EdgeAA > &edges)
static void	AddTerrainEdges (std::vector< Edge > &edges, std::vector< Vertex > &vertexes, int i0, int j0, int i1, int j1, pass_class_t passClass, const Grid< NavcellData > &grid)
	Add edges and vertexes to represent the boundaries between passable and impassable navcells (for impassable terrain). More...
static void	SplitAAEdges (const CFixedVector2D &a, const std::vector< Edge > &edges, const std::vector< Square > &squares, std::vector< Edge > &edgesUnaligned, std::vector< EdgeAA > &edgesLeft, std::vector< EdgeAA > &edgesRight, std::vector< EdgeAA > &edgesBottom, std::vector< EdgeAA > &edgesTop)

Variables
static std::mutex	anonymous_namespace{VertexPathfinder.cpp}::g_DebugMutex
VertexPathfinderDebugOverlay	g_VertexPathfinderDebugOverlay
static const u8	QUADRANT_NONE = 0
static const u8	QUADRANT_BL = 1
static const u8	QUADRANT_TR = 2
static const u8	QUADRANT_TL = 4
static const u8	QUADRANT_BR = 8
static const u8	QUADRANT_BLTR = QUADRANT_BL|QUADRANT_TR
static const u8	QUADRANT_TLBR = QUADRANT_TL|QUADRANT_BR
static const u8	QUADRANT_ALL = QUADRANT_BLTR|QUADRANT_TLBR
static const entity_pos_t	EDGE_EXPAND_DELTA = entity_pos_t::FromInt(1)/16

Detailed Description

Vertex-based algorithm for CCmpPathfinder.

Computes paths around the corners of rectangular obstructions.

Useful search term for this algorithm: "points of visibility".

Since we sometimes want to use this for avoiding moving units, there is no pre-computation - the whole visibility graph is effectively regenerated for each path, and it does A* over that graph.

This scales very poorly in the number of obstructions, so it should be used with a limited range and not exceedingly frequently.

Macro Definition Documentation

PUSH_POINT

#define PUSH_POINT

(

p

)

STMT(xz.push_back(p.X.ToFloat()); xz.push_back(p.Y.ToFloat()))

Typedef Documentation

VertexPriorityQueue

typedef PriorityQueueHeap<u16, fixed, fixed> VertexPriorityQueue

Function Documentation

AddTerrainEdges()

static void AddTerrainEdges ( std::vector< Edge > &  edges, std::vector< Vertex > &  vertexes, int  i0, int  j0, int  i1, int  j1, pass_class_t  passClass, const Grid< NavcellData > &  grid  )

static

Add edges and vertexes to represent the boundaries between passable and impassable navcells (for impassable terrain).

Navcells i0 <= i <= i1, j0 <= j <= j1 will be considered.

CheckVisibility()

static bool CheckVisibility ( const CFixedVector2D &  a, const CFixedVector2D &  b, const std::vector< Edge > &  edges  )

inlinestatic

Check whether a ray from 'a' to 'b' crosses any of the edges.

(Edges are one-sided so it's only considered a cross if going from front to back.)

CheckVisibilityBottom()

static bool CheckVisibilityBottom ( const CFixedVector2D &  a, const CFixedVector2D &  b, const std::vector< EdgeAA > &  edges  )

inlinestatic

CheckVisibilityLeft()

static bool CheckVisibilityLeft ( const CFixedVector2D &  a, const CFixedVector2D &  b, const std::vector< EdgeAA > &  edges  )

inlinestatic

CheckVisibilityRight()

static bool CheckVisibilityRight ( const CFixedVector2D &  a, const CFixedVector2D &  b, const std::vector< EdgeAA > &  edges  )

inlinestatic

CheckVisibilityTop()

static bool CheckVisibilityTop ( const CFixedVector2D &  a, const CFixedVector2D &  b, const std::vector< EdgeAA > &  edges  )

inlinestatic

SplitAAEdges()

static void SplitAAEdges ( const CFixedVector2D &  a, const std::vector< Edge > &  edges, const std::vector< Square > &  squares, std::vector< Edge > &  edgesUnaligned, std::vector< EdgeAA > &  edgesLeft, std::vector< EdgeAA > &  edgesRight, std::vector< EdgeAA > &  edgesBottom, std::vector< EdgeAA > &  edgesTop  )

static

Variable Documentation

EDGE_EXPAND_DELTA

const entity_pos_t EDGE_EXPAND_DELTA = entity_pos_t::FromInt(1)/16

static

g_VertexPathfinderDebugOverlay

VertexPathfinderDebugOverlay g_VertexPathfinderDebugOverlay

QUADRANT_ALL

const u8 QUADRANT_ALL = QUADRANT_BLTR|QUADRANT_TLBR

static

QUADRANT_BL

const u8 QUADRANT_BL = 1

static

QUADRANT_BLTR

const u8 QUADRANT_BLTR = QUADRANT_BL|QUADRANT_TR

static

QUADRANT_BR

const u8 QUADRANT_BR = 8

static

QUADRANT_NONE

const u8 QUADRANT_NONE = 0

static

QUADRANT_TL

const u8 QUADRANT_TL = 4

static

QUADRANT_TLBR

const u8 QUADRANT_TLBR = QUADRANT_TL|QUADRANT_BR

static

QUADRANT_TR

const u8 QUADRANT_TR = 2

static