Pokaż wiadomości

Ta sekcja pozwala Ci zobaczyć wszystkie wiadomości wysłane przez tego użytkownika. Zwróć uwagę, że możesz widzieć tylko wiadomości wysłane w działach do których masz aktualnie dostęp.


Wiadomości - Adam B

Strony: [1] 2 3 4 5 ... 10
1
Zakładając, że:
N - ilość obiektów
M - ilość tilesów z jakiej składa się cała mapa (zakładam na teraz, że 15000 - kiedy mapa ma 5 ekranów wysokości i szerokości)
P - średnia ilość tilesów jaką widzi/odkrywa obiekt - okolo 81. (9x9 tilesów)

Teraz złożoność algorytmu to:
N * P co daje średnio 81N. Co dla 1000 obiektów daje wynik 81000 obliczeń.

Jeżeli obiekty widziały by obszar kwadratowy wymyśliłem algorytm w najgorszym przypadku o złożoności:
N+M co daje 16000 tysięcy obliczeń.

W przypadku lepszym (nie cała mapa jest odsłonięta) to:
N + "potencjalna ilość odsłoniętych kafelków" - powiedzmy w sumie z 5000 obliczeń.

Muszę zastanowić się jak to przełożyć kiedy kształtem widoczności jednostki jest okrąg, a nie kwadrat.
Jak coś wymyślę zaraportuję.

2
Myślę że możesz połączyć oba rozwiązania - to znaczy wyliczanie FOW z położenia obiektu (nie z środka kawelka) jak i liczenie FOW *rzadziej* niż co klatkę, np. 5 razy na sekundę - dla mechaniki jak i człowieka to powinno wystarczyć (chyba że masz jednostkę, która porusza się szybciej niż 5 kafli na sekundę) - no... do przemyślenia

Przy okazji.. jak jest w innych grach? wydaje mi się, że FOW jest pewną mapą, która aktualizuje się przy poruszaniu jednostki, gdzie jestem skłonny uwierzyć, że
1) sprawdza się czy jednostka odkryła nowy teren, jeśli tak to ten teren się dodaje do "widocznego"
2) rzadko sprawdza się czy jakiś teren nie jest już widoczny (jednostka zginęła, odsunęła się itd.), w starcraft2 wydaje mi się, że teren "znika" gdzieś dopiero po 2 sekundach
3) troche kombinowane, ale może da się określić: jednostka znajduje się w "zasięgu" widoczności większej niż ona sama daje, więc można ją pominąc z obliczeń (może jakiś algorytm "otoczki wypukłej" na zbiorze jednostek będzie mniej kosztowny niż obecne podejście - chociaż ta "otoczka" może nie być wypełniona w środku :D)

Sprawdzanie czy jednostka odkryła nowy teren bez kasowania tego co wcześniej było niczym się nie różni od wykasowania wszystkich informacji i zbudowania ich od nowa.  Przynajmniej nie widzę tutaj optymalizacji..

Rozbicie na kilka kroków - może powodować przycięcia.. Generalnie ogólnego rozbijania ze liczę po 10% i po 10 obliczeniach (klatkach/petlach logicznych) wyświetlam efekt chciałbym uniknąć.. To nie jest optymalizacja - to jest rozłożenie słabo działającego algorytmu jaki mam teraz w czasie.

3
Jeśli chcesz naprawdę szybko:

Tworzysz grida bitowego który zapisuje jaki teren jest odkryty (niekoniecznie aktualnie obserwowany przez jednostkę). Updatujesz tylko wtedy kiedy jednostka się ruszy. Nie koniecznie w każdym framie.
Stosujesz operator OR na tym gridzie i masce bitowej zasięgu widoku jednostki.

Kafelki sprawdzane czy są widziane przez jednostkę obliczasz jedynie dla kafelków widocznych na ekranie.

Dodatkowo stosujesz quad-tree z uwzględnieniem zasięgu wzroku jednostki żeby nie sprawdzać dla każdej jednostki czy widzi dany kafelek na ekranie.

1) Czy grid bitowy czy oparty na intach - to nie ma roznicy za duzej.
2) A jak kafelka ma sprawdzac czy jest widoczna przez jednostke ? W czasie budowania struktury "prawdopodobnych" do sprawdzenia kolizji np. spatial hashing czy quad-tree musialbym do kafelka dodawać takie informacje - wydaje mi się, że nie różni się to od tego co teraz robie jakoś mocno.. sprawdzam jakie kafelki są w polu widzenia jednostek.

Generlanie to obiektu musza określać jakie kafelki są widoczne bo to obiekty mają "zasięg widzenia".
Myślę, że tu nie chodzi o optymalizacje tego co jest - bo ile wycisne ? 20% 50% zaoptymalizuje ? To dalej będzie za wolno... Bardziej potrzebna jest inna metoda..



4
tak

5
Po wprowadzeniu optymalizacji:

1) liczyć efekt względem środka kwadratu FOWa, a nie względem pikseli,
2) nie liczyć wartości dla kafelków FOWa w locie tylko przygotować tablice z wartościami w zależności od zasięgu widoczności - pewnie będzie kilka jednostek z kilkoma zasięgami widoczności więc danych do zapamiętania będzie mało. Takie preliczone tablice bym nanosił na kafelki FOWa, zamiast liczyć wszystko w locie.

Nie uzyskałem zauważalnej róznicy +/-1-2% wydajności - więc nic.

W środku funkcji przypisującej wartości do kafelka jest jeszcze sprawdzenie czy dany index kafelka istnieje (Math.min i Math.max) moze to sprawdzenie dużo kosztuje - potestuje.


Podsumowanie:
Na teraz wychodzi, że same obliczenia nie są kosztowne - problemem jest ilość operacji na całej mapie FOW. Bardzo dużo obiektów działa na tych samych kafelkach wpisując do nich wartość 0 - czyli kafelek widoczny..

Nowa myśl:
Moze duzo lepszym podejściem będzie dodanie eventu dla obiektu typu: "onTileChange" i aktualizowanie mapy FOWa przez obiekt po takim evencie? Nawet jak zaznaczę 1000 obiektów i wszystkie będą się poruszać to event dla pojedynczego obiektu będzie się średnio wywoływał raz na kilka/kilkanaście klatek więc teoretycznie powinien być duży zysk wydajności..

Problemem w tym podejściu może okazać się jednak większa podatność na błędy - no ale z tym trzeba się jakoś uporać.

EDIT:
W tym podejściu mapa FOW by miała inne wartości: 0 - niewidoczny kafelek, 1 i więcej - widoczny. Jeżeli kafelka by była w zasięgu widzenia 10 obiektów to miała by wartość 10.

6
Hej,

W projekcie, który właśnie robię zaimplementowałem FOWa.

Efekt można zobaczyć na:
http://supertowerdefence.pl/
+ wybrać obojętnie jaki zapis gry. np "map save" ma ponad 1200 obiektów to też można sprawdzić wydajność.


Na jaki problem natrafiłem?

Dla dużej ilości obiektów (np 1000) samo przygotowanie modelu dla renderowania FOWa zajmuje prawie połowę czasu modułu renderującego - zgroza:(

Jaka to u mnie działa:
 1) FOW to mapa z kafelków o rozdzielczości 40/40px,
 2) wartość kafelka 1 - rysuj maksymalnego FOW, wartość 0 - nie rysuj, wartości pomiędzy 0-1 to cieniowanie FOWa na krawędziach widoczności (taki mały bajer)
 3) dla każdego obiektu w team1 (czyli moje jednostki) nadaje dla kafelków FOWa (w zasięgu promienia widoczności) odpowiednie wartości od 0 do 1 - liczę to na zasadzie (kwadratu - żeby nie było pierwiastków) odległości kafelka do obiektu.
 4) dzięki takiemu podejściu jeżeli obiekt porusza się w obrębie jednego kafelka to FOW i tak jest przeliczany w zależności od dokładnej pozycji obiektu - dzięki temu na krawędziach jest "w miarę płynny" efekt cieniowania podczas poruszania się obiektów.
 5) co klatkę renderowania kasuje całego FOWa do wartości 1 i proces powtarzam od nowa.

Szukam pomysłów na optymalizację podejścia które zastosowałem, nawet przy zmniejszeniu jakości rozwiązania.

Jakie mam pomysły na optymalizację:
 1) liczyć efekt względem środka kwadratu FOWa, a nie względem pikseli,
 2) nie liczyć wartości dla kafelków FOWa w locie tylko przygotować tablice z wartościami w zależności od zasięgu widoczności - pewnie będzie kilka jednostek z kilkoma zasięgami widoczności więc danych do zapamiętania będzie mało. Takie preliczone tablice bym nanosił na kafelki FOWa, zamiast liczyć wszystko w locie.
 3) jeżeli dla danego kafelka FOWa dla takiej samej lub większej wartości "zasięgu widzenia" wartości FOWa zostały już ustalone (naniesione na mape FOWa) to przejść do kolejnego obiektu - powinno to znacznie poprawić wydajność kiedy dużo jednostek jest blisko siebie.
 4) aby zachować ładne cieniowanie renderer by animował moc FOWa - żeby były płynne przejścia w sensie jeżeli jest zmiana stanu z 1 na 0 (lub odwrotnie) to efekt jest płynny, ale dba o to już inny moduł + podpiąć to do eventu "onChangeFOWValue" aby animować tylko te kafelki, które tej animacji potrzebują.
 5) dla dużych map można zapamiętywać, które kafelki wymagają zresetowania FOWa, aby nie resetować całej mapy bo to nie ma sensu.

Dodatkowo myślę nad innymi optymalizacjami, jednocześnie nie mam przekonania czy nie będzie to powodowało pogorszenia wydajności:
 - przetrzymywanie informacji ile jest do granicy widzialności, z każdej ze stron lub do najbliższej granicy i jeżeli więcej niż to co ma widzieć aktualny obiekt to też go pomijać..

Nie wiem czy moje podejście jest w ogólne dobre - może istnieją jakieś lepsze, o których nie pomyślałem?
Trochę przybijające jak prosty efekt typu FOW zajmuje dla dużej ilości obiektów znaczny czas przygotowania modelu dla renderera.. :(

Pozdrawiam,
Adam

7
W sumie racja.. nawet elementy, które są poza viewportem musza mieć liczone kolizje co jest "100 razy" bardziej kosztowne..

8
Przemyślałem temat i wydaje mi się, że odpowiednim podejściem będzie tutaj informacja w modelu mapy zawierająca następujące informacje.

Kafelek będzie wiedział jakie obiekty graficzne do niego należą (nachodzą na niego) zarówno te, które mogą się poruszać jak i te, które nie mogą się poruszać.
Podczas renderowania kafelka system renderujący będzie sprawdzał listę obiektów, które na niego nachodzą i renderowal.
Element, który znajduje się niżej na ekranie będzie renderowany później.


W czasie ruchu jednostek/obiektu trzeba tylko aktualizować kafelki, do których jednostki należą.


Nie wiem tylko na ile dobre i wydajne będzie takie rozwiązanie bo gdy np. będę chciał poruszyć milionem elementów nawet poza ekranem to sam proces aktualizacji/przypisywania kafelków może być drogi.. Ale nie wiem czy jest jakieś inne dużo lepsze rozwiązanie ??

9
Przed narysowaniem konkretnej grafiki sprawdzam sąsiadujące z nią typy pól - podobnie jak to narysowałem na rysunku w pierwszym wpisie tematu.

Na teraz można rysować tylko górki, docelowo z lewego menu ma się dać wybrać typ terenu do rysowania.
W rysowaniu górek są jeszcze błędy - wynika to z tego, że nie mam wystarczającej ilości grafik więc będę musiał dodać logikę do "pędzla terenu" lub dorysować sobie kilka grafik :)))))

Pierwszy efekt można sprawdzić tutaj:
http://supertowerdefence.pl/Editor.php

TODO:
Po wykonaniu wyżej wymienionych zadań przyjdzie czas na grafikę drogi i wody + mostu.


PRZEMYŚLENIE:
1) Bez "mieszania/przenikania/półprzezroczystości" grafik dodawanie kolejnych typów terenu jest MEGA! czasochłonne, ponieważ trzeba dodawać wszystkie typy łączenia się terenu, a przyrost potrzebnych grafik jest geometryczny :(

Jak piszesz własną grę, to nie ma żadnych zasad. :)
2) Kiedy niektóre grafiki są większe niż standardowy kafelek trudność sprawia optymalizacja widoku mapy tak aby rysował faktycznie tylko to co ma być narysowane. U mnie przy scrollowaniu mapy widać ze na krawędziach canvasa znikają grafiki górek..

10
Częściowo poradziłem sobie z problemem jednak mam pewne wątpliwości więc zadam inne pytanie:

Czy jak budujemy mapę z kafelków czy jedne kafelki mogą być większe od innych ? Czy jednak powinno się trzymać zasady, ze wszystkie kafelki na mapie są tych samych rozmiarów?

11
Tak faktycznie jest to bug - "zółty kafelek" nie uwzględnia dobrze przesunięcia mapy/viewportu.


12
Hej,

Rozwijam sobie powoli i pomału projekt Gierki 2d - aktualnie pracuje nad edytorem:
http://supertowerdefence.pl/Editor.php

Z prawego menu trzeba wybrać grafikę 'gcc01.png"lub 'gcc02.png", żeby malować mapę - inne grafiki nie działają.

Znalazłem grafiki do generowania map 2d, oto link do obrazka gdzie są zaprezentowane (potem wrzucę na mojego FTP i podmienię żeby link nie wygasł i żeby grafika była w lepszej jakości):

link: http://supertowerdefence.pl/tailset_prezentacja.png



Na grafice jedynkami zaznaczyłem poziom wysoki, dwójkami poziom niski. Na podstawie jedynek i dwójek chce dopasowywać tilesy w edytorze. Zakładam, że w grze grafiki terenu będą wielkości jednego kafelka - edytor je potnie jeszcze odpowiednio..


Jestem teraz na etapie generowania "poziomu wysokiego", czyli highground'a.

Problem jaki mam:
Tilesy są tak zaprojektowane, ze nie mogą za ich pomocą narysować dowolnego kształtu " highground'a". - tego problemu nie ma przy generowaniu trawy i drogi.

Jak powinienem podejść do problemu?
1. Tilesy są złe i potrzebuje takich, którymi dam rade obrysować dowolny kształt?
2. W logice rysowania  "highground'a" uwzględnić to jakie mam tilesy i edytor ma pozwalać na rysowanie tylko takich kształtów "highground'a", które będą dobrze wyglądać?
3. Rozwiązanie jest zupełnie inne ?

Pozdrawiam,
Adam

Edit1:

Podminilem obrazek na taki w wysokiej rozdzielczosci.

13
Zastanawiam sie jak zrobic wydajnie kontrolke minimapy, ktora jest osobna kontrolka i nie jest mocno powiazana z projektem (zeby byla przenosna).


Doszedlem do podejscia wstrzykniacia do MinimapView obiektu o interfajsie jakiego potrzebuje minimapa. Konkretnie chodzi o to ze MinimapView wspolpracuje z interfejsem IMinimapElement lub IMinimapList.
Jest to interface, ktory okresla metody getX(), getY(), getColor() i getRadius().
Podstawowe Entity w grze implementuje ten interfejs aby moglo byc wyswietlony na widoku minimapy.

I teraz w sumie dochodze do wniosku ze wszystkie wlasciwosci widoku mozna przekazywac przez tak zdefiniowany interfejs np. viewport, ktory tez wyswietlamy na minimapie.

Dzieki temu w ogole nie bede musial updatowac danych w Widokach - beda one jedynie przerysowywac model, z ktorym sa powiazane dzieki interfejsowi, ktory definiuje widok.

Z drugiej strony nie zawsze model gry moze dostarczyc idealnych danych dla kontrolek np. widok moze miec width i heigth np. okreslone jako FILL_PARENT i wtedy juz musi być przeliczony layout wedle wewnetrznej logiki GUI.

Wychodzi mi na to ze:
 - wszystko co jest wewnetrz widoku moze byc przekazane przez interfejs jak pisalem, (np. elementy wewnetrz minimapy)
 - same dane opisujace kontrolek w drzewie widokow powinno byc okreslane jako wartosci i poddane do obliczen przez "silnik" GUI. Takie dane to glownie dane layoutu np. align, relacyjne ulozenie elementow pomiedzy soba itp.

Dobrze mysle ?

14
Popracowalem trochę i można zobaczyć na stronce efekt.
Chwilkę trzeba poczekać aż wszyscy przeciwnicy pojawią się na mapie.

Efekt wymaga jeszcze poprawek/optymalizacji/dopieszczenia ale na teraz jest na tyle zadowalający, że mogę zająć się kolejnymi aspektami gierki.

Pozdrawiam i dzięki wszystkim za odpowiedzi.

15
Cytuj
ad 1) zależy to od implementacji, prawdopodobnie szukanie drogi nie działa dla mobilnych jednostek - dla nich są tylko proste obliczenia niewchodzenia na siebie i poruszania się w grupie.

 - Zgadza się ale pytalem o potencjalna przyczynę.


Cytuj
ad 2) fuzzy-logic ku pomocy :) załóż, że jeśli mob jest w odległości X jednostek od celu i np. jest w otoczeniu kilku innych z własnej grupy, to uznaje, że dotarł na miejsce i nie próbuje osiągnąć punktowo x.y.z. celu

 - tyle to wiem - liczyłem na jakies opracowanie tematu lub link, w kórym jest wyjasnione teoretycznie jak takie rzeczy się robi - sam mialem problem zeby wyszukac.. a pewnie są takie materiały w sieci

Cytuj
ad 3) jak odp. wyżej - zależy od tego czy akceptowalny jest efekt przenikania się graficznych reprezentacji mobów.

 - bardziej chodziło mi o to czy taki algorytm jest w ogóle potrzebny, czy sam mechanizm pathfindingu powinien być na tyle dobry, żeby zapobiegać takiej sytuacji - jak to jest w praktyce ? Bo ja to widzę tak - jeżeli pathfinding jest niewystarczający to w łatwy sposób odpychanie się jednostek może zrekompensować tę niesodkonałość algorytmu wyszukiwania drogi.. szczególnie ważne gdy np. przez wąskie przejście ma się przedostać 200 jednostek. Albo po 1-- jednostek.. ale jedne idą z lewej strony, a drugie z prawej :)

Cytuj
ad 4) musisz stosować tutaj algorytmy poszukiwania drogi dla formacji - wtedy drogi nie szuka każda z jednostek oddzielnie tylko arbitralnie założony "środek ciężkości" grupy, a reszta podąża za nim, zachowując formację.

 - to zaobserwowałem, ze logika poruszania się często dotyczy grupy jednostek i środka ciężkości tej grupy. Bardziej chodziło mi o to, ze układamy jednostki w kowadło.. i gdy te kowadło nie jest zbyt duże to i tak powinno się dać z niego wyjść.. samo omijanie jednostek stojących w miejscu na zasadzie idź tą drogą (wektorem), której kąt pomiędzy wektorem do celu ma mniejszy kąt nie wystarczy..


Strony: [1] 2 3 4 5 ... 10