1 Temat przez nosty

  • nosty
  • Zbieracz kartridży
  • Nieaktywny
  • Skąd: Miasto Łódź
  • Zarejestrowany: 2002-08-20
  • Posty: 3,241

Potrzebuję wiedzy w tytulowym temacie:

Jak wydajnie wykrywac kolizje obiektow?

Znalazlem w sieci pare tekstow ale okazaly sie one srednio przydatne w kontekscie Atari.
Pytam pod kątem pisania gry na "Tomka", ale nie zakladam z gory, ze bedzie to robil koprocesor.
Sprawa nie jest trywialna jesli na ekranie ma byc kilkanascie duzych obiektow o nieregularnych ksztaltach. A uwzgledniajac np pociski moze ich byc kilkadziesiat!

Generalnie sa dwie metody:
1. Bitowa (czyli jakies operacje bitowe i wykrywanie ktore pixele sie pokrywaja - podobnie jak w PMG sprzetowym na Atari)
2. Obliczeniowa bazujaca na odleglosciach.

Pierwsza jest dokladniejsza, ale np XXL sugerowal mi niejednokrotnie ze odrzuca ja zazwyczaj bo jest "za dokladna" czyli ze denerwujaca jest smierc bohatera jesli zawadzi o cos jednym pixelem. Wiec stosuje metode obliczeniowo-odleglosciową.
Ale są sytuacje w ktorych precyzja jest bardzo wazna: np kiedy w platformowce jesli bohater staje przed opadajacymi smiercionosnymi obiektami (np. Henry's House).

Druga metoda wydaje sie latwiejsza, ale jest tak jesli obiekty maja w miare "ogrągly", zwarty ksztalt ;) czyli np okragle pociski trafiajace w niewielekie przeszkadzajki o wymiarach 10x10 pixeli. Tu przyblizenie oparte na odleglosci miedzy srdodkami obiektow jest wystarczajace zeby dobrze sie gralo. Ale co jesli obiekt bedzie duzy o bardzo nieregularnym ksztalcie? Kiedy trzeba sie zmierzyc z czyms takim jak to:
http://www.youtube.com/watch?v=MQvEUX5I … age#t=273s

Do tej pory wykombinowalem, ze moznaby zrobic wykrywanie kolizji troche inaczej: zrobic przyblizenie ksztaltu kazdego obiektu w nizszej rozdzielczosci, np na znakach (czyli na siatce 40x24) i wykrywac kolizje jesli pokrywaja sie "znaki" zajmowane przez dwa obiekty. To powinno dac zadowalajacy rezultat np w strzelankach.
Ale skutkuje to koniecznoscia dublowania animacji na tej "znakowej siatce kolizji".

Chcialbym wiec prosic praktykow o pare slow na temat metod jakie wykorzystywali w swoich grach. Szukam inspiracji i rozwiazan, ktore moglbym zaimplementowac :)

2 Odpowiedź przez sqward

  • sqward
  • Starszy Atarowiec
  • Nieaktywny
  • Skąd: Norfolk
  • Zarejestrowany: 2003-09-05
  • Posty: 2,389

http://en.wikipedia.org/wiki/Quadtree

What can be asserted without proof can be dismissed without proof.

3 Odpowiedź przez tebe Ostatnio edytowany przez tebe (2012-10-13 10:45:45)

  • tebe
  • tebe
  • Starszy Atarowiec
  • Nieaktywny
  • Skąd: Poznań
  • Zarejestrowany: 2002-04-06
  • Posty: 2,930

szybka detekcja kolizji, interko Raster/CPU

w Pangu detekcja kolizji kuli z bohaterem, kolizji harpun-kula realizowane są przez w/w metodę nachodzących się prostokątów/kwadratów (kula opisana jest poprzez wpisany w nią kwadrat), natomiast detekcja kuli - otoczenie (murki etc.) realizowana jest na znakach, z tym że dla każdego przesunięcia X kuli (X=<0..3>) jest inna detekcja, uwzględniająca przesunięcie 1 pikslowe, tylko to gwarantuje dokładną detekcję

w większości przypadków stosuje się metodę z czworokątem (w załączniku), czyli albo prostokąt albo kwadrat, jeśli się uprzeć to jakiś inny kształt też da się opisać takimi czworokątami

jak widać na postawie programiku z załącznika detekcja może być szybka

tutaj wersje bardziej pierwotne metody detekcji zaprezentowanej przez Rastera, dział poświęcony duchom C64
http://codebase64.org/doku.php?id=base:sprites

tutaj dla różnych kształtów
http://en.wikipedia.org/wiki/Point_in_polygon

kolizje kul z przykładową animacją, zmianą kierunku po uderzeniu etc. gdyby ktoś chciał robić bilard albo pinball to koniecznie musi to obejrzeć
http://processing.org/learning/topics/c … ision.html

Post's attachments

CI28.XEX 1 kb, liczba pobrań: 8 (od 2012-10-13) 

Tylko zalogowani mogą pobierać załączniki.
*- TeBe/Madteam
3x Atari 130XE, SDX, CPU 65816, 2x VBXE, 2x IDE Plus rev. C

tebe's Strona

4 Odpowiedź przez wieczor

  • Skąd: Gdańsk
  • Zarejestrowany: 2007-10-21
  • Posty: 4,404

Metoda oparta na odległościach po pierwsze jest czasochłonna - trzeba wyliczać odległości, po drugie działa w przypadku obiektów o regularnych kształtach. Metoda bitowa jest szybka i dokładna i nie ma czegoś takiego jak za duża dokładność. Nikt nie każe Ci zakładać że nastąpiła kolizja po pierwszym dotknięciu, można założyć próg - pokrywa się od np. 5,10 pikseli w górę - wtedy mamy kolizję.

The problem is not the problem; the problem is your attitude about the problem

5 Odpowiedź przez xxl

  • xxl
  • xxl
  • Naddyskownik
  • Nieaktywny
  • Skąd: Rabka-Zdrój
  • Zarejestrowany: 2002-04-23
  • Posty: 8,307

> Pierwsza jest dokladniejsza, ale np XXL sugerowal mi niejednokrotnie ze odrzuca ja zazwyczaj bo jest "za dokladna" czyli ze denerwujaca jest smierc bohatera jesli zawadzi o cos jednym pixelem. Wiec stosuje metode obliczeniowo-odleglosciową.

rozmawialismy o konkretnym przypadku :-)

to co sugeruje tebe jest dobre.

softwarowe kolizje sa o tyle lepsze ze mozna je wykryc przed narysowaniem ekranu, hadrwarowe dzialaja dopiero po narysowaniu ekranu...

http://atari.pl/hsc/ad.php?i=1.

xxl's Strona

6 Odpowiedź przez nosty

  • nosty
  • Zbieracz kartridży
  • Nieaktywny
  • Skąd: Miasto Łódź
  • Zarejestrowany: 2002-08-20
  • Posty: 3,241

Dzieki Panowie! Faktycznie nawet zlozone ksztalty mozna opisac za pomocą kilku - kilkunastu kwadratow, co w wiekszosci przypadkow moze byc wystarczajace.
Widze jednak, ze do zagadnienia nalezy podchodzic bardzo indywidualnie.

Ale moge zaimplementowac w Tomku najprostsza detekcje na zasadzie obiekt = prostokat o wymiarach obiektu. Lub nawet bardziej zlozoną, gdzie obiekt = lista prostokątow o zdefiniowanych wymiarach i polozeniu wzgledem lewego gornego rogu obiektu.

wieczor napisał/a:

Metoda bitowa jest szybka i dokładna

Szybka powiadasz... No to daj mi sensowny algorytm detekcji kolizji bitowej miedzy 32 obiektami o wymiarach do 64x64 piksele nakladanymi na grafike tla. Jak by nie kombinowac trzebaby dla wszystkich obiektow ktore choc w czesci sie pokrywaja robic operacje bitowe "kazdy z kazdym". IMHO nawet 40MIPS'owy PIC by mi sie spocil :P

Ale nie wykluczam w przyszlosci implementacji rozkazu "sprawdz kolizje biotowe obiektu X z pozostalymi".

7 Odpowiedź przez wieczor

  • Skąd: Gdańsk
  • Zarejestrowany: 2007-10-21
  • Posty: 4,404
nosty napisał/a:

Szybka powiadasz... No to daj mi sensowny algorytm detekcji kolizji bitowej miedzy 32 obiektami o wymiarach do 64x64 piksele nakladanymi na grafike tla. Jak by nie kombinowac trzebaby dla wszystkich obiektow ktore choc w czesci sie pokrywaja robic operacje bitowe "kazdy z kazdym"

To daj mi sensowny algorytm który to robi wyliczając odległości między nimi :D Acha - odległość właściwie czego?... Środków? Krawędzi?... Same problemy.

The problem is not the problem; the problem is your attitude about the problem

8 Odpowiedź przez nosty

  • nosty
  • Zbieracz kartridży
  • Nieaktywny
  • Skąd: Miasto Łódź
  • Zarejestrowany: 2002-08-20
  • Posty: 3,241

Nie czytales wczesniej? Przyblizasz ksztalt obiektow za pomoca prostokatow. Wykrywasz czy sie nakladaja.

9 Odpowiedź przez wieczor

  • Skąd: Gdańsk
  • Zarejestrowany: 2007-10-21
  • Posty: 4,404

Ano czytałem. Tyle, że jeśli obiekt jest nieregularny, to może być bardziej denerwujące niż dotknięcie - nie dotknąłeś w ogóle a nie żyjesz :)

The problem is not the problem; the problem is your attitude about the problem

10 Odpowiedź przez nosty

  • nosty
  • Zbieracz kartridży
  • Nieaktywny
  • Skąd: Miasto Łódź
  • Zarejestrowany: 2002-08-20
  • Posty: 3,241

zalezy od szybkosci gry... ja chce zrobic szybką :)
a zobacz to:
http://www.youtube.com/watch?v=hHmzO2RI … re=related
Tenchi opisal te gry jako "bullets hell" :D
Dalbym glowe ze statek zawadza o pociski a energii mu nie ubywa (lub to cheat).
Takze wszystko jest wkestia konwencji i przyzwyczajenia do regul gry.

11 Odpowiedź przez tebe

  • tebe
  • tebe
  • Starszy Atarowiec
  • Nieaktywny
  • Skąd: Poznań
  • Zarejestrowany: 2002-04-06
  • Posty: 2,930

w Mario Bros (konwersja z 5200) detekcja kolizji polega na sprawdzeniu podczas odrysowania ducha programowego, czy tło jest <> 0, jeśli jest różne to kolizja i dalsze uściślanie z czym ta kolizja nastąpiła

http://madteam.atari8.info/gry/mario2007.7z

stawianie/kasowanie duchów realizuje jedna procedura, dzięki metodzie EOR (XOR), czyli aby skasować poprzednio postawionego ducha, stawiamy ostatni kształt ducha ale przez EOR, aby postawić nową klatkę ducha używamy OR

pewne dodatkowe operacje są wymagane aby wiedzieć czy wcześniej była postawiona jakaś klatka ducha czy zaczynamy od czystego ekranu

dzięki tej metodzie udało zmieścić się intro do Panga w 2KB, bez potrzeby używania dwóch buforów dla zachowania płynności animacji obiektów

*- TeBe/Madteam
3x Atari 130XE, SDX, CPU 65816, 2x VBXE, 2x IDE Plus rev. C

tebe's Strona

12 Odpowiedź przez swinkamor12

  • Zarejestrowany: 2012-08-09
  • Posty: 261
nosty napisał/a:

Dzieki Panowie! Faktycznie nawet zlozone ksztalty mozna opisac za pomocą kilku - kilkunastu kwadratow, co w wiekszosci przypadkow moze byc wystarczajace.

Dokładnie tak.

nosty napisał/a:

Widze jednak, ze do zagadnienia nalezy podchodzic bardzo indywidualnie.

Jeśli komuś będzie trzeba więcej to sobie dorobi.

nosty napisał/a:

Ale moge zaimplementowac w Tomku najprostsza detekcje na zasadzie obiekt = prostokat o wymiarach obiektu. Lub nawet bardziej zlozoną, gdzie obiekt = lista prostokątow o zdefiniowanych wymiarach i polozeniu wzgledem lewego gornego rogu obiektu.

Super.

To będzie rozwiązanie które powinno wystarczyć w w 90% przypadków.