Автор: Дож 14.05.2005 0:04
Это обсуждалось много где, но алгоритма не было. Поэтому решил создать тему по этому поводу.
Задача звучит так:
Есть точки 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 14.05.2005 1:06
Цитата
Алгоритм поиска кратчайшего пути
И зачем велосипед изобретать?
Флойд или Дейктру.
Все дело в представлении графа.
Все твои условияможно эмулировать правильным заданием графа.
Автор: virt 15.05.2005 11:48
поищи алгоритм A* там где он есть там должно быть много подобных алгоритмов. Где искать ,да хоть на gamedev.ru.
Автор: Archon 10.06.2005 16:50
Блин, игроманию читать надо...
http://www.igromania.ru/articles/?89_samopal1