순전히 연속적인 물리 엔진을 개발 중이며 광범위하고 좁은 위상 충돌 감지를위한 알고리즘을 선택해야합니다. “순수하게 연속적”이란 교차 테스트를하지 않고 모든 충돌이 발생하기 전에 모든 충돌을 포착하고 TOI에서 주문한 “계획 충돌”스택에 배치하는 방법을 찾고자 함을 의미합니다.
넓은 위상
제가 생각할 수있는 유일한 연속적인 넓은 위상 방법은 각 바디를 원 안에 넣고 각 원이 다른 원과 겹칠 지 테스트하는 것입니다. 그러나 이것은 끔찍하게 비효율적이며 컬링이 부족합니다.
쿼드 트리와 같은 오늘날의 이산 충돌 컬링 방법에 어떤 연속적인 아날로그가 존재할지 전혀 모른다. 개별 엔진과 같이 부적절하고 무의미한 광범위한 테스트를 방지하려면 어떻게해야합니까? 또한 1 프레임 이상의 충돌을 볼 수 있기를 원합니다.
좁은 단계
나는 좁은 SAT를 불연속이 아닌 지속적인 검사에 적용 할 수 있었지만 논문이나 사이트에 더 나은 알고리즘이있을 것이라고 확신합니다.
내가 사용하는 다양한 빠르고 정확한 알고리즘은 무엇이며 각각의 장점 / 단점은 무엇입니까?
최종 참고 :
내가 말할 기술 이 아닌 알고리즘을 나는 아직 내가 오목, 볼록, 원형, 또는 심지어 구멍이있을 수 있습니다 다른 다각형을 저장하는 방법을 결정하지 않았기 때문에. 알고리즘에 필요한 것을 기반으로 결정을 내릴 계획입니다 (예 : 다각형을 삼각형 또는 볼록한 모양으로 나누는 알고리즘을 선택한 경우 다각형 데이터를이 형식으로 저장합니다).
답변
나는 단지 여기에 아이디어를 던지고 있습니다. 당신이 (최소한) current위치와 next위치 를 가지고 있다고 가정 ; 각 프레임마다.
두 개의 별도의 넓은 단계가 필요하고 좁은 단계가 필요합니다.
- 충돌이 발생한다는 것을 알 수 있습니다.
- 충돌이 실제로 발생하는 위치를 대략적으로 파악한 것 (예 : 넓은 위상 / 부정확 한 SAT)
- 마지막으로 좁은 단계는 두 번째 넓은 단계의 결과를 향상시킵니다.
초기의 광범위한 단계
당신은에 볼 수있는 공간 해시 합니다 (사용 next위치가 아닌 current초기 폭 넓은 위상을). 이것은 문제 공간을 충돌 후보 그룹으로 멋지게 분할합니다.
두 번째 넓은 단계
설명한 원 교차 방법을 사용하여 이진 다중 샘플을 수행하십시오. 다시 말해:
left = current
right = next
midpoint = (left + right) / 2
loop a desired amount of times tweaked to the accuracy you want:
is a collision occuring at midpoint?
right = midpoint
else?
left = midpoint
midpoint = (left + right) / 2
pointOfCollision = midpoint그 정확성 조정도 거리를 고려할 수 있습니다 . ‘길이 제곱’을 사용하면 완벽한 픽셀 결과를 얻을 수 있다고 생각 합니다 next - current.
좁은 단계
PMask 와 같은 것을 사용하여 이진 다중 샘플을 수행 하십시오. 논리는 위와 정확히 동일합니다. 다른 충돌 루틴을 사용합니다.
드디어
당신은 시간의 교차로를 해결할 수있을 것입니다 pointOfCollision, current당신의 현재 speed와 acceleration(당신이 합리적인 통합을 가정).
답변
알겠습니다. 질문을보다 구체적으로 업데이트했습니다. 좀 더 도와 드리겠습니다.
첫 번째 광범위한 단계 확인을 위해 공간 해싱을 강력히 권장 합니다.
기본적으로 화면을 동일한 크기의 격자로 나눕니다. 그런 다음 객체가 그리드 안에 있으면 1D 해시 테이블의 “버킷”에 추가합니다.
이것이 첫 번째 점검입니다. 객체가 동일한 버킷에 있지 않으면 교차 할 수 없습니다.
계속해서 객체가 (잠재적으로) 포함 된 버킷 목록이 생겼습니다. 다음 중 한 가지 방법으로 또 다른 광범위한 단계 점검을 수행 할 수 있습니다.
A.)이 버킷을 4 개의 다른 버킷으로 나누고 결과 1D 해시 테이블을 확인합니다. 동일한 버킷에 있지 않으면 충돌이 없습니다.
또는:
B.) 간단한 거리 점검을하고 정확성을 보장하기 위해 물체의 너비 및 / 또는 높이를 염두에 두십시오.
그러나 충돌 가능성이있는 경우는 어떻습니까?
그런 다음 이 라인을 따라 무언가를 추천 합니다 . 본질적으로 다각형 충돌 (복잡한 모양의 경우) 또는 덜 복잡한 모양의 사각형 / 원 사이의 일종의 혼합입니다.
또한, “충돌이 발생하기 전에 충돌을 잡아서 저장”하려면 항상 다음과 같은 작업을 수행 할 수 있습니다.
두 개의 객체가 동일한 버킷에 있으면 충돌 할 수 있습니다.
또한 물체가 머지 않아 충돌 할 수 있습니까? (속도, 물체 크기 및 거리 고려)
두 가지 모두에 대한 대답이 예라면 나중에 교차 테스트를 수행하기 위해 저장하십시오.
” 이전 답변
안타깝게도 “모든 충돌 유형 및 사용 대상”핸드북을 추적하지 못했습니다. 🙂
그러나 이것이 매우 광범위한 질문 이지만 시작하겠습니다.
여기 이와 관련된 좋은 (답변 된) 질문이 있습니다 .
여기에 N과 N +를 만든 사람들의 기사도 있습니다 .
말할 것도없이, 당신은 좋은 픽셀 당 충돌을 가지고 있습니다.
누구든지 모든 유형의 충돌에 유용한 목록을 가지고 있다는 것을 진심으로 의심하지만 시작하는 데 도움이됩니다.
그러나 필자가 필요로하는 충돌 유형 (그리고 결국에는 사용하게 될 충돌 유형)은 제작중인 게임 유형에 따라 크게 달라집니다. 그렇기 때문에 튜토리얼을 찾는 이유가 대부분입니다. 대부분의 사람들은 자신이 원하는 것에 대한 아이디어가 있다고 가정하여 해당 영역에서 도움을줍니다. 내 링크의 대부분이 특정 주제에 대한 튜토리얼이라는 것을 알고 있지만 튜토리얼이 더 많은 도움을 줄 것이라고 생각합니다. 목록은 한 가지 일이지만, 각 글 머리 기호에 대해 스스로 읽으면 더 구체적으로 요구 사항에 맞는 더 교육적인 결정을 내릴 수 있습니다.