Java보다 효율적인 배열 검색

Question

나는 LibGdx를 사용하여 게임을 코딩하고 있으며, 플레이어가 충돌 할 수있는 모든 내 벽의 개체가있는 배열을 가지고 있습니다. LibGdx를 사용하지 않는 사람들을 위해, 나는 ArrayList와 동일한 기능을 제공하는 LibGdx의 Array 클래스에 대해 말하고 있지만, 메모리 효율성을 염두에두고 만들어졌습니다. 나는 충돌을 검사 할 때,이 같은 충돌의 배열의 모든 벽을 통해 이동하고 확인하는 데 :

for(Wall w : walls) { 
    if(w.bounds().contains(player.bounds()) { 
    // handle collision 
    } 
} 

나는 내가 그 벽이 떨어져있는 경우에도 모든 벽을 통과하고 있기 때문에이 비효율적 실현 현재지도보기. 분명히 현재 카메라의 뷰포트에있는 벽과의 충돌을 확인하는 중이라면 (즉, 플레이어가 현재 볼 수 있음을 의미합니다) 플레이어가 충돌 할 때까지 플레이어가 충돌 할 수 없으므로 전체 배열을 지나는 데 아무런 포인트가 없습니다. 전망. 플레이어와 가까운 벽과의 충돌 만 확인하여 게임을 좀 더 효율적으로 만들려고했습니다. 내 게임에서는 모든 벽이 32x32 픽셀의 셀로 구성된 그리드 위에 고정되었습니다. 나는 충돌에 대한보다 효율적인 검색을 어떻게 만들 수 있는지 정말로 모른다. 해당 키에 vector2 위치를 사용하는 일종의지도처럼 사용할 수 있고지도의 플레이어 위치에서 특정 범위 내의 벽을 통해 플레이어의 위치를 ​​살펴볼 수 있습니까? 플레이어가 현재 어디에 있는지 만날 수있는 현재 벽이 10 개 밖에없는 경우 내 게임에서 100 개 이상의 벽을 모두 통과하지 못하는 코드를 보유하는 방법에 대해 정말 실종 상태입니다. 이게 말이 되니? 누군가 이런 식으로 할 수있는 좋은 방법을 설명 할 수 있을까요? 정말 고마워.

Answer 1

나는 하향식 RPT를 개발하는 동안 한 번 같은 실현에 들어갔다. 탑 다운 RPG에서 상상할 수있는 것보다 더 많은 벽이 있습니다. 여기

내가 그것을 해결하는 방법입니다

첫째 영역으로 세그먼트 맵이 즉) 종이 또는 무언가에지도를 그리는 부분으로 잘라..

두 번째 :지도의 각 세그먼트 섹션에 대한 픽셀 경계를 기록합니다.

세 번째 : 경계와 관련하여 플레이어의 위치를 ​​확인합니다.

마지막으로 : 경계 내의 벽만 확인하십시오. 무한 벽의 영역에서

이 더 이상 효율적이지

(빅 O 대해 말하기)를 제외한 모든 실용적인 목적이 룩업 번

---

if (boundary1.contains(player1)) { 

    for(Wall w : Boundary1Walls) { 
     if(w.bounds().contains(player.bounds()) { 
      // handle collision 
     } 
    } 
} 
else if (boundary2.contains(player1)) { 

    for (Wall w : Boundary2Walls) { 
     if(w.bounds().contains(player.bounds()) { 
      // handle collision 
     } 
    } 
} 

을 삭감에 유효하다 .... 계속 하시겠습니까?

참고 ... 나는 소프트웨어 개발을 위해 대학에 가기 전에 이런 식으로했기 때문에 BST와 같은 데이터 구조를 사용하지 않았습니다.이 구조는 BST와 관련하여 벽을 저장하는 데 사용할 수 있습니다. 좌표. 조회 시간이 매우 빠릅니다.

Answer 2

많은 충돌 충돌이 있습니다. 필요에 맞는 것을 찾으셔야합니다.

내 머리 꼭대기에서 생각할 수있는 한 가지 해결책은 다음과 같습니다.
벽 목록을 좌표에 정렬 된 상태로 유지하십시오. 새 벽을 만드는 경우 삽입 정렬을 사용하여 배열을 정렬하십시오. 충돌을 확인하려면 객체 좌표 (이 경우 플레이어가 실행 중일 가능성이 높음)를 가져와 이진 검색을 수행하여 플레이어에게 가장 가까운 벽을 찾습니다. 그런 다음 플레이어와이 벽이 충돌하는지 계산합니다.가장 가까운 벽이 충돌을 일으키지 않으면 다른 벽도 없다는 것을 확신 할 수 있습니다.

Answer 3

각 벽은 이러한 32x32 픽셀 격자 중 하나 이상에 있습니다. 그리드의 좌표를 x와 y라고합시다. 그리드 벽이있는 경우, 세트를 가져 좌표 격자의 작은 집합을 결정하는 위치의 좌표를 사용, 위치는 근처의 벽과 접촉하는 곳 조사하기 위해

HashMap<CoordPair,Set<Wall>> xy2wall 

에이를 입력하거나 이 CoordPairs에 의해 맵핑 된 Wall 세트. Player.bounds()가 적절한 좌표 집합을 제공 할 수 있다고 생각합니다.

32x32 격자의 결과가 너무 많으면 더 거친 격자를 사용할 수 있습니다.