Применяем градиентный спуск на реальной Земле

[DrZlodberg]

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

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

[Rend]

Обычная аналогия для объяснения градиентного спуска такая: человек застрял в горах во время сильного тумана и должен спуститься вниз. Самый логичный способ — осмотреть поверхность вокруг и медленно проложить путь, следуя вниз по склону.

Очень странная аналогия. Для человека выбор максимального градиента (то есть обрыва) закончится фатально.

[alizar]

Для человека выбор максимального градиента (то есть обрыва) закончится фатально.

Ближайшие точки дна обрыва находятся вне видимой области, так что объект «обрыв» не подходит под алгоритм «осмотреть поверхность вокруг».

[BeardedBeaver]

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

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

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

[DrZlodberg]

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

[BeardedBeaver]

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

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

Вообще говоря нахождение локального минимума в этом случае означает формирование озера (если мы говорим о наземном ландшафте и реках, при подводных турбидитных потоках тоже должно быть что-то подобное), так что по уму надо заполнить озеро и «стечь» туда, где должна быть вытекающая из озера река.

[DrZlodberg]

находил тот, который находится гипсометрически ниже других, и дальше шел в этом направлении

У меня немного по другому. Начинал ходить кругами вокруг узла выбирая минимальный. Рано или поздно путь выбирался (или находил глобальный минимум). Разметка оставалась, так что при объединении 2х минимумов можно было считать их одним и обрабатывать так-же.
Про осадконакопление не очень понял. Если есть пусть стока — то в чём проблема?
С озером я не доделал. Предполагалось учитывать, на сколько далеко прорезать и на сколько оно мелкое получилось. А там уже либо резать реку и делать озеро, либо резать и сливать, либо считать его бессточным (локальный глобальный минимум).

[QDeathNick]

Пилите игрушку, а то кроме From Dust ничего не выходило с симуляцией потоков, размытия грунта и наносов осадочных пород.

[DrZlodberg]

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