알까기게임 충돌 탐색 알고리즘 최적화 문제입니다.
글쓴이: dflkj2323k@GitHub / 작성시간: 목, 2018/09/20 - 1:39오전
단순한 알까기 게임을 만들고있습니다.
중심 ax ay 에 알이 있습니다. amax는 알 최대개수, distance는 두 좌표간의 거리를 리턴합니다.
그 알들간의 충돌을 검사하기위해 이런 코드를 만들었습니다.
.
for(i=0; i<amax; i++){
for(j=i+1; j<amax; j++){
if(distance(ax[i],ay[i],ax[j],ay[j])<=aradius*2)
{
//i, j 알은 충돌함
}
}
}그런데 문제는 이걸 프레임마다 검사를 하다보니
알이 한두개 있다면 상관없겠지만
알이 80개 이상 넘어갈경우
렉이 걸린다는 겁니다.
지금 시간복잡도가 O(n^2)인데 더 줄일수있는 방법이 있는지 알아보고싶습니다.
전혀 부딪힐 가능성없는 먼곳이나 각도가 안맞는 알까지 충돌검사를 해야된다는게 확실히 시간낭비인거 같습니다.
Forums:
k-d tree를 검색해 보세요.
k-d tree를 검색해 보세요.
정말 감사합니다.
k-d트리를 검색해보니 이게 최근접 이웃 알고리즘이라는 보편적 문제로 있었습니다.
시간복잡도를 O(n)으로 줄일수 있다고 하니 한번 공부해보고 적용해봐야겠습니다.
프루닝
모든 알을 검사할 필요가 있을까요?
알이 움직일 경로를 어떤 직선으로 볼 때, 그 직선과 충돌할 수 있는 범위 내에 있는 구슬들만 검사하면 어떨까요.
처음 알이 움직이기 시작할 때, 충돌할 수 있는 알 목록을 구한 다음, 다음 프레임부터는 그 목록과만 비교 체크하면 일반적인 상황에선 좀 더 빠르게 동작할 수 있을 거 같아요
코드를 만들어봤습니다.
http://codepad.org/D2RyH6QI
#include <stdio.h> #include <inttypes.h> // 하나의 배열에서. 여러 좌표를. 비교 확인하는 프로그램 // 개선방향 // 시간 마다. 4분면 영역 안에서의. 충돌 계산 // 전체 충돌 계산으로 충돌검사 별도 int aradius = 2; int distance(int ax, int ay, int ax2, int ay2) { if((ax == -1 && ay == -1) || (ax2 == -1 && ay2 == -1)) return 0; int x = ax - ax2; int y = ay - ay2; printf("%d = %d - %d\n", x, ax, ax2); printf("%d = %d - %d\n", y, ay, ay2); x = abs(x); y = abs(y); int cnt = 0; if(x <= aradius) { cnt ++; } if(y <= aradius) { cnt ++; } if(cnt >= 2) { return 1; } return 0; } int main() { int i; int j; int amax = 10; int ax[10]; int ay[10]; for(i=0; i<amax; i++) { ax[i] = -1; ay[i] = -1; } ax[0] = 0; ay[0] = 0; ax[2] = 2; ay[2] = 3; ax[6] = 6; ay[6] = 7; ax[7] = 1; ay[7] = 1; // for(i=0; i<amax; i++) { printf("%d,%d\n", ax[i], ay[i]); } printf("-----------------------\n"); // for(i=0; i<amax; i++) { for(j=0; j<amax; j++) { if(i == j) { printf("%d,%d ", ax[i], ay[j]); } else { printf("-1,-1 "); } } printf("\n"); } printf("-----------------------\n"); // for(i=0; i<amax; i++) { for(j=i+1; j<amax; j++) { printf("%d %d %d %d \n", ax[i], ay[i],ax[j],ay[j]); if(distance(ax[i],ay[i],ax[j],ay[j]) == 1) //<= aradius*2) { //i, j 알은 충돌함 printf("충돌 발생\n"); } } printf("\n"); } printf("-----------------------\n"); return 0; } #if 0 0,0 -1,-1 2,3 -1,-1 -1,-1 -1,-1 6,7 1,1 -1,-1 -1,-1 ----------------------- 0,0 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 2,3 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 6,7 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 1,1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 -1,-1 ----------------------- 0 0 -1 -1 0 0 2 3 -2 = 0 - 2 -3 = 0 - 3 0 0 -1 -1 0 0 -1 -1 0 0 -1 -1 0 0 6 7 -6 = 0 - 6 -7 = 0 - 7 0 0 1 1 -1 = 0 - 1 -1 = 0 - 1 충돌 발생 0 0 -1 -1 0 0 -1 -1 -1 -1 2 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 7 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 2 3 -1 -1 2 3 -1 -1 2 3 -1 -1 2 3 6 7 -4 = 2 - 6 -4 = 3 - 7 2 3 1 1 1 = 2 - 1 2 = 3 - 1 충돌 발생 2 3 -1 -1 2 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 7 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 7 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 7 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 6 7 1 1 5 = 6 - 1 6 = 7 - 1 6 7 -1 -1 6 7 -1 -1 1 1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 ----------------------- #endif//영역을 비교하는 방식
http://codepad.org/5igM638W
#include <stdio.h> #include <inttypes.h> int aradius = 2; int main() { int i; int j; int amax = 10; int ax[10]; int ay[10]; int bx[10]; int by[10]; int cx[10]; int cy[10]; int cnt = 0; for(i=0; i<amax; i++) { ax[i] = 0; ay[i] = 0; bx[i] = 0; by[i] = 0; cx[i] = 0; cy[i] = 0; } ax[2] = 1; ay[3] = 1; bx[6] = 1; by[8] = 1; //a와 b에 1이 있는지 확인 for(i=0; i<amax; i++) { for(j=0; j<amax; j++) { if((ax[i] == 1) && (ay[j] == 1) || (bx[i] == 1) && (by[j] == 1) ) { printf("1"); cx[cnt] = i; cy[cnt] = j; cnt++; } else { printf("0"); } } printf("\n"); } printf("-----------------------\n"); //확인된 a와 b 에 위치 for(i=0; i<10; i++) { printf("cx:%d cy:%d\n", cx[i], cy[i]); } //cx:2 cy:3 //cx:6 cy:8 printf("-----------------------\n"); //b영역 안에. a영역이 있는지 확인 int i2; int j2; int c2; for(c2=0; c2<10; c2++) { if((cx[c2] == 0) && (cy[c2] == 0)) { break; } for(i2=-aradius+cx[c2]; i2<aradius+cx[c2]; i2++) { for(j2=-aradius+cy[c2]; j2<aradius+cy[c2]; j2++) { if(i2<0) continue; if(i2>=amax) continue; if(j2<0) continue; if(j2>=amax) continue; printf("[%d,%d]", i2, j2); if((ax[i2] == 1) && (ay[j2] == 1) || (bx[i2] == 1) && (by[j2] == 1) ) { if((cx[i2] == ax[i2]) && (cy[j2] == ay[j2])) { printf("A "); continue; } else if((cx[i2] == bx[i2]) && (cy[j2] == by[j2])) { printf("B "); continue; } else { printf("1 "); } // printf("%d,%d %d,%d %d,%d \n", ax[i2], ay[j2], bx[i2], by[j2], i2, j2); } else { printf("0 "); } } printf("\n"); } printf("------------------\n"); } return 0; } #if 0 0000000000 0000000000 0001000000 0000000000 0000000000 0000000000 0000000010 0000000000 0000000000 0000000000 ----------------------- cx:2 cy:3 cx:6 cy:8 cx:0 cy:0 cx:0 cy:0 cx:0 cy:0 cx:0 cy:0 cx:0 cy:0 cx:0 cy:0 cx:0 cy:0 cx:0 cy:0 ----------------------- [0,1]0 [0,2]0 [0,3]0 [0,4]0 [1,1]0 [1,2]0 [1,3]0 [1,4]0 [2,1]0 [2,2]0 [2,3]B [2,4]0 [3,1]0 [3,2]0 [3,3]0 [3,4]0 ------------------ [4,6]0 [4,7]0 [4,8]0 [4,9]0 [5,6]0 [5,7]0 [5,8]0 [5,9]0 [6,6]0 [6,7]0 [6,8]A [6,9]0 [7,6]0 [7,7]0 [7,8]0 [7,9]0 ------------------ #endif----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.
매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.
각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com
댓글 달기