Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.75
taras atavin
4204 / 1763 / 212
Регистрация: 24.11.2009
Сообщений: 27,565
#1

Просчёт путей - Алгоритмы

16.12.2009, 05:02. Просмотров 1078. Ответов 9
Метки нет (Все метки)

Нужен просчёт путей в трехмерном пространстве. Препятствия делятся на два класса: проходимые и не проходимые. Через проходимые препятсвия можно пройти, но при их прохождении:
1. должен постянно работать главный двигатель, даже если это космос (плотные туманности, оказывающие сопротивление движению)
http://www.cyberforum.ru/algorithms/thread1897170.html
2. ограничена скорость
3. ограничена манёвренность
4. ограничены ускорения.
Не проходимые препятсвия абсолюно не проницаемы. Причём, препятсвия обоих классов могут быть и не выпуклыми. Нужен выбор оптимального пути. Дайте хотябы идею алгоритма. Модераторы, если я запостил не туда, снесите пожалуйста в игры но не удаляйте.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.12.2009, 05:02
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Просчёт путей (Алгоритмы):

поиск путей на графе
поиск путей на графе дан ориентированый граф из 2-50 вершин, где каждому...

Алгоритм поиска путей
Привет. Ребята, такая тема, у меня есть граф, взвешенный, неориентированный, у...

Хранение маршрутов (путей графа) в БД
Что-то без поллитры не соображу как хранить маршруты в базе данных. Маршрут...

ищу алгоритм поиска путей
http://www.codewars.com/kata/paths-in-the-grid Представим, что нам дают...

Экономное представление путей в графе
Есть приведенное бинарное дерево (изоморфные подграфы сливаются, в узла может...

9
TanT
эволюционирую потихоньку
467 / 465 / 91
Регистрация: 30.06.2009
Сообщений: 1,399
16.12.2009, 05:39 #2
цель движения какая? -> пройти путь максимально быстро?

ограничение на время расчёта есть?
если на время нет заморочек, то можно пербором вариантов попробовать, трёмерное пространство конечно вносит свои сложности, но по сути это всё тот же поиск пути в лабиринте, таких задач на форуме много уже обсуждалось
0
taras atavin
4204 / 1763 / 212
Регистрация: 24.11.2009
Сообщений: 27,565
16.12.2009, 11:58  [ТС] #3
Два варианта цели в зависимости от параметра:
1. Максимально быстро, но с ограниченным расходом топлива.
2. С минимальным расходом топлива, но за ограниченное время.
Время расчёта важнее времени прохождения в 180 раз. Сложность трехмерного пространства в необозримости числа вариантов. Особенно при отношении размеров пространства и координатного шага порядка 2^144, а у меня итменно этот вариант. И на маршруте надо ещё запланировать несколько посадок для дозаправки.
0
TanT
эволюционирую потихоньку
467 / 465 / 91
Регистрация: 30.06.2009
Сообщений: 1,399
16.12.2009, 13:06 #4
поясните про шаг
и номер варианта, какой именно у вас не очевидно

перебор всех вариантов в вашем случае, действительно не целесообразен.
однако, если исходит из физики космического пространсва, основная часть трёхмерного пространства должна быть свободна, что вероятно облегчит задачу.
так или иначе уточните
1. какой из вариантов вам нужен.
2. Заполненность пространства препятствиями
3. количество дозаправок
4. как понимать "координатного шага порядка 2^144,"
что-нить придумаем
0
taras atavin
4204 / 1763 / 212
Регистрация: 24.11.2009
Сообщений: 27,565
17.12.2009, 06:44  [ТС] #5
1. Оба. Выбор фактическим параметром при вызове функции. От раза к разу выбор меняется. В режиме патрулирования минимизируется расход топлива, в режиме атаки - время.
2. В космосе менее 1%. На планетах есть как пустыни, так и города и даже пещеры и в этом пространстве тоже надо двигаться и выбирать траекторию. Кпроме того, предположим и игрок, и противник находятся в туманности объёмом в один кубический парсек вблизи её центра на расстоянии в несколько триллионов километров. Тогда можешь считать что вокруг сплошное препятствие.
3. Пропорционально расстоянию. Ограничение задаётся в виде "не более n на мегапарсек при максимальной дальности с одной заправки d килопарсек).
4. Координаты известны очень точно и минимальный шаг изменения любой координаты есть 1/2^144 размера пространства по этой же оси. То есть, например, при миллиметровом разрешении имеем куб 2^144*2^144*2^144 мм. Таким образом, даже матрицу проходимости нет возможности ни целиком разметстить в памяти компьютера (даже долговременной) ни в обозримое время заполнить в любом формате, не ориентированном на сжатое предстваление разреженных матриц.
0
TanT
эволюционирую потихоньку
467 / 465 / 91
Регистрация: 30.06.2009
Сообщений: 1,399
17.12.2009, 08:54 #6
прочитал, самопроизвольно вырвалось - "ёптеть".
1. ситуация моделируется для очень различных ситуаций (космос, пустыни, города и даже пещеры)
2. "шаг изменения любой координаты есть 1/2^144 размера" - это ж нафига такая точность?
в каком виде у вас предствлена карта?

Таким образом, даже матрицу проходимости нет возможности ни целиком разметстить в памяти компьютера (даже долговременной) ни в обозримое время заполнить в любом формате, не ориентированном на сжатое предстваление разреженных матриц.
вот именно, а всякое сжатие ведёт к потери точности

как предложение
1. ограничивать вероятные маршруты некоторым объёмным телом, сужат область поиска вариантов, и уже работат с ограниченным числом точек, а не с всей картой.
2. строить различные алгоритмы поиска путей для различных сред. универсального скорее всего не будет. точнее универсального, отвечающего всем требованиям

Добавлено через 14 минут
по алгоритмы приходит в голову некоторая аналогия с распрастранение солнечных лучей (это про движение в космосе).
если направить лампу на стену и на стене, не жалее обоев, нарисовать точку, то кратчайшее растояние от источника света до точки это прямая. теперь, если перед лампой поместить помеху, то точка на стене будет в тени. и кратчайшее растояние до неё (считаем преграду не преодолимой) это два отрезка: первый от лампы до края преграды, второй от края преграды до точки на стене. количество вариантов ограниченно точками контура препятсвия. найти минимальный путь в этом случае просто. аналогично можно увеличивать количество препятствий, там возникают разные ситуации с размером препятствий, но это рещаемое.
для проходимых препятствий вводит затраты времени и анализировать суммарный путь с учётом этих затрат.
0
taras atavin
4204 / 1763 / 212
Регистрация: 24.11.2009
Сообщений: 27,565
17.12.2009, 10:28  [ТС] #7
вот именно, а всякое сжатие ведёт к потери точности
Не ведёт. Путота, она путота и есть, скольбы кубических парсек в ней ни было.
1. ограничивать вероятные маршруты некоторым объёмным телом, сужат область поиска вариантов, и уже работат с ограниченным числом точек, а не с всей картой.
Как?
2. строить различные алгоритмы поиска путей для различных сред. универсального скорее всего не будет. точнее универсального, отвечающего всем требованиям
Допустим. Исходная точка в городе, точка назначения в подводной пещере на другой планете, комодром в другом городе, дороги нет, надо пересечь или пустыню или горы, или болото. Каким образом спланировать путь, если нет универсального, пусть даже смешанного циклически-ветвящегося алгоритма?
в каком виде у вас предствлена карта?
Да просто в навал дискрипторы всех препятствий.
по алгоритмы приходит в голову некоторая аналогия с распрастранение солнечных лучей (это про движение в космосе).
если направить лампу на стену и на стене, не жалее обоев, нарисовать точку, то кратчайшее растояние от источника света до точки это прямая. теперь, если перед лампой поместить помеху, то точка на стене будет в тени. и кратчайшее растояние до неё (считаем преграду не преодолимой) это два отрезка: первый от лампы до края преграды, второй от края преграды до точки на стене. количество вариантов ограниченно точками контура препятсвия. найти минимальный путь в этом случае просто. аналогично можно увеличивать количество препятствий, там возникают разные ситуации с размером препятствий, но это рещаемое. для проходимых препятствий вводит затраты времени и анализировать суммарный путь с учётом этих затрат.
По-русски я это понимаю и когда выбираю траекторию сам, то выбираю квазиоптимально. Мне надо, чтоб монстры не были пьяными, а тоже могли планировать свои действия, в том числе, движение.
0
TanT
эволюционирую потихоньку
467 / 465 / 91
Регистрация: 30.06.2009
Сообщений: 1,399
17.12.2009, 12:25 #8
Допустим. Исходная точка в городе, точка назначения в подводной пещере на другой планете, комодром в другом городе, дороги нет, надо пересечь или пустыню или горы, или болото. Каким образом спланировать путь, если нет универсального, пусть даже смешанного циклически-ветвящегося алгоритма?
тут не так ты меня понял, я не говорил про разбиение областей. скажем в городе алгоритм/механизм выбора один, в космосе другой, общий путь будет собран из результата всех решений.

в общем я по обыкновению пользуюсь следующим алгоритмом:
1. движемся прямок к цели пока не стретили препятствие.
2. выбираем любой путь к обходу этого препятсвия, остальные возможные варианты в стек(буфер).
3. снова п.1, если достигли точки и время в пути меньше имеющегося, запомнили время затраченное на движение. и этот путь, переходим к п.4
4. выбираем вариант из вершины стека и п.1, пока стек не пуст

но так как дело не на плоскости и вариантов будет много, даже слишком, то моэно ввести упрощения:
1. выбирать несколько (а не все возможные пути). пути выбирать по миниму затраченного времени для огибания препятствия.
2. останавливать расчёт путей у которых в процессе расчёта величина времени превосходит текущее оптимальное значение
3. может чего ещё
1
taras atavin
4204 / 1763 / 212
Регистрация: 24.11.2009
Сообщений: 27,565
18.12.2009, 05:35  [ТС] #9
Цитата Сообщение от TanT Посмотреть сообщение
тут не так ты меня понял, я не говорил про разбиение областей. скажем в городе алгоритм/механизм выбора один, в космосе другой, общий путь будет собран из результата всех решений.
А разве алгоритм, умеющий их собирать в одно общее, а для получения кусочных решений выбирать и вызывать алгоритмы для конкретных сред, не будет универсальм алгоритмом?
0
TanT
эволюционирую потихоньку
467 / 465 / 91
Регистрация: 30.06.2009
Сообщений: 1,399
18.12.2009, 10:36 #10
Цитата Сообщение от taras atavin Посмотреть сообщение
А разве алгоритм, умеющий их собирать в одно общее, а для получения кусочных решений выбирать и вызывать алгоритмы для конкретных сред, не будет универсальм алгоритмом?
я бы назвал его сборным или общим, ты можешь называть его как угодно.
как точнее назвать алгоритм вопрос уже больше риторики.
0
18.12.2009, 10:36
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.12.2009, 10:36
Привет! Вот еще темы с решениями:

Нахождение количества кратчайших путей
собственно, то задачка: Шпиону требуется пробраться из одной клетки лабиринта...

Логическая задача на количество путей
Робот может двигаться только вправо и вниз на одну клетку. В клетки,...

Поиск нескольких кратчайших путей в графе
Добрый день всем! Такая казалось бы тривиальная задача для гуру программистов,...

Алгоритм Флойда-Уоршелла [для нахождения кратчайших путей]
Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru