• A* pathfinding на C#: двоичные кучи и борьба с аллокациями
    0
    UPD: неверно понял высказывание автора. Сразу придумал ситуацию, где алгоритм, как показалось, будет обходить путь неверно:

    Изображение


    Но при моделировании путь определяется правильно, не делая большой крюк. И не должен — не знаю, почему я так решил.

    Изображение


    Мораль: всегда проверяй гипотезу, прежде чем признавать ошибку.
  • A* pathfinding на C#: двоичные кучи и борьба с аллокациями
    0
    Но они не включены в стандартные библиотеки .Net!

    Не то чтобы хорошим тоном было бы взять стороннюю готовую имплементацию и закончить на этом. Нужно было бы включать в статью подробный разбор и анализ исходников. Статья, во-первых, не совсем про это, а во вторых, структурно от этого не изменилась бы.
  • A* pathfinding на C#: двоичные кучи и борьба с аллокациями
    0
    Самое близкое решение из коробки — SortedSet, о нём я упомянул в статье — в коллекцию не пропустит ноды с одинаковой ценой, хотя сами ноды разные.

    Ещё есть SortedDictionary с вложенными листами — но это очень дорогое решение для динамичного набора нод.
  • A* pathfinding на C#: двоичные кучи и борьба с аллокациями
    +1
    Интересная статья, спасибо.

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