AI_NavigationMesh Class Reference
[InExIn]

#include <AI_NavigationMesh.h>

Detailed Description

Navigation mesh for agent pathfinding.

Navigation mesh (navmesh) represents surface along which the agents could walk. Navmesh is constructed from vertices, triangles and edges. Triangles and border edges are using clockwise order of vertices and navmesh is in right handed coordinate system. Each border edge must have exactly two adjacent edges. Navmesh should not contain duplicate vertices.

Once the navmesh is built up then it must be preprocessed before it is used to find some way. You can also enable or disable wide agents support. When this option is turned off then pathfinding is significantly faster in navmeshes with high local complexity.

Navigation mesh should be as easy as possible due to performance issues. This requirement considers two basic rules:

Small number of triangles
- Navigation mesh should contains as little inner vertices as possible (inner vertex is vertex that is not part of border edge).
- Navigation mesh should contains as little collinear adjacent border edges as possible (typically one edge of navmesh polygon is made by several triangle edges).
Small local complexity.
- Navigation mesh souldn't contains too many small obstacles in large area (typical example is forest with trees). Each concave corner in navigation mesh results to one node in A* graph so too many little obstacles makes A* graph too complex and to heavy for searching. Small obstacles (no mather if they are static or not) should be solved as AI_Obstacle.
- Navigation mesh shouldn't contains too many small corners.

It is clear that both these rules couldn't be adhere at 100% but the creator of the navmesh shoud keep these rules in his mind.

Navigation mesh of course should be meaningfull. It should represents compat area.

It MUST NOT contains edges with less then one or more then two adjacent triangles.
It MUST NOT contains duplicate vertices, edges or triangles.
It MUST NOT contains only vertices that are contained by no ro exactly two border edges.
It MUST NOT contains endless band - 2d projection of triangles intersects and these triangles are part of loop (for example navmesh could not be sphere or centrifuge).

Here are examples of navigation meshes:

Example of inadvisable navigation mesh

There are unreasonable many inner vertices and fragmented border edges. This mesh will work but it is not optimal.

Example of inadvisable navigation mesh

Small obstacles shoudl be solved with AI_Obstacle inserted into the world. This example will work but it is not optimal.

Example of totaly wrong navigation mesh

This example will lead to crash in preprocess time because 2d projections of adjacent triangles intersect. This navigationmash has no meaning.

Example of fine navigation mesh

This is well created navigation mesh which leads to good stability and performance.

KNOWN BUGS:
1) PROBABLY SOLVED IN 1.25: If agent is standing exactly on the corner and finish is visible from agent's standing point then founded way is not shortest way.

2) PROBABLY SOLVED IN 1.25: If wide agents is turned on and agent is standing near to any corner then it sometimes go to this corner first instead to go to visible corner in direction of final point.

Version:

1.25 (11.1.2007)

bug fixed: singularity in ray-edge intersection solved

1.21 (18.8.2006)

bug fixed in clear()

1.2 (21.10.2005)

Internal structures (Vertex, Triangle...) are pointer based (instead of index based)
Navigation mesh session
findWay() gain session as only parameter

1.0 Initial release.

Author:: Jindrich Rohlik


Public Types
enum	{ INVALID_INDEX = 0xffff }
typedef AI_Array< Vertex * >	VertexArray
	Array of vertices.
typedef VertexArray::iterator	VertexArrayIt
	Iterator to array of vertices.
typedef AI_Array< Edge * >	EdgeArray
	Array of edges.
typedef EdgeArray::iterator	EdgeArrayIt
	Iterator to array of edges.
typedef AI_Array< Triangle * >	TriangleArray
	Array of triangles.
typedef TriangleArray::iterator	TriangleArrayIt
	Iterator to array to triangles.
typedef AI_Array< Corner * >	CornerArray
	Array of corners.
typedef CornerArray::iterator	CornerArrayIt
	Iterator to array of corners.
Public Member Functions
	AI_NavigationMesh (void)
	Deafult constructor.
	~AI_NavigationMesh (void)
	Destructor.
ai_index	addVertex (const AI_Vector3 &v_vertex)
	Add vertex into navigation mesh.
ai_index	addTriangle (ai_index i_v1, ai_index i_v2, ai_index i_v3)
	Add triangle into navigation mesh.
ai_index	addEdge (ai_index i_t1, ai_index i_t2, ai_index i_v1, ai_index i_v2)
	Add edge into navigation mesh.
Vertex *	getVertex (ai_index i) const
	Return vertex by index.
Triangle *	getTriangle (ai_index i) const
	Return triangle by index.
Edge *	getEdge (ai_index i) const
	Return edge by index.
bool	preprocess (void)
	Preprocess navigation mesh.
bool	findWay (Session &session)
	Find a way between start and final positions.
bool	testVisibility (const AI_Vector3 &v_first, const AI_Vector3 &v_second)
	Test direct visibility between two points.
const bool	testBorderIntersection (const AI_Vector3 &v_first, const AI_Vector3 &v_second, float &f_distance)
	Test whether line between two points intersects the border.
void	clear (void)
	Destroy all data in navigation mesh.
const AI_AStar &	getVisibilityGraph (void) const
	Return visiblity graph associated with navigation mesh.
void	setWideAgents (bool b_support=true)
	Turn on/of wide agents support.
bool	isWideAgents (void) const
	Test if wide agents are supported.
bool	isPreprocessed (void) const
	Test if navigation mesh was successfully preprocessed.
Triangle *	identifyTriangle (const AI_Vector3 &v_coord)
	Return nearest triangle to position.
bool	getNearestPosition (const AI_Vector3 &v_position, float width, bool cylinder, AI_Vector3 &v_nearest_position)
	Return nearest position on navigation mesh to given position and width, which defines sphere or infinite Y axis aligned cylinder - depending on state of cylinder parameter.
Protected Attributes
VertexArray	m_arr_vertices
	Vertices.
TriangleArray	m_arr_triangles
	Triangles.
EdgeArray	m_arr_edges
	Edges.
CornerArray	m_arr_corners
	Corners.
AI_SDB_SpatialAABBTree	m_spatial_tree
	Spatial tree with all triangles.
AI_SDB_VisibilityVisitor::VisibleElements	m_spatial_elements
	Pointers to all spatial elements (bboxes with pointers to triangles).
AI_SDB_VisibilityVisitor::VisibleElements	m_visible_elements
	Array of selected visible elements.
AI_AStar	m_astar
	A* algorithm and graph.
Informator	m_astar_informator
	A* informator.
bool	m_b_preprocessed
	Preprocessed flag.
bool	m_b_wide_agents
	Support wide agents flag.
Classes
struct	Bundle
class	Corner
class	Edge
class	Informator
class	PointVisitor
class	Session
class	Triangle
class	Vertex

Member Typedef Documentation

typedef AI_Array<Vertex*> AI_NavigationMesh::VertexArray

Array of vertices.

typedef VertexArray::iterator AI_NavigationMesh::VertexArrayIt

Iterator to array of vertices.

typedef AI_Array<Edge*> AI_NavigationMesh::EdgeArray

Array of edges.

typedef EdgeArray::iterator AI_NavigationMesh::EdgeArrayIt

Iterator to array of edges.

typedef AI_Array<Triangle*> AI_NavigationMesh::TriangleArray

Array of triangles.

typedef TriangleArray::iterator AI_NavigationMesh::TriangleArrayIt

Iterator to array to triangles.

typedef AI_Array<Corner*> AI_NavigationMesh::CornerArray

Array of corners.

typedef CornerArray::iterator AI_NavigationMesh::CornerArrayIt

Iterator to array of corners.

Member Enumeration Documentation

anonymous enum

Enumerator:

INVALID_INDEX

First invalid index.

Constructor & Destructor Documentation

AI_NavigationMesh::AI_NavigationMesh ( void )

Deafult constructor.

AI_NavigationMesh::~AI_NavigationMesh ( void )

Destructor.

Member Function Documentation

ai_index AI_NavigationMesh::addVertex ( const AI_Vector3 & v_vertex )

Add vertex into navigation mesh.

ai_index AI_NavigationMesh::addTriangle	(	ai_index	i_v1,
		ai_index	i_v2,
		ai_index	i_v3
	)

Add triangle into navigation mesh.

ai_index AI_NavigationMesh::addEdge	(	ai_index	i_t1,
		ai_index	i_t2,
		ai_index	i_v1,
		ai_index	i_v2
	)

Add edge into navigation mesh.

Parameters:

	i_t1	Index of the first adjacent triangle of winged edge.
	i_t2	Index of the second adjacent triangle of winged edge.
	i_v1	Index of the first vertex of the edge.
	i_v2	Index of the second vertex of the edge.

AI_NavigationMesh::Vertex * AI_NavigationMesh::getVertex ( ai_index i ) const [inline]

Return vertex by index.

AI_NavigationMesh::Triangle * AI_NavigationMesh::getTriangle ( ai_index i ) const [inline]

Return triangle by index.

AI_NavigationMesh::Edge * AI_NavigationMesh::getEdge ( ai_index i ) const [inline]

Return edge by index.

bool AI_NavigationMesh::preprocess ( void )

Preprocess navigation mesh.

Prepare data, check well constructed mesh and build graph for A*.

bool AI_NavigationMesh::findWay ( AI_NavigationMesh::Session & session )

Find a way between start and final positions.

Vectors must not be exactly on navigation mesh surface but they should be as near as possible in case when there is more then one navigation mesh floor. Path is stored in a session could be retrieved through getWay() method.

bool AI_NavigationMesh::testVisibility	(	const AI_Vector3 &	v_first,
		const AI_Vector3 &	v_second
	)

Test direct visibility between two points.

const bool AI_NavigationMesh::testBorderIntersection	(	const AI_Vector3 &	v_first,
		const AI_Vector3 &	v_second,
		float &	f_distance
	)

Test whether line between two points intersects the border.

Parameters:

	v_first	First point of line segment (must lie on navigation mesh)
	v_second	Second point of tested line segment (need not to lie on navigation mesh)
	f_distance	If method returns true then third patameter contains distance from the first point in which the line intersects border.

Returns:: Return true if line segment intersects border. Return false if line segment doesn't intersect border (f_distance is set to infinity) or if first point doesn't lie on navigation mesh (f_distance is set to 0).

void AI_NavigationMesh::clear ( void )

Destroy all data in navigation mesh.

const AI_AStar & AI_NavigationMesh::getVisibilityGraph ( void ) const [inline]

Return visiblity graph associated with navigation mesh.

void AI_NavigationMesh::setWideAgents ( bool b_support = true ) [inline]

Turn on/of wide agents support.

bool AI_NavigationMesh::isWideAgents ( void ) const [inline]

Test if wide agents are supported.

bool AI_NavigationMesh::isPreprocessed ( void ) const [inline]

Test if navigation mesh was successfully preprocessed.

AI_NavigationMesh::Triangle * AI_NavigationMesh::identifyTriangle ( const AI_Vector3 & v_coord )

Return nearest triangle to position.

bool AI_NavigationMesh::getNearestPosition	(	const AI_Vector3 &	v_position,
		float	width,
		bool	cylinder,
		AI_Vector3 &	v_nearest_position
	)

Return nearest position on navigation mesh to given position and width, which defines sphere or infinite Y axis aligned cylinder - depending on state of cylinder parameter.