|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
14.10.2013, 19:43
|
#1
|
Дэвелопер
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений (для 2,419 пользователей)
|
Пуск рек на карте высот
Есть сгенерированная карта высот. Нужно из заданной точки пустить реку.
Моё решение (и как оказалось не только мое):
1) Набросать на карту случайно (но достаточно равномерно) много-много точек. Сразу же определить для каждой точки её соседей.
Как делал я: точки ставятся в виде сетки, потом отодвигаются от своих позиций на небольшую величину.
Находил способ с диаграммой Вороного, но результат лишь немного лучше получается.
2) Берем начальную точку. Задаем при необходимости угол, если необходимо.
Ищем у точки соседей, с высотой меньше чем у данной. Стараясь сохранить угол течения, и течь на более низкую высоту, подбираем оптимальную точку. Опционально: высчитываем новый угол течения.
В 80% случаев результат хороший. В остальных, речка, столкнувшись с возвышенностью может повернуть градусов на 120. Можно заюзать сглаживание ломаной прямой, но тогда река будет теч не там где её сказали. Можно ещё резать каналы в холмах, но это не правдоподобно.
Пока писал понял, что можно просто отбраковывать неугодные реки.
Но всё таки может кто-то сталкивался с такой задачей?
(чуть позже будут скрины демо (js же!) с отбраковкой, если получится)
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо den за это полезное сообщение:
|
|
14.10.2013, 21:05
|
#2
|
Мастер
Регистрация: 13.06.2011
Сообщений: 1,103
Написано 481 полезных сообщений (для 1,836 пользователей)
|
Ответ: Пуск рек на карте высот
я пытался делать так:
на каждой точке карты 1 капля
потом даю течь каплям к самой нижней из соседних точек, при каждом перемещении капли в новую клетку делаю в специальной карте +1 к этой точке. Потом рисую только те у которых набежавший счетчик больше какого то методом тыка подбираемого числа. Тоже ниче так выходит
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
15.10.2013, 01:05
|
#3
|
Дэвелопер
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений (для 2,419 пользователей)
|
Ответ: Пуск рек на карте высот
ДЕМО
Пускается три реки из одних и тех же точек, отбраковываются только те, которые не дошли до океана, или переселись с другой рекой.
Галочка что бы сделать карту ступенчатой, так лучше вроде реки получаются.
Кнопка для обновления.
UPD: часто ли у вас получаются ну уж совсем не правдоподобные карты?
|
(Offline)
|
|
Эти 4 пользователя(ей) сказали Спасибо den за это полезное сообщение:
|
|
15.10.2013, 01:24
|
#4
|
Задрот
Регистрация: 24.07.2009
Адрес: Ивановская область, г. Кинешма
Сообщений: 1,574
Написано 407 полезных сообщений (для 863 пользователей)
|
Ответ: Пуск рек на карте высот
манки?
|
(Offline)
|
|
15.10.2013, 01:30
|
#5
|
Дэвелопер
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений (для 2,419 пользователей)
|
Ответ: Пуск рек на карте высот
Сообщение от Reizel
манки?
|
чистый js)
|
(Offline)
|
|
17.10.2013, 10:38
|
#6
|
Чудо-кот
Регистрация: 22.02.2011
Сообщений: 901
Написано 480 полезных сообщений (для 1,471 пользователей)
|
Ответ: Пуск рек на карте высот
Эта река какая-то неправильная.
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо Nerd за это полезное сообщение:
|
|
17.10.2013, 17:32
|
#7
|
Дэвелопер
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений (для 2,419 пользователей)
|
Ответ: Пуск рек на карте высот
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
17.10.2013, 22:37
|
#8
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Пуск рек на карте высот
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
18.10.2013, 17:42
|
#9
|
Дэвелопер
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений (для 2,419 пользователей)
|
Ответ: Пуск рек на карте высот
Сообщение от impersonalis
|
была идея заюзать, но как его посчитать для произвольной поверхности?
я только для заданной формулой умею
|
(Offline)
|
|
18.10.2013, 18:13
|
#10
|
.
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений (для 6,863 пользователей)
|
Ответ: Пуск рек на карте высот
А можешь сделать с не столь разблуренной картой высот?
Как понимаю сперва мы считаем нормали изходя из карты высот (тот же подход как в нормалях для bump'а в шейдерах). Данные нормелей используются для определения течения.
Далее даём каплям течь. Каждый раз когда капля где-то протекает она увеличивает степень протекаемости зоны по которой течёт.
От степени протекаемости определяется радиус капли.
Радиус капли нужен для определения направления течения, для вытекания при скоплении в одном водоёме. Получается капли текут и могуз застрять в низинке, тогда они там скапливаются тем самым увеличивая количество воды (степень в зоне), и каждый раз пытаются найти вектор вытекания исходя из векторов нормалей в радиусе.
Имхо, нужно пробовать реализовать, но думаю таким образом у нас получяться широкие и менее реки, а также озёра.
Естественно вода также теряет свою степень значимости со временем, т.к. проникает через почву. Что может по сути привезти к озёрам без рек с выходами если степень поглащения достаточно высокая чтобы не дать каплям разливаться.
Удобно делать демки в JS - дал ссылку, и затестили.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
18.10.2013, 23:53
|
#11
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Пуск рек на карте высот
Ну в общем, градиент численно можно реализовать оператором Собеля, например. Но вообще такое решение (градиент) имеет минусы: оно будет выбирать единственное направление русла или всё множество (в случае плато). Лучше опереться на другой подход, минус которого, правда, в тяжести вычислений.
Для каждой точки вычисляется напряжение, как разность между гравитационными потенциалами точек (высотами). Каждая точка порождает потоки во все направления с отрицательными напряжениями (в точки с меньшей высотой), при этом скорость истечения (сила тока воды) распределяется пропорционально модулям напряжений (водопады, пороги, тихие долинные реки) - аналогично закону Ома. В случае попадания в локальный минимум (низину), образуется озеро, а следующей точкой истечения определяется наиболее низкий берег (это будет точка с наименьшим положительным напряжением относительно дна). Можно так же ввести модель сопротивления среды (тип дна) - по аналогии с сопротивлением в электрическом контуре. Управляемые плотины будут аналогом конденсаторов (озёра, с ручной регуляцией входного / выходного потенциала). Насосы, очевидно, будут источниками тока (воды): буду создавать заданную силу тока воды и обладать бесконечным внутренним сопротивлением.
Можно подойти к задаче и со стороны CV: распознать контура на карте высот и от них плясать. С другой стороны, реальное русло ещё зависит от характера земной породы: вымывание грунта, подземные реки и прочее.
Upd: поправил термниологию
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо impersonalis за это полезное сообщение:
|
|
19.10.2013, 00:19
|
#12
|
Дэвелопер
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений (для 2,419 пользователей)
|
Ответ: Пуск рек на карте высот
А можешь сделать с не столь разблуренной картой высот?
|
ну так галочка специально есть, что бы сделать карту ступенчатой.
а сильный блюр получается потому, что используется шум перлина.
Далее даём каплям течь.....
|
У меня была старая реализация с каплями, но это все генерировалось очень долго, а результат выходил не очень. На карте получались тысячи маленьких речушек и озер. Скринов и демок к сожалению не сохранилось, т.к. я посчитал это тупиковой ветвью и забил.
В принципе, если грамотно обработать карту высот (убрать мелкие ямки, округлить горы...) и увеличить масштаб раз эдак в 100, сделать высыхание луж воды, то может и получится, но это очень сложно (как в плане написания (я такое не осилю), так и в плане производительности)
Для каждой точки вычисляется минус сопротивление...
|
ну у меня практически тоже самое сейчас, только скорость потока не учитывается, зато поток старается сохранить прямое направление.
и озера не образуются да, я специально отбраковывал такие реки, следующим шагом как раз будут озера, но позже)
|
(Offline)
|
|
19.10.2013, 01:07
|
#13
|
Мастер
Регистрация: 13.06.2011
Сообщений: 1,103
Написано 481 полезных сообщений (для 1,836 пользователей)
|
Ответ: Пуск рек на карте высот
Сообщение от Den
У меня была старая реализация с каплями, но это все генерировалось очень долго, а результат выходил не очень. На карте получались тысячи маленьких речушек и озер. Скринов и демок к сожалению не сохранилось, т.к. я посчитал это тупиковой ветвью и забил.
|
ну вот с каплями и со скрином.
Сообщение от dsd
какая то фигня при отрисовке в текстуру напоминающая реки.
довольно шустрая для карты 1024х1024
using UnityEngine; using System.Collections; public class CalcRiverbend : MonoBehaviour { public static int width = 1024; //карта высот public static float [,] map = new float [width,width]; //количество воды прошедшей по клетке public static int [,] water = new int [width,width]; //количество воды в клетке public static int [,] waterNumber = new int [width,width]; //кто из соседей клетки самый нижний // значение от 0 до 9 public static byte [,] height = new byte [width,width]; //смещения для воды public static Vector2 [] disp = { new Vector2(-1,-1), new Vector2(-1,0), new Vector2(-1,1), new Vector2(0,-1), new Vector2(0,0), new Vector2(0,1), new Vector2(1,-1), new Vector2(1,0), new Vector2(1,1)}; public static void Init(){ //получение карты высот for(int i = 0; i < width; i++){ for(int j = 0; j < width; j++) { map[i,j] = PerlinNoise.perlin2d(i*0.01f,j*0.01f,0); } } //вычисление самого низкого из ближайших соседей for(int i = 0; i < width; i++){ for(int j = 0; j < width; j++) { height[i,j] = CalcLowest(i,j); } } //теперь сбрасываю на каждую клетку карты по 1 капле воды for(int i = 0; i < width; i++){ for(int j = 0; j < width; j++) { waterNumber[i,j] = 1; } } //а теперь пусть капли текут вниз //заодно считаю для каждой точки сколько капель прошло по ней //повторяю сколько то раз процедуру for(int k = 0; k < 200; k++){ for(int i = 0; i < width; i++){ for(int j = 0; j < width; j++) { //если в точке есть капли if (waterNumber[i,j]>0) { //узнаю в какую из соседей она течет Vector2 displacement = disp[height[i,j]]; //номер ячейки int x0= (int)displacement.x + i, y0 = (int)displacement.y + j; //если точки в границах if(x0>=0 && y0>=0 && x0<width && y0<width){ //перевожу воду куда следует waterNumber[x0,y0] += waterNumber[i,j]; //увеличиваю счетчик воды прошедшей по клетке water[i,j] += waterNumber[i,j]; //убираю утекшую воду waterNumber[i,j] = 0; } } } } } } //вычисляет какое из девяти чисел самое маленькое private static byte CalcLowest(int x, int y){ //пусть нижняя центральная по умолчанию byte result = 4; //создаю массив для значений высот float [] heights = {0f,0f,0f,0f,0f,0f,0f,0f,0f}; //теперь заполняю его значения высот for(int i = -1; i <=1; i++){ for(int j = -1; j <=1; j++) { int x0= x+i, y0 = y+j; if(x0>=0 && y0>=0 && x0<width && y0<width){ heights[(i+1)*3+j+1] = map[x0,y0]; } } } //рисую где находится нижняя точка из текущих 9-ти for(int i = 0; i < heights.Length; i++){ if(heights[result]>heights[i]){result = (byte)i;} } return result; } }
|
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 06:38.
|