Правила форума
Алгоритм поиска кратчайшего пути, движение персонажей в RPG играх
Задача звучит так:
Есть точки Start,Finish типа point. Есть набор препятствий, заданных, допустим, в массиве
Код
walls : array[0..n] of point;
{point = record
x,y = integer;
end;}
{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 было бы наименьшим возможным.
Хотелось бы хотя бы образного алгоритма, по которому программа была бы очевидна. Заранее спасибо.
