powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вопрос к игроделам по поиску пути
25 сообщений из 29, страница 1 из 2
Вопрос к игроделам по поиску пути
    #39778687
iskatelsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В сети есть алгоритмы для поиска кратчайшего пути между точками, которые отлично работают пока на поле нет препятствий, т.к. пытаются соединить точки напрямую. Если же на поле препятствия есть, то тут есть вероятность удачного исхода, если путь можно построить так, чтоб препятствие обойти, но чаще алгоритм просто падает.

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



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



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

Зы. как итог нужно соединить все точки замкнутым кольцевым путем, без пересечений с самим собой.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39778744
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
iskatelsqlкак итог нужно соединить все точки замкнутым кольцевым путем, без пересечений с самим собой.
Модифицированный алгоритм волны, например.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39778753
m7m
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39778780
iskatelsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alex55555, m7m

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

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

Нет ли такого алгоритма, которому можно указать вспомогательные, необязательные точки.? Т.е. Например на первой картинке препятствие можно обойти сверху и снизу. Наставить вспомогательных точек и там и там (да хоть по периметру препятствия) а алгоритм бы знал что зеленые кружки - обязательные точки, а по остальным опционально пробежаться, чтоб путь замкнулся?
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39778790
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
iskatelsql, тебе совершенно правильно сказали про волновой алгоритм. В общем случае - это алгоритм Дейкстры
для произвольного графа. И точки по которым ходит волна вовсе не обязаны быть квадратной сеткой. Они могут
быть произвольными выпуклыми полигонами.

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

Другого способа скорее всего не существует.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39778804
iskatelsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

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

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

Т.к. я заранее не знаю какие точки будут выбраны, специальных вспомогательных заранее расставить не могу. (да и нелегко это на таком объеме)
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39778810
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Подойдет.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779034
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
iskatelsql
Зы. как итог нужно соединить все точки замкнутым кольцевым путем, без пересечений с самим собой.

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

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

Алгоритмы прямого соединения? Что это?
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779037
iskatelsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

Это то, что ты написал в первом комменте :(
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779042
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Гамильтонов цикл здеь непричем.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779043
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
iskatelsqlSashaMercury,

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

Что-то не встречал я такого термина в контексте графов. Вы бы все-таки более подробно описали с какими структурами данных вы работаете
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779048
iskatelsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

Автокад. Есть координаты точек, есть координаты областей. 2Д.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779055
iskatelsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonГамильтонов цикл здеь непричем.

Это мне или ему?
Остановился на 2opt. Препятствия ставил как бесконечное расстояние. Это работало, когда было какими точками обойти препятствие, но если есть хоть одна непроходимость - приехали.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779331
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сделай наоборот: добавь углы препятствий в качестве узлов графа. Потом любой алгоритм поиска кратчайшего пути найдёт тебе оптимальную траекторию.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779333
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В играх наподобие StarCraft и Age Of Empires поле - квадратная сетка с ячейками.
Так проще дизайнить. И алгоритмы волны работают быстро. А плавность движения
персонажей на поворотах - иммитация. Поэтому и дом с двумя дверями можно просто
бить на квадратную сетку и не парится.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779336
iskatelsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,

Так что-то вроде я и хотел... Только вот какой алгоритм работает так, что можно указать какие точки обязательные, а какие нет? Те, что я нашел, проходят обязательно по всем точкам. Т.е. если добавить углы он по ним пойдет, даже если этого не нужно
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779347
iskatelsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПоэтому и дом с двумя дверями можно просто
бить на квадратную сетку и не парится.

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

Если только автоматически, на квадраты где-то 30х30 сантиметров (чтоб дорогу шириной в метр не пропустить) а потом проверить, препятствие в квадрате или нет... но это получится 27'773'889 квадратов примерно. Даже стремно начинать в этом направлении.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779370
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
iskatelsqlmaytonПоэтому и дом с двумя дверями можно просто
бить на квадратную сетку и не парится.

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

Если только автоматически, на квадраты где-то 30х30 сантиметров (чтоб дорогу шириной в метр не пропустить) а потом проверить, препятствие в квадрате или нет... но это получится 27'773'889 квадратов примерно. Даже стремно начинать в этом направлении.
Погугли fintank. Чувак разбил поле на мелкие квадратики 2 на 2 мильярда или более.
И памяти хватило. Как - это его know-how.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779516
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПогугли fintank. Чувак разбил поле на мелкие квадратики 2 на 2 мильярда или более.
И памяти хватило. Как - это его know-how.Я в свое время в институте делал крестики-нолики на поле 65к*65к, игра по сети.
Но там делалось примитивно, поле билось на ячейки 16*16 клеток (каждая такая ячейка занимала 16*32 бит), и ячейки тупо динамически подгружались при необходимости. Сколько препод ни пытался, больше чем что-то вроде ~10мб программа так и не скушала, хотя это java со свингом была...
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779864
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
iskatelsqlТолько вот какой алгоритм работает так, что можно указать какие точки обязательные, а какие нет? Те, что я нашел, проходят обязательно по всем точкам. Т.е. если добавить углы он по ним пойдет, даже если этого не нужно
Прямой путь будет короче пути по углам, так что они отпадут автоматически. Тот же Форд-Фалкерсон влёт перебирает пути в графе с тысячами рёбер, можешь пока не париться о быстродействии.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779868
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А если ты говоришь о маршруте патрулирования (обхода точек), то там просто (любым способом) задаёшь реперные точки, обязательные к посещению, а уже потом последовательно ищешь кратчайшие пути между ними. Это задача коммивояжера.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779874
iskatelsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,

Ну я так и делаю... Ты суть проблемы не понял. Если есть препятствия (которые я задаю как расстояния бесконечной длины) алгоритм не работает. Не находит путь. Вот как эта задача коммивояжера отработает например на первой картинке? Зря чтоль я их рисовал :)
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39779879
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Посмотрел еще раз https://fintank.ru/game/

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

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

Но я убежден что автор фин-танка был хитер и замутил структуру данных которая хранит меньше.
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39780046
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
iskatelsqlDimitry Sibiryakov,

Ну я так и делаю... Ты суть проблемы не понял. Если есть препятствия (которые я задаю как расстояния бесконечной длины) алгоритм не работает. Не находит путь. Вот как эта задача коммивояжера отработает например на первой картинке? Зря чтоль я их рисовал :)пропусти, задачу коммивояжера на таком объёме не решить
...
Рейтинг: 0 / 0
Вопрос к игроделам по поиску пути
    #39780048
iskatelsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

Алгоритмом 2opt вполне решается. Не хватает трассировки, как в навигаторе :)
...
Рейтинг: 0 / 0
25 сообщений из 29, страница 1 из 2
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вопрос к игроделам по поиску пути
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]