Такая задача лучше решается аппроксимацией препядствий к многоугольникам. В таком случае самый короткий путь будет однозначно опираться на вершины этих многоугольников.
Далее, существует много разновидностей А* алгоритма, но в чистом виде А* интересен только как теория - на практике он очень медленный. Отличие этого алгоритма заключается в том, что у него есть эвристическая функция которая "примерно"* рассчитывает расстояние до цели. Благодаря этой функции можно строить стек по приоритетам какие узлы просматривать следующими.
В вашем случае эвристической функцией может быть расстояние по прямой до цели. Таким образом будет выбран узел (точка пересечения пути и многоугольника ограничивающего препядствие) который ближе всего к конечной цели. На следующем этапе будут опять проверены все узлы-потомки на предмет приближенности к цели, и, скорее всего будет раскрыт не потом узла раскрытого на предыдущем этапе, а его сосед (см. картинку).
Код:
| (1) | (2) | (3) | (4) | (5)
/ \ / \ / \ / \
[] [] / [] / [] \ / [] \
\
* * * * *
Т.е. при близких значениях полученных из f(N,P) = h(P) + c(N,P), где N - текущий узел, P - потомок, h - эвристическая функция, c - цена перехода от одного узла к другому, полученных из функции f - неизбежно получается, что нужно проверить какое-то дополнительное количество узлов (тем более, что в общем случае нет гарантии того, что вообще лучшее решение - единственное). Чем лучше эвристическая функция, тем меньше процент "ненужных" узлов, которые прийдется посетить за время поиска.
Есть несколько вариантов тактик обхода дерева, можно при нахождении узла-соседа с лучшим показателем записывать в предыдущем значение лучшего узла-наследника и "закрывать" его, переходя в проверку нового найденного лучшего узла. Можно пытаться не смотря ни на что добраться до целевого узла, а потом проверять остальные "хорошие" узлы, которые были встречены на пути - при обнаружении лучшего пути, заменить им бывший выбранный, и повторить процедуру.
Но что самое хорошее в этом деле, так это то, что алгоритмы поиска пути еще все не найдены, и у вас есть все шансы найти лучший
* - эвристическая функция должна быть "оптимистической" - т.е. она никогда не должна переоценивать сложность перехода к целевому узлу.