Warsztat.GDCompo!ProjektyMediaArtykułyQ&AForumOferty pracyPobieranie

Opisz napotkaną sytuację, a redakcja niezwłocznie znajdzie rozwiązanie!

wyślij anuluj

System widoczności w grach strategicznych

Tekst został importowany z Warsztatowych artykułów. Jego oryginalnym autorem jest Michał Młoźniak. Jeżeli został importowany poprawnie, usuń ten szablon!

Wstęp

Chyba każda gra strategiczna wykorzystuje linię widoczności i mgłę wojny do znajdowania jednostek i budynków na mapie. W tym artykule mam zamiar przedstawić bardzo wydajny system widoczności, który będzie m.in. realizował te dwa zagadnienia. Zasada jego działania oparta jest na podziale świata gry na małe fragmenty (pola), czyli stworzenie dwuwymiarowej tablicy tzw. mapy widoczności. Każdy jej element będzie odpowiadał jednemu polu mapy.

Stworzony w ten sposób system widoczności będzie obsługiwał w tym samym czasie do 16 graczy, umożliwiał wymianę danych między nimi, zapewniał szybkie wyszukiwanie jednostek, umożliwiał zmienianie rozmiarów mapy i promieni wyszukiwania oraz dodawanie nowych jednostek.

Co to jest LOS?

LOS (z ang. Line of Sight) - linia widoczności to obszar wokół jednostki, który jest dla niej widoczny.

Co to jest FOW?

FOW (z ang. Fog of War) - obszar odkryty ale nie znajdujący się w polu widoczności jednostek.


Rys. 1

Na rysunku czerwone pole to miejsce, gdzie znajduje się jednostka. Białe pole to linia widoczności jednostki, szare to mgła wojny natomiast czarne to pole niewidoczne dla jednostki.

Mapa widoczności

Pierwszą rzeczą jaką należy zrobić to stworzyć tablicę dwuwymiarową, która będzie naszą mapą widoczności. Na początek zaczniemy od obsługi jednego gracza.

int MapOfSight[MAP_X][MAP_Y];

Nie musi ona być tworzona dokładnie w taki sposób, ważne aby miała tyle elementów ile pól na mapie. Każdy element zawiera informacje o tym ile jednostek gracza widzi to pole. W momencie tworzenia jednostki lub jej przemieszczenia na nowe pole należy zwiększyć wartość wszystkich pól widocznych dla tej jednostki. W przypadku śmierci jednostki lub jej przemieszczenia należy zmniejszyć wszystkie wartości pól, które były widoczne dla jednostki przed wykonaniem polecenia. Trzeba jeszcze ustalić jakie wartości powinno przyjmować pole jeżeli kratka nie została jeszcze odkryta i kiedy nie jest widoczna dla gracza. Proponuje aby 0 oznaczało pole odkryte ale niewidoczne, natomiast liczba ujemna np. -1 pole nie odkryte. Typ int może przechowywać liczby z zakresu <-32768,32767> więc powinno to wystarczyć. Nie spotkałem jeszcze gry, która obsługuje 32 tys. jednostek.

Jak zwiększać wartości pól?

Jednostki mają na ogół linie widoczności w kształcie koła o pewnym promieniu liczonym w kratkach (na rys. 1 jednostka ma promień równy 2). Aby policzyć taki kształt wiele gier buduje kwadrat o boku dwa razy dłuższym od promienia i dla każdego pola znajdującego się wewnątrz kwadratu sprawdza czy odległość tej kratki od jednostki jest mniejsza lub równa promieniowi. Jest to prosta metoda ale dosyć czasochłonna, takie zwiększanie wartości pól będzie się odbywało kilkaset razy w ciągu jednej klatki. Lepszym rozwiązaniem jest stworzenie szablonów widoczności. Może to być np. taka tablica:

0000000
0001000
0011100
0111110
0011100
0001000
0000000

Dla uproszczenia przykładu załóżmy, że tablica jest indeksowana od -3 do 3.

W środku znajduje się jednostka, wszystkie jedynki oznaczają, że to pole jest widoczne dla jednostki. Przykładowe zwiększenie wartości pól można zapisać: for (i=-3; i<=3 i++) for (j=-3; j<=3; j++) { if ((MapOfSight[PozXJednostki+i][PozYJednostki+j]<0) && (Szablon[i][j]==1)) MapOfSight[PozXJednostki+i][PozYJednostki+j]=1 else MapOfSight[PozXJednostki+i][PozYJednostki+j]+=Szablon[i][j]; }

Analogicznie wygląda zmniejszanie wartości należy zamiast += napisać -= i nie trzeba uwzględniać czy wartość pola jest ujemna.

Jeszcze lepszym rozwiązaniem jest szablon złożony z poziomych pasków. Jest to lista struktur, zawierających takie informacje jak początek paska, koniec paska i położenie w pionie:

struct { int p,k,y; } Pasek;

Dalej tworzymy listę pasków

list<Pasek> Szablon;

Zamiast pasków można także przechowywać listę punktów. Takie rozwiązanie pozwala zaoszczędzić trochę pamięci w przypadku tworzenia większych szablonów. Ogólnie metoda tworzenia szablonów jest bardzo użyteczna ponieważ pozwala tworzyć obszary widoczności o różnych promieniach a także o różnych kształtach np. taki obszar gdzie widoczne będą tylko pola znajdujące się przed jednostką. Każda jednostka może posiadać wiele szablonów widoczności i podczas gry zamieniać je np. po wejściu jednostki na wzniesienie jej promień widoczności powinien się zwiększyć, natomiast przy wejściu do lasu zmniejszyć. W tej sytuacji wystarczy ustawić tylko odpowiedni szablon. Szablony można tworzyć w plikach tekstowych a następnie wczytywać je do programu. Jest to więc bardzo elastyczny system, który daje możliwość wprowadzania zmian bez ponownej kompilacji programu.

Kolejna optymalizacja

Można łatwo zauważyć, że za każdym razem gdy jednostka zmienia położenie musimy zmniejszyć wartości pól dla starego położenia a następnie zwiększyć dla nowego położenia. Nasze jednostki poruszają się po planszy z jednego pola do drugiego a więc przy zmniejszaniu i zwiększaniu wartości pól większość z nich się pokrywa, czyli najpierw zmniejszamy jedno pole a potem znowu je zwiększamy. Biorąc pod uwagę, że operacje te są wykonywane bardzo często, zwalniają one znacząco grę. Usprawnienie tej metody polega na aktualizowaniu tylko tych pól, które się nie pokrywają. Tutaj też można stworzyć szablony, w których zapamiętamy które pola należy aktualizować. Takie rozwiązanie powinno przyśpieszyć działanie systemu widoczności.

Więcej graczy

Na razie stworzyliśmy mapę widoczności, która obsługuje tylko jednego gracza. Teraz musimy stworzyć połączoną mapę widoczności dla wszystkich 16 graczy. Jest to także tablica o rozmiarach jakie ma mapa gry lecz każdy element tej tablicy musi być wartością 32-bitową. Każde dwa bity są przeznaczone dla jednego gracza. Pierwszy bit zawiera informacje czy dane pole zostało odkryte przez gracza, a drugi czy jest dla niego widoczne. Aby wyłuskać pojedynczą informacje o danym polu musimy użyć operacji na bitach. Zakładam na początku, że gracze są ponumerowani od 0 do 15. Oto kod sprawdzający czy dane pole (x,y) zostało odkryte przez gracza z:

if (MapOfSight[x][y] & (1 << (z*2+1)))==1 return true else return false;

A teraz czy to pole jest dla gracza widoczne:

if (MapOfSight[x][y] & (1 << (z*2)))==1 return true else return false;

Powyższy kod opiera się na funkcji sprawdzającej wartości poszczególnych bitów w liczbie:

Liczba & (1 << NumerBitu)

Przykład:

Mamy liczbę 101011 i chcemy sprawdzić wartość trzeciego bitu (właściwie czwartego ponieważ bity numeruje się od 0 i od prawej strony). Najpierw dokonujemy przesunięcia bitowego w lewo tyle razy ile wynosi numer bitu. Operacja przesunięcia o jeden w lewo to inaczej pomnożenie przez dwa ale jest znacznie szybsza od mnożenia. Czyli 0001 << 3 = 1000. Następnie wykonujemy operację AND czyli mamy 101011 & 1000

101011 &
001000 =
001000

Wyszła prawda, czyli trzeci bit jest ustawiony na true. W taki sposób działa wydobywanie informacji z mapy widoczności. Aby ustawić jakiś bit na podaną wartość postępujemy tak samo jak przy wydobywaniu informacji ale używamy operacji OR zamiast AND. System ten pozwala także tworzyć wiele ciekawych efektów. Umożliwia sprawdzanie kilku wartości naraz. Chodzi mi o to, że można w jednej chwili sprawdzić czy dane pole jest widoczne dla 1, 4 i 11 gracza. Możliwe są różne kombinacje wystarczy tylko odpowiednio łączyć maski widoczności aby sprawdzały odpowiednie wartości. W tej chwili system widoczności jest w stanie obsługiwać do 16 graczy, jednak liczbę graczy można zmniejszyć i przechowywać dodatkowe informacje np. czy dane pole jest zaopatrzone w energię elektryczną. Wykorzystuje się do tego mapę widoczności. Na każdego gracza będzie przypadał jeszcze jeden bit, mówiący czy dane pole jest w zasięgu elektrowni czy innego źródła energii. Można dodawać różne informacje wedle własnych życzeń, najlepiej jednak aby ilość bitów przypadająca na jednego gracza była potęgą dwójki np. 2, 4, 8 co daje odpowiednią liczbę obsługiwanych graczy: 16, 8, 4.

Bardziej realistyczny system widoczności

Zauważyłem w kilku grach, że kiedy jednostka podejdzie do muru to i tak widzi obszar znajdujący się za nim co raczej nie odpowiada rzeczywistości(chyba, że jednostka jest wyższa od muru). Aby jednostka widziała bardziej realistycznie należy szablon widoczności modyfikować w zależności od ukształtowania terenu i znajdujących się na nim obiektów. Taki sposób jest oczywiście wolniejszy niż standardowe rozwiązanie, lecz według mnie warto trochę zwolnić grę aby wyglądała bardziej realistycznie.

Zastosowanie mapy widoczności w systemie sztucznej inteligencji

Dzięki systemowi widoczności możemy usprawnić wyszukiwanie przez sztuczną inteligencję jednostek lub innych interesujących obiektów. Normalnie szukanie jednostek polega na sprawdzaniu wszystkich pól, które znajdują się w polu widzenia danej jednostki. W ten sposób czas wykonywania tej operacji wzrasta proporcjonalnie do ilości posiadanych jednostek. Dodatkowo przy sprawdzaniu większość widocznych klatek jest pusta więc marnuje się tylko czas procesora na niepotrzebne obliczenia. Szybszy sposób polega na przechowywaniu na liście jakie jednostki znajdują się w polu widzenia danego. Można je podzielić pod względem rodzaju jednostek. Dzięki temu każdy gracz otrzyma kilka list na których będą znajdowały się jednostki będące w jego polu widzenia. Jedna lista może np. przechowywać wrogie jednostki, a druga jednostki sojusznicze. Teraz wyszukiwanie sprowadza się tylko do przeszukiwania odpowiednich list. Jak jednak je tworzyć? Jest to bardzo proste. Każda jednostka sprawdza czy pole, na którym aktualnie się znajduje jest widoczne dla jakiegokolwiek gracza. Jeżeli tak to dodaje się do odpowiedniej listy. Jeżeli jednostka z pola widzenia jakiegoś gracza to usuwa się z odpowiedniej listy. Dobrą rzeczą jest przechowywanie dla każdej jednostki informacji o widoczności z poprzedniej klatki. Wtedy będziemy aktualizować dane jeżeli wartość widoczności uległa zmianie od ostatniej klatki. Taka metoda wyszukiwanie jest bardzo szybko, pozwala na wyszukiwanie jednostek w całym polu widoczności a nie tylko w promieniu wyszukiwania.

Podsumowanie

To już koniec. Mam nadzieje, że w miarę zrozumiale przedstawiłem jak stworzyć wydajny system widoczności i jak wykorzystać go w systemie AI. W planie mam jeszcze kilka artykułów na temat sztucznej inteligencji. Jeśli macie jakieś pytania lub uwagi, piszcie do mnie.

Autor: Michał Młoźniak
Data: 15 stycznia 2003

Tekst dodał:
Adam Sawicki
09.04.2006 18:15

Ostatnia edycja:
Adam Sawicki
09.04.2006 18:15

Kategorie:

Aby edytować tekst, musisz się zalogować.

# Edytuj Porównaj Czas Autor Rozmiar
#1 edytuj 09.04.2006 18:15 Adam Sawicki 11.88 KB
Zwykły
Do sprawdzenia
Do akceptacji
  • Wine (@Wine) 06 kwietnia 2010 15:09
    Czemu wykorzystujesz poszczególne bity liczby jak można skorzystać ze vector<char>* i mieć prawie nieogrniczoną liczbę graczy?

    *char ponieważ bool nie przejdzie (błędy kompilacji)
  • Napisz komentarz:
    Aby dodać swój komentarz, musisz się zalogować.
Licencja Creative Commons

Warsztat używa plików cookies. | Copyright © 2006-2017 Warsztat · Kontakt · Regulamin i polityka prywatności
build #ff080b4740 (Tue Mar 25 11:39:28 CET 2014)