Menu
▾
▴
[Supertuxkart-commit] SF.net SVN: supertuxkart:[9773] main/trunk/src
|
From: <hik...@us...> - 2011-09-06 06:56:06
|
Revision: 9773
http://supertuxkart.svn.sourceforge.net/supertuxkart/?rev=9773&view=rev
Author: hikerstk
Date: 2011-09-06 06:56:00 +0000 (Tue, 06 Sep 2011)
Log Message:
-----------
Added information about which successor of a graph node to
use in order to reach a certain target graph node.
This is now used by the rubber ball to follow karts even
if they are on an alternatice way/shortcut.
Modified Paths:
--------------
main/trunk/src/items/rubber_ball.cpp
main/trunk/src/tracks/graph_node.cpp
main/trunk/src/tracks/graph_node.hpp
main/trunk/src/tracks/quad_graph.cpp
main/trunk/src/tracks/quad_graph.hpp
main/trunk/src/tracks/track.cpp
Modified: main/trunk/src/items/rubber_ball.cpp
===================================================================
--- main/trunk/src/items/rubber_ball.cpp 2011-09-06 06:09:27 UTC (rev 9772)
+++ main/trunk/src/items/rubber_ball.cpp 2011-09-06 06:56:00 UTC (rev 9773)
@@ -150,8 +150,15 @@
unsigned int RubberBall::getSuccessorToHitTarget(unsigned int node_index,
float *dist)
{
- // For now: always pick a successor on the main driveline.
int succ = 0;
+ LinearWorld *lin_world = dynamic_cast<LinearWorld*>(World::getWorld());
+ // FIXME: what does the rubber ball do in case of battle mode??
+ if(lin_world)
+ {
+ unsigned int sect =
+ lin_world->getSectorForKart(m_target->getWorldKartId());
+ succ = QuadGraph::get()->getNode(node_index).getSuccessorToReach(sect);
+ }
if(dist)
*dist += QuadGraph::get()->getNode(node_index)
.getDistanceToSuccessor(succ);
Modified: main/trunk/src/tracks/graph_node.cpp
===================================================================
--- main/trunk/src/tracks/graph_node.cpp 2011-09-06 06:09:27 UTC (rev 9772)
+++ main/trunk/src/tracks/graph_node.cpp 2011-09-06 06:56:00 UTC (rev 9773)
@@ -46,6 +46,7 @@
m_node_index = node_index;
m_predecessor = -1;
m_distance_from_start = 0;
+
const Quad &quad = m_all_quads->getQuad(m_quad_index);
// FIXME: the following values should depend on the actual orientation
// of the quad. ATM we always assume that indices 0,1 are the lower end,
@@ -118,6 +119,71 @@
} // addSuccessor
// ----------------------------------------------------------------------------
+/** If this node has more than one successor, it will set up a vector that
+ * contains the direction to use when a certain graph node X should be
+ * reached.
+ */
+void GraphNode::setupPathsToNode()
+{
+ if(m_successor_node.size()<2) return;
+
+ const unsigned int num_nodes = QuadGraph::get()->getNumNodes();
+ m_path_to_node.resize(num_nodes);
+
+ // Initialise each graph node with -1, indicating that
+ // it hasn't been reached yet.
+ for(unsigned int i=0; i<num_nodes; i++)
+ m_path_to_node[i] = -1;
+
+ // Indicate that this node can be reached from this node by following
+ // successor 0 - just a dummy value that might only be used during the
+ // recursion below.
+ m_path_to_node[m_node_index] = 0;
+
+ // A simple depth first search is used to determine which successor to
+ // use to reach a certain graph node. Using Dijkstra's algorithm would
+ // give the shortest way to reach a certain node, but the shortest way
+ // might involve some shortcuts which are hidden, and should therefore
+ // not be used.
+ for(unsigned int i=0; i<getNumberOfSuccessors(); i++)
+ {
+ GraphNode &gn = QuadGraph::get()->getNode(getSuccessor(i));
+ gn.markAllSuccessorsToUse(i, &m_path_to_node);
+ }
+#ifdef DEBUG
+ for(unsigned int i=0; i<m_path_to_node.size(); i++)
+ {
+ if(m_path_to_node[i]==-1)
+ printf("[WARNING] No path to node %d found on graph node %d.\n",
+ i, m_node_index);
+ }
+#endif
+} // setupPathsToNode
+
+// ----------------------------------------------------------------------------
+/** This function marks that the successor n should be used to reach this
+ * node. It then recursively (depth first) does the same for all its
+ * successors. Depth-first
+ * \param n The successor which should be used in m_path_node to reach
+ * this node.
+ * \param path_to_node The path-to-node data structure of the node for
+ * which the paths are currently determined.
+ */
+void GraphNode::markAllSuccessorsToUse(unsigned int n,
+ PathToNodeVector *path_to_node)
+{
+ // End recursion if the path to this node has already been found.
+ if( (*path_to_node)[m_node_index] >-1) return;
+
+ (*path_to_node)[m_node_index] = n;
+ for(unsigned int i=0; i<getNumberOfSuccessors(); i++)
+ {
+ GraphNode &gn = QuadGraph::get()->getNode(getSuccessor(i));
+ gn.markAllSuccessorsToUse(n, path_to_node);
+ }
+} // markAllSuccesorsToUse
+
+// ----------------------------------------------------------------------------
/** Returns the distance a point has from this quad in forward and sidewards
* direction, i.e. how far forwards the point is from the beginning of the
* quad, and how far to the side from the line connecting the center points
Modified: main/trunk/src/tracks/graph_node.hpp
===================================================================
--- main/trunk/src/tracks/graph_node.hpp 2011-09-06 06:09:27 UTC (rev 9772)
+++ main/trunk/src/tracks/graph_node.hpp 2011-09-06 06:56:00 UTC (rev 9773)
@@ -88,6 +88,16 @@
* from the center of the drivelines anyway. */
core::line2df m_line;
+ typedef std::vector<int> PathToNodeVector;
+ /** This vector is only used if the graph node has more than one
+ * successor. In this case m_path_to_node[X] will contain the index
+ * of the successor to use in order to reach graph node X for this
+ * graph nodes. */
+ PathToNodeVector m_path_to_node;
+
+ void markAllSuccessorsToUse(unsigned int n,
+ PathToNodeVector *m_path_to_node);
+
public:
/** Keep a shared pointer so that some asserts and tests can be
* done without adding additional parameters. */
@@ -100,7 +110,8 @@
void addSuccessor (unsigned int to);
void getDistances(const Vec3 &xyz, Vec3 *result);
float getDistance2FromPoint(const Vec3 &xyz);
-
+ void setupPathsToNode();
+ // ------------------------------------------------------------------------
/** Returns the i-th successor node. */
unsigned int getSuccessor(unsigned int i) const
{ return m_successor_node[i]; }
@@ -163,6 +174,17 @@
/** Returns a predecessor for this node. */
int getPredecessor() const {return m_predecessor; }
// ------------------------------------------------------------------------
+ /** Returns which successor node to use in order to be able to reach the
+ * given node n.
+ * \param n Index of the graph node to reach.
+ */
+ int getSuccessorToReach(unsigned int n)
+ {
+ // If we have a path to node vector, use its information, otherwise
+ // (i.e. there is only one successor anyway) use this one successor.
+ return m_path_to_node.size()>0 ? m_path_to_node[n] : 0;
+ }
+ // ------------------------------------------------------------------------
}; // GraphNode
#endif
Modified: main/trunk/src/tracks/quad_graph.cpp
===================================================================
--- main/trunk/src/tracks/quad_graph.cpp 2011-09-06 06:09:27 UTC (rev 9772)
+++ main/trunk/src/tracks/quad_graph.cpp 2011-09-06 06:56:00 UTC (rev 9773)
@@ -166,6 +166,7 @@
}
delete xml;
+ // Define the track length
for(unsigned int i=0; i<m_all_nodes.size(); i++)
{
if(m_all_nodes[i]->getSuccessor(0)==0)
@@ -176,8 +177,31 @@
}
}
setDefaultSuccessors();
+
} // load
+// ----------------------------------------------------------------------------
+/** 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).
+ */
+void QuadGraph::setupPaths()
+{
+ for(unsigned int i=0; i<getNumNodes(); i++)
+ {
+ m_all_nodes[i]->setupPathsToNode();
+ }
+} // setupPaths
+
// -----------------------------------------------------------------------------
/** 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.
Modified: main/trunk/src/tracks/quad_graph.hpp
===================================================================
--- main/trunk/src/tracks/quad_graph.hpp 2011-09-06 06:09:27 UTC (rev 9772)
+++ main/trunk/src/tracks/quad_graph.hpp 2011-09-06 06:56:00 UTC (rev 9773)
@@ -113,7 +113,7 @@
=video::SColor(127, 255, 255, 255) );
void mapPoint2MiniMap(const Vec3 &xyz, Vec3 *out) const;
void updateDistancesForAllSuccessors(unsigned int indx, float delta);
-
+ void setupPaths();
// ----------------------------------------------------------------------
/** Returns the one instance of this object. It is possible that there
* is no instance created (e.g. in battle mode, since it doesn't have
Modified: main/trunk/src/tracks/track.cpp
===================================================================
--- main/trunk/src/tracks/track.cpp 2011-09-06 06:09:27 UTC (rev 9772)
+++ main/trunk/src/tracks/track.cpp 2011-09-06 06:56:00 UTC (rev 9773)
@@ -393,6 +393,8 @@
{
QuadGraph::create(m_root+"/"+m_all_modes[mode_id].m_quad_name,
m_root+"/"+m_all_modes[mode_id].m_graph_name);
+
+ QuadGraph::get()->setupPaths();
#ifdef DEBUG
for(unsigned int i=0; i<QuadGraph::get()->getNumNodes(); i++)
{
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|