Алгоритм нахождения кратчайшего пути

Описание

Алгоритм нахождения кратчайшего пути используется в широком спектре компьютерных игр. Конкретная демонстрация реализована на языке C++ в ОС linux. Сам алгоритм запрограммирован в теле функции findPath в файле Path.cpp.

По своей сути процесс состоит из двух частей: расчета расстояний (где рекурсивный алгоритм заменен на матричный) от точки назначения и движения в сторону кратчайшего расстояния.

Это, скажем так, первое приближение. Я не пытался воссоздать максимально изящный вариант этого алгоритма, но и стремления запутать читателя тоже не было.

Графическая часть демонстрации реализована с использованием libkxl0.

Исходники

Скачать