TaxiPathGraph Class Reference

#include <TaxiPathGraph.h>

Classes
struct	EdgeCost

Public Member Functions
void	Initialize ()
std::size_t	GetCompleteNodeRoute (TaxiNodesEntry const *from, TaxiNodesEntry const *to, Player const *player, std::vector< uint32 > &shortestPath)

Static Public Member Functions
static TaxiPathGraph &	Instance ()

Private Types
typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS, boost::property < boost::vertex_index_t, uint32 >, boost::property < boost::edge_weight_t, EdgeCost > >	Graph
typedef boost::property_map < Graph, boost::edge_weight_t > ::type	WeightMap
typedef Graph::vertex_descriptor	vertex_descriptor
typedef Graph::edge_descriptor	edge_descriptor
typedef std::pair< uint32, uint32 >	edge

Private Member Functions
	TaxiPathGraph ()
	~TaxiPathGraph ()
void	AddVerticeAndEdgeFromNodeInfo (TaxiNodesEntry const *from, TaxiNodesEntry const *to, uint32 pathId, std::vector< std::pair< edge, EdgeCost >> &edges)
vertex_descriptor	GetVertexIDFromNodeID (TaxiNodesEntry const *node)
uint32	GetNodeIDFromVertexID (vertex_descriptor vertexID)
vertex_descriptor	CreateVertexFromFromNodeInfoIfNeeded (TaxiNodesEntry const *node)
std::size_t	GetVertexCount ()
	TaxiPathGraph (TaxiPathGraph const &)=delete
TaxiPathGraph &	operator= (TaxiPathGraph const &)=delete

Private Attributes
Graph	m_graph
std::vector< TaxiNodesEntry const * >	m_vertices

Member Typedef Documentation

typedef std::pair<uint32, uint32> TaxiPathGraph::edge

private

typedef Graph::edge_descriptor TaxiPathGraph::edge_descriptor

private

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::property<boost::vertex_index_t, uint32>, boost::property<boost::edge_weight_t, EdgeCost> > TaxiPathGraph::Graph

private

typedef Graph::vertex_descriptor TaxiPathGraph::vertex_descriptor

private

typedef boost::property_map<Graph, boost::edge_weight_t>::type TaxiPathGraph::WeightMap

private

Constructor & Destructor Documentation

TaxiPathGraph::TaxiPathGraph ( )

inlineprivate

{ }

TaxiPathGraph::~TaxiPathGraph ( )

inlineprivate

{ }

TaxiPathGraph::TaxiPathGraph ( TaxiPathGraph const &  )

privatedelete

Member Function Documentation

void TaxiPathGraph::AddVerticeAndEdgeFromNodeInfo ( TaxiNodesEntry const *  from, TaxiNodesEntry const *  to, uint32  pathId, std::vector< std::pair< edge, EdgeCost >> &  edges  )

private

{
 if (from != to)
 {
 vertex_descriptor fromVertexID = CreateVertexFromFromNodeInfoIfNeeded(from);
 vertex_descriptor toVertexID = CreateVertexFromFromNodeInfoIfNeeded(to);

 float totalDist = 0.0f;
 TaxiPathNodeList const& nodes = sTaxiPathNodesByPath[pathId];
 if (nodes.size() < 2)
 {
 edges.push_back(std::make_pair(edge(fromVertexID, toVertexID), EdgeCost{ to, 0xFFFF }));
 return;
 }

 std::size_t last = nodes.size();
 std::size_t first = 0;
 if (nodes.size() > 2)
 {
 --last;
 ++first;
 }

 for (std::size_t i = first + 1; i < last; ++i)
 {
 if (nodes[i - 1]->Flags & TAXI_PATH_NODE_FLAG_TELEPORT)
 continue;

 uint32 map1, map2;
 DBCPosition2D pos1, pos2;

 DeterminaAlternateMapPosition(nodes[i - 1]->MapID, nodes[i - 1]->Loc.X, nodes[i - 1]->Loc.Y, nodes[i - 1]->Loc.Z, &map1, &pos1);
 DeterminaAlternateMapPosition(nodes[i]->MapID, nodes[i]->Loc.X, nodes[i]->Loc.Y, nodes[i]->Loc.Z, &map2, &pos2);

 if (map1 != map2)
 continue;

 totalDist += std::sqrt(
 std::pow(pos2.X - pos1.X, 2) +
 std::pow(pos2.Y - pos1.Y, 2) +
 std::pow(nodes[i]->Loc.Z - nodes[i - 1]->Loc.Z, 2));
 }

 uint32 dist = uint32(totalDist);
 if (dist > 0xFFFF)
 dist = 0xFFFF;

 edges.push_back(std::make_pair(edge(fromVertexID, toVertexID), EdgeCost{ to, dist }));
 }
}

Here is the call graph for this function:

Here is the caller graph for this function:

TaxiPathGraph::vertex_descriptor TaxiPathGraph::CreateVertexFromFromNodeInfoIfNeeded ( TaxiNodesEntry const *  node )

private

{
 //Check if we need a new one or if it may be already created
 if (m_vertices.size() <= node->LearnableIndex)
 m_vertices.resize(node->LearnableIndex + 1);

 m_vertices[node->LearnableIndex] = node;
 return node->LearnableIndex;
}

Here is the caller graph for this function:

std::size_t TaxiPathGraph::GetCompleteNodeRoute	(	TaxiNodesEntry const *	from,
		TaxiNodesEntry const *	to,
		Player const *	player,
		std::vector< uint32 > &	shortestPath
	)

{
 /*
 Information about node algorithm from client
 Since client does not give information about *ALL* nodes you have to pass by when going from sourceNodeID to destinationNodeID, we need to use Dijkstra algorithm.
 Examining several paths I discovered the following algorithm:
 * If destinationNodeID has is the next destination, connected directly to sourceNodeID, then, client just pick up this route regardless of distance
 * else we use dijkstra to find the shortest path.
 * When early landing is requested, according to behavior on retail, you can never end in a node you did not discovered before
 */

 // Find if we have a direct path
 uint32 pathId, goldCost;
 sObjectMgr->GetTaxiPath(from->ID, to->ID, pathId, goldCost);
 if (pathId)
 shortestPath = { from->ID, to->ID };
 else
 {
 shortestPath.clear();
 std::vector<vertex_descriptor> p(boost::num_vertices(m_graph));

 boost::dijkstra_shortest_paths(m_graph, GetVertexIDFromNodeID(from),
 boost::predecessor_map(boost::make_iterator_property_map(p.begin(), boost::get(boost::vertex_index, m_graph)))
 .weight_map(boost::make_transform_value_property_map(
 [player](EdgeCost const& edgeCost) { return edgeCost.EvaluateDistance(player); },
 boost::get(boost::edge_weight, m_graph))));

 // found a path to the goal
 for (vertex_descriptor v = GetVertexIDFromNodeID(to); ; v = p[v])
 {
 shortestPath.push_back(GetNodeIDFromVertexID(v));
 if (v == p[v])
 break;
 }

 std::reverse(shortestPath.begin(), shortestPath.end());
 }

 return shortestPath.size();
}

Here is the call graph for this function:

uint32 TaxiPathGraph::GetNodeIDFromVertexID ( vertex_descriptor  vertexID )

private

{
 if (vertexID < m_vertices.size())
 return m_vertices[vertexID]->ID;

 return std::numeric_limits<uint32>::max();
}

Here is the call graph for this function:

Here is the caller graph for this function:

std::size_t TaxiPathGraph::GetVertexCount ( )

private

{
 //So we can use this function for readability, we define either max defined vertices or already loaded in graph count
 return std::max(boost::num_vertices(m_graph), m_vertices.size());
}

Here is the call graph for this function:

Here is the caller graph for this function:

TaxiPathGraph::vertex_descriptor TaxiPathGraph::GetVertexIDFromNodeID ( TaxiNodesEntry const *  node )

private

{
 return node->LearnableIndex;
}

Here is the caller graph for this function:

void TaxiPathGraph::Initialize

(

)

{
 if (GetVertexCount() > 0)
 return;

 std::vector<std::pair<edge, EdgeCost>> edges;

 // Initialize here
 for (TaxiPathEntry const* path : sTaxiPathStore)
 {
 TaxiNodesEntry const* from = sTaxiNodesStore.LookupEntry(path->From);
 TaxiNodesEntry const* to = sTaxiNodesStore.LookupEntry(path->To);
 if (from && to && from->Flags & (TAXI_NODE_FLAG_ALLIANCE | TAXI_NODE_FLAG_HORDE) && to->Flags & (TAXI_NODE_FLAG_ALLIANCE | TAXI_NODE_FLAG_HORDE))
 AddVerticeAndEdgeFromNodeInfo(from, to, path->ID, edges);
 }

 // create graph
 m_graph = Graph(GetVertexCount());
 WeightMap weightmap = boost::get(boost::edge_weight, m_graph);

 for (std::size_t j = 0; j < edges.size(); ++j)
 {
 edge_descriptor e = boost::add_edge(edges[j].first.first, edges[j].first.second, m_graph).first;
 weightmap[e] = edges[j].second;
 }
}

Here is the call graph for this function:

TaxiPathGraph & TaxiPathGraph::Instance ( )

static

{
 static TaxiPathGraph instance;
 return instance;
}

TaxiPathGraph& TaxiPathGraph::operator= ( TaxiPathGraph const &  )

privatedelete

Member Data Documentation

Graph TaxiPathGraph::m_graph

private

std::vector<TaxiNodesEntry const*> TaxiPathGraph::m_vertices

private

---

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

• src/server/game/Entities/Taxi/TaxiPathGraph.h
• src/server/game/Entities/Taxi/TaxiPathGraph.cpp