Algorytm Układania Map
Mapa
Tworzę RPG na bazie kafelków z Javascript, używając Perlin noise heightmaps, 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 przekształca go w liczbę całkowitą (0-5) w zależności od jego położenia pomiędzy (0-255), co odpowiada kafelkowi w słowniku płytek. To Tablica 200x200 jest następnie przekazywana do klienta.
Następnie silnik określa płytki z wartości w tablicy i rysuje je na kanwie. Tak więc kończę z ciekawymi światami, które mają realistycznie wyglądające cechy: góry, morza itp.
Następną rzeczą, którą chciałem zrobić, było zastosowanie pewnego rodzaju algorytmu mieszania, który spowodowałby, że płytki płynnie wtopią się w sąsiadów, jeśli sąsiad nie jest tego samego typu. Przykładowa Mapa powyżej jest tym, co gracz widzi w ich minimapie. Na ekranie widzą renderowaną wersję sekcji oznaczonej białym prostokątem; gdzie kafelki są renderowane z ich obrazami, a nie jako jednokolorowe piksele.
Jest to przykład tego, co użytkownik zobaczy na mapie, ale Nie Jest to ta sama lokalizacja, co pokazuje widok powyżej!
To właśnie w tym widoku chcę, aby nastąpiło przejście.
Algorytm
Wymyśliłem prosty algorytm, który przemierzaj mapę w obszarze widokowym i Renderuj inny obraz na górze każdego kafelka, pod warunkiem, że znajduje się on obok kafelka innego typu. (Nie zmieniając mapy! Renderuję dodatkowe obrazy.) Algorytm miał na celu profilowanie sąsiadów obecnego kafelka:
Jest to przykładowy scenariusz tego, co silnik może mieć do renderowania, z bieżącym kafelkiem oznaczonym symbolem X.
Tworzona jest tablica 3x3 i odczytywane są wartości wokół niej. Więc w tym przykładzie tablica wyglądałaby tak.
[
[1,2,2]
[1,2,2]
[1,1,2]
];
Moim pomysłem było wtedy opracowanie serii przypadków 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 wynik:
, który działa jako przejście z [0][1] do [1][1], ale nie z [1][1] do [2][1], gdzie pozostaje twarda krawędź. Więc pomyślałem, że w tym przypadku trzeba będzie użyć płytki narożnej. Stworzyłem dwa arkusze 3x3 sprite, które myślałem, że pomieszczą wszystkie możliwe kombinacje płytek, które mogą być potrzebne. Następnie odtworzyłem to dla wszystkich płytek, które są w grze (białe obszary są przezroczyste). Oznacza to 16 płytek dla każdego typu płytek (środkowe płytki na każdym arkuszu spritesheet nie są używane.)
Idealny Wynik
Więc, z tymi nowymi kafelkami i poprawnym algorytmem, sekcja przykładowa wyglądałaby tak:
Każda moja próba zakończyła się niepowodzeniem, jest zawsze jakaś wada algorytmu i wzory kończą się dziwnie. Nie wydaje mi się, aby wszystkie sprawy były prawidłowe i ogólnie wydaje się, że to kiepski sposób na to.
Rozwiązanie?Więc, jeśli ktoś mógłby dostarczyć alternatywne rozwiązanie, jak mogę stworzyć ten efekt, lub w jakim kierunku iść do pisania algorytmu profilowania, byłbym bardzo wdzięczny!
5 answers
Podstawową ideą tego algorytmu jest użycie wstępnego etapu 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 będzie znalezienie wszystkich krawędzi. W poniższym przykładzie edge tiles oznaczone znakiem X są wszystkie zielone płytki z tan tiles jako jeden lub więcej z ich ośmiu sąsiadujących płytek. W przypadku różnych typów terenu warunek ten może przekładać się na to, że płytka jest płytką krawędziową, jeśli ma sąsiadów o niższych teren-numer.
Po wykryciu wszystkich płytek krawędzi następną rzeczą do zrobienia jest wybranie odpowiedniego kafelka wygładzającego dla każdej płytki krawędzi. Oto moja reprezentacja Twoich gładkich płytek.
Zauważ, że nie ma tak wielu różnych rodzajó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 jest 12 różnych przypadków, które musimy rozróżnić.
Teraz, patrząc na jedną krawędziową płytkę, możemy określić, w którą stronę obraca się granica, patrząc na cztery najbliższe sąsiadujące płytki. Zaznaczając krawędź płytki z X tak jak powyżej mamy następujące sześć różnych przypadków.
Te przypadki są używane do określenia odpowiedniej płytki wygładzającej i możemy odpowiednio numerować płytki wygładzające.
Jest jeszcze wybór a lub b dla każdego przypadku. To zależy od tego, po której stronie znajduje się trawa. Jednym ze sposobów na określenie tego może być śledzenie orientacji granicy, ale prawdopodobnie najprostszym sposobem na to jest wybranie jednego kafelka obok krawędzi i sprawdzenie, jaki ma kolor. Poniższy obrazek pokazuje dwa przypadki 5a) i 5b), które można rozróżnić, na przykład sprawdzając kolor prawej górnej płytki.
Ostateczne wyliczenie dla oryginalnego przykładu wyglądałoby wtedy następująco to.
I po zaznaczeniu odpowiedniej krawędzi krawędź będzie wyglądać mniej więcej tak.
Na koniec mogę powiedzieć, że będzie to działać tak długo, jak granica jest w pewnym sensie regularna. Dokładniej, płytki krawędziowe, które nie mają dokładnie dwóch płytek krawędziowych, ponieważ ich sąsiedzi będą musieli być traktowani oddzielnie. Będzie to miało miejsce dla płytek krawędziowych na krawędzi mapy, które będą miały jedną krawędź sąsiada i dla bardzo wąskich kawałków teren, w którym liczba sąsiednich płytek krawędziowych może wynosić trzy lub nawet cztery.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-01-22 08:54:31
Poniższy kwadrat przedstawia metalową płytę. W prawym górnym rogu znajduje się "odpowietrznik ciepła". Możemy zobaczyć, jak ponieważ temperatura tego punktu pozostaje stała, metalowa płyta zbiega się do stałej temperatury w każdym punkcie, będąc naturalnie gorętsza w pobliżu góry: {]}
Jeśli zastosujesz to do swojego problemu, jest to bardzo podobne, tylko średnie kolory zamiast temperatur. Prawdopodobnie potrzebujesz około 5 iteracji. Proponuję użyć siatki 400x400. To 400x400x5 = mniej niż 1 milion iteracji, które będą szybkie. Jeśli używasz tylko 5 iteracji, prawdopodobnie nie będziesz musiał martwić się o utrzymywanie stałego koloru punktów, ponieważ nie będą one zbytnio przesuwać się od ich oryginału (w rzeczywistości tylko punkty w odległości 5 od koloru mogą być realizowane przez kolor). 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
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-01-20 23:59:30
Ok, więc pierwsze myśli są takie, że automatyzacja idealnego rozwiązania problemu wymaga dość mięsistej matematyki interpolacji. Opierając się na fakcie, że wspominasz wstępnie renderowane obrazy płytek, zakładam, że pełne rozwiązanie interpolacji nie jest tutaj uzasadnione.
Z drugiej strony, jak powiedziałeś, ręczne wykończenie mapy doprowadzi do dobrego wyniku... ale zakładam również, że każdy ręczny proces naprawiania usterek również nie jest opcją.
Oto prosty algorytm, który nie daje doskonały wynik, ale jest to bardzo satysfakcjonujące ze względu na niski wysiłek, jaki zajmuje.
Zamiast próbować mieszać wszystkie krawędzie płytek (co oznacza, że musisz albo znać wynik mieszania sąsiednich płytek najpierw - interpolacja, albo musisz udoskonalić całą mapę kilka razy i nie możesz polegać na wstępnie wygenerowanych kafelkach) dlaczego nie mieszać płytek w naprzemienny wzór szachownicy?
[1] [*] [2]
[*] [1] [*]
[1] [*] [2]
Czyli tylko mieszanie płytek z powyższej matrycy?
Zakładając, że jedynymi dozwolonymi krokami wartości są pojedynczo, 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]
W sumie będzie 16 wzorów. Jeśli skorzystasz z symetrii obrotowej i refleksyjnej, będzie ich jeszcze mniej.
'A' będzie gładką płytką w stylu [1]. "D" będzie przekątną.
Będą małe nieciągłości w rogach płytek, ale będą one niewielkie w porównaniu do przykładu, który podałeś.
Jeśli mogę, zaktualizuję ten post zdjęciami później.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-01-17 22:07:15
Bawiłem się czymś podobnym do tego, nie zostało to ukończone z wielu powodów; ale w zasadzie potrzeba byłoby matrycy 0 i 1, 0 jest ziemią i 1 jest ścianą dla aplikacji Generator 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 wszystkie płytki wokół niego, przechodząc od lewej do prawej, od góry do dołu i zakłada, że płytki krawędzi są zawsze 1. Pozwoliłem sobie również na eksportowanie obrazów jako pliku do użycia jako klucza:
Jest to niekompletne i prawdopodobnie hakerski sposób, aby to osiągnąć, ale pomyślałem, że może to przynieść jakąś korzyść.
Edit: zrzut ekranu wyniku tego kodu.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-01-19 21:21:58
Proponuję kilka rzeczy:
/ align = "center" bgcolor = "# e0ffe0 " / cesarz chin / / align = center / może być 2, ale jeśli wszystkie pozostałe są 1, to będzie 1?
Liczy się tylko to, jakie są rogi, gdy istnieje różnica w bezpośrednich sąsiadów do góry lub boku. Jeśli wszyscy najbliżsi sąsiedzi są 1, A róg jest 2, to pokazuje 1.
-
Prawdopodobnie wstępnie obliczyłbym wszystkie możliwe kombinacje sąsiadów, tworząc indeks 8 tablica z czterema pierwszymi wskazującymi wartości sąsiadów góry/dołu, a drugim wskazującymi przekątne:
Krawędzie [N] [E] [S] [W] [NE] [SE] [SW] [NW] = dowolne przesunięcie do sprite
Więc w Twoim przypadku, [2][2][1][1][2][2][1][1] = 4 (5. sprite).
W Tym Przypadku, [1][1][1][1] byłoby 1, [2][2][2][2] byłoby 2, a reszta musiałaby być opracowana. Ale wyszukiwanie konkretnego kafelka byłoby trywialne.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-01-17 21:53:56