은 Java에서 공의 2D 더미를 나타냅니다.

Question

자바를 사용하여 2 차원 '공'(원)을 모델링 (및 표시)해야하는 애플리케이션을 만듭니다. 나는 ArrayList의 Circle 개체 (내가 정의한 클래스로 원의 중심 x/y 픽셀 좌표, 반경, 색 및 속도가 x & y 방향으로 있음)를 만들어 시작했습니다. 나는 동그라미의 움직임을 제어하기 위해 java.util.Timer 객체와 TimerTask을 반복하여 사용한다. 원의 크기는 약 10-50 픽셀 반경에서 다양합니다.

내가 뭘하고 싶은지는 화면 맨 아래에서 볼이 떨어지는 것입니다 (x 축을 따라 무작위로 분포합니다). 화면 하단에 도달하면 바닥에 도달하는 바닥 공처럼 움직입니다. , 정지 된 볼에 도달하는 볼은 낮은/평평한 지점에 놓일 때까지 다른 볼 위에서 내리막으로 굴러갑니다. 앞으로는 자신의 행동을 좀 더 복잡하게 만들고 싶을 수도 있으므로 유연한 코드를 작성하여 쉽게 확장 할 수 있습니다. 현재 작동하는 방법은 매주기마다 매주마다 다른 모든 서클과 얼마나 가까운 지 확인합니다. 근처에 다른 서클이없는 경우 정상적으로 계속 떨어집니다. 두 개 (또는 그 이상)의 원이 서로 가깝다면 상호 작용 방법을 결정하는 코드가 있습니다.

적은 수의 원 (< 200)에 대해서는 완벽하게 작동하지만, 더 많은 수의 원 (> 400)을 얻으면 상당히 느리게 시작됩니다. 비교를 좀 더 빨리하기 위해 일부 로직을 최적화 할 수 있다고 확신하지만, 일부 구조에 원을 저장하는 방법이 있는지 여부를 알기 위해 정리되지 않은 ArrayList 외에도 쉽게 찾을 수있는 서클을 쉽게 찾을 수 있을지 궁금합니다. 그래서 나는 각 원을 다른 원과 비교하는 N^2 연산을 수행 할 필요가 없으며, 대신 원을 그것을 가장 가까운 5-10 원으로 비교합니다. 예를 들어, 모든 픽셀 (또는 5x5 픽셀의 정사각형)을 표현하고 그 중심이있는 원을 저장하기 위해 2D 배열을 사용하는 것을 고려했습니다. (즉, 근처의 셀에 원이 있는지 확인하고 휴식). 그러나 이것은 여전히 ​​500x1000 픽셀의 캔버스에 500 개의 원을 사용하는 것처럼 2 차원 배열에 빈 공간이 많아서 시간을 확인하는 데 낭비하는 것처럼 비효율적 인 것처럼 보입니다. 나는 또한 일종의 해시 맵을 고려해 봤지만 그 중 하나를 사용하는 좋은 방법을 생각하지 못했습니다.

사람은 2 차원 공간에서의 위치에 해당하는이 원을 저장하는 효율적인 방법을 생각하고 주변 원을 쉽게 찾을 수 있습니까? 미리 감사드립니다!

Answer 1

가까운 이웃을 찾기 위해 QuadTree를 사용할 수 있습니다. 또는 한 방향으로 정렬하면 구현하기가 훨씬 쉬우 며 후보 이웃들의 수를 작은 창으로 줄일 수 있어야합니다.

Answer 2

아마도 2D 배열에 대한 당신의 아이디어는 그렇게 미친 것이 아닙니다. 내가 원한다고 생각하는 것은 모든 서클 목록과 서클을 참조하는 2D 배열입니다. 따라서 매회마다 List<Circle>을 반복하여 각각을 확인할 수 있습니다. 각 원에는 x, y 좌표가 있으며 (x, y +/- 5)에 대해서만 배열을 반복하면됩니다. 이미 각 서클의 중심을 추적하고 있기 때문에 서클의 전체 공간을 확인할 필요가 없습니다. 센터를 잡고 다른 주변을 확인하십시오.