충돌 감지 방법론

Question

저는 약 6 개월 동안 C++로 프로그래밍을 해왔습니다. 아직 초보자이지만, 게임에 대한 충돌 감지 시스템을 만드는 데 어려움을 겪고 있습니다. 나는 다각형을 사용하는 방법을 고안해 냈고 그 다각형 안에 있는지 알아보기 위해 점을 테스트했습니다. 일단 그래픽에 대한 더 나은 핸들을 얻으면 모든 투사 물을 가진 모든 적을 테스트 한 애니메이션 루프를 실행 한 다음 이동 기능에 따라 모두 움직이게 할 것입니다.

충돌 감지를 처리 ​​한 방식은 그림 in this link으로 표시된 시스템을 사용하는 것입니다. 내가 만든 코드는 here과 그 아래에 있습니다. 내 질문은, 이러한 모든 프로세스가 모든 단일 프레임마다 모든 경계 상자 (모든 적)에 대해 너무 많이 실행되는 것입니까? 처리 속도와 효율성이 게임 디자인에서 매우 중요하다는 것을 알고 있습니다. 따라서이 유형의 방법론이 너무 오래 지속되었거나 프로세서가 실제로 얼마나 빨리 작동하는지 과소 평가합니까? 이러한 것들이 일반적으로 처리되는 방법에 대한 조언을 주시면 감사하겠습니다.

#include <iostream> 
#include <vector> 


class point 
{ 
    public: 
     point (int a, int b): x(a), y(b) {}; 
     ~point() {}; 

     int getX() {return x;} 
     int getY() {return y;} 

    private: 
     int x; 
     int y; 
}; 


class side 
{ 
    public: 
     side(point f, point s): first(f), second(s) {}; 
     ~side() {}; 
     point getFirst() {return first;} 
     point getSecond() {return second;} 

    private: 
     point first; 
     point second; 
}; 


class boundingBox 
{ 
    public: 
     boundingBox(std::vector <point> p); 
     ~boundingBox() {}; 

     std::vector <side> getSides() {return boundingSides;} 

    private: 
     std::vector <point> boundingPoints; 
     std::vector <side> boundingSides; 
}; 


boundingBox::boundingBox(std::vector <point> p) 
{ 
    boundingPoints = p; 

    // in the constructor, create a vector of sides from the points 
    for (std::vector <point>::iterator i = boundingPoints.begin(); i != boundingPoints.end()-1; i++) 
    { 
     boundingSides.push_back(side(*i, *(i+1))); 
    } 

    boundingSides.push_back(side (*(boundingPoints.end()-1), *(boundingPoints.begin()))); 
} 






bool collisionCheck(std::vector <side> s, point p) 
{ 
    std::vector <side> nodeSides; 

    int toleft = 0; 
    int toright = 0; 

    for (std::vector <side>::iterator i = s.begin(); i != s.end(); i++) 
    { 
     //if the Y value of the point being tested is between the Y values of a side, add a node 
     if (p.getY() > (*i).getFirst().getY() && p.getY() < (*i).getSecond().getY() || 
      p.getY() < (*i).getFirst().getY() && p.getY() > (*i).getSecond().getY()) 
     { 
      nodeSides.push_back(side ((*i).getFirst(), (*i).getSecond())); 
     } 


     // if the Y value of the point being tested is also the Y of the second point of the side... 
     if (p.getY() == (*i).getSecond().getY()) 
     { 
      //if it isn't the last side, and this side and the next strattle that y value, add a node 
      if (i != s.end()-1) 
      { 
       if ((*i).getFirst().getY() < p.getY() && (*(i+1)).getSecond().getY() > p.getY() || 
        (*i).getFirst().getY() > p.getY() && (*(i+1)).getSecond().getY() < p.getY()) 
       { 
        nodeSides.push_back(side ((*i).getFirst(), (*i).getSecond())); 
       } 
      } 

      //if it is the last side, and this side and the first side strattle that y value, add a node 
      else if ((*i).getFirst().getY() < p.getY() && s.front().getSecond().getY() > p.getY() || 
       (*i).getFirst().getY() > p.getY() && s.front().getSecond().getY() < p.getY()) 
      { 
       nodeSides.push_back(side ((*i).getFirst(), (*i).getSecond())); 
      } 
     } 
    } 

    for (std::vector <side>::iterator i = nodeSides.begin(); i != nodeSides.end(); i++) 
    { 
     double deltaY = (*i).getSecond().getY() - (*i).getFirst().getY(); 
     double deltaX = (*i).getSecond().getX() - (*i).getFirst().getX(); 

     double slope = deltaX - deltaY; 

     double x = (p.getY() - (*i).getSecond().getY() + (slope * (*i).getSecond().getX()))/slope; 

     if (x < p.getX()) 
     { 
      toleft++; 
     } 

     else 
     { 
      toright++; 
     } 
    } 


    std::cout << "Analysis: " << toleft << " nodes to the left, " << toright << " nodes to the right." << std::endl; 

    if (toleft % 2 == 0) 
    { 
     std::cout << "return false, does not hit" << std::endl; 
     return false; 
    } 

    else 
    { 
     std::cout << "return true, hits" << std::endl; 
     return true; 
    } 
} 






int main() 
{ 
    std::vector <point> points; 

    points.push_back(point(3, 5)); 
    points.push_back(point(1, 13)); 
    points.push_back(point(7, 16)); 
    points.push_back(point(14, 14)); 
    points.push_back(point(8, 13)); 
    points.push_back(point(9, 11)); 
    points.push_back(point(17, 13)); 
    points.push_back(point(16, 18)); 
    points.push_back(point(21, 15)); 
    points.push_back(point(17, 9)); 
    points.push_back(point(9, 7)); 
    points.push_back(point(12, 5)); 
    points.push_back(point(14, 7)); 
    points.push_back(point(15, 2)); 
    points.push_back(point(6, 3)); 

    boundingBox enemy(points); 

    point hitSimp(13, 4); 
    point hitComp(19, 15); 
    point missNear(10, 12); 
    point missFar(100,100); 

    collisionCheck(enemy.getSides(), hitSimp); 

    collisionCheck(enemy.getSides(), hitComp); 

    collisionCheck(enemy.getSides(), missNear); 

    collisionCheck(enemy.getSides(), missFar); 

    return 0; 
} 

Answer 1

프로그램이 너무 많은 충돌을 확인하여 준수 할 경우, 당신은 다각형 충돌 시험을하기 전에 당신은 또한 최초의 축 정렬과 중심의 경계 상자와 같은 간단한 경계 볼륨을 확인할 수 있습니다 Quad Trees

로 본다.