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

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

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

Понадобилось незадолго алгорифм поиска пути для нашей игры переделать. Прошлый был всецело самописный — шаг в сторону, и все плохо… Захотелось взять готовый из классного источника. Здесь-то и вспомнилось, что в boost есть функциональность для работы с графами. К сожалению подход, «обнаружь функцию, вызови — и все заработает» не состоялся. Упор в библиотеке сделан на максимальную эластичность применения, что отрицательно сказалось на простоте. В то же время и ничего губительного — все отменнее, чем с нуля делать (и потом исправлять). С другими библиотеками тоже связываться мечты не было, в то время как boost в плане применяется давно…

Дано — класс игрового поля со дальнейшим (важным для данной статьи) интерфейсом

class GameField
{
public:

    GameField();

    bool canPass(int x, int y) const;
    int getWidth() const;
    int getHeight() const;
};

Поле представляет собой обыкновенную сетку из квадратных клеток. Ходить дозволено в соседние ячейки как прямо, так и по диагонали. Способ GameField::canPass разрешает проверить, дозволено ли пройти в заданную клетку (т.е. она существует и в ней не расположена преграда)

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

BOOST_CONCEPT_ASSERT((SomeFuncAppropriate<SomeClass>));

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

boost::function_requires<SomeFuncAppropriate<SomeClass> >();

Именно такой формой записи я буду пользоваться в последующем.

Выходит. Есть начальный класс, тот, что необходимо замаскировать под граф, Дабы boost его принял. При этом сам класс игрового поля (GameField) менять не хочется — тут я привожу его упрощенный вариант, на самом деле интерфейс класса и без того немаленький, менять его ради не относящейся к прямой функциональности задачи нецелесообразно. Для поиска пути будем применять алгорифм A* (AStar). В документации говорится, что функция boost::astar_search требует от графа соответствия двум доктринам: Vertex List Graph и Incidence Graph.

  • VertexListGraph полагает вероятность результативного обхода всех вершин графа. Для этого необходимо будет предоставить средства определения числа вершин и их перебора.
  • IncidenceGraph должен иметь интерфейс для перебора всех исходящих из вершины ребер. Также для графов этого типа должна существовать вероятность приобретения исходной и финальной вершины для заданного ребра.

Помимо того, доктрины графов требуют определения ряда особых типов, опираясь на которые boost сумеет манипулировать нашим классом. Остановимся на них подробнее.

vertex_descriptor определяет тип вершины. В классе GameField вершина определяется двумя координатами ячейки. Первая мысль — повторить это определение с поддержкой конструкции либо пары значений (std::pair). Впрочем vertex_descriptor в зависимости от типа графа должна удовлетворять различным доктринам, т.е придется реализовывать операторы, конструкторы и т.д. Не сказать, что дюже трудно, но проще задуматься и осознать, что две координаты вершины — это легко специфика реализации нашего игрового поля. Само по себе представление графа от этого (в нашем случае) не выигрывает. Так что было решено, что в модели графа вершины будут легко пронумерованы ((0, 0) -> 0, (0, 1) -> 1 и так дальше). Это дозволит применять в качестве типа вершин типовой int, тот, что теснее поддерживает всю нужную функциональность. Безусловно, придется реализовать две функции — для перевода индекса вершины в координаты графа

std::pair<int, int> getCoordinates(const Vertex position, const GameField& graph)
{
    return std::make_pair(position % graph.getWidth(), position / graph.getWidth());
}

и обратно

Vertex getVertex(int x, int y, const GameField& graph)
{
    return x   y * graph.getWidth();
}

Откуда взялся тип Vertex будет объяснено ниже.

edge_descriptor — тип ребра. Ребро — это две вершины, так и запишем: std::pair <vertex_descriptor, vertex_descriptor>

directed_category — должен соответствовать одному из особых типов-тегов (по сути это конструкции без данных и способов), котрые определят, является ли граф направленным. В нашем случае не является, следственно применять будем значение boost::undirected_tag

edge_parallel_category Еще один тип-тег, определяющий, возможны ли в нашем графе параллельные ребра (когда между двумя вершинами может существовать огромнее одного ребра). Не возможны — используем значение boost::disallow_parallel_edge_tag

traversal_category Тоже тег. Определяет методы обхода графа. Тут все немножко труднее. Для VertexListGraph это должен быть boost::vertex_list_graph_tag, а для IncidenceGraph соответственно boost::incidence_graph_tag. Решается это созданием нового типа-тега, тот, что наследовал бы оба варианта обхода

struct game_field_traversal_catetory:
    public boost::vertex_list_graph_tag,
    public boost::incidence_graph_tag
{
};

vertex_iterator Итератор для обхода вершин. Его реализацию разглядим в дальнейшей части статьи.

out_edge_iterator Итератор для обхода исходящих из вершины ребер, также будет реализован в последующем.

degree_size_type Тип, в котором выражается степень вершины (число исходящих ребер). Целое число.

vertices_size_type Тип, в котором выражено число вершин графа. Также примем за целое число.

Подробнее остановлюсь на типах-тегах (верно это именуется диспетчеризация тегов). Они применяются для перегрузки функций, Дабы воспользоваться той либо другой спецификой модели. Скажем, определив тег boost::undirected_tag, мы уведомляем библиотеке, что ребра графа не являются направленными. В итоге она будет применять функции, не требующие отдельного задания исходящих и входящих ребер.

Сейчас необходимо сопоставить типы игровому полю. 1-й вариант привязки — размещение дополнительных определений непринужденно в классе.

class GameField
{
public:
        typedef int vertex_descriptor;
...

Впрочем интерфейс GameField хочется оставить без изменений. К счастью, boost предоставляет такую вероятность. Все нужные типы извлекаются библиотекой не из класса графа напрямую, то есть не так

GameField::vertex_descriptor

Взамен этого применяется особый образец boost::graph_traits

boost::graph_traits<GameField>::vertex_iterator

По умолчанию он легко получает соответствующий тип из класса-параметра, т.е. делает следующее

  template <typename Graph>
  struct graph_traits {
    typedef typename Graph::vertex_descriptor vertex_descriptor;
...

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

namespace boost
{
   template <> struct graph_traits<GameField>
    {
        typedef int vertex_descriptor;
        typedef std::pair <vertex_descriptor, vertex_descriptor> edge_descriptor;
        typedef boost::undirected_tag directed_category;
        typedef boost::disallow_parallel_edge_tag edge_parallel_category;
        typedef game_field_traversal_catetory traversal_category;

        typedef VertexIteratorImpl vertex_iterator;
        typedef OutEdgeIteratorImpl out_edge_iterator;
        typedefint degree_size_type;
        typedef int vertices_size_type;

        typedef void in_edge_iterator;
        typedef void edge_iterator;
        typedef void edges_size_type;
    };
}

Обратите внимание, что конструкция содержит несколько типов, которые ранее не упоминались: in_edge_iterator, edge_iterator, edges_size_type. Они не необходимы для реализации доктрин VertexListGraph и IncidenceGraph, соответственно их дозволено не уточнять (сделать void).

В последующей работе желанно ссылаться на типы в graph_traits (т.е. применять vertex_descriptor взамен int, если речь идет о вершине), Дабы оставить себе вероятность менять при необходимости определения в одном месте. От того что конструкция вида boost::graph_traits&ltGameField&gt::vertex_descriptor тяжеловата как для написания, так и для прочтения, введем примитивные имена типов, которыми будем пользоваться в последующем

typedef boost::graph_traits<GameField>::vertex_descriptor Vertex;
typedef boost::graph_traits<GameField>::edge_descriptor Edge;
typedef boost::graph_traits<GameField>::vertex_iterator VertexIterator;
typedef boost::graph_traits<GameField>::out_edge_iterator OutEdgeIterator;
typedef boost::graph_traits<GameField>::degree_size_type DegreeSizeType;

Всё, нужные типы определены. В graph_traits&ltGameField&gt были использованы VertexIteratorImpl иOutEdgeIteratorImpl — реализацию этих итераторов разглядим в дальнейшей части статьи. Также будут реализованы нужные для поддерживаемых доктрин функции работы с графами.

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

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