Дано:
Двухмерная система координат, поле известных размеров, массив с координатами препятствий, начальные координаты, конечные координаты.
Нужно:
Массив с координатами кратчайшего пути от начальных до конечных координат.

Какой алгоритм наиболее оптимален для данной задачи?

Во-первых, как мы передвигаемся по полю? Попробую стелепатировать, что с каждой клетки мы можем передвигаться на 4 соседа.

Мне видится два алгоритма - в зависимости от размеров поля.

Первый, самый очевидный - за O(NM) для каждой стартовой клетки, т.е. когда поле не очень большое. Это обход в ширину (как его часто называют, волновой алгоритм), - представляем поле как граф, в котором вершины - клетки, а рёбра проводятся между соседними клетками. Граф невзвешенный, и обход в ширину самое то для поиска кратчайшего пути.

Второй - если размеры поля могут быть огромными, а число P препятствий не очень много. Поле представляем как сетку - вокруг каждого препятствия оставляем 4 клетки-соседа, из оставшихся клеток строим сетку (т.е. проводим горизонтальные и вертикальные прямые через каждую оставшуюся клетку), в результате получится O(P^2) вершин в графе, между которыми проводятся взвешенные рёбра (из каждой клетки можем пойти только в 4 её соседа по 4-м направлениям (именно не соседнюю клетку в этом направлении, а соседнюю в сетке), поэтому рёбер будет тоже O(P^2). На получившемся графе надо будет запускать уже Дейкстру, асимптотика получится O(P^2 logP) для каждой стартовой клетки, да и с нехилой константой, но зато не зависящая от размеров поля.

Добавлено через 8 минут и 13 секунд
Вместо Дейкстры можно применить какой-нибудь шаманский алгоритм вроде Левита, он здесь вполне может оказаться быстрее, но всё-таки надо учесть, что вершин в графе будет в худшем случае (4*P)^2, и уже для P=1000 кодес надо будет жестоко оптимайзить.

Передвигаться можно на любую соседнюю клетку т.е. в 8ми направлениях. Поле максимум 100*100. На координаты в массиве препятствий нельзя наступать.

Можно попросить линк на человеческое описание любого из перечисленных выше алгоритмов или на топик где подобное уже обсуждали, просто нужен самый быстрый вариант алгоритма. Образование у меня не совсем по этой области, а в подобных алгоритмах слаб и выше написанное немного недопонял.

Добавлено @ 20:24
Пряпятствия генерируются рэндомно в зависимости от поля, их количество может достигать до 30% от всего поля.

Это сообщение отредактировал(а) Onis - 30.12.2008, 20:25

Если 100x100, то не париться и написать обычный обход в ширину.
Ссылку давать не буду, он описывается в десятках мест (а описать его "плохо" невозможно  ).
Наводку я уже дал:

Запускаем обход в ширину из стартовой клетки, запрещаем ему заходить в "плохие" клетки, он находит кратчайшие пути от стартовой клетки до всех. Граф можно в явном виде не строить - просто есть у нас текущая вершина (которая задаётся координатами (x,y)), и из неё пытаемся перейти в 8 соседних клеток.

Я на досуге немного по рассуждал, и дошел до того что просто поиск в ширину будет жрать слишком много ресурсов, решил взять алгоритм А*. Написал код, потом переписал, потом заново написал, потом опять прочел мануал и всё равно работает косо.

МБ знающие люди подскажут нормальную литературу по AI с более подробным рассмотрением подобных проблем?

Как это дофига? Для обхода в ширину надо 2 массива того же размера, что и поле, и больше ничего. И время работы будет O(NM), при данных ограничениях порядка 10^5 операций (учитывая, что за секунду примерно 10^7-10^8 операций выполняется - разве это много?)

посмотри здесь:
волновой алгоритм