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"

Classes
struct	Vertex

struct	Edge

struct	EdgeAA

struct	TileEdge

struct	EdgeSort
	Functor for sorting edges by approximate proximity to a fixed point. More...

Typedefs
typedef PriorityQueueHeap< u16, fixed >	PriorityQueue

Functions
static bool	CheckVisibility (CFixedVector2D a, CFixedVector2D b, const std::vector< Edge > &edges)
	Check whether a ray from 'a' to 'b' crosses any of the edges. More...

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

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

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

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

static CFixedVector2D	NearestPointOnGoal (CFixedVector2D pos, const CCmpPathfinder::Goal &goal)

static void	AddTerrainEdges (std::vector< Edge > &edgesAA, std::vector< Vertex > &vertexes, u16 i0, u16 j0, u16 i1, u16 j1, fixed r, ICmpPathfinder::pass_class_t passClass, const Grid< TerrainTile > &terrain)

static void	SplitAAEdges (CFixedVector2D a, const std::vector< Edge > &edgesAA, 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)/4

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.

Definition in file CCmpPathfinder_Vertex.cpp.

Typedef Documentation

typedef PriorityQueueHeap<u16, fixed> PriorityQueue

Definition at line 328 of file CCmpPathfinder_Vertex.cpp.

Function Documentation

static void AddTerrainEdges	(	std::vector< Edge > &	edgesAA,
		std::vector< Vertex > &	vertexes,
		u16	i0,
		u16	j0,
		u16	i1,
		u16	j1,
		fixed	r,
		ICmpPathfinder::pass_class_t	passClass,
		const Grid< TerrainTile > &	terrain
	)

static

Definition at line 336 of file CCmpPathfinder_Vertex.cpp.

static bool CheckVisibility	(	CFixedVector2D	a,
		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.)

Definition at line 130 of file CCmpPathfinder_Vertex.cpp.

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

inlinestatic

Definition at line 230 of file CCmpPathfinder_Vertex.cpp.

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

inlinestatic

Definition at line 174 of file CCmpPathfinder_Vertex.cpp.

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

inlinestatic

Definition at line 202 of file CCmpPathfinder_Vertex.cpp.

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

inlinestatic

Definition at line 258 of file CCmpPathfinder_Vertex.cpp.

static CFixedVector2D NearestPointOnGoal	(	CFixedVector2D	pos,
		const CCmpPathfinder::Goal &	goal
	)

static

Definition at line 287 of file CCmpPathfinder_Vertex.cpp.

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

static

Definition at line 446 of file CCmpPathfinder_Vertex.cpp.

Variable Documentation

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

static

Definition at line 124 of file CCmpPathfinder_Vertex.cpp.

const u8 QUADRANT_ALL = QUADRANT_BLTR|QUADRANT_TLBR

static

Definition at line 82 of file CCmpPathfinder_Vertex.cpp.

const u8 QUADRANT_BL = 1

static

Definition at line 76 of file CCmpPathfinder_Vertex.cpp.

const u8 QUADRANT_BLTR = QUADRANT_BL|QUADRANT_TR

static

Definition at line 80 of file CCmpPathfinder_Vertex.cpp.

const u8 QUADRANT_BR = 8

static

Definition at line 79 of file CCmpPathfinder_Vertex.cpp.

const u8 QUADRANT_NONE = 0

static

Definition at line 75 of file CCmpPathfinder_Vertex.cpp.

const u8 QUADRANT_TL = 4

static

Definition at line 78 of file CCmpPathfinder_Vertex.cpp.

const u8 QUADRANT_TLBR = QUADRANT_TL|QUADRANT_BR

static

Definition at line 81 of file CCmpPathfinder_Vertex.cpp.

const u8 QUADRANT_TR = 2

static

Definition at line 77 of file CCmpPathfinder_Vertex.cpp.

Classes

Typedefs

Functions

Variables

Detailed Description

Typedef Documentation

Function Documentation

Variable Documentation