Отображение карты высоты в виде контуров на основе сетки

У меня есть карта 2D-высоты в следующем формате

06 36 39 42 43 55 ... 
37 40 43 43 45 46 ...
40 43 44 45 46 48 ...
44 44 46 47 48 50 ...
41 44 45 47 48 48 ...
...

И мне нужно перенаправить его в формат контура, основанный на усмешке (так что он может быть затем отображен в спрайты)

. . . . | . . 
. . . . \ . . 
. . . / / . . 
. . . | . . . 
. . . | . . . 
. / - / . . .

Здесь . означает плоскую область, | и - прямые скалы, / и \ углы скалы (каждая из которых представляет две разные возможности).

Я пробовал стандартный подход маршевых квадратов, но обнаружил, что выборка только 3 соседей приводит к довольно большому количеству проблем из-за перегрузки смежных случаев. (Обратите внимание на дополнительные неулокальные прямые скалы ниже)

. . . . | . \ 
. . . . \ \ .
. . . / / - .
. . . | - . .
. . . | . . .
. / - / . . .

Что бы я хотел, это некоторые ссылки на алгоритмы/подходы, которые помогают справиться с такими вещами. Я знаю, что контурная ходьба с каким-то глубинным поиском - это вариант, но еще не опробовал его, и предпочел бы оставить это в качестве крайней меры. Также есть вопросы о представлении некоторых функций, например, следует ли включать в себя клиновые выступы толщиной 1 элемент или просто игнорировать их. Другой вариант - пройти через сгенерированные контуры и изменить их, чтобы они плавно соответствовали друг другу, но это кажется действительно взломанным...

Ответ 1

Создайте функцию интерполяции/наилучшего соответствия. Ваша модель должна быть двумерным многочленом (в x и y), степень которого "правильная": не слишком высокая, чтобы вы переработали все, но не слишком низко, чтобы вы теряли детали.

Теперь у вас есть математическая функция, которую вы можете нарезать, установив f(x,y) = height. Решение этого уравнения является контуром. Теперь у вас есть два варианта, в зависимости от того, сможете ли вы аналитически решить.

Предполагая, что вы не можете аналитически решить, вы все же можете легко проследить приближение кривой:
- Начните с окраски белой сетки, если f(x,y)>height и черный, если f(x,y)<height. Обратите внимание на все "переходные" области, где есть черно-белый переход внутри примерно 1 сетки: это квадраты, в которых будет находиться контур.
- Случайно выберите квадрат перехода и найдите в пределах примерно 1 радиус сетки для f(x,y)==height, чтобы найти точку на контуре. В этот момент (не обязательно на сетке) мы вычисляем градиент ∇f(x,y) = (∂f/∂x, ∂f/∂y) ( "вектор гора" ). Мы поворачиваем его на 90 градусов в любом направлении: (∂f/∂y, -∂f/∂x): этот путь указывает вдоль контура. Мы очень медленно (с размером шага намного меньше, чем сетка) прослеживаем контур. Это приведет нас к контуру вокруг.
- Каждый раз, когда мы проходим через gridbox во время этой трассировки, мы обозначаем его как {|, -,/,} в зависимости от того, какое направление указывает среднее значение градиента. (Мы также должны маркировать соседей как ., если они еще не помечены, см. [& Ast;].)
- Обратите внимание, что после этого могут остаться переходные сетки. Например, если у вас есть два холма, вы заполняете один круг, но контур состоит из двух кругов. Повторите описанную выше процедуру на другом случайном (немеченым) "переходном" сетке (вот почему нам нужно [& ast;], иначе мы могли бы зафиксировать соседние точки, которые мы уже учитывали). Повторяйте до тех пор, пока не появятся более небезопасные "переходные" gridboxes.
- Сделайте это для каждого уровня height, который вы хотите нарисовать как контур, и все готово.
Вы можете аналитически решить, как и для конических разделов, но это, вероятно, вряд ли и выходит за рамки этого вопроса. Если бы вы могли решить эту кривую, вы могли бы "разложить" ее, используя различные методы (например, параметризуйте ее, затем пройдите по контуру, используя размеры шага, возможно, половину сетки, отметив ближайших соседей)

(Если один из ваших контуров перекрывает другой, расстояние между вашими контурными высотами слишком мало. Если вас не устраивает данный контур, набор возможностей {-, |,/,} слишком мал.)