bsivko:Разница между вычислением с помощью волны от всего региона и наименьшим расстоянием по прямой между двумя точками составляет менее (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 раз.

Это, наверное, замечательно, но... ну и что? :) Какая разница, какая между ними разница?

Возможно для игры нужны только горизонтальные/вертикальные(/диагональные) коридоры
?

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

Да, надо найти наикратчайшее расстояние. Когда спросили как это считаю я, я ответил что суммой квадратов. Почему ты решил, что это условие?

Не вкурил... Пошагово можешь алгоритм описать?

Shirson написал:
Дело в том, что ты не видил результат реализации

А ты покажи. Мы ж не по телефону общаемся. Выкладывай что у тебя там и что ты хочешь получить.

bsivko написал:
1. Представим их в виде двух упорядоченных массивов (C И D).
2. Находим все расстояния между каждой пятой точкой C и D.

bsivko написал:

Это далеко не всегда возможно. Думаю что Shirson погонял большое количество вариантов и результат находится скорее в его интуиции, чем в картинках.

RichDad написал:

Мн кажется, или ты пытаешься реализовать велосипед деления на 2. :)

То есть делим список (вектор/массив) точек бордюра на 4 зоны (равные), берем середины зон и сравниваем с 4 другими точками другого бордюра.
Выбираем наименьшее расстояние, знаем "зону" в которой были эти точки. Делим зоны снова на 4 и т.д.

Не кажется, что это будет еще на порядок быстрее? Для уровня 256 х 256 это всего 4-5 итераций по 16 сравнений.

Shirson написал:
Время генерации конкретно этого уровня на слабом компе порядка 47 мс (время колеблется от 16 до 47 мс).

Dan написал:
Zer0 это примерно то что предлагал DJ_smart только более обобщенно

CoderInTank написал:
И вообще, можно все что надо загружать/вычислять в фоне, пока игрок в главном меню ковыряется, генерируется десяток карт.

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

Должно корректно работать на выпуклых регионах, на невыпуклых скорее всего будет не совсем корректно работать, но зато разнообразие))