Autor Wątek: Szukanie drogi na dynamicznie zmieniajacaj sie planszy  (Przeczytany 12405 razy)

Offline TheLoader

  • Użytkownik

# Luty 22, 2007, 00:16:57
Interesuje mnie temat szybkiego odnajdywania najkrotszej (lub przynajmniej w miare krotkiej ;) drogi na planszy ktora zmienia sie w czasie dzialania gry. Owy algorytm odnajdywania drogi musi dzialac natychmiastowo [przykladowo aby serwer obslugujacy 1000 graczy mogl znalesc dla nich wszystkich odpowiednie drogi ktoredy maja isc w ciagu 1 sekundy (czyli 1ms na gracza)]. Wiekszosc geometrii na planszy bedzie statyczna - takiej jak domy drzewa itp. Przemieszczac sie beda glownie gracze, a wszystko musi dzialac tak aby nie przechodzili przez siebie.
Interesuje mnie algorytm ktory bedzie mial jak najkrotszy _pesymistyczny_ czas dzialania. Czyli taki czas kiedy bedzie musiala zostac sprawdzona cala plansza a zadnej drogi nie bedzie. Taki przypadek wystapi np wtedy kiedy ktos bedzie chcial wejsc do domku (i kliknie w jego wnetrzu aby jego postac tam poszla), a wczesniej jakas inna postac stanie w drzwiach domku zagradzajac wejscie.
Narazie uzywalem planszy 1000x1000 (to jest jedynie fragment ktory aktualnie jest widoczny na ekranie, nie badam drogi tego co jeszcze nie jest wyswietlane bo ktos nie doszedl do danego fragmentu mapy). Testowalem predkosc dla algorytmu optymalnego dla planszy statycznej (cos ala BFS, w implementacji podobnej do tej http://darkcult.republika.pl/alg/droga.html z tym, ze na moich kolejkach 2.85 raza szybszych niz STLowe). I kiedy szukanej drogi nie bylo czas dzialania algorytmu wynosil 1.75s czyli znacznie za dlugo. Dodam ze moj procesor dziala z predkoscia 1.73Ghz. Moglbym podzielic scene drzewem czworkowym co pewnie znacznie zmniejszylo by ilosc pol(wezlow) ale czy to w ogole nadaje sie do dynamicznej sceny? Kiedy kilka postaci bedzie sie poruszac nie bede przeciez w kazdym kroku dzialania algorytmu przeliczal od nowa drzewa ani nawet nie moge robic uaktualnien wezlow (droga mogla by prowadzic przez wezel ktory skasuje w nastepnym kroku dzialania algorytmu). Co zrobic? Jaki algorytm i strukture danych stosowac? Pomocy.
Aha jakby ktos radzil A* to z gory mowie ze jest wolniejsze dla przypadku pesymistycznego gdy drogi w ogole nie ma bo schodzi sporo czasu na przeliczanie heurystyk, a mnie wlasnie taki przypadek intersuje. Bo co z tego, ze sredni czas poszukiwania drogi to 0.01s kiedy jak ktos trafi na ten wredny przypadek to bedize musial czekac 10s zanim ludzik sie ruszy. Gracz w takim przypadku wkurzyl by sie i gre wylaczyl.

Offline Mr. Spam

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

Offline KriS

  • Użytkownik
    • KriS

# Luty 22, 2007, 00:59:27
Hmm, moze podzielic mape na sektory bedace jakimis figurami wypuklymi. Nastepnie najpierw szukac drogi pomiedzy tymi sektorami, a pozniej szukac dokladnej drogi przy przechodzeniu przez taki sektor. Moze tez jakies potential fields czy cos.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Luty 22, 2007, 02:07:24
Cytuj
[przykladowo aby serwer obslugujacy 1000 graczy mogl znalesc dla nich wszystkich odpowiednie drogi ktoredy maja isc w ciagu 1 sekundy (czyli 1ms na gracza)]
Zrzuć to na klienta i do serwera przesyłaj początek wyznaczonej trasy. Tutaj i tak niekt nie zcheatuje (kolizje sprawdzaj już na serwerze), a zawsze to trochę serwer odciąży. :)

Offline Moriturius

  • Użytkownik

# Luty 22, 2007, 08:51:37
hmm... ja widze 2 proste sposoby -

1) olać szukanie ścieżki i zrobić sterowanie w stylu Diablo - wtedy sprawdzanie kolizji sprowadza sie do sprawdzenia czy pole na ktore chce gracz wejsc nie jest zajete przez innego gracza

2) olać kolizje międzygraczowe - może trochę nierealistycznie będzie wyglądać, ale nie sądzę, aby ktoś miał coś przeciwko temu. W wielu grach już to widziałem i nie zniechęcało ludu do nich ;) [ btw. jak jakiś gracz będzie stał w przejściu a ten drugi wogóle nie będzie mógł wejść to też nie będzie szczęśliwy ]

Teraz mi przyszedł do głowy jeszcze jeden pomysł. Nie wiem czy jest w ogóle do wykonania ale myślę o tym, żeby podzielić pola na mapie na dostępne i niedostępne. Tzn oczywiście relatywnie ponieważ ktoś znajdujący się w domku byłby "zamknięty" w jego przestrzeni. W tym wypadku trzeba by zrobić jakiś algorytm dzielenia tych pól i sprawdzania tych 'regionów' świata.

Jak mówię - nie wiem czy to w ogóle wykonalne i ja po prostu zrezygnowałbym z kolizji między graczami ;D

Offline TheLoader

  • Użytkownik

# Luty 22, 2007, 13:10:52
Hmm, moze podzielic mape na sektory bedace jakimis figurami wypuklymi. Nastepnie najpierw szukac drogi pomiedzy tymi sektorami, a pozniej szukac dokladnej drogi przy przechodzeniu przez taki sektor.
Tak, to jest standardowy pomysl przyspieszenia A*, tylko nie bardzo wiem jak moglby wygladac w moim przypadku. Bo dzielenie, ma sens kiedy przestrzen da sie jakos naturalnie podzielic na odcinki czy sektory. Przytocze przyklad z perelek. Sa dwa zamki w obcych Panstwach. Chcemy dostac sie z komnaty tronowej zamku A, do komnaty odwiedzin zamku B znajdujacego sie w osobnym panstwie. Tutaj mozemy najpierw odpalic algorytm aby znalazl droge do wyjscia z zamku A, pozniej odpalic algorytm aby znalazl droge z wyjscia zamku A do granicy Panstwa, nastepnie odpalic go tak aby znalazl droge od granicy do wejscia zamku B, i czwarty raz od wejscia zamku B do komnaty odwiedzin. Tutaj taki podzial jest naturalny. Ale u mnie jest zwykla jednolita otwarta plansza na ktorej sa jakies przeszkody typu lawki itd. oraz oczywiscie ludzie. Moze sie zdarzyc, ze nawet otoczy nas paru gosci i nie bedziemy mogli sie ruszyc, wiec jak tutaj rozmiescic te sektory? Jakos nie bardzo moge sobie to wyobrazic. Powiedzmy, ze mape 1000x1000 podziele rowno na 25 kwadratow 200x200 kazdy. No i najpierw szukam przejscia w srod tych 25 kwadratow, a pozniej lokalnie w 200x200. Ale szukajac drogi w tych 25 kwadratach skad mialbym wiedziec gdzie jest przejscie a gdzie nie? Moglbym to obliczyc wczesniej, przed odpaleniem gry dla geometrii statycznej ale przeciez pozniej jakas postac/postacie moga stanac na laczeniu owych sektorow i juz przejscia nie bedzie. Nie wyobrazam sobie jakos weryfikowania tego w czasie rzeczywistym dla calej planszy. I druga sprawa. Moze sie przeciez zdarzyc tak, ze szukajac przejscia tym juz mniejszym kwadracie 200x200 w ogole go nie znajdziemy, bo algorytm nie bedzie uwzgledniac ze bedzie trzeba isc po granicy dwoch sektorow aby dojsc do celu. Poprostu przesmyk bedzie tak wązki, ze rozpatrujac tylko jeden sektor nie bedzie przejscia (postac nie zmiesci sie), ale idac po granicy sektorow przejscie bedzie juz wystarczajaco szerokie.
Mozesz napisac dokladniej jak Ty widzisz takie rozwiazanie?
Moze tez jakies potential fields czy cos.
Mozesz napisac konkretniej co masz na mysli w tym kontekscie?

Cytat: Krzysiek K.
Zrzuć to na klienta i do serwera przesyłaj początek wyznaczonej trasy. Tutaj i tak niekt nie zcheatuje (kolizje sprawdzaj już na serwerze), a zawsze to trochę serwer odciąży.
To jest dobry pomysl. Moge nawet w calosci liczyc trase na klientach a nastepnie przesylac do serwera (tylko serwer zna aktualne polozenie wszystkich obiektow, gracze maja lagi, a nawet opoznienia wynikajace ze zwyklych opozniej w sieci) ja w celu weryfikacji. Serwer bedzie weryfikowal czy trasa jest poprawna i odpowiadal klientowi. Zwiekszy to znacznie ilosc przesylanych danych, ale z  tym moge sobie juz radzic roznymi sztuczkami, pakowaniem pakietow itd.
Tylko, ze to nadal nie rozwiazuje problemu. Jak juz wspomnialem w obecnej sytuacji dla STATYCZNEJ planszy wszystko liczy sie 1.75s czyli i tak za dlugo. Jak dojdzie 100 dynamicznych graczy to wszystko zwolni kilka razy. Takie opoznienia sa nieakceptowalne. Jeszcze do tego trzeba dodac rendering przeplatany z liczeniem. Bo przeciez jak cos sie bedzie liczyc nawet 0.5s to nie moge tego przeliczyc w jednym przebiegu gry. Musze liczyc kawalek, renderowac, znowu liczyc kawalek, renderowac itd. Albo odpalic w osobnym watku. A, ze rendering tez swoje trwa wszystko dodatkowo zwolni.  Musze znacznie to przyspieszyc z sytuacji ktora mam obecnie.
Cytat: Moriturius
olać szukanie ścieżki i zrobić sterowanie w stylu Diablo - wtedy sprawdzanie kolizji sprowadza sie do sprawdzenia czy pole na ktore chce gracz wejsc nie jest zajete przez innego gracza
Sorry, ale nie gralem nigdy w diablo. Moglbys w 2 slowach opisac co masz na mysli?
Cytat: Moriturius
olać kolizje międzygraczowe - może trochę nierealistycznie będzie wyglądać, ale nie sądzę, aby ktoś miał coś przeciwko temu. W wielu grach już to widziałem i nie zniechęcało ludu do nich  [ btw. jak jakiś gracz będzie stał w przejściu a ten drugi wogóle nie będzie mógł wejść to też nie będzie szczęśliwy ]
No niestety opcja olania kolizji mieczy graczowych odpada. W obecnej wersji gry mam takie rozwiazanie i niestety ludzie skarza sie. Teraz zabieram sie za nowy silnik i musze wprowadzic ten element. Wszystko jest juz przemyslane jesli chodzi o gameplay. Jak gracz bedzie stal w przejsciu i niebedzie chcial Cie przepuscic to bedziesz mogl wyslac specjalne ostrzezenie, a jesli na nie nie zareaguje to go zaatakowac niezaleznie od lokacji w ktorej sie znajdujesz, jego levelu itd.
I tutaj mam jedna wazna prosbe. Nie rozmawiajmy wiecej o gameplayu ani o tym czy jest sens w ogole robic kolizje miedzy graczami. Moim zdaniem jest i tego dotyczny ten temat. Nie robmy offtopa please.
Cytat: Moriturius
Teraz mi przyszedł do głowy jeszcze jeden pomysł. Nie wiem czy jest w ogóle do wykonania ale myślę o tym, żeby podzielić pola na mapie na dostępne i niedostępne. Tzn oczywiście relatywnie ponieważ ktoś znajdujący się w domku byłby "zamknięty" w jego przestrzeni. W tym wypadku trzeba by zrobić jakiś algorytm dzielenia tych pól i sprawdzania tych 'regionów' świata
Hmm, nie bardzo wiem jak to widzisz. Moglbys opisac to dokladniej? Bo jak np. otoczylo by Cie 4 drabów i nie moglbys sie ruszyc jak rozpoznal bys, ze cala plansza to sa "pola niedostepne"? Jak taki algorytm mialby dzialac? Nie bardzo wiem. To wlasnie robi BFS, czy A*. Nie da sie z "palca" moim zdaniem sprawdzic ktore pola sa dostepne na planszy a ktore nie. Przyklad z domkiem to tylko jenda z wielu mozliwosci. Odciac droge moga tez przeciez ludzie ktorzy sie ustawia do okola Ciebie, badz przy wyjsciu z jakiejs slepej uliczki na planszy itd. itp.

Offline mINA87

  • Użytkownik

# Luty 22, 2007, 13:30:21
A może warto pomyśleć o jakimś rozwiązaniu zachłannym? Pregenerować graf potencjalnie dostępnych miejsc, oznaczać wierzchołki w jakimś promieniu jako dostępne lub nie i starać się iść po "optymalnej drodze" czyli w lini prostej po grafie, omijając przeszkody, możnaby zastosować trochę randomalizacji(jednak wybór omijań musiałby być pamiętany, by w razie w możnabyło wrócić i sprawdzić inną ściechę) i heurestyki aby robić predykcję ruchów w promieniu widoczności  - może coś takiego miałoby szansę działać? Tak w sumie postępujemy my - ludzie i w sumie działa to ^^ W HLu 2 nie wiem czy czasem nie robią podobnie IIRC. Dla małych odległości powinno to być szybkie i poprawne. Dla bardziej skomplikowanych postać będzie się obijać i krążyć - nie wiem czy właśnie o tym czasem nie mówisz gdy piszesz, że na to się skarżą gracze.

Offline Gloggie

  • Użytkownik

# Luty 22, 2007, 13:33:53
Tak się z ciekawości spytam - to blokowanie się graczy nawzajem to ma być 'ficzer' twojej gry? Mnie to by generalnie denerwowało :)

Jeżeli chcesz po prostu uniknąć nachodzenia się postaci to pozwól klientom na lokalne przesuwanie blokujących graczy. W sensie - klient wie, że jest kolizja i na czas przejścia gracza lokalnego lekko animuje odsunięcie się innych graczy, po czym wszyscy wracają na swoje miejsca. To przesunięcie było by czysto lokalne i żadna inna maszyna w sieci by o tym nie wiedziała.

Bo inaczej to ja nie widzę praktyczengo rozwiązania tego problemu. Co z tego że w czasie t0 masz znalezioną ścieżkę przez wąskie gardło mapy, skoro zanim gracz tam dojdzie w t1 to się położenie innych postaci może całkowicie zmienić?

Offline mINA87

  • Użytkownik

# Luty 22, 2007, 13:44:34
Tak się z ciekawości spytam - to blokowanie się graczy nawzajem to ma być 'ficzer' twojej gry? Mnie to by generalnie denerwowało :)

Jeżeli chcesz po prostu uniknąć nachodzenia się postaci to pozwól klientom na lokalne przesuwanie blokujących graczy. W sensie - klient wie, że jest kolizja i na czas przejścia gracza lokalnego lekko animuje odsunięcie się innych graczy, po czym wszyscy wracają na swoje miejsca. To przesunięcie było by czysto lokalne i żadna inna maszyna w sieci by o tym nie wiedziała.

Bo inaczej to ja nie widzę praktyczengo rozwiązania tego problemu. Co z tego że w czasie t0 masz znalezioną ścieżkę przez wąskie gardło mapy, skoro zanim gracz tam dojdzie w t1 to się położenie innych postaci może całkowicie zmienić?

Główny i podstawowy problem (pomijając kwestie fabuły, gdyż scenariusz może być trudniej zrealizować jeśli jakaś postać nie będzie mogła zablokować drogi itp) to potencjalne bugi. Jak Ci się odsunie postać która stoi w wąskim przejściu, to prawdopodobnie wyląduje w ścianie x].

Offline Gloggie

  • Użytkownik

# Luty 22, 2007, 13:55:55
Ale kto każe odsuwać przeszkadzajki po chamsku w bok :) ? Sposób przesuwania może być bardziej fiinezyjny.

A co do osób nieprzesuwalnych - jeżeli scenariusz by tego wymagał, to nie sądzę aby to byli akurat inni gracze. Prędzej NPC, a wtedy mozna ich traktować jako statyczny element mapy.

Offline TheLoader

  • Użytkownik

# Luty 22, 2007, 14:02:44
Tak się z ciekawości spytam - to blokowanie się graczy nawzajem to ma być 'ficzer' twojej gry? Mnie to by generalnie denerwowało :)

Jeżeli chcesz po prostu uniknąć nachodzenia się postaci to pozwól klientom na lokalne przesuwanie blokujących graczy. W sensie - klient wie, że jest kolizja i na czas przejścia gracza lokalnego lekko animuje odsunięcie się innych graczy, po czym wszyscy wracają na swoje miejsca. To przesunięcie było by czysto lokalne i żadna inna maszyna w sieci by o tym nie wiedziała.

Bo inaczej to ja nie widzę praktyczengo rozwiązania tego problemu. Co z tego że w czasie t0 masz znalezioną ścieżkę przez wąskie gardło mapy, skoro zanim gracz tam dojdzie w t1 to się położenie innych postaci może całkowicie zmienić?

Główny i podstawowy problem (pomijając kwestie fabuły, gdyż scenariusz może być trudniej zrealizować jeśli jakaś postać nie będzie mogła zablokować drogi itp) to potencjalne bugi. Jak Ci się odsunie postać która stoi w wąskim przejściu, to prawdopodobnie wyląduje w ścianie x].
Tak, zgadzam sie. Tez jakos nie widze tego sposobu. Jeszcze na otwartej przestrzeni to mozna by przesuwac goscia po scianie tak zeby nie wszedl w nia. Ale co jesli wejdziemy do domku wypchanego ludzmi po brzegi? Tutaj juz ktorys musi wyladowac w scianie na 100%. Inna sprawa. Wyobrazmy sobie dwoch gosci stojacych obok siebie i naparzajacych sie z piesci. Raz wali jeden raz drugi. Na zmiane stoja sobie i sie wala po mordach:
XY
X to jeden gosc, Y to drugi.
I teraz Przychodzisz Ty z kierunku dolnego lub gornego
XZY
Z to jestes Ty. No i jak to ma dzialac? Oni przestaja  sie bic (to bez sensu, przeciez musi byc odejmowana im energia, bo inni gracze by nawet nie wiedzieli, ze oni sie odsuneli - sam mowiles ze lokalnie). Nie moga tez sie bic walac w Ciebie bo to Tobie w takim przypadku powinna byc odejmowana energia nie im. Itd. Jest pelno takich przypadkow. Poprostu nie widze tego rozwiazania w praktyce.

Cytat: mINA87
A może warto pomyśleć o jakimś rozwiązaniu zachłannym? Pregenerować graf potencjalnie dostępnych miejsc, oznaczać wierzchołki w jakimś promieniu jako dostępne lub nie i starać się iść po "optymalnej drodze" czyli w lini prostej po grafie, omijając przeszkody, możnaby zastosować trochę randomalizacji(jednak wybór omijań musiałby być pamiętany, by w razie w możnabyło wrócić i sprawdzić inną ściechę) i heurestyki aby robić predykcję ruchów w promieniu widoczności  - może coś takiego miałoby szansę działać? Tak w sumie postępujemy my - ludzie i w sumie działa to ^^ W HLu 2 nie wiem czy czasem nie robią podobnie IIRC. Dla małych odległości powinno to być szybkie i poprawne. Dla bardziej skomplikowanych postać będzie się obijać i krążyć - nie wiem czy właśnie o tym czasem nie mówisz gdy piszesz, że na to się skarżą gracze.
No dobrze, ale w takim przypadku przeciez droga bedzie obliczana na bierzaco u klienta w raz z tym kiedy przemieszcza sie po planszy. A serwer nie bedzie w danym momencie wiedzial nawet dokladnie gdzie znajduje sie gracz. Chodzi oto, zeby serwer wiedzial pierwszy jaka droga bedzie poruszal sie klient. Bo w takim przypadku to stanie sie nastepujaca rzecz.
Przemieszczasz sie z punku A do B ktore sa blisko siebie. Na Twoim kompie jestes juz w punkcie B (rednerujesz swoja postac w punkcie B). Serwer mysli, jeszcze ze jestes w punkcie A (nie doszedl jeszcze pakiet informujacy o tym, ze jestes w B). I zalozmy ze jakis gosc Cie zaatakuje (u tego innego klienta tez jestes jeszcze przeciez w punkcie A - tam gdzie on). I jak to ma byc wieswietlone niby na Twojej maszynie? Goscie bija sie na odleglosc? Tez jakos nie czuje tego rozwiazania.

Offline mINA87

  • Użytkownik

# Luty 22, 2007, 14:10:56
Cytat: mINA87
A może warto pomyśleć o jakimś rozwiązaniu zachłannym? Pregenerować graf potencjalnie dostępnych miejsc, oznaczać wierzchołki w jakimś promieniu jako dostępne lub nie i starać się iść po "optymalnej drodze" czyli w lini prostej po grafie, omijając przeszkody, możnaby zastosować trochę randomalizacji(jednak wybór omijań musiałby być pamiętany, by w razie w możnabyło wrócić i sprawdzić inną ściechę) i heurestyki aby robić predykcję ruchów w promieniu widoczności  - może coś takiego miałoby szansę działać? Tak w sumie postępujemy my - ludzie i w sumie działa to ^^ W HLu 2 nie wiem czy czasem nie robią podobnie IIRC. Dla małych odległości powinno to być szybkie i poprawne. Dla bardziej skomplikowanych postać będzie się obijać i krążyć - nie wiem czy właśnie o tym czasem nie mówisz gdy piszesz, że na to się skarżą gracze.
No dobrze, ale w takim przypadku przeciez droga bedzie obliczana na bierzaco u klienta w raz z tym kiedy przemieszcza sie po planszy. A serwer nie bedzie w danym momencie wiedzial nawet dokladnie gdzie znajduje sie gracz. Chodzi oto, zeby serwer wiedzial pierwszy jaka droga bedzie poruszal sie klient. Bo w takim przypadku to stanie sie nastepujaca rzecz.
Przemieszczasz sie z punku A do B ktore sa blisko siebie. Na Twoim kompie jestes juz w punkcie B (rednerujesz swoja postac w punkcie B). Serwer mysli, jeszcze ze jestes w punkcie A (nie doszedl jeszcze pakiet informujacy o tym, ze jestes w B). I zalozmy ze jakis gosc Cie zaatakuje (u tego innego klienta tez jestes jeszcze przeciez w punkcie A - tam gdzie on). I jak to ma byc wieswietlone niby na Twojej maszynie? Goscie bija sie na odleglosc? Tez jakos nie czuje tego rozwiazania.
Klient liczy takie cudo na parę kroków w przód i zgłasza rządanie do serwa ze ścieżką, serw sprawdza czy wszystko gra, jeśli tak to ql, zezwala na wykonanie drogi po tym grafie (algorytm wymaga by droga była fragmentowana, tutaj też się to przyda dla serwa) i wtedy rezerwuje sobie te miejsca u siebie jako potencjalnie zajęte. Gdy następny klient się odpyta o widoczność tych wierzchołków, to są one _potencjalnie_ zajęte, więc ich albo nie użyje wcale i będzie się starał ominąć wierzchołki używane przez naszego gracza, albo dopuścimy małą kolizyjność/awaryjność. Im krótsze ścieżki częściowe, tym lepiej będzie to działałao - i synchronizacja będzie mniej zachłanna i lepsza. Problem że więcej pakietów będzie leciało.

Offline KriS

  • Użytkownik
    • KriS

# Luty 22, 2007, 14:13:38
Mozesz napisac dokladniej jak Ty widzisz takie rozwiazanie?

Ja bym raczej dzielil na podstawie geometrii (navigation mesh) niz na podstawie z gory zdefiniowanych kwadratow. Do kazdego sektora mozna dodac dodatkowe informacje o "waskich gardlach" w takim sektorze, tak aby szybko mozna bylo sprawdzic, czy w ogole da sie przez taki sektor przejsc. Oczywiscie zawsze mozna wymyslic przypadki w ktorych cos takiego mogloby nie zadzialac, ale IMHO jest to wystarczajaco dobre rozwiazanie :) (zreszta sam cos takiego robilem dla znacznie wiekszych plansz).

Offline TheLoader

  • Użytkownik

# Luty 22, 2007, 14:43:33
Klient liczy takie cudo na parę kroków w przód i zgłasza rządanie do serwa ze ścieżką, serw sprawdza czy wszystko gra, jeśli tak to ql, zezwala na wykonanie drogi po tym grafie (algorytm wymaga by droga była fragmentowana, tutaj też się to przyda dla serwa) i wtedy rezerwuje sobie te miejsca u siebie jako potencjalnie zajęte. Gdy następny klient się odpyta o widoczność tych wierzchołków, to są one _potencjalnie_ zajęte, więc ich albo nie użyje wcale i będzie się starał ominąć wierzchołki używane przez naszego gracza, albo dopuścimy małą kolizyjność/awaryjność. Im krótsze ścieżki częściowe, tym lepiej będzie to działałao - i synchronizacja będzie mniej zachłanna i lepsza. Problem że więcej pakietów będzie leciało.
No dobrze. A ten graf rozumiem ze musialby byc rozkladany recznie przez osobe tworzaca level?
Pozatym wierzcholki grafu nie mogly by docierac przeciez w wszystkie mozliwe miejsca gdzie sie kliknie na planszy. Rozumiem, ze graf mialby byc rozlozony w ten sposob ze z kazdego miejsca w ktore da sie dojsc na planszy prowadzi prosta droga (bez przeszkod na tej drodze) do jakiegos wierzcholku grafu? Dobrze rozumiem? A co jesli jakas postac dojdzie juz do wierzcholka ostatniego i zostanie juz mu ta "prosta droga", a na tej drodze akurat ktos stanie? Jak na tym etapie bedzie przeprowadzane szukanie sciezki? Implementowales juz cos takiego dla duzych plansz?
Cytat: Kris
Ja bym raczej dzielil na podstawie geometrii (navigation mesh) niz na podstawie z gory zdefiniowanych kwadratow. Do kazdego sektora mozna dodac dodatkowe informacje o "waskich gardlach" w takim sektorze, tak aby szybko mozna bylo sprawdzic, czy w ogole da sie przez taki sektor przejsc.
Te "navigation mesh" rozkladal by levedesigner czy automat mialby to robic? Robiles to z duza iloscia botow na planszy? Przeciez te sektory moga byc blokowane przez boty(czy graczy) caly czas, a jak na tak malej planszy bedzie powiedzmy 100 playerow to nie wiem jak mialo by dzialac uaktualnianie informacji czy z z danego sektora da sie przejsc do innego? W ciagu ulamka sekundy przeciez syuacja moze sie zmienic.
Cytat: Kris
Oczywiscie zawsze mozna wymyslic przypadki w ktorych cos takiego mogloby nie zadzialac, ale IMHO jest to wystarczajaco dobre rozwiazanie  (zreszta sam cos takiego robilem dla znacznie wiekszych plansz).
Zle mnie zrozumiales. Moja plansza bedzie praktycznie nieskonczenie duza (zajmowac bedzie wiele giga, i bedzie dynamicznie zczytywana z internetu na HD, i dynamicznie zczytywana z HD do RAM, a z RAMu na pamiec karty graficznej w czasie dzialanai gry). Ten podany rozmiar 1000x1000 to jak powiedzialem tylko kawalek ktory aktualnie oglada gracz. Tylko na tym obszarze szukam drogi (dla uproszczenia).
« Ostatnia zmiana: Luty 22, 2007, 14:45:53 wysłana przez TheLoader »

Offline Gloggie

  • Użytkownik

# Luty 22, 2007, 14:48:23
Inna sprawa. Wyobrazmy sobie dwoch gosci stojacych obok siebie i naparzajacych sie z piesci. Raz wali jeden raz drugi. Na zmiane stoja sobie i sie wala po mordach:
XY
X to jeden gosc, Y to drugi.
I teraz Przychodzisz Ty z kierunku dolnego lub gornego
XZY
Z to jestes Ty. No i jak to ma dzialac? Oni przestaja  sie bic (to bez sensu, przeciez musi byc odejmowana im energia, bo inni gracze by nawet nie wiedzieli, ze oni sie odsuneli - sam mowiles ze lokalnie). Nie moga tez sie bic walac w Ciebie bo to Tobie w takim przypadku powinna byc odejmowana energia nie im. Itd. Jest pelno takich przypadkow. Poprostu nie widze tego rozwiazania w praktyce.

Ho ho, widzę że się w takim razie szykuje pierwsza gra MMO oferująca sposób walki w stylu Quake :)
Powiem tak - z chęcią bym zagrał w taką grę (bo niestety, wszystkie MMO to na dzisiaj jest po prostu automatyczna nawalanka), ale jest to technicznie nie do wykonania, gdyż wszyscy gracze musieli by mieć pingi <150ms. Jest to nie do spełnienia, więc wygrywały by osoby z mniejszym pingiem (tak jak to się dzieje w CS, Quake, itp) a nie te posiadające silniejsze postaci.

Tak więc we wszystkich MMO w jakie grałem gracze bili się na odległość i mogłeś stac pomiędzy bijącymi się, a  tobie nic się nie działo.

Więc życzę powodzenia w pisaniu, na pewno w to zagram :)

Offline mINA87

  • Użytkownik

# Luty 22, 2007, 15:03:18
No dobrze. A ten graf rozumiem ze musialby byc rozkladany recznie przez osobe tworzaca level?
Pozatym wierzcholki grafu nie mogly by docierac przeciez w wszystkie mozliwe miejsca gdzie sie kliknie na planszy. Rozumiem, ze graf mialby byc rozlozony w ten sposob ze z kazdego miejsca w ktore da sie dojsc na planszy prowadzi prosta droga (bez przeszkod na tej drodze) do jakiegos wierzcholku grafu? Dobrze rozumiem? A co jesli jakas postac dojdzie juz do wierzcholka ostatniego i zostanie juz mu ta "prosta droga", a na tej drodze akurat ktos stanie? Jak na tym etapie bedzie przeprowadzane szukanie sciezki? Implementowales juz cos takiego dla duzych plansz?
Wierzchołki grafu obejmowałyby drobne sektory, układ macierzowy, rozmieszczane automatycznie, właśnie z drobną randomalizacją, by krata nie wypadła tak strasznie regularnie - dzięki temu będzie lepiej jej rozwiązać szczególne przypadki. Jasne, że nie byłyby to wszytskie możliwe punkty kliknięcia na mapie, ale taka kula o promieniu 1,5 szerokości średniego gracza byłoby dobre, szczególnie, że myślimy dosyć lokalnie - w obrębie ekranu. Tak, dobrze rozumiesz, z tym że wierzchołki do których da się dojść to również te wierzchołki na których mogą stać inni gracze. Ta prosta droga będzie na tyle krótka, że gracz będzie albo przy punkcie docelowym, albo w nim (jeśli wybierzesz spore odległości między wierzchołkami, to możesz zawsze poruszać się po krawędziach czworokąta-prawie_kwadratu(jego wierzchołki to wierzchołki grafu) w którym zawiera się punkt docelowy) . Niestety nie miałem okazji implementować takiego czegoś z braku czasu, jednak omawiałem z paroma osobami podobne coś i stwierdziliśmy że ma szanse działać.