We mask the class under the graph Boost. Part 3: Finding the Way

Prologue: Boost Concepts
Part 1: Connecting Associated Types Without Interfering with the Interface of the Source Class
Part 2: Finishing Up the Support for Concepts

In the previous articles of the series, we described the process of adapting the class of a cellular playing field to the concepts of boost graphs. Now we will consider actually what it was all about - the search for a path in the cell field. The boost search implementation allows you to fine-tune the algorithm, in this article we will give only one example of such a parameterization - the ability to specify different lengths of the edges of the graph.

We’ll start with the description of the parameter. You need to create an edge weight map that satisfies the ReadablePropertyMapConcept concept.. 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 - we 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;
    }
};

Using typedef, you can determine the type of key (Edge), the type of the return value (double), and the label by which boost can understand that values ​​can be obtained from the map (boost :: readable_property_map_tag). 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, let's introduce short type aliases (for ourselves)

typedef boost::property_map::const_type EdgeWeightMapConst;
typedef boost::property_traits::reference EdgeWeightMapValueType;
typedef boost::property_traits::key_type EdgeWeightMapKey;

The function should return the value from the map by key

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

Now you can specify a map of the weights of the ribs. Note that the declaration is made in the boost namespace.

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

Checking the concept

boost::function_requires >();

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 vertices by default. To do this, just specify the type of vertex properties; let it be the type of vertex index

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

This definition should also be in the boost namespace.

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

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

Please note that in this article the weights of the edges are not calculated (equal to 1), therefore there is no need to save the pointer to the graph in it, respectively, and the graph parameter is not used. We also define a function for determining the weight of an 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 finished, you can check

boost::function_requires >();

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

class GameFieldHeuristic: public boost::astar_heuristic
{
public:
	GameFieldHeuristic(const GameField& gameField, Vertex goal)
    : mGameField(&gameField)
    {
        std::pair goalPosition = getCoordinates(goal, gameField);
        mGoalX = goalPosition.first;
        mGoalY = goalPosition.second;
    };
    int operator()(Vertex v) {
        std::pair 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 on 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, so the square of the distance is calculated (the square root in the formula is omitted).

And finally, create a class that can signal the solution found. We will signal by raising a FoundGoal exception .

struct FoundGoal {};

Create a visitor class whose method examine_vertex is called for each vertex that the algorithm has reached. As soon as we get to the target vertex - 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 the 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 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 predecessor(num_vertices(graph));
    std::vector 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 coordinates = getCoordinates(i, graph);
            result.push_front(NextStep(coordinates.first, coordinates.second));
        }
    }
    return result;
}

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

I will not stop a few points. Firstly, calling the astar_search search function . At the beginning, nothing bodes - the usual parameters go: graph, starting point, heuristic, but then the construction begins through a dot 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 (so as not to get confused), the subtleties of the mechanism do not apply to the article, just a few comments.

1. The names of all parameters are defined in the boost namespace, however, you need to specify it only once at the beginning of the chain
2. Parameters are transferred as follows: the name of the parameter is written, then in parentheses is the value, the parameters are separated by a dot
3. The order of parameters can be any

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