Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Маскируем класс под граф Boost. Часть 3: Находим путь

Anna | 24.06.2014 | нет комментариев

Пролог: Доктрины Boost
Часть 1: Подключение ассоциированных типов без вмешательства в интерфейс начального класса
Часть 2: Завершаем реализацию поддержки доктрин 

В прошлых статьях цикла описывался процесс адаптации класса клеточного игрового поля под доктрины графов boost. Теперь разглядим собственно то, ради чего все затевалось — поиск пути на клеточном поле. Реализация поиска boost разрешает довольно тонко настраивать алгорифм, в этой статье будет приведет только один пример такой параметризации — вероятность задавать разную длину ребер графа.

С изложения параметра и начнем. Требуется сделать карту весов ребер, которая удовлетворяет доктриныReadablePropertyMapConcept. Реализуется она довольно легко — необходимо определить несколько типов и оператор [], тот, что на основе ключа-ребра, возвращает его длину. Для простоты расчеты будут опущены — примем размер всех ребер равным единице.

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

С поддержкой typedef определяются тип ключа (Edge), тип возвращаемого значения (double) и метка, по которой boost сумеет осознать, что из карты дозволено получать значения (boost::readable_property_map_tag). Edge и другие пользовательские типы определены в первой части статьи.

Дальше необходимо реализовать требуемую доктриной функцию. Но вначале введем короткие псевдонимы типов (для себя)

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;

Функция должна возвращать значение из карты по ключу

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

Сейчас дозволено задать карту весов ребер. Обратите внимание — объявление делается в пространстве имен boost.

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

Проверяем доктрину

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

Дозволено еще задать свойства вершин — этого мы делать не будем, впрочем придется сделать заглушку, Дабы boost мог сгенерировать карту для вершин по умолчанию. Для этого довольно указать тип свойств вершин, пускай это будет тип индекса вершины

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

Это определение также должно располагаться в пространстве имен boost.

Реализуем поддержку нашим графом еще одной доктрины — ReadablePropertyGraphConcept, т.е. «граф со свойствами». Для этого понадобится задать две функции. Первая создает карту свойств графа

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

Обратите внимание, в данной статье веса ребер не рассчитываютcя (равны 1), следственно и указатель на граф в ней сберегать незачем, соответственно и параметр graph не применяется. Также зададим функцию определения веса ребра

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

На этом с следующий доктриной завершено, дозволено исполнить проверку

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

Алгорифм поиска пути A* относится к классу информированных, а, значит, ему дозволено (и необходимо) подмогнуть. Для этого определим эвристику, которая дозволит обнаружить больше результативные направления поиска. Эвристика представляет собой функтор, определяющий насколько заданная вершина далека от целевой. Применяется эвклидова метрика

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

Класс довольно примитивен — в конструктор ему передается игровое поле и индекс целевой вершины. По индексу вычисляются координаты вершины на клеточном поле (подробнее об этом рассказано в первой части статьи). Для алгорифма значимо увеличение либо уменьшение расстояние — точное значение не требуется, следственно вычисляется квадрат расстояния (квадратный корень в формуле опущен).

Ну и, наконец, сделаем класс, тот, что сумеет просигнализировать о обнаруженном решении. Сигнализировать будем посредством возбуждения исключения FoundGoal.

struct FoundGoal {};

Сделаем класс-посетитель, способ которого examine_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;
};

Наконец, пишем функцию поиска пути из одной точки графа в иную. В качестве параметров она принимает координаты начальной и целевой вершин, а также ссылку на граф

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

Функция переводит координаты вершин в целочисленные индексы. После этого создается векторpredecessor, из которого будет извлекаться итог и вектор расстояний dist.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB