Algorytm kafelkowania mapy

Mapa

Robię grę RPG opartą na kafelkach z Javascriptem, używając map wysokości szumów Perlin, a następnie przypisuję typ kafelka na podstawie wysokości szumu.

Mapy wyglądają mniej więcej tak (w widoku minimapy).

Mam dość prosty algorytm, który wyodrębnia wartość koloru z każdego piksela na obrazie i konwertuje ją na liczbę całkowitą (0-5) w zależności od pozycji między (0-255), która odpowiada kafelkowi w słowniku kafelków. Ta tablica 200x200 jest następnie przekazywana do klienta.

Silnik następnie określa kafelki z wartości w tablicy i rysuje je na kanwie. W rezultacie otrzymuję interesujące światy, które mają realistycznie wyglądające cechy: góry, morza itp.

Teraz następną rzeczą, którą chciałem zrobić, było zastosowanie pewnego rodzaju algorytmu mieszania, który powodowałby płynne wtapianie się kafelków w sąsiadów, jeśli sąsiad nie jest tego samego typu. Przykładowa mapa powyżej jest tym, co gracz widzi na swojej minimapie. Na ekranie widzą wyrenderowaną wersję sekcji oznaczonej białym prostokątem; gdzie kafelki są renderowane z ich obrazami, a nie jako piksele w jednym kolorze.

To jest przykład tego, co użytkownik zobaczy na mapie, ale nie jest to ta sama lokalizacja, jak pokazuje powyższy widok!

Z tego punktu widzenia chcę, aby nastąpiło przejście.

Algorytm

Wymyśliłem prosty algorytm, który przechodziłby przez mapę w rzutni i renderował inny obraz na górze każdego kafelka, pod warunkiem, że znajdował się on obok kafelka innego typu. (Nie zmienia mapy! Renderuje tylko dodatkowe obrazy). Pomysł algorytmu polegał na profilowaniu sąsiadów bieżącego kafelka:

To jest przykładowy scenariusz tego, co silnik może musieć renderować, przy czym bieżący kafelek jest oznaczony X.

Tworzona jest tablica 3x3 i wartości wokół niej są wczytywane. W tym przykładzie tablica będzie wyglądać.

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

Mój pomysł polegał wtedy na opracowaniu serii przypadków dla możliwych konfiguracji płytek. Na bardzo prostym poziomie:

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

Co daje taki wynik:

Który działa jako przejście od [0][1]do [1][1], ale nie od [1][1]do [2][1], gdzie pozostaje twarda krawędź. Pomyślałem więc, że w tym przypadku trzeba będzie użyć płytki narożnej. Stworzyłem dwa arkusze sprite'ów 3x3, które moim zdaniem będą zawierać wszystkie możliwe kombinacje płytek, które mogą być potrzebne. Następnie powtórzyłem to dla wszystkich kafelków w grze (białe obszary są przezroczyste). To kończy się 16 kafelkami dla każdego rodzaju kafelka (środkowe kafelki na każdym arkuszu kształtów nie są używane).

Idealny wynik

Tak więc, z tymi nowymi kafelkami i poprawnym algorytmem, przykładowa sekcja wyglądałaby następująco:

Każda podjęta przeze mnie próba zakończyła się jednak niepowodzeniem, algorytm zawsze zawiera błędy, a wzorce kończą się dziwnie. Wydaje się, że nie mogę rozwiązać wszystkich przypadków dobrze i ogólnie wydaje się to kiepskim sposobem zrobienia tego.

Rozwiązanie?

Tak więc, gdyby ktoś mógł zaproponować alternatywne rozwiązanie, jak mogę stworzyć ten efekt lub w jakim kierunku pójść pisanie algorytmu profilowania, byłbym bardzo wdzięczny!

Podstawową ideą tego algorytmu jest użycie etapu wstępnego przetwarzania, aby znaleźć wszystkie krawędzie, a następnie wybrać właściwą płytkę wygładzającą zgodnie z kształtem krawędzi.

Pierwszym krokiem byłoby znalezienie wszystkich krawędzi. W poniższym przykładzie płytki krawędzi oznaczone X to wszystkie zielone płytki z brązową płytką jako jedną lub więcej z ośmiu sąsiadujących płytek. Przy różnych typach terenu warunek ten może oznaczać, że płytka jest płytką krawędziową, jeśli ma sąsiadów o niższym numerze terenu.

Po wykryciu wszystkich płytek krawędzi kolejną rzeczą do zrobienia jest wybranie odpowiedniej płytki wygładzającej dla każdej płytki krawędzi. Oto moja reprezentacja twoich wygładzających płytek.

Zwróć uwagę, że w rzeczywistości nie ma zbyt wielu różnych typów płytek. Potrzebujemy ośmiu zewnętrznych płytek z jednego z kwadratów 3x3, ale tylko cztery narożne kwadraty z drugiego, ponieważ płytki o prostych krawędziach znajdują się już w pierwszym kwadracie. Oznacza to, że w sumie musimy rozróżnić 12 różnych przypadków.

Teraz, patrząc na jeden kafelek krawędzi, możemy określić, w którą stronę obraca się granica, patrząc na cztery najbliższe sąsiednie kafelki. Zaznaczając płytkę krawędzi X, tak jak powyżej, mamy sześć następujących przypadków.

Te przypadki służą do określenia odpowiedniej płytki wygładzającej i możemy odpowiednio ponumerować płytki wygładzające.

Nadal istnieje możliwość wyboru a lub b dla każdego przypadku. To zależy od tego, po której stronie znajduje się trawa. Jednym ze sposobów ustalenia tego może być śledzenie orientacji granicy, ale prawdopodobnie najprostszym sposobem na to jest wybranie jednej płytki obok krawędzi i sprawdzenie, jaki ma kolor. Poniższy rysunek przedstawia dwa przypadki 5a) i 5b), które można rozróżnić, na przykład sprawdzając kolor prawej górnej płytki.

Ostateczne wyliczenie oryginalnego przykładu wyglądałoby wtedy następująco.

A po wybraniu odpowiedniego kafelka krawędzi obramowanie wyglądałoby mniej więcej tak.

Na koniec mogę powiedzieć, że to zadziała, o ile granica jest dość regularna. Mówiąc dokładniej, płytki krawędziowe, które nie mają dokładnie dwóch płytek krawędzi, ponieważ sąsiedzi, będą musieli traktować oddzielnie. Będzie to miało miejsce w przypadku kafelków krawędzi na krawędzi mapy, które będą miały jednego sąsiada na krawędzi, oraz w przypadku bardzo wąskich fragmentów terenu, gdzie liczba sąsiadujących kafelków krawędzi może wynosić trzy lub nawet cztery.

Poniższy kwadrat przedstawia metalową płytkę. W prawym górnym rogu znajduje się „otwór wentylacyjny”. Widzimy, że gdy temperatura tego punktu pozostaje stała, metalowa płyta zbiega się do stałej temperatury w każdym punkcie, będąc naturalnie cieplejszą w pobliżu szczytu:

Problem znalezienia temperatury w każdym punkcie można rozwiązać jako „Problem z wartością graniczną”. Jednak najprostszym sposobem obliczenia ciepła w każdym punkcie jest modelowanie płyty jako siatki. Znamy punkty na siatce przy stałej temperaturze. Ustawiliśmy temperaturę wszystkich nieznanych punktów na temperaturę pokojową (tak, jakby wentylacja została dopiero włączona). Następnie pozwalamy, aby ciepło rozchodziło się po płycie, aż osiągniemy konwergencję. Odbywa się to poprzez iterację: iterujemy przez każdy punkt (i, j). Ustawiamy punkt (i, j) = (punkt (i + 1, j) + punkt (i-1, j) + punkt (i, j + 1) + punkt (i, j-1)) / 4 [chyba że punkt (i, j) ma wylot ciepła o stałej temperaturze]

Jeśli zastosujesz to do swojego problemu, jest on bardzo podobny, po prostu średnie kolory zamiast temperatur. Prawdopodobnie potrzebowałbyś około 5 iteracji. Sugeruję użycie siatki 400x400. To 400x400x5 = mniej niż 1 milion iteracji, które będą szybkie. Jeśli użyjesz tylko 5 iteracji, prawdopodobnie nie będziesz musiał martwić się o utrzymanie stałego koloru jakichkolwiek punktów, ponieważ nie będą one zbytnio odbiegać od oryginału (w rzeczywistości tylko punkty w odległości 5 od koloru mogą być efektem koloru). Pseudo kod:

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

Ok, więc pierwsze myśli są takie, że zautomatyzowanie idealnego rozwiązania problemu wymaga dość skomplikowanej matematyki interpolacyjnej. Biorąc pod uwagę fakt, że wspomniałeś o wstępnie renderowanych obrazach kafelków, zakładam, że rozwiązanie pełnej interpolacji nie jest tutaj uzasadnione.

Z drugiej strony, jak powiedziałeś, ręczne wykańczanie mapy da dobry wynik ... ale zakładam też, że jakikolwiek ręczny proces naprawiania usterek również nie wchodzi w grę.

Oto prosty algorytm, który nie daje doskonałych wyników, ale jest bardzo satysfakcjonujący ze względu na niewielki wysiłek.

Zamiast próbować mieszać KAŻDĄ krawędź płytki (co oznacza, że ​​musisz najpierw znać wynik mieszania sąsiednich płytek - interpolację, albo musisz kilkakrotnie udoskonalić całą mapę i nie możesz polegać na wstępnie wygenerowanych kafelkach) dlaczego by nie połączyć płytek w naprzemienny wzór szachownicy?

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

To znaczy tylko mieszanie płytek zaznaczonych gwiazdką w powyższej matrycy?

Zakładając, że jedyne dozwolone kroki wartości są jednorazowe, masz tylko kilka płytek do zaprojektowania ...

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]           

Łącznie będzie 16 wzorów. Jeśli wykorzystasz symetrię obrotową i refleksyjną, będzie ich jeszcze mniej.

„A” to zwykły kafelek stylu [1]. „D” byłoby przekątną.

W rogach płytek będą występować niewielkie nieciągłości, ale będą one niewielkie w porównaniu z podanym przykładem.

Jeśli będę mógł, zaktualizuję ten post obrazami później.

Bawiłem się czymś podobnym do tego, nie skończyło się to z wielu powodów; ale w zasadzie wymagałoby to macierzy 0 i 1, gdzie 0 to ziemia, a 1 to ściana dla aplikacji generatora labiryntu we Flashu. Ponieważ AS3 jest podobny do JavaScript, nie byłoby trudno przepisać go w 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;
}

Zasadniczo sprawdza to każdy kafelek wokół niego, przechodząc od lewej do prawej, od góry do dołu i zakłada, że ​​kafelki krawędzi są zawsze 1. Pozwoliłem sobie również wyeksportować obrazy jako plik, aby użyć go jako klucza:

Jest to niekompletne i prawdopodobnie hacky sposób na osiągnięcie tego celu, ale pomyślałem, że może to przynieść pewne korzyści.

Edycja: zrzut ekranu z wynikiem tego kodu.

Proponuję kilka rzeczy:

• nie ma znaczenia, jaki jest kafelek „środkowy”, prawda? może to być 2, ale jeśli wszystkie pozostałe to 1, to pokaże 1?

• ważne jest tylko to, jakie są rogi, gdy istnieje różnica w bezpośrednim sąsiedztwie na górze lub z boku. Jeśli wszyscy najbliżsi sąsiedzi mają 1, a róg ma 2, to pokaże 1.

• Prawdopodobnie wstępnie obliczyłbym wszystkie możliwe kombinacje sąsiadów, tworząc tablicę indeksów 8 z pierwszymi czterema wskazującymi wartości górnych / dolnych sąsiadów, a drugą wskazującą przekątne:

krawędzie [N] [E] [S] [W] [NE] [SE] [SW] [NW] = jakiekolwiek przesunięcie w sprite

więc w twoim przypadku [2] [2] [1] [1] [2] [2] [1] [1] = 4 (piąty duszek).

w tym przypadku [1] [1] [1] [1] będzie równe 1, [2] [2] [2] [2] będzie równe 2, a resztę należałoby dopracować. Ale wyszukiwanie konkretnego kafelka byłoby trywialne.