Autor Wątek: Wykrywanie 'spotykania sie' obiektow w serwerze MMO.  (Przeczytany 3741 razy)

Offline waz0n

  • Użytkownik

# Sierpień 22, 2008, 20:39:27
Witam,
Aktualnie zajmuje się developingiem serwera gry MMORPG (emulatorem :)). Wszystko do tej pory szło gładko, ale zabrakło mi pomyslu na wydajny mechanizm 'spotykania sie' graczy i potworow.

Obiekty w swojej grze przechowuje w tablicy. Typem danych tej tablicy jest specjalna struktura. Kazdy obiekt ma swoj unikalny indeks, co wynika z faktu korzystania z tablicy :). Tablica ma rozmiar 7400 obiektow - 6400 potworow, 1000 graczy.

Pod terminem 'spotykanie sie' rozumiem:
Przypuscmy, ze gracz przemierza mape (Mapa 255x255, pole widzenia 15x15). Po mapce mozna poruszac sie w osiach X i Y (takze wystepuja tylko dwa koordynaty mapy: X i Y). Przy kazdym ruchu gracza wysylana jest do serwera cala sciezka, ktora postac zamierza przejsc.

Teraz moj problem:
W jaki sposob wydajnie wykryc spotkanie sie dwoch lub wiecej obiektow (wejscie w swoje pole widzenia) i rozstanie sie (wyjscie ze swojego pola widzenia). Jedyne, co przychodzi mi na mysl to, petla z 7400 iteracjami, ktora bedzie sprawdzac roznice koordynatow i wysylac odpowiednie informacje na temat pola widzenia. Jednak mam opory przed tym rozwiazaniem, bo z 7400 iteracjami, 1000 graczami i pakietami ruchu wysylanymi co ~200ms nie jest to rozwiazanie racjonalne.

Nie prosze o kod zrodlowy tylko o jakies pomysly (wlasne lub z innych serwerow MMORGP), chociaz nie obraze sie, jesli ktos zarzuci jakims kodem zrodlowym lub pseudo kodem :P.

Z gory bardzo dziekuje za jakiekolwiek pomysly i pozdrawiam!

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline BTM

  • Użytkownik

# Sierpień 22, 2008, 20:43:08
Nie koniecznie musisz mieć 7500 "ciężkich" iteracji - przecież (zakładając, że wszystkie obiekty mają ten sam zakres widzenia) to jeżeli obiekt nic nie widzi, to nic nie widzi jego.

Czyli nie masz 7500 x 7499 sprawdzeń (każdy z 7500 obiektów sprawdza czy widzi pozostałe 7499), tylko trochę mniej :D

Offline yarpen

  • Użytkownik

# Sierpień 22, 2008, 20:44:29
Poczytaj o podziale przestrzeni.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Sierpień 22, 2008, 20:50:22
Podziel całą mapę na kafle 8x8 i zrób dla każdego kafla dynamiczną listę tego, co się w nim znajduje (dwa nowe pola do obiektu - wskaźnik na następny i poprzedni, nie radzę robić nowych dynamicznych struktur specjalnie pod to). Każdy obiekt podczas ruchu sprawdza, czy zmienił się mu "megakafel" i jeżeli tak, to się wyprzęga z jednej listy, a wprzęga do drugiej. Teraz sprawdzenie potencjalnej widoczności z danego miejsca to 3x3 sprawdzenia kafli. :)

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Sierpień 22, 2008, 22:29:14
Ogólnie to trzeba zastosować jakąś strukturę danych spod szyldu podział przestrzeni. Niektóre możliwości to:

- Kafle, o których napisał Krzysiek K.
- Drzewa czwórkowe (quadtree)
- BSP
- K-d tree

Offline Kos

  • Użytkownik
    • kos.gd

# Sierpień 22, 2008, 22:48:33
Jeśli masz dużo obiektów rozsianych po przestrzeni i chcesz wcześnie odsiać znaczną wielkość "sprawdzeń", to jakiś rodzaj drzewa jest wręcz naturalnym zastępstwem dla zwykłej tablicy. Takie informacje przydają się nie tylko do logiki, ale też np. do widoczności grafiki.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Sierpień 22, 2008, 23:08:04
Cytuj
- Drzewa czwórkowe (quadtree)
- BSP
- K-d tree
Jak dla mnie do tego celu nieco przebajerzone. Dla mapy 255x255 stracisz na obsługę dodatkowej tablicy raptem 4kB + 8B na każdy obiekt i masz wyszukiwanie obiektów praktycznie w czasie stałym. Bardziej zaawansowane struktury danych przydają się wtedy, gdy mamy bardziej nietypowe zapytania (np. poszukiwanie obiektów w frustum) lub bardziej złożony problem (np. wyszukiwanie trójkątów w triangle meshu). :)

Offline waz0n

  • Użytkownik

# Sierpień 23, 2008, 23:52:38
Tylko jak podzielic mapke na te kafle?

Jak juz mowilem mapka to kwadrat 255x255. Mapa odwzorowana jest w kodzie jako klasa:

#define MAP_WIDTH 255
#define MAP_HEIGHT 255

class CMap {
public:
bool CheckStandAttr(unsigned char uPosX, unsigned char uPosY);

inline int getMapNumber() { return m_aMapNumber; }
inline void setMapNumber(int aMapNumber) { m_aMapNumber = aMapNumber; }

unsigned char m_uMapAttr[MAP_WIDTH * MAP_HEIGHT];

private:
int m_aMapNumber;
};

tablica m_uMapAttr przechowuje kazdy punkt mapy. Punkt moze miec jeden z kilku atrybutow:

enum MAP_ATTR_ENUM {
ATTR_GROUND = 0,
ATTR_GROUND_NONGROUND = 5,
ATTR_SAFEZONE = 1,
ATTR_SAFEZONE_NONGROUND = 4,
};

Chodzic mozna tylko po ATTR_GROUND i ATTR_SAFEZONE.

Teraz w jaki sposob podzielic ta mapke 255x255 na kafle(sektory?), aby pokryc cala mape. Kafel ma byc jakims kontenerem, ktory przechowywac bedzie indeksy obiektow?

Gat-demet-szit, nigdy nie robilem takich rzeczy i dlatego tak pytam. NIe chce odwalic fuszerki tylko zastosowac optymalne, schludne i popularne rozwiazanie. Czy na lamach warsztatu sa jakies artykuly odnosnie implementacji takich rozwiazan lub objasnienie ich idei (cos w stylu path findingu/wlasnego jezyka skryptowego). Slowo kafle zwraca bardzo roznorodne wyniki.

Z gory dziekuje za pomoc.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Sierpień 23, 2008, 23:58:27
Mapy nie musisz na nic dzielić. Wystarczy że podzielisz logicznie wszystkie obiekty ruchome. :)

Offline yomyn

  • Użytkownik
    • yomyn::dev

# Sierpień 23, 2008, 23:59:28
Ale po co sprawdzac 7400 obiektow? Co nas obchodza potwory? Chyba ze potwory tez ze soba oddzialuja nawet jak gracz tego nie widzi, ale takto nie wiedze sensu sprawdzania tego dla potworow a jedynie dla 1000 graczy. Chyba ze czegos nie zajarzylem ^^.

-yomyn

Offline waz0n

  • Użytkownik

# Sierpień 24, 2008, 00:04:47
Nie, potwory miedzy soba nie oddzialuja, ale gracz tez musi je widziec :).

Offline Kos

  • Użytkownik
    • kos.gd

# Sierpień 24, 2008, 12:54:22
A powinny, bo inaczej będą sobie swobodnie łazić jeden po drugim, jak to zwykle bywa w darmowych koreańskich MMO :)

Offline waz0n

  • Użytkownik

# Sierpień 24, 2008, 20:08:46
Wymyslilem taki podzial mapki na kafelki:

http://img148.imageshack.us/img148/9639/tilegs5.jpg

Kazdy kafelek ma rozmiar 15x15. Kafelkow na mapce wyszlo 289 (17 kafelkow w pionie x 17 kafelkow w poziomie). Gracz, aby plynnie spotykac inne obiekty, powinien tez miec dostep do kafli otaczajacych jego aktualny kafelek:

Przypuscmy, ze gracz stoi bardzo blisko krawedzi swojego kafelka i powinien widziec juz, co dzieje sie na sasiednim kafelku, bo jezeli inny obiekt wejdzie na aktualny kafelek gracza, to zostanie wyswietlony nagle 'z nieba' :P.

Czy taki pomysl jest dobry? Jesli tak, to czy istnieja jakies ogolne 'algorytmy' rozwiazania takiego problemu (chodzi mi tutaj o wyznaczenie kafli sasiadujacych)?

Offline djsmtih

  • Użytkownik

# Sierpień 24, 2008, 20:34:02
Niech każdy kafel ma 2 kordynaty np x i z


3,1|3,2|3,3|             
2,1|2,2|3,2|
1,1|2,1|3,1|

Wczytuj tylko te kafle z kordynatami wiekszymi lub mniejszymi max o 1 od kafla w ktorym obiekt sie znajduje.
Edit Lub tymi samymi ofc :P
« Ostatnia zmiana: Sierpień 24, 2008, 20:37:08 wysłana przez djsmtih »

Offline waz0n

  • Użytkownik

# Sierpień 25, 2008, 01:19:36
Ok, powiedzmy, ze wyznaczanie kafli mam juz gotowe.

Przy kazdym ruchu wyznaczam lacznie 9 kafli (jeden kafel, na ktorym stoi postac i osiem go otaczajacych). Zapisuje je w tymczasowej tablicy. W jaki sposob najwydajniej wyznaczyc ze zbioru starych kafli te, ktore nie zawieraja sie w nowym zbiorze? Gdybym dokonal takiego wyznaczenia, to wiedzialbym, na ktorych kaflach w 100% nie widac juz postaci.

Mowiac ogolniej:

Mam dwa dziewięcio elementowe zbiory liczb:

#define COLLECTION_LEN 9

int aCollection1[COLLECTION_LEN] = {3, 7, 11, 32, 44, 312, 8, 1, 19};
int aCollection2[COLLECTION_LEN] = {19, 1, 312, 7, 8, 11, 69, 67, 31};

Czy istnieje taka metoda, ktora wyznaczylaby elementy rozne dla obu tych zbiorow? Mi na mysl przychodzi tylko upakowanie ktoregos ze zbioru do std::set i pozniej za pomoca .find() po kolei szukac roznych elementow. Czy istnieje jakas lepszy sposob :)?

Z gory dzieki za pomoc!