Comments 15
добрый день. отличная статья. Смотрю в ыразбираетесь в алгоритмах.
Хотеел бы от вас статьи вроде, "найти тренд видео", "самые горячие за N часов" и.т.д.
-12
В целом ок. Реализация не блещет, но это хорошая заготовка.
То, что вы называете «DistanceEstimate» это эвристическая функция — ядро алгоритма А*. Обычно для него используется Манхеттенское расстояние между точками, иногда Евклидово. Правда, обычно считается расстояние до соседней ноды, а не до конечной, а уже сумма этих расстояний для выбрных нод дает длину пути. Когда вы в эвристике делаете расчет расстояния сразу до конечной точки, вы превращаете алгоритм в «жадный», который стремится в первую очередь выбирать ноды, которые как можно ближе к последней точке. И в момент прихода к последней точке вы алгоритм останавливаете, поэтому путь будет де-факто не кратчайшим.
Чуток моих замшелых исследований по эвристике тут.
То, что вы называете «DistanceEstimate» это эвристическая функция — ядро алгоритма А*. Обычно для него используется Манхеттенское расстояние между точками, иногда Евклидово. Правда, обычно считается расстояние до соседней ноды, а не до конечной, а уже сумма этих расстояний для выбрных нод дает длину пути. Когда вы в эвристике делаете расчет расстояния сразу до конечной точки, вы превращаете алгоритм в «жадный», который стремится в первую очередь выбирать ноды, которые как можно ближе к последней точке. И в момент прихода к последней точке вы алгоритм останавливаете, поэтому путь будет де-факто не кратчайшим.
Чуток моих замшелых исследований по эвристике тут.
+6
Интересная статья, спасибо.
Про жадность алгоритма замечание дельное.
Мне не хотелось слишком нагружать пример из статьи, а способа решить данную проблему просто и без ущерба быстродействию я, к сожалению, не нашёл. Распределённый по времени автоматически обновляемый поиск пути будет выглядеть уже совсем иначе. Тянет на ещё одну статью.
Про жадность алгоритма замечание дельное.
Мне не хотелось слишком нагружать пример из статьи, а способа решить данную проблему просто и без ущерба быстродействию я, к сожалению, не нашёл. Распределённый по времени автоматически обновляемый поиск пути будет выглядеть уже совсем иначе. Тянет на ещё одну статью.
+1
UPD: неверно понял высказывание автора. Сразу придумал ситуацию, где алгоритм, как показалось, будет обходить путь неверно:
Но при моделировании путь определяется правильно, не делая большой крюк. И не должен — не знаю, почему я так решил.
Мораль: всегда проверяй гипотезу, прежде чем признавать ошибку.
Изображение
Но при моделировании путь определяется правильно, не делая большой крюк. И не должен — не знаю, почему я так решил.
Изображение
Мораль: всегда проверяй гипотезу, прежде чем признавать ошибку.
0
Правда, обычно считается расстояние до соседней ноды, а не до конечной
Можете рассказать поподробнее о какой эвристики вы говорите тут (оценка полного пути, или эвристика оставшегося)?
я вижу такое:
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
+1
Как водится, я написал не сильно вчитавшись в код, а народ еще и заплюсовал. Якорь в корму мне за менторский тон и поспешность!
У автора 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* подходит идеально. В моем текущем проекте ноды графа это места, куда можно доехать, зажав комбинацию клавиш «влево», «вправо» и «акселератор» на разные промежутки времени, двигаясь по кривой Корню с учетом ускорения, текущей линейной и угловой скорости, вязкости среды. Визуально эти точки образуют сложное облако, ничуть не похожее на сетку или навмеш.
0
автор, спасибо вам за статью, очень понравился ваша реализация алгоритма на шарпе, многое для себя открыл. Побольше бы таких статей
+1
В C# разве нет очереди с приоритетами?
0
Самое близкое решение из коробки — SortedSet, о нём я упомянул в статье — в коллекцию не пропустит ноды с одинаковой ценой, хотя сами ноды разные.
Ещё есть SortedDictionary с вложенными листами — но это очень дорогое решение для динамичного набора нод.
Ещё есть SortedDictionary с вложенными листами — но это очень дорогое решение для динамичного набора нод.
0
SO подсказывает, что в .net существует как минимум две имплементации, правда минимум один в 17 году был с багом из-за некорректной реализации Pop()
.
0
Но они не включены в стандартные библиотеки .Net!
Не то чтобы хорошим тоном было бы взять стороннюю готовую имплементацию и закончить на этом. Нужно было бы включать в статью подробный разбор и анализ исходников. Статья, во-первых, не совсем про это, а во вторых, структурно от этого не изменилась бы.
Не то чтобы хорошим тоном было бы взять стороннюю готовую имплементацию и закончить на этом. Нужно было бы включать в статью подробный разбор и анализ исходников. Статья, во-первых, не совсем про это, а во вторых, структурно от этого не изменилась бы.
0
Нет ;(
0
удалено
0
Вспоминаю свою курсовую работу: нужно было найти кратчайший путь до ноды с весом: сделал с циклом и со стеком, вполне хватало для малого числа нод и рёбер.
0
Спасибо за статью. Интересно: «Сохранить хеш для метода GetHashCode в локальную переменную в классе Vector2Int.» насколько это даст выигрыш? И вообще даст ли?
0
Sign up to leave a comment.
A* pathfinding на C#: двоичные кучи и борьба с аллокациями