Навигация
Поддержать материально
Steam Greenlight

Логотипы
Медальки
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Темы форума
185 - RPG
9.02.2024
 Vaskrol
В каком банке открыт…
24.01.2024
 Darthman
185 - ?
30.12.2023
 Mefistofel
TESTAMENT - Тактичес…
15.11.2023
 KregHek
WoL
13.10.2023
 Darthman
RES - Движок для пик…
27.09.2023
 rimush
177 - One Button Str…
20.09.2023
 VoroneTZ
JS 13k contest
13.09.2023
 Mefistofel
184 - Arcade II
14.08.2023
 tiger1025
184 - ?
14.07.2023
 Kaps
Сейчас на сайте
Гостей: 1
На сайте нет зарегистрированных пользователей

Пользователей: 1,787
новичок: vovasmirnov198
Обсуждение «Кратчайшее расстояние между регионами.»
Страница 2 из 2 < 1 2
Shirson
Avatar пользователя

Опубликовано 20.09.2012 16:05 (12 лет назад)    #
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, 20.09.2012 16:08

bsivko
Avatar пользователя

Опубликовано 20.09.2012 16:58 (12 лет назад)    #
Это, наверное, замечательно, но... ну и что? :) Какая разница, какая между ними разница?

Разница в 8% (;

Т.е. если мы ищем найкратчайшее, то можем его не найти. Но зато найдем расстояние, которое не будет отличаться от найкратчайшего более чем на 8%. Например для генерации уровня игры это скорее всего будет более чем достаточно. А в жизни могут оказаться задачи, для которых этого будет недостаточно.

Свищи на полуровня даже не рассматриваю, и любые алгоритмы, к ним приводящие - тоже.


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

г/в/д коридоры необязательно пилить на полуровня, чтобы соединить все.
или я опять чего-то не понимаю в диалоге

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

Только что провел мат. док-во для точек, а не регионов с тем же свойством. В результате ранее придуманные контрпримеры рассыпались.

Скорее всего да, никак не могут.

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

Не понимаю, как это можно понять по другому.

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

Есть два множества точек бордюров: A и B.

1. Представим их в виде двух упорядоченных массивов (C И D). В массивах присутствуют все точки множества, но при этом расстояние между двумя любыми C(i) и C(i+1) не превышает 1 (или sqrt(2)), тжс для D.
Другими словами, точки в массивах идут так, как они идут "вдоль" бордюра на плоскости.

2. Находим все расстояния между каждой пятой точкой C и D. С(0), С(5), С(10), ... и D(0), .., D(5), .. D(10), ... Всего N(C)*N(D)/25 расстояний R(i, j).

3. Выбираем из них минимальное MIN. Из множества найденных расстояний выкидываем все, которые больше (MIN + 10)
или (MIN + 10*sqrt(2)), если бордюр построен с использованием диагоналей минуя в некоторых точках горизонтали и вертикали.

4. Остается малое количество пар R(i, j). Искомое расстояние где-то рядом с ними. Где-то тут R(i-5..i+5, j-5..j+5).

5. Это можно перебрать в лоб (100 расстояний), а можно применить градиентный спуск:
а. +-1 по i и j, это расчет 8 расстояний, итерация с перемещением.
б. повторять (а) пока не будет найдено (тут не более 4 раз).

---
5-ку взял интуитивно исходя из картинок уровней. возможно подойдет и 3, и 10. Это от форм уровня зависит и оптимум по скорости ищется экспериментально.

редакция от bsivko, 20.09.2012 17:07

RichDad
Avatar пользователя

Опубликовано 20.09.2012 17:01 (12 лет назад)    #
Shirson написал:
Дело в том, что ты не видил результат реализации

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

Опубликовано 20.09.2012 17:04 (12 лет назад)    #
А ты покажи. Мы ж не по телефону общаемся. Выкладывай что у тебя там и что ты хочешь получить.

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

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

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

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

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

Опубликовано 20.09.2012 17:08 (12 лет назад)    #
bsivko написал:
А ты покажи. Мы ж не по телефону общаемся. Выкладывай что у тебя там и что ты хочешь получить.

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

PrintScreen еще никто не отменял. Ширсон говорит у него есть рабочий, но медленный вариант. Вот пусть покажет результат.
bsivko
Avatar пользователя

Опубликовано 20.09.2012 17:13 (12 лет назад)    #
RichDad написал:
bsivko написал:
1. Представим их в виде двух упорядоченных массивов (C И D).
2. Находим все расстояния между каждой пятой точкой C и D.

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

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

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

Это не гарантирует требуемого результата.

Выбрав зоны любым образом и приняв решение, ты отсекаешь 3/4 решений, и нет гарантии, что среди них есть правильное.

Например ты взял 4 зоны-точки и получил 4 приблизительно равных числа. Выбрав любое из них, ты отбрасываешь 3/4 решений, а среди них может оказаться оптимальное. Например какая-нибудь выпуклость, не попавшая в 4 точки зон.
Shirson
Avatar пользователя

Опубликовано 20.09.2012 17:20 (12 лет назад)    #
Это реоптимизированный бордюрный алгоритм, без пост-обработки (нет специальных шагов по приданию просверлов "естественного" вида. Время генерации конкретно этого уровня на слабом компе порядка 47 мс (время колеблется от 16 до 47 мс). Примерно в 18-20 раз быстрее изначального варианта, при котором я стартовал топик.

Тут было восемь или девять разных комнат.

редакция от Shirson, 20.09.2012 18:41

Zer0
Avatar пользователя

Опубликовано 20.09.2012 18:55 (12 лет назад)    #
Я просто оставлю это здесь:
http://www.codersnotes.com/notes/signed-distance-fields
Из

Делает

редакция от Zer0, 20.09.2012 18:56

Dan
Avatar пользователя

Опубликовано 20.09.2012 19:06 (12 лет назад)    #
Zer0 это примерно то что предлагал DJ_smart только более обобщенно
RichDad
Avatar пользователя

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

Для генерации уровня все значения меньше полсекунды приемлемы, ИМХО.
MysticCoder
Avatar пользователя

Опубликовано 21.09.2012 08:34 (12 лет назад)    #
И вообще, можно все что надо загружать/вычислять в фоне, пока игрок в главном меню ковыряется, генерируется десяток карт.
Если главное это быстрота, то могу предложить вычислять среднюю точку каждого региона и выбирать в каждом бордюре ближайшую точку к средней соседнего региона, их и соединять. Должно корректно работать на выпуклых регионах, на невыпуклых скорее всего будет не совсем корректно работать, но зато разнообразие))

редакция от MysticCoder, 21.09.2012 08:37

Zer0
Avatar пользователя

Опубликовано 21.09.2012 10:52 (12 лет назад)    #
Dan написал:
Zer0 это примерно то что предлагал DJ_smart только более обобщенно


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

Опубликовано 21.09.2012 14:18 (12 лет назад)    #
CoderInTank написал:
И вообще, можно все что надо загружать/вычислять в фоне, пока игрок в главном меню ковыряется, генерируется десяток карт.
Это может решить текущую, сиюсекундную, ситуацию, но в будущем такой номер не прокатит. Потом будет понятно почему.

Если главное это быстрота, то могу предложить вычислять среднюю точку каждого региона и выбирать в каждом бордюре ближайшую точку к средней соседнего региона, их и соединять.
Этот вариант я обдумывал, как один из возможных. Результаты будут не очень хорошие, потому, что, повторюсь, регионы могут быть любой формы. И центральная точка может оказаться за три П от региона, с которым должен соединяться текущий. И на пути такого соединений, может оказаться другой регион.

Должно корректно работать на выпуклых регионах, на невыпуклых скорее всего будет не совсем корректно работать, но зато разнообразие))
Это не разнообразие, это безобразие :)
Страница 2 из 2 < 1 2
Перейти на форум:
Конкурсы
Открытые конкурсы:
Активных нет
Недавние конкурсы:
 185 - RPG XII
 184 - Arcade II
 183 - Novel
 182 - RPG XI
 181 - Pixel Craft 128
 Все конкурсы
Случайная игра
Мини-чат
Вам необходимо залогиниться.

Архив чата

25,320,175 уникальных посетителей

Создано на базе русской версии PHP-Fusion copyright © 2003-2006 by Nick Jones.
Released as free software under the terms of the GNU/GPL license.