Алгоритм листов карты

Question

Карта

Я делаю RPG на основе плиток с использованием Javascript, использую перлинные карты высоты шума, затем назначаю тип плиток на основе высоты шума.

Карты заканчиваютсявыглядит примерно так (в виде мини-карты).

У меня есть довольно простой алгоритм, который извлекает значение цвета из каждого пикселя на изображении и преобразует его в целое число (0-5) в зависимости от его положения между (0-255), которое соответствует плитке в словаре мозаики.Этот массив 200x200 затем передается клиенту.

Затем механизм определяет плитки по значениям в массиве и выводит их на холст.Итак, я получаю интересные миры с реалистично выглядящими объектами: горы, моря и т. Д.

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

Это пример того, что пользователь будет видеть на карте, но это не то же местоположение, что показано в окне просмотра выше!

Именно в этом представлении я хочу, чтобы переход произошел.

Алгоритм

Я придумалпростой алгоритм, который будет перемещаться по карте в области просмотра и отображать другое изображение поверх каждой плитки, при условии, что она находится рядом с плиткой другого типа.(Не меняя карту! Просто рендеринг некоторых дополнительных изображений.) Идея алгоритма состояла в том, чтобы профилировать соседей текущего тайла:

Это пример сценария того, что движокможет потребоваться отрисовка, при этом текущая плитка будет помечена знаком X.

Создается массив 3x3 и считываются значения вокруг него. Так что в этом примере массив будет выглядеть следующим образом.

[
    [1,2,2]
    [1,2,2]
    [1,1,2]
];

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

if(profile[0][1] != profile[1][1]){
     //draw a tile which is half sand and half transparent
     //Over the current tile -> profile[1][1]
     ...
}

, который дает этот результат:

, который работает как переход от [0][1] к [1][1], ноне от [1][1] до [2][1], где остается твердый край.Поэтому я подумал, что в этом случае нужно будет использовать угловую плитку.Я создал два листа спрайтов 3x3, которые, как я думал, будут содержать все возможные комбинации плиток, которые могут понадобиться.Затем я повторил это для всех плиток, которые есть в игре (белые области прозрачны).В итоге получается 16 плиток для каждого типа плиток (центральные плитки на каждом листе спрайтов не используются.)

Идеальный результат

Таким образом, с этими новыми тайлами и правильным алгоритмом пример раздела будет выглядеть так:

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

Решение?

Так что, если кто-то может предоставить альтернативное решение относительно того, какЯ мог бы создать этот эффект, или в каком направлении писать алгоритм профилирования, тогда я был бы очень признателен!

Answer 1

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

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

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

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

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

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

Для каждого случая все еще есть выбор a или b. Это зависит от того, на какой стороне трава. Одним из способов определить это может быть отслеживание ориентации границы, но, возможно, самый простой способ сделать это - выбрать одну плитку рядом с краем и посмотреть, какой у нее цвет. На рисунке ниже показаны два случая 5a) и 5b), которые можно различить, например, путем проверки цвета верхней правой плитки.

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

И после выбора соответствующего ребра плитки граница будет выглядеть примерно так:

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

Answer 2

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

Проблемаопределение температуры в каждой точке может быть решено как «краевая задача».Однако самый простой способ отобрать тепло в каждой точке - смоделировать пластину в виде сетки.Мы знаем точки на сетке при постоянной температуре.Мы устанавливаем температуру всех неизвестных точек равной комнатной температуре (как будто вентиляция только что была включена).Затем мы позволяем теплу распространяться через пластину, пока не достигнем сходимости.Это делается путем итерации: мы перебираем каждую (i, j) точку.Мы устанавливаем точку (i, j) = (точка (i + 1, j) + точка (i-1, j) + точка (i, j + 1) + точка (i, j-1)) / 4 [еслиточка (i, j) имеет тепловую вентиляцию с постоянной температурой]

Если вы примените это к своей проблеме, она будет очень похожа, только средние цвета вместо температур.Вам, вероятно, потребуется около 5 итераций.Я предлагаю использовать сетку 400x400.Thats 400x400x5 = менее 1 миллиона итераций, которые будут быстрыми.Если вы используете только 5 итераций, вам, вероятно, не нужно беспокоиться о том, чтобы удерживать какие-либо точки постоянным цветом, поскольку они не будут слишком сильно сдвигаться от своего оригинала (фактически цвет может воздействовать только на точки на расстоянии 5 от цвета).Псевдокод:

iterations = 5
for iteration in range(iterations):
    for i in range(400):
        for j in range(400):
            try:
                grid[i][j] = average(grid[i+1][j], grid[i-1][j],
                                     grid[i][j+1], grid[i][j+1])
            except IndexError:
                pass

Answer 3

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

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

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

Вместо того, чтобы пытаться смешать КАЖДЫЙ край, (это означает, что вам нужно либо узнать результат смешивания смежных плиток сначала - интерполяцию, либо вам нужно уточнить всю карту несколько раз и не полагаться на сгенерированные плитки) почему бы не смешать плитки в чередующемся образце шахматной доски?

[1] [*] [2]
[*] [1] [*]
[1] [*] [2]

т.е. только смешивание плиток, отмеченных в матрице выше?

Предполагая, что единственные допустимые шаги в значении - это по одному, у вас есть только несколько плиток для проектирования ...

A    [1]      B    [2]      C    [1]      D    [2]      E    [1]           
 [1] [*] [1]   [1] [*] [1]   [1] [*] [2]   [1] [*] [2]   [1] [*] [1]   etc.
     [1]           [1]           [1]           [1]           [2]           

Всего будет 16 шаблонов. Если вы воспользуетесь симметрией вращения и отражения, их будет еще меньше.

«A» будет плиткой в ​​стиле [1]. «D» будет диагональ.

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

Если смогу, позже обновлю этот пост изображениями.

Answer 4

Я играл с чем-то похожим на это, оно не было закончено по ряду причин; но в основном это будет матрица из 0 и 1, 0 - это земля, а 1 - стена для приложения-генератора лабиринта во Flash. Поскольку AS3 похож на JavaScript, переписать в JS не составит труда.

var tileDimension:int = 20;
var levelNum:Array = new Array();

levelNum[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
levelNum[1] = [1, 0, 0, 0, 0, 0, 0, 0, 1];
levelNum[2] = [1, 0, 1, 1, 1, 0, 1, 0, 1];
levelNum[3] = [1, 0, 1, 0, 1, 0, 1, 0, 1];
levelNum[4] = [1, 0, 1, 0, 0, 0, 1, 0, 1];
levelNum[5] = [1, 0, 0, 0, 0, 0, 0, 0, 1];
levelNum[6] = [1, 0, 1, 1, 1, 1, 0, 0, 1];
levelNum[7] = [1, 0, 0, 0, 0, 0, 0, 0, 1];
levelNum[8] = [1, 1, 1, 1, 1, 1, 1, 1, 1];

for (var rows:int = 0; rows < levelNum.length; rows++)
{
    for (var cols:int = 0; cols < levelNum[rows].length; cols++)
    {
        // set up neighbours
        var toprow:int = rows - 1;
        var bottomrow:int = rows + 1;

        var westN:int = cols - 1;
        var eastN:int = cols + 1;

        var rightMax =  levelNum[rows].length;
        var bottomMax = levelNum.length;

        var northwestTile =     (toprow != -1 && westN != -1) ? levelNum[toprow][westN] : 1;
        var northTile =         (toprow != -1) ? levelNum[toprow][cols] : 1;
        var northeastTile =     (toprow != -1 && eastN < rightMax) ? levelNum[toprow][eastN] : 1;

        var westTile =          (cols != 0) ? levelNum[rows][westN] : 1;
        var thistile =          levelNum[rows][cols];
        var eastTile =          (eastN == rightMax) ? 1 : levelNum[rows][eastN];

        var southwestTile =     (bottomrow != bottomMax && westN != -1) ? levelNum[bottomrow][westN] : 1;
        var southTile =         (bottomrow != bottomMax) ? levelNum[bottomrow][cols] : 1;
        var southeastTile =     (bottomrow != bottomMax && eastN < rightMax) ? levelNum[bottomrow][eastN] : 1;

        if (thistile == 1)
        {
            var w7:Wall7 = new Wall7();
            addChild(w7);
            pushTile(w7, cols, rows, 0);

            // wall 2 corners

            if      (northTile === 0 && northeastTile === 0 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
            {
                var w21:Wall2 = new Wall2();
                addChild(w21);
                pushTile(w21, cols, rows, 270);
            }

            else if (northTile === 0 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 0)
            {
                var w22:Wall2 = new Wall2();
                addChild(w22);
                pushTile(w22, cols, rows, 0);
            }

            else if (northTile === 1 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 1 && northwestTile === 1)
            {
                var w23:Wall2 = new Wall2();
                addChild(w23);
                pushTile(w23, cols, rows, 90);
            }

            else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
            {
                var w24:Wall2 = new Wall2();
                addChild(w24);
                pushTile(w24, cols, rows, 180);
            }           

            //  wall 6 corners

            else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 0 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 1)
            {
                var w61:Wall6 = new Wall6();
                addChild(w61);
                pushTile(w61, cols, rows, 0); 
            }

            else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 0 && westTile === 1 && northwestTile === 1)
            {
                var w62:Wall6 = new Wall6();
                addChild(w62);
                pushTile(w62, cols, rows, 90); 
            }

            else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 0)
            {
                var w63:Wall6 = new Wall6();
                addChild(w63);
                pushTile(w63, cols, rows, 180);
            }

            else if (northTile === 1 && northeastTile === 0 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 1)
            {
                var w64:Wall6 = new Wall6();
                addChild(w64);
                pushTile(w64, cols, rows, 270);
            }

            //  single wall tile

            else if (northTile === 0 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
            {
                var w5:Wall5 = new Wall5();
                addChild(w5);
                pushTile(w5, cols, rows, 0);
            }

            //  wall 3 walls

            else if (northTile === 0 && eastTile === 1 && southTile === 0 && westTile === 1)
            {
                var w3:Wall3 = new Wall3();
                addChild(w3);
                pushTile(w3, cols, rows, 0);
            }

            else if (northTile === 1 && eastTile === 0 && southTile === 1 && westTile === 0)
            {
                var w31:Wall3 = new Wall3();
                addChild(w31);
                pushTile(w31, cols, rows, 90);
            }

            //  wall 4 walls

            else if (northTile === 0 && eastTile === 0 && southTile === 1 && westTile === 0)
            {
                var w41:Wall4 = new Wall4();
                addChild(w41);
                pushTile(w41, cols, rows, 0);
            }

            else if (northTile === 1 && eastTile === 0 && southTile === 0 && westTile === 0)
            {
                var w42:Wall4 = new Wall4();
                addChild(w42);
                pushTile(w42, cols, rows, 180);
            }

            else if (northTile === 0 && northeastTile === 0 && eastTile === 1 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
            {
                var w43:Wall4 = new Wall4();
                addChild(w43);
                pushTile(w43, cols, rows, 270);
            }

            else if (northTile === 0 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 1 && northwestTile === 0)
            {
                var w44:Wall4 = new Wall4();
                addChild(w44);
                pushTile(w44, cols, rows, 90);
            }

            //  regular wall blocks

            else if (northTile === 1 && eastTile === 0 && southTile === 1 && westTile === 1)
            {
                var w11:Wall1 = new Wall1();
                addChild(w11);
                pushTile(w11, cols, rows, 90);
            }

            else if (northTile === 1 && eastTile === 1 && southTile === 1 && westTile === 0)
            {
                var w12:Wall1 = new Wall1();
                addChild(w12);
                pushTile(w12, cols, rows, 270);
            }

            else if (northTile === 0 && eastTile === 1 && southTile === 1 && westTile === 1)
            {
                var w13:Wall1 = new Wall1();
                addChild(w13);
                pushTile(w13, cols, rows, 0);
            }

            else if (northTile === 1 && eastTile === 1 && southTile === 0 && westTile === 1)
            {
                var w14:Wall1 = new Wall1();
                addChild(w14);
                pushTile(w14, cols, rows, 180);
            }

        }
        // debug === // trace('Top Left: ' + northwestTile + ' Top Middle: ' + northTile + ' Top Right: ' + northeastTile + ' Middle Left: ' + westTile + ' This: ' + levelNum[rows][cols] + ' Middle Right: ' + eastTile + ' Bottom Left: ' + southwestTile + ' Bottom Middle: ' + southTile + ' Bottom Right: ' + southeastTile);
    }
}

function pushTile(til:Object, tx:uint, ty:uint, degrees:uint):void
{
    til.x = tx * tileDimension;
    til.y = ty * tileDimension;
    if (degrees != 0) tileRotate(til, degrees);
}

function tileRotate(tile:Object, degrees:uint):void
{
    // http://www.flash-db.com/Board/index.php?topic=18625.0
    var midPoint:int = tileDimension/2;
    var point:Point=new Point(tile.x+midPoint, tile.y+midPoint);
    var m:Matrix=tile.transform.matrix;
    m.tx -= point.x;
    m.ty -= point.y;
    m.rotate (degrees*(Math.PI/180));
    m.tx += point.x;
    m.ty += point.y;
    tile.transform.matrix=m;
}

В основном это проверяет каждую плитку вокруг нее, идущую слева направо, сверху вниз и предполагает, что края плитки всегда равны 1. Я также позволил себе экспортировать изображения в файл для использования в качестве ключа: *

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

Редактировать: скриншот результата этого кода.

Answer 5

Я бы предложил несколько вещей:

• не имеет значения, что такое "центральная" плитка, верно?это может быть 2, но если бы все остальные были равны 1, это показало бы 1?

• , это только имеет значение, какие углы есть, когда есть различие в непосредственных соседях к вершинеили сторона.Если все непосредственные соседи равны 1, а угол равен 2, он будет показывать 1.

• Я бы, вероятно, рассчитал все возможные комбинации соседей, создав массив из 8 индексов с первымчетыре, указывающие значения верхних / нижних соседей, а вторая, указывающая диагонали:

ребра [N] [E] [S] [W] [NE] [SE] [SW] [NW] = любое смещение в спрайте

, поэтому в вашем случае [2] [2] [1] [1] [2] [2] [1] [1] = 4 (5-йsprite).

в этом случае [1] [1] [1] [1] будет 1, [2] [2] [2] [2] будет 2, а остальные будут иметьбыть выработанным.Но поиск конкретной плитки будет тривиальным.