Path finding class. More...

#include <tdme/utilities/PathFinding.h>

Collaboration diagram for PathFinding:

Classes
struct	PathFindingNode
	Path finding node. More...

Public Member Functions
	PathFinding (World *world, bool sloping=false, int stepsMax=1000, float actorHeight=2.0f, float stepSize=0.5f, float stepSizeLast=0.75f, float actorStepUpMax=0.25f, uint16_t skipOnCollisionTypeIds=0, int maxTries=5, float flowMapStepSize=0.5f, float flowMapScaleActorBoundingVolumes=1.0f)
	Public constructor. More...

	~PathFinding ()
	Destructor. More...

float	getStepSize ()

void	reset ()
	Clear caches. More...

string	toId (float x, float y, float z)
	Return string representation of given x,y,z for path finding id. More...

float	alignPositionComponent (float value)
	Align position component. More...

int	getIntegerPositionComponent (float value)
	Returns integer position component. More...

bool	findPath (const Vector3 &startPosition, const Vector3 &endPosition, const uint16_t collisionTypeIds, vector< Vector3 > &path, int alternativeEndSteps=0, int maxTriesOverride=-1, PathFindingCustomTest *customTest=nullptr)
	Finds path to given end position. More...

bool	findFlowMapPath (const Vector3 &startPosition, const Vector3 &endPosition, const uint16_t collisionTypeIds, vector< Vector3 > &path, int alternativeEndSteps=0, int maxTriesOverride=-1, PathFindingCustomTest *customTest=nullptr)
	Finds path to given end position for flow maps. More...

bool	findPathCustom (const Vector3 &startPosition, const Vector3 &endPosition, float stepSize, float scaleActorBoundingVolumes, const uint16_t collisionTypeIds, vector< Vector3 > &path, int alternativeEndSteps=0, int maxTriesOverride=-1, PathFindingCustomTest *customTest=nullptr)
	Finds path to given end position. More...

bool	isWalkable (float x, float y, float z, float &height, float stepSize, float scaleActorBoundingVolumes, bool flowMapRequest, uint16_t collisionTypeIds=0, bool ignoreStepUpMax=false)
	Checks if a cell is walkable. More...

FlowMap *	createFlowMap (const vector< Vector3 > &endPositions, const Vector3 &center, float depth, float width, const uint16_t collisionTypeIds, const vector< Vector3 > &path=vector< Vector3 >(), bool complete=true, PathFindingCustomTest *customTest=nullptr)
	Create flow map. More...

const vector< Vector3 >	generateDirectPath (const Vector3 &start, const Vector3 &end)
	Generate direct path from start to end. More...

Static Public Member Functions
static string	toId (float x, float y, float z, float stepSize)
	Return string representation of given x,y,z for path finding id. More...

static float	alignPositionComponent (float value, float stepSize)
	Align position component. More...

static int	getIntegerPositionComponent (float value, float stepSize)
	Returns integer position component. More...

static string	toIdInt (int x, int y, int z)
	Return string representation of given x,z integer flow map position representation for path finding id. More...

Static Public Attributes
static constexpr bool	VERBOSE { true }

Private Member Functions
float	computeDistance (const PathFindingNode &a, const PathFindingNode &b)
	Computes non square rooted distance between a and b. More...

float	computeDistanceToEnd (const PathFindingNode &node)
	Computes minimal non square rooted distance between node and end point. More...

bool	equals (const PathFindingNode &a, float bX, float bY, float bZ)
	Returns if nodes are equals. More...

bool	equalsLastNode (const PathFindingNode &a, const PathFindingNode &b)
	Returns if nodes are equals for (last node test) More...

bool	isWalkableInternal (float x, float y, float z, float &height, float stepSize, float scaleActorBoundingVolumes, bool flowMapRequest, uint16_t collisionTypeIds=0, bool ignoreStepUpMax=false)
	Checks if a cell is walkable. More...

bool	isSlopeWalkableInternal (float x, float y, float z, float successorX, float successorY, float successorZ, float stepSize, float scaleActorBoundingVolumes, bool flowMapRequest, uint16_t collisionTypeIds=0)
	Checks if a cell is slope walkable. More...

void	step (const PathFindingNode &node, float stepSize, float scaleActorBoundingVolumes, const unordered_set< string > *nodesToTest, bool flowMapRequest)
	Processes one step in AStar path finding. More...

Private Attributes
World *	world { nullptr }

PathFindingCustomTest *	customTest { nullptr }

bool	sloping

int	stepsMax

float	actorHeight

float	stepSize

float	stepSizeLast

float	actorStepUpMax

uint16_t	skipOnCollisionTypeIds

uint16_t	collisionTypeIds

int	maxTries

float	flowMapStepSize

float	flowMapScaleActorBoundingVolumes

PathFindingNode	end

unordered_map< string, PathFindingNode >	openNodes

unordered_map< string, PathFindingNode >	closedNodes

BoundingVolume *	actorBoundingVolume { nullptr }

BoundingVolume *	actorBoundingVolumeSlopeTest { nullptr }

unordered_map< string, float >	walkableCache

Detailed Description

Path finding class.

Author: Andreas Drewke

Version: $Id$

Definition at line 43 of file PathFinding.h.

Constructor & Destructor Documentation

◆ PathFinding()

PathFinding	(	World *	world,
		bool	sloping = `false`,
		int	stepsMax = `1000`,
		float	actorHeight = `2.0f`,
		float	stepSize = `0.5f`,
		float	stepSizeLast = `0.75f`,
		float	actorStepUpMax = `0.25f`,
		uint16_t	skipOnCollisionTypeIds = `0`,
		int	maxTries = `5`,
		float	flowMapStepSize = `0.5f`,
		float	flowMapScaleActorBoundingVolumes = `1.0f`
	)

Public constructor.

Parameters

world	world
sloping	sloping
stepsMax	steps max
actorHeight	actor height
stepSize	step size
stepSizeLast	step size last
actorStepUpMax	actor step up max
skipOnCollisionTypeIds	skip cells with given collision type ids
maxTries	max tries
flowMapStepSize	flow map step size
flowMapScaleActorBoundingVolumes	flow map scale actor bounding volumes

Definition at line 47 of file PathFinding.cpp.

◆ ~PathFinding()

~PathFinding ( )

Destructor.

Definition at line 77 of file PathFinding.cpp.

Member Function Documentation

◆ alignPositionComponent() [1/2]

float alignPositionComponent ( float value )

inline

Align position component.

Parameters

value value which is usually a position vector 3 position component

Definition at line 140 of file PathFinding.h.

◆ alignPositionComponent() [2/2]

static float alignPositionComponent	(	float	value,
		float	stepSize
	)

inlinestatic

Align position component.

Parameters

value	value which is usually a position vector 3 position component
stepSize	step size

Definition at line 132 of file PathFinding.h.

◆ computeDistance()

float computeDistance	(	const PathFindingNode &	a,
		const PathFindingNode &	b
	)

inlineprivate

Computes non square rooted distance between a and b.

Parameters

a	node a
b	node b

Returns: non square rooted distance

Definition at line 319 of file PathFinding.h.

◆ computeDistanceToEnd()

float computeDistanceToEnd ( const PathFindingNode & node )

inlineprivate

Computes minimal non square rooted distance between node and end point.

Parameters

node node

Returns: non square rooted distance

Definition at line 328 of file PathFinding.h.

◆ createFlowMap()

FlowMap * createFlowMap	(	const vector< Vector3 > &	endPositions,
		const Vector3 &	center,
		float	depth,
		float	width,
		const uint16_t	collisionTypeIds,
		const vector< Vector3 > &	path = `vector<Vector3>()`,
		bool	complete = `true`,
		PathFindingCustomTest *	customTest = `nullptr`
	)

Create flow map.

Parameters

endPositions	end positions
center	flow map center
depth	flow map depth
width	flow map width
collisionTypeIds	collision type ids
path	path to test along
complete	complete
customTest	custom test

Returns: flow map

Definition at line 719 of file PathFinding.cpp.

◆ equals()

bool equals	(	const PathFindingNode &	a,
		float	bX,
		float	bY,
		float	bZ
	)

inlineprivate

Returns if nodes are equals.

Parameters

a	a
bX	b x coordinate
bY	b y coordinate
bZ	b z coordinate

Returns: if node a == node b

Definition at line 340 of file PathFinding.h.

◆ equalsLastNode()

bool equalsLastNode	(	const PathFindingNode &	a,
		const PathFindingNode &	b
	)

inlineprivate

Returns if nodes are equals for (last node test)

Parameters

a	a
lastNode	b

Returns: if node a == node b

Definition at line 350 of file PathFinding.h.

◆ findFlowMapPath()

bool findFlowMapPath	(	const Vector3 &	startPosition,
		const Vector3 &	endPosition,
		const uint16_t	collisionTypeIds,
		vector< Vector3 > &	path,
		int	alternativeEndSteps = `0`,
		int	maxTriesOverride = `-1`,
		PathFindingCustomTest *	customTest = `nullptr`
	)

inline

Finds path to given end position for flow maps.

Parameters

startPosition	start position
endPosition	end position
collisionTypeIds	collision type ids
path	path from actor to target
alternativeEndSteps	alternative end steps
maxTriesOverride	max tries override or -1 for default
customTest	custom test

Returns: success

Definition at line 206 of file PathFinding.h.

◆ findPath()

bool findPath	(	const Vector3 &	startPosition,
		const Vector3 &	endPosition,
		const uint16_t	collisionTypeIds,
		vector< Vector3 > &	path,
		int	alternativeEndSteps = `0`,
		int	maxTriesOverride = `-1`,
		PathFindingCustomTest *	customTest = `nullptr`
	)

inline

Finds path to given end position.

Parameters

startPosition	start position
endPosition	end position
collisionTypeIds	collision type ids
path	path from actor to target
alternativeEndSteps	alternative end steps
maxTriesOverride	max tries override or -1 for default
customTest	custom test

Returns: success

Definition at line 190 of file PathFinding.h.

◆ findPathCustom()

bool findPathCustom	(	const Vector3 &	startPosition,
		const Vector3 &	endPosition,
		float	stepSize,
		float	scaleActorBoundingVolumes,
		const uint16_t	collisionTypeIds,
		vector< Vector3 > &	path,
		int	alternativeEndSteps = `0`,
		int	maxTriesOverride = `-1`,
		PathFindingCustomTest *	customTest = `nullptr`
	)

Finds path to given end position.

Parameters

startPosition	start position
endPosition	end position
stepSize	step size
scaleActorBoundingVolumes	scale actor bounding volumes
collisionTypeIds	collision type ids
path	path from actor to target
alternativeEndSteps	alternative end steps
maxTriesOverride	max tries override or -1 for default
customTest	custom test

Returns: success

Definition at line 313 of file PathFinding.cpp.

◆ generateDirectPath()

const vector< Vector3 > generateDirectPath	(	const Vector3 &	start,
		const Vector3 &	end
	)

Generate direct path from start to end.

Parameters

start	start
end	end

Returns: path nodes

Definition at line 1075 of file PathFinding.cpp.

◆ getIntegerPositionComponent() [1/2]

int getIntegerPositionComponent ( float value )

inline

Returns integer position component.

Parameters

value value

Returns: integer position component

Definition at line 159 of file PathFinding.h.

◆ getIntegerPositionComponent() [2/2]

static int getIntegerPositionComponent	(	float	value,
		float	stepSize
	)

inlinestatic

Returns integer position component.

Parameters

value	value
stepSize	step size

Returns: integer position component

Definition at line 150 of file PathFinding.h.

◆ getStepSize()

float getStepSize ( )

inline

Returns: step size

Definition at line 84 of file PathFinding.h.

◆ isSlopeWalkableInternal()

bool isSlopeWalkableInternal	(	float	x,
		float	y,
		float	z,
		float	successorX,
		float	successorY,
		float	successorZ,
		float	stepSize,
		float	scaleActorBoundingVolumes,
		bool	flowMapRequest,
		uint16_t	collisionTypeIds = `0`
	)

private

Checks if a cell is slope walkable.

Parameters

x	x
y	y
z	z
successorX	x
successorY	y
successorZ	z
stepSize	step size
scaleActorBoundingVolumes	scale actor bounding volumes
collisionTypeIds	collision type ids or 0 for default

Returns: if cell is walkable

Definition at line 104 of file PathFinding.cpp.

◆ isWalkable()

bool isWalkable	(	float	x,
		float	y,
		float	z,
		float &	height,
		float	stepSize,
		float	scaleActorBoundingVolumes,
		bool	flowMapRequest,
		uint16_t	collisionTypeIds = `0`,
		bool	ignoreStepUpMax = `false`
	)

Checks if a cell is walkable.

Parameters

x	x
y	y
z	z
height	y stepped up
stepSize	step size
scaleActorBoundingVolumes	scale actor bounding volumes
flowMapRequest	flow map request
collisionTypeIds	collision type ids or 0 for default
ignoreStepUpMax	ignore step up max

Returns: if cell is walkable

Definition at line 152 of file PathFinding.cpp.

◆ isWalkableInternal()

bool isWalkableInternal	(	float	x,
		float	y,
		float	z,
		float &	height,
		float	stepSize,
		float	scaleActorBoundingVolumes,
		bool	flowMapRequest,
		uint16_t	collisionTypeIds = `0`,
		bool	ignoreStepUpMax = `false`
	)

private

Checks if a cell is walkable.

Parameters

x	x
y	y
z	z
height	y stepped up
stepSize	step size
scaleActorBoundingVolumes	scale actor bounding volumes
flowMapRequest	flow map request
collisionTypeIds	collision type ids or 0 for default
ignoreStepUpMax	ignore step up max

Returns: if cell is walkable

Definition at line 80 of file PathFinding.cpp.

◆ reset()

void reset ( )

inline

Clear caches.

Definition at line 91 of file PathFinding.h.

◆ step()

void step	(	const PathFindingNode &	node,
		float	stepSize,
		float	scaleActorBoundingVolumes,
		const unordered_set< string > *	nodesToTest,
		bool	flowMapRequest
	)

private

Processes one step in AStar path finding.

Parameters

node	node
stepSize	step size
scaleActorBoundingVolumes	scale actor bounding volumes
nodesToTest	nodes to test or nullptr, applies to flow cost map generation
flowMapRequest	flow map request

Returns: step status

Definition at line 192 of file PathFinding.cpp.

◆ toId() [1/2]

string toId	(	float	x,
		float	y,
		float	z
	)

inline

Return string representation of given x,y,z for path finding id.

Parameters

x	x
y	y
z	z
stepSize	step size

Returns: string representation

Definition at line 103 of file PathFinding.h.

◆ toId() [2/2]

static string toId	(	float	x,
		float	y,
		float	z,
		float	stepSize
	)

inlinestatic

Return string representation of given x,y,z for path finding id.

Parameters

x	x
y	y
z	z

Returns: string representation

Definition at line 114 of file PathFinding.h.

◆ toIdInt()

static string toIdInt	(	int	x,
		int	y,
		int	z
	)

inlinestatic

Return string representation of given x,z integer flow map position representation for path finding id.

Parameters

x	x
y	y
z	z

Returns: string representation

Definition at line 170 of file PathFinding.h.

Member Data Documentation

◆ actorBoundingVolume

BoundingVolume* actorBoundingVolume { nullptr }

private

Definition at line 412 of file PathFinding.h.

◆ actorBoundingVolumeSlopeTest

BoundingVolume* actorBoundingVolumeSlopeTest { nullptr }

private

Definition at line 413 of file PathFinding.h.

◆ actorHeight

float actorHeight

private

Definition at line 400 of file PathFinding.h.

◆ actorStepUpMax

float actorStepUpMax

private

Definition at line 403 of file PathFinding.h.

◆ closedNodes

unordered_map<string, PathFindingNode> closedNodes

private

Definition at line 411 of file PathFinding.h.

◆ collisionTypeIds

uint16_t collisionTypeIds

private

Definition at line 405 of file PathFinding.h.

◆ customTest

PathFindingCustomTest* customTest { nullptr }

private

Definition at line 397 of file PathFinding.h.

◆ end

PathFindingNode end

private

Definition at line 409 of file PathFinding.h.

◆ flowMapScaleActorBoundingVolumes

float flowMapScaleActorBoundingVolumes

private

Definition at line 408 of file PathFinding.h.

◆ flowMapStepSize

float flowMapStepSize

private

Definition at line 407 of file PathFinding.h.

◆ maxTries

int maxTries

private

Definition at line 406 of file PathFinding.h.

◆ openNodes

unordered_map<string, PathFindingNode> openNodes

private

Definition at line 410 of file PathFinding.h.

◆ skipOnCollisionTypeIds

uint16_t skipOnCollisionTypeIds

private

Definition at line 404 of file PathFinding.h.

◆ sloping

bool sloping

private

Definition at line 398 of file PathFinding.h.

◆ stepSize

float stepSize

private

Definition at line 401 of file PathFinding.h.

◆ stepSizeLast

float stepSizeLast

private

Definition at line 402 of file PathFinding.h.

◆ stepsMax

int stepsMax

private

Definition at line 399 of file PathFinding.h.

◆ VERBOSE

constexpr bool VERBOSE { true }

staticconstexpr

Definition at line 46 of file PathFinding.h.

◆ walkableCache

unordered_map<string, float> walkableCache

private

Definition at line 414 of file PathFinding.h.

◆ world

World* world { nullptr }

private

Definition at line 396 of file PathFinding.h.

The documentation for this class was generated from the following files:

/home/andreas/Development/drewke.net/tdme2/src/tdme/utilities/PathFinding.h
/home/andreas/Development/drewke.net/tdme2/src/tdme/utilities/PathFinding.cpp

Classes

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ PathFinding()

◆ ~PathFinding()

Member Function Documentation

◆ alignPositionComponent() [1/2]

◆ alignPositionComponent() [2/2]

◆ computeDistance()

◆ computeDistanceToEnd()

◆ createFlowMap()

◆ equals()

◆ equalsLastNode()

◆ findFlowMapPath()

◆ findPath()

◆ findPathCustom()

◆ generateDirectPath()

◆ getIntegerPositionComponent() [1/2]

◆ getIntegerPositionComponent() [2/2]

◆ getStepSize()

◆ isSlopeWalkableInternal()

◆ isWalkable()

◆ isWalkableInternal()

◆ reset()

◆ step()

◆ toId() [1/2]

◆ toId() [2/2]

◆ toIdInt()

Member Data Documentation

◆ actorBoundingVolume

◆ actorBoundingVolumeSlopeTest

◆ actorHeight

◆ actorStepUpMax

◆ closedNodes

◆ collisionTypeIds

◆ customTest

◆ end

◆ flowMapScaleActorBoundingVolumes

◆ flowMapStepSize

◆ maxTries

◆ openNodes

◆ skipOnCollisionTypeIds

◆ sloping

◆ stepSize

◆ stepSizeLast

◆ stepsMax

◆ VERBOSE

◆ walkableCache

◆ world