Потребовалось недавно алгоритм поиска пути для нашей игры переделать. Прошлый был полностью самописный — шаг в сторону, и все плохо… Захотелось взять готовый из хорошего источника. Тут-то и вспомнилось, что в 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, мы сообщаем библиотеке, что ребра графа не являются направленными. В результате она будет использовать функции, не требующие отдельного задания исходящих и входящих ребер.
Теперь нужно сопоставить типы игровому полю. Первый вариант привязки — размещение дополнительных определений непосредственно в классе.
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;
typedef int 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<GameField>::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<GameField> были использованы VertexIteratorImpl и OutEdgeIteratorImpl — реализацию этих итераторов рассмотрим в следующей части статьи. Также будут реализованы необходимые для поддерживаемых концепций функции работы с графами.
Автор: vadim_ig
