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

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

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

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

Приступим!