12.03.2012 23:02
Podstawy silnika kafelkowego część 2: odnajdywanie ścieżki [zaawansowany]
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:
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.
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ę)
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.
