• A* pathfinding на C#: двоичные кучи и борьба с аллокациями

    Сегодня мы разбираем один из популярнейших алгоритмов поиска пути. Работать будем с двумерным массивом целочисленных координат.

    Сначала кратко ознакомимся с методами обхода графов, напишем собственно поиск пути, а затем перейдём к самому вкусному: оптимизации быстродействия и затрат по памяти. В идеале следует разработать реализацию, вообще не генерирующую мусор при использовании.

    Я был изумлен, когда поверхностный поиск не выдал мне ни одной качественной реализации алгоритма A* на C# без использования сторонних библиотек (это не значит, что их нет). А значит самое время размять пальцы!

    Жду читателя, который хочет разобраться в работе алгоритмов поиска пути, как и знатоков алгоритмов для ознакомления с реализацией и способами её оптимизации.

    Приступим!
    Читать дальше →