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

A graph made from driveline. More...

#include <drive_graph.hpp>

Inheritance diagram for DriveGraph:
Inheritance graph
[legend]

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. More...
 
void getSuccessors (int node_number, std::vector< unsigned int > &succ, bool for_ai=false) const
 Returns the list of successors or a node. More...
 
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. More...
 
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. More...
 
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. More...
 
void setupPaths ()
 This function defines the "path-to-nodes" for each graph node that has more than one successor. More...
 
void computeChecklineRequirements ()
 Sets the checkline requirements for all nodes in the graph.
 
float getDistanceToNext (int n, int j) const
 Return the distance to the j-th successor of node n. More...
 
float getAngleToNext (int n, int j) const
 Returns the angle of the line between node n and its j-th. More...
 
int getNumberOfSuccessors (int n) const
 Returns the number of successors of a node n. More...
 
DriveNodegetNode (unsigned int j) const
 Returns the quad that belongs to a graph node. More...
 
float getDistanceFromStart (int j) const
 Returns the distance from the start to the beginning of a quad. More...
 
float getLapLength () const
 Returns the length of the main driveline. More...
 
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. 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 DriveGraphget ()
 
- 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 setDefaultSuccessors ()
 This function sets a default successor for all graph nodes that currently don't have a successor defined. More...
 
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. More...
 
void determineDirection (unsigned int current, unsigned int succ_index)
 Determines the direction of the drive graph when driving to the specified successor. More...
 
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. More...
 
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. More...
 
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. More...
 
unsigned int getStartNode () const
 Returns the index of the first graph node (i.e. More...
 
virtual bool hasLapLine () const OVERRIDE
 
virtual void differentNodeColor (int n, video::SColor *c) const OVERRIDE
 

Private Attributes

float m_lap_length
 The length of the first loop. More...
 
std::string m_quad_filename
 Stores the filename - just used for error messages. More...
 
bool m_reverse
 Wether the graph should be reverted or not.
 

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

Constructor & Destructor Documentation

◆ DriveGraph()

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.

Parameters
quad_file_nameName of the file of all quads
graph_file_nameName of the file describing the actual graph

Member Function Documentation

◆ computeDirectionData()

void DriveGraph::computeDirectionData ( )
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).

◆ computeDistanceFromStart()

void DriveGraph::computeDistanceFromStart ( unsigned int  node,
float  new_distance 
)
private

Recursively determines the distance the beginning (lower end) of the quads have from the start of the track.

Parameters
nodeThe node index for which to set the distance from start.
new_distanceThe new distance for the specified graph node.

◆ determineDirection()

void DriveGraph::determineDirection ( unsigned int  current,
unsigned int  succ_index 
)
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.

Parameters
currentIndex of the graph node with which to start ('n' in the description above).
succ_indexThe successor to be followed from the current node. If there should be any other branches later, successor 0 will always be tetsed.

◆ getAngleToNext()

float DriveGraph::getAngleToNext ( int  n,
int  j 
) const

Returns the angle of the line between node n and its j-th.

successor.

◆ getDistanceFromStart()

float DriveGraph::getDistanceFromStart ( int  j) const

Returns the distance from the start to the beginning of a quad.

◆ getDistanceToNext()

float DriveGraph::getDistanceToNext ( int  n,
int  j 
) const

Return the distance to the j-th successor of node n.

◆ getLapLength()

float DriveGraph::getLapLength ( ) const
inline

Returns the length of the main driveline.

◆ getNode()

DriveNode * DriveGraph::getNode ( unsigned int  j) const

Returns the quad that belongs to a graph node.

◆ getNumberOfSuccessors()

int DriveGraph::getNumberOfSuccessors ( int  n) const

Returns the number of successors of a node n.

◆ getPoint()

void DriveGraph::getPoint ( const XMLNode xml,
const std::string &  attribute_name,
Vec3 result 
) const
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

◆ getStartNode()

unsigned int DriveGraph::getStartNode ( ) const
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.

◆ getSuccessors()

void DriveGraph::getSuccessors ( int  node_number,
std::vector< unsigned int > &  succ,
bool  for_ai = false 
) const

Returns the list of successors or a node.

Parameters
node_numberThe number of the node.
succA vector of ints to which the successors are added.
for_aitrue if only quads accessible by the AI should be returned.

◆ load()

void DriveGraph::load ( const std::string &  quad_file_name,
const std::string &  filename 
)
private

Loads a drive graph from a file.

Parameters
filenameName of the quad file to load.
filenameName of the graph file to load.

◆ setDefaultStartPositions()

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.

Parameters
start_transformsA vector sized to the needed number of start positions. The values will all be overwritten with the default start positions.
karts_per_rowHow many karts to place in each row.
forwards_distanceDistance in forward (Z) direction between each kart.
sidewards_distanceDistance in sidewards (X) direction between karts.

◆ setDefaultSuccessors()

void DriveGraph::setDefaultSuccessors ( )
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.

◆ setupPaths()

void DriveGraph::setupPaths ( )

This function defines the "path-to-nodes" for each graph node that has more than one successor.

The path-to-nodes 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).

◆ spatialToTrack()

void DriveGraph::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.

The y-axis of the returned vector is how much of the track the point has gone through, the x-axis 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.

Parameters
dstReturns the results in the X and Z coordinates.
xyzThe position of the kart.
sectorThe graph node the position is on.

◆ updateDistancesForAllSuccessors()

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.

Parameters
indxIndex of the node for which to increase the distance.
deltaAmount by which to increase the distance.
recursive_countCounts how often this function was called recursively in order to catch incorrect graphs that contain loops.

Member Data Documentation

◆ m_lap_length

float DriveGraph::m_lap_length
private

The length of the first loop.

◆ m_quad_filename

std::string DriveGraph::m_quad_filename
private

Stores the filename - just used for error messages.


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