SuperTuxKart
arena_graph.hpp
1 //
2 // SuperTuxKart - a fun racing game with go-kart
3 // Copyright (C) 2016 SuperTuxKart Team
4 //
5 // This program is free software; you can redistribute it and/or
6 // modify it under the terms of the GNU General Public License
7 // as published by the Free Software Foundation; either version 3
8 // of the License, or (at your option) any later version.
9 //
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with this program; if not, write to the Free Software
17 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18 
19 #ifndef HEADER_ARENA_GRAPH_HPP
20 #define HEADER_ARENA_GRAPH_HPP
21 
22 #include "tracks/graph.hpp"
23 #include "utils/cpp2011.hpp"
24 
25 #include <set>
26 
27 class ArenaNode;
28 class XMLNode;
29 
34 class ArenaGraph : public Graph
35 {
36 private:
38  std::vector<std::vector<float>> m_distance_matrix;
39 
41  std::vector<std::vector<int16_t>> m_parent_node;
42 
44  std::set<int> m_red_node;
45 
46  std::set<int> m_blue_node;
47 
48  // ------------------------------------------------------------------------
49  void loadGoalNodes(const XMLNode *node);
50  // ------------------------------------------------------------------------
51  void loadNavmesh(const std::string &navmesh);
52  // ------------------------------------------------------------------------
53  void buildGraph();
54  // ------------------------------------------------------------------------
55  void setNearbyNodesOfAllNodes();
56  // ------------------------------------------------------------------------
57  void computeDijkstra(int n);
58  // ------------------------------------------------------------------------
59  void computeFloydWarshall();
60  // ------------------------------------------------------------------------
61  static std::vector<int16_t> getPathFromTo(int from, int to,
62  const std::vector< std::vector< int16_t > >& parent_node);
63  // ------------------------------------------------------------------------
64  virtual bool hasLapLine() const OVERRIDE { return false; }
65  // ------------------------------------------------------------------------
66  virtual void differentNodeColor(int n, video::SColor* c) const OVERRIDE;
67 
68 public:
69  static ArenaGraph* get() { return dynamic_cast<ArenaGraph*>(m_graph); }
70  // ------------------------------------------------------------------------
71  static void unitTesting();
72  // ------------------------------------------------------------------------
73  ArenaGraph(const std::string &navmesh, const XMLNode *node = NULL);
74  // ------------------------------------------------------------------------
75  virtual ~ArenaGraph() {}
76  // ------------------------------------------------------------------------
77  ArenaNode* getNode(unsigned int i) const;
78  // ------------------------------------------------------------------------
83  int getNextNode(int i, int j) const
84  {
85  if (i == Graph::UNKNOWN_SECTOR || j == Graph::UNKNOWN_SECTOR)
86  return Graph::UNKNOWN_SECTOR;
87  return (int)(m_parent_node[j][i]);
88  }
89  // ------------------------------------------------------------------------
91  float getDistance(int from, int to) const
92  {
93  if (from == Graph::UNKNOWN_SECTOR || to == Graph::UNKNOWN_SECTOR)
94  return 99999.0f;
95  return m_distance_matrix[from][to];
96  }
97 
98 }; // ArenaGraph
99 
100 #endif
void computeDijkstra(int n)
Dijkstra shortest path computation.
Definition: arena_graph.cpp:220
Definition: arena_node.hpp:31
void computeFloydWarshall()
THIS FUNCTION IS ONLY USED FOR UNIT-TESTING, to verify that the new Dijkstra algorithm gives the same...
Definition: arena_graph.cpp:277
This class stores a graph of quads.
Definition: graph.hpp:52
std::vector< std::vector< int16_t > > m_parent_node
The matrix that is used to store computed shortest paths.
Definition: arena_graph.hpp:41
std::set< int > m_red_node
Used in soccer mode to colorize the goal lines in minimap.
Definition: arena_graph.hpp:44
float getDistance(int from, int to) const
Returns the distance between any two nodes.
Definition: arena_graph.hpp:91
A graph made from navmesh.
Definition: arena_graph.hpp:34
std::vector< std::vector< float > > m_distance_matrix
The actual graph data structure, it is an adjacency matrix.
Definition: arena_graph.hpp:38
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).
Definition: arena_graph.cpp:365
utility class used to parse XML files
Definition: xml_node.hpp:47
static void unitTesting()
Unit testing for arena graph distance and parent node computation.
Definition: arena_graph.cpp:385
int getNextNode(int i, int j) const
Returns the next node on the shortest path from i to j.
Definition: arena_graph.hpp:83