forum.boolean.name - Пуск рек на карте высот

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - Пуск рек на карте высот (http://forum.boolean.name/showthread.php?t=18624)

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

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

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

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

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

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

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

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

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

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

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

Цитата:

Сообщение от Reizel (Сообщение 268797)

манки?

чистый js)

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

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

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

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

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

Цитата:

Сообщение от impersonalis (Сообщение 268998)

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

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

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

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

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

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

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

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

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

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

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

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

Цитата:

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

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

Цитата:

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

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

Цитата:

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

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

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

Цитата:

Сообщение от Den (Сообщение 269055)

ну вот с каплями и со скрином.

Цитата:

Сообщение от dsd (Сообщение 254703)

какая то фигня при отрисовке в текстуру напоминающая реки.
довольно шустрая для карты 1024х1024

PHP код:


		
			
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;

    }



}