A graph made from navmesh. More...

#include <arena_graph.hpp>

Inheritance diagram for ArenaGraph:

Public Member Functions
	ArenaGraph (const std::string &navmesh, const XMLNode *node=NULL)

ArenaNode *	getNode (unsigned int i) const

int	getNextNode (int i, int j) const
	Returns the next node on the shortest path from i to j.

float	getDistance (int from, int to) const
	Returns the distance between any two nodes.

Public Member Functions inherited from Graph
void	createDebugMesh ()
	Creates the debug mesh to display the graph on top of the track model.

RenderTarget *	makeMiniMap (const core::dimension2du &dimension, const std::string &name, const video::SColor &fill_color, bool invert_x_z)
	Takes a snapshot of the graph so they can be used as minimap.

void	mapPoint2MiniMap (const Vec3 &xyz, Vec3 *out) const
	Returns the 2d coordinates of a point when drawn on the mini map texture.

Quad *	getQuad (unsigned int i) const

unsigned int	getNumNodes () const

void	findRoadSector (const Vec3 &XYZ, int sector, std::vector< int > all_sectors=NULL, bool ignore_vertical=false) const
	findRoadSector returns in which sector on the road the position xyz is.

int	findOutOfRoadSector (const Vec3 &xyz, const int curr_sector=UNKNOWN_SECTOR, std::vector< int > *all_sectors=NULL, bool ignore_vertical=false) const
	findOutOfRoadSector finds the sector where XYZ is, but as it name implies, it is more accurate for the outside of the track than the inside, and for STK's needs the accuracy on top of the track is unacceptable; but if this was a 2D function, the accuracy for out of road sectors would be perfect.

const Vec3 &	getBBMin () const

const Vec3 &	getBBMax () const

const int *	getBBNodes () const

Static Public Member Functions
static ArenaGraph *	get ()

static void	unitTesting ()
	Unit testing for arena graph distance and parent node computation.

Static Public Member Functions inherited from Graph
static Graph *	get ()
	Returns the one instance of this object.

static void	setGraph (Graph *graph)
	Set the graph (either drive or arena graph for now).

static void	destroy ()
	Cleans up the graph.

Private Member Functions
void	loadGoalNodes (const XMLNode *node)

void	loadNavmesh (const std::string &navmesh)

void	buildGraph ()

void	setNearbyNodesOfAllNodes ()

void	computeDijkstra (int n)
	Dijkstra shortest path computation.

void	computeFloydWarshall ()
	THIS FUNCTION IS ONLY USED FOR UNIT-TESTING, to verify that the new Dijkstra algorithm gives the same results.

virtual bool	hasLapLine () const OVERRIDE

virtual void	differentNodeColor (int n, video::SColor *c) const OVERRIDE

Static Private Member Functions
static std::vector< int16_t >	getPathFromTo (int from, int to, const std::vector< std::vector< int16_t > > &parent_node)
	Determines the full path from 'from' to 'to' and returns it in a std::vector (in reverse order).

Private Attributes
std::vector< std::vector< float > >	m_distance_matrix
	The actual graph data structure, it is an adjacency matrix.

std::vector< std::vector< int16_t > >	m_parent_node
	The matrix that is used to store computed shortest paths.

std::set< int >	m_red_node
	Used in soccer mode to colorize the goal lines in minimap.

std::set< int >	m_blue_node

Additional Inherited Members
Static Public Attributes inherited from Graph
static const int	UNKNOWN_SECTOR = -1

static const float	MIN_HEIGHT_TESTING = -1.0f

static const float	MAX_HEIGHT_TESTING = 5.0f

Protected Member Functions inherited from Graph
void	createQuad (const Vec3 &p0, const Vec3 &p1, const Vec3 &p2, const Vec3 &p3, unsigned int node_index, bool invisible, bool ai_ignore, bool is_arena, bool ignore)
	Factory method to dynamic create 2d / 3d quad for drive and arena graph.

void	loadBoundingBoxNodes ()
	Map 4 bounding box points to 4 closest graph nodes.

Protected Attributes inherited from Graph
std::vector< Quad * >	m_all_nodes

Static Protected Attributes inherited from Graph
static Graph *	m_graph = NULL

Detailed Description

A graph made from navmesh.

Member Function Documentation

◆ computeDijkstra()

void ArenaGraph::computeDijkstra ( int source )

private

Dijkstra shortest path computation.

It computes the shortest distance from the specified node 'source' to all other nodes. At the end of the computation, m_distance_matrix[i][j] stores the shortest path distance from source to j and m_parent_node[source][j] stores the last vertex visited on the shortest path from i to j before visiting j. Suppose the shortest path from i to j is i->......->k->j then m_parent_node[i][j] = k

◆ computeFloydWarshall()

void ArenaGraph::computeFloydWarshall ( )

private

THIS FUNCTION IS ONLY USED FOR UNIT-TESTING, to verify that the new Dijkstra algorithm gives the same results.

computeFloydWarshall() computes the shortest distance between any two nodes. At the end of the computation, m_distance_matrix[i][j] stores the shortest path distance from i to j and m_parent_node[i][j] stores the last vertex visited on the shortest path from i to j before visiting j. Suppose the shortest path from i to j is i->......->k->j then m_parent_node[i][j] = k

◆ differentNodeColor()

void ArenaGraph::differentNodeColor	(	int	n,
		video::SColor *	c
	)		const

privatevirtual

Implements Graph.

◆ getNextNode()

int ArenaGraph::getNextNode	(	int	i,
		int	j
	)		const

inline

Returns the next node on the shortest path from i to j.

Note: m_parent_node[j][i] contains the parent of i on path from j to i, which is the next node on the path from i to j (undirected graph)

◆ getPathFromTo()

std::vector< int16_t > ArenaGraph::getPathFromTo	(	int	from,
		int	to,
		const std::vector< std::vector< int16_t > > &	parent_node
	)

staticprivate

Determines the full path from 'from' to 'to' and returns it in a std::vector (in reverse order).

Used only for unit testing.

◆ hasLapLine()

virtual bool ArenaGraph::hasLapLine ( ) const

inlineprivatevirtual

Implements Graph.

◆ unitTesting()

void ArenaGraph::unitTesting ( )

static

Unit testing for arena graph distance and parent node computation.

Instead of using hand-tuned test cases we use the tested, verified and easier to understand Floyd-Warshall algorithm to compute the distances, and check if the (significanty faster) Dijkstra algorithm gives the same results. For now we use the cave mesh as test case.

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

tracks/arena_graph.hpp
tracks/arena_graph.cpp

Public Member Functions

Static Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members