렌더링 전에 y 값으로 객체 정렬?

Question

나는 포켓몬이나 젤다 같은 2D 탑 다운 45도 게임을 가지고있다. 객체의 y 값은 깊이를 결정하므로 y 값의 순서로 객체를 그려야합니다. 예를 들어 나무 뒤에 서있을 때, 나무가 당신의 나무 꼭대기에 서있는 것처럼 보입니다.

현재의 디자인은 타일 열을 그려서 그 행에 서있는 모든 플레이어를 그린 다음 다음 행을 그려서 그 위에 서있는 모든 플레이어를 그립니다. 이 방법을 사용하면 플레이어보다 y 값이 높은 타일을 앞에 그려서 깊이를 시뮬레이션 할 수 있습니다.

그러나 내 플레이어는 현재 모든 타일이 그려진 후 반복되고 그려지는 객체 인 std::vector입니다. 내 방법이 작동하려면 타일의 행마다 의 벡터를 반복하거나 현재 행에있는 경우에만 렌더링하거나 모든 플레이어를 y 값별로 정렬합니다. 이 두 가지 방법 모두 상당히 CPU 집약적 인 것처럼 보입니다. 어쩌면이 생각을 다 끝내고이 유형의 게임에서 깊이를 시뮬레이션하는 간단한 방법이 있습니다.

편집 : 이 게임은 MMORPG 형 게임이기 때문에 잠재적으로이 많은 플레이어/NPC의 도보 될 나는 매우 효율적인 방법이 필요한 이유 주위에 있었다.

아이디어 나 의견을 보내 주시면 감사하겠습니다.

감사

Answer 1

(당신이 그것을 읽는다면, 내 원래의 제안을 Disgregard;.이 바보였다)

당신이 렌더링 지금까지 내가 말할 수있는, 당신은 기본적으로 정렬 된 컨테이너 매번 반복을 가지고 틀; 이것에 대한 계산상의 불이익이있을 것이고, 복사와 정렬을 할 때마다 (O (N log N) sorting time) 나쁘지 않을 것입니다.

영리한 데이터 구조가 도움이 될 수 있습니다. 예를 들어, 각 요소로서 게임 객체의 벡터를 포함하는 배열. 배열의 각 요소는 바둑판 식 배열의 행을 나타내며 개체의 벡터를 반복하고 깊이 버퍼 배열로 저장합니다 (대략 O (N) 시간이 소요됨). 그런 다음 각 행을 나타내는 벡터를 반복하고 각 객체를 다시 O (N)로 그립니다.

아마도 더 깨끗한 z 버퍼링 기술이있을 수 있지만 독자들을위한 연습으로 남겨 둘 것입니다.

Answer 2

vector 대신 std::set 또는 std::map을 사용하여 개체를 정렬 된 순서로 유지할 수 있습니다. 불행히도 자신의 위치를 ​​간단히 수정할 수는 없으므로 y 좌표를 변경해야 할 때마다 제거/삽입해야합니다.

Answer 3

다른 기준에 따라 플레이어를 정렬하지 않으려는 경우 플레이어를 반복 할 때마다 플레이어를 y 좌표로 정렬하면됩니다. 입력이 대부분 정렬 될 때 선형 시간으로 실행되는 정렬을 사용하는 한이 단계에서 O (n log n) 시간이되지 않을 것입니다. 저는 여러분의 선수 세트가 천천히 변화하고 y 좌표가 천천히 변할 것이라는 가정을하고 있습니다. 이 경우 벡터를 정렬해야 할 때마다 이미 대부분 정렬되고 Smooth sort 또는 Tim sort 같은 선형 시간으로 실행됩니다.

Tim 계열 here의 구현을 찾을 수있는 것처럼 보입니다.

Answer 4

공간이있는 경우, 배열의 색인을 행 번호로 사용하고 배열에 플레이어 행을 포함하는 배열로 플레이어 목록을 만드는 것이 좋습니다.

앞서 언급했듯이 플레이어가 다른 행으로 이동할 때마다 약간의 추가 메모리가 필요할 것이지만 드로잉은 단순히 행 반복을 통해 플레이어를 그리는 문제입니다 그 행에.