범위별로 대규모 배열 또는 기타 데이터 구조 탐색

스네이크 게임에서 지도에 많은 음식이 있다고 상상해 보세요. 프로그램은 (지도의 좌표에 따라) 뱀의 머리가 음식과 충돌하는지 여부를 감지해야 합니다.
음식 정보를 저장하기 위해 배열을 사용하는 경우 배열을 순회해야 합니다. 그러나 음식이 많은 경우(배열이 큰 경우) 특정 범위 내의 음식만 충돌할 수 있으므로 완전한 순회가 필요하지 않습니다.
문제는 배열 전체를 순회하지 않고 좌표를 기준으로 충돌할 수 있는 음식을 어떻게 찾는가입니다.

내가 생각할 수 있는 것은 array_filter를 사용하는 것이지만 본질적으로 여전히 순회 중입니다.
배열 없이 다른 데이터 구조를 사용할 수 있는 방법이 있다면 제공할 수도 있습니다.
게임을 해본 친구들이라면 좋은 해결책이 나올 수도 있겠네요.

답글 내용:

스네이크 게임에서 지도에 많은 음식이 있다고 상상해 보세요. 프로그램은 (지도의 좌표에 따라) 뱀의 머리가 음식과 충돌하는지 여부를 감지해야 합니다.
음식 정보를 저장하기 위해 배열을 사용하는 경우 배열을 순회해야 합니다. 그러나 음식이 많은 경우(배열이 큰 경우) 특정 범위 내의 음식만 충돌할 수 있으므로 완전한 순회가 필요하지 않습니다.
문제는 배열 전체를 순회하지 않고 좌표를 기준으로 충돌할 수 있는 음식을 어떻게 찾는가입니다.

내가 생각할 수 있는 것은 array_filter를 사용하는 것이지만 본질적으로 여전히 순회 중입니다.
배열 없이 다른 데이터 구조를 사용할 수 있는 방법이 있다면 제공할 수도 있습니다.
게임을 해본 친구들이라면 좋은 해결책이 나올 수도 있겠네요.

Redis의 정렬 세트 유형은 귀하의 요구 사항을 충족할 수 있습니다. http://redis.readthedocs.io/e...

이렇게 생겼을 것 같아요:

• 먼저 욕심쟁이 뱀의 음식은 공입니다. 음식을 저장하는 배열은 C++에서 사용할 수 있는 맵이 있습니다.

그런 다음 Map이라는 배열을 열 수 있습니다. 배열의 크기는 맵의 w
• h입니다. 그런 음식 <(x,y), r>이 있다고 가정하면 Map이 필요합니다. 다음과 같이 할당됩니다: Map[w

  x + y] = r; 음식의 최대 반경을 나타내는 maxR 항목을 기록합니다. maxR=max(r).

마지막으로 뱀 머리의 위치를 ​​(a, b)라고 가정하고 충돌을 판단하려면 (a, b)로 원의 모든 좌표 (x, y)를 순회해야 합니다. )를 중심으로 하고 반경을 maxR로 하고, r = Map[w*x + y]를 꺼내서 now_r = dis((a,b), (x,y))와 비교합니다. r>=now_r이면 뱀이 이 음식을 먹는다는 뜻이고, 이보다 작으면 먹을 수 없다는 뜻이라면 계속해서 다음 좌표로 판단하세요.
사실 실제로 해보면 먹이를 다 순회해야 한다고 추정하는데, 욕심쟁이 뱀은 먹이가 그리 많지 않습니다.