Всем привет.
Тема, в принципе, изъезженная, но тем не менее, мне так и не удалось найти достаточно четких обоснований в пользу тех или иных алгоритмов, а главное, сравнения их эффективности.

Задача известна: есть двумерный массив ячеек с весами. От 1 до 255. Чем больше вес, тем сложнее пройти через эту область (ячейку). Если вес 0 - значит пройти через эту ячейку вообще нельзя. Нужно найти минимальный по стоимости (сумме весов) путь из А в Б. Особый интерес предоставляет факт наличия вовсе непроходимых областей.

Кто что знает по этому поводу, поделитесь. В первую очередь интересуют максимально быстрые алгоритмы с резонными по потимальности найденными путями на больших массивах (начиная с 256х256). И конечно, очень буду рад линкам на качественные ресурсы по теме. Все это применительно к игроделанью, кстати.

TheRawGod
Поисковик: weighted graphs Floyd Dijkstra shortest path

тот же поисковик: волновой алгоритм
;)

Да, обе квери оказались актуалными, спасибо.

Чтобы подитожить, скажу что нарыл: на сегодня объективно наиболее премлемым для сабжа является алгоритм А* и его вариации/доработки под конкретный случай. Это по сути классический метод Дейкстры, только доработанный и немного измененный, в чем-то он похож и на волновой, кстати. Вот так.


ЗЫ Оффтоп, но: спасибо админам, за то что поправили неуклюжее название топика. В будущем буду внимательнее.

Я этой вещью занимался когда игру писал, там есть карта с рельефом и войска (стратегия пошаговая) с разной проходимостью. Правда исходник щас выслать не могу, это было на Спеке... Но я ее ща портирую, если интересно- месяца через четыре иожет выйдет. Мой алгоритм самодельный, нихрена никогда по программированию не читал (да и негде было)- находит кратчайший путь (незнаю насколько быстро- карту 48*48 проходил за 8 секунд, но это ZX, 3.5 МГц.