Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 14.10.2013, 19:43   #1
den
Дэвелопер
 
Аватар для den
 
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений
(для 2,419 пользователей)
Пуск рек на карте высот

Есть сгенерированная карта высот. Нужно из заданной точки пустить реку.
Моё решение (и как оказалось не только мое):
1) Набросать на карту случайно (но достаточно равномерно) много-много точек. Сразу же определить для каждой точки её соседей.
Как делал я: точки ставятся в виде сетки, потом отодвигаются от своих позиций на небольшую величину.
Находил способ с диаграммой Вороного, но результат лишь немного лучше получается.
2) Берем начальную точку. Задаем при необходимости угол, если необходимо.
Ищем у точки соседей, с высотой меньше чем у данной. Стараясь сохранить угол течения, и течь на более низкую высоту, подбираем оптимальную точку. Опционально: высчитываем новый угол течения.

В 80% случаев результат хороший. В остальных, речка, столкнувшись с возвышенностью может повернуть градусов на 120. Можно заюзать сглаживание ломаной прямой, но тогда река будет теч не там где её сказали. Можно ещё резать каналы в холмах, но это не правдоподобно.

Пока писал понял, что можно просто отбраковывать неугодные реки.
Но всё таки может кто-то сталкивался с такой задачей?

(чуть позже будут скрины демо (js же!) с отбраковкой, если получится)
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо den за это полезное сообщение:
ABTOMAT (15.10.2013), Mr_F_ (14.10.2013)
Старый 14.10.2013, 21:05   #2
dsd
Мастер
 
Аватар для dsd
 
Регистрация: 13.06.2011
Сообщений: 1,103
Написано 481 полезных сообщений
(для 1,836 пользователей)
Ответ: Пуск рек на карте высот

я пытался делать так:
на каждой точке карты 1 капля
потом даю течь каплям к самой нижней из соседних точек, при каждом перемещении капли в новую клетку делаю в специальной карте +1 к этой точке. Потом рисую только те у которых набежавший счетчик больше какого то методом тыка подбираемого числа. Тоже ниче так выходит
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
den (15.10.2013)
Старый 15.10.2013, 01:05   #3
den
Дэвелопер
 
Аватар для den
 
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений
(для 2,419 пользователей)
Ответ: Пуск рек на карте высот

ДЕМО
Пускается три реки из одних и тех же точек, отбраковываются только те, которые не дошли до океана, или переселись с другой рекой.
Галочка что бы сделать карту ступенчатой, так лучше вроде реки получаются.
Кнопка для обновления.

UPD: часто ли у вас получаются ну уж совсем не правдоподобные карты?
(Offline)
 
Ответить с цитированием
Эти 4 пользователя(ей) сказали Спасибо den за это полезное сообщение:
ABTOMAT (15.10.2013), moka (18.10.2013), Phantom (17.10.2013), Reizel (15.10.2013)
Старый 15.10.2013, 01:24   #4
Reizel
Задрот
 
Аватар для Reizel
 
Регистрация: 24.07.2009
Адрес: Ивановская область, г. Кинешма
Сообщений: 1,574
Написано 407 полезных сообщений
(для 863 пользователей)
Ответ: Пуск рек на карте высот

манки?
(Offline)
 
Ответить с цитированием
Старый 15.10.2013, 01:30   #5
den
Дэвелопер
 
Аватар для den
 
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений
(для 2,419 пользователей)
Ответ: Пуск рек на карте высот

Сообщение от Reizel Посмотреть сообщение
манки?
чистый js)
(Offline)
 
Ответить с цитированием
Старый 17.10.2013, 10:38   #6
Nerd
Чудо-кот
 
Аватар для Nerd
 
Регистрация: 22.02.2011
Сообщений: 901
Написано 480 полезных сообщений
(для 1,471 пользователей)
Ответ: Пуск рек на карте высот


Эта река какая-то неправильная.
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо Nerd за это полезное сообщение:
den (17.10.2013), Phantom (17.10.2013)
Старый 17.10.2013, 17:32   #7
den
Дэвелопер
 
Аватар для den
 
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений
(для 2,419 пользователей)
Ответ: Пуск рек на карте высот


(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
St_AnGer (17.10.2013)
Старый 17.10.2013, 22:37   #8
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: Пуск рек на карте высот

минус градиент?
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Старый 18.10.2013, 17:42   #9
den
Дэвелопер
 
Аватар для den
 
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений
(для 2,419 пользователей)
Ответ: Пуск рек на карте высот

Сообщение от impersonalis Посмотреть сообщение
минус градиент?
была идея заюзать, но как его посчитать для произвольной поверхности?
я только для заданной формулой умею
(Offline)
 
Ответить с цитированием
Старый 18.10.2013, 18:13   #10
moka
.
 
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений
(для 6,863 пользователей)
Ответ: Пуск рек на карте высот

А можешь сделать с не столь разблуренной картой высот?

Как понимаю сперва мы считаем нормали изходя из карты высот (тот же подход как в нормалях для bump'а в шейдерах). Данные нормелей используются для определения течения.
Далее даём каплям течь. Каждый раз когда капля где-то протекает она увеличивает степень протекаемости зоны по которой течёт.
От степени протекаемости определяется радиус капли.
Радиус капли нужен для определения направления течения, для вытекания при скоплении в одном водоёме. Получается капли текут и могуз застрять в низинке, тогда они там скапливаются тем самым увеличивая количество воды (степень в зоне), и каждый раз пытаются найти вектор вытекания исходя из векторов нормалей в радиусе.

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

Удобно делать демки в JS - дал ссылку, и затестили.
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
den (19.10.2013)
Старый 18.10.2013, 23:53   #11
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: Пуск рек на карте высот

Ну в общем, градиент численно можно реализовать оператором Собеля, например.

Но вообще такое решение (градиент) имеет минусы: оно будет выбирать единственное направление русла или всё множество (в случае плато). Лучше опереться на другой подход, минус которого, правда, в тяжести вычислений.
Для каждой точки вычисляется напряжение, как разность между гравитационными потенциалами точек (высотами). Каждая точка порождает потоки во все направления с отрицательными напряжениями (в точки с меньшей высотой), при этом скорость истечения (сила тока воды) распределяется пропорционально модулям напряжений (водопады, пороги, тихие долинные реки) - аналогично закону Ома. В случае попадания в локальный минимум (низину), образуется озеро, а следующей точкой истечения определяется наиболее низкий берег (это будет точка с наименьшим положительным напряжением относительно дна). Можно так же ввести модель сопротивления среды (тип дна) - по аналогии с сопротивлением в электрическом контуре. Управляемые плотины будут аналогом конденсаторов (озёра, с ручной регуляцией входного / выходного потенциала). Насосы, очевидно, будут источниками тока (воды): буду создавать заданную силу тока воды и обладать бесконечным внутренним сопротивлением.
Можно подойти к задаче и со стороны CV: распознать контура на карте высот и от них плясать. С другой стороны, реальное русло ещё зависит от характера земной породы: вымывание грунта, подземные реки и прочее.

Upd: поправил термниологию
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо impersonalis за это полезное сообщение:
den (19.10.2013), SBJoker (19.10.2013)
Старый 19.10.2013, 00:19   #12
den
Дэвелопер
 
Аватар для den
 
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений
(для 2,419 пользователей)
Ответ: Пуск рек на карте высот

А можешь сделать с не столь разблуренной картой высот?
ну так галочка специально есть, что бы сделать карту ступенчатой.
а сильный блюр получается потому, что используется шум перлина.

Далее даём каплям течь.....
У меня была старая реализация с каплями, но это все генерировалось очень долго, а результат выходил не очень. На карте получались тысячи маленьких речушек и озер. Скринов и демок к сожалению не сохранилось, т.к. я посчитал это тупиковой ветвью и забил.
В принципе, если грамотно обработать карту высот (убрать мелкие ямки, округлить горы...) и увеличить масштаб раз эдак в 100, сделать высыхание луж воды, то может и получится, но это очень сложно (как в плане написания (я такое не осилю), так и в плане производительности)

Для каждой точки вычисляется минус сопротивление...
ну у меня практически тоже самое сейчас, только скорость потока не учитывается, зато поток старается сохранить прямое направление.
и озера не образуются да, я специально отбраковывал такие реки, следующим шагом как раз будут озера, но позже)
(Offline)
 
Ответить с цитированием
Старый 19.10.2013, 01:07   #13
dsd
Мастер
 
Аватар для dsd
 
Регистрация: 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 0widthi++){
            for(
int j 0widthj++) {
                
map[i,j] = PerlinNoise.perlin2d(i*0.01f,j*0.01f,0);
            }
        }
        
//вычисление самого низкого из ближайших соседей
        
for(int i 0widthi++){
            for(
int j 0widthj++) {        
                
height[i,j] = CalcLowest(i,j);
            }
        }
        
//теперь сбрасываю на каждую клетку карты по 1 капле воды
        
for(int i 0widthi++){
            for(
int j 0widthj++) {
                
waterNumber[i,j] = 1;
            }
        }
        
//а теперь пусть капли текут вниз
        //заодно считаю для каждой точки сколько капель прошло по ней
        //повторяю сколько то раз процедуру
        
for(int k 0200k++){
            for(
int i 0widthi++){
                for(
int j 0widthj++) {
                    
//если в точке есть капли
                    
if (waterNumber[i,j]>0) {
                        
//узнаю в какую из соседей она течет
                        
Vector2 displacement disp[height[i,j]];
                        
//номер ячейки
                        
int x0= (int)displacement.iy0 = (int)displacement.j;
                        
//если точки в границах
                        
if(x0>=&& y0>=&& 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 xint y){
        
//пусть нижняя центральная по умолчанию
        
byte result 4;
        
//создаю массив для значений высот
        
float [] heights = {0f,0f,0f,0f,0f,0f,0f,0f,0f};
        
//теперь заполняю его значения высот
        
for(int i = -1<=1i++){
            for(
int j = -1<=1j++) {    
                
int x0x+iy0 y+j;
                if(
x0>=&& y0>=&& x0<width && y0<width){
                    
heights[(i+1)*3+j+1] = map[x0,y0];    
                }
            }
        }    
        
//рисую где находится нижняя точка из текущих 9-ти    
        
for(int i 0heights.Lengthi++){
            if(
heights[result]>heights[i]){result = (byte)i;}
        }
        return 
result;
    }


(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
den (19.10.2013)
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 21:02.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com