Попытки сделать изучение алгоритмов поиска пути проще

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

Каждый игровой разработчик сталкивается с задачей, в которой требуется заставить персонажа(или бота) пройти из одной точки в другую, при этом не собрав все стены. А разработчикам стратегий ещё нужно учитывать проходимость клеток(дороги, болота, леса и так далее). Вот здесь на помощь приходят алгоритмы поиска пути.

image

Зачем?


Из вышесказанного можно сделать вывод, что любому игровому разработчику рано или поздно приходится сталкиваться и разбираться с поиском пути, а позже и модифицировать и оптимизировать его для собственных проектов. А так как очень много новичков сразу идут в GameDev для них не всегда просто прочитать несколько статей и понять тот или иной алгоритм. В этом посте описаны попытки создать программное обеспечение, которое поможет облегчить процесс понимания принципов работы алгоритмов поиска пути.

Несколько слов об основных алгоритмах


Мы будем рассматривать 3 основных алгоритма. Теперь в двух словах о каждом из основных алгоритмов и скриншоты визуализации их работы в программе (немного опережая события).

Алгоритм Дейкстры


Разработан нидерландским учёным Эдсгером Дейкстрой в 1959 году. Алгоритм проверит каждую из вершин графа пока не найдет кратчайший путь до исходной вершины. Подробнее можно прочитать, например, тут.

image

A*(A Star)


Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. При рассмотрении каждой отдельной вершины переход делается в ту соседнюю вершину, предположительный путь из которой до искомой вершины самый короткий.
Начать изучение можно здесь.

image

Jump Point Search


Данный алгоритм был представлен в 2011 году Д. Харбором и А. Грастиеном. JPS ускоряет поиск пути, «перепрыгивая» многие места, которые должны быть просмотрены. «Прыжковые точки» позволяют ускорить алгоритм поиска пути, рассматривая только «необходимые» узлы. Очень хорошо объясняется принцип работы здесь

image

Небольшая оговорка


Стоить отметить, что Growing Tree генератор, также представленный в программе, создает «классический лабиринт» как на картинке ниже(только больше), высота и ширина в настройках далее задается именно для него. Этот генератор был добавлен для создания «Вау-эффекта» у новичка и для демонстрации пути, построенного самыми базовыми алгоритмами(Правило правой или левой руки, DFS), в посте я не буду здесь останавливаться и сосредоточусь на ручном режиме.

image

Основа поиска — клетчатое поле


Поиск работает на графе, самый простой создать из карты граф — это расставить вэйпоинты самому перевести карту в клетчатое поле. Так как цель — облегчить понимание основ, мы и собираемся работать с квадратными клетками.

Для начала нам стоит определить класс клетки. У пользователя должна быть возможность установить вход, выход и нанести на поле непроходимые препятствия, также для изучения полезно узнавать характеристики клетки, её родителя и статус прямо во время работы алгоритма. В итоге получаем представленный класс (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

Всё, мы обеспечили работу поля для визуализации, половина сложной работы сделана, ура!

Визуализация хода работ по поиску пути


Самая интересная часть программы, то, что должно превращать скучную (или не очень) статью в нечто такое:

image

Есть и пошаговый режим, который, в связке с инфобоксами, поможет на 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

Работа со статистикой


Программой также можно воспользоваться, чтобы выбрать наиболее эффективный алгоритм для данной ситуации:

  • Примерно рисуем необходимую карту, получается что-то как на картинке
  • Запускаем все 3 алгоритма, на глаз оцениваем работу.

Что примерно может получиться
image

Очевидно, что для более менее серьёзных проектов «на глаз» недостаточно, поэтому необходимо отображать статистику.

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

Реализация виджета с краткой статистикой очень походит на реализацию виджета с настройками, да и выглядит он почти также:

image

Алгоритм сам подсчитывает количество операций. Длину пути можно узнать из характеристик клетки выхода, а время мы считаем таймерами, вычитая время потраченное на рисовку(хотя это не очень то и точно). Когда алгоритм заканчивает работу он передает статистику на виджет и вызвает функцию создания записи в таблице. В итоге имеет такую таблицу:

image
Стоит отдельно сказать почему у A* и Декстры результаты одинаковые, а у JPS отличный. Это связано с тем, что используются 2 разные методики подсчета растояния между клетками: A* и Дейкстра используют стоимость вертикального и горизонтального перехода 10 и диагонального 14, а потом делят общий результат на 10; JPS использует 1 и sqrt(2) соответственно и ничего не делит, но тоже округляет. JPS показывает длину пути несколько точнее, именно поэтому числа различны.
После обработки данных можно получить что-то такое:
Для такой ситуации:
image

Такой график:
image

Заключение


Мы получили программу, которая помогает начинающим, и не только, программистам разобраться с алгоритмами поиска пути. По крайней мере я всё-таки помог паре своей друзей)

Автор будет рад выслушать ваши пожелания и исполнить их, как только напишет экзамены.
Возможно, череда улучшений приведет к тому, что мы получим мощную библиотеку с алгоритмами, а программа станет приятной демкой для неё (Как PathFinding.js, только лучше).

Если вы, возможно, хотели бы написать статью о поиске пути, можете приложить к ней и эту программу.

image

→ Опытный материал для исследования: PathFinding.js
→ Скачать архив с программой можно с ЯД или с DropBox.
UPD: изначально по ошибке была опубликована не до конца отлаженная версия, теперь все ок. Приношу свои извинения. 14.03.2017 (да-да около 4х суток висела забагованная версия :C)
→ Исходный проект VS2013: ЯД и Dropbox
Share post

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 18

    0

    поиск Дейкстры находит минимальные пути. по таблице результатов это не так — 115 vs 112. где-то ошибки
    A* тоже должен был найти 112, но тут можно списать на нелучшую эвристистику

      +1
      Это связано с тем, что для Дейкстры и A* мы используем стоимость единичного перехода горизонталь и вертикаль 10, а диагональ 14, потом делим общий результат на 10. А в JPS мы более точно считаем 1 для горизонтали и вертикали, и sqrt(2) для диагонали. Делалось это для демонстации того, что можно по разному считать: для Дейкстры и AStar'а быстрее, но менее точно, а т.к. JPS сам очень эффективный и быстрый, можем пожертвовать капелькой времени, ради точности. Я хотел об этом сказать, но забыл) Спасибо, что напомнили
        0
        А почему не стали делать для дейкстры веса 1 000 000 и 1 414 214 соответссвенно и не жертвовать точностью?
          0
          Тогда будет необходимо реализовывать длинную арифметику + во всех статьях используются именно такие методы подсчета, а планировалось, что программу нужно использовать в связке со справочным материалом. Следовательно, чтобы пользователю было удобно и привычно, я поставил такие величины
      0
      Правило левой или правой руки не работает для любого лабиранта.
      Вероятностый алгоритм Тарри обходит любой лабиринт за минимальное м.о. времени
        0
        В этой программе пользователь может запустить правило руки только на самом простом лабиринте без циклов и галерей, поэтому правило руки всегда будет давать верное решение. Да и добавлял я его просто для введения в лабиринты и поиск пути.
        0
        Я не полностью понимаю все детали JPS, но не верю, что можно взять и провести прямую линию между двумя клетками, не просмотрев все клетки по пути, что следует из представленной иллюстрации. Алгоритм Дейкстры, в свою очередь, не будет просматривать точки на бОльшем удалении от искомой точки, так что эту иллюстрацию тоже сложно назвать корректной.
          0
          JPS тоже рекурентно просматривает множество клеток, но он не совершает с ними много операций(не заносит в открытий и закрытый список, не проверяет соседей, не вычисляет F, G, H), а лишь вызывает рекурсивную функцию далее, пока точка не будет соответствовать правилам перхода, это и значительно увеличивает скорость поиска. Об этом можно прочитать по ссылке из поста. Цвет в свою очередь показывает принадлежность закрытому(желтый) и открытому(синий) спискам, поэтому все честно)

          А Декстра слева ушел далеко, потому что правой стороне надо было еще искать путь обогнуть стену. Если оставить две точки на пустом поле ваше утверждение будет верным, как только появляются препятсвия, Дейкстра пойдет неравномерно.
            +2
            JPS тоже рекурентно просматривает множество клеток, но он не совершает с ними много операций

            Сложность от этого не меняется и остается линейной количеству просмотренных клеток (Дейкстра, конечно, медленее асимптотически, но этот тут не принципиально). Хотя бы подсветить их другим цветом и учесть в графиках количества пройденных клеток не помешало бы.

            А Декстра слева ушел далеко, потому что правой стороне надо было еще искать путь обогнуть стену

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

              Дейкстра реализовывалась строго по «учебникам», поэтому поиск должен быть верным. Приложу парочку гифок для понятности.

              Gif #1
              image

              Здесь вы на 100% правы

              Gif #2
              image


              Здесь расстояние между точками тоже, только появляется стена(вверх короче чем вниз). Пока левая сторона обходит стену, правая продолжает расширятся.
              Мы могли бы и прерывать поиск в одну сторону, когда видим, что превышен радиус, в котором находится выход, но одним из ключевых преимуществ Дейкстры является то, что не нужна вообще никакая информация о выходе, и, добавляя проверку радиуса, мы это теряем.
              Также этот эффект наблюдается и в проверенной многими библиотеке PathFinding.js (на случай, если вы мне не верите, можете попробовать :) ). Это объясняется тем, что когда мы натыкаемся на стену, например, слева (как на гифке), поиск влево временно прекращается, поэтому и нарушается равенства радиуса поиска во всех направлениях.
                +1
                Не должно быть посещено ни одной клетки, которая находится дальше от старта, чем целевая вершина, т.е. как минимум клетки в нижнем правом углу не должны быть посещены. Ну или меня глазомер обманывает :)
                На похожем принципе и работает алгоритм А*.
                В общем случае это не верно. Если стена в форме буквы П, то нам придется посетить клетки, которые находятся дальше* от старта.
                *) по прямой.
                ПС. Если вы можете быстро посчитать расстояние с учетом препятствий, то можете просто выбирать соседа с наименьшим расстоянием до финиша.
            0
            → Скачать архив с программой можно с ЯД или с DropBox.
            Выкладывать программы без исходников нехорошо. :-)
              0
              Боюсь критики, своего некачественного кода:D Это мой первый проект выше уровня тетриса :)
              Но если так положено приложу в ближайшее время.
                +1
                К вечеру будет.
              0
              А можете подробнее описать процедуру подсчёта времени. Это результаты в каких единицах?
                0
                Это в миллисекундах.
                Время считают QTimer'ы, один считает общее время, второй считает время на паузы(отрисовка, переходы функций). Если использовать один и постоянно тормозить его, получалось вообще неточно. Эта часть статистики остро нуждается в доработке, желательно поискать какую-нибудь библиотеку для этого или, ещё лучше, попробовать QDebug или QTest для этого.
                0
                Эта ссылка должна быть в каждой статье про алгоритмы поиска пути в качестве опытного материала для исследования…
                  0
                  Она там есть в самом конце. Сейчас ещё раз отдельно вставлю.
                  Возможно, череда улучшений приведет к тому, что мы получим мощную библиотеку с алгоритмами, а программа станет приятной демкой для неё (Как PathFinding.js, только лучше).

                Only users with full accounts can post comments. Log in, please.