Masking a Class in Boost Graph. Part 3: Finding the Path

In the previous articles of the series we’ve reviewed the adaptive process of the square game field for concepts of boost graphs. Now we’ll consider the process of finding the path in the square field. Implementation of boost search allows adapting the algorithm quite accurately. In this article we’ll provide just one example of such parameterization – an ability to create various lengths of graph edges.

Let’s begin with describing the parameter. We should create a map of edge weights. This map will meet requirements of ReadablePropertyMapConcept concept. It’s quite easy to implement. We should define several types and [] iterator. On the basis of the key-type edge the latter returns its length.

It’s quite easy to implement it. We just need to define several types. For simplicity, we’ll omit the calculations and accept 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 typedef we define the type of a key (Edge), the type of returned value (double) and a tag. The tag will help boost to understand that it’s possible to get values from the map (boost::readable_property_map_tag). Edge and other user types are defined in the first part of the series.

Then we’ll implement a function required by the concept. But at first let’s introduce short alias names for the types (for our use)

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

The function should return a value from the map according to the key.

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

Now we can define the map of edge weights. Note that we perform the declaration in the boost name space.

namespace boost
{
    template
    struct property_map {
        typedef EdgeWeightMap type;
        typedef EdgeWeightMap const_type;
    };
}

Let's verify the concept

boost::function_requires<:readablepropertymapconcept edge> >();

We could also define the properties of vertices, but won’t do that. We’ll have to create a stub so that boost could generate the map for vertices by default. We should indicate the type of vertices properties for that purpose. Let it be the type of the vertex index.

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

This definition should also be located in the boost name space.

Now let’s make our graph to support one more concept – ReadablePropertyGraphConcept – i.e. “graph with properties”. We’ll define two functions. The first one will create the map of graph properties:

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

Please note that edge weights are not calculated (they’re equal to 1). Therefore, there’s no point in saving a pointer to the graph. So the graph parameter isn’t used. We’ll also define a function to determine the edge weight:

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

That’s it with another concept. Now we can perform a check

boost::function_requires<:readablepropertygraphconcept edge boost::edge_weight_t> >();

A* search algorithm refers to the class of informed(heuristic) ones. So we can (and should) help it. Let’s define the heuristic that will allow us finding more efficient search directions. The heuristic represents a function object determining how far the given vertex is from the target one. Euclidean distance is used here.

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. We pass the game field and the index of the target vertex to the constructor. Coordinates of the vertex in the square field are calculated by the index (you’ll find more details about in the first part of the series). We don’t need the exact value for the given algorithm. Therefore we calculate the squared distance (the square root is left out in the formula)
Finally, let’s create a class that will be able to give a signal of the found solution. It will signal by throwing FoundGoal exception.

struct FoundGoal {};

Now let’s build a visitor class. We’ll call its examine_vertex method for each vertex our algorithm has reached. The exception will be thrown as soon as we get to the target vertex.

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;
};

Now, let’s write a pathfinding function to find the way from one graph point to another one. It accepts coordinates of initial and target vertices and also a reference 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 converts vertices coordinates to integer indices. Then we’ll create predecessor vector, which will be used to extract the result and the vector of dist distances.

I’ll dwell on several points here. First of all, I’ll tell you about calling astar_search search function. There’s nothing unusual at first. Regular parameters are defined: a graph, an initial point, and heuristics. But then comes a construction with a period instead of a coma. And it’s not a misprint. Boost provides its own method of passing named arguments for functions with a big number of unnecessary parameters. Here are some things about it:

1. The names of all parameters are defined in the boost name space. But we should indicate it once only at the beginning of a chain.
2. We pass parameters the following way: write the parameter name, then the value in brackets. We separate parameters by periods.
3. Parameter’s can be placed in any order.

If we get to catch block it means that we’ve found the path. It’s written into predecessor vector in a form of a list of preceding vertices. So the vertex index is located at predecessor[vertex] position. From the index we get to vertex. Traversing the predecessors one by one we can get a more usual path — a sequence of vertices we should pass from point A to point B. The result is being written to result list.

Here is the list of articles from the series:

1. Boost Concepts
2. Masking a Class in Boost Graph. Part 1: Let the Interface Be
3. Masking a Class in Boost Graph. Part 2: Completing the Implementation of Concept Support
4. Masking a Class in Boost Graph. Part 3: Finding the Path