Введение

1. Краткое описание

В данном проекте был реализован алгоритм поиска пути в двумерном пространстве. Программа была написана на языке программирования C++ в среде разработки Microsoft Visual Studio 2008 с помощью технологии Windows Forms и с использованием стандартной библиотеки шаблонов STL.

2. Некоторые алгоритмы поиска пути

2.1. Волновой алгоритм, A*, алгоритм  Дейкстры

Путь ищется во всех направлениях от начальной (красной точки) до конечной. Поиск ведется только по 4(максимум 8) направлениям. Данный алгоритм неэффективен, если препятствий не очень много и на его выполнение тратится довольно много времени. Если пути не существует, то алгоритм просматривает всю карту. Также необходимо хранить много информации.

2.2. Навигационная сетка

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

2.3 Алгоритм в проекте

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