AV-2: AstarVis

Введение

На основе кода BY-1 и в качестве продолжения идей AV-1 был разработан визуализатор алгоритма A*. Архив содержит проект Visual C++ 2010 со всем исходным кодом и библиотекой FreeGLUT, готовый к использованию «как есть». В архив также включены откомпилированный exe и html-документация, сгенерированная системой Doxygen/Graphviz по комментариям в исходном коде.

Управление

  • ESC выход;
  • SPACE/ENTER новый ландшафт;
  • стрелки/WASDXZ управление камерой;
  • 0123456789 выбор множителя эвристики (соответственно от 0 до 9) с перерасчётом А*-пути, если нужно;
  • G показывать рёбра графа;
  • P показывать пути, полученные алгоритмами Дейкстры и А*.

Цвета

Про структуру графа, отражающего ландшафт, рассказано в следующем разделе «Ландшафт».

Предварительная заливка ландшафта вычисляется функцией Scene::prepareColors и состоит из синей и красной компонент. Красная компонента возрастает по мере приближения к целевой вершине, оставаясь при этом всегда меньше единицы. Синяя компонента возрастает по мере приближения к начальной вершине (эти вершины находятся в противоположных углах).

Вершины (треугольники), попадающие в открытое множество, помечаются единичной красной компонентой (что делает их светлее соседних) и зелёной компонентой тем большей, чем меньше соответствующая оценка пути gscore для этой вершины.

Вершины (треугольники), попадающие в закрытое множество, помечаются нулевой красной компонентой, приобретая оттенки синего, голубого, зелёного (зависит от оценки gscore, тем синее и темнее, чем больше gscore).

Рёбра графа изображаются отрезками жёлто-оранжевого цвета. Путь, построенный алгоритмом Дейкстры, изображается линией жёлто-зелёного цвета, А*-путь — линией светло-синего цвета.

Ландшафт

Ландшафт генерируется как карта высот сложением псевдослучайных чисел, «холмов» и «кратеров» (вычисляемых как сдвинутая и повёрнутая обратная квадратичная форма координат узла, точнее см. код классов Hill и Ring в HeightMap.h).

Карта высот представляет собой набор отсчётов (двумерный массив чисел), заданных в узлах прямоугольной сетки (лежащей в плоскости 0xy), используемыми как высоты (координаты по оси 0z) некоторого ландшафта в этих узлах. Карту высот представляет класс HeightMap.

Карта высот может быть изображена как набор полосок треугольников. Каждая четвёрка соседних узлов (ограничивающих ячейку сетки в плоскости 0xy) задаёт два треугольника. При этом дублируются вершины всех рядов кроме двух крайних. Нормали к этим треугольникам можно вычислить, например, используя векторное произведение разностей пар их вершин. Полоски треугольников строит и отображает класс Terrain.

Чтобы рассчитывать пути на ландшафте, нужно отождествить элементы графа с некоторыми элементами ландшафта. В простейшем случае можно считать вершинами графа вершины треугольников, а рёбрами графа — рёбра треугольников, проецирующиеся на 0xy в отрезки, параллельные осям 0x и 0y.

В данном случае было решено немного усложнить построение графа, так как удобно отождествить вершины графа с самими треугольниками, а рёбрами соединять те треугольники, что имеют общее ребро или общую вершину при «прямом» угле (этот угол является прямым в проекции на плоскость 0xy). Удобство состоит в том, что в этом варианте состояние вершин можно показывать цветом треугольника. Вершина графа размещается в «центре» треугольника (точке пересечения медиан). Расчётом координат вершин, стоимости переходов между вершинами и составлением списков смежности занимается класс TerrainGraph.

Связывание визуализации с алгоритмом А*

Класс TerrainGraph может быть использован непосредственно как вектор списков смежности благодаря перегруженному оператору [ ]. Веса рёбер и оценка расстояний (эвристика) рассчитываются с помощью функции-члена estimatePrice. Функторы-адапторы WeightsForGraph и HeuristicForGraph представляют граф соответственно в виде матрицы весов рёбер и эвристики для алгоритма А*.

Визуализатор использует три типа событий:

  1. OpenedEvent для события размещения вершины в очереди с приоритетом (открытое множество).
  2. ClosedEvent для события извлечения вершины из очереди.
  3. PathEvent для пометки очередной вершины в пути, построенном алгоритмом А*.

События последнего типа генерируются в последнем цикле в функции Scene::makeApath. События первых двух типов генерируются и помещаются в очередь объектом класса AstarDemo, передаваемом функции astar в качестве последнего параметра (класс AstarDemo выступает в роли модели параметра шаблона DemoPolicy).

UPDATE. 2013.01.25. Более новый вариант расположен здесь (в составе AV Orchid).

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: