Vertex-based algorithm for CCmpPathfinder. More...

#include "precompiled.h"
#include "CCmpPathfinder_Common.h"
#include "lib/timer.h"
#include "ps/Profile.h"
#include "simulation2/components/ICmpObstructionManager.h"
#include "simulation2/helpers/PriorityQueue.h"
#include "simulation2/helpers/Render.h"

Include dependency graph for CCmpPathfinder_Vertex.cpp:

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

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 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

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

Typedef Documentation

typedef PriorityQueueHeap<u16, fixed, fixed> VertexPriorityQueue

Function Documentation

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.

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.)

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

inlinestatic

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

inlinestatic

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

inlinestatic

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

inlinestatic

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
	)