0
사각형 격자에 커넥터로 연결된 건물을 배치하는 게임을하고 있습니다. 아무것도 겹칠 수는 없습니다. 건물과 커넥터는 그리드 위에 있으면 변경할 수 없습니다. 그들은 언제든지 파괴 될 수 있습니다. 그리드는 왼쪽 하단 모서리가 (0,0)이되도록 정의됩니다.큰 격자에 배치 중복 확인
건물은 직사각형이며, 각 모서리는 1 - 4 단위 일 수 있습니다. 또한 5x5 사각형이 있습니다.
커넥터에는 시작점과 끝점이 있습니다. 그들은 겹칠 수 없으며, 1 단위 넓이입니다. 그들은 직선으로 갈 수 있습니다. 편집 : (왼쪽, 오른쪽, 위 아래로) 90도 어디서나 구부릴 수 있습니다. 무제한 길이.
그리드는 이상적으로 매우 큽니다 (200x200 이상). 즉, 수천 개의 이러한 개체와 커넥터가있을 수 있습니다.
개체가 만들어지면 무엇과도 겹치는 지 확인해야합니다. 비트 그리드를 만들면 크기가 300x300을 초과하여 엄청나게 커질 것입니다. 모든 객체의 목록을 만들면 어느 정도 범위 내에서 검색 할 수 있지만 커넥터는 어떻게 처리합니까?
비트의 2 차원 배열로 보는 것은 불가능합니다. 모든 건물을 색인화하고 x 좌표로 정렬 한 다음 y 좌표로 정렬해야합니다. 커넥터에 대한 선형 검색을 수행 할 수는 있지만 매우 지루하고 고통 스러울 것입니다.
누구에게 의견이 있습니까? 오후 8시 30 분 P.S. 나는 C++에서 이것을 수행하고있다
90 킬로 비트는 그리 크지 않습니다. 타겟 플랫폼의 제약 조건은 무엇입니까? 아마 quadtree를 봐야 할 것입니다. 커넥터는 일련의 1xN 직사각형으로 표현 될 수 있습니다. –
나는 메모리 오버 헤드를 하이퍼 최적화하려고 노력하고있다. 이제 언급 했으니 비트 배열을 사용할 수 있습니다. 이론적으로 1000x1000 격자가 배열로 표현되거나 객체 충돌을 감지하는 것이 가장 좋을까요? 어떻게 quadtree 도움이 될까요? – ithenoob
쿼드 트리는 '이 새 셰이프가 기존 셰이프와 교차하는지'와 같은 쿼리를 작성해야합니다. 철저한 선형 검색보다 우수해야합니다. –