Вот нашел две либы с алгоритмами нахождения кратчайшего пути между двумя точками А*(A Star) - в фосьми направлениях и Mordystar - оптимизированный А* для четырех направлений.

Сам я пытался разобраться да понял далеко не все. Прошу тех кто разберется описать работу алгоритмов (желательно на русском :)).

ОЧЕНЬ подробное описание алгоритма:
http://blitzetc.boolean.name/03-apr05.htm

Да особенно меня интересует алгоритм Mordystar для четырех направлений :)