A Primer on AABB Collision Resolution - Deen Games

AABB (Axis Aligned Bounding Boxes) means two non-rotated boxes, that are aligned on one axis. · Collsiion detection means detecting if there is a ... Togglenavigation Home | About | Games Newsletter Discord Categories: Devlog| GameDesign| GameDevelopment| News| Retrospective| Technical| WebDevelopment| APrimeronAABBCollisionResolution Technical · Physics · 2020-01-30 · nightblade ThisblogpostincludesadiscussionaboutAABBcollisionresolution:whatitisandisn't,it'sstrengthsandweaknesses,somecommonpitfalls,andhowyoucan(hopefully)implementitinyourlow-levelgamingtoolofchoice,ifneeded. Ilearnedallthis(thesecondtime)aspartofaddingfast/stablecollisionresolutiontoPuffin,afast,lightweight2DgameenginebuiltontopofMonoGame. AABB,CollisionDetection,andCollisionResolution Somequickdefinitionstostart: AABB(AxisAlignedBoundingBoxes)meanstwonon-rotatedboxes,thatarealignedononeaxis.In2D,everythingonthesame"layer"or"z"isonthesameaxis;in3D,itmeansyourboxesareonthesameplane. Collsiiondetectionmeansdetectingifthereisacollision(twoAABBsoverlapping)orwillbeacollision(eg.in0.3sthesetwowillstartcolliding). Collisionresolutionmeansresolvingthecollision.Broadly,therearetwoapproachestothis:preventionorpre-collisionresolution(stopjustattheonsetofcollisionwhenthetwoAABBstouch),andpost-collisionresolution(oncetwoAABBsoverlap,movethembackwardintimeuntiltheynolongeroverlap). MyapproachtoAABBusespre-collisionresolution,becauseittendstobelesscomplexandmorestable. ProsandConsofAABB WhyshouldyouuseAABBcollisionresolution?Therearemanyotheroptions,suchascollisionpoints,sphere/linecollsionalgorithms,polygons,etc. ThestrengthsofAABBinclude: Itworkswellinmostcases.Mostgamescandowellenoughwithjustboundingboxesontheirentities. It'srelativelysimpletocode(math-wise),becauseit'sjustboxes. It'squitecheapcomputationally(eg.doesn'thaveanexpensivesquare-rootcalculation,unlikesphericalchecks) However,itincludessomedrawbacks: Itdoesn'tworkwithrotatedboxes Itdoesn'tworkwellwithnon-boxshapes Itrequiresextraworkforittoworkwellwithmulti-entitycollisions It'ssucceptibleto"tunnelling"(high-speedobjectsmovethroughsolidobjectsbecauseoftheirvelocity) Ifyoucanlivewiththoselimitations,IrecommendAABB,primarilybecauseitiscomputationallycheap(workswellwithahighnumberofcollidingentities). CollisionResolutionisComplex,likePhysics WhileAABBcollisionresolutionisrelativelyeasiertocode,itdoesn'tmeanit'seasytocode.Manygameframeworksdon'tincludecollisionresolution,becausethisispartofthephysicsengine. Readthatagain:it'softenpartofthephysicsengine.Physicsenginesarenotoriouslydifficulttogetright,andrequirelotsoffiddlingandcorner-caseevaluation.Evenhigh-qualityphysicsengineshavelimitations,suchastunneling. Ittookmearound10hourstodiscoverallthecaveatsandgetthistoworkright.Anditworkswell,includingwithmulti-entitycollisions.Testthoroughly. Thatsaid,myimplementationincludesafewbonusfeatures: It'sresistanttocollisiontunneling(butnotimpervious) Itworkswithmultipleobjectscollidingatthesametime Itallowsanobjecttooptionally"collideandslide"alongtheobjectitcollideswith Withthatoutoftheway,let'sdiveintotheactualtheoryofhowtomakeastableAABBresolution,andthensomecode. High-LevelDescriptionofAABB AABBcollisionresolutionworksbylookingattheXandYcomponentresolutionsofyourvelocity.Simplyput: Considertheintendeddestinationofyourmovingentity(whereitwillbeafterupdatingitsposition,notwhereitisnow) LookatthedistancedxtotravelbeforewecollideontheX-axisanddyfortheY-axis DividethesebyyourcomponentX-velocityandY-velocityrespectively(vxandvy)tofigureouthowlongbeforeeachaxiscollisiontakesplace(txandty) Resolvethecollisionontheaxisthatcollidesfirst Thisexcellentdiagram(credit:LaroLaroonGameDev.SE)showsamovingobject(A)thatwillcollidewithasecondobject(B).Basedonthecomponentvelocities,youcanseefromtheprojectedAboxthatthefastercollisionwillbeontheY-axisfirst. Becausecollisionresolutiontakesplaceonasingleaxisatatime,youmayenduphavingtoresolvethesamecollisionmultipletimestogetastableresolution.Ifindthatrunningthecollisionresolutiontwicesuffices. AndNow,theCode Below,Idiscusssomepseudocodethat'salmostthesameastheactual(C#)codefromPuffin.Thesamecodecanapplytoanyprogramminglanguageorframework. OneunorthodoximplementationdetailIused:wheneachentitymoves,Imakeanoteoftheir"intended"destinationX/Y.Ifthatlocationwouldcauseittocollideinsideanobject,Iinsteadupdateitsoitstopsjustatthepointofcollision.Inmypseudocodebelow,you'llseethisasintendedXandintendedY. Foreverycollidableentity,you'regoingtocompareittoeveryothercollidableentity.Sincewe'reusingAABBs,thisisprettysimple:justcomparethecoordinatesplusintendedmovementofthemovingentity,againsttheentitythatisn'tmoving: privatestaticboolisAabbCollision(floatx1,floaty1,intw1,inth1,floatx2,floaty2,intw2,inth2) { //Adaptedfromhttps://tutorialedge.net/gamedev/aabb-collision-detection-tutorial/ returnx1x2&& y1y2; } Yousimplycallthiswithe1.x+e1.velocity.x,e1.y+e1.velocity.y,e1.width,e1.height,e2.x,e2.y,e2.width,e2.heightanditwillreturniftheycollideornot. However,tostopatthepointofcollision,weneedtoconsiderourentity'svelocity:ifit'smovingright,thenthedistancetocollideontheX-axisistherightedgeofe1comparedtotheleft-edgeofe2.Ifit'smovingleft,thenvice-versa(leftedgeofe1vs.therightedgeofe2).ThesamethingapplieswhenweresolveontheY-axis. //AssumingwehavetwoAABBs,what'stheactualdistancebetweenthem? //eg.if`e1`isontheleftof`e2`,wewant`dx`tobe`e2.left-e1.right`. privatestatic(float,float)CalculateAabbDistanceTo(Entitye1,Entitye2) { floatdx=0; floatdy=0; if(e1.Xe2.X) { dx=e1.X-(e2.X+e2.Width); } if(e1.Ye2.Y) { dy=e1.Y-(e2.Y+e2.Height); } return(dx,dy); } Then,foreverycollidableentity,ifitresultsinanAABBcollisionwithanothercollidableentity,wefigureoutwhichaxiscollidesfirst,basedonwhichonecollidesfirsttime-wise: //Anotherentityoccupiesthatspace.Useseparatingaxistheorem(SAT) //toseehowmuchwecanmove,andthenmoveaccordingly,resolvingatwhichever //axiscollidesfirstbytime(notwhicheveroneisthesmallestdiff). (floatxDistance,floatyDistance)=CalculateAabbDistanceTo(entity,target); (floatxVelocity,floatyVelocity)=(entity.VelocityX,entity.VelocityY); floatxAxisTimeToCollide=xVelocity!=0?Math.Abs(xDistance/xVelocity):0; floatyAxisTimeToCollide=yVelocity!=0?Math.Abs(yDistance/yVelocity):0; Resolvingcollisionbasedoncollisiontimesolvessomecorner-caseswhereanobjectisveryclosetocollisionononeaxis,butmovingmuchfasterontheotheraxis(eg.aplayerfallingoffatallbuildingmovesintoit,andinsteadofcollidingagainsttheside,hecollideswiththetop). Onceweknowwhichcollisionisfirst,it'seasytoresolveifthecollisionisonlyononeaxis: floatshortestTime=0; if(xVelocity!=0&&yVelocity==0) { //ColliisononX-axisonly shortestTime=xAxisTimeToCollide; entity.IntendedMoveDeltaX=shortestTime*xVelocity; } elseif(xVelocity==0&&yVelocity!=0) { //CollisiononY-axisonly shortestTime=yAxisTimeToCollide; entity.IntendedMoveDeltaY=shortestTime*yVelocity; } Finally,themostcomplexcase:whatdowedoiftheobjectwouldcollideonbothX-andY-axes?Weresolvethefastestcollisionfirst: else { //CollisiononXandYaxis(eg.slideupagainstawall) shortestTime=Math.Min(Math.Abs(xAxisTimeToCollide),Math.Abs(yAxisTimeToCollide)); entity.IntendedMoveDeltaX=shortestTime*xVelocity; entity.IntendedMoveDeltaY=shortestTime*yVelocity; } Easy!Ifitwouldtake0.1stocollideontheX-axis,and0.2ontheY-axis,weincrementtheentity'sXandYbytheirvelocitytimes0.1(thefastercollisiontime). Finally,forstableresolutions,makesureyourunthecollisionresolutiontwiceperupdate.SinceMonoGame-basedframeworksgiveyoutheupdatetime,simplyruntheupdatetwice,withhalfoftheelapsedtime,eachupdate: varhalfElapsed=TimeSpan.FromMilliseconds(elapsed.TotalMilliseconds/2); //Resolvecollisionstwicetostabilizemulti-collisions. this.ProcessMovement(halfElapsed,entity); this.ProcessMovement(halfElapsed,entity); That'sit,you'redone! SlideonCollide Withbasiccollisionresolutionoutoftheway,youmightask"howdoIslideupagainstthetargetobjectinsteadofsimplystoppingabruptly?" Theanswertothatcausedabout50%ofmydevelopmenttime.Theansweris"youcollideasusualbutthenmoveontheotheraxisasmuchasisreasonable,"wherereasonablemeans"don'tmovesomuchyoucollidewithsomethingelse."Inthiscase,don'tslideifdoingsowouldlandyouinanotherAABBcollision. AnothercomplicationIcan'texplainwellismyneedtorefertothe"old"intendedX/Ydistances;I'mnot100%sureatthismomentwhyIneededthose,butthoseareneededforaproperresolution. Somecode: if(entity.SlideOnCollide) { //SettingoldIntendedX/oldIntendedYmightputusdirectlyinsideanothersolidthing. //Noworries,weresolvecollisionstwice,sotheseconditerationwillcatchit. //ResolvedcollisionontheX-axisfirst if(shortestTime==xAxisTimeToCollide) { //Slidevertically entity.IntendedMoveDeltaX=0; //Ifwe'reinacorner,don'tresolveincorrectly;moveonlyifwe'reclearontheY-axis. //Fixesabugwhereyoumovealotinthecorner(left/right/left/right)andsuddenlygothroughthewall. if(!isAabbCollision(entity.X,entity.Y+oldIntendedY,entity.Width,entity.Height, collideAgainst.X,collideAgainst.Y,target.Width,target.Height)) { entity.IntendedMoveDeltaY=oldIntendedY; } } //ResolvedcollisionontheY-axisfirst if(shortestTime==yAxisTimeToCollide) { //Slidehorizontally entity.IntendedMoveDeltaY=0; //Ifwe'reinacorner,don'tresolveincorrectly;moveonlyifwe'reclearontheX-axis. //Fixesabugwhereyoumovealotinthecorner(left/right/left/right)andsuddenlygothroughthewall. if(!isAabbCollision(entity.X+oldIntendedX,entity.Y,entity.Width,entity.Height, collideAgainst.X,collideAgainst.Y,target.Width,target.Height)) { entity.IntendedMoveDeltaX=oldIntendedX; } } } } WrappingitAllUp ThatconcludesasomewhatwhirlwindtourofAABBcollisiondetection.Ihopeyoucameoutofitunderstandingtheprosandcons,howtoassesswhenyouneeditornot,andenoughpseudo-codetoactuallygetitworkingforyou. Iwouldlovetohearfromyou!Ifyouhaveanyfeedback,pleasedropmeamessage/tweetonTwitter. Likedourupdates?Subscribetoournewslettertogetaccesstoourgamedemosandexclusiveinsiderupdates! «Newer Older» Copyright©NightBlade,2018+.Allrightsreserved.