若是用方程式解决此问题，将会变得非常复杂，利用向量就简单得多了。 简化问题 首先介绍简化问题的方法。题目中，小球是半径为1的圆形。将小球简化成点，并把所有障碍物的半径加1，这样就能把相同的球作为点求解。虽然这种简化并不能让题目更简单，但是小球的运动轨迹可以变成一条直线，对解题也比较有利。 状态表现与模拟 接下来正式考虑如何模拟。此题需要模拟出二维平面上小球的运动轨迹。为了预测出小球的运动轨迹，需要知道小球的当前位置和方向。可以用表示当前位置的位置向量和表示方向的单位向量表示这两种信息。那么，就可以先找出下一个将要撞击的障碍物并输出其序号，然后更改小球的位置和方向信息。这种操作要重复至无障碍物可撞击，或撞击到第10次为止。 找出小球和障碍物的撞击点 首先找出下一个将会撞击的障碍物。给出小球的当前位置p和方向向量q时，小球的轨迹将定义为从当前位置起始的射线。此射线和障碍物的边界相交的瞬间，小球和障碍物相互撞击。射线和障碍物的边缘发生多次相交时，将在第一个交点上撞击。为此，需要先找出第一个与障碍物发生撞击的位置。假设小球会以每秒d的速度前行，那么可以得到函数f(t)=p+t•d（t≥0）表示的小球轨迹。小球轨迹与圆心为c、半径为r的障碍物相交的时间t可以通过如下公式求解。 因为向量a有|a|2=a•a的性质，所以对上面公式的两边取平方，得到如下等式。 展开等式并整理后，可得到如下关于t的二次方程。 现在，方程式的系数已不再是向量，而全部变成了实数。因此，解开此二次方程就能得知小球的轨迹和障碍物的边界相交的时刻。对各障碍物求出此方程为正值的解后，找出其中的最小值，这样就能得知何时与哪个障碍物发生撞击。二次方程是否有解，意味着小球与障碍物会否发生撞击。 代码15-7是给出小球当前状态和障碍物信息时，能够求出撞击时间的hitCircle()函数。虽然hitCircle()函数非常简单，不过很难判断能否正确处理各种情况。下面看看函数会如何处理二次方程的解，首先要经过如下确认过程。 二次方程没有实根时（sols.empty()），小球的轨迹和障碍物不会相交。因此，小球将不会与障碍物发生撞击。 在返回的实根中，应当忽略小于等于0的根。负值的实根表示小球在前进方向的后方位置与直线相交，所以应当忽略。等于0的实根表示小球已经与障碍物接触，也应当忽略。一旦与障碍物发生撞击，小球的位置就会与当前障碍物的边缘相邻。因此，如果不忽略0的情况，小球就会与最后一个障碍物反复撞击。实际代码中为了避免解二次方程时可能发生的数值误差，即使实根为正，如果其比一个很小的数值EPSILON还要小，那么也会忽略。 代码15-7 找出小球与障碍物之间撞击点的函数 const double EPSILON = 1e-9; const double INFTY = 1e200; // 按照大小顺序返回二次方程ax^2+bx+c=0的所有实根。 vector<double> solve2(double a, double b, double c) { double d = b*b - 4*a*c; // 无解时 if(d < -EPSILON) return vector<double>(); // 重根 if(d < EPSILON) return vector<double>(1, -b / (2*a)); vector<double> ret; ret.push_back((-b - sqrt(d)) / (2*a)); ret.push_back((-b + sqrt(d)) / (2*a)); return ret; } // 处在here的小球每秒向前移动dir时，返回与以center为圆心 // radius为半径的障碍物发生撞击的时间。 // 不发生撞击时，返回“极大值”INFTY。 double hitCircle(vector2 here, vector2 dir, vector2 center, int radius) { double a = dir.dot(dir); double b = 2 * dir.dot(here - center); double c = center.dot(center) + here.dot(here) - 2 * here.dot(center) - radius * radius; vector<double> sols = solve2(a, b, c); if(sols.empty() || sols[0] < EPSILON) return INFTY; return sols[0]; } hitCircle()函数中即使返回两个实根，也只会确认sols[0]。小球总在障碍物外部，所以返回两个实根时，或者均为负值，或者均为正值。因为已忽略了小于0的值，所以只考虑两根均为正的情况，此时只确认出更小的值即可得出结论。因此，通过这些过程就能判断出，此障碍物会与小球的轨迹相交。 处理反射 对各障碍物调用hitCircle()函数后，找出其中的最小值就能求出与这些障碍物发生撞击的时间。接下来将小球移到发生撞击的位置，并适当变换小球的运动方向，这样即可继续模拟。假设，从p位置沿d方向滚来的小球与半径为r的障碍物在q位置上发生撞击，之后小球会向哪个方向移动呢？ 图15-7 模拟小球与障碍物反射的方法 最容易想到的方法如图15-7(a)所示，利用向量的内积计算出入射角θ后，把d旋转π2θ度。这种方法虽然可行，但是实现起来比较复杂，而且不能用于解决三维空间的问题。更好的一种方法就是利用反射向量。图15-7(b)表示，将d反射至从圆心到撞击点的向量n后，得到了新的方向向量。 那么，怎样才能求出反射向量呢？如图15-7(c)所示，首先把需要反射的向量d投影到n，得到d'。接下来把从d的端点到d'端点的向量d '(d)=d '+d向d反射两次，就能得到反射的结果d''。简化此结果就能编写出代码15-8的reflect()函数，此函数只有1行代码。各位可以想想，用圆方程和直线方程实现该函数会有多么繁琐。 代码15-8 计算小球与障碍物发生撞击后弹出角度的reflect()函数 // here处的小球从dir方向滚动到以center为圆心的障碍物的 // contact位置发生碰撞时，返回小球的新的滚动方向。 vector2 reflect(vector2 dir, vector2 center, vector2 contact) { return (dir - dir.project(contact - center) * 2).normalize(); } 全部合并 这两个函数已准备就绪，接下来就可以进行结合。代码15-9是使用hitCircle()函数和reflect()函数模拟小球运行轨迹的算法源代码。hitCircle()函数和reflect()函数都具有常数时间复杂度，所以计算前k次撞击时，simulate()函数的时间复杂度是O(nk)。此题中，n=50、k=10，因此，此算法可在限制时间内完成运算。 代码15-9 解决弹球模拟问题的模拟代码 // 给出小球当前位置和移动方向时，最多输出前10次撞击。 void simulate(vector2 here, vector2 dir) { // 总将方向保存为单位向量。 dir = dir.normalize(); int hitCount = 0; while(hitCount < 10) { // 找出此次将要撞击障碍物。 int circle = -1; double time = INFTY*0.5; // 遍历所有障碍物，找出最先撞击的障碍物。 for(int i = 0; i < n; ++i) { double cand = hitCircle(here, dir, center[i], radius[i] + 1); if(cand < time) { time = cand; circle = i; } } // 不再与障碍物发生撞击而直接滚出游戏台时 if(circle == -1) break; // 输出被撞击的障碍物序号。 if(hitCount++) cout << ""; cout << circle; // 计算小球的新位置。 vector2 contact = here + dir * time; // 将here和dir更新为撞击位置和新方向。 dir = reflect(dir, center[circle], contact); here = contact; } cout << endl; }
