W poprzedniej części omówiłem pokrótce przekształcenie izometryczne i jak uzyskać je w najłatwiejszy sposób. Tym razem, zgodnie z obietnicą zajmiemy się znajdywaniem ścieżki w silniku kafelkowym wykorzystując jak najprostszą metodę (aczkolwiek nie najszybszą). Nie wiem czy algorytm który tutaj przybliżę ma jakąś konkretną nazwę, ale na pewno jest jednym z najbardziej bezpośrednich spośród wszystkich dostępnych.
Dla wszystkich tych których nie interesują szczegóły przygotowałem klasę z całym algorytmem oraz dodatkowo plikiem FLA pokazującym jak go wykorzystać: PathFind.zip
W działaniu wygląda tak:
(Wybierz punkt startowy i końcowy naciskając na puste pola. Spacja by stworzyć nową mapę)

Działanie algorytmu jest całkiem proste i dzieli się na dwie fazy:
1. Poszukiwanie celu. Z punktu startowego krok po kroku sprawdzamy co raz większy obszar w poszukiwaniu docelowej pozycji, w międzyczasie zapisując do siatki aktualny krok iteracji. Numery iteracji będą nam później potrzebne by odtworzyć ścieżkę.
Urywek kodu z załączonego przykładu:

// ...
var vWrite:Vector.<Vector.<int>> = recreateTiles(tiles);
vWrite[startx][starty] = 1;
vWrite[endx][endy] = -1;
var vCheck:Vector.<Point>;
var vRead.<Point> = new Vector.<Point>();
			
var tile:Point;
var nStep:int = 2;
vRead.push( new Point(startx,starty) );
while(vRead.length != 0) {
				
	vCheck = vRead;
	vRead = new Vector.<Point>();
	for each(tile in vCheck) if(lookupTile(tile.x, tile.y, nStep, vRead,vWrite,vTile)) {
		return retracePath(tile.x,tile.y,nStep,vWrite);
	}
	nStep ++;
}
return null;
// ...

Funkcja lookupTile poszukuje kolejnych kafelek do iteracji. Jeśli któryś z 4 kierunków zawiera docelowy punkt, pętla zostaje zakończona i zwrócona zostaje znaleziona ścieżka. W przeciwnym wypadku w vWrite zapisywany jest aktualny krok, a do vRead wpisywana jest pozycja kolejnej kafelki do sprawdzenia.
2. Odtwarzanie ścieżki. Gdy już odnajdziemy punkt docelowy wystarczy krok po kroku zacząć wracać po zapisanych liczbach w vWrite by uzyskać naszą ścieżkę. Powiedzmy że doszliśmy do docelowej pozycji w 20 iteracji - teraz musimy zacząć się wracać zaczynając od znalezienia najbliższej kafelki z numerem 19, potem 18, 17, itd. Aż do 1 który będzie punktem startowym (0 powinny mieć kafelki które nigdy nie zostały sprawdzone).

Na koniec jeszcze tylko mała uwaga: algorytm można przyspieszyć wykonując go jednocześnie na punkcie startowym i końcowym, przez co ścieżka będzie odnaleziona gdy oba spotkają się w połowie drogi. Taki też sposób został użyty w dołączonej klasie.
Następnym razem przyjrzymy się idei "pola widzenia" w silnikach kafelkowych.

W tym trzyczęściowym artykule postaram się przybliżyć kilka najbardziej podstawowych zagadnień z silników opartych o kratki - czy też kafelki (tile-based). Owe silniki istnieją już od bardzo dawna i wydawać by się mogło, że już wszystko w tej sprawie zostało powiedziane, jednak wciąż wiele osób ma z nimi problemy, nierzadko komplikując trywialne zagadnienia.
Jednym z takich zagadnień jest widok izometryczny (czasem nazywanym "widokiem po skosie") będący specyficznym rodzajem transformacji 3D bez dodatku perspektywy, często wykorzystywanym w starszych grach strategicznych. Chociaż definicja mówi o transformacji 3D takowa wcale nie jest wymagana i można ją zastąpić czymś o wiele prostszym, co niestety nie wszyscy próbują zrobić i dlatego w Internecie można całkiem sporo podobnych artykułów, które jednak najpierw tłumaczą podstawy 3D - nie potrzebnie.
Całość można sprowadzić do pojedynczej funkcji:

function getTile(nTargetX:Number,nTargetY:Number,nWidth:Number,nHeight:Number):Point {
	var nScale:Number = nWidth/nHeight;
	var nTransY:Number = (nScale*nTargetY-nTargetX)/2;
	var nTransX:Number = nTargetX+nTransY;
	var nTmpY:Number = Math.round( nTransY/(nHeight*nScale) );
	var nTmpX:Number = Math.round( nTransX/nWidth );	
	var nTileX:Number = (nTmpX-nTmpY)*nWidth;
	var nTileY:Number = (nTmpX+nTmpY)*nHeight;
	return new Point(nTileX,nTileY);
}

W efekcie dostając:
(Zielone kółko to Point zwrócony przez getTile)
Gotowy przykład: tile_example.zip

I to w zasadzie wszystko, dalej tylko jeszcze poświecę parę słów na wyjaśnienie działania funkcji getTile krok po kroku:
1.
var nScale:Number = nWidth/nHeight;
Skala będzie nam potrzebna przy transformacji by wyrównać wysokość do szerokości (ponieważ algorytm działa tylko w skali 1:1).
2.
var nTransY:Number = (nScale*nTargetY-nTargetX)/2;
var nTransX:Number = nTargetX+nTransY;
W tym miejscu następuje transformacja punktu na ekranie, na punkt w rzucie izometrycznym.
Najczęściej mówiąc o rzucie izometrycznym mamy na myśli przestrzeń obróconą o kąt 45 stopni, w taki sposób że ruchowi w prawo nie będzie odpowiadać samo +X, ale raczej pewna wartość X plus częściowo również i Y. Najlepiej zobrazować to na przykładzie:

Jak widać przesunięcie kursora w prawo, przesuwa punkt transformacji w prawo tylko po części, ponieważ dochodzi do tego jeszcze przesunięcie do góry. Uzbrojeni w ta wiedzę, możemy spróbować napisać generalny wzór - skoro przesunięcie w prawy (+X) daje nam również trochę przesunięcia do góry (-Y) można powiedzieć, że Y maleje wraz ze wzrostem X, czyli innymi słowy Y = -nTargetX. Jednak należy pamiętać, że nie jest to transformacja x=>y (inaczej mieli byśmy do czynienia z obrotem o 90 stopni), stąd też do równania należy dołączyć również dzielnie przez 2 (bo 90 stopni podzielone przez 2 to nasze 45 stopni... w wielkim uproszczeniu). Teraz gdy już znamy Y, obliczenie X jest trywialne i wystarczy, że odejmiemy wartość Y od docelowego X (by pokonany dystans był identyczny z tym przed transformacją), a ponieważ Y już jest ujemne wstawiamy znak dodawania Y = nTargetX+nTransY;. Przy okazji, plus i minus można w tych równaniach zamienić miejscami by uzyskać transformację dla obrotu -45 stopni.
3.
var nTmpY:Number = Math.round( nTransY/(nHeight*nScale) );
var nTmpX:Number = Math.round( nTransX/nWidth );
var nTileX:Number = (nTmpX-nTmpY)*nWidth;
var nTileY:Number = (nTmpX+nTmpY)*nHeight;
Tutaj zmieniamy wybrany punkt na podpadający pod niego kafelek, poprzez "skurczenie" całej przestrzeni o wysokość i szerokość kratki, następnie usunięcie informacji po przecinku i przywrócenia całości do "normalnych rozmiarów". Ponieważ uwielbiam przykłady o to następny: jeśli szerokość kafelki numer #0 wynosi 20 pikseli, to wszystko pomiędzy 0 a 20 pikseli będzie podpadać właśnie pod nią, tak więc: jak sprawdzić do której kafelki należy siódma piksela? Bierzemy owe 7, dzielimy przez 20 i dostajemy 0.35. Z rezultatu usuwamy wszystko po przecinku i dostajemy naszą kratkę #0. Jeszcze spróbujmy tego samego dla pikseli 27; 27/20 = 1.35; usuwamy liczby po przecinku i dostajemy #1, co się zgadza bo dwudziesta siódma piksela nie należy do kratki #0.

Uff, starczy na dzisiaj. Za dwa tygodnie napisze jak w najłatwiejszy sposób zaimplementować znajdywanie ścieżki w silnikach kafelkowych.