|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
В сети есть алгоритмы для поиска кратчайшего пути между точками, которые отлично работают пока на поле нет препятствий, т.к. пытаются соединить точки напрямую. Если же на поле препятствия есть, то тут есть вероятность удачного исхода, если путь можно построить так, чтоб препятствие обойти, но чаще алгоритм просто падает. На примере ниже данные алгоритмы не сработают, т.к. прямой видимости между верхними точками нет. Хотелось бы алгоритм, который сам бы обошел препятствие сверху или снизу (где оптимальней по расстоянию). Но нагуглить что-то подобное не получилось. Или вот такой вариант: две двери. В данном случае напрашивается вход через одну дверь, а выход через другую. Вобщем нужен алгоритм в возможностью трассировки, а не просто прямого соединения. В играх вроде есть что-то такое. Подскажите что гуглить. Мои запросы приводят все к тем же алгоритмам прямого соединения :( Зы. как итог нужно соединить все точки замкнутым кольцевым путем, без пересечений с самим собой. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2019, 11:19 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
iskatelsqlкак итог нужно соединить все точки замкнутым кольцевым путем, без пересечений с самим собой. Модифицированный алгоритм волны, например. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2019, 12:53 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2019, 13:02 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
alex55555, m7m Про волновой алгоритм я читал - но везде, где я его встречал он был между двумя точками. У меня же этих точек бывает под две сотни. Причем сначала пройтись алгоритмом поиска кратчайшего пути без препятствий и найти последовательность, потом волновым попарно - не получится. Я пробовал отключать "препятствия". Путь рисовался красивый, вот только вручную его потом растащить вокруг препятствий не получилось - образовывались петли. Нужен такой алгоритм, который будет сразу знать о всех точках, а не только о двух. Нет ли такого алгоритма, которому можно указать вспомогательные, необязательные точки.? Т.е. Например на первой картинке препятствие можно обойти сверху и снизу. Наставить вспомогательных точек и там и там (да хоть по периметру препятствия) а алгоритм бы знал что зеленые кружки - обязательные точки, а по остальным опционально пробежаться, чтоб путь замкнулся? ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2019, 13:43 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
iskatelsql, тебе совершенно правильно сказали про волновой алгоритм. В общем случае - это алгоритм Дейкстры для произвольного графа. И точки по которым ходит волна вовсе не обязаны быть квадратной сеткой. Они могут быть произвольными выпуклыми полигонами. По поводу твоего желания ходить в одну дверь а выходить в другую или ходить по кругу. Это делается элементарно. Ты просто маршрут разбиваешь на части в соотвенствии с замыслом. На 3 под-маршрута. И ставишь промежуточные точки прямо в дверях. Другого способа скорее всего не существует. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2019, 13:49 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
mayton, Скажи, а этот алгоритм подойдет для моей задачи? На обычном компьютере за разумное время отработает? У меня всего около тысячи точек, десятки препятствий. Из этих точек выбираются определенные (пока было от 18 до 190 штук). Ну и соответственно между ними нужен кольцевой путь, обходящий препятствия. Т.к. я заранее не знаю какие точки будут выбраны, специальных вспомогательных заранее расставить не могу. (да и нелегко это на таком объеме) ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2019, 14:07 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
Подойдет. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2019, 14:17 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
iskatelsql Зы. как итог нужно соединить все точки замкнутым кольцевым путем, без пересечений с самим собой. Гамильтонов цикл? iskatelsqlВобщем нужен алгоритм в возможностью трассировки, а не просто прямого соединения. В играх вроде есть что-то такое. Подскажите что гуглить. Мои запросы приводят все к тем же алгоритмам прямого соединения :( Алгоритмы прямого соединения? Что это? ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2019, 22:20 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
SashaMercury, Это то, что ты написал в первом комменте :( ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2019, 22:22 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
Гамильтонов цикл здеь непричем. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2019, 22:29 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
iskatelsqlSashaMercury, Это то, что ты написал в первом комменте :( Что-то не встречал я такого термина в контексте графов. Вы бы все-таки более подробно описали с какими структурами данных вы работаете ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2019, 22:29 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
SashaMercury, Автокад. Есть координаты точек, есть координаты областей. 2Д. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2019, 22:35 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
maytonГамильтонов цикл здеь непричем. Это мне или ему? Остановился на 2opt. Препятствия ставил как бесконечное расстояние. Это работало, когда было какими точками обойти препятствие, но если есть хоть одна непроходимость - приехали. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2019, 22:51 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
Сделай наоборот: добавь углы препятствий в качестве узлов графа. Потом любой алгоритм поиска кратчайшего пути найдёт тебе оптимальную траекторию. ... |
|||
:
Нравится:
Не нравится:
|
|||
26.02.2019, 14:32 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
В играх наподобие StarCraft и Age Of Empires поле - квадратная сетка с ячейками. Так проще дизайнить. И алгоритмы волны работают быстро. А плавность движения персонажей на поворотах - иммитация. Поэтому и дом с двумя дверями можно просто бить на квадратную сетку и не парится. ... |
|||
:
Нравится:
Не нравится:
|
|||
26.02.2019, 14:34 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov, Так что-то вроде я и хотел... Только вот какой алгоритм работает так, что можно указать какие точки обязательные, а какие нет? Те, что я нашел, проходят обязательно по всем точкам. Т.е. если добавить углы он по ним пойдет, даже если этого не нужно ... |
|||
:
Нравится:
Не нравится:
|
|||
26.02.2019, 14:36 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
maytonПоэтому и дом с двумя дверями можно просто бить на квадратную сетку и не парится. Чтоб было понятнее - это точки на реальной карте. И вполне себе реальные препятствия в виде зданий, заборов, и остальных непроходимостей. Конкретно этот кусок примерно 1 на 2,5 километра. Мне не кажется простым бить его на квадраты... Если только автоматически, на квадраты где-то 30х30 сантиметров (чтоб дорогу шириной в метр не пропустить) а потом проверить, препятствие в квадрате или нет... но это получится 27'773'889 квадратов примерно. Даже стремно начинать в этом направлении. ... |
|||
:
Нравится:
Не нравится:
|
|||
26.02.2019, 14:57 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
iskatelsqlmaytonПоэтому и дом с двумя дверями можно просто бить на квадратную сетку и не парится. Чтоб было понятнее - это точки на реальной карте. И вполне себе реальные препятствия в виде зданий, заборов, и остальных непроходимостей. Конкретно этот кусок примерно 1 на 2,5 километра. Мне не кажется простым бить его на квадраты... Если только автоматически, на квадраты где-то 30х30 сантиметров (чтоб дорогу шириной в метр не пропустить) а потом проверить, препятствие в квадрате или нет... но это получится 27'773'889 квадратов примерно. Даже стремно начинать в этом направлении. Погугли fintank. Чувак разбил поле на мелкие квадратики 2 на 2 мильярда или более. И памяти хватило. Как - это его know-how. ... |
|||
:
Нравится:
Не нравится:
|
|||
26.02.2019, 15:24 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
maytonПогугли fintank. Чувак разбил поле на мелкие квадратики 2 на 2 мильярда или более. И памяти хватило. Как - это его know-how.Я в свое время в институте делал крестики-нолики на поле 65к*65к, игра по сети. Но там делалось примитивно, поле билось на ячейки 16*16 клеток (каждая такая ячейка занимала 16*32 бит), и ячейки тупо динамически подгружались при необходимости. Сколько препод ни пытался, больше чем что-то вроде ~10мб программа так и не скушала, хотя это java со свингом была... ... |
|||
:
Нравится:
Не нравится:
|
|||
26.02.2019, 20:28 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
iskatelsqlТолько вот какой алгоритм работает так, что можно указать какие точки обязательные, а какие нет? Те, что я нашел, проходят обязательно по всем точкам. Т.е. если добавить углы он по ним пойдет, даже если этого не нужно Прямой путь будет короче пути по углам, так что они отпадут автоматически. Тот же Форд-Фалкерсон влёт перебирает пути в графе с тысячами рёбер, можешь пока не париться о быстродействии. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2019, 14:47 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
А если ты говоришь о маршруте патрулирования (обхода точек), то там просто (любым способом) задаёшь реперные точки, обязательные к посещению, а уже потом последовательно ищешь кратчайшие пути между ними. Это задача коммивояжера. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2019, 14:51 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov, Ну я так и делаю... Ты суть проблемы не понял. Если есть препятствия (которые я задаю как расстояния бесконечной длины) алгоритм не работает. Не находит путь. Вот как эта задача коммивояжера отработает например на первой картинке? Зря чтоль я их рисовал :) ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2019, 14:55 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
Посмотрел еще раз https://fintank.ru/game/ Со старта меня рандомно выбрасывает в поле (прибл) к координатами (1 200 000, 1 200 000). Рискну предположить что это центр поля. Тогда получается что у него примерно 2.5 на 2.5 миллиона ячеек. Каждая из которых имеет много состояний. Возможно 1 байт. Итого получается что фин-танки должны потреблять порядка 6 250 000 000 000 байт или 6 терабайт оперативы. Но я убежден что автор фин-танка был хитер и замутил структуру данных которая хранит меньше. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2019, 15:03 |
|
Вопрос к игроделам по поиску пути
|
|||
---|---|---|---|
#18+
iskatelsqlDimitry Sibiryakov, Ну я так и делаю... Ты суть проблемы не понял. Если есть препятствия (которые я задаю как расстояния бесконечной длины) алгоритм не работает. Не находит путь. Вот как эта задача коммивояжера отработает например на первой картинке? Зря чтоль я их рисовал :)пропусти, задачу коммивояжера на таком объёме не решить ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2019, 18:45 |
|
|
start [/forum/topic.php?fid=16&fpage=11&tid=1339985]: |
0ms |
get settings: |
11ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
68ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
58ms |
get tp. blocked users: |
1ms |
others: | 258ms |
total: | 432ms |
0 / 0 |