roboforum.ru

Этот метод описывает методы нахождения оптимального маршрута на заранее известной карте.

Свободный перевод материала :
( не пиняйте на корявость - редактирование машинного перевода)
http://www.gamedev.net/reference/articl ... le1125.asp


Что такое - поле потенциала?
Прежде, чем начать, мы должны договориться о некоторых определениях. Мы будем говорить о 'модуле' размера пиксел, который может свободно маневрировать во всех 8 направлениях со скоростью одного пикселя в среде. Эта среда ? 2х мерная карта, которая была разделена на квадраты, размером один пиксель каждый. В этом примере мы возьмем 100*100 квадратов и назовем это 'сеткой'. Границы - стены, через которые нельзя проникнуть и есть несколько 'объектов' на карте, которых нужно избежать. В теории, эти объекты могут иметь любую форму, но мы сосредоточимся на прямоугольниках.

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

Методика 1: линейный градиент
Теперь рассмотрим несколько методов. Каждый будет немного более сложным чем предыдущий, решая проблемы от предыдущей методики, но к сожалению создавая новые.
Мы начинаем простой метод.
Вычисляем расстояние каждого пикселя до места назначения и даем это расстояние как 'потенциальное' значение к тому пикселю. Пожалуйста обратите внимание, что в этом случае Вы не должны заботиться о препятствиях (только дать им очень высокое значение). Как только это сделано, мы применяем этот алгоритм: "Проверьте все соседние пиксели текущего пикселя и выберите пиксель с самым низким потенциальным значением. Двигайтесь в этот пиксель и продолжайте, пока Вы не достигаете вашей цели или застряните."
Этот алгоритм работает весьма хорошо, если Вы имеете немного объектов в сетке, но часто, модуль застрянет позади объекта и не имеет возможности  вернуться на правильный  путь.

Методика 2: Заполнение местных минимумов
Как мы видели в первой методике можно застрять. Это случается, когда модуль находит местный минимум. В поле потенциала это представлено пикселем, который имеет соседей, которые являются или объектами или доступны, но имеют более высокое значение, не являясь местом назначения.
Улучшим наш алгоритм, используя поиск по первому наилучшему совпадению. Сделаем это, строя дерево с пикселями в сетке. Наш корень в дереве - стартовое местоположение. Этот корень имеет  8 направлений, в которых наш модуль может путешествовать, образуя ветви. Возьмем ветвь с самым низким значением и оценим все направления, в которые мы можем путешествовать отсюда, но не те, которые находятся уже в дереве. Тогда оцениваем все листья в дереве и повторяем процесс для нахождения самого низкого значения. Продолжаем процесс пока не дошли до нашего места назначения, или пока мы оценили все листья и не можем найти другой пиксель для движения (так случится, если недостижимо место назначения от нашего стартового местоположения). Если повезло, и путь определен, преодолеваем дерево от корня до выхода, содержащего наше место назначения.

Методика 3: лучше предотвратить...
Мы, возможно, нашли способ выйти из местных минимумов в нашем предыдущем решении, но было бы лучше, если мы могли бы только найти способ не иметь никаких местных минимумов вообще. Чтобы достигнуть этого, нужно изменить метод, которым формируется наше поле потенциала.
Вместо того, чтобы непосредственно вычислять расстояние между пикселем и место назначением, дадим месту назначения значение нуль и затем применим такой алгоритм: Каждый прямой (горизонтальный и вертикальный, но не диагональный) сосед места назначения получает значение 1, тогда их прямые соседи получают 2, и так далее...
Так как только наше место назначения имеет нулевое значение, и каждый другой пиксель всегда имеет соседа с более низким значением, задача будет решена, если путь существует. Этот метод также известен как расширение фронта импульса.

Методика 4: Уйдите от граней
С тех пор как мы начали наше исследование поля потенциала, мы учились выходить из минимумов и даже запрещать их полностью. Но Вы заметите в последнем рисунке, что мы двигались опасно близко к краю объектов и стен. В среде, где мы могли бы только знать приблизительное местоположение объектов, будет лучше всего остаться как далеко от них насколько возможно, чтобы избежать столкновений.
Для этого мы должны расширить наш алгоритм от предыдущей методики. Вместо того, чтобы инициализировать один фронт импульса в место назначениее, мы теперь запустим фронт импульса в каждом пикселе, который находится на краю объекта. Каждый из этих 'пикселей края' получает уникальный идентификатор и дает этот идентификатор всем его прямым соседям. Когда два идентификатора, которые являются достаточно отличными, сталкиваются, мы нашли середину между двумя близкими объектами. Результатом будет своего рода диаграмма Voronoi между объектами, которые мы можем использовать как маршрут, чтобы передвигаться между объектами. Все, что мы тогда должны сделать - дать значения пикселям в сетке, которая не принадлежит этому маршруту так, чтобы наш модуль продвинулся на маршрут как можно скорее. Для этого мы можем использовать один из методов выше.

Заключение
Методы, описанные выше - интересная альтернатива для A* алгоритма, который, кажется, очень популярен в эти дни. Хотя поля потенциала требуют,  некоторых серьезных вычислений, их принцип можетбыть полезен, если Вы нуждаетесь быстро в изменяющихся  места назначения, потому что все, что нужно сделать - увеличить или уменьшить числа в некоторой области, чтобы делать это более (или менее) привлекательным  для модуля, чтобы следовать этим путем.

А можно просто использовать поиск в ширину на карте

Во всех этих алгоритмах плохо одно - у них всего 8 направлений максимум, т.е. все маршруты по большому счету будут неоптимальны.

Можно слегка переработать алгоритм и сделать его оптимальным для любого количества направлений, с ограничением, что узловые точки маршрута все-таки будут лежать в центрах "клеток".

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

=DeaD= писал(а):Во всех этих алгоритмах плохо одно - у них всего 8 направлений максимум, т.е. все маршруты по большому счету будут неоптимальны.

Регулируется шагом сетки, с уменьшением шага движения становятся более плавными.  К тому же никто не мешает сделать сглаживание траектории по трём точкам.

setar писал(а):

=DeaD= писал(а):Во всех этих алгоритмах плохо одно - у них всего 8 направлений максимум, т.е. все маршруты по большому счету будут неоптимальны.

Регулируется шагом сетки, с уменьшением шага движения становятся более плавными.  К тому же никто не мешает сделать сглаживание траектории по трём точкам.

Нет, именно 8 направлений, а не шаг сетки будут иметь значение, например без препятствий относительное перемещение (100,200) будет всегда состоять из двух кусков (100,100) и (0,100).

Сглаживание по трем точкам поможет в данном случае только в одной точке.

Хотя в принципе можно даже посчитать на сколько будет различаться оптимальный путь из А в Б в идеальном и 8-направленном методе. И это не шибко много, так что забудем.

=DeaD= писал(а):Нет, именно 8 направлений, а не шаг сетки будут иметь значение, например без препятствий относительное перемещение (100,200) будет всегда состоять из двух кусков (100,100) и (0,100).

Ничего подобного ! невнимательное ознакомление с материалом.

Если шаг сетки 1 и нужно сделать перемещение (100,200) то результатом будет прямая, точнее это будет массив узлов сетки максимально приближенный к прямой (насколько позволяет её шаг).

setar писал(а):Ничего подобного ! невнимательное ознакомление с материалом.

Если шаг сетки 1 и нужно сделать перемещение (100,200) то результатом будет прямая, точнее это будет массив узлов сетки максимально приближенный к прямой (насколько позволяет её шаг).

неа

Тогда это что? тут видно что вместо прямой едем по ломаной в нижнем правом углу.

И вообще исходя из 8 направлений никак не может быть оптимальным именно приближенная к прямой ломанная. Она ничем не будет по расстоянию отличаться от ломанной из 2 кусков. Это практически очевидно

=DeaD= писал(а):неа
Тогда это что? тут видно что вместо прямой едем по ломаной в нижнем правом углу.

И вообще исходя из 8 направлений никак не может быть оптимальным именно приближенная к прямой ломанная. Она ничем не будет по расстоянию отличаться от ломанной из 2 кусков. Это практически очевидно

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

совпадение прямой маршрута с одним из 8 направлений поиска решения в данном случае случайное и исходит от постановки задачи - левый верхний угол старт, и нижний правый финиш. Просто в данной задаче область координат квадратная, а была бы она прямоугольная, то маршрут бы пролегал по диагонали, отличающейся от 45%.

setar писал(а):немного не так.
...skipped...
совпадение прямой маршрута с одним из 8 направлений поиска решения в данном случае случайное и исходит от постановки задачи - левый верхний угол старт, и нижний правый финиш. Просто в данной задаче область координат квадратная, а была бы она прямоугольная, то маршрут бы пролегал по диагонали, отличающейся от 45%.

Это почему случайное? видно же, что с угла препятствия в правую нижнюю точку идти над по прямой, а не по ломаной.

=DeaD= писал(а):Это почему случайное? видно же, что с угла препятствия в правую нижнюю точку идти над по прямой, а не по ломаной.

Это второй метод, градиент которого построен по прямой линии, следовательно оттимальным маршрутом всегда является прямая соединяющая старт и финиш. После исчезновения препятствия траектория стремится вернуться на исходную прямую.

Впрочем согласен, выглядит не красиво.

Рациональнее использовать последний метод.

setar писал(а):Рациональнее использовать последний метод.

А как он учитывает существование каких-то еще направлений, кроме этих 8-ми?

=DeaD= писал(а):А как он учитывает существование каких-то еще направлений, кроме этих 8-ми?

вот тут
мы явно получаем маршрут движения отличный от фосьмилучевой схемы (движение осушествляется по фиолетовым дорожкам)