А* не имеет непосредственного отношения к сетке. Сетка имеет смысл если объекты могут передвигаться исключительно квадратно-гнездовым способом. Но если объекты передвигаются так, как у вас показано на рисунке, то лучше строить направленный граф в котором ребра - цена перехода от одной вершины многоугольника описывающего препядствие до другой вершины. Получится невпример быстрее.
Очень хорошо, подробно и с иллюстрациями алгоритмы поиска пути разбирает Питер Норвиг (Peter Norvig, Artificial Intelligence A Modern Approach / AIMA). Это практически должно быть настольной книжкой игродела
