Пуск рек на карте высот

[den]

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

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

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

(чуть позже будут скрины демо (js же!) с отбраковкой, если получится)

[dsd]

я пытался делать так:
на каждой точке карты 1 капля
потом даю течь каплям к самой нижней из соседних точек, при каждом перемещении капли в новую клетку делаю в специальной карте +1 к этой точке. Потом рисую только те у которых набежавший счетчик больше какого то методом тыка подбираемого числа. Тоже ниче так выходит

[den]

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

UPD: часто ли у вас получаются ну уж совсем не правдоподобные карты?

[Reizel]

манки?

[den]

Сообщение от Reizel

манки?

чистый js)

[Nerd]

Эта река какая-то неправильная.

[den]

[impersonalis]

минус градиент?

[den]

Сообщение от impersonalis

минус градиент?

была идея заюзать, но как его посчитать для произвольной поверхности?
я только для заданной формулой умею

[moka]

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

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

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

Удобно делать демки в JS - дал ссылку, и затестили.

[impersonalis]

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

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

Upd: поправил термниологию

[den]

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

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

Далее даём каплям течь.....

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

Для каждой точки вычисляется минус сопротивление...

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

[dsd]

Сообщение от 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;
    }

}