Kolizja typu SAT implementacja w grze

Witam! Chciałbym zaimplementować w mojej grze kolizję typu SAT pomiędzy mapą(czytana z txt) a graczem. Obejrzałem sobie i dowiedziałem się jak obliczać dot product. Jednak nadal nie za bardzo wiem jak mógłbym to wykorzystać w mojej grze. Teorie jako samą rozumiem. Klasę vector mam już też napisaną. Prosiłbym o pomoc, najlepiej w postaci kodu, który jest łatwy w zrozumieniu i nie zawiera dużo "dodatków", oczywiście uwagi też są mile widziane. Tak naprawdę, to wszystko co mogłoby mi pomóc w napisaniu tego.
Pozdrawiam serdecznie

Jak to rozkminiles, napisz cos wiecej, z czym jest problem, o co chodzi w tym twierdzeniu.

Jak są np. dwa kwadraty i nie można narysować między nimi linii to znaczy, że jest kolizja, jak można, to nie ma kolizji. Trzeba zapisać min i max każdego kwadratu do zmiennej i wtedy sprawdzić to. Problem jest taki, że nie mogę sobie "wyobrazić" jak mógłbym to zapisać.

Edit: 2

W SAT collision chodzi o to, że tworzysz abstrakcyjne "szyny" wzdłóż twojego obiektu, np jeżeli obiekt to kwadrat z kątem nachylenia 0 to szyny są na osi x, y.
Teraz zanaczasz na tych "szynach" twój obiekt zrzutowany względem danej osi.
W nastepnej kolejności sprawdzasz czy te "szyny" nakładają sie z innymi "szynami" innego obiektu i na tej podstawie aplikujesz kolizje.

Czyli na przykład, mam kod, który wczytuje mapę

for(int i = 0; i < map.size(); i ++)
{
          for(int j = 0; j < map[i].size(); j++)
          {
              // szyny X
              int minX = j * 32;
              int maxX = (j*32) + 32;

              // szyny Y
              int minY = i *32;
              int maxY = (i * 32) + 32;

              ... // wczytywanie mapy
          }
}

I dostaję szyny dla mapy?

JoaWionek napisał(a):

Czyli na przykład, mam kod, który wczytuje mapę

for(int i = 0; i < map.size(); i ++)
{
          for(int j = 0; j < map[i].size(); j++)
          {
              // szyny X
              int minX = j * 32;
              int maxX = (j*32) + 32;

              // szyny Y
              int minY = i *32;
              int maxY = (i * 32) + 32;

              ... // wczytywanie mapy
          }
}

I dostaję szyny dla mapy?

Tylko po co ci przy wczytywaniu mapy te szyny? Sprawdzasz z jakimi obiektami twój player koliduje i rzutujesz ze wszystkich stron "szyny" dla twojego playera i dla kolidujących obiektów. Po tym aplikujesz kolizje wtedy kiedy widzisz, że szyny na siebie nachodzą. Poczytaj jeszcze raz o tym. Ja korzystałem jak robiłem swoją implementacje z tej strony.

Tak jak tutaj:
http://www.sevenson.com.au/actionscript/sat/
Po kolei, dla kazdego boku, każdej z dwóch figur:

• Załóżmy, że Masz wektor równoległy do boku;
• Z iloczynu skalarnego znajdujesz do niego prostooadły;
• Dokonujesz na ten prostopadły wektor projekcji punktów obu figur (wystarczy wziąć kluczowe punkty, rogi i po jednym z boku);
• Jak nie nachodzą na siebie (chyba wystarczy sprawdzić ich współrzędny x - lub y gdy jest to prosta postaci x = c), to odfajkować;
• Powtórzyć dla następnego boku
  Jak żadne nie nachodzą to się nie przecinają.
  Wkleiłem zdjęcie z prostym przykładem projekcji.

Dzięki, przejrzę wszystko parę razy na spokojnie. Pozdrawiam

Jeśli to pomoże to pamiętaj że z każdym bokiem wielokąta można stowarzyszyć układ współrzędnych (dla prostokąta sprawa jest prosta, jest tylko jeden układ współrzędnych). Jeśli prostokąt jest obrócony o 45 stopni to możesz z nim stowarzyszyć układ współrzędnych obrócony o 45 stopni i na osiach tego układu odkładać współrzędne punktów wielokątów.
https://pl.wikibooks.org/wiki/Metody_matematyczne_fizyki/Obrót_układu_współrzędnych - wzory na współrzędne punktów w obróconym układzie współrzędnych.

Oczywiście dla innych wielokątów taka metoda będzie wprowadzać niepotrzebne osie, więc trzeba robić tak jak pisze lion137, ale dla prostokątów jest w sam raz.

czaffik napisał(a):

Jeśli to pomoże to pamiętaj że z każdym bokiem wielokąta można stowarzyszyć układ współrzędnych (dla prostokąta sprawa jest prosta, jest tylko jeden układ współrzędnych). Jeśli prostokąt jest obrócony o 45 stopni to możesz z nim stowarzyszyć układ współrzędnych obrócony o 45 stopni i na osiach tego układu odkładać współrzędne punktów wielokątów.
https://pl.wikibooks.org/wiki/Metody_matematyczne_fizyki/Obrót_układu_współrzędnych - wzory na współrzędne punktów w obróconym układzie współrzędnych.

Oczywiście dla innych wielokątów taka metoda będzie wprowadzać niepotrzebne osie, więc trzeba robić tak jak pisze lion137, ale dla prostokątów jest w sam raz.

Tak, ale...To też spowoduje komplikacje, trzeba będzie przesuwać układ współrzędnych, po czym go obracać; więc musi znajść macierz przejścia, zapisać wszystkie figury w nowych współrzędnych (na szczęście będą ortonormalne) i dopiero kontynuować algorytm; też wcale nie tak prosto. A tak jak podałem, to jedziemy po kolei, nie myśląc.

Przejrzałem sobie wszystko na spokojnie, parę razy i stwierdzam, że średnio rozumiem i nie jestem w stanie tego napisać. Nie stoję za wysoko z matematyką, o macierzach nie wiem nic, o wektorach nauczyłem się w domu dość dużo, mi się wydaje. Miałbym ogromną prośbę, gdyby ktoś był wstanie mi to wytłumaczyć może prostszymi słowami.

JoaWionek napisał(a):

Przejrzałem sobie wszystko na spokojnie, parę razy i stwierdzam, że średnio rozumiem i nie jestem w stanie tego napisać. Nie stoję za wysoko z matematyką, 2 technikum, o macierzach nie wiem nic, o wektorach nauczyłem się w domu dość dużo, mi się wydaje. Miałbym ogromną prośbę, gdyby ktoś był wstanie mi to wytłumaczyć może prostszymi słowami.

W takim razie jakieś dane pomocnicze, którego kroku w algorytmie nie Rozumiesz, i czego nie Rozumiesz z rysunku który wrzuciłem, może jest niewyraźny?

Z rysunku mało rozumiem, wyraźny jest wystarczająco. Nie rozumiem w jaki sposób mam ustawić min i max kwadratu i zrobić do niego oś. Znalazłem jakiś czas temu silnik, który bazuje na takiej kolizji: https://github.com/atraczyk/2d-engine, tutaj używane min i max mają 2 wartości.

JoaWionek napisał(a):

Z rysunku mało rozumiem, wyraźny jest wystarczająco. Nie rozumiem w jaki sposób mam ustawić min i max kwadratu i zrobić do niego oś. Znalazłem jakiś czas temu silnik, który bazuje na takiej kolizji: https://github.com/atraczyk/2d-engine, tutaj używane min i max mają 2 wartości.

A Spróbuj nie szukać min i max, tylko Zrzutuj wierzchołki kwadratów (wieloboków).

tzn? Mam wypisać pozycje x i y dla każego wierzchołka?

Piszesz, ze Rozumiesz, ale my się nie rozumiemy:) Napisz mi dokładnie i zacytuj mnie z https://4programmers.net/Forum/C_i_C++/298059-kolizja_typu_sat_implementacja_w_grze?p=1410188#id1410188 który krok, nie Wiesz jak wykonać; wtedy będę mógł pomóc.

Tak, współrzędne wierzchołków w układzie odniesienia ekranu znasz, jeżeli prostokąty są ustawione bokami równolegle do osi tego układu to w zasadzie nic nie musisz robić, jeżeli jednak są obrócone to musisz znaleźć pozycje (x, y) wierzchołków w obróconym układzie współrzędnych, odłożyć te punkty na jego osie i patrzeć czy na siebie nachodzą czy nie.
Jak nie ogarniasz to poćwicz najpierw zderzenia nieobróconych prostokątów.

Yhm.

1. "Z iloczynu skalarnego znajdujesz do niego prostooadły;"
   Mamy te kwadraty, kwadrat jest zakodowany jako zbiór wierzchołków, czyli par liczb; znajdujemy, z prostej geometrii analitycznej, prostą przechodząca przez bok, jeśli się zdarzy, że mamy to w postaci parametrycznej, to mamy wektor równoległy do boku (a do algorytmu potzrebujemy prostopadły), to wtedy właśnie korzystamy z iloczynu skalarnego, żeby znaleźć ten protopadły wektor. Mamy, na przykład, wektor a = (1, 2), wiemy, że, gdy wektory są prostopadłe, ich iloczyn skalarny x * y = 0, to:
   [1, 2] * [x, y] = 0 =>
1 * x + 2 * y = 0 =>// z definicji iloczynu skalarnego
x = -2y
   Podstawiamy teraz, np., x = 1, to y = -2, i tak dalej, [1, -2], [2, -4] // gdy weźmiemiy x =2, generalnie każdy wektor postaci [c, -2c] // gdzie c rzeczywiste będzie prostopadły do naszego.
2. "Dokonujesz na ten prostopadły wektor projekcji punktów obu figur (wystarczy wziąć kluczowe punkty, rogi i po jednym z boku);"
   Wycofuję się z tych punktów na bokach, wystarczy wziąć wierzchołki i zrzutować je (znajdując projection matrix), tak jak zrobiłem na rysunku, na wektor z punktu wcześniejszego, dla przykładu, powiedzmy [1, -2]. Po zrzutowaniu, na ten wektor, wierchołków obu kwadratów, otrzymamy dwie listy czterech par liczb, do porównywania wystarczy wziąć pierwsze współrzędne, czyli tak naprawdę mamy dwie listy czterech liczb (niekoniecznie różnych), teraz sprawdzamy czy na siebie nie nachodzą - max pierwszej mniejszy od min drugiej, lub max drugiej mniejsze od min pierwszej (bo algorytm nie "widzi" tego tak jak my). No i powtórzyć operację dla wszystkich boków obu figur, jak żadne nie nachodzą to nie ma kolizji. Musisz tylk pamiętać, że jak w pierwszym punkcie wyjdzie Ci prosta postaci x = c, to do porównywania min i max w punkcie frugim bierzemy współrzędne y - kowe, x - sowe będą zerami.