Masking the class under the Boost graph. Part 3: Finding the Way

Prologue: Boost Concepts
Part 1: Connection of associated types without interfering with the source class interface
Part 2: Completing the implementation of concept support

In the previous articles of the cycle, the process of adapting the class of the cellular playing field to the concepts of graphs boost was described. Now we will consider the very thing for which everything was started - the search for a path in the cellular field. The implementation of the boost search allows you to fine-tune the algorithm, in this article there will be only one example of such a parameterization - the ability to set different lengths of the graph edges.

With the description of the parameter and begin. You want to create an edge scale map that satisfies the concept of ReadablePropertyMapConcept . It is implemented quite simply - you need to define several types and the operator [], which, based on the key-edge, returns its length. For simplicity, the calculations will be omitted - let's take the size of all edges equal to one.

struct EdgeWeightMap { typedef double value_type; typedef value_type reference; typedef Edge key_type; typedef boost::readable_property_map_tag category; reference operator[](key_type e) const { return 1; } }; 

With the help of a typedef, the key type (Edge), the return value type (double) and the label by which boost can understand that values ​​can be obtained from the map (boost :: readable_property_map_tag) are determined. Edge and other custom types are defined in the first part of the article .
')
Next, you need to implement the function required by the concept. But first we introduce short type aliases (for yourself)

 typedef boost::property_map<GameField, boost::edge_weight_t>::const_type EdgeWeightMapConst; typedef boost::property_traits<EdgeWeightMapConst>::reference EdgeWeightMapValueType; typedef boost::property_traits<EdgeWeightMapConst>::key_type EdgeWeightMapKey; 

The function must return a value from the map by key.

 EdgeWeightMapValueType get(EdgeWeightMapConst pMap, EdgeWeightMapKey pKey) { return pMap[pKey]; } 

Now you can set the edge scale map. Note that the declaration is in the namespace boost.

 namespace boost { template<> struct property_map< GameField, edge_weight_t > { typedef EdgeWeightMap type; typedef EdgeWeightMap const_type; }; } 

We check the concept

 boost::function_requires<boost::ReadablePropertyMapConcept<EdgeWeightMap, Edge> >(); 

You can also set the properties of the vertices - we will not do this, but we will have to create a stub so that boost can generate a map for the default vertices. For this, it is enough to specify the type of vertex properties, let it be the type of the vertex index

 namespace boost { template <> struct vertex_property_type<GameField> { typedef boost::graph_traits<GameField>::vertex_descriptor type; }; } 

This definition must also be in the namespace boost.

We implement the support of our graph to another concept - ReadablePropertyGraphConcept , i.e. "Graph with properties". To do this, you need to set two functions. The first one creates a map of graph properties.

 EdgeWeightMapConst get(boost::edge_weight_t, const GameField& graph) { return EdgeWeightMapConst(); } 

Please note that in this article the weight of the ribs is not calculated (equal to 1), therefore there is no need to save a pointer to the graph in it, respectively, and the graph parameter is not used. Also set the function to determine the weight of the edge

 EdgeWeightMapValueType get(boost::edge_weight_t tag, const GameField& g, EdgeWeightMapKey e) { return get(tag, g)[e]; } 

On this with the next concept is completed, you can check

 boost::function_requires<boost::ReadablePropertyGraphConcept<GameField, Edge, boost::edge_weight_t> >(); 

The algorithm for finding the path A * belongs to the class of informed , and, therefore, it can (and should) be helped. To do this, we define heuristics, which will allow us to find more effective search directions. Heuristics is a functor that determines how far a given vertex is far from the target. Euclidean metric used

 class GameFieldHeuristic: public boost::astar_heuristic<GameField, int> { public: GameFieldHeuristic(const GameField& gameField, Vertex goal) : mGameField(&gameField) { std::pair<int, int> goalPosition = getCoordinates(goal, gameField); mGoalX = goalPosition.first; mGoalY = goalPosition.second; }; int operator()(Vertex v) { std::pair<int, int> position = getCoordinates(v, *mGameField); int dx = mGoalX - position.first; int dy = mGoalY - position.second; int result =dx * dx + dy * dy; return result; } private: int mGoalX; int mGoalY; const GameField* mGameField; }; 

The class is quite simple - the playing field and the index of the target vertex are passed to the constructor. The index calculates the coordinates of the vertex on the cell field (more about this in the first part of the article ). For the algorithm, it is important to increase or decrease the distance - the exact value is not required, therefore, the square of the distance is calculated (the square root in the formula is omitted).

And finally, create a class that can signal the found solution. We will signal through the exclusion of the FoundGoal exception.

 struct FoundGoal {}; 

Create a class visitor, whose examine_vertex method is called for each vertex the algorithm has reached. As soon as we reach the top of the target, we will raise an exception

 struct AstarGoalVisitor : public boost::default_astar_visitor { AstarGoalVisitor(Vertex goal) : mGoal(goal) { } void examine_vertex(Vertex u, const GameField&) { if (u == mGoal) { throw FoundGoal(); } } private: Vertex mGoal; }; 

Finally, we write the function of finding a path from one point of the graph to another. As parameters, it takes the coordinates of the source and target vertices, as well as a link to the graph

 typedef std::list<NextStep> StepsList; StepsList findPath(int sourceX, int sourceY, int targetX, int targetY, const GameFieldMap& graph) { GraphVertex source = getVertex(sourceX, sourceY, graph); GraphVertex destination = getVertex(targetX, targetY, graph); std::vector<GraphVertex> predecessor(num_vertices(graph)); std::vector<edge_weight_map_value_type> dist(num_vertices(graph)); StepsList result; try { astar_search(graph, source, GameFieldHeuristic(graph, destination), boost::visitor(AstarGoalVisitor(destination)). predecessor_map(&predecessor[0]). distance_map(&dist[0])); } catch (FoundGoal f) { for (int i = destination; i != source; i = predecessor[i]) { std::pair<int, int> coordinates = getCoordinates(i, graph); result.push_front(NextStep(coordinates.first, coordinates.second)); } } return result; } 

The function translates the vertex coordinates into integer indices. Then a predecessor vector is created, from which the result and distance vector dist will be extracted.

I will stop not a few moments. First, the search function call astar_search . At the beginning, nothing portends - the usual parameters go: the graph, the starting point, heuristics, but then the construction starts through a point instead of a comma. This is not a typo. For functions with a large number of optional parameters, boost offers its own way of passing named arguments (not to get confused), the subtleties of the mechanism do not apply to the article, just a few remarks.

1. The names of all parameters are defined in the namespace boost, but it must be specified only once at the beginning of the chain
2. Parameters are passed as follows: the name of the parameter is written, then the value is in parentheses, the parameters are separated by a period
3. The order of the parameters can be any

If we get into the catch block, the path is found. It is written to the vector predecessor , in the form of a list of previous vertices. That is, the position of the predecessor [vertex] is the index of the vertex, from which we get to the vertex. In this way, turning one's predecessors one by one, one can get a more familiar way - a sequence of vertices that need to go from point A to point B. The result is written into the list of results.