Поиск пути по точкам (графу)

AndyLy · **Добавлено:** Чт фев 13, 2014 2:55 pm

Хочу сделать элементарный поиск пути в 3Д. Насколько понял, самый простой способ расставить точки, соединить в такую штуку как граф и по нему искать. Нашел в инете разные алгоритмы (Флойда, Дейкстры...), проблема в том, что у меня математика на уровне 5 класа, и я не понимаю о чем там в описании алгоритма народ пишет.
Например:

Цитата:

Задача алгоритма: перезаписать данную матрицу так, чтобы каждая ячейка вместо веса ребра из i в j, содержала кратчайший путь из i в j.

Что это значит? Мне нужно, чтобы в результате работы кода я получил список точек описывающих кратчайший путь из 1 в 5, из 1 в 9, и3 3 в 7 ... и т.д.
Кто-нибудь занимался этой проблемой? Можете помочь?

P.s. ссылка на алгоритмы
http://kvodo.ru/algoritm-floyda-uorshella.html

MrF · **Добавлено:** Пт фев 14, 2014 3:27 am

AndyLy писал(а):

Хочу сделать элементарный поиск пути в 3Д.

Поиск пути в 3D - это поиск в трехмерном пространстве, или как в гта(или нфс)? Если последнее, то там двухмерный поиск и делается он как обычно(имхо), только с учетом карты(дороги, препятствия, ландшафт, высота).

AndyLy · **Добавлено:** Пт фев 14, 2014 9:23 am

В 3Д. Например 1 точка в начале коридора, двигаешься по прямой ко второй, на второй развилка вправо, влево, и вверх. Пошел по прямой к следующей точке вверх- там снова развилка.. В таком духе.
Если есть способ получше и с готовым решением- предлагай, я что-то не могу ничего найти, только глубокомысленные замечания типа поиск в3Д это как в2Д только учитывается 3 измерение.
У меня есть код а* алгоритма для 2Д , но я понятия не имею как его приспособить для 3х измерений.

DogIntro · **Добавлено:** Пт фев 14, 2014 10:31 am

Не совсем понял задачу, но почему бы не использовать векторы.
В 3D векторы считаються так же как и в 2D, только добовляется еще 1 координата по z-оси.

AndyLy · **Добавлено:** Пт фев 14, 2014 5:32 pm

Цитата:

только глубокомысленные замечания типа поиск в3Д это как в2Д только учитывается 3 измерение.

DogIntro · **Добавлено:** Пт фев 14, 2014 5:58 pm

Не понятно, что вам в 3D непонятно.

Как ищется путь от точки A до B. Допустим у А координаты (1,1), у B (5,7). Отрезок AB получится [5-1,7-1], итого [4,6].
В 3D точно так же, только вместо двух осей (x,y) у нас уже три (x,y,z).

Допустим A3D (1,2,3), B3D (7,8,9), то путь от А до В [7-1,8-2,9-3]=[6,6,6]

Или вы о другом?

AndyLy · **Добавлено:** Пт фев 14, 2014 6:25 pm

Мне нужен поиск кратчайшего пути в 3Д пространстве.

DogIntro · **Добавлено:** Пт фев 14, 2014 6:30 pm

А кратчайший путь- это разве не прямая линия от А до B?
Если опустить присутстиве преград.

Walt · **Добавлено:** Пт фев 14, 2014 6:36 pm

AndyLy писал(а):

В 3Д. Например 1 точка в начале коридора, двигаешься по прямой ко второй, на второй развилка вправо, влево, и вверх. Пошел по прямой к следующей точке вверх- там снова развилка.. В таком духе.
Если есть способ получше и с готовым решением- предлагай

Получение чего? я чего то не догоняю

, какой движок какой функционал ?? нечего подробно не описал и хочет чтоб дали "готовое решение", в 3д координаты-расстояние-скорость рассчитывается с помощью трассировки-векторов-элементарной математики. ХЗ как это там реализовано в PB на но на сях выгладит примерно так
"зависит от наличия - отсутствия - названия функций"

Код:

1
2
3
4
5
6
 
TargetPos=entity_player():getpos()   //стартовая точка где находится игрок 
EndPos=entity_info_Target():getpos()  //точка к которой двигаться 
Vector=TargetPos-EndPos  //вычисление вектора 
entity_player():setvelocity(Vector*10+Vector) //придать ускорение игроку к указным координатам  
 

Вектор3Д / С++ для начинающих http://www.cyberforum.ru/cpp-beginners/thread363626.html
и ещё прилагаю погуглить по ключевым словам
3d vector - трассировка в 3D - path tracing 3d и тд.

purebasic.info

Поиск пути по точкам (графу)

Кто сейчас на форуме