는 인터넷 검색과 독서의 시간 후,

Question

그래서 분리 축 정리를 사용하여 충돌 감지를 구현하는 데 도움이 필요, 내가 찾은 SAT를 사용하여 충돌을 감지의 기본 과정입니다 :

for each edge of poly A 
    project A and B onto the normal for this edge 
    if intervals do not overlap, return false 
end for 

for each edge of poly B 
    project A and B onto the normal for this edge 
    if intervals do not overlap, return false 
end for 

그러나, 많은 방법으로 코드에서 구현하려고하면 충돌을 감지 할 수 없습니다. 다음 나의 현재 코드 :

for (unsigned int i = 0; i < asteroids.size(); i++) { 
    if (asteroids.valid(i)) { 
     asteroids[i]->Update(); 

     // Player-Asteroid collision detection 
     bool collision = true; 
     SDL_Rect asteroidBox = asteroids[i]->boundingBox; 

     // Bullet-Asteroid collision detection 
     for (unsigned int j = 0; j < player.bullets.size(); j++) { 
      if (player.bullets.valid(j)) { 
       Bullet b = player.bullets[j]; 

       collision = true; 
       if (b.x + (b.w/2.0f) < asteroidBox.x - (asteroidBox.w/2.0f)) collision = false; 
       if (b.x - (b.w/2.0f) > asteroidBox.x + (asteroidBox.w/2.0f)) collision = false; 
       if (b.y - (b.h/2.0f) > asteroidBox.y + (asteroidBox.h/2.0f)) collision = false; 
       if (b.y + (b.h/2.0f) < asteroidBox.y - (asteroidBox.h/2.0f)) collision = false; 

       if (collision) { 
        bool realCollision = false; 

        float min1, max1, min2, max2; 

        // Create a list of vertices for the bullet 
        CrissCross::Data::LList<Vector2D *> bullVerts; 
        bullVerts.insert(new Vector2D(b.x - b.w/2.0f, b.y + b.h/2.0f)); 
        bullVerts.insert(new Vector2D(b.x - b.w/2.0f, b.y - b.h/2.0f)); 
        bullVerts.insert(new Vector2D(b.x + b.w/2.0f, b.y - b.h/2.0f)); 
        bullVerts.insert(new Vector2D(b.x + b.w/2.0f, b.y + b.h/2.0f)); 
        // Create a list of vectors of the edges of the bullet and the asteroid 
        CrissCross::Data::LList<Vector2D *> bullEdges; 
        CrissCross::Data::LList<Vector2D *> asteroidEdges; 
        for (int k = 0; k < 4; k++) { 
         int n = (k == 3) ? 0 : k + 1; 
         bullEdges.insert(new Vector2D(bullVerts[k]->x - bullVerts[n]->x, 
               bullVerts[k]->y - bullVerts[n]->y)); 
         asteroidEdges.insert(new Vector2D(asteroids[i]->vertices[k]->x - asteroids[i]->vertices[n]->x, 
                asteroids[i]->vertices[k]->y - asteroids[i]->vertices[n]->y)); 
        } 

        Vector2D *vectOffset = new Vector2D(asteroids[i]->center.x - b.x, asteroids[i]->center.y - b.y); 

        for (unsigned int k = 0; k < asteroidEdges.size(); k++) { 
         Vector2D *axis = asteroidEdges[k]->getPerpendicular(); 
         axis->normalize(); 
         min1 = max1 = axis->dotProduct(asteroids[i]->vertices[0]); 
         for (unsigned int l = 1; l < asteroids[i]->vertices.size(); l++) { 
          float test = axis->dotProduct(asteroids[i]->vertices[l]); 
          min1 = (test < min1) ? test : min1; 
          max1 = (test > max1) ? test : max1; 
         } 
         min2 = max2 = axis->dotProduct(bullVerts[0]); 
         for (unsigned int l = 1; l < bullVerts.size(); l++) { 
          float test = axis->dotProduct(bullVerts[l]); 
          min2 = (test < min2) ? test : min2; 
          max2 = (test > max2) ? test : max2; 
         } 
         float offset = axis->dotProduct(vectOffset); 
         min1 += offset; 
         max1 += offset; 
         delete axis; axis = NULL; 
         float d0 = min1 - max2; 
         float d1 = min2 - max1; 
         if (d0 > 0 || d1 > 0) { 
          realCollision = false; 
          break; 
         } else { 
          realCollision = true; 
         } 
        } 

        if (realCollision) { 
         for (unsigned int k = 0; k < bullEdges.size(); k++) { 
          Vector2D *axis = bullEdges[k]->getPerpendicular(); 
          axis->normalize(); 
          min1 = max1 = axis->dotProduct(asteroids[i]->vertices[0]); 
          for (unsigned int l = 1; l < asteroids[i]->vertices.size(); l++) { 
           float test = axis->dotProduct(asteroids[i]->vertices[l]); 
           min1 = (test < min1) ? test : min1; 
           max1 = (test > max1) ? test : max1; 
          } 
          min2 = max2 = axis->dotProduct(bullVerts[0]); 
          for (unsigned int l = 1; l < bullVerts.size(); l++) { 
           float test = axis->dotProduct(bullVerts[l]); 
           min2 = (test < min2) ? test : min2; 
           max2 = (test > max2) ? test : max2; 
          } 
          float offset = axis->dotProduct(vectOffset); 
          min1 += offset; 
          max1 += offset; 
          delete axis; axis = NULL; 
          float d0 = min1 - max2; 
          float d1 = min2 - max1; 
          if (d0 > 0 || d1 > 0) { 
           realCollision = false; 
           break; 
          } else { 
           realCollision = true; 
          } 
         } 
        } 
        if (realCollision) { 
         player.bullets.remove(j); 

         int numAsteroids; 
         float newDegree; 
         srand (j + asteroidBox.x); 
         if (asteroids[i]->degree == 90.0f) { 
          if (rand() % 2 == 1) { 
           numAsteroids = 3; 
           newDegree = 30.0f; 
          } else { 
           numAsteroids = 2; 
           newDegree = 45.0f; 
          } 
          for (int k = 0; k < numAsteroids; k++) 
           asteroids.insert(new Asteroid(asteroidBox.x + (10 * k), asteroidBox.y + (10 * k), newDegree)); 
         } 
         delete asteroids[i]; 
         asteroids.remove(i); 
        } 
        while (bullVerts.size()) { 
         delete bullVerts[0]; 
         bullVerts.remove(0); 
        } 
        while (bullEdges.size()) { 
         delete bullEdges[0]; 
         bullEdges.remove(0); 
        } 
        while (asteroidEdges.size()) { 
         delete asteroidEdges[0]; 
         asteroidEdges.remove(0); 
        } 

        delete vectOffset; vectOffset = NULL; 
       } 
      } 
     } 
    } 
} 

bullEdges

가 asteroidEdges 유사하다 총알의 에지 벡터의리스트이며, bullVerts 소행성 [I] .vertices는 분명히 각 정점의 벡터리스트 각각의 총알이나 소행성에 대해.

솔직히 말하면, 나는 코드 보정을 찾고 있지 않으며, 눈이 신선합니다.

Answer 1

정리의 내 수학적 이해는 완전히 훌륭했다.대신 문제는 꼭지점 벡터에서 다각형의 중심점을 포함하지 않는다는 사실에 있습니다.

모두에게 감사드립니다.

Answer 2

당신은이 vectOffset 부분을 잘못 추가했습니다 - 소행성과 탄환 좌표계가 모두 동일합니다, 맞습니까? (바운딩 박스 테스트가 작동하는 경우라면되어야합니다.)

소행성 스퀘어입니까? 그렇다면 경계 상자 테스트는 항상 정확하며 realCollision 및 collision은 항상 동일해야합니다. 그렇지 않다면, asteroidEdges을 적절히 빌드하지 않아야합니다. - 정점 수를 반복해야합니다.

진지하게이 코드를 별도의 메소드로 만들고 단위 테스트를 작성하십시오. 유일한 방법입니다. 무슨 일이 일어나고 있는지 당신의 코드를 실행할 수 있습니다.

Answer 3

bullVerts.insert(new Vector2D(b.x - b.w/2.0f, b.y + b.h/2.0f)); bullVerts.insert(new Vector2D(b.x - b.w/2.0f, b.y - b.h/2.0f)); bullVerts.insert(new Vector2D(b.x + b.w/2.0f, b.y - b.h/2.0f)); bullVerts.insert(new Vector2D(b.x + b.w/2.0f, b.y + b.h/2.0f));

당신이 총알이 회전을 기대하는 경우에 소행성 클론을 생성하고 있지만 완전히 수직 인 것처럼이 코드는 항상 총알을 처리하는 것 같습니다. 그게 당신 문제일까요?

Answer 4

문제를 찾는 데 도움이되는 정보는 글 머리를 가리키는 것입니다. 코드의 다른 부분에 문제가 발생할 수 있습니다. 게다가, 당신의 요점이 충돌을 일으키지 만 총알이 보이지 않으면 당신은 볼만한 것을 얻을 것입니다.

즉, 솔루션이 나올 때까지 문제를 단순화하십시오. ;)

Answer 5

버그가있는 오프셋 된 것 이외에도 나머지 알고리즘 은 인 것처럼 보입니다. 문제를 발견하기 위해 추적을 시도 했습니까? 대신 스택에 그 일시 Vector2Ds을 모두 할당

• 왜 포인터를 어디서나 :

  BTW, 하드 코드가 한 눈에 읽을 수 있도록 몇 가지 문체 단점이있다?

• 왜 "good old"대신 CrissCross::Data::LList입니까? std::vector?
• 분명히 Vector2D에 과부하 연산자가 있습니까?

다음은 빠르고 간단하게 알고리즘을 구현 한 것입니다. 나는 그것을 약간 테스트했지만 아무 보증도하지 않았다 :

#include <vector> 
#include <limits> 

using namespace std; 

class Vector2D 
{ 
public: 
    Vector2D() : x(0), y(0) {} 
    Vector2D(double x, double y) : x(x), y(y) {} 

    Vector2D operator-(const Vector2D &other) const 
    { 
    return Vector2D(x - other.x, y - other.y); 
    } 

    double dot(const Vector2D &other) const 
    { 
    return x * other.x + y*other.y; 
    } 

    Vector2D perp() const 
    { 
    return Vector2D(-y, x); 
    } 

    double x,y; 
}; 

bool checkCollisionOneSided(vector<Vector2D> &object1, vector<Vector2D> &object2) 
{ 
    int nume = object1.size(); 
    for(int i=0; i<nume; i++) 
    { 
     Vector2D edge = object1[(i+1)%nume] - object1[i]; 
     Vector2D normal = edge.perp(); 

     double min1 = numeric_limits<double>::infinity(); 
     double min2 = min1; 
     double max1 = -numeric_limits<double>::infinity(); 
     double max2 = max1; 

     for(int j=0; j<object1.size(); j++) 
    { 
     double dot = normal.dot(object1[j]); 
     min1 = std::min(min1, dot); 
     max1 = std::max(max1, dot); 
    } 
     for(int j=0; j<object2.size(); j++) 
    { 
     double dot = normal.dot(object2[j]); 
     min2 = std::min(min2, dot); 
     max2 = std::max(max2, dot); 
    } 

     if(min2 > max1 || min1 > max2) 
    return false; 
    } 
    return true; 
} 

bool isColliding(vector<Vector2D> &object1, vector<Vector2D> &object2) 
{ 
    return checkCollisionOneSided(object1, object2) && checkCollisionOneSided(object2, object1); 
}