Алгоритмы поиска пути — неотъемлемая часть разработки игр. А также различных систем навигации, ориентации и много чего ещё. Но мы сосредоточимся на именно игровой индустрии и алгоритмах, которые в ней применяются.
Каждый игровой разработчик сталкивается с задачей, в которой требуется заставить персонажа(или бота) пройти из одной точки в другую, при этом не собрав все стены. А разработчикам стратегий ещё нужно учитывать проходимость клеток(дороги, болота, леса и так далее). Вот здесь на помощь приходят алгоритмы поиска пути.
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/0b5/78a/208/0b578a20808152ba8b2065fe6903c560.png)
Из вышесказанного можно сделать вывод, что любому игровому разработчику рано или поздно приходится сталкиваться и разбираться с поиском пути, а позже и модифицировать и оптимизировать его для собственных проектов. А так как очень много новичков сразу идут в GameDev для них не всегда просто прочитать несколько статей и понять тот или иной алгоритм. В этом посте описаны попытки создать программное обеспечение, которое поможет облегчить процесс понимания принципов работы алгоритмов поиска пути.
Мы будем рассматривать 3 основных алгоритма. Теперь в двух словах о каждом из основных алгоритмов и скриншоты визуализации их работы в программе (немного опережая события).
Разработан нидерландским учёным Эдсгером Дейкстрой в 1959 году. Алгоритм проверит каждую из вершин графа пока не найдет кратчайший путь до исходной вершины. Подробнее можно прочитать, например, тут.
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/099/0b5/fbe/0990b5fbe1cbe56d472197f4c601e49a.png)
Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. При рассмотрении каждой отдельной вершины переход делается в ту соседнюю вершину, предположительный путь из которой до искомой вершины самый короткий.
Начать изучение можно здесь.
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/dab/9a1/36f/dab9a136fa8c54c8f36a8cf35b393936.png)
Данный алгоритм был представлен в 2011 году Д. Харбором и А. Грастиеном. JPS ускоряет поиск пути, «перепрыгивая» многие места, которые должны быть просмотрены. «Прыжковые точки» позволяют ускорить алгоритм поиска пути, рассматривая только «необходимые» узлы. Очень хорошо объясняется принцип работы здесь
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/ff9/f1a/d91/ff9f1ad91302d14d2125760bfa120bf1.png)
Стоить отметить, что Growing Tree генератор, также представленный в программе, создает «классический лабиринт» как на картинке ниже(только больше), высота и ширина в настройках далее задается именно для него. Этот генератор был добавлен для создания «Вау-эффекта» у новичка и для демонстрации пути, построенного самыми базовыми алгоритмами(Правило правой или левой руки, DFS), в посте я не буду здесь останавливаться и сосредоточусь на ручном режиме.
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/e7d/c68/286/e7dc682861ac9dc2f74fea2f366b69e2.png)
Поиск работает на графе, самый простой создать из карты граф — эторасставить вэйпоинты самому перевести карту в клетчатое поле. Так как цель — облегчить понимание основ, мы и собираемся работать с квадратными клетками.
Для начала нам стоит определить класс клетки. У пользователя должна быть возможность установить вход, выход и нанести на поле непроходимые препятствия, также для изучения полезно узнавать характеристики клетки, её родителя и статус прямо во время работы алгоритма. В итоге получаем представленный класс (set-, get-функции я убрал для экономии места):
Функции pressButton и updateStatus обрабатывают изменение статуса и цвета клетки. А showInfo и deleteInfo за инфобокс, о котором далее. Переменные x и y отвечают за координаты; f, g, h, weight за характеристики необходимые для работы алгоритмов поиска, status и listStatus за
статус клетки, isEnter и isExit за то, существует ли на карте вход и выход, par за родительскую клетку(необходимо для восстановления построенного пути).
Клетчатое поле мы создали, теперь хорошо бы предоставить пользователю возможность наносить вход и выход, расставлять стены и вызывать вышеупомянутый инфобокс.
К счастью, класс QGraphicsView из фреймворка Qt, на котором мы и создаем интерфейс, предоставляет нам виртуальные функции щелчка, двойного клика и движения курсора (mousePressEvent, doubleClickEvent, mouseMoveEvent соответственно). Их мы и перегружаем в классе сцены, которая содержит наши клетки.
Функция checkPos проверяет, чтобы курсор находился над объектом клетки.
Реализация функции щелчка. Определяем по какой клетке мы нажали и просим её обновить свой статус. Инфобокс пришлось поставить на ПКМ, так как в Qt при использовании двойного клика сначала вызывается функция обычного клика и это приводило к мерцанию клетки(мы обновляли состояние клетки при одинарном клике и возвращали его назад, когда понимали, что клик двойной).
Вход ставится на 'Ctrl + ЛКМ', а выход на колесико мыши или для тачпада 'Alt + ЛКМ'. Достаточно удобно. Стена устанавливается обычным ЛКМ.
Также хотелось позволить пользователю рисовать стены, как это сделано в привычных графических редакторах, зажав ЛКМ, водить по полю.
Для этого перегружаем функцию mouseMoveEvent(). Проверяем, чтобы мы были над клетками, и просим обновить состояние клетки под курсором. Если начать рисовать с пустой клетки, то и продолжим рисовать стены, если стерли стену, то и далее будем в режиме «ластика». Функция ещё отвечает за удаление инфобокса, если мы убираем курсор с клетки, на которой он был вызван.
Инфобокс создадим как обычный прямоугольник, на котором показаны характеристики веса, F, G, H (если вы знакомы с представленными выше алгоритмами, то знаете эти обозначения), текущий статус клетки и её родитель.
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/37b/13d/492/37b13d492f58f1c9967de627f31b6b76.png)
Всё, мы обеспечили работу поля для визуализации, половина сложной работы сделана, ура!
Самая интересная часть программы, то, что должно превращать скучную (или не очень) статью в нечто такое:
![image](https://habrastorage.org/getpro/habr/post_images/cc9/9fa/3aa/cc99fa3aa55351b3a7cc395ecb2fa4e6.gif)
Есть и пошаговый режим, который, в связке с инфобоксами, поможет на 100% понять работу каждого алгоритма.
Теперь пару слов о том, как это реализовывалось. Для примера рассмотрим функцию алгоритма AStar, остальные алгоритмы реализованы аналогично. Также мы оставим передачу сигнала от кнопки к самой функции.
Пошаговый режим и полное решение мы реализовывали одной функцией, поэтому приходится передавать ID режима(0 — полное решение и 1 — для очередного шага). Далее, если это полное решение или первый шаг в пошаговом, очищаем поле от остатков предыдущего решения, чистим статусы клеток и обновляем характеристики c помощью функции clearLabyr. Функции самих алгоритмов реализованы так, что возвращают истину, если достигнута конечная точка поиска или поиск продолжать невозможно, и false, если можно работать дальше. Следовательно, для полного решения оператором while вызываем функцию, пока она не вернет true и наносим на сцену линию пути вызвав функцию updatePictureSolve. Для пошагового режима вызываем функцию при каждом щелчке, если путь найден, также отправляем его на отрисовку и выводим сообщение, чтобы пользователь случайно не прокликал момент решения.
Сами алгоритмы поиска обновляют статус клеток, когда заносят их в открытый или закрытый список.
В программе представлены:
Необходимо было позволить пользователю удобно переключаться между назваными опциями. Результатомвеликого дизайна работы стала небольшая панелька меню в рабочей области, которую можно скрыть и вызвать через тулбар. Есть возможность менять цвета линии пути, кликнув по цветному полю.(если вам не нравится мой вкус)
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/1b8/772/87f/1b877287f7fb5a3ca2733aa7676c5af2.png)
Программой также можно воспользоваться, чтобы выбрать наиболее эффективный алгоритм для данной ситуации:
Очевидно, что для более менее серьёзных проектов «на глаз» недостаточно, поэтому необходимо отображать статистику.
Мы будем делать это в виде виджета с краткой статистикой текущего алгоритма в рабочей области и отдельного окна, отображающего работу всех алгоритмов за сеанс и позволяющего создать отчет, который можно будет скопировать, например, в Excel, построить там графики.
Реализация виджета с краткой статистикой очень походит на реализацию виджета с настройками, да и выглядит он почти также:
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/17e/e8c/83a/17ee8c83a5348a849b0486e0c3aba809.png)
Алгоритм сам подсчитывает количество операций. Длину пути можно узнать из характеристик клетки выхода, а время мы считаем таймерами, вычитая время потраченное на рисовку(хотя это не очень то и точно). Когда алгоритм заканчивает работу он передает статистику на виджет и вызвает функцию создания записи в таблице. В итоге имеет такую таблицу:
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/7c8/19a/0e6/7c819a0e67fc0072b63c26c3c75f15b1.png)
Стоит отдельно сказать почему у A* и Декстры результаты одинаковые, а у JPS отличный. Это связано с тем, что используются 2 разные методики подсчета растояния между клетками: A* и Дейкстра используют стоимость вертикального и горизонтального перехода 10 и диагонального 14, а потом делят общий результат на 10; JPS использует 1 и sqrt(2) соответственно и ничего не делит, но тоже округляет. JPS показывает длину пути несколько точнее, именно поэтому числа различны.
Мы получили программу, которая помогает начинающим, и не только, программистам разобраться с алгоритмами поиска пути. По крайней мере я всё-таки помог паре своей друзей)
Автор будет рад выслушать ваши пожелания и исполнить их, как только напишет экзамены.
Возможно, череда улучшений приведет к тому, что мы получим мощную библиотеку с алгоритмами, а программа станет приятной демкой для неё (Как PathFinding.js, только лучше).
Если вы, возможно, хотели бы написать статью о поиске пути, можете приложить к ней и эту программу.
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/98b/9f6/a19/98b9f6a19b7a889a7cb109213f1630e5.png)
→ Опытный материал для исследования: PathFinding.js
→ Скачать архив с программой можно с ЯД или с DropBox.
UPD: изначально по ошибке была опубликована не до конца отлаженная версия, теперь все ок. Приношу свои извинения. 14.03.2017 (да-да около 4х суток висела забагованная версия :C)
→ Исходный проект VS2013: ЯД и Dropbox
Каждый игровой разработчик сталкивается с задачей, в которой требуется заставить персонажа(или бота) пройти из одной точки в другую, при этом не собрав все стены. А разработчикам стратегий ещё нужно учитывать проходимость клеток(дороги, болота, леса и так далее). Вот здесь на помощь приходят алгоритмы поиска пути.
![image](https://habrastorage.org/getpro/habr/post_images/0b5/78a/208/0b578a20808152ba8b2065fe6903c560.png)
Зачем?
Из вышесказанного можно сделать вывод, что любому игровому разработчику рано или поздно приходится сталкиваться и разбираться с поиском пути, а позже и модифицировать и оптимизировать его для собственных проектов. А так как очень много новичков сразу идут в GameDev для них не всегда просто прочитать несколько статей и понять тот или иной алгоритм. В этом посте описаны попытки создать программное обеспечение, которое поможет облегчить процесс понимания принципов работы алгоритмов поиска пути.
Несколько слов об основных алгоритмах
Мы будем рассматривать 3 основных алгоритма. Теперь в двух словах о каждом из основных алгоритмов и скриншоты визуализации их работы в программе (немного опережая события).
Алгоритм Дейкстры
Разработан нидерландским учёным Эдсгером Дейкстрой в 1959 году. Алгоритм проверит каждую из вершин графа пока не найдет кратчайший путь до исходной вершины. Подробнее можно прочитать, например, тут.
![image](https://habrastorage.org/getpro/habr/post_images/099/0b5/fbe/0990b5fbe1cbe56d472197f4c601e49a.png)
A*(A Star)
Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. При рассмотрении каждой отдельной вершины переход делается в ту соседнюю вершину, предположительный путь из которой до искомой вершины самый короткий.
Начать изучение можно здесь.
![image](https://habrastorage.org/getpro/habr/post_images/dab/9a1/36f/dab9a136fa8c54c8f36a8cf35b393936.png)
Jump Point Search
Данный алгоритм был представлен в 2011 году Д. Харбором и А. Грастиеном. JPS ускоряет поиск пути, «перепрыгивая» многие места, которые должны быть просмотрены. «Прыжковые точки» позволяют ускорить алгоритм поиска пути, рассматривая только «необходимые» узлы. Очень хорошо объясняется принцип работы здесь
![image](https://habrastorage.org/getpro/habr/post_images/ff9/f1a/d91/ff9f1ad91302d14d2125760bfa120bf1.png)
Небольшая оговорка
Стоить отметить, что Growing Tree генератор, также представленный в программе, создает «классический лабиринт» как на картинке ниже(только больше), высота и ширина в настройках далее задается именно для него. Этот генератор был добавлен для создания «Вау-эффекта» у новичка и для демонстрации пути, построенного самыми базовыми алгоритмами(Правило правой или левой руки, DFS), в посте я не буду здесь останавливаться и сосредоточусь на ручном режиме.
![image](https://habrastorage.org/getpro/habr/post_images/e7d/c68/286/e7dc682861ac9dc2f74fea2f366b69e2.png)
Основа поиска — клетчатое поле
Поиск работает на графе, самый простой создать из карты граф — это
Для начала нам стоит определить класс клетки. У пользователя должна быть возможность установить вход, выход и нанести на поле непроходимые препятствия, также для изучения полезно узнавать характеристики клетки, её родителя и статус прямо во время работы алгоритма. В итоге получаем представленный класс (set-, get-функции я убрал для экономии места):
enum Status{ Click, Unclick, Enter, Exit, NoStatus };
enum ListStatus {NoList, InClosed, InOpen};
class GraphicsCell : public QGraphicsRectItem
{
public:
GraphicsCell(int, int, int, bool *, bool *, bool *, QGraphicsItem *parent = 0);
void pressButton(int buttonID);
void showInfo(QPoint pos);
void updateStatus(int upd);
void deleteInfo();
private:
int x;
int y;
int f;
int g;
int h;
int weight = INT_MAX;
Status status;
ListStatus listStatus;
bool *isEnter;
bool *isExit;
bool visited;
GraphicsCell *par;
QGraphicsRectItem *infoBox;
};
Функции pressButton и updateStatus обрабатывают изменение статуса и цвета клетки. А showInfo и deleteInfo за инфобокс, о котором далее. Переменные x и y отвечают за координаты; f, g, h, weight за характеристики необходимые для работы алгоритмов поиска, status и listStatus за
статус клетки, isEnter и isExit за то, существует ли на карте вход и выход, par за родительскую клетку(необходимо для восстановления построенного пути).
Работа с полем
Клетчатое поле мы создали, теперь хорошо бы предоставить пользователю возможность наносить вход и выход, расставлять стены и вызывать вышеупомянутый инфобокс.
К счастью, класс QGraphicsView из фреймворка Qt, на котором мы и создаем интерфейс, предоставляет нам виртуальные функции щелчка, двойного клика и движения курсора (mousePressEvent, doubleClickEvent, mouseMoveEvent соответственно). Их мы и перегружаем в классе сцены, которая содержит наши клетки.
Функция checkPos проверяет, чтобы курсор находился над объектом клетки.
void MazeWindow::mousePressEvent(QMouseEvent *event)
{
checkPos(event);
GraphicsCell *currCell = static_cast<GraphicsCell *>(scene()->itemAt(mapFromGlobal(cursor().pos()), QTransform()));
if (currCell == NULL)
return;
if (startStatus == Status::NoStatus)
{
if (currCell->status == Status::Click)
startStatus = Status::Click;
else
startStatus = Status::Unclick;
}
if (event->button() == Qt::RightButton)
{
currCell->showInfo(mapFromGlobal(cursor().pos()));
cellWithInfo = currCell;
}
else
currCell->pressButton(event->button());
}
Реализация функции щелчка. Определяем по какой клетке мы нажали и просим её обновить свой статус. Инфобокс пришлось поставить на ПКМ, так как в Qt при использовании двойного клика сначала вызывается функция обычного клика и это приводило к мерцанию клетки(мы обновляли состояние клетки при одинарном клике и возвращали его назад, когда понимали, что клик двойной).
Вход ставится на 'Ctrl + ЛКМ', а выход на колесико мыши или для тачпада 'Alt + ЛКМ'. Достаточно удобно. Стена устанавливается обычным ЛКМ.
void MazeWindow::mouseMoveEvent(QMouseEvent *event)
{
checkPos(event);
GraphicsCell *currCell = static_cast<GraphicsCell *>(scene()->itemAt(mapFromGlobal(cursor().pos()), QTransform()));
if (currCell == NULL)
return;
if (cellWithInfo != NULL && currCell != cellWithInfo)
{
cellWithInfo->deleteInfo();
cellWithInfo = NULL;
}
if (currCell->status == Status::Enter || currCell->status == Status::Exit)
return;
if (event->buttons() & Qt::LeftButton)
{
if (startStatus == Status::Click && currCell->status == Status::Click)
currCell->updateStatus(1);
else if (startStatus == Status::Unclick && currCell->status == Status::Unclick)
currCell->updateStatus(0);
}
}
Также хотелось позволить пользователю рисовать стены, как это сделано в привычных графических редакторах, зажав ЛКМ, водить по полю.
Для этого перегружаем функцию mouseMoveEvent(). Проверяем, чтобы мы были над клетками, и просим обновить состояние клетки под курсором. Если начать рисовать с пустой клетки, то и продолжим рисовать стены, если стерли стену, то и далее будем в режиме «ластика». Функция ещё отвечает за удаление инфобокса, если мы убираем курсор с клетки, на которой он был вызван.
Инфобокс создадим как обычный прямоугольник, на котором показаны характеристики веса, F, G, H (если вы знакомы с представленными выше алгоритмами, то знаете эти обозначения), текущий статус клетки и её родитель.
![image](https://habrastorage.org/getpro/habr/post_images/37b/13d/492/37b13d492f58f1c9967de627f31b6b76.png)
Всё, мы обеспечили работу поля для визуализации, половина сложной работы сделана, ура!
Визуализация хода работ по поиску пути
Самая интересная часть программы, то, что должно превращать скучную (или не очень) статью в нечто такое:
![image](https://habrastorage.org/getpro/habr/post_images/cc9/9fa/3aa/cc99fa3aa55351b3a7cc395ecb2fa4e6.gif)
Есть и пошаговый режим, который, в связке с инфобоксами, поможет на 100% понять работу каждого алгоритма.
Теперь пару слов о том, как это реализовывалось. Для примера рассмотрим функцию алгоритма AStar, остальные алгоритмы реализованы аналогично. Также мы оставим передачу сигнала от кнопки к самой функции.
bool MazeWindow::ASolve(int mode)
{
currMode = 0;
if (a == NULL)
{
//Удаление предыдущего решения, если оно существует
if (aL != NULL)
scene()->removeItem(aL);
clearLabyr();
a = new A(&labyr);
a->solveMaze(0);
}
if (mode == 0)
{
while (!a->solveMaze(1));
//Отображение
updatePictureSolve(Algorithms::AStarAlgo);
currMode = 1;
return true;
}
else
{
if (a->solveMaze(1))
{
//Отображение
updatePictureSolve(Algorithms::AStarAlgo);
QMessageBox msgBox;
msgBox.setText(tr("Sucsess"));
msgBox.setIcon(QMessageBox::Information);
msgBox.exec();
currMode = 1;
return true;
}
}
return false;
}
Пошаговый режим и полное решение мы реализовывали одной функцией, поэтому приходится передавать ID режима(0 — полное решение и 1 — для очередного шага). Далее, если это полное решение или первый шаг в пошаговом, очищаем поле от остатков предыдущего решения, чистим статусы клеток и обновляем характеристики c помощью функции clearLabyr. Функции самих алгоритмов реализованы так, что возвращают истину, если достигнута конечная точка поиска или поиск продолжать невозможно, и false, если можно работать дальше. Следовательно, для полного решения оператором while вызываем функцию, пока она не вернет true и наносим на сцену линию пути вызвав функцию updatePictureSolve. Для пошагового режима вызываем функцию при каждом щелчке, если путь найден, также отправляем его на отрисовку и выводим сообщение, чтобы пользователь случайно не прокликал момент решения.
Сами алгоритмы поиска обновляют статус клеток, когда заносят их в открытый или закрытый список.
Панель управления
В программе представлены:
- Два типа генераторов: Growing Tree и ручной режим(клетчатое поле, о котором говорилось выше)
- Пять типов алгоритмов: DFS и поиск по правилу руки для Growing Tree генератора, а также Дейкстра, AStar, JPS для ручного режима.
Необходимо было позволить пользователю удобно переключаться между назваными опциями. Результатом
![image](https://habrastorage.org/getpro/habr/post_images/1b8/772/87f/1b877287f7fb5a3ca2733aa7676c5af2.png)
Работа со статистикой
Программой также можно воспользоваться, чтобы выбрать наиболее эффективный алгоритм для данной ситуации:
- Примерно рисуем необходимую карту, получается что-то как на картинке
- Запускаем все 3 алгоритма, на глаз оцениваем работу.
Что примерно может получиться![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/ca6/369/129/ca63691292b744fc1501ebe887012a49.png)
![image](https://habrastorage.org/getpro/habr/post_images/ca6/369/129/ca63691292b744fc1501ebe887012a49.png)
Очевидно, что для более менее серьёзных проектов «на глаз» недостаточно, поэтому необходимо отображать статистику.
Мы будем делать это в виде виджета с краткой статистикой текущего алгоритма в рабочей области и отдельного окна, отображающего работу всех алгоритмов за сеанс и позволяющего создать отчет, который можно будет скопировать, например, в Excel, построить там графики.
Реализация виджета с краткой статистикой очень походит на реализацию виджета с настройками, да и выглядит он почти также:
![image](https://habrastorage.org/getpro/habr/post_images/17e/e8c/83a/17ee8c83a5348a849b0486e0c3aba809.png)
Алгоритм сам подсчитывает количество операций. Длину пути можно узнать из характеристик клетки выхода, а время мы считаем таймерами, вычитая время потраченное на рисовку(хотя это не очень то и точно). Когда алгоритм заканчивает работу он передает статистику на виджет и вызвает функцию создания записи в таблице. В итоге имеет такую таблицу:
![image](https://habrastorage.org/getpro/habr/post_images/7c8/19a/0e6/7c819a0e67fc0072b63c26c3c75f15b1.png)
Стоит отдельно сказать почему у A* и Декстры результаты одинаковые, а у JPS отличный. Это связано с тем, что используются 2 разные методики подсчета растояния между клетками: A* и Дейкстра используют стоимость вертикального и горизонтального перехода 10 и диагонального 14, а потом делят общий результат на 10; JPS использует 1 и sqrt(2) соответственно и ничего не делит, но тоже округляет. JPS показывает длину пути несколько точнее, именно поэтому числа различны.
После обработки данных можно получить что-то такое:
Для такой ситуации:
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/499/1f4/12a/4991f412aea9e1397eed678d0ec22af7.png)
Такой график:
![image](https://habrastorage.org/r/w1560/getpro/habr/post_images/6ea/f10/ca8/6eaf10ca8b014709539bdac3fb3365ff.png)
![image](https://habrastorage.org/getpro/habr/post_images/499/1f4/12a/4991f412aea9e1397eed678d0ec22af7.png)
Такой график:
![image](https://habrastorage.org/getpro/habr/post_images/6ea/f10/ca8/6eaf10ca8b014709539bdac3fb3365ff.png)
Заключение
Мы получили программу, которая помогает начинающим, и не только, программистам разобраться с алгоритмами поиска пути. По крайней мере я всё-таки помог паре своей друзей)
Автор будет рад выслушать ваши пожелания и исполнить их, как только напишет экзамены.
Возможно, череда улучшений приведет к тому, что мы получим мощную библиотеку с алгоритмами, а программа станет приятной демкой для неё (Как PathFinding.js, только лучше).
Если вы, возможно, хотели бы написать статью о поиске пути, можете приложить к ней и эту программу.
![image](https://habrastorage.org/getpro/habr/post_images/98b/9f6/a19/98b9f6a19b7a889a7cb109213f1630e5.png)
→ Опытный материал для исследования: PathFinding.js
→ Скачать архив с программой можно с ЯД или с DropBox.
UPD: изначально по ошибке была опубликована не до конца отлаженная версия, теперь все ок. Приношу свои извинения. 14.03.2017 (да-да около 4х суток висела забагованная версия :C)
→ Исходный проект VS2013: ЯД и Dropbox