Sprawdzanie czy obiekt jest widoczny przez gracza w grze 2D w c++

Question

Hej, robię grę 2D (w formie labiryntu) i chciałbym sprawdzić czy różne obiekty na mapie są widoczne przez gracza. Ściany labiryntu przechowuję w tablicy; ściana zdefiniowana jest jako struktura:

struct edge {
   float s_x;
   float s_y;
   float e_x;
   float e_y;
}

Do dyspozycji mam pozycję gracza i pozycję obiektu którego widoczność sprawdzam. Dodam jeszcze że każdy edge jest zawsze albo pionowy albo poziomy.

Generalnie chodzi mi o sprawdzenie czy na drodze gracz-obiekt znajduje się jakiś edge, ale nie mam pomysłu jak to zakodować.

Z góry dziękuję za wszystkie odpowiedzi i szczęśliwego nowego roku :)

Answer 1

Cały problem można zredukować do sprawdzenia czy dwa odcinki AB i CD przecinają się. Założenia:

A - pozycja gracza, B - pozycja obiektu, CD - krawędź ściany

Sposób 1: Oblicz punkt przecięcia dwóch prostych. Sprawdź czy punkt przecięcia leży na dwóch odcinkach. Troszkę słabszy sposób.

Sposób 2: Nie musisz wiedzieć gdzie znajduje się punkt przecięcia, ale potrzebujesz troszkę więcej matematyki. Przecięcie występuje punkty A i B zostaną rozdzielone odcinkiem CD. Wówczas każda z par ACD i BCD oraz ABC i ABD muszą mieć różną orientację. Przykładowo ABC jest zorientowane zgodnie ze wskazówkami zegara gdy:

 

 

 

Możemy to zapisać w ten sposób jeżeli nie przejmujemy się kolinearnością punktów:

bool is_counterwise(vec A, vec B, vec C) { 
    return (C.y - A.y) * (B.x - A.x) > (B.y - A.y) * (C.x - A.x);
}

bool intersect(vec A, vec B, vec C, vec D) {
    return is_counterwise(A, C, D) != is_counterwise(B, C, D)
        && is_counterwise(A, B, C) != is_counterwise(A, B, D);
}

Pewnie istnieje bardziej optymalne rozwiązanie gdy krawędzie ścian są zawsze pionowe, lub poziome. Teraz wystarczy sprawdzić czy któraś z która z krawędzi przecina się z odcinkiem gracz-obiekt:

bool has_intersect = false;
for (auto& edge : edges) {
    if (intersect(objPos, playerPos, edge.v1, edge.v2)) {
        has_intersect = true;
        break;
    }
}

Comments

wow, wielkie dzięki