Алгоритм поиска кратчайшего пути, движение персонажей в RPG играх Опции

[Дож]

Это обсуждалось много где, но алгоритма не было. Поэтому решил создать тему по этому поводу.

Задача звучит так:
Есть точки Start,Finish типа point. Есть набор препятствий, заданных, допустим, в массиве

Код

walls   : array[0..n] of point;
          {point = record
            x,y = integer;
            end;}

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

Код

route  : array[0..m] of point;

так, что бы выполнялись следующие условия:
1) Если взять route[i] (i<m), то точка route[i+1] должна находиться сверху, снизу, справа или слева;
2) Никакая точка из массива route не совпадает ни с одной точкой из массива walls;
3) Пусть кол-во значимых точек в массиве равно length. Тогда должно выполняться условие: route[length-1] = finish, если такого достичь не возможно, то lenght=0;
4) Lenght было бы наименьшим возможным.

Хотелось бы хотя бы образного алгоритма, по которому программа была бы очевидна. Заранее спасибо.

[Altair]

Алгоритм поиска кратчайшего пути

И зачем велосипед изобретать?
Флойд или Дейктру.
Все дело в представлении графа.
Все твои условияможно эмулировать правильным заданием графа.

[virt]

поищи алгоритм A* там где он есть там должно быть много подобных алгоритмов. Где искать ,да хоть на gamedev.ru.

[Archon]

Блин, игроманию читать надо...

http://www.igromania.ru/articles/?89_samopal1

Сообщение отредактировано: Archon - 10.06.2005 12:59