SuperTuxKart
Public Member Functions | Static Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
ArenaGraph Class Reference

A graph made from navmesh. More...

#include <arena_graph.hpp>

Inheritance diagram for ArenaGraph:
Inheritance graph
[legend]

Public Member Functions

 ArenaGraph (const std::string &navmesh, const XMLNode *node=NULL)
 
ArenaNodegetNode (unsigned int i) const
 
int getNextNode (int i, int j) const
 Returns the next node on the shortest path from i to j. More...
 
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. More...
 
RenderTargetmakeMiniMap (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. More...
 
QuadgetQuad (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. More...
 
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. More...
 
const Vec3getBBMin () const
 
const Vec3getBBMax () const
 
const int * getBBNodes () const
 

Static Public Member Functions

static ArenaGraphget ()
 
static void unitTesting ()
 Unit testing for arena graph distance and parent node computation. More...
 
- Static Public Member Functions inherited from Graph
static Graphget ()
 Returns the one instance of this object. More...
 
static void setGraph (Graph *graph)
 Set the graph (either drive or arena graph for now). More...
 
static void destroy ()
 Cleans up the graph. More...
 

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. More...
 
void computeFloydWarshall ()
 THIS FUNCTION IS ONLY USED FOR UNIT-TESTING, to verify that the new Dijkstra algorithm gives the same results. More...
 
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). More...
 

Private Attributes

std::vector< std::vector< float > > m_distance_matrix
 The actual graph data structure, it is an adjacency matrix. More...
 
std::vector< std::vector< int16_t > > m_parent_node
 The matrix that is used to store computed shortest paths. More...
 
std::set< int > m_red_node
 Used in soccer mode to colorize the goal lines in minimap. More...
 
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. More...
 
void loadBoundingBoxNodes ()
 Map 4 bounding box points to 4 closest graph nodes. More...
 
- Protected Attributes inherited from Graph
std::vector< Quad * > m_all_nodes
 
- Static Protected Attributes inherited from Graph
static Graphm_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

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

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

Member Data Documentation

◆ m_distance_matrix

std::vector<std::vector<float> > ArenaGraph::m_distance_matrix
private

The actual graph data structure, it is an adjacency matrix.

◆ m_parent_node

std::vector<std::vector<int16_t> > ArenaGraph::m_parent_node
private

The matrix that is used to store computed shortest paths.

◆ m_red_node

std::set<int> ArenaGraph::m_red_node
private

Used in soccer mode to colorize the goal lines in minimap.


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