PathPlanningProject

Программный проект для нахождения кратчайших путей при помощи алгоритмов Дейкстры или A*. Текущий этап разработки: написание онлайн-демонстратора.

Входные данные:

На вход подаётся XML-файл, содержащий опции алгоритма поиска, карту с препятствиями, координаты стартовой точки и цели, уровни логирования.

Теги входного файла XML:

• root

• map

  • title - заглавие
  • width - ширина карты
  • height - высота карты
  • cellsize - масштаб карты
  • startx, starty - координаты начала. Координаты начинаются в верхнем левом углу.
  • finishx, finishy - координаты конца
  • grid - сама карта

• algorithm - опции алгоритма

  • metrictype - тип метрики
  • searchtype - алгоритм поиска (Дейкстра или Астар)
  • hweight - вес эвристической функции
  • breakingties - g_max или g_min, при равенстве F-значений вершин сравниваются их g-значения
  • allowdiagonal - разрешено ли движение по диагонали
  • allowsqueeze - разрешено ли просачивание, то есть проход между двумя непроходимыми вершинами
  • cutcorners - разрешено ли срезать углы

• options - описание логирования

  • loglevel - уровень логирования
  • logpath - путь для сохранения выходного XML-файла
  • logfilename - название выходного XML-файла

Выходные данные:

На выходе мы получаем XML-файл, содержащий всю ту же информацию, что и входной XML-файл плюс следующая информация:

• log
  • mapfilename - путь к исходному XML-файлу
  • Информация о работе алгоритма:
    • summary time - суммарное время работы алгоритма
    • length - длина пути
    • nodescreated - количество созданных вершин
    • numberofsteps - количество шагов в алгоритме
  • path - путь от начало до конца или "Path NOT found!" в случае отсутствия пути
  • lplevel - вершины, образующие путь
  • hplevel

Начало работы

Клонируйте содержимое этого репозитория в нужную директорию при помощи Git bash'a. (В нужной директории Rightclick + Git Bash here)

git clone https://github.com/*account*/PathPlanningProject.git

Сборка и запуск

Сборку проекта возможно осуществить двумя способами:

• Используя QtCreator и qmake;
• Используя CMake.

При использовании CMake сборка и запуск может производиться как из командной строки, так и при помощи различных IDE (например JetBrains CLion). Ниже приведены скрипты сборки и запуска с использованием командной строки.

Linux и Mac

Release сборка:

cd PathPlanning2D
cd Build
cd Release
cmake ../../ -DCMAKE_BUILD_TYPE="Release"
make
make install

Debug сборка:

cd PathPlanning2D
cd Build
cd Debug
cmake ../../ -DCMAKE_BUILD_TYPE="Debug"
make
make install

Запуск:

cd ../../Bin/{Debug|Release}/
./Khaybulin_Daniel_ASearch ../../Examples/example.xml

Результат запуска:

Windows

Release сборка:

cd PathPlanning2D
cd Build
cd Release
set PATH
cmake ../../ -DCMAKE_BUILD_TYPE="Release" -G "MinGW Makefiles"
mingw32-make
mingw32-make install

Debug сборка:

cd PathPlanning2D
cd Build
cd Debug
set PATH
cmake ../../ -DCMAKE_BUILD_TYPE="Debug" -G "MinGW Makefiles"
mingw32-make
mingw32-make install

Запуск:

cd ../../Bin/{Debug|Release}/
Khaybulin_Daniel_ASearch.exe ../../Examples/example.xml

Результат запуска:

Тестирование

 ctest

либо (для более подробного вывода):

 ctest --output-on-failure

Контакы

Хайбулин Даниэль

• https://t.me/kiDaniel