purebasic.info

PureBasic forum
Текущее время: Вт июл 17, 2018 6:01 pm

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
 Заголовок сообщения: Поиск пути по точкам (графу)
СообщениеДобавлено: Чт фев 13, 2014 2:55 pm 
Не в сети
профессор
Аватар пользователя

Зарегистрирован: Пт окт 31, 2008 4:49 pm
Сообщений: 717
Благодарил (а): 1 раз.
Поблагодарили: 4 раз.
Пункты репутации: 0
Хочу сделать элементарный поиск пути в 3Д. Насколько понял, самый простой способ расставить точки, соединить в такую штуку как граф и по нему искать. Нашел в инете разные алгоритмы (Флойда, Дейкстры...), проблема в том, что у меня математика на уровне 5 класа, и я не понимаю о чем там в описании алгоритма народ пишет.
Например:
Цитата:
Задача алгоритма: перезаписать данную матрицу так, чтобы каждая ячейка вместо веса ребра из i в j, содержала кратчайший путь из i в j.

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

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

_________________
мой форум http://spaceminers.mybb2.ru
Dungeon Raider (Ogre). Game video: http://www.youtube.com/watch?v=ZlhBgPJhAxI


Вернуться наверх
 Профиль  
 
 Заголовок сообщения: Re: Поиск пути по точкам (графу)
СообщениеДобавлено: Пт фев 14, 2014 3:27 am 
Не в сети
профессор

Зарегистрирован: Вс июн 10, 2012 8:18 am
Сообщений: 1294
Благодарил (а): 60 раз.
Поблагодарили: 49 раз.
Пункты репутации: 14
AndyLy писал(а):
Хочу сделать элементарный поиск пути в 3Д.

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


Вернуться наверх
 Профиль  
 
 Заголовок сообщения: Re: Поиск пути по точкам (графу)
СообщениеДобавлено: Пт фев 14, 2014 9:23 am 
Не в сети
профессор
Аватар пользователя

Зарегистрирован: Пт окт 31, 2008 4:49 pm
Сообщений: 717
Благодарил (а): 1 раз.
Поблагодарили: 4 раз.
Пункты репутации: 0
В 3Д. Например 1 точка в начале коридора, двигаешься по прямой ко второй, на второй развилка вправо, влево, и вверх. Пошел по прямой к следующей точке вверх- там снова развилка.. В таком духе.
Если есть способ получше и с готовым решением- предлагай, я что-то не могу ничего найти, только глубокомысленные замечания типа поиск в3Д это как в2Д только учитывается 3 измерение.
У меня есть код а* алгоритма для 2Д , но я понятия не имею как его приспособить для 3х измерений.

_________________
мой форум http://spaceminers.mybb2.ru
Dungeon Raider (Ogre). Game video: http://www.youtube.com/watch?v=ZlhBgPJhAxI


Вернуться наверх
 Профиль  
 
 Заголовок сообщения: Re: Поиск пути по точкам (графу)
СообщениеДобавлено: Пт фев 14, 2014 10:31 am 
Не в сети
студент

Зарегистрирован: Пт фев 14, 2014 10:27 am
Сообщений: 3
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Пункты репутации: 0
Не совсем понял задачу, но почему бы не использовать векторы.
В 3D векторы считаються так же как и в 2D, только добовляется еще 1 координата по z-оси.


Вернуться наверх
 Профиль  
 
 Заголовок сообщения: Re: Поиск пути по точкам (графу)
СообщениеДобавлено: Пт фев 14, 2014 5:32 pm 
Не в сети
профессор
Аватар пользователя

Зарегистрирован: Пт окт 31, 2008 4:49 pm
Сообщений: 717
Благодарил (а): 1 раз.
Поблагодарили: 4 раз.
Пункты репутации: 0
Цитата:
только глубокомысленные замечания типа поиск в3Д это как в2Д только учитывается 3 измерение.
:)

_________________
мой форум http://spaceminers.mybb2.ru
Dungeon Raider (Ogre). Game video: http://www.youtube.com/watch?v=ZlhBgPJhAxI


Вернуться наверх
 Профиль  
 
 Заголовок сообщения: Re: Поиск пути по точкам (графу)
СообщениеДобавлено: Пт фев 14, 2014 5:58 pm 
Не в сети
студент

Зарегистрирован: Пт фев 14, 2014 10:27 am
Сообщений: 3
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Пункты репутации: 0
Не понятно, что вам в 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]

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


Вернуться наверх
 Профиль  
 
 Заголовок сообщения: Re: Поиск пути по точкам (графу)
СообщениеДобавлено: Пт фев 14, 2014 6:25 pm 
Не в сети
профессор
Аватар пользователя

Зарегистрирован: Пт окт 31, 2008 4:49 pm
Сообщений: 717
Благодарил (а): 1 раз.
Поблагодарили: 4 раз.
Пункты репутации: 0
Мне нужен поиск кратчайшего пути в 3Д пространстве.

_________________
мой форум http://spaceminers.mybb2.ru
Dungeon Raider (Ogre). Game video: http://www.youtube.com/watch?v=ZlhBgPJhAxI


Вернуться наверх
 Профиль  
 
 Заголовок сообщения: Re: Поиск пути по точкам (графу)
СообщениеДобавлено: Пт фев 14, 2014 6:30 pm 
Не в сети
студент

Зарегистрирован: Пт фев 14, 2014 10:27 am
Сообщений: 3
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Пункты репутации: 0
А кратчайший путь- это разве не прямая линия от А до B?
Если опустить присутстиве преград.


Вернуться наверх
 Профиль  
 
 Заголовок сообщения: Re: Поиск пути по точкам (графу)
СообщениеДобавлено: Пт фев 14, 2014 6:36 pm 
Не в сети
доцент

Зарегистрирован: Сб июл 13, 2013 3:39 pm
Сообщений: 46
Благодарил (а): 10 раз.
Поблагодарили: 3 раз.
Пункты репутации: 0
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 и тд.


Вернуться наверх
 Профиль  
 
Показать сообщения за:  Сортировать по:  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Часовой пояс: UTC + 3 часа


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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group (блог о phpBB)
Сборка создана CMSart Studio
Русская поддержка phpBB