Введение

На основе кода 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).

Введение

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

В качестве основы визуализатора взят код из BY-0.

Исходный код: codepad. Архив откомпилированный exe + freeglut.dll можно скачать по ссылке (для запуска exe должны быть установлены библиотеки Microsoft Visual C++ 2010 redistributable).

Принцип работы

Рассматривается сортировка массива чисел. На экране «число» представляется как прямоугольник определённой длины, а процесс сортировки выглядит как последовательность сравнений (зелёный цвет) и присваиваний (красный цвет), упорядочивающая столбец прямоугольников по убыванию (если смотреть сверху-вниз).

Итак, рассматриваем только те алгоритмы, которым достаточно сравнивать (оператор < ) и присваивать (оператор = ) объекты сортируемой последовательности. Чтобы «записать» последовательность вызова указанных операторов вместо чисел сортируются объекты специального класса — «зонда» Probe, который содержит как числовое значение, так и указатель на очередь событий, куда перегруженные operator< и operator= складывают соответствующие события. Такой подход позволяет визуализировать подходящий алгоритм (например, std::sort), не внося в него изменений.

Для каждого столбца создаётся свой массив и своя очередь событий, используется свой алгоритм сортировки. После применения всех сортировок очереди событий «раскручиваются» с определённой временной задержкой (нажмите «+», чтобы ускорить, «-«, чтобы замедлить), применяя к прямоугольникам на экране действия, ранее произведённые с «зондами».

Детали реализации

Прямоугольник (class Rect) является визуализацией числа, задаётся двумя углами (левый нижний с координатами (x0, y0) и правый верхний с координатами (x1, y1)) и цветом.

Массив прямоугольников (class RectArray), также «столбец», является визуализацией сортируемого массива. Имеет две функции-члена, отвечающих за визуализацию событий:

void assign ( unsigned index, float value );

соответствует присваиванию элементу массива с индексом index значения value,  прямоугольник с этим индексом изменит длину и будет помечен красным цветом;

void compare ( unsigned i1, unsigned i2 );

соответствует сравнению двух элементов массива с индексами i1 и i2, отвечающие за них прямоугольники будут помечены зелёным цветом.

Событие (struct IEvent) — абстрактный базовый класс, наследники которого должны определять метод void apply(RectArray&), вызов которого с передачей соответствующего массива прямоугольников и будет приводить к применению события и его последующей визуализации.

Очередь событий (class EventQueue) — основной структурный элемент, хранит как собственно очередь событий с временными метками их наступления (в секундах), так и указатель на соответствующий массив прямоугольников, а также его координаты на плоскости. Таким образом, очередь отвечает как за сохранение событий (функция push), за применение событий, произошедших к заданному моменту времени (функция next), так и за отрисовку связанного с ней массива прямоугольников (функция paint).

Зонд (class Probe) — сортируемый объект, генерирующий события с помощью перегруженных операторов. Событиям сравнения и присваивания нужны индексы элементов, поэтому зонд кроме собственно числового значения хранит и свой индекс. Кроме того, так как очередь событий требует «глобальную» временную метку, было решено перенести ответственность за вычисление времени наступления события на специальный класс TimeMapper, который получает объект IEvent, вычисляет время и уже сам отправляет событие в очередь. Поэтому зонд хранит указатель на объект TimeMapper, который является общим для всех элементов сортируемого массива.

Сцена (class Scene) — главный класс, соединяющий все куски визуализатора воедино. Хранит набор очередей событий и соответствующих массивов прямоугольников. Функция makeNew сбрасывает очереди, создаёт и сортирует новые массивы, заполняя очереди событиями. Функция paint отрисовывает все столбцы ( «всю сцену» ). Функция next передаёт время функциям next всех очередей, возвращает true, если хотя бы одно событие было извлечено из очередей (что используется как условие обновления буфера кадра в обработчике frameMove).

Таймер (class Timer) написан для удобного управления скоростью визуализации. Хранит «реальное» время, возвращаемое std::clock(), и «виртуальное» время визуализации в «секундах», с учётом скорости течения времени (поле factor).

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