| Strona Główna | Artykuły | Produkcje | Linki | O mnie | Kontakt |
|
ARTYKUŁY: "Metoda obcinania izometrycznej planszy do rozmiaru widoku " |
|
Spis treści 1. WstępDo napisanie tego artykułu zainspirował mnie fakt braku konkretnych rozwiązań opisywanego problemu w Sieci. Jako że sam potrzebowałem jakiegoś sposobu obcinania dużych plansz izometrycznych do rozmiarów widoku (np. ekranu monitora) poświęciłem trochę czasu na próbę rozwiązania tego problemu. Wyniki swojej pracy przedstawiam właśnie w tym artykule, aby zaoszczędzić czasu i nerwów tym osobom, które staną przed podobnym problemem.  Rysunek 1 Rysunek przedstawia wynik działania programu "ClippingDemo", który napisałem na potrzeby artykułu, a który można pobrać (wraz ze źródłami) spod adresu wskazanego na końcu artykułu. Pola białe oznaczają pola rysowane, które są widoczne w obszarze wyznaczonym przez wykropkowany prostokąt. 2. Rozwiązanie intuicyjneNa samym początku chciałbym jeszcze napisać co rozumiem pod pojęciem planszy z widokiem izometrycznym, bo jest to temat dość kontrowersyjny. Generalnie tą samą nazwą określa się przedstawienia świata gry z ukosa (w przeciwieństwie do równie popularnego, "zwykłego" widoku z góry), co sprawia wrażenie trójwymiarowości. Implementacje jednak bywają różne tj. jedne wykorzystują kafle o stosunku wysokości do szerokość 2:1, inne 3:1, inne za kształt kafla uznają romb, a jeszcze inne widok izometryczny implementują jako widok z góry i z przodu (jak w japońskich cRPG). Ja w swoim artykule przyjmuję pierwszą wspomnianą implementację, czyli wykorzystuję kafle 2:1 (dokładniej 96 x 48 pikseli). Przykładowy kafelek jest widoczny na poniższym obrazku:  Rysunek 2 Choć w widoczny sposób faworyzuję jeden rozmiar i kształt kafla, to jednak opisywana metoda może być bez przeszkód implementowana dla innych systemów. | - - - - - - - # - - - - - - | | - - - - - - # - # - - - - - | | - - - - - # - # - # - - - - | | - - - - # - # - # - # - - - | | - - - # - # - # - # - # - - | | - - # - # - # - # - # - # - | | - # - # - # - # - # - # - # | | # - # - # - # - # - # - # - | | - # - # - # - # - # - # - - | | - - # - # - # - # - # - - - | | - - - # - # - # - # - - - - | | - - - - # - # - # - - - - - | | - - - - - # - # - - - - - - | | - - - - - - # - - - - - - - | Nie było by to jednak rozwiązanie optymalne, ponieważ jak widać znaczki '-' przeważają nad '#' co w naszym przypadku oznacza zwykłe marnotrawstwo pamięci. Mamy w sumie 7 * 9 = 63 kafle, a macierz ma 15 * 15 = 225 pozycji, czyli potrzebowalibyśmy 225 / 63 = 3,5 razy więcej pamięci niż trzeba do przechowania "zwykłych" kafli. Co więcej, 162 pozycje są zupełnie nie potrzebne. Podsumowując mielibyśmy do czynienia z metodą bardzo szybką (odnalezienie kafli leżących w jakimś obszarze miało by koszt stały, ot zwykłe operacje na tablicy), ale niestety także z metodą szalenie pamięciożerną, bo co jeśli wymyślimy sobie mapkę 123 x 456? 3. Opis metodya) Ogólnie o metodzieDo opisu metody posłużę się obrazkiem przedstawiającym "rozbitą" planszę 9 x 7, tą samą jaką rozważaliśmy w poprzednich punktach.  Rysunek 3 Jak do tej pory nie widać żadnej różnicy z intuicyjną metodą, opisaną w poprzednim punkcie. Jednak sam sposób interpretacji jest zupełnie różny. Gdy przełożymy obraz rysunku 1 na obraz rysunku 3 zauważymy, że w wyniku obcinania zostały wyznaczone kafelki leżące w kolumnach 5, 6, 7, 8, 9 i 10, oraz w wierszach 4, 5, 6, 7, 8, 9 i 10 (rys. 3). Taką pojedynczą kolumnę nazywać będę x-kubełkiem, zaś pojedynczy wiersz y-kubełkiem.  Rysunek 4 Ktoś mógłby zapytać, dlaczego akurat taka kolejność rysowania kafli jest wymagana. Otóż plansza rysowana w opisany powyżej sposób pozwala nam na stosowanie kafli o różnych grubościach podstawy. Jeśli w swoim projekcie zamierzasz używać "płaskich" kafli (jak na rysunku 2) to masz w kwestii wyboru kierunku rysowania pełną dowolność. liczba_y_kubelkow = szerokosc_planszy + wysokosc_planszy - 1 przy czym wysokość i szerokość planszy wyraża się w ilości kafli. Warto zauważyć, że ilość y-kubełków zawsze jest równa ilości x-kubełków.
b) Budowa struktury planszyZbudowanie powyższej struktury nie jest jakimś trudnym zadaniem. Spójrzmy na poniższą plansze 9 x 7 (szerokość i wysokość planszy jest indeksowana od zera): - 0 1 2 3 4 5 6 7 8 0 # # # # # # # # # 1 # # # # # # # # # 2 # # # # # # # # # 3 # # # # # # # # # 4 # # # # # # # # # 5 # # # # # # # # # 6 # # # # # # # # # Zbudowanie struktury z tak przedstawionej planszy można zrealizować w taki sposób, aby do y-kubełków przechodziły elementy wyznaczone przez przechodzenie pomiędzy kolumnami i wierszami na ukos w góre i w lewo, zaczynając od prawej strony. Kierunek przechodzenia ilustruje poniższy rysunek.  Rysunek 5 Poniżej przedstawiam fragment kodu napisany w języku C/C++, który implementuje przykładową funkcję budującą strukturę planszy. Jest to fragment programu "ClippingDemo", więc struktura kafli nie jest zbyt skomplikowana, podobnie rozmiary planszy są zdeterminowane programowo. Myślę jednak, że nie będzie stanowić problemu przebudowanie kodu do własnych potrzeb. Oto wspomniany kod:
#include <vector>
// definicja typu kafla (tile'a)
typedef struct {
int x, y; // wpolrzedne tile'a na mapie (x - nr. kolumny, y - nr. wiersza)
} TILE, * LPTILE;
// definicja typu tablicy dynamicznej tile'ow
typedef std::vector<LPTILE> VecOfTiles;
// ...
// Funkcja tworzy cala strukture przechowujaca dane o tile'ach, czyli jednowymiarowa
// tablice wskaznikow na wektory przechowujace liste tile'ow w danym kubelku.
// Funkcja pobiera jako argumenty wysokosc i szerokosc planszy.
VecOfTiles** InitBoardData(int boardWidth, int boardHeigth) {
VecOfTiles** ppTiles;
LPTILE ptl;
int x, xSaved, y, ySaved;
int iSize;
iSize = boardWidth + boardHeigth - 1; // - Oblicz ilosc Y-kubelkow
ppTiles = new VecOfTiles* [iSize]; // - Tworz tablice wskaznikow na kolekcje kafli
// Buduje cala strukture danych
xSaved = boardWidth - 1; // - Zaczynamy od prawej strony, czyli od ostatniego X-kubelka
for(int i = 0; i < iSize; i++) {
ppTiles[i] = new VecOfTiles(); // - Tworz Y-kubelek
if(i < boardHeigth) // - Jesli numer Y-kubelka jest mniejszy od calkowitej wysokosci planszy
// to aktualizuj numer wiersza od ktorego zaczynamy wstawianie...
ySaved = i;
else // - W przeciwnym razie aktualizuj tylko numer kolumny (X-kubelka)
xSaved--;
x = xSaved;
y = ySaved;
// W tym momencie, gdy mamy wyliczone polozenie kafla na planszy (x, y), rozpoczynamy dodawanie elementow
// do aktualnego Y-kubelka. Kazdy kolejny element jest wyznaczany przez zmniejszenie wspolrzednych x i y.
// Koniec dodawania elementow nastepuje wtedy, gdy ktores z wyznaczonych pol nie istnieje.
while(x >= 0 && y >= 0) {
// Utworz obiekt kafla i nadaj mu odpowiednie wspolrzedne
ptl = new TILE;
ptl->x = x;
ptl->y = y;
// Dodaj pole do aktualnego Y-kubelka
ppTiles[i]->push_back(ptl);
x--;
y--;
}
}
return ppTiles; // - Zwroc przygotowana plansze
}
Gdy już wiemy, w jaki sposób przechowywać informację o planszy możemy powrócić do głównego wątku naszych rozważań. Omówię teraz sposób pozyskiwania numerów y-kubełków, które odpowiednio wyznaczają górną (y_kubelek_start) i dolną (y_kubelek_end) granicę obszaru obcinania. c) Wyznaczanie widoczności poziomych obszarówRozpatrzmy sobie przykład pokazany na rysunku 1. Przypomnę, że wyznaczono tam y-kubełki (wiersze) od 4 do 10. Ale jak to się stało? Bardzo prosto. Powiedzmy, że mamy jakiś obszar, którego górna krawędź (nazwijmy ją topBoundary) i dolna krawędź (bottomBoundary) wyraża się w ekranowych pikselach. Aby teraz wyznaczyć numer y-kubełka, od którego zaczynamy rysowanie (czyli od tego, który ogranicza nam obszar widoku od góry), wystarczy policzyć: y_kubelek_start = 2 * topBoundary / wysokosc_kafla_px W wyniku tych obliczeń uzyskamy numer y-kubełka, w którym środek jego elementów znajduje się zaraz pod górną krawędzią obszaru (stąd wzór, bo topBoudary / wysokosc_kafla_px / 2 = 2 * topBoundary / wysokosc_kafla_px). Jednak tak nie może być, bo nie będą widoczne fragmenty tych kafli, których środek leży na, lub zaraz ponad granicą. Dlatego od uzyskanego wyniku musimy odjąć 1. Stwarza to jednak niebezpieczną sytuację, gdy z powyższego wzoru uzyskamy liczbę 0. Wtedy odwoływalibyśmy się do -1 y-kubełka, który przecież nie istnieje. Dlatego w swoim programie wykorzystuję makroinstrukcję max, zwracającą największy element z podanych. Podsumowując wszystko, ostateczna wersja wzoru na początkowy y-kubełek ma postać: y_kubelek_start = max(0, (2 * topBoundary / wysokosc_kafla_px) - 1) To początek mamy wyznaczony. Do wyznaczenia końcowego y-kubełka wykorzystamy bardzo podobny sposób. Trzeba tylko dodać 1 (aby rysować kafle, których fragmenty znajdują się na lub zaraz pod krawędzią bottomBoundary), no i zabezpieczyć się przed możliwością wyliczenia nieistniejącego (zbyt dużego) indeksu kubełka. Tym razem do tego celu użyjemy makra min, które zwraca najmniejszy element. W rezultacie mamy: y_kubelek_end = min(1 + (2 * bottomBoundary / wysokosc_kafla_px), szerokosc_planszy + wysokosc_planszy - 1) Pierwszy argument makra min omówiliśmy przed chwilą, zaś drugi to przypomnę, że jest całkowitą ilością y-kubełków (patrz "a) Ogólnie o metodzie"). d) Wyznaczanie widoczności pionowych obszarówW tym wypadku sprawa nieco się komplikuje. Najpierw musimy policzyć, które x-kubełki (czyli kolumny na rysunku 1) leżą w obszarze widoku, a następnie musimy przeliczyć numer x-kubełka na indeks konkretnego elementu w y-kubełku.  Rysunek 6 Teraz zastanówmy się, skąd wzięła się zaznaczona 8. Otóż wzięła się ona z odjęcia numeru x-kubełka, w którym znajduje się pierwszy element piątego y-kubełka (numer_x_kubelka_pierwszego_elementu = 13), od numeru x-kubełka w którego obszarze leży prawa krawędź obszaru obcinania (numer_x_kubelka_granicy = 5). Tą ostatnią wartość możemy uzyskać bardzo prosto ze wzoru (podobnie jak w przypadku y_kubelek_start): numer_x_kubelka_granicy = 2 * rightBoundary / szerokosc_kafla_px - 1 Uzyskanie pierwszej wspomnianej wartości jest już nieco bardziej skomplikowane. W tym celu musimy od wartości całkowitej ilości y-kubełków (liczba_y_kubelkow) odjąć odległość y-kubełka od numeru ostatniego wiersza planszy (reprezentowanego przez wartość wysokosc_planszy). Tę ostatnią wartość uzyskamy odejmując od numeru y-kubełka wysokość planszy. Należy jednak pamiętać że chodzi nam o odległość, więc musimy pozyskać wartość bezwzględną wspomnianej różnicy. Mamy zatem: numer_x_kubelka_pierwszego_elementu = liczba_y_kubelkow - abs(wysokosc_planszy - y_kubelek_start - 1) Odjęcie jedynki w drugim członie wyrażenia jest konieczne, ponieważ numery y-kubełków liczymy od 0, ale wysokość planszy już nie. x_kubelek_start = numer_x_kubelka_pierwszego_elementu - numer_x_kubelka_granicy = Tutaj podobnie jak wcześniej istnieje ryzyko wyliczenia wartości ujemnych, dlatego całość musimy wrzucić do makra max. Ostatecznie mamy: x_kubelek_start = max(0, liczba_y_kubelkow - abs(wysokosc_planszy - y_kubelek_start - 1) - 2 * rightBoundary / szerokosc_kafla_px - 1) Uzyskana w ten sposób wartość (w naszym przykładzie jest to 8) nie odzwierciedla jednak numeru indeksu elementu, od którego zaczynamy rysowanie. Potrzebne jest nam jeszcze jedno przekształcenie. Zauważmy, że w naszym przykładzie moglibyśmy uzyskaną przed chwilą wartość po prostu podzielić przez 2 uzyskując w ten sposób poszukiwany numer indeksu. Ale czy zawsze jest tak prosto? Niestety nie. Spojrzmy jeszcze raz na rysunek 6. Gdybyśmy lekko przesunęli granicę rightBoundary w prawo (powiedzmy na odległość połowy szerokości kafla), w wyniku obliczeń wartość numer_x_kubelka_granicy zamiast 5 miałby wartość 6. W ten sposób uzyskalibyśmy jako x_kubelek_start wartość 7. Zauważmy, że i w tym wypadku powinniśmy rozpocząć rysowanie 5 y-kubełka od elementu o tym samym indeksie co w przypadku nie przesuwania granicy. Musimy zatem uzyskaną wartość (7) zwiększyć o jeden i dopiero po tym podzielić przez 2. Jak widać po obliczeniu wartości x_kubelek_start konieczne jest każdorazowe sprawdzenie, czy uzyskana liczba jest parzysta, czy nie. Jeśli nie jest parzysta, należ przed podzieleniem dodać do niej jedynkę. Zatem kolejne, ostatnie już przekształcenie, ma postać: x_kubelek_start = (x_kubelek_start + (x_kubelek_start % 2)) / 2 W końcu udało nam się odnaleźć poszukiwany indeks:) Odnalezienie wartości x_kubelek_end jest analogiczne, dlatego napiszę od razu gotowe wzorki: x_kubelek_end = max(0, liczba_y_kubelkow - abs(wysokosc_planszy - y_kubelek_start - 1) - 2 * leftBoundary / szerokosc_kafla_px + 1) oraz x_kubelek_end = min((x_kubelek_end + (x_kubelek_end % 2)) / 2, ilosc_kafli_w_y_kubelku) Ostatnie makro min zostało dodane na wypadek, gdyby w wyniku obliczeń został wyznaczony indeks elementu wybiegający poza faktyczną ilość elementów w y-kubełku. e) Rysowanie wyznaczonych kafli - praktyczne zastosowanie pomysłuTutaj sprawa jest prosta. Rysowanie implementujemy w dwóch pętlach, jedna rozpoczyna rysowanie w y_kubelek_start a kończy na y_kubelek_end, druga zaś wykonywana jest dla każdego y-kubełka, i rozpoczyna rysowanie od kafla o indeksie x_kubelek_start, a kończy na kaflu x_kubełek_end. Poniżej przedstawiam kolejny fragment kodu tym razem przedstawiający przykładowy sposób rysowania planszy.
RECT rcBoundary; // prostokat opisujacy obszar widoku
// ...
// Procedura rysujaca:
iSize = wysokosc_planszy + szerokosc_planszy - 1;
// Obliczam numery poczatkowego i koncowego y-kubelka
y_kubelek_start = max((2 * rcBoundary.top / wysokosc_pola_px) - 1, 0);
y_kubelek_end = min(1 + (2 * rcBoundary.bottom / wysokosc_pola_px), iSize);
// Petla przechodzi od poczatkowego y-kubelka do koncowego
for(; y_kubelek_start < y_kubelek_end; y_kubelek_start++) {
x_kubelek_start = max(0, iSize - (2 * rcBoundary.right / szerokosc_pola_px) - abs(wysokosc_planszy - y_kubelek_start - 1) - 1);
// Obliczony numer y-kubelka zamieniamy na index tablicy (wektora)
x_kubelek_start = (x_kubelek_start + (x_kubelek_start % 2)) / 2;
// Powtorz powyzsze obliczenia dla pozyskania indeksu elementu na ktorym konczymy rysowanie
x_kubelek_end = max(0, iSize - (2 * rcBoundary.left / szerokosc_pola_px) - abs(wysokosc_planszy - y_kubelek_start - 1) + 1);
x_kubelek_end = min((x_kubelek_end + (x_kubelek_end % 2)) / 2, ppTiles[y_kubelek_start]->size());
// Rysuj wyznaczone kafle z obecnego x-kubelka
for(; x_kubelek_start < x_kubelek_end; x_kubelek_start++)
DrawTile(hdc, (*ppTiles[y_kubelek_start])[x_kubelek_start]);
}
// ...
I oto dotarliśmy do końca naszych rozważań. Jak obiecywałem na początku, metoda ma złożoność stałą, oraz nie wykorzystuje żadnych dodatkowych zasobów pamięci. Może się jednak zdarzyć, że zostaną wyznaczone kafle, które jednak nie są widoczne w obszarze widoku (rysunek 8 zaznacza te obszary kolorem jasnozielonym), jednak w najgorszym przypadku będą to tylko cztery kafle.  Rysunek 7 4. Od autoraMam nadzieję, że artykuł wyjaśnił Ci na czym polega opisywany pomysł. Starałem się go opisać w możliwie przystępnej formie, nie pozostawiającej żadnej wątpliwości. Jeśli jednak masz pytania lub sugestie dotyczące artykułu, to bardzo proszę o kontakt poprzez mój adres e-mail. r.Q 5. Załączniki[1] ClippingDemo - program (+ źródła) dla systemu Windows demostrujący działanie opisywanej metody [30 KB] |
|
