Autor Wątek: Dla zaawansowanych- Wieeeeel obiektow na duuuuzej mapie - optymalny algorytm  (Przeczytany 3239 razy)

Offline jarekKatowice

  • Użytkownik

# Sierpień 13, 2009, 23:30:03
Witam!
Od jakiegos czasu zacalem sie bawic w pisanie gierek :) w oparcio o SDL.
Mam pewien dylemat a ze nie chce wywazac otwartych drzwi dlatego  pytam was starych wyjadaczy o opinie.
Zaluzmy ze twozymy pewien swiat 2D.
 - Mamy mape ktora gdyby dalo sie wyswietlic miala by powiedzmy 10.000X10.000 pikseli. Na ekranie monitora wyswietlany jest jej wycinek  np 200 na 400
- Na tej mapie mamy rozlozone postacie powiedzmy rasy A, B, C, D. Jest ich powiedzmy w sumie 1000 Rasy te roznia sie wielkoscia (w sensownej proporcji do wielosci mapy) np sa wieksze lub grubsze albo naj jedna lub dwie glowy - nie ma znaczenia. chodzi oto ze nie sa jednakowego ksztaltu. Rasa A jest slabsza od B b slabsza od c itd
 - Na tej mapie mamy rozlozone powiedzmy 2000 przeszkod typu domki, skaly, drzewa na ktore jak natrafi postac musi zmienic kierunek drogi oraz 1000 przedmiotow ktore daja ludkowi jakies dodatkowe moce lub mu je odbieraja. Wszytskie te przedmioty jak i przeszkody maja roze wielkosci (w sensownych proporcjach w stosunku do mapy)i ksztalty. Ich polozenie  moze byc rozne jednak nie zachodza na siebie. odleglosc miedzy nimi nie jest wielokrotnscia jakiego kafla. Np. Domek moze stac 10 pikseli obok drzewka, 4 piksele naprzeciwko kamienia i 200 pikseli na ukos od lezacego jablka (przedmiot dajacy energie itp itd)
Nasz swiat zaczyna zyc. Postacie poruszaja sie po nim , kazda rasa w innej sensownej szybkosci i sensownej odleglosci w stosunku do wielkosci mapy. Jesli Postac zderzy sie z postacia swoje rasy obie postacie wzrastaja w sile. Jezeli  z rasa slabsza to slabsza traci sile. Chodzi o to ze nastepuja jakas akcja w wyniku spotkania sie postaci. JJesli postac natrafi na przedmiot "dobry " np. jablko zwrasta sila dwukrotnie jak na "zly" np ognisko traci sile dwukrotnie.
W prawym gornym rogu ekrany wyswetla nam sie jakis raport z zycia teo swiata np rasa A w sumie posiada sile iles tam rasa B tyle a ty itd.
A teraz sedno (nareszcie :) )  Jak optymalnie zimplementowac taki swiat. Postacie zderzaja sie ze soba z przeszkodami i przedmiotami. Nie mozna chyba dla kazdej postaci sprawdzac iteracyjnie czy nie zderza sie po wykonaniu kroku  z inna bo bylo by to 999+2000+1000=3999 dla kazdej  z 1000 postaci. Komputer by chyba tego nie wytrzymal. A moze sie myle?
Czy ktos z was mial juz taki dylemat? Jak podeszlibyscie do tego problemu?

Offline Mr. Spam

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

# Sierpień 13, 2009, 23:32:35
oooooooooooeeeeeeeeeeeeeezzzzzzzzzzzaaaaaaaaaaaaaaaa....
 ;D
PoL.

Nie wiem jak komputer, ale moja głowa tego nie ogarnia.

Edit:
Żeby nie było że też tylko śmiecę to:

Od zarządzania nieogarnionymi zdarzeniami jest statystyka. Jeżeli obserwator widzi tylko efekt... nie jest w stanie stwierdzić jak te milion zdarzeń przebiegło.

To możemy te masy wydarzeń uprościć do 4, 5, ew. 6 zmiennych. Jednego wzoru przedstawiającego uproszczenie rozkładu i powinno być ok.

Nie działa to zazwyczaj w drugą stronę czyli tworzenie modelu czegoś co już się dzieje z wysoką dokładnością zazwyczaj się nie udaje... Ale tutaj kreujesz jakis własny świat i nikt cię o realizm czy zgodność z rzeczywistością posądzać nie będzie.
« Ostatnia zmiana: Sierpień 13, 2009, 23:39:00 wysłana przez poopa »

Offline Joker

  • Użytkownik

# Sierpień 13, 2009, 23:36:13
Najpierw przydała by się czytelność kodu oraz wyeliminowanie błędów ortograficznych.Potem wiedza na temat pisania gier.A potem mógłbym powiedzieć że możesz wyświetlać daną cześć planszy którą gracz widzi zamiast wyświetlania całego świata.Dodatkowo możesz dodać mgłę a obiekty które będzie zasłaniała usuwać bo i tak ich nie będzie widać.A że mam dobry humor to nakieruje cię na fajny poradnik który ci się przyda (Jest płatny,ale w necie znajdziesz darmowy):Słownik poprawnej polszczyzny.

Offline jarekKatowice

  • Użytkownik

# Sierpień 13, 2009, 23:45:31
Wpadl mi do glowy pewien pomysl tylko nie wiem czy jest dobry . Moze znacie lepszy?
postacie, przeszkody i przedmioty pochodza z abstrakcyjnej klasy typu object.
Mozna bylo by utworzyc vetor ktorego kazdy element byl lista typu obiekt. kazda element wektora (czyli lista) przechowuje objecty ktorych wpolrzedne lewego gornego oraz prawego dolnego znajduja w obrebiu mapy za ktory odpowieda dany element wektora
np
pierwszy element vektora odpowiada za wycinek mapy x1=0 y1=0 x2=199 y2=199  

drugi element vektora odpowiada za wycinek mapy x1=199 y1=0 x2=399 y2=199  
itd
Object poruszajacy sie po mapie za kazdym rzem wypisuje sie z jednej listy i dopisuje do innej lub kilku innych list (moze lezec np na przecieciu obszarow).
Dzieki temu sprawdzajac zderzenie tylko z objectami listy w ktorej znajduje sie ten object mozna ograniczyc liczbe sprawdzen dla jednego objectu. Znajac współrzędne postaci latwo mozna wyznaczyc index elementu wektora w ktorym sie znajduje lub w ktorym powinna sie znajdowac.
Nie wiem czy to dobry pomysl...
« Ostatnia zmiana: Sierpień 14, 2009, 00:05:53 wysłana przez jarekKatowice »

Offline jarekKatowice

  • Użytkownik

# Sierpień 13, 2009, 23:49:08
Wpadl mi do glowy pewien pomysl tylko nie wiem czy jest dobry . Moze znacie lepszy?
postacie, przeszkody i przedmioty pochodza z apstrakcyjnej klasy typu object.
Mozna bylo by utworzyc vetor ktorego kazdy element byl lista typu obiekt. kazda element wektora (czyli lista) przechowuje objecty ktorych wpolrzedne lewego gornego oraz prawego dolnego znajduja w obrebiu mapy za ktory odpowieda dany element wektora
np
pierwszy element vektora odpowiada za wycinek mapy x1=0 y1=0 x2=199 y2=199  

drugi element vektora odpowiada za wycinek mapy x1=199 y1=0 x2=399 y2=199  
itd
Object poruszajacy sie po mapie za kazdym rzem wypisuje sie z jednej listy i dopisuje do innej lub kilku innych list (moze lezec np na przecieciu obszarow).
Dzieki temu sprawdzajac zderzenie tylko z objectami listy w ktorej znajduje sie ten object mozna ograniczyc liczbe sprawdzen dla jednego objectu. Znajac współrzędne postaci latwo mozna wyznaczyc index elementu wektora w ktorym sie znajduje lub w ktorym powinna sie znajdowac.
Nie wiem czy to dobry pomysl...

nie zrozumielas mnie...nie chodzi mi tak o te statystyki jak o to ze postaci jest wiele bo tysiac, przeszkod 2000 a przedmiotow 1000. kazda postac robi krok po zrobieniu kroku sprawdza czt sie z kims nie zderzyla 
jak tak to jest jakas reakcja na to nie wazne jaka moze nawet pierdnać.
Chodzi oto jak optymanie to zrobic

Offline jarekKatowice

  • Użytkownik

# Sierpień 13, 2009, 23:51:26
Najpierw przydała by się czytelność kodu oraz wyeliminowanie błędów ortograficznych.Potem wiedza na temat pisania gier.A potem mógłbym powiedzieć że możesz wyświetlać daną cześć planszy którą gracz widzi zamiast wyświetlania całego świata.Dodatkowo możesz dodać mgłę a obiekty które będzie zasłaniała usuwać bo i tak ich nie będzie widać.A że mam dobry humor to nakieruje cię na fajny poradnik który ci się przyda (Jest płatny,ale w necie znajdziesz darmowy):Słownik poprawnej polszczyzny.
pisalem szybko wiec nie nie sprawdzalem bledow. Jak nie masz nic sensownego do powiedzenia to nie pisz nic. Kompletnie nie zrozumiales o co chodzi w poscie

Offline Oti

  • Użytkownik

# Sierpień 13, 2009, 23:57:26
Wpadl mi do glowy pewien pomysl tylko nie wiem czy jest dobry . Moze znacie lepszy?
postacie, przeszkody i przedmioty pochodza z apstrakcyjnej klasy typu object.
Mozna bylo by utworzyc vetor ktorego kazdy element byl lista typu obiekt. kazda element wektora (czyli lista) przechowuje objecty ktorych wpolrzedne lewego gornego oraz prawego dolnego znajduja w obrebiu mapy za ktory odpowieda dany element wektora
np
pierwszy element vektora odpowiada za wycinek mapy x1=0 y1=0 x2=199 y2=199  

drugi element vektora odpowiada za wycinek mapy x1=199 y1=0 x2=399 y2=199  
itd
Object poruszajacy sie po mapie za kazdym rzem wypisuje sie z jednej listy i dopisuje do innej lub kilku innych list (moze lezec np na przecieciu obszarow).
Dzieki temu sprawdzajac zderzenie tylko z objectami listy w ktorej znajduje sie ten object mozna ograniczyc liczbe sprawdzen dla jednego objectu. Znajac współrzędne postaci latwo mozna wyznaczyc index elementu wektora w ktorym sie znajduje lub w ktorym powinna sie znajdowac.
Nie wiem czy to dobry pomysl...

nie zrozumielas mnie...nie chodzi mi tak o te statystyki jak o to ze postaci jest wiele bo tysiac, przeszkod 2000 a przedmiotow 1000. kazda postac robi krok po zrobieniu kroku sprawdza czt sie z kims nie zderzyla 
jak tak to jest jakas reakcja na to nie wazne jaka moze nawet pierdnać.
Chodzi oto jak optymanie to zrobic
LOL rozdwojenie jaźni? :D
P.S. Edytuj posty.

Offline jarekKatowice

  • Użytkownik

# Sierpień 14, 2009, 00:04:59
Pokornie proszę by wypowiadać się na temat. Nie chcesz pomoc merytorycznie nie zabieraj głosu.

Offline soku11

  • Użytkownik

# Sierpień 14, 2009, 00:18:18
Sposób, który zaprezentowałeś to po prostu QuadTree. Poczytaj na google. Warto dodać, że w przypadku poruszających się obiektów nie trzeba poruszać każdego z mapy, tylko np. te z najbliższych quadów. Znacznie ograniczy obliczenia kolizji.

Pozdrawiam.

# Sierpień 14, 2009, 00:28:56
Ograniczę się do tego:
Cytuj
Postacie zderzaja sie ze soba z przeszkodami i przedmiotami. Nie mozna chyba dla kazdej postaci sprawdzac iteracyjnie czy nie zderza sie po wykonaniu kroku  z inna bo bylo by to 999+2000+1000=3999 dla kazdej  z 1000 postaci.
Do tego wystarczy partycjonowanie przestrzenne:
http://en.wikipedia.org/wiki/Space_partitioning
na chłopski rozum - jest to grupowanie. Podziel przestrzen 2 wymiarowa na 4 równe sektory(pionowe paski w tym akurat przykladzie). A, B, C i D. Jeżeli obiekty nie mają tak dużego zasięgu jak sektor co turę to możesz luzem wykluczyć kolizje A z C lub D, B z D. I tak idziesz w dół. W zależności od charakterystki rozkładu dobierasz odpowiednie rozmiary przedziałów.

Edit: ano dopiero doczytałem... a rzeczywiscie kolega jakies zapedy sam robi w tym kierunku(dobrym) widac.

« Ostatnia zmiana: Sierpień 14, 2009, 00:31:52 wysłana przez poopa »

Offline jarekKatowice

  • Użytkownik

# Sierpień 14, 2009, 01:06:12
Ograniczę się do tego:
Cytuj
Postacie zderzaja sie ze soba z przeszkodami i przedmiotami. Nie mozna chyba dla kazdej postaci sprawdzac iteracyjnie czy nie zderza sie po wykonaniu kroku  z inna bo bylo by to 999+2000+1000=3999 dla kazdej  z 1000 postaci.
Do tego wystarczy partycjonowanie przestrzenne:
http://en.wikipedia.org/wiki/Space_partitioning
na chłopski rozum - jest to grupowanie. Podziel przestrzen 2 wymiarowa na 4 równe sektory(pionowe paski w tym akurat przykladzie). A, B, C i D. Jeżeli obiekty nie mają tak dużego zasięgu jak sektor co turę to możesz luzem wykluczyć kolizje A z C lub D, B z D. I tak idziesz w dół. W zależności od charakterystki rozkładu dobierasz odpowiednie rozmiary przedziałów.

Edit: ano dopiero doczytałem... a rzeczywiscie kolega jakies zapedy sam robi w tym kierunku(dobrym) widac.



dzięki za rzeczową odpowiedz. W zasadzie podpowiedziałeś mi jak uprościć mój algorytm.

Offline jarekKatowice

  • Użytkownik

# Sierpień 14, 2009, 01:07:42
Sposób, który zaprezentowałeś to po prostu QuadTree. Poczytaj na google. Warto dodać, że w przypadku poruszających się obiektów nie trzeba poruszać każdego z mapy, tylko np. te z najbliższych quadów. Znacznie ograniczy obliczenia kolizji.

Pozdrawiam.
hmmmm czyli Ameryki nie odkryłem :)
Dzięki bardzo zapoznam się z tematem.

Offline rm-f

  • Użytkownik
    • Tu trolluje

# Sierpień 14, 2009, 03:07:16
Ale zejdź z drzewa, i naucz się edytować posty.

# Sierpień 14, 2009, 08:03:39
na chłopski rozum - jest to grupowanie. Podziel przestrzen 2 wymiarowa na 4 równe sektory(pionowe paski w tym akurat przykladzie). A, B, C i D. Jeżeli obiekty nie mają tak dużego zasięgu jak sektor co turę to możesz luzem wykluczyć kolizje A z C lub D, B z D. I tak idziesz w dół. W zależności od charakterystki rozkładu dobierasz odpowiednie rozmiary przedziałów.


Nie ma sensu dzielić plansze na cztery sektory jeśli koleś chce mieć tysiące jednostek.
Może jakbyś robił strzelankę "massive multiplayer" to mógłbyś podzielić planszę na 4 serwery
Lepiej spróbować podzielić mapę na stosunkowo małe sektory, zresztą wielkosć sektora zależy od specyfiki gry.
Nawet kolizje były by zwalone między sektorami , jeśli było by ich 4. Minimalna ilość sektorów powinna wynosić 9,jeśli chcemy mieć normalne kolizje. Wtedy jednostka z sektora [3,3] sprawdzała by jednostki z sektorów : [3,3],[3,2],[2,3] (+ ewentualnie [2,2]) - zakładając że plansza wynosi [3,3].
Żeby nie było że się wypowiadam nie na swój temat: http://www.warsztat.gd/projects.php?x=view&id=791 
« Ostatnia zmiana: Sierpień 14, 2009, 10:58:22 wysłana przez Wladekprogramista »

Offline mihu

  • Użytkownik
    • mihu

# Sierpień 14, 2009, 10:35:33
na chłopski rozum - jest to grupowanie. Podziel przestrzen 2 wymiarowa na 4 równe sektory(pionowe paski w tym akurat przykladzie). A, B, C i D. Jeżeli obiekty nie mają tak dużego zasięgu jak sektor co turę to możesz luzem wykluczyć kolizje A z C lub D, B z D. I tak idziesz w dół. W zależności od charakterystki rozkładu dobierasz odpowiednie rozmiary przedziałów.


Nie chce cię pouczać, ale nie ma sensu dzielić plansze na cztery sektory jeśli koleś chce mieć tysiące jednostek.
Może jakbyś robił strzelankę "massive multiplayer" to mógłbyś podzielić planszę na 4 serwery
Lepiej spróbować podzielić mapę na stosunkowo małe sektory, zresztą wielkosć sektora zależy od specyfiki gry.
Nawet kolizje były by zwalone między sektorami , jeśli było by ich 4. Minimalna ilość sektorów powinna wynosić 9,jeśli chcemy mieć normalne kolizje. Wtedy jednostka z sektora [3,3] sprawdzała by jednostki z sektorów : [3,3],[3,2],[2,3] (+ ewentualnie [2,2]) - zakładając że plansza wynosi [3,3].
Żeby nie było że się wypowiadam nie na swój temat: http://www.warsztat.gd/projects.php?x=view&id=791 
Myślę, że kluczowe znaczenie miało tu chyłkiem wstawione na koniec zdanie:
I tak idziesz w dół.
;D