Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Вопрос к игроделам по поиску пути  [new]
iskatelsql
Member

Откуда:
Сообщений: 783
В сети есть алгоритмы для поиска кратчайшего пути между точками, которые отлично работают пока на поле нет препятствий, т.к. пытаются соединить точки напрямую. Если же на поле препятствия есть, то тут есть вероятность удачного исхода, если путь можно построить так, чтоб препятствие обойти, но чаще алгоритм просто падает.

На примере ниже данные алгоритмы не сработают, т.к. прямой видимости между верхними точками нет. Хотелось бы алгоритм, который сам бы обошел препятствие сверху или снизу (где оптимальней по расстоянию). Но нагуглить что-то подобное не получилось.

Картинка с другого сайта.

Или вот такой вариант: две двери. В данном случае напрашивается вход через одну дверь, а выход через другую.

Картинка с другого сайта.

Вобщем нужен алгоритм в возможностью трассировки, а не просто прямого соединения. В играх вроде есть что-то такое. Подскажите что гуглить. Мои запросы приводят все к тем же алгоритмам прямого соединения :(

Зы. как итог нужно соединить все точки замкнутым кольцевым путем, без пересечений с самим собой.
25 фев 19, 11:19    [21818536]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
alex55555
Member

Откуда:
Сообщений: 2095
iskatelsql
как итог нужно соединить все точки замкнутым кольцевым путем, без пересечений с самим собой.

Модифицированный алгоритм волны, например.
25 фев 19, 12:53    [21818646]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
m7m
Member

Откуда: Украина, Мариуполь
Сообщений: 1322
iskatelsql,

Волновой алгоритм
25 фев 19, 13:02    [21818658]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
iskatelsql
Member

Откуда:
Сообщений: 783
alex55555, m7m

Про волновой алгоритм я читал - но везде, где я его встречал он был между двумя точками. У меня же этих точек бывает под две сотни.

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

Нет ли такого алгоритма, которому можно указать вспомогательные, необязательные точки.? Т.е. Например на первой картинке препятствие можно обойти сверху и снизу. Наставить вспомогательных точек и там и там (да хоть по периметру препятствия) а алгоритм бы знал что зеленые кружки - обязательные точки, а по остальным опционально пробежаться, чтоб путь замкнулся?
25 фев 19, 13:43    [21818702]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
iskatelsql, тебе совершенно правильно сказали про волновой алгоритм. В общем случае - это алгоритм Дейкстры
для произвольного графа. И точки по которым ходит волна вовсе не обязаны быть квадратной сеткой. Они могут
быть произвольными выпуклыми полигонами.

По поводу твоего желания ходить в одну дверь а выходить в другую или ходить по кругу. Это делается элементарно. Ты просто
маршрут разбиваешь на части в соотвенствии с замыслом. На 3 под-маршрута. И ставишь промежуточные точки прямо в дверях.

Другого способа скорее всего не существует.
25 фев 19, 13:49    [21818714]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
iskatelsql
Member

Откуда:
Сообщений: 783
mayton,

Скажи, а этот алгоритм подойдет для моей задачи? На обычном компьютере за разумное время отработает?

У меня всего около тысячи точек, десятки препятствий. Из этих точек выбираются определенные (пока было от 18 до 190 штук). Ну и соответственно между ними нужен кольцевой путь, обходящий препятствия.

Т.к. я заранее не знаю какие точки будут выбраны, специальных вспомогательных заранее расставить не могу. (да и нелегко это на таком объеме)
25 фев 19, 14:07    [21818736]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Подойдет.
25 фев 19, 14:17    [21818743]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2647
iskatelsql

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


Гамильтонов цикл?

iskatelsql
Вобщем нужен алгоритм в возможностью трассировки, а не просто прямого соединения. В играх вроде есть что-то такое. Подскажите что гуглить. Мои запросы приводят все к тем же алгоритмам прямого соединения :(


Алгоритмы прямого соединения? Что это?
25 фев 19, 22:20    [21819202]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
iskatelsql
Member

Откуда:
Сообщений: 783
SashaMercury,

Это то, что ты написал в первом комменте :(
25 фев 19, 22:22    [21819207]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Гамильтонов цикл здеь непричем.
25 фев 19, 22:29    [21819212]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2647
iskatelsql
SashaMercury,

Это то, что ты написал в первом комменте :(


Что-то не встречал я такого термина в контексте графов. Вы бы все-таки более подробно описали с какими структурами данных вы работаете
25 фев 19, 22:29    [21819213]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
iskatelsql
Member

Откуда:
Сообщений: 783
SashaMercury,

Автокад. Есть координаты точек, есть координаты областей. 2Д.
25 фев 19, 22:35    [21819220]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
iskatelsql
Member

Откуда:
Сообщений: 783
mayton
Гамильтонов цикл здеь непричем.


Это мне или ему?
Остановился на 2opt. Препятствия ставил как бесконечное расстояние. Это работало, когда было какими точками обойти препятствие, но если есть хоть одна непроходимость - приехали.
25 фев 19, 22:51    [21819228]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47390
Сделай наоборот: добавь углы препятствий в качестве узлов графа. Потом любой алгоритм поиска кратчайшего пути найдёт тебе оптимальную траекторию.
26 фев 19, 14:32    [21819760]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
В играх наподобие StarCraft и Age Of Empires поле - квадратная сетка с ячейками.
Так проще дизайнить. И алгоритмы волны работают быстро. А плавность движения
персонажей на поворотах - иммитация. Поэтому и дом с двумя дверями можно просто
бить на квадратную сетку и не парится.
26 фев 19, 14:34    [21819766]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
iskatelsql
Member

Откуда:
Сообщений: 783
Dimitry Sibiryakov,

Так что-то вроде я и хотел... Только вот какой алгоритм работает так, что можно указать какие точки обязательные, а какие нет? Те, что я нашел, проходят обязательно по всем точкам. Т.е. если добавить углы он по ним пойдет, даже если этого не нужно
26 фев 19, 14:36    [21819772]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
iskatelsql
Member

Откуда:
Сообщений: 783
mayton
Поэтому и дом с двумя дверями можно просто
бить на квадратную сетку и не парится.


Чтоб было понятнее - это точки на реальной карте. И вполне себе реальные препятствия в виде зданий, заборов, и остальных непроходимостей. Конкретно этот кусок примерно 1 на 2,5 километра. Мне не кажется простым бить его на квадраты...

Если только автоматически, на квадраты где-то 30х30 сантиметров (чтоб дорогу шириной в метр не пропустить) а потом проверить, препятствие в квадрате или нет... но это получится 27'773'889 квадратов примерно. Даже стремно начинать в этом направлении.
26 фев 19, 14:57    [21819812]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
iskatelsql
mayton
Поэтому и дом с двумя дверями можно просто
бить на квадратную сетку и не парится.


Чтоб было понятнее - это точки на реальной карте. И вполне себе реальные препятствия в виде зданий, заборов, и остальных непроходимостей. Конкретно этот кусок примерно 1 на 2,5 километра. Мне не кажется простым бить его на квадраты...

Если только автоматически, на квадраты где-то 30х30 сантиметров (чтоб дорогу шириной в метр не пропустить) а потом проверить, препятствие в квадрате или нет... но это получится 27'773'889 квадратов примерно. Даже стремно начинать в этом направлении.

Погугли fintank. Чувак разбил поле на мелкие квадратики 2 на 2 мильярда или более.
И памяти хватило. Как - это его know-how.
26 фев 19, 15:24    [21819845]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 56546
mayton
Погугли fintank. Чувак разбил поле на мелкие квадратики 2 на 2 мильярда или более.
И памяти хватило. Как - это его know-how.
Я в свое время в институте делал крестики-нолики на поле 65к*65к, игра по сети.
Но там делалось примитивно, поле билось на ячейки 16*16 клеток (каждая такая ячейка занимала 16*32 бит), и ячейки тупо динамически подгружались при необходимости. Сколько препод ни пытался, больше чем что-то вроде ~10мб программа так и не скушала, хотя это java со свингом была...
26 фев 19, 20:28    [21820055]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47390
iskatelsql
Только вот какой алгоритм работает так, что можно указать какие точки обязательные, а какие нет? Те, что я нашел, проходят обязательно по всем точкам. Т.е. если добавить углы он по ним пойдет, даже если этого не нужно

Прямой путь будет короче пути по углам, так что они отпадут автоматически. Тот же Форд-Фалкерсон влёт перебирает пути в графе с тысячами рёбер, можешь пока не париться о быстродействии.
27 фев 19, 14:47    [21820642]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47390
А если ты говоришь о маршруте патрулирования (обхода точек), то там просто (любым способом) задаёшь реперные точки, обязательные к посещению, а уже потом последовательно ищешь кратчайшие пути между ними. Это задача коммивояжера.
27 фев 19, 14:51    [21820652]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
iskatelsql
Member

Откуда:
Сообщений: 783
Dimitry Sibiryakov,

Ну я так и делаю... Ты суть проблемы не понял. Если есть препятствия (которые я задаю как расстояния бесконечной длины) алгоритм не работает. Не находит путь. Вот как эта задача коммивояжера отработает например на первой картинке? Зря чтоль я их рисовал :)
27 фев 19, 14:55    [21820664]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Посмотрел еще раз https://fintank.ru/game/

Со старта меня рандомно выбрасывает в поле (прибл) к координатами (1 200 000, 1 200 000).
Рискну предположить что это центр поля. Тогда получается что у него примерно 2.5 на 2.5 миллиона
ячеек. Каждая из которых имеет много состояний. Возможно 1 байт.

Итого получается что фин-танки должны потреблять порядка 6 250 000 000 000 байт или 6
терабайт оперативы.

Но я убежден что автор фин-танка был хитер и замутил структуру данных которая хранит меньше.
27 фев 19, 15:03    [21820676]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
iskatelsql
Dimitry Sibiryakov,

Ну я так и делаю... Ты суть проблемы не понял. Если есть препятствия (которые я задаю как расстояния бесконечной длины) алгоритм не работает. Не находит путь. Вот как эта задача коммивояжера отработает например на первой картинке? Зря чтоль я их рисовал :)
пропусти, задачу коммивояжера на таком объёме не решить
27 фев 19, 18:45    [21821001]     Ответить | Цитировать Сообщить модератору
 Re: Вопрос к игроделам по поиску пути  [new]
iskatelsql
Member

Откуда:
Сообщений: 783
kealon(Ruslan),

Алгоритмом 2opt вполне решается. Не хватает трассировки, как в навигаторе :)
27 фев 19, 18:48    [21821005]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Программирование Ответить