SuperTuxKart

A graph made from driveline. More...
#include <drive_graph.hpp>
Public Member Functions  
DriveGraph (const std::string &quad_file_name, const std::string &graph_file_name, const bool reverse)  
Constructor, loads the graph information for a given set of quads from a graph file.  
void  getSuccessors (int node_number, std::vector< unsigned int > &succ, bool for_ai=false) const 
Returns the list of successors or a node.  
void  spatialToTrack (Vec3 *dst, const Vec3 &xyz, const int sector) const 
This function takes absolute coordinates (coordinates in OpenGL space) and transforms them into coordinates based on the track.  
void  setDefaultStartPositions (AlignedArray< btTransform > *start_transforms, unsigned int karts_per_row, float forwards_distance=1.5f, float sidewards_distance=1.5f, float upwards_distance=0.0f) const 
Sets all start positions depending on the drive graph.  
void  updateDistancesForAllSuccessors (unsigned int indx, float delta, unsigned int count) 
Increases the distance from start for all nodes that are directly or indirectly a successor of the given node.  
void  setupPaths () 
This function defines the "pathtonodes" for each graph node that has more than one successor.  
void  computeChecklineRequirements () 
Sets the checkline requirements for all nodes in the graph.  
float  getDistanceToNext (int n, int j) const 
Return the distance to the jth successor of node n.  
float  getAngleToNext (int n, int j) const 
Returns the angle of the line between node n and its jth.  
int  getNumberOfSuccessors (int n) const 
Returns the number of successors of a node n.  
DriveNode *  getNode (unsigned int j) const 
Returns the quad that belongs to a graph node.  
float  getDistanceFromStart (int j) const 
Returns the distance from the start to the beginning of a quad.  
float  getLapLength () const 
Returns the length of the main driveline.  
bool  isReverse () const 
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 DriveGraph *  get () 
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  setDefaultSuccessors () 
This function sets a default successor for all graph nodes that currently don't have a successor defined.  
void  computeChecklineRequirements (DriveNode *node, int latest_checkline) 
Finds which checklines must be visited before driving on this quad (useful for rescue)  
void  computeDirectionData () 
Computes the direction (straight, left, right) of all graph nodes and the lastest graph node that is still turning in the given direction.  
void  determineDirection (unsigned int current, unsigned int succ_index) 
Determines the direction of the drive graph when driving to the specified successor.  
float  normalizeAngle (float f) 
Adjust the given angle to be in [PI, PI].  
void  addSuccessor (unsigned int from, unsigned int to) 
void  load (const std::string &quad_file_name, const std::string &filename) 
Loads a drive graph from a file.  
void  getPoint (const XMLNode *xml, const std::string &attribute_name, Vec3 *result) const 
This function interprets a point specification as an attribute in the xml quad file.  
void  computeDistanceFromStart (unsigned int start_node, float distance) 
Recursively determines the distance the beginning (lower end) of the quads have from the start of the track.  
unsigned int  getStartNode () const 
Returns the index of the first graph node (i.e.  
virtual bool  hasLapLine () const OVERRIDE 
virtual void  differentNodeColor (int n, video::SColor *c) const OVERRIDE 
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 
A graph made from driveline.
DriveGraph::DriveGraph  (  const std::string &  quad_file_name, 
const std::string &  graph_file_name,  
const bool  reverse  
) 
Constructor, loads the graph information for a given set of quads from a graph file.
quad_file_name  Name of the file of all quads 
graph_file_name  Name of the file describing the actual graph 

private 
Computes the direction (straight, left, right) of all graph nodes and the lastest graph node that is still turning in the given direction.
For example, if a successor to this graph node is turning left, it will compute the last graph node that is still turning left. This data is used by the AI to estimate the turn radius. At this stage there is one restriction: if a node with more than one successor is ahead, only successor 0 is used. That might lead to somewhat incorrect results (i.e. the last successor is determined assuming that the kart is always using successor 0, while in reality it might follow a different successor, resulting in a different turn radius. It is not expected that this makes much difference for the AI (since it will update its data constantly, i.e. if it takes a different turn, it will be using the new data).

private 
Recursively determines the distance the beginning (lower end) of the quads have from the start of the track.
node  The node index for which to set the distance from start. 
new_distance  The new distance for the specified graph node. 

private 
Determines the direction of the drive graph when driving to the specified successor.
It also determines the last graph node that is still following the given direction. The computed data is saved in the corresponding graph node. It compares the lines connecting the center point of node n with n+1 and the lines connecting n+1 and n+2 (where n is the current node, and +1 etc. specifying the successor). Then it keeps on testing the line from n+2 to n+3, n+3 to n+4, ... as long as the turn direction is the same. The last value that still has the same direction is then set as the last node with the same direction in the specified graph node.
current  Index of the graph node with which to start ('n' in the description above). 
succ_index  The successor to be followed from the current node. If there should be any other branches later, successor 0 will always be tetsed. 

privatevirtual 
Implements Graph.
float DriveGraph::getAngleToNext  (  int  n, 
int  j  
)  const 
Returns the angle of the line between node n and its jth.
successor.

private 
This function interprets a point specification as an attribute in the xml quad file.
It understands two different specifications: p1="n:p" : get point p from square n (n, p integers) p1="p1,p2,p3" : make a 3d point out of these 3 floating point values

private 
Returns the index of the first graph node (i.e.
the graph node which will trigger a new lap when a kart first enters it). This is always 0 for normal direction (this is guaranteed by the track exporter), but in reverse mode (where node 0 is actually the end of the track) this is 0's successor.
void DriveGraph::getSuccessors  (  int  node_number, 
std::vector< unsigned int > &  succ,  
bool  for_ai = false 

)  const 
Returns the list of successors or a node.
node_number  The number of the node. 
succ  A vector of ints to which the successors are added. 
for_ai  true if only quads accessible by the AI should be returned. 

privatevirtual 
Implements Graph.

private 
Loads a drive graph from a file.
filename  Name of the quad file to load. 
filename  Name of the graph file to load. 
void DriveGraph::setDefaultStartPositions  (  AlignedArray< btTransform > *  start_transforms, 
unsigned int  karts_per_row,  
float  forwards_distance = 1.5f , 

float  sidewards_distance = 1.5f , 

float  upwards_distance = 0.0f 

)  const 
Sets all start positions depending on the drive graph.
The number of entries needed is defined by the size of the start_transform (though all entries will be overwritten). E.g. the karts will be placed as: 1 \ 2 +– row with three karts, each kart is 'sidewards_distance' 3 / to the right of the previous kart, and 4 'forwards_distance' behind the previous kart. 5 The next row starts again with the kart being 6 'forwards_distance' behind the end of the previous row. etc.
start_transforms  A vector sized to the needed number of start positions. The values will all be overwritten with the default start positions. 
karts_per_row  How many karts to place in each row. 
forwards_distance  Distance in forward (Z) direction between each kart. 
sidewards_distance  Distance in sidewards (X) direction between karts. 

private 
This function sets a default successor for all graph nodes that currently don't have a successor defined.
The default successor of node X is X+1.
void DriveGraph::setupPaths  (  ) 
This function defines the "pathtonodes" for each graph node that has more than one successor.
The pathtonodes indicates which successor to use to reach a certain node. This is e.g. used for the rubber ball to determine which path it is going to use to reach its target (this allows the ball to hit a target that is on a shortcut). The algorithm for the path computation favours the use of successor 0, i.e. it will if possible only use main driveline paths, not a shortcut (even though a shortcut could result in a faster way to the target)  but since shotcuts can potentially be hidden they should not be used (unless necessary). Only graph nodes with more than one successor have this data structure (since on other graph nodes only one path can be used anyway, this saves some memory).
This function takes absolute coordinates (coordinates in OpenGL space) and transforms them into coordinates based on the track.
The yaxis of the returned vector is how much of the track the point has gone through, the xaxis is on which side of the road it is (relative to a line connecting the two center points of a quad). The Y axis is not changed.
dst  Returns the results in the X and Z coordinates. 
xyz  The position of the kart. 
sector  The graph node the position is on. 
void DriveGraph::updateDistancesForAllSuccessors  (  unsigned int  indx, 
float  delta,  
unsigned int  recursive_count  
) 
Increases the distance from start for all nodes that are directly or indirectly a successor of the given node.
This code is used when two branches merge together, but since the latest 'fork' indicates a longer distance from start.
indx  Index of the node for which to increase the distance. 
delta  Amount by which to increase the distance. 
recursive_count  Counts how often this function was called recursively in order to catch incorrect graphs that contain loops. 