지정된 공간에 블럭을 설치하지 못하게 막는 마인크래프트 플러그인을 만들고 있는데(c++ 20)
보호하고 싶은 공간을 담아두는 Area 클래스가 있음.
class Area { public: Vector3 first; Vector3 second; bool inArea(Vector3 &vec) { auto minX = std::min(first.x, second.x); auto maxX = std::max(first.x, second.x); auto minY = std::min(first.y, second.y); auto maxY = std::max(first.y, second.y); auto minZ = std::min(first.z, second.z); auto maxZ = std::max(first.z, second.z); auto &x = vec.x; auto &y = vec.y; auto &z = vec.z; return x >= minX && x <= maxX && y >= minY && y <= maxY && z >= minZ && z <= maxZ; } };그리고 Area클래스들을 저장하는 myMap과 플레이어가 블럭을 설치할 때 마다 호출되는 canPlaceBlock함수가 있음
std::map<int, Area> myMap; // 블럭 설치시 호출되는 함수 bool canPlaceBlock(Vector3 &blockLocation) { for (auto &it : std::views::values(myMap)) { if (it.inArea(blockLocation)) // 만일 myMap에 추가된 Area의 위치에 블럭을 놓으려 했다면 return false; // 블럭 설치 불가능 } return true; // myMap에 등록된 area들과 겹치지 않음, 블럭 설치 가능! }myMap에 담긴 데이터가 몇십개라면 괜찮겠지만 저게 수백 수천개가 들어가게 되고, 그걸 for loop으로 하나하나 검사하면 블럭을 놓을때 마다 처리속도가 너무 느려지지 않을까 싶은데..
이것보다 효율적인 방법이 있을까?
비트마스킹으로 1차 필터링 하셈
참고하겠읍니다 ㄳㄳ
일종의 충돌 판정이니까 그쪽 알고리즘 찾아보는것도 괜찮을듯
좌표가 들어가는 Area를 검색한다는 느낌으로 접근해보세여
진자 땡큐합니다 키워드로 뭘 넣어야 할지 고민했는데 collision으로 찾아보니깐 바로 나옴 그리고 좌표가 들어가는 area를 검색 << 이해가 쏙쏙됨 정말 ㄳㄳ
물리엔진에서 충돌감지 최적화하는 알고리즘을 가져다쓰면 되지 않을까 마인크래프트 물리엔진에서 사용하는 충돌감지 함수를 호출해서 쓸수있으면 가장 좋고
진짜 땡큐합니다 ㄳㄳㄳ
그냥 복잡한 알고리즘 안 쓰고
https://ideone.com/6zX6LJ
이런 느낌으로 하는 건 어떤가요
흠 kd interval tree를 짜거나 fractional cascading을 잘 쓰면 O(log n)에 될 것 같긴 한데 솔직히 개수가 수천 개밖에 안 되는 상황에서 쓰기엔 뇌절인 듯요
결함이 있는데다가 worst case가 너무 많음
그러네요 너무 생각없이 짠 듯 ㅋㅋ 그냥 interval tree나 짜죠