Ориентация в пространстве. Урок 4. А-Алогоритм

Что бы смотреть урок полностью, подпишитесь на платный раздел.

В платном разделе статья находиться здесь.

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

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

1. Начинаем со стартовой точки A и добавляем ее в "открытый список" клеток, которые нужно обработать. Открытый список это что-то наподобие списка покупок. В данный момент есть только один элемент в списке, но позже мы добавим еще. Список содержит клетки, которые может быть находятся вдоль пути, который вы выберете, а может и нет. Проще говоря, это список клеток, которые нужно проверить.
2. Ищем доступные или проходимые клетки, граничащие со стартовой точкой, игнорируя клетки со стенами, водой или другой непроходимой областью. И также добавляем их в открытый список. Для каждой из этих клеток сохраняем точку A, как "родительскую клетку". Эта родительская клетка важна, когда мы будем прослеживать наш путь. Это будет описано намного позже.
3. Удаляем стартовую точку A с вашего открытого списка и добавляем ее в "закрытый список" клеток, которые вам больше не нужно проверять.
4. Удаляем ее из открытого списка и добавляем в закрытый список.
5. Проверяем все соседние клетки. Игнорируем те, которые находятся в закрытом списке или непроходимы (поверхность со стенами, водой), остальные добавляем в открытый список, если они там еще не находятся. Делаем выбранную клетку "родительской" для всех этих клеток.
6. Если соседняя клетка уже находится в открытом списке, проверяем, а не короче ли путь по этой клетке? Иными словами, сравниваем значения стоимости G этих двух клеток. Если при использовании этой клетки стоимость перехода выше, чем при использовании текущей клетки, то не предпринимаем ничего. Если же она ниже, то меням "родителя" этой клетки на выбранную клетку.

Повторяем цикл до тех пор, пока не доберемся до исходной клетки или пока не обнаружим, что нам некуда идти.

Как определить стоимость пути?  Общем случае при движении по горизонтали  и вертикали берем стоимость перемещения по клетке 1, а по диагонали 1.4 (путь по диагонали длиннее, данный коэффициент следует из теоремы Пифагора).  Когда рассчитываем стоимость пути до пункта назначения, предполагаем, что мы движемся по горизонтали до того момента, пока координата x не станет равной координате точки назначения, затем по вертикали, пока не сравняется координата y. Ну, или наоборот, от перестановки слагаемых сумма не меняется.  Расчет производиться следующим образом: сначала считаем стоимость перемещения в проверяемую соседнюю клетку, затем из нее в пункт назначения. Полученные результаты складываются. Стоимость не обязательно 1 и 1.4. В пространстве могут быть и такие объекты, которые препятствуют движению. Например, пространство может быть картой компьютерной игры, где есть болота, леса, горы.

Описание этого алгоритма взяты из статьи Патрика Лестера (Patrick Lester) "Алгоритм A* для новичков.". Описано несколько сумбурно и не совсем понятно, но тем не менее, мы попробуем его реализовать, а потом будем понимать как он работает и оптимизировать. Но сначала создадим ряд вспомогательных классов...

...

...Для задач ориентации робота в пространстве (включая в том числе и А Алгоритм) мы создадим абстрактный  класс Task:

Подробнее о методах. Тут есть один важный метод step - это шаг выполнения задачи. На каждом шаге робот будет выполнять определенные действия, до тех пор, пока задача не будет выполнена. В случае с A Алгоритмом мы сначала рассчитаем пусть, согласно этому алгоритму, а потом будем двигать робота по этому пути, вызывая метод step. В рамках данного урока реализуем алгоритм расчета:

Добавим в форме кнопочку*:

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

Тестируем:

Как видим, алгоритм довольно корректно рассчитал путь. К сожалению, он делает это не всегда оптимально:

Почему так происходит? Дело в том, ...

....

... Это не единственный подводный камень данного алгоритма. Но более подробно мы будем с ним работать на будущих уроках.

Скриншоты, помеченные знаком *, являются цитатами и иллюстрациями  программного продукта "Microsoft Visual Studio 2010 Professional", авторское право на который принадлежит корпорации Microsoft..