ai Tutorials Искусственный интеллект

С помощью библиотеки GSL (Graph Search Library, библиотека поиска на графе), написанной на ANSI C++, можно быстро запустить игровой AI engine. Идея GSL состоит в том, что, написав одну основную функцию - процедуру раскрытия вершины, разработчик сразу же получает доступ к широкому множеству поисковых алгоритмов. Чтобы запустить какой-то алгоритм достаточно произвести вызов соответствующей обобщенной (generic) процедуры GSL, инстанциируя ее входной параметр - траверсер - процедурой раскрытия вершины. Для демонстрации методов программирования с применением GSL рассмотрена одна из основных задач, возникающих в игровых системах принятия решения - поиск минимального по стоимости пути на треугольной сетке на основе хорошо известного алгоритма A*. Предполагается, что читатель знаком с самим алгоритмом A*, идеей обобщенного программирования (generic programming) на С++ и такой замечательной библиотекой как STL.

Вначале коротко о компонентах библиотеки.

Основной компонентой GSL является траверсер (от to traverse a search tree - обходить дерево поиска ) - это объект, который “знает”, как двигаться вперед (move_forward()) и откатываться назад (backtrack()) по дереву поиска.

Обобщенные алгоритмы поиска на графе принимают траверсер в качестве входного параметра и управляют им на основе двух данных функций. Помимо них еще используются следующие методы для контроля состояния траверсера:

GSL является библиотекой, построенной на шаблонах С++ (C++ templates). Алгоритмы библиотеки являются параметризованными, то есть на вход они принимают траверсеры, удовлетворяющие некоторому набору операций, который может быть произведен над траверсером.

Чтобы вся эта наука:-) не отставала от практических результатов, предлагается рассмотреть алгоритм из библиотеки GSL, который называется ForwardSearch. Смысл этого алгоритма сводится к поиску первого решения (то есть некоторого пути на дереве от корня к конечной листовой вершине) без каких-либо ограничений на его стоимость. Вот как выглядит алгоритм (его программировать не нужно - он уже содержится в библиотеке).

template <class Tr, class Goal>
void ForwardSearch(Tr &tr, Goal goal)
{
while( !tr.empty() && !goal(tr.cursor() ) tr.move_forward();
}

Согласно основной идее обобщенного программирования (generic programming) - имеется некоторый объект - траверсер Tr, над которым можно выполнить перечень операций, указанных в алгоритме. Еще присутствует предикат Goal, у которого должна быть переопределена операция () для проверки, является ли вершина целевой. Итак, смысл алгоритма сводится к тому, что траверсер все время движется вперед по дереву поиска, пока либо не останется больше вершин для раскрытия либо в качестве курсора (то есть вершины, которая будет раскрыта на следующем шаге) не будет взята целевая вершина.

Получается, что в траверсере уже имеется (запрограммирована) некая функциональность, связанная с управлением множеством потомков вершины и перемещением курсора. Надо только “научить” траверсер раскрывать вершины.

Траверсер как шаблон C++ параметризован тремя компонентами - этот тип вершины, тип стоимости и тип функции раскрытия или на языке С++.

template <class value_type, class cost_type, class exp_type> class Tr.

Траверсеры бывают двух типов - линейные (LinTr) и экспоненциальные (ExpTr).

Линейные траверсеры держат в памяти только вершины вдоль основной ветви дерева поиска вместе со множеством потомков. Они так называются, потому что число вершин в дереве поиска оценивается как O(bd), где b - средний коэффициент ветвления вершины, d - глубина дерева.

Экспоненциальные траверсеры поддерживают в памяти сразу много альтернатив, лежащих в разных ветвях дерева поиска. Если говорить упрощенно, то экспоненциальные траверсеры свою функциональность строят на основе алгоритма A*.

Пример - Модель поиска на сетке

Пусть имеется сетка с перенумерованными вершинами и множеством стоимостей дуг между ними и пусть вся эта “карта” записана с помощью структуры map из STL.

map<int, map<int, int> > C;

Где-то в программе происходит ее инициализация

С[1][2] = 10; С[1][5] = 12;

и т.д.

Надо найти путь минимальной стоимости между вершинами, например, 1 и 100, с помощью алгоритма A*.

Как написать параметры для траверсера

Первые два параметра - это int и int - описание вершины и ее стоимость. Функция exp_type выглядит так

class expand
{
public:
operator()(list<int>& e, list<int> ce, int n, int, int c) {
for(map<int, int>::iterator i = C[n].begin(); i != C[n].end(); ++i) {
e.push_back((*i).first);
ce.push_back(c + (*i).second);
}
}

С помощью итератора i добавляются все потомки вершины n вместе со стоимостями в две коллекции - потомков e и cтоимостей ce. Важно, что коллекции передаются через ссылку!

Итак, траверсер будет такой

typedef ExpTr<int, int, expand> ExpTr_t;

Предикат проверки на целевое условие выглядит так

bool goal(int n) { return n==100; }

Основная работа связана с написанием процедуры раскрытия вершины - теперь можно запустить алгоритм

ExpTr_t  tr;
ForwardSearch(tr = ExpTr_t(1), goal);

После завершения работы алгоритма траверсер представляет собой дерево поиска в момент нахождения решения. Для доступа к полученному решению используется так называемый обратный итератор, который движется от листовой вершины к целевой.

list<int> result;
for(RevIter ri = tr.RPathBegin(); ri != tr.RPathEnd(); ++ri) {
result.push_front(*ri);
}

Так выглядит в GSL алгоритм A. Полученный траверсер можно без изменения использовать со всеми другими алгоритмами GSL, главное, чтобы траверсер поддерживал тот набор операций, который использует алгоритм поиска. Если этот набор не совпадает с требуемым, то выдается ошибка на этапе компиляции.

Заключение

GSL (документацию и код) можно получить на сайте http://gslconcept.virtualave.net. В данном обзоре в интересах простоты изложения опущены некоторые несущественные подробности - пожалуйста, смотрите код и руководство пользователя. Все вопросы по GSL, равно как замечания и предложения, направляйте пожалуйста по адресу info@gslconcept.virtualave.net. Хочу выразить большую благодарность автору этого сайта Сергею Анисимову за предоставленную возможность немного рассказать про GSL.

PMG   27 Ноября 2001   (c)   Беркульцев Максим