Routemaker::Graph< T > Class Template Reference

Abstract graph interface optimized for path-finding. More...

#include <graph.h>

Collaboration diagram for Routemaker::Graph< T >:

Public Types
using	NodePtr = std::shared_ptr< Node< T > >
	Helper alias to make code more readable.

Public Member Functions
virtual std::vector< NodePtr >	GetNeighbors (NodePtr node)=0
	Collects all neighbor nodes of node.
virtual double	GetCost (NodePtr a, NodePtr b)=0
	Returns the cost between a and b.
virtual bool	HasLineOfSight (NodePtr a, NodePtr b)=0
	Determines if there is a direct line of sight between node a and node b.
virtual void	ResetNodes (void)=0
	Resets all local and global goals and parent relationships of all nodes.
void	SolveAStar (NodePtr start, NodePtr goal)
	Finds cheapest path from start to goal.
void	PostSmooth (NodePtr start, NodePtr goal)
	Simplifies the path from start to goal.

Detailed Description

template<typename T>
class Routemaker::Graph< T >

Abstract graph interface optimized for path-finding.

Template Parameters

T	Type of user data to store in each node

This interface is designed to be flexible and scalable. The sub-classes are required to implement a few methods, such as Graph::GetNeighbors and Graph::GetCost for the A* path-finding algorithm to work.

Definition at line 73 of file graph.h.

Member Typedef Documentation

NodePtr

template<typename T >

using Routemaker::Graph< T >::NodePtr = std::shared_ptr<Node<T> >

Helper alias to make code more readable.

Definition at line 76 of file graph.h.

Member Function Documentation

GetCost()

template<typename T >

virtual double Routemaker::Graph< T >::GetCost ( NodePtr  a, NodePtr  b  )

pure virtual

Returns the cost between a and b.

Implemented by sub-classes of Graph. The a* path-finding algorithm uses cost to efficiently find the best path between two nodes. In order to do this, it requires some method of calculating the cost of moving between any two nodes. It is up to the sub-class to define how this is calulated. An example of this cost may be the euclidean distance between two nodes.

Parameters

a	Pointer to the first Node
b	Pointer to the second Node

Returns

Cost between node a and node b.

Implemented in Routemaker::Routemaker.

GetNeighbors()

template<typename T >

virtual std::vector< NodePtr > Routemaker::Graph< T >::GetNeighbors ( NodePtr  node )

pure virtual

Collects all neighbor nodes of node.

Implemented by sub-classes of Graph. The neighbor relationship between nodes define the edges of the graph. It is up to the subclass to define these relationships. For a 2D grid, the neighbors would simply be the nodes directly to the north, south, east and west, in addition to the corners between them. For a road network, the relationships may be more complex.

Parameters

node	A pointer to the node from which to collect all neighbors

Returns

A vector of pointers to all the neighbors of node

Implemented in Routemaker::Routemaker.

HasLineOfSight()

template<typename T >

virtual bool Routemaker::Graph< T >::HasLineOfSight ( NodePtr  a, NodePtr  b  )

pure virtual

Determines if there is a direct line of sight between node a and node b.

Implemented by sub-classes of Graph. The Graph::PostSmooth method traverses the already found path through the A* path-finding algorithm and simplifies it by using this method. In a graph representing a 2D grid, a Bresenham implementation or ray-casting can be used to determine line of sight.

Parameters

a	Pointer to the first Node
b	Pointer to the second Node

Returns

bool specifying whether or not there is a direct line of sight

Implemented in Routemaker::Routemaker.

PostSmooth()

template<typename T >

void Routemaker::Graph< T >::PostSmooth	(	NodePtr	start,
		NodePtr	goal
	)

Simplifies the path from start to goal.

Parameters

start	Pointer to the start node of the path
goal	Pointer to the end node of the path

Should be run on the same nodes as Graph::SolveAStar, and should only be called after Graph::SolveAStar has finished.

Definition at line 231 of file graph.h.

ResetNodes()

template<typename T >

virtual void Routemaker::Graph< T >::ResetNodes ( void  )

pure virtual

Resets all local and global goals and parent relationships of all nodes.

Implemented by sub-classes of Graph. In order to be able to re-use the same graph for several A* searches, the Graph::SolveAStar method needs to be able to reset all the nodes. As this interface does not contain the actual collection of nodes, this needs to be implemented in the sub-classes.

Implemented in Routemaker::Routemaker.

SolveAStar()

template<typename T >

void Routemaker::Graph< T >::SolveAStar	(	NodePtr	start,
		NodePtr	goal
	)

Finds cheapest path from start to goal.

Parameters

start	Pointer to the node to start the path from
goal	Pointer to the node to find the path to

Using the A* algorithm, this method explores the graph's nodes and updates their local and global goals, their visited flags, as well as their parent relationships.

When the algorithm finishes, given that a path exists between the nodes, the cheapest path between them is defined by the parent relationships. The path can be extracted by starting at the goal and following the Node::Parent pointers until start is reached, saving each node in a list and reversing it at the end.

Definition at line 165 of file graph.h.

---

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

• include/routemaker/graph.h