Box2D-подобный столкновение с множеством кругов

Question

Я пытаюсь написать очень урезанный простой коллайдер, похожий на Box2D--, отсутствующий вся физика, вращение и т. Д. Я делаю это как для того, чтобы держать след в коде крошечным и понятным , а также просто изучить внутреннюю работу этих вещей лично.

Все, что я пытаюсь сделать, это столкнуться с кругами и линиями, и не дать им встать в друг друга.

Box2D делает это почти идеально - очень небольшое количество перекрытий! Однако, когда я пишу свой собственный простой симулятор, я получаю много перекрытий: .

Когда я запускаю ту же симуляцию с помощью Box2D (это всего лишь круги, преследующие точку в центре экрана), я не вижу видимого перекрытия во ВСЕХ.

В псевдокоде, это то, что я делаю:

For each Circle In List: 
    Determine who will collide with the circle in next step 
    Sort collisions by closest first 
    For each possible collision: 
     Add the unembed vector to the Circle's movement vector 

...and then: 

For each Circle In List: 
    At the movement to the circle 

Таким образом, если окружности не получить толкнул на что-нибудь другое, это также работает отлично. Когда вещи накапливаются, тем не менее, это НЕ работает, и я знаю, почему - unembeds просто накапливаются, и все толкаются и толкаются, потому что более поздние круги становятся неотвязными в более ранние круги, а в конце моделирования некоторые просто застревают внутри других , Огромный смысл.

Вот где я смущен: Рядом, как я могу судить, Box2D работает ТОЧНО одинаково - получите возможные столкновения, не связанные друг с другом, сделаны. Но Box2D никогда, никогда, не перекрывается, как у меня (или он становится настолько маленьким, чтобы не иметь значения).

Может кто-нибудь сказать мне, какой шаг я пропустил здесь? Я могу улучшить настройки (например, повторять всех, кто столкнулся снова и снова ... но Box2D, похоже, не делает этого, и я хочу понять, сохраняя код легко и быстро).

Спасибо!

Соответствующие реальный код ниже:

aO->mPos = x,y of object 
aO->mMove = x,y of movement this step 
aO->mRadius = radius of object 
aO->MovingBound() = bound of object including the move 

void Step() 
{ 
EnumList(MCObject,aO,mMovingObjectList) 
{ 
    mTree.GetAllNearbyObjects(aO->MovingBound().Expand(aO->mRadius/4),&aHitList); 
    aHitList-=aO; // Remove self from list 
    if (aHitList.GetCount()>0) 
    { 
     // Sort the collisions by closest first 
     if (mSortCollisions) 
     { 
      // Snip, took this out for clarity... 
      // It just sorts aHitList by who is closest 
      // to the current object 
     } 
     // Apply the unembedding 
     EnumList(MCObject,aO2,aHitList) CollideObjectObject(aO,aO2); 
    } 
} 

// Do the actual moves 
EnumList(MCObject,aO,mMovingObjectList) 
{ 
    mTree.Move(aO->mProxy,aO->Bound(),aO->mMove); 
    aO->mPos+=aO->mMove; 
    aO->mMove=0; 
} 
} 


void CollideObjectObject(MCObject* theO1, MCObject* theO2) 
{ 
float aOverlap=gMath.DistanceSquared(theO1->mPos+theO1->mMove,theO2->mPos+theO2->mMove); 
float aMixRadius=theO1->mRadius+theO2->mRadius; 
if (aOverlap<=aMixRadius*aMixRadius) 
{ 
    Point aUnembed=(theO1->mPos-theO2->mPos); 
    float aUnembedLength=aMixRadius-sqrt(aOverlap); 
    aUnembed.SetLength(aUnembedLength); 
    float aMod=.5f; 
    if (theO2->mCollideFlags&COLLIDEFLAG_STATIONARY) aMod=1.0f; 

    theO1->mMove+=aUnembed*aMod; 
} 
} 

Answer 1

Разрешающих столкновения между многими объектами является весьма трудной задачей, потому что, в дополнении к основнымам математике столкновений, вы должны работать намного усерднее при фиксации накопление математических ошибки, которые исходят от аппроксимативных решателей (физика в реальном мире работает на основе интеграции, которая диктует бесконечно малые временные шаги, а в наших симуляциях мы обычно решаем только 60 раз в секунду).

Давайте посмотрим на Box2D's constraint solver loop, located in b2island.cpp: На каждом шаге мира распознаватель столкновений работает не только один раз. Он будет повторять velocityIterations раз, что в официальных тестах обычно устанавливается в 6 или 8. И это вам тоже нужно будет сделать.