Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 15
добрый день. отличная статья. Смотрю в ыразбираетесь в алгоритмах.
Хотеел бы от вас статьи вроде, "найти тренд видео", "самые горячие за N часов" и.т.д.
В целом ок. Реализация не блещет, но это хорошая заготовка.
То, что вы называете «DistanceEstimate» это эвристическая функция — ядро алгоритма А*. Обычно для него используется Манхеттенское расстояние между точками, иногда Евклидово. Правда, обычно считается расстояние до соседней ноды, а не до конечной, а уже сумма этих расстояний для выбрных нод дает длину пути. Когда вы в эвристике делаете расчет расстояния сразу до конечной точки, вы превращаете алгоритм в «жадный», который стремится в первую очередь выбирать ноды, которые как можно ближе к последней точке. И в момент прихода к последней точке вы алгоритм останавливаете, поэтому путь будет де-факто не кратчайшим.
Чуток моих замшелых исследований по эвристике тут.
То, что вы называете «DistanceEstimate» это эвристическая функция — ядро алгоритма А*. Обычно для него используется Манхеттенское расстояние между точками, иногда Евклидово. Правда, обычно считается расстояние до соседней ноды, а не до конечной, а уже сумма этих расстояний для выбрных нод дает длину пути. Когда вы в эвристике делаете расчет расстояния сразу до конечной точки, вы превращаете алгоритм в «жадный», который стремится в первую очередь выбирать ноды, которые как можно ближе к последней точке. И в момент прихода к последней точке вы алгоритм останавливаете, поэтому путь будет де-факто не кратчайшим.
Чуток моих замшелых исследований по эвристике тут.
Интересная статья, спасибо.
Про жадность алгоритма замечание дельное.
Мне не хотелось слишком нагружать пример из статьи, а способа решить данную проблему просто и без ущерба быстродействию я, к сожалению, не нашёл. Распределённый по времени автоматически обновляемый поиск пути будет выглядеть уже совсем иначе. Тянет на ещё одну статью.
Про жадность алгоритма замечание дельное.
Мне не хотелось слишком нагружать пример из статьи, а способа решить данную проблему просто и без ущерба быстродействию я, к сожалению, не нашёл. Распределённый по времени автоматически обновляемый поиск пути будет выглядеть уже совсем иначе. Тянет на ещё одну статью.
UPD: неверно понял высказывание автора. Сразу придумал ситуацию, где алгоритм, как показалось, будет обходить путь неверно:
Но при моделировании путь определяется правильно, не делая большой крюк. И не должен — не знаю, почему я так решил.
Мораль: всегда проверяй гипотезу, прежде чем признавать ошибку.
Изображение
Но при моделировании путь определяется правильно, не делая большой крюк. И не должен — не знаю, почему я так решил.
Изображение
Мораль: всегда проверяй гипотезу, прежде чем признавать ошибку.
Правда, обычно считается расстояние до соседней ноды, а не до конечной
Можете рассказать поподробнее о какой эвристики вы говорите тут (оценка полного пути, или эвристика оставшегося)?
я вижу такое:
EstimatedTotalCost = TraverseDistance + heuristicDist;double traverseDistance = parent.TraverseDistance + cost;и это выглядить с моей колокольни верно: оценка полного пути= пройденное расстояние + эвристика до цели. И приоритетом в очереди является именно оценка полного пути.
var comparer = Comparer<PathNode>.Create((a, b) => b.EstimatedTotalCost.CompareTo(a.EstimatedTotalCost));P.S.
Но для сетки, я бы лучше использовал массивы а не хэш сеты. Отсутствие аллокация это хорошо, но и локальность данных тоже хорошо бы иметь
P.P.S.
или если уже граф, то можно делать более эффективное представление для статических карт например сильно упрощенный navigation mesh
Как водится, я написал не сильно вчитавшись в код, а народ еще и заплюсовал. Якорь в корму мне за менторский тон и поспешность!
У автора Vector2Int.DistanceEstimate считает точное диагональное расстояние до точки (0,0), это значит, что два весовых коэффициента (уже пройденный путь и тот, который надо пройти) имеют 1в1 одинаковую размерность и, по-сути для пути без препятствий показывают точное расстояние от старта до точки и точки до цели:
Это превращает алгоритм в точный A*, без намека на «жадность». Путь получается гарантированно кратчайшим по расстоянию и недостаток у него лишь один — излишняя геометричность:
Еще раз по пунктам, как это работает: в каждой точке алгоритм оценивает следующий шаг, сортируя возможные шаги по приблизительному расстоянию до цели heuristicDistance. Когда происходит возврат назад из финальной точки к конечной (разворачивание всех точек пути), используется traverseDistance. Т.к. эти значения считаются по одинаковому принципу, то обратный путь будет гарантировано кратчайшим.
Единственное, что надо проверить, так это заменяет ли автор уже в найденных точках значение traverseDistance, если к ним нашелся более короткий путь. Update: заменяет, это как раз последняя строка кода в листинге в статье.
P.S. На счет массивов и хешсетов. Я бы использовал вообще все коллекции другие. Но это уже детали. Правильно сделать сначала так, а потом уже оптимизировать по мере надобности. Если собственное бинарное дерево решило вопросы производительности, значит в задаче автора этого достаточно.
P.P.S. Навигация по навмешу это та же самая навигация по графу с эвристикой и для нее A* подходит идеально. В моем текущем проекте ноды графа это места, куда можно доехать, зажав комбинацию клавиш «влево», «вправо» и «акселератор» на разные промежутки времени, двигаясь по кривой Корню с учетом ускорения, текущей линейной и угловой скорости, вязкости среды. Визуально эти точки образуют сложное облако, ничуть не похожее на сетку или навмеш.
У автора Vector2Int.DistanceEstimate считает точное диагональное расстояние до точки (0,0), это значит, что два весовых коэффициента (уже пройденный путь и тот, который надо пройти) имеют 1в1 одинаковую размерность и, по-сути для пути без препятствий показывают точное расстояние от старта до точки и точки до цели:
double traverseDistance = parent.TraverseDistance + cost;
double heuristicDistance = (position - target).DistanceEstimate();Это превращает алгоритм в точный A*, без намека на «жадность». Путь получается гарантированно кратчайшим по расстоянию и недостаток у него лишь один — излишняя геометричность:
Скрытый текст
Еще раз по пунктам, как это работает: в каждой точке алгоритм оценивает следующий шаг, сортируя возможные шаги по приблизительному расстоянию до цели heuristicDistance. Когда происходит возврат назад из финальной точки к конечной (разворачивание всех точек пути), используется traverseDistance. Т.к. эти значения считаются по одинаковому принципу, то обратный путь будет гарантировано кратчайшим.
Единственное, что надо проверить, так это заменяет ли автор уже в найденных точках значение traverseDistance, если к ним нашелся более короткий путь. Update: заменяет, это как раз последняя строка кода в листинге в статье.
P.S. На счет массивов и хешсетов. Я бы использовал вообще все коллекции другие. Но это уже детали. Правильно сделать сначала так, а потом уже оптимизировать по мере надобности. Если собственное бинарное дерево решило вопросы производительности, значит в задаче автора этого достаточно.
P.P.S. Навигация по навмешу это та же самая навигация по графу с эвристикой и для нее A* подходит идеально. В моем текущем проекте ноды графа это места, куда можно доехать, зажав комбинацию клавиш «влево», «вправо» и «акселератор» на разные промежутки времени, двигаясь по кривой Корню с учетом ускорения, текущей линейной и угловой скорости, вязкости среды. Визуально эти точки образуют сложное облако, ничуть не похожее на сетку или навмеш.
автор, спасибо вам за статью, очень понравился ваша реализация алгоритма на шарпе, многое для себя открыл. Побольше бы таких статей
В C# разве нет очереди с приоритетами?
Самое близкое решение из коробки — SortedSet, о нём я упомянул в статье — в коллекцию не пропустит ноды с одинаковой ценой, хотя сами ноды разные.
Ещё есть SortedDictionary с вложенными листами — но это очень дорогое решение для динамичного набора нод.
Ещё есть SortedDictionary с вложенными листами — но это очень дорогое решение для динамичного набора нод.
SO подсказывает, что в .net существует как минимум две имплементации, правда минимум один в 17 году был с багом из-за некорректной реализации Pop().
Но они не включены в стандартные библиотеки .Net!
Не то чтобы хорошим тоном было бы взять стороннюю готовую имплементацию и закончить на этом. Нужно было бы включать в статью подробный разбор и анализ исходников. Статья, во-первых, не совсем про это, а во вторых, структурно от этого не изменилась бы.
Не то чтобы хорошим тоном было бы взять стороннюю готовую имплементацию и закончить на этом. Нужно было бы включать в статью подробный разбор и анализ исходников. Статья, во-первых, не совсем про это, а во вторых, структурно от этого не изменилась бы.
Нет ;(
удалено
Вспоминаю свою курсовую работу: нужно было найти кратчайший путь до ноды с весом: сделал с циклом и со стеком, вполне хватало для малого числа нод и рёбер.
Спасибо за статью. Интересно: «Сохранить хеш для метода GetHashCode в локальную переменную в классе Vector2Int.» насколько это даст выигрыш? И вообще даст ли?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
A* pathfinding на C#: двоичные кучи и борьба с аллокациями