| Гость |
Вы не зарегистрированны? Нажмите здесь для регистрации.
Забыли пароль? Запросите новый здесь.
|
|
| Сейчас на сайте |
Гостей: 25
На сайте нет зарегистрированных пользователей
Пользователей: 1,790
новичок: Durved
|
|
|
| Обсуждение «Кратчайшее расстояние между регионами.» |
|
| Опубликовано 19.09.2012 21:04 (12 лет назад) # |
Коллеги, алгоритмический вопрос.
Есть два региона произвольной формы, заданные множеством точек на плоскости (массив W на H из единиц, в котором есть два региона, заполненные нулями).
Требуется найти кратчайшее расстояние между этими регионами.
На данный момент, мне не придумалось ничего умнее, чем последовательный перебор и вычисление расстояния между точками (каждой к каждой). Соответственно, это требует РазмерРегиона1 х РезмерРегиона2 операций нахождения расстояния.
Что вы можете посоветовать из более оптимальных решений в данном случае? |
|
|
|
|
| Опубликовано 19.09.2012 22:17 (12 лет назад) # |
Что такое регион?
Как считается расстояние?
Если ты сверлишь коридоры между комнатами, то для них совсем необязательно чтобы они были как можно более короткими. Более того, сверление самых коротких путей приводит к предсказуемости лабиринта.
редакция от bsivko, 19.09.2012 22:21 |
|
|
|
|
| Опубликовано 19.09.2012 22:47 (12 лет назад) # |
Пускаем волну от одной из форм, пока волна не достигнет какой-либо точки.
Пуская волну, мы отмечаем все соседние точки для текущей волны — точками следующей волны (первая волна - тело первой формы), назначая им цену — расстояние: обычное в +1 и +1.4 с небольшим для клетки по-диагонали + собственную цену (цена суммируется с ценой точки, которая пускает волну).
Если две точки смотрят на одну и ту же — выбирается меньшая цена. Если точка оказалась серой, цена серой клетки — кратчайшее расстояние. (На картинке 3.8 не точно, т.к. юзал +1.4 по диагонали).
Но. Тут имеют место сравнение клеток, а не расстояний меж ними. Пускать волну надо из формы с меньшим количеством клеток. Возможно, алгоритм стоит доработать. |
|
|
|
|
| Опубликовано 20.09.2012 01:11 (12 лет назад) # |
bsivko написал:
Что такое регион?
http://igdc.ru/forum/viewthread.php?forum_id=14&thread_id=464&rowstart=77
Как считается расстояние?
Сумма квадратов.
Если ты сверлишь коридоры между комнатами, то для них совсем необязательно чтобы они были как можно более короткими. Более того, сверление самых коротких путей приводит к предсказуемости лабиринта.
Суть в том, что:
Чем короче просверл, тем более естественным по виду его проще сделать.
Чем короче просверл, тем более он управляем, в плане точек соеденения или расположения, скажем, дверей и ключей.
Кроме того, никакой предсказуемости не получается. Всё получается прекрасно, только медленно :) |
|
|
|
|
| Опубликовано 20.09.2012 01:16 (12 лет назад) # |
Dj_smart написал:
Пускаем волну от одной из форм, пока волна не достигнет какой-либо точки.
...
Тут имеют место сравнение клеток, а не расстояний меж ними. Пускать волну надо из формы с меньшим количеством клеток. Возможно, алгоритм стоит доработать. Мысль интересная. Главное достоинство в том, что так можно найти еще и ближайший регион (если их несколько). Надо будет подумать, что из этого можно выжать, спасибо за идею.
Сам, пока ехал с работы, придумал другой вариант. На этапе формирования регионов, записывать их границы - т.е. клетки, которые соприкасаются со стенками. А потом сравнивать расстояния не между всеми клетками каждого региона, а только между граничными. Скорость должна вырасти в несколько раз.
редакция от Shirson, 20.09.2012 01:17 |
|
|
|
|
| Опубликовано 20.09.2012 02:13 (12 лет назад) # |
| Реализовал вариант с "бордюрным" поиском. Скорость подпрыгнула в 6 раз. |
|
|
|
[35].jpg)
|
| Опубликовано 20.09.2012 04:05 (12 лет назад) # |
| Shirson, если колличество крайних точек региона не измеряется в тысячах то перебор должен делаться довольно быстро (и колличество итераций будет не n точек одного * m точек другого, а (n * m) / 2 при правильном написании алгоритма) и ищи не расстояния а квадраты расстояния (это на всякий случай если ты так ещё не делаешь). если расстояние между регионами обычно не большое то используй алгоритм как Dj_smart предложил, только пускай волны изо всех регионов сразу. |
|
|
|
|
| Опубликовано 20.09.2012 04:29 (12 лет назад) # |
На счёт (n * m) / 2 - а как делать перебор, чтобы так вышло?
Дистанции я считаю как сумму квадратов (выше написал)
редакция от Shirson, 20.09.2012 04:51 |
|
|
|
|
| Опубликовано 20.09.2012 06:07 (12 лет назад) # |
| извеняюсь тут я немного напутал, это работает только когда перебираем точки из одного множества...
редакция от Dan, 20.09.2012 06:12 |
|
|
|
Инженер‑космогоник
|
| Опубликовано 20.09.2012 06:35 (12 лет назад) # |
| Помимо "бордюрного" поиска можно использовать еще несколько оптимизаций - выкидывать из списка отдельные точки, делать предварительный поиск по x + y а не sqrt(x^2 + y^2)(и вообще выкинуть корень). |
|
|
|
|
| Опубликовано 20.09.2012 08:19 (12 лет назад) # |
Shirson написал:
(выше написал)
слуш, ты говорил, что у тебя на карту расставляется несколько так называемых "центров", от которых потом расширяется уровень, так?
если так, то не очевидно разве, что кратчайшее расстояние скорее всего лежит на линии, соединяющей центры этих зон? |
|
|
|
|
| Опубликовано 20.09.2012 10:20 (12 лет назад) # |
Замкнутая область (секретка) относится к региону?
Чем регион отличается от комнаты?
Shirson написал:
Если ты сверлишь коридоры между комнатами, то для них совсем необязательно чтобы они были как можно более короткими. Более того, сверление самых коротких путей приводит к предсказуемости лабиринта.
Суть в том, что:
Чем короче просверл, тем более естественным по виду его проще сделать.
Чем короче просверл, тем более он управляем, в плане точек соеденения или расположения, скажем, дверей и ключей.
Кроме того, никакой предсказуемости не получается. Всё получается прекрасно, только медленно :)
Эти условия не требуют, чтобы просверл был самым коротким. Если алгоритм будет быстро находить просверлы, которые например не превышают 10% от оптимального, то такого решения окажется вполне достаточно.
Shirson написал:
Как считается расстояние?
Сумма квадратов.
Данное условие, плюс непримеримое желание сделать именно оптимум ставят крест на алгоритме волны, предложенного Dj_smart'ом (ака велосипед Shirson'a под названием "алгоритм выпуклой оболочки").
Пример:
Здесь сумма квадратов отличается от результата, который дает волна.
Волна: AB меньше BC. Квадраты: AB больше BC.
Ещё один момент. Возможно для игры нужны только горизонтальные/вертикальные(/диагональные) коридоры. Поэтому может сначала попробовать эвристики по разным вариантам, а потом уже искать оптимальные алгоритмы.
редакция от bsivko, 20.09.2012 12:51 |
|
|
|
|
| Опубликовано 20.09.2012 11:06 (12 лет назад) # |
bsivko написал:
Ещё один момент. Возможно для игры нужны только горизонтальные/вертикальные коридоры.
Тогда имеет смысл гуглить по запросу: roguelike level generating
или типа того. Там есть и свежие мысли. |
|
|
|
|
| Опубликовано 20.09.2012 13:40 (12 лет назад) # |
можно заюзать kd-дерево за O(n*logn + m*sqrt(n)) в худшем случае или O(n*logn + m*log(n)) в среднем
ну это что сразу в голову пришло
можно попробовать подобрать структуру данных попроще, сейчас подумаю
upd. ошибся в сложности, поправил
редакция от rip, 20.09.2012 14:15 |
|
|
|
|
| Опубликовано 20.09.2012 13:59 (12 лет назад) # |
Dan:
извеняюсь тут я немного напутал, это работает только когда перебираем точки из одного множества...
Я тоже сначала себя по лбу хлопнул - Ну как же, можно же в половину меньше! А когда взялся делать, понял, что для двух множеств такое не прокатит. Но ты мог знать секретную формулу :) Жаль.
Mefistofel:
Помимо "бордюрного" поиска можно использовать еще несколько оптимизаций - выкидывать из списка отдельные точки, делать предварительный поиск по x + y а не sqrt(x^2 + y^2)(и вообще выкинуть корень).
А по какому принципу выкидывать точки?
Корни я и так не использую, работаю просто с квадратами.
RichDad:
слуш, ты говорил, что у тебя на карту расставляется несколько так называемых "центров", от которых потом расширяется уровень, так?
Нигде и никогда я такого не говорил :) Даже ничего подобного или похожего не говорил :)
У меня используется
1й шаг - шумовой генератор.
2й шаг (несколько итераций) фрактальный зуум
3й шаг (несколько итераций) шумоподавление
4й шаг - пост-обработка (вроде удаления стен, касающихся друг друга только по диагонали) |
|
|
|
|
| Опубликовано 20.09.2012 14:05 (12 лет назад) # |
RichDad:
Тогда имеет смысл гуглить по запросу: roguelike level generating
или типа того. Там есть и свежие мысли.
Ты не повершь, но я с этого начинаю :) А когда перепробую всё, перепробую кучу и не найду решения, тогда спрашиваю на форуме ;)
Да, такие люди бывают, те что сначала гуглят, а потом спрашивают, а не наоборот :) |
|
|
|
|
| Опубликовано 20.09.2012 14:30 (12 лет назад) # |
bsivko:
Замкнутая область (секретка) относится к региону?
Конечно.
Чем регион отличается от комнаты?
Ничем. В данном случае, это синонимы. Я задавал вопрос в общей теме, и взял термин "регион", чтобы с первого же поста не объяснять, что такое "комната".
Эти условия не требуют, чтобы просверл был самым коротким. Если алгоритм будет быстро находить просверлы, которые например не превышают 10% от оптимального, то такого решения окажется вполне достаточно.
Тут больше вопроса, чем ответов.
Почему именно 10%?
Как понять, что за "оптимальная длина"? Откуда её можно вычислить, если форма регионов, их размеры и количество - произвольны? Произвольны, это всмсле совсем произвольны. Может быть один регион, может быть двадцать. Они могут быть в виде кругов, окружностей, полумесяцев, клакс и чего угодно. Они могут быть один внутри другого.
Если сверлить с произвольного места одного региона, до произвольного места другого, такой штрек может пересечь свой же регион несколько раз.
Он может "мусорно" зацепить друго регион, это когда получается щель по диагонали, совершенно ненужная на практике.
Проблема в том, что это нарушает удобную последовательность соединения регионов, при которой можно правильно рассполагать двери и ключи к ним.
Плюс, опять же, повторюсь, это каверны, а не корридоры административного здания. Просверлы должны выглядить естественно. Сейчас они даже без постобработки выглядят вполне естественно, а прямолинейный свищ на пол-уровня будет выглядить ужасно.
Данное условие, плюс непримеримое желание сделать именно оптимум ставят крест на алгоритме волны, предложенного Dj_smart'ом
Какое еще условие? Ты спросил, как считается расстояния, я тебе ответил. Почему ты решил, что это условие?
И что не так с попыткой найти оптимальный по скорости аглоритм?
(ака велосипед Shirson'a под названием "алгоритм выпуклой оболочки"). А поиск заливов то тут причём? И что в ним не так?
bsivko, с тебя негатив что-то прёт просто фонтаном. Я, проде, ничего плохого тебе не говорил, в постах никакого криминала нет. Но ты явно чем-то недоволен.
Здесь сумма квадратов отличается от результата, который дает волна.
Волна: AB меньше BC. Квадраты: AB больше BC. Ну и что - пусть отличается, почему ты на этом внимание заострил? Потому что решил, что я хочу считать только суммой квадратов? Я немогу назвать причину, почему ты так решил.
Ещё один момент. Возможно для игры нужны только горизонтальные/вертикальные(/диагональные) коридоры. Поэтому может сначала попробовать эвристики по разным вариантам, а потом уже искать оптимальные алгоритмы. Опять же, я в карту уровня втыкал с неделю, когда время выдавалось, прикидывая разные варианты соединения регионов. И по центрам регионов, как на прямую, так и по "кварталам" (те самые прямы корридоры), и общее соединение в центре уровня и еще кучу всяких вариантов. Вчера мне пришла в голову последовательное соединение ближайших регионов по ближайшим точкам. Реализация дала великолепные результаты, главный минус - долго считается. Я чпросил совета, как это сделать быстрее. Вот толькои всего :) |
|
|
|
|
| Опубликовано 20.09.2012 15:22 (12 лет назад) # |
Я так и не понял.
Ты хочешь соединить секретки с основным регионом? Или это будут проходы между частями одного региона (внутри то есть)? |
|
|
|
|
| Опубликовано 20.09.2012 15:23 (12 лет назад) # |
Shirson написал:
Реализовал вариант с "бордюрным" поиском. Скорость подпрыгнула в 6 раз.
Код "бордюрного поиска" покажешь? :) я, порой, код понимаю лучше, чем собеседника. |
|
|
|
|
| Опубликовано 20.09.2012 15:25 (12 лет назад) # |
В данном случае, это синонимы.
Ок. Теперь предельно понятно.
Как понять, что за "оптимальная длина"? Откуда её можно вычислить, если форма регионов, их размеры и количество - произвольны?
Разница между вычислением с помощью волны от всего региона и наименьшим расстоянием по прямой между двумя точками составляет менее (sqrt(2)+1)/sqrt(5) - 1 (там более хитрая формула, но это одна из близких верхних оценок), а это менее 8%.
Плюс, опять же, повторюсь, это каверны, а не корридоры административного здания. Просверлы должны выглядить естественно. Сейчас они даже без постобработки выглядят вполне естественно, а прямолинейный свищ на пол-уровня будет выглядить ужасно.
Свищи на полуровня даже не рассматриваю, и любые алгоритмы, к ним приводящие - тоже.
Ещё, насколько я себя помню в настоящих кавернах, там просверлы от рек и прочих не прямые.
Посверлы кстати при некоторых реализациях могут самопересекаться. В том числе в этих:
Вчера мне пришла в голову последовательное соединение ближайших регионов по ближайшим точкам.
Ты спросил, как считается расстояния, я тебе ответил. Почему ты решил, что это условие?
В названии темы и в первом сообщении написано, что требуется найти найкратчайшее расстояние.
Расстояние может считаться по-разному. В связи с этим и уточнение.
Но ты явно чем-то недоволен.
Всем доволен. С заливами все отлично. Просто там использовались подобные кирпичи для стройки.
Я немогу назвать причину, почему ты так решил.
Потому что обладаю свойством вьедливости. И не умею считать "какие-нибудь расстояния" в "каких-нибудь регионах" и писать все подряд методом "накидания всегочтоприходитвголову от того, что написал автор".
Насколько все понял, требуется найкратчайшее правдоподобное расстояние для пользователя. Не важно, Пифагор, max(dx, dy), min(dx+dy) или ещё что.
Бордюрный поиск можно значительно ускорить засчет интерполяции. Фактически, расстояния каждого бордюра к каждому - это функция от двух переменных - на выходе плоскость. В этой плоскости надо найти минимум. Особенность в том, что точки плоскости не могут мгновенно изменять свое значение, а только на 1 или sqrt(2) максимум (смотря как бордюр построен, без диагоналей или с).
Быстро кодится оптимизация, когда например считается в этой плоскости каждая например 5-я точка с каждой 5-й (точки выстроены вдоль бордюра). Находится минимум X. Все ребра, которые не получили X+10 (или X+10*sqrt(2)), выкидываются из выборки. Остальное - градиентный спуск. В итоге - профит в 5*5 раз.
редакция от bsivko, 20.09.2012 15:38 |
|
|
|
Перейти на форум:
|
|
|
|
| Конкурсы |
|
Открытые конкурсы:
|
|
|