Collision Detection
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Collision Detection as PDF for free.
More details
- Words: 1,084
- Pages: 14
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
,VQ WLWZRQGHUIXOWRPRYHWKURXJKWKHYLUWXDOZRUOGLQD'JDPH"7KHZD\\RXFDQZDONLQWR ZDOOVDQGVOLGHDORQJWKHPDV\RXIUHHO\WXUQZLWKRXJJHWWLQJ\RXUUDLOJXQVWXFNEHWZHHQ \RXDQGWKHZDOO"7KHZD\\RXDQG\RXURSSRQHQWFDQUXQDWHDFKRWKHUVZRUGVGUDZQ DFWXDOO\VWRSZKHQ\RXUHDFKHDFKRWKHUDQGFDQWKHQEDFNDZD\ZLWKRXWZRUU\LQJDERXW \RXUVKLHOGJHWWLQJFDXJKWLQKLVFKDLQPDLO"7KHZD\\RXFDQFLUFOHVWUDIH\RXURSSRQHQWRYHU XQHYHQJURXQGZLWKRXWHYHUKDYLQJWRZRUU\DERXWWULSSLQJ",QWKHUHDOZRUOG\RXZRXOGKDYH WRZRUU\DERXWWKLVNLQGRIVWXII« $VGHYHORSHUVZHFDQ WDIIRUGWRGRFROOLVLRQGHWHFWLRQEHWZHHQHYHU\SRO\JRQRIDFKDUDFWHU DQGWKHLUHQYLURQPHQWRQHYHQWKHEHVWFXUUHQWKDUGZDUH LIZHGLGQRWRQO\ZRXOGRXU JDPHVEHSDLQIXOO\VORZEXWZH GDOVRUXQLQWRSUREOHPVOLNHWKRVHGHVFULEHGDERYH8VXDOO\D GHFHQWVSDWLDOSDUWLWLRQLQJV\VWHPDQGWKHXVHRIVSKHUHVWRERXQGFRPSOH[PRELOHREMHFWVOHW XVSHUIRUPFROOLVLRQGHWHFWLRQURXWLQHVWKDWDUHYHU\IDVWDQGRQO\LQYROYHWKHPLQLPXP QXPEHURISRO\JRQV1RWRQO\LVLWIDVWHUEXWLWKHOSVDYRLGHQWDQJOLQJERWKSOD\HUFKDUDFWHUV DQGQRQSOD\HUFKDUDFWHUVLQWKHHQYLURQPHQWDQGHDFKRWKHU 7LP6FKURHGHUV VDUWLFOH&ROOLVLRQ'HWHFWLRQ8VLQJ5D\&DVWLQJLQWKH$XJXVWLVVXHRI *DPH'HYHORSHUPDJD]LQHIRFXVHGRQGHWHFWLQJFROOLVLRQVEHWZHHQVSKHUHVDQGSRO\JRQV7KLV DUWLFOHFRPSOLPHQWVWKHLQIRUPDWLRQSUHVHQWHGWKHUHE\H[SODLQLQJKRZWRGHWHFWFROOLVLRQV EHWZHHQWZRVSKHUHVDQGGHWHUPLQHZKDWWKH\ OOGRDIWHUWKH\FROOLGH7KLVLVXVHIXOQRWRQO\ IRUJDPHVOLNHSRROZKHUHDFFXUDWHFROOLVLRQRIVSKHUHVLVNH\EXWDOVRLQJDPHVZKHUH FKDUDFWHUVDQGRWKHUPRELOHREMHFWVDUHERXQGHGE\VSKHUHVWKHVHFDQEHXVHGWRTXLFNO\ GHWHUPLQHLIWKH\KDYHEXPSHGLQWRHDFKRWKHU 7RPDNHLWHDVLHUWRH[SODLQDOOWKHH[DPSOHVZLOOEHILUVWLQ'$ODWHUVHFWLRQRIWKLVDUWLFOH ZLOOH[SODLQKRZWRDSSO\WKHVDPHDOJRULWKPVWR')RUWKHSXUSRVHVRIWKLVDUWLFOHDFLUFOH ZLOOEHUHSUHVHQWHGE\WKHSRLQWDWLWVFHQWHUDQGLWVUDGLXV 5DFN HP 3UR[LPLW\'HWHFWLRQEHWZHHQWZRVWDWLRQDU\FLUFOHV
$DQG%FXUUHQWO\WRXFKLQJ"7KHDQVZHUDV, PVXUH\RXDOUHDG\
$UHWZRVWDWLRQDU\FLUFOHV
NQRZLVYHU\VLPSOH7ZRFLUFOHVDUHLQFRQWDFWZLWKHDFKRWKHULIDQGRQO\LIWKHGLVWDQFH EHWZHHQWKHLUFHQWHUVLVOHVVWKDQRUHTXDOWRWKHVXPRIWKHLUUDGLL6RILQGWKHGLVWDQFH EHWZHHQWKHFHQWHUVRIWKHWZRFLUFOHVXVLQJWKHHTXDWLRQ
7KHQDGGWKHUDGLLRIWKHWZRFLUFOHVWRJHWKHU,IWKHVXPRIWKHUDGLLLVJUHDWHUWKDQRUHTXDOWR
'LVWWKHQWKH
FLUFOHVDUHWRXFKLQJ6LQFHPXOWLSOLFDWLRQVDUHOHVVFRPSXWDWLRQDOO\H[SHQVLYHWKDQVTXDUHURRWV\RXVKRXOG
VSHHGXSWKLVFRGHE\QRWSHUIRUPLQJWKHVTXDUHURRWZKHQFDOFXODWLQJWKHGLVWDQFHDQGLQVWHDGVTXDUHWKH VXPRIWKHUDGLL7KHFRGHEHORZVKRZVDVDPSOHLPSOHPHQWDWLRQXVLQJWKLVVKRUWFXW
double deltaXSquared = A.x - B.x; // calc. delta X deltaXSquared *= deltaXSquared; // square delta X
double deltaYSquared = A.y - B.y; // calc. delta Y deltaYSquared *= deltaYSquared; // square delta Y // Calculate the sum of the radii, then square it
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
double sumRadiiSquared = A.radius + B.radius; sumRadiiSquared *= sumRadiiSquared; if(deltaXSquared + deltaYSquared <= sumRadiiSquared){ // A and B are touching }
)RUWKLVSUREOHP\RXDUHJLYHQDFLUFOH$WKDWLVPRYLQJWKURXJKDYLUWXDOZRUOG2YHUDILQLWH SHULRGRIWLPHZKLFKZH OOFDOOW$PRYHVDFHUWDLQGLVWDQFHLQDFHUWDLQGLUHFWLRQ:H OO UHSUHVHQWWKLVPRYHPHQWE\DYHFWRU9$OVRLQWKLVYLUWXDOZRUOGLVDFLUFOH%WKDWLVQRW PRYLQJ7KHSUREOHPLVWRILJXUHRXWLI$FRPHVLQWRFRQWDFWZLWK%ZKLOHLWLVPRYLQJDORQJ9 DQGLILWGRHVE\ZKDWDPRXQWGRZHKDYHWRVKRUWHQ9VRWKDW$FRPHVWRUHVWMXVWDWWKH SRLQWRIFRQWDFWZLWK%"$QLOOXVWUDWLRQRIWKHSUREOHPLVVKRZQLQILJXUH
)LJXUH ,OOXVWUDWLRQRIWKH'\QDPLF6WDWLF &ROOLVLRQ3UREOHP
/HYHUDJLQJ6WDWLRQDU\&ROOLVLRQ
7KHILUVWDQGPRVWREYLRXVVROXWLRQWRWKLVZRXOGEHWRXVHWKHVWDWLRQDU\FROOLVLRQPHWKRG GHVFULEHGDERYHRQWKHFKDQJLQJGHVWLQDWLRQORFDWLRQRIFLUFOH$,QRWKHUZRUGVPRYHFLUFOH$ WRWKHHQGRIWKHPRYHPHQWYHFWRUDQGWKHQWHVWLW VQHZSRVLWLRQIRUFROOLVLRQV,I$LVLQ FRQWDFWZLWKDQRWKHUFLUFOHLQLWVQHZORFDWLRQ\RXKDYHWZRFKRLFHV
$EHWWHUDSSURDFKZRXOGEHWRXVHWKHPRYHPHQWYHFWRU9WRUHSUHVHQWWKHFLUFOHDVLWPRYHV WKURXJKWKHZRUOG1RZDOOWKHFROOLVLRQGHWHFWLRQLVVLPSOLILHGGRZQWRDYHFWRUWHVWHGDJDLQVW DVWDWLFFLUFOH7KLVDSSURDFKGRHVRQHWHVWWRVHHLI9WRXFKHV%,ILWGRHVQRWFROOLGHWKHQ\RX DUHGRQHWHVWLQJ
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
7KLVVROXWLRQKDVSUREOHPVDVZHOO&RQVLGHUWKHVLWXDWLRQVKRZQLQILJXUH7KHPRYHPHQW YHFWRU9IURPWKHFHQWHURI$GRHVQRWFRPHLQWRFRQWDFWZLWKDQ\WKLQJ+RZHYHULWRQO\ FKHFNVWKHSDWKWUDYHOHGE\WKHFHQWHURI$IRUFROOLVLRQDQGWKHERWWRPRUWRSFRXOGVWLOO FROOLGHZLWK%HYHQLIWKHPLGGOHGRHVQRW
)LJXUH
$SRVVLEOHVROXWLRQWRWKLVSUREOHPLVWRWHVWDJDLQVWWZRPRUHYHFWRUVFRPLQJIURPWKHHGJHV RIWKHPRYLQJFLUFOHSDUDOOHOWRWKHPRYHPHQWYHFWRU9:KLOHWKLVPD\IL[WKHSUREOHP GHVFULEHGDERYHZHFDQVHHLQILJXUHWKDWLIZHDGMXVWWKHPRYHPHQWYHFWRU9WREHWKH OHQJWKRIWKHFOLSSHGVHFRQGYHFWRUWKHFLUFOHVZLOOVWLOORYHUODS$OVRLIWKHPRYLQJFLUFOHLV ODUJHUWKDQWKHVWDWLFRQHWKHVWDWLFRQHPLJKWILWEHWZHHQWKHWRSDQGFHQWHUYHFWRUVRU EHWZHHQWKHFHQWHUDQGERWWRPYHFWRUVVRWKHFROOLVLRQZRXOGQRWEHGHWHFWHGDWDOO7KH PRYLQJFLUFOHZRXOGDSSHDUWRJRULJKWRYHUWKHVPDOOHUVWDWLFRQH2EYLRXVO\WKLVLVQRWWKH FRUUHFWDQVZHUIRUFROOLVLRQGHWHFWLRQ
)LJXUH $Q$OJRULWKP7KDW:RUNV
7KHILUVWVWHSWRWKHULJKWVROXWLRQLVWRTXLFNO\GHWHUPLQHWKDWWKHUHFDQEHQRFROOLVLRQDQG DYRLGGRLQJDQ\PRUHWHVWV6RILUVWZHILJXUHRXWLI$LVJRLQJIDUHQRXJKWKDWLWFRXOG FRQFHLYDEO\KLW%7KDWPHDQVWKDWWKHPRYHPHQWYHFWRUPXVWEHDWOHDVWDVORQJDVWKH VKRUWHVWGLVWDQFHEHWZHHQWKHFLUFOHVZKLFKZRXOGEHDVWUDLJKWOLQHSDVVLQJWKURXJKWKHLU FHQWHUV6RWKHPRYHPHQWYHFWRUPXVWEHDWOHDVWWKHGLVWDQFHEHWZHHQWKHFHQWHUVRIWKH FLUFOHVPLQXVWKHUDGLXVRIHDFK,ILWLVQRWWKHQWKHUHLVQRZD\WKDWWKHFLUFOHVZLOOFROOLGH 1RWHWKDWWKLVWHVWGRHVQRWWDNHGLUHFWLRQLQWRDFFRXQW7KXVLWGRHVQRWWHOOXVWKDW$DQG% ZLOOFROOLGH LWWHOOVXVWKDWWKH\ZRQ W6HH)LJXUHIRUDQLOOXVWUDWLRQ
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
)LJXUH 7KHVKRUWHVWOHQJWK WKHPRYHPHQWYHFWRUFDQEH IRU$DQG%WRFROOLGH
2XUQH[WHDUO\HVFDSHWHVWLVWRGHWHUPLQHLI$LVDFWXDOO\PRYLQJWRZDUGV%,ILW VQRWWKHQ REYLRXVO\\RXGRQ WKDYHWRZRUU\DERXWWKHPFROOLGLQJ7RGRWKLVZHWDNHDGYDQWDJHRIRXU IULHQGWKH'RW3URGXFW)LUVWILQG&WKHYHFWRUIURPWKHFHQWHURI$WRWKHFHQWHURI% 5HPHPEHUWKDWDSRLQWPLQXVDSRLQWLVDYHFWRUVR&
%$1RZJHWWKHGRWSURGXFWRI&
DQGWKHPRYHPHQWYHFWRU9 LIWKHUHVXOWLVOHVVWKDQRUHTXDOWRWKHQ$LVQRWPRYLQJ WRZDUGV%DQGQRPRUHWHVWLQJQHHGVWREHGRQH 2QHPRUHHVFDSHWHVW ,IWKHFORVHVWWKDW$HYHUJHWVWR%LVPRUHWKDQWKHVXPRIWKHLUUDGLL WKHQWKH\GRQRWKLW'RWSURGXFWWRWKHUHVFXHDJDLQ,IWKHWDLVWKHDQJOHEHWZHHQDQ\WZR YHFWRUV3DQG4WKHQWKHGRWSURGXFWEHWZHHQ3DQG4LVHTXLYDOHQWWR
,QRWKHUZRUGVWKHGRWSURGXFWRIWZRYHFWRUV3DQG4LVHTXDOWRWKHFRVLQHRIWKHDQJOH EHWZHHQWKHPWLPHVWKHOHQJWKRI3DQGWKHOHQJWKRI4 $OVRUHFDOOWKDWWKHFRVLQHRIDQDQJOHLVHTXDOWRWKHVLGHRIDULJKWWULDQJOHDGMDFHQWWRWKDW DQJOHGLYLGHGE\WKHK\SRWHQXVHRIWKDWVDPHWULDQJOH7KHUHIRUHWKHGRWSURGXFWRIDYHFWRU
4LVHTXDOWRWKHOHQJWKRI3WLPHVWKHFRVLQH EHWZHHQWKHWZRYHFWRUV:KLFKLQWXUQLVHTXDOWRWKHOHQJWKRIWKHYHFWRU3LQWKHGLUHFWLRQ RIWKHQRUPDOL]HGYHFWRU47KLVLVVKRZQLQ)LJXUH 3DQGDQRUPDOL]HG LH KDVDOHQJWKRI YHFWRU
)LJXUH
9DQG $WRWKHFHQWHURIFLUFOH%FDOOHGYHFWRU&:HZDQWWRILQG WKHSRLQWRQ9WKDWLVFORVHVWWRWKHFHQWHURI%,QWXLWLYHO\LIZHZHUHWRGUDZDOLQHIURPWKLV SRLQWWRWKHFHQWHURI%LWZRXOGEHDWULJKWDQJOHVWR97KHUHIRUHZHFDQXVHWKHGRW SURGXFWDVGHVFULEHGDERYHWRILQGWKHGLVWDQFHIURPWKHFHQWHURI$WRWKDWSRLQW&RPSXWH WKHQRUPDOL]HG9 FDOOLW1 DQGWKHQWDNHWKHGRWSURGXFWRI1DQG&7KHUHVXOWZLOOEHWKH IORDWLQJSRLQWQXPEHU'WKHGLVWDQFHEHWZHHQWKHFHQWHURI$DQGWKHFORVHVWSRLQWRQ9WR% :LWKWKLVLQPLQGOHWVJREDFNWRWKHSUREOHPDWKDQG:HKDYHRXUPRYHPHQWYHFWRU RXUYHFWRUIURPWKHFHQWHURIFLUFOH
6HH)LJXUHIRUDYLVXDOUHIHUHQFH
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
)LJXUH &DOFXODWLQJWKHFORVHVWSRLQWRQ
7KHOHQJWKRI
9WR%
&DQG'DUHWKHOHQJWKVRIWZRVLGHVRIDULJKWWULDQJOH7KXVZHFDQXVHWKH
3\WKDJRUHDQ7KHRUHP DAEA
FA WRILQGWKHOHQJWKRIWKHWKLUGVLGHUHSUHVHQWHGLQ
&DQGVXEWUDFWWKHVTXDUHRI'IURPLWDQGFDOOWKH
JUHHQLQILJXUH6TXDUHWKHOHQJWKRI
)
UHVXOW
)
%WRWKHFORVHVW
1RZWREHDFFXUDWHWKHVTXDUHURRWRI LVWKHOHQJWKIURPWKHFHQWHURI
%RQ9+RZHYHUSHUIRUPLQJVTXDUHURRWVWDNHDORWRISURFHVVRUWLPH6RZHZLOO ) DVVWDWHGEHIRUHGR$DQG%WRXFKZKHQ$LVDWWKHFORVHVWSRLQWWR%DORQJ9",QRWKHU ZRUGVLVVTUW ) $UDGLXV%UDGLXV"%XWUDWKHUWKDQWDNHWKHVTXDUHURRWRI)FKHFN) $UDGLXV%UDGLXV A,IWKLVFRPSDULVRQLVIDOVHWKHQWKHUHLVQRFROOLVLRQDQG\RXFDQ SRLQWWR
SHUIRUPRXUHDUO\HVFDSHWHVWZLWKRXWWDNLQJWKHVTXDUHURRWRI :KDWZHQHHGWRNQRZLV
HVFDSHWKHURXWLQH
$WWKLVSRLQWZH YHH[KDXVWHGRXUHDUO\HVFDSHWHVWVDQGWKHUHLVVWLOODFKDQFHWKDWWKHWZR FLUFOHVZLOOFROOLGH
$ %LVULJKWXSXQWLOLWLVMXVWWRXFKLQJWKHHGJHRIFLUFOH%$WWKDW
)LJXUHJLYHVDYLVXDOH[SODQDWLRQRIWKHVWHSVDERXWWREHGHVFULEHG7KHGLVWDQFHFLUFOH FDQPRYHEHIRUHFROOLGLQJZLWK
SRLQWWKHGLVWDQFHEHWZHHQWKHFHQWHUVRIWKHFLUFOHVLVHTXDOWRWKHVXPRIWKHUDGLL6LQFHZH
9WRWKHFHQWHURI%DNDVTUW ) ZHKDYHWKH OHQJWKVRIWZRVLGHVRIDULJKWWULDQJOH7KHWKLUGVLGHLVHTXDOWR'GLVWDQFH$FDQWUDYHO EHIRUHLWKLWV%6RDJDLQZHFDQXVHWKH3\WKDJRUHDQWKHRUHPDQGILQGWKHOHQJWK7 $UDGLXV%UDGLXV A)7KHGLVWDQFH$KDVWRPRYHDORQJ9WRFRPHLQWRFRQWDFWZLWK% LV'VTUW 7 DOUHDG\NQRZWKHVKRUWHVWGLVWDQFHIURP
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
)LJXUH )LQGLQJWKHIDUWKHVWWKDW$FDQJR
$DQG%
2QHILQDOFKHFNLVQHHGHG5HPHPEHUZKHQZHWHVWHGWKHVKRUWHVWGLVWDQFHEHWZHHQ
EXWLWGLGQRWWDNHLQWRDFFRXQWGLUHFWLRQ"+HUH VZKHUHWKDWFDQFRPHEDFNDQGELWHXV &RQVLGHUWKHVLWXDWLRQLOOXVWUDWHGLQILJXUH %RWKDUURZVDUHWKHVDPHOHQJWKEXWLQVOLJKWO\ GLIIHUHQWGLUHFWLRQV7KLVVKRZVWKDW\HVWKHPRYHPHQWYHFWRULVORQJHQRXJKWREULQJWKHWZR FLUFOHVFORVHHQRXJKWRWRXFKEXWWKHGLUHFWLRQLVVXFKWKDWWKH\ZRQ W6RDWWKLVSRLQWLQWKH
9WKHQWKHUH
DOJRULWKPZHQHHGWRGRDUHDOLW\FKHFN LI'LVWDQFHLVJUHDWHUWKDQWKHOHQJWKRI LVQRFROOLVLRQ
)LJXUH
9DQGWKHQPXOWLSO\LWE\'VTUW 7 1RZ&LUFOH$ %7KH-DYDFRGHLPSOHPHQWLQJWKLVDOJRULWKPLVOLVWHG
,IWKHILQDOWHVWLVSDVVHGZHFDQQRUPDOL]H ZLOOPRYHXQWLOLWLVMXVWWRXFKLQJFLUFOH EHORZ
// Early Escape test: if the length of the movevec is less // than distance between the centers of these circles minus // their radii, there's no way they can hit. double dist = B.center.distance(A.center); double sumRadii = (B.radius + A.radius); dist -= sumRadii; if(movevec.Magnitude() < dist){ return false; } // Normalize the movevec Vector N = movevec.copy(); N.normalize(); // Find C, the vector from the center of the moving // circle A to the center of B Vector C = B.center.minus(A.center); // D = N . C = ||C|| * cos(angle between N and C) double D = N.dot(C);
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
// Another early escape: Make sure that A is moving // towards B! If the dot product between the movevec and // B.center - A.center is less that or equal to 0, // A isn't isn't moving towards B if(D <= 0){ return false; } // Find the length of the vector C double lengthC = C.Magnitude(); double F = (lengthC * lengthC) - (D * D); // Escape test: if the closest that A will get to B // is more than the sum of their radii, there's no // way they are going collide double sumRadiiSquared = sumRadii * sumRadii; if(F >= sumRadiiSquared){ return false; } // We now have F and sumRadii, two sides of a right triangle. // Use these to find the third side, sqrt(T) double T = sumRadiiSquared - F; // If there is no such right triangle with sides length of // sumRadii and sqrt(f), T will probably be less than 0. // Better to check now than perform a square root of a // negative number. if(T < 0){ return false; } // Therefore the distance the circle has to travel along // movevec is D - sqrt(T) double distance = D - sqrt(T); // Get the magnitude of the movement vector double mag = movevec.Magnitude(); // Finally, make sure that the distance A has to move // to touch B is not greater than the magnitude of the // movement vector. if(mag < distance){ return false; } // Set the length of the movevec so that the circles will just // touch movevec.normalize(); movevec.times(distance); return true; %DQN6KRW &ROOLVLRQEHWZHHQWZRPRYLQJFLUFOHV
7KLVSUREOHPVHHPVHYHQPRUHFRPSOLFDWHGWKDQWKHSUHYLRXVRQH*LYHQWZRPRYLQJFLUFOHV GHWHUPLQHZKHWKHURUQRWWKH\FROOLGH/RRNLQJDWWKHSUREOHPLQILJXUHZHFDQVHHWKDW MXVWEHFDXVHWKHLUSDWKVFURVVGRHVQRWPHDQWKDWWKHFLUFOHVZLOOFRPHLQWRFRQWDFW2QHPD\ KDYHPRYHGRXWRIWKHZD\LQWLPH,WDOVRVKRZVWKDWMXVWEHFDXVHWKHLUSDWKVGRQRWFURVV GRHVQRWPHDQWKDWWKH\GRQ WFROOLGH
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
)LJXUH WKH'\QDPLF'\QDPLFFROOLVLRQSUREOHP
7KDQNIXOO\WKHVROXWLRQWRDYHU\KDUGSUREOHPFRXOGQRWEHVLPSOHU:KDWZHDUHUHDOO\ LQWHUHVWHGLQLVQRWWKHLUPRYHPHQWYHFWRUVEXWWKHLUPRYHPHQWUHODWLYHWRHDFKRWKHU,IZH WUDQVODWHFLUFOH
$ VPRYHPHQWVXFKWKDW%FDQEHFRQVLGHUHGVWDWLRQDU\ZHFDQXVHWKH
'\QDPLF6WDWLFVROXWLRQGHVFULEHGDERYH
)LUVWRIDOOVXEWUDFWWKHPRYHPHQWYHFWRURIRQHFLUFOHIURPDQRWKHU RU\RXFDQWKLQNRILWDV DGGLQJWKHUHYHUVHRIRQHYHFWRUWRDQRWKHU 7KHQSHUIRUPWKHG\QDPLFVWDWLFFROOLVLRQ DOJRULWKPRQWKHFLUFOHVDQGWKHQHZYHFWRU,IWKH\FROOLGHGLYLGHWKHOHQJWKRIWKHVKRUWHQHG YHFWRUE\WKHOHQJWKRIWKHRQH\RXRULJLQDOO\SDVVHGLQWRWKHIXQFWLRQ7KHUHVXOWVKRXOGEHD IORDWLQJSRLQWQXPEHUEHWZHHQDQG7KLVUHSUHVHQWVZKHQRYHUWKHFRXUVHRIWKHLU PRYHPHQWWKHFLUFOHVFROOLGHG0XOWLSO\WKHRULJLQDOPRYHPHQWYHFWRUVE\WKLVQXPEHUDQGWKH UHVXOWLVVKRUWHQHGPRYHPHQWYHFWRUVWKDWWDNHWKHFLUFOHVXSWRWKHSRLQWZKHUHWKH\WRXFK IRUWKHILUVWWLPH -XPSLQJWKH&XHEDOO $SSO\LQJWKHVHDOJRULWKPVWR'
'HWHFWLQJSUR[LPLW\EHWZHHQWZRVWDWLRQDU\VSKHUHV
7KHDSSOLFDWLRQRIWKLVDOJRULWKPWR'HQYLURQPHQWVFRXOGQ WEHHDVLHU&LUFOHVLQ'DQG VSKHUHVLQ'DUHERWKGHILQHGWKHVDPHZD\PDWKHPDWLFDOO\ *LYHQDFHQWHUSRLQWWKH ERXQGDULHVRIERWKFLUFOHVDQGVSKHUHVDUHGHILQHGDVDOOSRLQWVWKDWDUHDJLYHQGLVWDQFH WKH UDGLXV IURPWKHFHQWHUSRLQW6RVSKHUHVFDQEHPDWKHPDWLFDOO\VSHFLILHGLQWKHVDPHZD\DV FLUFOHVZLWKDFHQWHUSRLQWDQGDUDGLXV7KHUHLVRQHFDYHDWIRUWKH'UHSUHVHQWDWLRQ7KH FHQWHUSRLQWLQ'XVHVDWKLUGFRRUGLQDWH]6RWKHGLVWDQFHEHWZHHQWKHFHQWHUVRIWKHWZR VSKHUHVFDQEHIRXQGE\
,IWKDWGLVWDQFHLVOHVVWKDQWKHVXPRIWKHUDGLLRIWKHWZRVSKHUHVWKHQWKH\DUHLQFRQWDFW ZLWKHDFKRWKHU &ROOLVLRQRIDPRYLQJVSKHUHZLWKDVWDWLRQDU\VSKHUH
7KH'\QDPLF6WDWLFFROOLVLRQDOJRULWKPZRUNVLQ'EHFDXVHWKH'VFHQDULRFDQEHUHGXFHGWR ',I\RXORRNDWRXUVROXWLRQIRUWKLVSUREOHPLQ'\RX OOQRWLFHWKDWLWLVEDVHGDURXQGWZR YHFWRUV
9DQG& DQGDFRPPRQSRLQW WKHFHQWHURI$ 7KHVHWZRYHFWRUVGHILQHWKH
RULHQWDWLRQRIWKHSODQHLQ'DQGWKHSRLQWSURYLGHVDUHIHUHQFHWRZKHUHLQVSDFHWKDWSODQH OLHV)LJXUHVDQGVKRZWZRVSKHUHVWKHUHGRQHLQPRWLRQDQGWKHEOXHRQHDWUHVW 7KHVHILJXUHVDOVRVKRZWKHPRYHPHQWYHFWRURIWKHUHGRQHDQGWKHYHFWRUEHWZHHQWKH FHQWHUVRIWKHVSKHUHV1RWLFHWKH'SODQHWKDWLVSDVVLQJWKURXJKWKHREMHFWVLQWKHVFHQHLQ ERWKILJXUHV7KLVSODQHFXWVULJKWGRZQWKHPLGGOHRIWKHWZRVSKHUHVDQGDORQJWKHWZR YHFWRUVFOHDUO\VKRZLQJWKDWWKHVHYHFWRUVDUHFRSODQDU$OVRQRWLFHWKDWWKHSODQHFXWVWKH VSKHUHVSHUIHFWO\LQKDOIVRWKDWWKHDUHDVRIFRQWDFWEHWZHHQWKHVSKHUHVDQGWKHSODQHDUH FLUFOHVZLWKWKHVDPHFHQWHUDQGUDGLXVDVWKHVSKHUHV$OORIWKHLQIRUPDWLRQQHHGHGWRXVH WKHG\QDPLFVWDWLFDOJRULWKPZHGHVFULEHGDERYHLVSURMHFWHGLQWRD'VSDFHRQWKHOLJKWEOXH SODQH
9DQG &OLHDORQJWKHVDPHOLQHWKHQWKHUHDUHDQLQILQLWHQXPEHURISODQHVLQZKLFKWKHSUREOHPFDQ 7KHUHLVDVSHFLDOFDVHWREHFRQVLGHUHGDOWKRXJKLWVUHVROXWLRQLVWULYLDO,IWKHYHFWRUV
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
9DQG&DUHFROLQHDUWKDWPHDQV $LVPRYLQJGLUHFWO\WRZDUGVVSKHUH%DQGWKHTXHVWLRQRIZKHWKHUWKH\FROOLGH UHGXFHVWRRQO\RXUILUVWHDUO\HVFDSHWHVW1DPHO\GRHV$PRYHIDUHQRXJKWRKLW%"RULQ RWKHUZRUGV,V9JUHDWHUWKDQ &VXP5DGLL " EHVROYHG7KLVFDVHVKRXOGEHFKHFNHGIRU2IFRXUVHLI WKDWVSKHUH
7KHUHDUHQRFKDQJHVQHHGHGWRWKHFRGHDERYHLQRUGHUIRULWWRZRUNLQWKH'FDVH7KH FKDQJHVWKDWQHHGWREHGRQHDUHLQWKHFODVVHVWKDWDUHDVVXPHGE\WKHDERYHFRGH)RU H[DPSOHLQVWHDGRIWKH9HFWRUFODVVKDYLQJRQO\[DQG\PHPEHUYDULDEOHVLWVKRXOGEH FKDQJHGWRLQFOXGHDWKLUGPHPEHUYDULDEOH]
)LJXUH '\QDPLF6WDWLF&ROOLVLRQLQ '
)LJXUH 7KH'\QDPLF6WDWLF &ROOLVLRQSURMHFWHGLQ' &ROOLVLRQEHWZHHQWZRPRYLQJVSKHUHV
$JDLQE\WUDQVODWLRQRIWKHSUREOHPWRRQHVSKHUH VIUDPHRIUHIHUHQFHWKLVSUREOHPLV UHGXFHGWRWKH'\QDPLF6WDWLF'SUREOHPZKLFKLQWXUQVFDOHVGRZQWRWKH'FDVHDV GHVFULEHGDERYH)LJXUHVKRZVWZRVSKHUHVHDFKZLWKLW VRZQPRYHPHQWYHFWRUVKRZQLQ
% VPRYHPHQWYHFWRUDQGWKH\HOORZPRYHPHQW YHFWRUIURP$ WKHUHGEDOO LVWKHPRYHPHQWRI$DVREVHUYHGIURP% VSRLQWRIUHIHUHQFH 7KH'SODQHFRQWDLQLQJWKH\HOORZYHFWRUDOVRFRQWDLQVWKHFHQWHURIVSKHUH%DQGVRLWFDQ JUHHQ7KHRUDQJHYHFWRULVRSSRVLWHRI
EHXVHGWRVROYHWKHSUREOHP
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
)LJXUH &ROOLVLRQRIWZRPRYLQJVSKHUHVLQ'DQG KRZLWFDQEHUHGXFHGWRRQHPRYLQJFLUFOHLQ'
6LQNLQJ
1RZWKDW\RXKDYHGHWHUPLQHGWKDW\RXUFLUFOHVFROOLGH\RXZDQWWRKDYHWKHPERXQFHRIIRI HDFKRWKHULQDUHDOLVWLFPDQQHUWDNLQJLQWRDFFRXQWWKHLUUHODWLYHPDVVDQGVSHHG7RVROYH WKLVZHDUHJRLQJWRUHO\RQVRPHVLPSOHODZVRISK\VLFVVSHFLILFDOO\WKHFRQVHUYDWLRQRI PRPHQWXPDQGWKHFRQVHUYDWLRQRIHQHUJ\ /RRNDWILJXUHWRJHWDQLGHDRIWKHSUREOHPDQGWKHYDULDEOHVWKDWZHDUHJRLQJWRXVH 7KHUHGFLUFOHLVFLUFOHWKHEOXHRQHFLUFOH7KH\HDFKKDYHDPRYHPHQWYHFWRU PRYHYHFDQGPRYHYHFDQGDPDVVPDQGP
)LJXUH %RXQFH
&RQVHUYDWLRQRI0RPHQWXPVWDWHVWKDWWKHWRWDOPRPHQWXPRIWKHV\VWHPEHIRUHWKHFROOLVLRQ LVHTXDOWRWKHWRWDOPRPHQWXPLQWKHV\VWHPDIWHUWKHFROOLVLRQ,IZHUHSUHVHQWWKH PRPHQWXPRIDFLUFOHWREH3
0 9ZKHUH0LVWKHFLUFOHVPDVVDQG9LVLWVPRYHPHQW
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
YHFWRUWKHQZHFDQGHULYHWKHHTXDWLRQ
ZKHUHY DQGY DUHWKHPRYHPHQWYHFWRUVRIFLUFOHDQGUHVSHFWLYHO\DIWHUWKHFROOLVLRQ 6LQFHWKHVHFRQGFLUFOHJDLQVDQ\PRPHQWXPORVWE\WKHILUVWZHFDQUHSUHVHQWWKHGLIIHUHQFH
GHOWD3
EHWZHHQWKHPRPHQWXPVRIWKHEDOOVEHIRUHDQGDIWHUE\WKHVDPHYHFWRU
1RZKHUHLVZKHUHWKHGLIIHUHQFHEHWZHHQUHDOLW\DQGVLPXODWLRQFRPHVLQWRSOD\,IWKHVHWZR VSKHUHVZHUHWKHUXEEHUEDOOVZHDOOXVHGLQJ\PFODVVLQKLJKVFKRROZKHQWKH\KLWWKH\ ZRXOGGHIRUP7KLVGHIRUPDWLRQZRXOGLQFUHDVHWKHDUHDZKHUHWKHEDOOVDUHWRXFKLQJDQG VRPHRIWKHHQHUJ\ZRXOGEHORVWLQWKDWGHIRUPDWLRQ2WKHUDPRXQWVRILWZRXOGEHORVWLQ VSLQ%XWLQWKLVVLPXODWLRQZHDUHDVVXPLQJWKHEDOOVWREHULJLGIULFWLRQOHVVSHUIHFWVSKHUHV $FRPPRQUHDOZRUOGH[DPSOHRIWKLVW\SHPLJKWEHWKHVWHHOEDOOVKDQJLQJIURPDIUDPHWKDW FROOLGHZLWKHDFKRWKHUWRGHPRQVWUDWHDFWLRQUHDFWLRQ EHFDXVHWKH\DUHVRULJLGYHU\OLWWOHRI WKHLUPRPHQWXPLVORVWZKHQWKH\FROOLGHDQGVRZKHQ\RXVHWRQHEDOOVZLQJLQJLWWDNHV VRPHWLPHIRUWKHPDOOWRVWRS 6RLQRXUVLPXODWLRQRISHUIHFWULJLGVSKHUHVWKHRQO\WUDQVIHUHQFHRIPRPHQWXPFDQRFFXU
GHOWD3
DORQJWKHVLQJOHSRLQWRIFRQWDFWDVLOOXVWUDWHGLQILJXUH7KHUHIRUHZHFDQEUHDN
LQWRDXQLWYHFWRU1WKDWSRLQWVGRZQWKHOLQHRIFRQWDFWDQGDVFDODU3UHSUHVHQWLQJWKH PDJQLWXGHRIGHOWD36RLIZHDSSO\WKLVWRWKHHTXDWLRQVDERYHZHFDQVROYHIRUWKHQHZ PRYHPHQWYHFWRUVRIWKHFLUFOHVDQGJHW
6RLIZHFDQVROYHIRU3ZHFDQFDOFXODWHWKHQHZPRYHPHQWYHFWRUV 1RZORRNEDFNDWILJXUHDQGQRWLFHWKDWYDQGYFDQEHUHSUHVHQWHGE\WKHVXPRIWZR YHFWRUV RQHWKDWLVSDUDOOHOWRWKHOLQHDORQJZKLFKPRPHQWXPLVH[FKDQJHGDQGRQHWKDWLV SHUSHQGLFXODUWRLW8VLQJWKLVLQIRUPDWLRQZHFDQUHSUHVHQWYY YDQGY E\
:KHUHDDEDQGEDUHVFDODUV1LVWKHVDPH1DVPHQWLRQHGEHIRUHDQG4LVWKH QRUPDOL]HGYHFWRUSHUSHQGLFXODUWRWKHOLQHDORQJZKLFKPRPHQWXPLVH[FKDQJHGDQGRQWKH VDPHSODQHDV1DQGWKHPRYHPHQWYHFWRU 6XEVWLWXWLQJYLQHTXDWLRQIRUWKHYDOXHRIYLQHTXDWLRQDQGYLQHTXDWLRQIRUWKH YDOXHRIYLQHTXDWLRQZHJHW
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
$QGVLQFHY
D
1E
4DQGY
D
1E
4ZHFDQVHHWKDW
1RZZHFDQXVHWKH&RQVHUYDWLRQRI(QHUJ\WRVROYHIRU37KHHTXDWLRQIRUNLQHWLFHQHUJ\LV
6LQFHHQHUJ\LVFRQVHUYHGWKHWRWDOHQHUJ\EHIRUHWKHFROOLVLRQPXVWHTXDOWKHWRWDOHQHUJ\ DIWHUWKHFROOLVLRQ
8VLQJWKHPRYHPHQWYHFWRUDVWKHK\SRWHQXVHRIDULJKWWULDQJOHZHFDQVXEVWLWXWH
6XEVWLWXWLQJHTXDWLRQIRUD E D DQGE ZHJHW
1RWHWKDWWKHEDQGEWHUPVLQHTXDWLRQGURSRXWRIWKHHTXDWLRQ:LWKDQHTXDWLRQLQ WHUPVRIPPDDDQG3ZHKDYHDQHTXDWLRQZLWKYDULDEOHVWKDWDUHHLWKHUJLYHQRU FDQEHFDOFXODWHGIURPZKDWZDVJLYHQH[FHSWIRU36RLIZHVROYHIRU3ZHZLOOEHDEOHWR SOXJLQWKHNQRZQYDULDEOHVGHULYH3DQGWKHQXVH3WRFDOFXODWHWKHQHZPRYHPHQWYHFWRUV (TXDWLRQVKRZVHTXDWLRQDIWHUVROYLQJIRU3
6RSOXJJLQJWKLVLQWR(TXDWLRQV
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
1RWLFHWKDWIRUERWKY DQGY WKHWHUPLQWKH EUDFNHWVLVWKHVDPHVR\RXRQO\QHHGWR FDOFXODWHWKDWRQFH:LWKWKDWGRQH\RXFDQFDOFXODWHY DQGY 1RZWKDWZH YHGRQHWKH PDWKIRUWKLVWKHFRGHWRLPSOHPHQWWKHUHVXOWVLVYHU\VKRUWDQGTXLFN7KHYDULDEOH RSWLPL]HG3LQWKHFRGHUHIHUVWRWKHWHUPLQEUDFNHWVDERYH
// First, find the normalized vector n from the center of // circle1 to the center of circle2 Vector n = circle1.center - circle2.center; n.normalize(); // Find the length of the component of each of the movement // vectors along n. // a1 = v1 . n // a2 = v2 . n float a1 = v1.dot(n); float a2 = v2.dot(n); // Using the optimized version, // optimizedP = 2(a1 - a2) // ----------// m1 + m2 float optimizedP = (2.0 * (a1 - a2)) / (circle1.mass + circle2.mass); // Calculate v1', the new movement vector of circle1 // v1' = v1 - optimizedP * m2 * n Vector v1' = v1 - optimizedP * circle2.mass * n; // Calculate v1', the new movement vector of circle1 // v2' = v2 + optimizedP * m1 * n Vector v2' = v2 + optimizedP * circle1.mass * n; circle1.setMovementVector(v1'); circle2.setMovementVector(v2'); %DOO&RUQHU3RFNHW
7KHVHWHFKQLTXHVZLOODOORZ\RXXVHVSKHUHVZLWKDKLJKHUGHJUHHRIDFFXUDF\WKDQLVSUREDEO\ QHFHVVDU\LI\RXUVSKHUHVDUHDOOERXQGLQJVSKHUHV3UHFLVHFROOLVLRQVEHWZHHQVSKHUHVEHFRPH LPSRUWDQWZKHQVLPXODWLQJWKLQJVOLNHVSRROEDOOVRUPDUEOHVRUSRWHQWLDOO\URFNVLQD ODQGVOLGH%XWIRUVSKHUHVERXQGLQJFKDUDFWHUVIRUH[DPSOH\RXPLJKWQRWFDUHZKDWDQJOH WZRFROOLGLQJFKDUDFWHUVZRXOGERXQFHDZD\DW+RZHYHUSDUWVRIWKHVHPHWKRGVDUHIDVW HQRXJKWREHXVHIXOLIRQO\WRGHWHUPLQHWKDWDFROOLVLRQZDVDYRLGHG%XWZKRNQRZV XVLQJD SXPSHGXSVSDFHPDULQHDVDFXHEDOOMXVWPLJKWEHKXPRURXVHQRXJKWRGR« 6SHFLDOWKDQNVWR'DYH%DXPIRUKLVKHOSZLWKFROOLVLRQUHVSRQVH
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
&RS\ULJKW&030HGLD,QF$OOULJKWVUHVHUYHG
,VQ WLWZRQGHUIXOWRPRYHWKURXJKWKHYLUWXDOZRUOGLQD'JDPH"7KHZD\\RXFDQZDONLQWR ZDOOVDQGVOLGHDORQJWKHPDV\RXIUHHO\WXUQZLWKRXJJHWWLQJ\RXUUDLOJXQVWXFNEHWZHHQ \RXDQGWKHZDOO"7KHZD\\RXDQG\RXURSSRQHQWFDQUXQDWHDFKRWKHUVZRUGVGUDZQ DFWXDOO\VWRSZKHQ\RXUHDFKHDFKRWKHUDQGFDQWKHQEDFNDZD\ZLWKRXWZRUU\LQJDERXW \RXUVKLHOGJHWWLQJFDXJKWLQKLVFKDLQPDLO"7KHZD\\RXFDQFLUFOHVWUDIH\RXURSSRQHQWRYHU XQHYHQJURXQGZLWKRXWHYHUKDYLQJWRZRUU\DERXWWULSSLQJ",QWKHUHDOZRUOG\RXZRXOGKDYH WRZRUU\DERXWWKLVNLQGRIVWXII« $VGHYHORSHUVZHFDQ WDIIRUGWRGRFROOLVLRQGHWHFWLRQEHWZHHQHYHU\SRO\JRQRIDFKDUDFWHU DQGWKHLUHQYLURQPHQWRQHYHQWKHEHVWFXUUHQWKDUGZDUH LIZHGLGQRWRQO\ZRXOGRXU JDPHVEHSDLQIXOO\VORZEXWZH GDOVRUXQLQWRSUREOHPVOLNHWKRVHGHVFULEHGDERYH8VXDOO\D GHFHQWVSDWLDOSDUWLWLRQLQJV\VWHPDQGWKHXVHRIVSKHUHVWRERXQGFRPSOH[PRELOHREMHFWVOHW XVSHUIRUPFROOLVLRQGHWHFWLRQURXWLQHVWKDWDUHYHU\IDVWDQGRQO\LQYROYHWKHPLQLPXP QXPEHURISRO\JRQV1RWRQO\LVLWIDVWHUEXWLWKHOSVDYRLGHQWDQJOLQJERWKSOD\HUFKDUDFWHUV DQGQRQSOD\HUFKDUDFWHUVLQWKHHQYLURQPHQWDQGHDFKRWKHU 7LP6FKURHGHUV VDUWLFOH&ROOLVLRQ'HWHFWLRQ8VLQJ5D\&DVWLQJLQWKH$XJXVWLVVXHRI *DPH'HYHORSHUPDJD]LQHIRFXVHGRQGHWHFWLQJFROOLVLRQVEHWZHHQVSKHUHVDQGSRO\JRQV7KLV DUWLFOHFRPSOLPHQWVWKHLQIRUPDWLRQSUHVHQWHGWKHUHE\H[SODLQLQJKRZWRGHWHFWFROOLVLRQV EHWZHHQWZRVSKHUHVDQGGHWHUPLQHZKDWWKH\ OOGRDIWHUWKH\FROOLGH7KLVLVXVHIXOQRWRQO\ IRUJDPHVOLNHSRROZKHUHDFFXUDWHFROOLVLRQRIVSKHUHVLVNH\EXWDOVRLQJDPHVZKHUH FKDUDFWHUVDQGRWKHUPRELOHREMHFWVDUHERXQGHGE\VSKHUHVWKHVHFDQEHXVHGWRTXLFNO\ GHWHUPLQHLIWKH\KDYHEXPSHGLQWRHDFKRWKHU 7RPDNHLWHDVLHUWRH[SODLQDOOWKHH[DPSOHVZLOOEHILUVWLQ'$ODWHUVHFWLRQRIWKLVDUWLFOH ZLOOH[SODLQKRZWRDSSO\WKHVDPHDOJRULWKPVWR')RUWKHSXUSRVHVRIWKLVDUWLFOHDFLUFOH ZLOOEHUHSUHVHQWHGE\WKHSRLQWDWLWVFHQWHUDQGLWVUDGLXV 5DFN HP 3UR[LPLW\'HWHFWLRQEHWZHHQWZRVWDWLRQDU\FLUFOHV
$DQG%FXUUHQWO\WRXFKLQJ"7KHDQVZHUDV, PVXUH\RXDOUHDG\
$UHWZRVWDWLRQDU\FLUFOHV
NQRZLVYHU\VLPSOH7ZRFLUFOHVDUHLQFRQWDFWZLWKHDFKRWKHULIDQGRQO\LIWKHGLVWDQFH EHWZHHQWKHLUFHQWHUVLVOHVVWKDQRUHTXDOWRWKHVXPRIWKHLUUDGLL6RILQGWKHGLVWDQFH EHWZHHQWKHFHQWHUVRIWKHWZRFLUFOHVXVLQJWKHHTXDWLRQ
7KHQDGGWKHUDGLLRIWKHWZRFLUFOHVWRJHWKHU,IWKHVXPRIWKHUDGLLLVJUHDWHUWKDQRUHTXDOWR
'LVWWKHQWKH
FLUFOHVDUHWRXFKLQJ6LQFHPXOWLSOLFDWLRQVDUHOHVVFRPSXWDWLRQDOO\H[SHQVLYHWKDQVTXDUHURRWV\RXVKRXOG
VSHHGXSWKLVFRGHE\QRWSHUIRUPLQJWKHVTXDUHURRWZKHQFDOFXODWLQJWKHGLVWDQFHDQGLQVWHDGVTXDUHWKH VXPRIWKHUDGLL7KHFRGHEHORZVKRZVDVDPSOHLPSOHPHQWDWLRQXVLQJWKLVVKRUWFXW
double deltaXSquared = A.x - B.x; // calc. delta X deltaXSquared *= deltaXSquared; // square delta X
double deltaYSquared = A.y - B.y; // calc. delta Y deltaYSquared *= deltaYSquared; // square delta Y // Calculate the sum of the radii, then square it
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
double sumRadiiSquared = A.radius + B.radius; sumRadiiSquared *= sumRadiiSquared; if(deltaXSquared + deltaYSquared <= sumRadiiSquared){ // A and B are touching }
)RUWKLVSUREOHP\RXDUHJLYHQDFLUFOH$WKDWLVPRYLQJWKURXJKDYLUWXDOZRUOG2YHUDILQLWH SHULRGRIWLPHZKLFKZH OOFDOOW$PRYHVDFHUWDLQGLVWDQFHLQDFHUWDLQGLUHFWLRQ:H OO UHSUHVHQWWKLVPRYHPHQWE\DYHFWRU9$OVRLQWKLVYLUWXDOZRUOGLVDFLUFOH%WKDWLVQRW PRYLQJ7KHSUREOHPLVWRILJXUHRXWLI$FRPHVLQWRFRQWDFWZLWK%ZKLOHLWLVPRYLQJDORQJ9 DQGLILWGRHVE\ZKDWDPRXQWGRZHKDYHWRVKRUWHQ9VRWKDW$FRPHVWRUHVWMXVWDWWKH SRLQWRIFRQWDFWZLWK%"$QLOOXVWUDWLRQRIWKHSUREOHPLVVKRZQLQILJXUH
)LJXUH ,OOXVWUDWLRQRIWKH'\QDPLF6WDWLF &ROOLVLRQ3UREOHP
/HYHUDJLQJ6WDWLRQDU\&ROOLVLRQ
7KHILUVWDQGPRVWREYLRXVVROXWLRQWRWKLVZRXOGEHWRXVHWKHVWDWLRQDU\FROOLVLRQPHWKRG GHVFULEHGDERYHRQWKHFKDQJLQJGHVWLQDWLRQORFDWLRQRIFLUFOH$,QRWKHUZRUGVPRYHFLUFOH$ WRWKHHQGRIWKHPRYHPHQWYHFWRUDQGWKHQWHVWLW VQHZSRVLWLRQIRUFROOLVLRQV,I$LVLQ FRQWDFWZLWKDQRWKHUFLUFOHLQLWVQHZORFDWLRQ\RXKDYHWZRFKRLFHV
$EHWWHUDSSURDFKZRXOGEHWRXVHWKHPRYHPHQWYHFWRU9WRUHSUHVHQWWKHFLUFOHDVLWPRYHV WKURXJKWKHZRUOG1RZDOOWKHFROOLVLRQGHWHFWLRQLVVLPSOLILHGGRZQWRDYHFWRUWHVWHGDJDLQVW DVWDWLFFLUFOH7KLVDSSURDFKGRHVRQHWHVWWRVHHLI9WRXFKHV%,ILWGRHVQRWFROOLGHWKHQ\RX DUHGRQHWHVWLQJ
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
7KLVVROXWLRQKDVSUREOHPVDVZHOO&RQVLGHUWKHVLWXDWLRQVKRZQLQILJXUH7KHPRYHPHQW YHFWRU9IURPWKHFHQWHURI$GRHVQRWFRPHLQWRFRQWDFWZLWKDQ\WKLQJ+RZHYHULWRQO\ FKHFNVWKHSDWKWUDYHOHGE\WKHFHQWHURI$IRUFROOLVLRQDQGWKHERWWRPRUWRSFRXOGVWLOO FROOLGHZLWK%HYHQLIWKHPLGGOHGRHVQRW
)LJXUH
$SRVVLEOHVROXWLRQWRWKLVSUREOHPLVWRWHVWDJDLQVWWZRPRUHYHFWRUVFRPLQJIURPWKHHGJHV RIWKHPRYLQJFLUFOHSDUDOOHOWRWKHPRYHPHQWYHFWRU9:KLOHWKLVPD\IL[WKHSUREOHP GHVFULEHGDERYHZHFDQVHHLQILJXUHWKDWLIZHDGMXVWWKHPRYHPHQWYHFWRU9WREHWKH OHQJWKRIWKHFOLSSHGVHFRQGYHFWRUWKHFLUFOHVZLOOVWLOORYHUODS$OVRLIWKHPRYLQJFLUFOHLV ODUJHUWKDQWKHVWDWLFRQHWKHVWDWLFRQHPLJKWILWEHWZHHQWKHWRSDQGFHQWHUYHFWRUVRU EHWZHHQWKHFHQWHUDQGERWWRPYHFWRUVVRWKHFROOLVLRQZRXOGQRWEHGHWHFWHGDWDOO7KH PRYLQJFLUFOHZRXOGDSSHDUWRJRULJKWRYHUWKHVPDOOHUVWDWLFRQH2EYLRXVO\WKLVLVQRWWKH FRUUHFWDQVZHUIRUFROOLVLRQGHWHFWLRQ
)LJXUH $Q$OJRULWKP7KDW:RUNV
7KHILUVWVWHSWRWKHULJKWVROXWLRQLVWRTXLFNO\GHWHUPLQHWKDWWKHUHFDQEHQRFROOLVLRQDQG DYRLGGRLQJDQ\PRUHWHVWV6RILUVWZHILJXUHRXWLI$LVJRLQJIDUHQRXJKWKDWLWFRXOG FRQFHLYDEO\KLW%7KDWPHDQVWKDWWKHPRYHPHQWYHFWRUPXVWEHDWOHDVWDVORQJDVWKH VKRUWHVWGLVWDQFHEHWZHHQWKHFLUFOHVZKLFKZRXOGEHDVWUDLJKWOLQHSDVVLQJWKURXJKWKHLU FHQWHUV6RWKHPRYHPHQWYHFWRUPXVWEHDWOHDVWWKHGLVWDQFHEHWZHHQWKHFHQWHUVRIWKH FLUFOHVPLQXVWKHUDGLXVRIHDFK,ILWLVQRWWKHQWKHUHLVQRZD\WKDWWKHFLUFOHVZLOOFROOLGH 1RWHWKDWWKLVWHVWGRHVQRWWDNHGLUHFWLRQLQWRDFFRXQW7KXVLWGRHVQRWWHOOXVWKDW$DQG% ZLOOFROOLGH LWWHOOVXVWKDWWKH\ZRQ W6HH)LJXUHIRUDQLOOXVWUDWLRQ
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
)LJXUH 7KHVKRUWHVWOHQJWK WKHPRYHPHQWYHFWRUFDQEH IRU$DQG%WRFROOLGH
2XUQH[WHDUO\HVFDSHWHVWLVWRGHWHUPLQHLI$LVDFWXDOO\PRYLQJWRZDUGV%,ILW VQRWWKHQ REYLRXVO\\RXGRQ WKDYHWRZRUU\DERXWWKHPFROOLGLQJ7RGRWKLVZHWDNHDGYDQWDJHRIRXU IULHQGWKH'RW3URGXFW)LUVWILQG&WKHYHFWRUIURPWKHFHQWHURI$WRWKHFHQWHURI% 5HPHPEHUWKDWDSRLQWPLQXVDSRLQWLVDYHFWRUVR&
%$1RZJHWWKHGRWSURGXFWRI&
DQGWKHPRYHPHQWYHFWRU9 LIWKHUHVXOWLVOHVVWKDQRUHTXDOWRWKHQ$LVQRWPRYLQJ WRZDUGV%DQGQRPRUHWHVWLQJQHHGVWREHGRQH 2QHPRUHHVFDSHWHVW ,IWKHFORVHVWWKDW$HYHUJHWVWR%LVPRUHWKDQWKHVXPRIWKHLUUDGLL WKHQWKH\GRQRWKLW'RWSURGXFWWRWKHUHVFXHDJDLQ,IWKHWDLVWKHDQJOHEHWZHHQDQ\WZR YHFWRUV3DQG4WKHQWKHGRWSURGXFWEHWZHHQ3DQG4LVHTXLYDOHQWWR
,QRWKHUZRUGVWKHGRWSURGXFWRIWZRYHFWRUV3DQG4LVHTXDOWRWKHFRVLQHRIWKHDQJOH EHWZHHQWKHPWLPHVWKHOHQJWKRI3DQGWKHOHQJWKRI4 $OVRUHFDOOWKDWWKHFRVLQHRIDQDQJOHLVHTXDOWRWKHVLGHRIDULJKWWULDQJOHDGMDFHQWWRWKDW DQJOHGLYLGHGE\WKHK\SRWHQXVHRIWKDWVDPHWULDQJOH7KHUHIRUHWKHGRWSURGXFWRIDYHFWRU
4LVHTXDOWRWKHOHQJWKRI3WLPHVWKHFRVLQH EHWZHHQWKHWZRYHFWRUV:KLFKLQWXUQLVHTXDOWRWKHOHQJWKRIWKHYHFWRU3LQWKHGLUHFWLRQ RIWKHQRUPDOL]HGYHFWRU47KLVLVVKRZQLQ)LJXUH 3DQGDQRUPDOL]HG LH KDVDOHQJWKRI YHFWRU
)LJXUH
9DQG $WRWKHFHQWHURIFLUFOH%FDOOHGYHFWRU&:HZDQWWRILQG WKHSRLQWRQ9WKDWLVFORVHVWWRWKHFHQWHURI%,QWXLWLYHO\LIZHZHUHWRGUDZDOLQHIURPWKLV SRLQWWRWKHFHQWHURI%LWZRXOGEHDWULJKWDQJOHVWR97KHUHIRUHZHFDQXVHWKHGRW SURGXFWDVGHVFULEHGDERYHWRILQGWKHGLVWDQFHIURPWKHFHQWHURI$WRWKDWSRLQW&RPSXWH WKHQRUPDOL]HG9 FDOOLW1 DQGWKHQWDNHWKHGRWSURGXFWRI1DQG&7KHUHVXOWZLOOEHWKH IORDWLQJSRLQWQXPEHU'WKHGLVWDQFHEHWZHHQWKHFHQWHURI$DQGWKHFORVHVWSRLQWRQ9WR% :LWKWKLVLQPLQGOHWVJREDFNWRWKHSUREOHPDWKDQG:HKDYHRXUPRYHPHQWYHFWRU RXUYHFWRUIURPWKHFHQWHURIFLUFOH
6HH)LJXUHIRUDYLVXDOUHIHUHQFH
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
)LJXUH &DOFXODWLQJWKHFORVHVWSRLQWRQ
7KHOHQJWKRI
9WR%
&DQG'DUHWKHOHQJWKVRIWZRVLGHVRIDULJKWWULDQJOH7KXVZHFDQXVHWKH
3\WKDJRUHDQ7KHRUHP DAEA
FA WRILQGWKHOHQJWKRIWKHWKLUGVLGHUHSUHVHQWHGLQ
&DQGVXEWUDFWWKHVTXDUHRI'IURPLWDQGFDOOWKH
JUHHQLQILJXUH6TXDUHWKHOHQJWKRI
)
UHVXOW
)
%WRWKHFORVHVW
1RZWREHDFFXUDWHWKHVTXDUHURRWRI LVWKHOHQJWKIURPWKHFHQWHURI
%RQ9+RZHYHUSHUIRUPLQJVTXDUHURRWVWDNHDORWRISURFHVVRUWLPH6RZHZLOO ) DVVWDWHGEHIRUHGR$DQG%WRXFKZKHQ$LVDWWKHFORVHVWSRLQWWR%DORQJ9",QRWKHU ZRUGVLVVTUW ) $UDGLXV%UDGLXV"%XWUDWKHUWKDQWDNHWKHVTXDUHURRWRI)FKHFN) $UDGLXV%UDGLXV A,IWKLVFRPSDULVRQLVIDOVHWKHQWKHUHLVQRFROOLVLRQDQG\RXFDQ SRLQWWR
SHUIRUPRXUHDUO\HVFDSHWHVWZLWKRXWWDNLQJWKHVTXDUHURRWRI :KDWZHQHHGWRNQRZLV
HVFDSHWKHURXWLQH
$WWKLVSRLQWZH YHH[KDXVWHGRXUHDUO\HVFDSHWHVWVDQGWKHUHLVVWLOODFKDQFHWKDWWKHWZR FLUFOHVZLOOFROOLGH
$ %LVULJKWXSXQWLOLWLVMXVWWRXFKLQJWKHHGJHRIFLUFOH%$WWKDW
)LJXUHJLYHVDYLVXDOH[SODQDWLRQRIWKHVWHSVDERXWWREHGHVFULEHG7KHGLVWDQFHFLUFOH FDQPRYHEHIRUHFROOLGLQJZLWK
SRLQWWKHGLVWDQFHEHWZHHQWKHFHQWHUVRIWKHFLUFOHVLVHTXDOWRWKHVXPRIWKHUDGLL6LQFHZH
9WRWKHFHQWHURI%DNDVTUW ) ZHKDYHWKH OHQJWKVRIWZRVLGHVRIDULJKWWULDQJOH7KHWKLUGVLGHLVHTXDOWR'GLVWDQFH$FDQWUDYHO EHIRUHLWKLWV%6RDJDLQZHFDQXVHWKH3\WKDJRUHDQWKHRUHPDQGILQGWKHOHQJWK7 $UDGLXV%UDGLXV A)7KHGLVWDQFH$KDVWRPRYHDORQJ9WRFRPHLQWRFRQWDFWZLWK% LV'VTUW 7 DOUHDG\NQRZWKHVKRUWHVWGLVWDQFHIURP
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
)LJXUH )LQGLQJWKHIDUWKHVWWKDW$FDQJR
$DQG%
2QHILQDOFKHFNLVQHHGHG5HPHPEHUZKHQZHWHVWHGWKHVKRUWHVWGLVWDQFHEHWZHHQ
EXWLWGLGQRWWDNHLQWRDFFRXQWGLUHFWLRQ"+HUH VZKHUHWKDWFDQFRPHEDFNDQGELWHXV &RQVLGHUWKHVLWXDWLRQLOOXVWUDWHGLQILJXUH %RWKDUURZVDUHWKHVDPHOHQJWKEXWLQVOLJKWO\ GLIIHUHQWGLUHFWLRQV7KLVVKRZVWKDW\HVWKHPRYHPHQWYHFWRULVORQJHQRXJKWREULQJWKHWZR FLUFOHVFORVHHQRXJKWRWRXFKEXWWKHGLUHFWLRQLVVXFKWKDWWKH\ZRQ W6RDWWKLVSRLQWLQWKH
9WKHQWKHUH
DOJRULWKPZHQHHGWRGRDUHDOLW\FKHFN LI'LVWDQFHLVJUHDWHUWKDQWKHOHQJWKRI LVQRFROOLVLRQ
)LJXUH
9DQGWKHQPXOWLSO\LWE\'VTUW 7 1RZ&LUFOH$ %7KH-DYDFRGHLPSOHPHQWLQJWKLVDOJRULWKPLVOLVWHG
,IWKHILQDOWHVWLVSDVVHGZHFDQQRUPDOL]H ZLOOPRYHXQWLOLWLVMXVWWRXFKLQJFLUFOH EHORZ
// Early Escape test: if the length of the movevec is less // than distance between the centers of these circles minus // their radii, there's no way they can hit. double dist = B.center.distance(A.center); double sumRadii = (B.radius + A.radius); dist -= sumRadii; if(movevec.Magnitude() < dist){ return false; } // Normalize the movevec Vector N = movevec.copy(); N.normalize(); // Find C, the vector from the center of the moving // circle A to the center of B Vector C = B.center.minus(A.center); // D = N . C = ||C|| * cos(angle between N and C) double D = N.dot(C);
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
// Another early escape: Make sure that A is moving // towards B! If the dot product between the movevec and // B.center - A.center is less that or equal to 0, // A isn't isn't moving towards B if(D <= 0){ return false; } // Find the length of the vector C double lengthC = C.Magnitude(); double F = (lengthC * lengthC) - (D * D); // Escape test: if the closest that A will get to B // is more than the sum of their radii, there's no // way they are going collide double sumRadiiSquared = sumRadii * sumRadii; if(F >= sumRadiiSquared){ return false; } // We now have F and sumRadii, two sides of a right triangle. // Use these to find the third side, sqrt(T) double T = sumRadiiSquared - F; // If there is no such right triangle with sides length of // sumRadii and sqrt(f), T will probably be less than 0. // Better to check now than perform a square root of a // negative number. if(T < 0){ return false; } // Therefore the distance the circle has to travel along // movevec is D - sqrt(T) double distance = D - sqrt(T); // Get the magnitude of the movement vector double mag = movevec.Magnitude(); // Finally, make sure that the distance A has to move // to touch B is not greater than the magnitude of the // movement vector. if(mag < distance){ return false; } // Set the length of the movevec so that the circles will just // touch movevec.normalize(); movevec.times(distance); return true; %DQN6KRW &ROOLVLRQEHWZHHQWZRPRYLQJFLUFOHV
7KLVSUREOHPVHHPVHYHQPRUHFRPSOLFDWHGWKDQWKHSUHYLRXVRQH*LYHQWZRPRYLQJFLUFOHV GHWHUPLQHZKHWKHURUQRWWKH\FROOLGH/RRNLQJDWWKHSUREOHPLQILJXUHZHFDQVHHWKDW MXVWEHFDXVHWKHLUSDWKVFURVVGRHVQRWPHDQWKDWWKHFLUFOHVZLOOFRPHLQWRFRQWDFW2QHPD\ KDYHPRYHGRXWRIWKHZD\LQWLPH,WDOVRVKRZVWKDWMXVWEHFDXVHWKHLUSDWKVGRQRWFURVV GRHVQRWPHDQWKDWWKH\GRQ WFROOLGH
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
)LJXUH WKH'\QDPLF'\QDPLFFROOLVLRQSUREOHP
7KDQNIXOO\WKHVROXWLRQWRDYHU\KDUGSUREOHPFRXOGQRWEHVLPSOHU:KDWZHDUHUHDOO\ LQWHUHVWHGLQLVQRWWKHLUPRYHPHQWYHFWRUVEXWWKHLUPRYHPHQWUHODWLYHWRHDFKRWKHU,IZH WUDQVODWHFLUFOH
$ VPRYHPHQWVXFKWKDW%FDQEHFRQVLGHUHGVWDWLRQDU\ZHFDQXVHWKH
'\QDPLF6WDWLFVROXWLRQGHVFULEHGDERYH
)LUVWRIDOOVXEWUDFWWKHPRYHPHQWYHFWRURIRQHFLUFOHIURPDQRWKHU RU\RXFDQWKLQNRILWDV DGGLQJWKHUHYHUVHRIRQHYHFWRUWRDQRWKHU 7KHQSHUIRUPWKHG\QDPLFVWDWLFFROOLVLRQ DOJRULWKPRQWKHFLUFOHVDQGWKHQHZYHFWRU,IWKH\FROOLGHGLYLGHWKHOHQJWKRIWKHVKRUWHQHG YHFWRUE\WKHOHQJWKRIWKHRQH\RXRULJLQDOO\SDVVHGLQWRWKHIXQFWLRQ7KHUHVXOWVKRXOGEHD IORDWLQJSRLQWQXPEHUEHWZHHQDQG7KLVUHSUHVHQWVZKHQRYHUWKHFRXUVHRIWKHLU PRYHPHQWWKHFLUFOHVFROOLGHG0XOWLSO\WKHRULJLQDOPRYHPHQWYHFWRUVE\WKLVQXPEHUDQGWKH UHVXOWLVVKRUWHQHGPRYHPHQWYHFWRUVWKDWWDNHWKHFLUFOHVXSWRWKHSRLQWZKHUHWKH\WRXFK IRUWKHILUVWWLPH -XPSLQJWKH&XHEDOO $SSO\LQJWKHVHDOJRULWKPVWR'
'HWHFWLQJSUR[LPLW\EHWZHHQWZRVWDWLRQDU\VSKHUHV
7KHDSSOLFDWLRQRIWKLVDOJRULWKPWR'HQYLURQPHQWVFRXOGQ WEHHDVLHU&LUFOHVLQ'DQG VSKHUHVLQ'DUHERWKGHILQHGWKHVDPHZD\PDWKHPDWLFDOO\ *LYHQDFHQWHUSRLQWWKH ERXQGDULHVRIERWKFLUFOHVDQGVSKHUHVDUHGHILQHGDVDOOSRLQWVWKDWDUHDJLYHQGLVWDQFH WKH UDGLXV IURPWKHFHQWHUSRLQW6RVSKHUHVFDQEHPDWKHPDWLFDOO\VSHFLILHGLQWKHVDPHZD\DV FLUFOHVZLWKDFHQWHUSRLQWDQGDUDGLXV7KHUHLVRQHFDYHDWIRUWKH'UHSUHVHQWDWLRQ7KH FHQWHUSRLQWLQ'XVHVDWKLUGFRRUGLQDWH]6RWKHGLVWDQFHEHWZHHQWKHFHQWHUVRIWKHWZR VSKHUHVFDQEHIRXQGE\
,IWKDWGLVWDQFHLVOHVVWKDQWKHVXPRIWKHUDGLLRIWKHWZRVSKHUHVWKHQWKH\DUHLQFRQWDFW ZLWKHDFKRWKHU &ROOLVLRQRIDPRYLQJVSKHUHZLWKDVWDWLRQDU\VSKHUH
7KH'\QDPLF6WDWLFFROOLVLRQDOJRULWKPZRUNVLQ'EHFDXVHWKH'VFHQDULRFDQEHUHGXFHGWR ',I\RXORRNDWRXUVROXWLRQIRUWKLVSUREOHPLQ'\RX OOQRWLFHWKDWLWLVEDVHGDURXQGWZR YHFWRUV
9DQG& DQGDFRPPRQSRLQW WKHFHQWHURI$ 7KHVHWZRYHFWRUVGHILQHWKH
RULHQWDWLRQRIWKHSODQHLQ'DQGWKHSRLQWSURYLGHVDUHIHUHQFHWRZKHUHLQVSDFHWKDWSODQH OLHV)LJXUHVDQGVKRZWZRVSKHUHVWKHUHGRQHLQPRWLRQDQGWKHEOXHRQHDWUHVW 7KHVHILJXUHVDOVRVKRZWKHPRYHPHQWYHFWRURIWKHUHGRQHDQGWKHYHFWRUEHWZHHQWKH FHQWHUVRIWKHVSKHUHV1RWLFHWKH'SODQHWKDWLVSDVVLQJWKURXJKWKHREMHFWVLQWKHVFHQHLQ ERWKILJXUHV7KLVSODQHFXWVULJKWGRZQWKHPLGGOHRIWKHWZRVSKHUHVDQGDORQJWKHWZR YHFWRUVFOHDUO\VKRZLQJWKDWWKHVHYHFWRUVDUHFRSODQDU$OVRQRWLFHWKDWWKHSODQHFXWVWKH VSKHUHVSHUIHFWO\LQKDOIVRWKDWWKHDUHDVRIFRQWDFWEHWZHHQWKHVSKHUHVDQGWKHSODQHDUH FLUFOHVZLWKWKHVDPHFHQWHUDQGUDGLXVDVWKHVSKHUHV$OORIWKHLQIRUPDWLRQQHHGHGWRXVH WKHG\QDPLFVWDWLFDOJRULWKPZHGHVFULEHGDERYHLVSURMHFWHGLQWRD'VSDFHRQWKHOLJKWEOXH SODQH
9DQG &OLHDORQJWKHVDPHOLQHWKHQWKHUHDUHDQLQILQLWHQXPEHURISODQHVLQZKLFKWKHSUREOHPFDQ 7KHUHLVDVSHFLDOFDVHWREHFRQVLGHUHGDOWKRXJKLWVUHVROXWLRQLVWULYLDO,IWKHYHFWRUV
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
9DQG&DUHFROLQHDUWKDWPHDQV $LVPRYLQJGLUHFWO\WRZDUGVVSKHUH%DQGWKHTXHVWLRQRIZKHWKHUWKH\FROOLGH UHGXFHVWRRQO\RXUILUVWHDUO\HVFDSHWHVW1DPHO\GRHV$PRYHIDUHQRXJKWRKLW%"RULQ RWKHUZRUGV,V9JUHDWHUWKDQ &VXP5DGLL " EHVROYHG7KLVFDVHVKRXOGEHFKHFNHGIRU2IFRXUVHLI WKDWVSKHUH
7KHUHDUHQRFKDQJHVQHHGHGWRWKHFRGHDERYHLQRUGHUIRULWWRZRUNLQWKH'FDVH7KH FKDQJHVWKDWQHHGWREHGRQHDUHLQWKHFODVVHVWKDWDUHDVVXPHGE\WKHDERYHFRGH)RU H[DPSOHLQVWHDGRIWKH9HFWRUFODVVKDYLQJRQO\[DQG\PHPEHUYDULDEOHVLWVKRXOGEH FKDQJHGWRLQFOXGHDWKLUGPHPEHUYDULDEOH]
)LJXUH '\QDPLF6WDWLF&ROOLVLRQLQ '
)LJXUH 7KH'\QDPLF6WDWLF &ROOLVLRQSURMHFWHGLQ' &ROOLVLRQEHWZHHQWZRPRYLQJVSKHUHV
$JDLQE\WUDQVODWLRQRIWKHSUREOHPWRRQHVSKHUH VIUDPHRIUHIHUHQFHWKLVSUREOHPLV UHGXFHGWRWKH'\QDPLF6WDWLF'SUREOHPZKLFKLQWXUQVFDOHVGRZQWRWKH'FDVHDV GHVFULEHGDERYH)LJXUHVKRZVWZRVSKHUHVHDFKZLWKLW VRZQPRYHPHQWYHFWRUVKRZQLQ
% VPRYHPHQWYHFWRUDQGWKH\HOORZPRYHPHQW YHFWRUIURP$ WKHUHGEDOO LVWKHPRYHPHQWRI$DVREVHUYHGIURP% VSRLQWRIUHIHUHQFH 7KH'SODQHFRQWDLQLQJWKH\HOORZYHFWRUDOVRFRQWDLQVWKHFHQWHURIVSKHUH%DQGVRLWFDQ JUHHQ7KHRUDQJHYHFWRULVRSSRVLWHRI
EHXVHGWRVROYHWKHSUREOHP
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
)LJXUH &ROOLVLRQRIWZRPRYLQJVSKHUHVLQ'DQG KRZLWFDQEHUHGXFHGWRRQHPRYLQJFLUFOHLQ'
6LQNLQJ
1RZWKDW\RXKDYHGHWHUPLQHGWKDW\RXUFLUFOHVFROOLGH\RXZDQWWRKDYHWKHPERXQFHRIIRI HDFKRWKHULQDUHDOLVWLFPDQQHUWDNLQJLQWRDFFRXQWWKHLUUHODWLYHPDVVDQGVSHHG7RVROYH WKLVZHDUHJRLQJWRUHO\RQVRPHVLPSOHODZVRISK\VLFVVSHFLILFDOO\WKHFRQVHUYDWLRQRI PRPHQWXPDQGWKHFRQVHUYDWLRQRIHQHUJ\ /RRNDWILJXUHWRJHWDQLGHDRIWKHSUREOHPDQGWKHYDULDEOHVWKDWZHDUHJRLQJWRXVH 7KHUHGFLUFOHLVFLUFOHWKHEOXHRQHFLUFOH7KH\HDFKKDYHDPRYHPHQWYHFWRU PRYHYHFDQGPRYHYHFDQGDPDVVPDQGP
)LJXUH %RXQFH
&RQVHUYDWLRQRI0RPHQWXPVWDWHVWKDWWKHWRWDOPRPHQWXPRIWKHV\VWHPEHIRUHWKHFROOLVLRQ LVHTXDOWRWKHWRWDOPRPHQWXPLQWKHV\VWHPDIWHUWKHFROOLVLRQ,IZHUHSUHVHQWWKH PRPHQWXPRIDFLUFOHWREH3
0 9ZKHUH0LVWKHFLUFOHVPDVVDQG9LVLWVPRYHPHQW
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
YHFWRUWKHQZHFDQGHULYHWKHHTXDWLRQ
ZKHUHY DQGY DUHWKHPRYHPHQWYHFWRUVRIFLUFOHDQGUHVSHFWLYHO\DIWHUWKHFROOLVLRQ 6LQFHWKHVHFRQGFLUFOHJDLQVDQ\PRPHQWXPORVWE\WKHILUVWZHFDQUHSUHVHQWWKHGLIIHUHQFH
GHOWD3
EHWZHHQWKHPRPHQWXPVRIWKHEDOOVEHIRUHDQGDIWHUE\WKHVDPHYHFWRU
1RZKHUHLVZKHUHWKHGLIIHUHQFHEHWZHHQUHDOLW\DQGVLPXODWLRQFRPHVLQWRSOD\,IWKHVHWZR VSKHUHVZHUHWKHUXEEHUEDOOVZHDOOXVHGLQJ\PFODVVLQKLJKVFKRROZKHQWKH\KLWWKH\ ZRXOGGHIRUP7KLVGHIRUPDWLRQZRXOGLQFUHDVHWKHDUHDZKHUHWKHEDOOVDUHWRXFKLQJDQG VRPHRIWKHHQHUJ\ZRXOGEHORVWLQWKDWGHIRUPDWLRQ2WKHUDPRXQWVRILWZRXOGEHORVWLQ VSLQ%XWLQWKLVVLPXODWLRQZHDUHDVVXPLQJWKHEDOOVWREHULJLGIULFWLRQOHVVSHUIHFWVSKHUHV $FRPPRQUHDOZRUOGH[DPSOHRIWKLVW\SHPLJKWEHWKHVWHHOEDOOVKDQJLQJIURPDIUDPHWKDW FROOLGHZLWKHDFKRWKHUWRGHPRQVWUDWHDFWLRQUHDFWLRQ EHFDXVHWKH\DUHVRULJLGYHU\OLWWOHRI WKHLUPRPHQWXPLVORVWZKHQWKH\FROOLGHDQGVRZKHQ\RXVHWRQHEDOOVZLQJLQJLWWDNHV VRPHWLPHIRUWKHPDOOWRVWRS 6RLQRXUVLPXODWLRQRISHUIHFWULJLGVSKHUHVWKHRQO\WUDQVIHUHQFHRIPRPHQWXPFDQRFFXU
GHOWD3
DORQJWKHVLQJOHSRLQWRIFRQWDFWDVLOOXVWUDWHGLQILJXUH7KHUHIRUHZHFDQEUHDN
LQWRDXQLWYHFWRU1WKDWSRLQWVGRZQWKHOLQHRIFRQWDFWDQGDVFDODU3UHSUHVHQWLQJWKH PDJQLWXGHRIGHOWD36RLIZHDSSO\WKLVWRWKHHTXDWLRQVDERYHZHFDQVROYHIRUWKHQHZ PRYHPHQWYHFWRUVRIWKHFLUFOHVDQGJHW
6RLIZHFDQVROYHIRU3ZHFDQFDOFXODWHWKHQHZPRYHPHQWYHFWRUV 1RZORRNEDFNDWILJXUHDQGQRWLFHWKDWYDQGYFDQEHUHSUHVHQWHGE\WKHVXPRIWZR YHFWRUV RQHWKDWLVSDUDOOHOWRWKHOLQHDORQJZKLFKPRPHQWXPLVH[FKDQJHGDQGRQHWKDWLV SHUSHQGLFXODUWRLW8VLQJWKLVLQIRUPDWLRQZHFDQUHSUHVHQWYY YDQGY E\
:KHUHDDEDQGEDUHVFDODUV1LVWKHVDPH1DVPHQWLRQHGEHIRUHDQG4LVWKH QRUPDOL]HGYHFWRUSHUSHQGLFXODUWRWKHOLQHDORQJZKLFKPRPHQWXPLVH[FKDQJHGDQGRQWKH VDPHSODQHDV1DQGWKHPRYHPHQWYHFWRU 6XEVWLWXWLQJYLQHTXDWLRQIRUWKHYDOXHRIYLQHTXDWLRQDQGYLQHTXDWLRQIRUWKH YDOXHRIYLQHTXDWLRQZHJHW
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
$QGVLQFHY
D
1E
4DQGY
D
1E
4ZHFDQVHHWKDW
1RZZHFDQXVHWKH&RQVHUYDWLRQRI(QHUJ\WRVROYHIRU37KHHTXDWLRQIRUNLQHWLFHQHUJ\LV
6LQFHHQHUJ\LVFRQVHUYHGWKHWRWDOHQHUJ\EHIRUHWKHFROOLVLRQPXVWHTXDOWKHWRWDOHQHUJ\ DIWHUWKHFROOLVLRQ
8VLQJWKHPRYHPHQWYHFWRUDVWKHK\SRWHQXVHRIDULJKWWULDQJOHZHFDQVXEVWLWXWH
6XEVWLWXWLQJHTXDWLRQIRUD E D DQGE ZHJHW
1RWHWKDWWKHEDQGEWHUPVLQHTXDWLRQGURSRXWRIWKHHTXDWLRQ:LWKDQHTXDWLRQLQ WHUPVRIPPDDDQG3ZHKDYHDQHTXDWLRQZLWKYDULDEOHVWKDWDUHHLWKHUJLYHQRU FDQEHFDOFXODWHGIURPZKDWZDVJLYHQH[FHSWIRU36RLIZHVROYHIRU3ZHZLOOEHDEOHWR SOXJLQWKHNQRZQYDULDEOHVGHULYH3DQGWKHQXVH3WRFDOFXODWHWKHQHZPRYHPHQWYHFWRUV (TXDWLRQVKRZVHTXDWLRQDIWHUVROYLQJIRU3
6RSOXJJLQJWKLVLQWR(TXDWLRQV
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
1RWLFHWKDWIRUERWKY DQGY WKHWHUPLQWKH EUDFNHWVLVWKHVDPHVR\RXRQO\QHHGWR FDOFXODWHWKDWRQFH:LWKWKDWGRQH\RXFDQFDOFXODWHY DQGY 1RZWKDWZH YHGRQHWKH PDWKIRUWKLVWKHFRGHWRLPSOHPHQWWKHUHVXOWVLVYHU\VKRUWDQGTXLFN7KHYDULDEOH RSWLPL]HG3LQWKHFRGHUHIHUVWRWKHWHUPLQEUDFNHWVDERYH
// First, find the normalized vector n from the center of // circle1 to the center of circle2 Vector n = circle1.center - circle2.center; n.normalize(); // Find the length of the component of each of the movement // vectors along n. // a1 = v1 . n // a2 = v2 . n float a1 = v1.dot(n); float a2 = v2.dot(n); // Using the optimized version, // optimizedP = 2(a1 - a2) // ----------// m1 + m2 float optimizedP = (2.0 * (a1 - a2)) / (circle1.mass + circle2.mass); // Calculate v1', the new movement vector of circle1 // v1' = v1 - optimizedP * m2 * n Vector v1' = v1 - optimizedP * circle2.mass * n; // Calculate v1', the new movement vector of circle1 // v2' = v2 + optimizedP * m1 * n Vector v2' = v2 + optimizedP * circle1.mass * n; circle1.setMovementVector(v1'); circle2.setMovementVector(v2'); %DOO&RUQHU3RFNHW
7KHVHWHFKQLTXHVZLOODOORZ\RXXVHVSKHUHVZLWKDKLJKHUGHJUHHRIDFFXUDF\WKDQLVSUREDEO\ QHFHVVDU\LI\RXUVSKHUHVDUHDOOERXQGLQJVSKHUHV3UHFLVHFROOLVLRQVEHWZHHQVSKHUHVEHFRPH LPSRUWDQWZKHQVLPXODWLQJWKLQJVOLNHVSRROEDOOVRUPDUEOHVRUSRWHQWLDOO\URFNVLQD ODQGVOLGH%XWIRUVSKHUHVERXQGLQJFKDUDFWHUVIRUH[DPSOH\RXPLJKWQRWFDUHZKDWDQJOH WZRFROOLGLQJFKDUDFWHUVZRXOGERXQFHDZD\DW+RZHYHUSDUWVRIWKHVHPHWKRGVDUHIDVW HQRXJKWREHXVHIXOLIRQO\WRGHWHUPLQHWKDWDFROOLVLRQZDVDYRLGHG%XWZKRNQRZV XVLQJD SXPSHGXSVSDFHPDULQHDVDFXHEDOOMXVWPLJKWEHKXPRURXVHQRXJKWRGR« 6SHFLDOWKDQNVWR'DYH%DXPIRUKLVKHOSZLWKFROOLVLRQUHVSRQVH
Gamasutra - Features - "Pool Hall Lessons" [01.18.02]
&RS\ULJKW&030HGLD,QF$OOULJKWVUHVHUYHG
Related Documents
Collision Detection
November 2019 22
Precise Collision Detection
November 2019 14
Modul8 - Sprite & Collision Detection
November 2019 30
Vb6 Tutorial- Rectangle Collision Detection
May 2020 9
Collision
December 2019 15