游戏算法题

​​1、最小圆覆盖算法关键性质若点 p不在当前点集 S的最小覆盖圆内则 p一定在 S∪ {p}的最小覆盖圆的边界上。最小覆盖圆是唯一的。最终的最小圆要么由圆上至少三个点确定三点定圆要么由圆上两个点确定以这两点连线为直径。算法步骤随机化点集遍历0 ~ n整个点集初始圆为当前点圆心直径0的圆。i在当前圆外时更新圆心为i的坐标遍历0 ~ i-1j在当前圆外时更新i到j之间的距离为直径遍历0 ~ j-1k在当前圆外时更新​​三点i, j, k唯一确定一个圆最差情况是O(n^3)但随机初始化后更新次数少可以看作为O(n)。CircleminCircleCover(std::vectorPointpoints){if(points.empty())return{{0,0},0};if(points.size()1)return{points[0],0};// 1. 随机打乱点集 [1,2,4,6](ref)std::srand(std::time(0));std::random_shuffle(points.begin(),points.end());Circle currentCircle{points[0],0.0};for(size_t i1;ipoints.size();i){if(!isInside(points[i],currentCircle)){currentCircle{points[i],0.0};// 点i在边界上for(size_t j0;ji;j){if(!isInside(points[j],currentCircle)){currentCirclecircleFrom2Points(points[i],points[j]);// 点j也在边界上for(size_t k0;kj;k){if(!isInside(points[k],currentCircle)){// 点k也在边界上三点定圆 [1,2,6](ref)currentCirclecircleFrom3Points(points[i],points[j],points[k]);}}}}}}returncurrentCircle;}1.1、三点定圆转载https://blog.csdn.net/weixin_46098577/article/details/118659102不共线的三点相互连接必然构成一个三角形这个三角形称为圆的内接三角形这个圆称为三角形的外接圆。三角形三边垂直平分线的交点即为三角形外接圆的圆心。CirclecircleFrom3Points(constPointa,constPointb,constPointc){// 计算三条中垂线的交点外心doubleAb.x-a.x,Bb.y-a.y;doubleCc.x-a.x,Dc.y-a.y;doubleEA*(a.xb.x)B*(a.yb.y);doubleFC*(a.xc.x)D*(a.yc.y);doubleG2*(A*(c.y-b.y)-B*(c.x-b.x));if(std::fabs(G)1e-5){// 三点共线返回以最远两点为直径的圆doubled1distance(a,b),d2distance(a,c),d3distance(b,c);if(d1d2d1d3)returncircleFrom2Points(a,b);if(d2d1d2d3)returncircleFrom2Points(a,c);returncircleFrom2Points(b,c);}Point center;center.x(D*E-B*F)/G;center.y(A*F-C*E)/G;doubleradiusdistance(center,a);return{center,radius};}2、GJK碰撞检测算法2.1、闵可夫斯基差/闵可夫斯基和点集A与B的闵可夫斯基和被定义为A B {a b | a ∈ Ab ∈ B}GJK算法用到的不是闵可夫斯基和而是闵可夫斯基差即A - B {a - b | a ∈ Ab ∈ B}GJK算法核心若两个多边形相交则它们的闵可夫斯基差必然包括原点。2.2、单纯形k阶单纯形simplex指的是k维空间中的多胞形该多胞形是k1个顶点组成的凸包。2.3、Support 函数Support函数的作用是计算多边形在给定方向上的最远点。2.4、GJK步骤转自https://zhuanlan.zhihu.com/p/5111642483、三维SAT3.1、二维SAT如果两个物体必须是凸有凹陷就不准彼此分离那么一定能找到一条只需要一条轴线将这两个物体分隔在轴线的两侧如图。选择其中一条边作为轴两个物体投影算是否有交集即可。3.2、三维SAT版本这里的图片用了一位师兄的笔记我自己想了半天想不出来。流程是面检测面检测边检测面检测和二维版本差不多是两个物体中每次选一个面法线作为轴判断另一个物体上所有点在轴上投影是否有一个越过界限产生交集如果找到一个面法线没有交集那么就不相交。面检测可能会出现这种情况两者很接近不相交但面检测都找不到那个轴。前两种是面检测检测不出来这时候需要一个额外的分离轴看第三种情况。边检测是找一个额外的面检测每次两个物体各选一条边两个边的点互相做差就能做出一个面这个做差就构成了闵可夫斯基支撑面。每个点都考虑太暴力。需要先排除一些情况。//判断是否符合条件floatCBAmath.dot(C,B_x_A);floatDBAmath.dot(D,B_x_A);floatADCmath.dot(A,D_x_C);floatBDCmath.dot(B,D_x_C);returnCBA*DBA0ADC*BDC0CBA*BDC0;AB是边1对应的朝外面的两个法线CD是边2对应的朝内的两个法线CD法线朝内相当于二维闵可夫斯基中的相减操作。CBA * DBA 0​​ ​ADC * BDC 0表示​​这两个法线应该尽量互相垂直不要接近互相平行如下图这样交叉着的两个面元两个边的叉乘就是中间的黄线这个就是支撑面的法线如果没有交叉虽然有法线但其实不构成支撑面相当于并没有意义。如果两边近似平行它们的叉积会接近零向量无法定义一个良好的方向计算其投影距离也就没有意义且数值不稳定。如果两条边对应的面元在空间中没有交叉即使它们不平行其叉积方向也可能指向闵可夫斯基差集内部或者对应一个​​凹陷的​​concave或​​无效的铰链状结构​​而非凸包的​​外表面​​。这样的方向无法作为有效的分离轴。CBA * BDC 0确保两个边不是同向的想象二维闵可夫斯基差找支撑点时要往方向最远点找两个同向的点做差肯定是在闵可夫斯基差内部的所以没有用。三维情况也差不多两条边不能都在左上角或右上角因为那两个边碰撞前会有其他边对碰撞。因为这个面是在闵可夫斯基面上找的因此要符合闵可夫斯基面的标准RVOReciprocal Velocity Obstacles互惠速度障碍流场步骤1构建网格与成本场划分网格将游戏地图划分为均匀的网格如正方形、六边形。 标记障碍遍历网格将不可行走的区域如墙壁、山脉标记为“障碍”。 计算成本场为每个非障碍网格计算一个移动成本值。 基础成本通常平坦地形为1。 惩罚成本对希望单位“避开但不完全阻挡”的区域增加成本如沼泽3敌方防御塔附近5。这使流场能生成更智能、更安全的路径。步骤2生成积分场积分场存储了从地图上每个点到达目标点的“总成本”。计算过程类似于Dijkstra算法或带启发函数的A的反向传播*初始化将所有目标点可能是一个区域的成本设为0放入开放列表。 传播 从开放列表中取出成本最低的节点。 检查其上、下、左、右、对角共8个邻居。 邻居的新成本 当前节点成本 移动到邻居的代价考虑对角移动的√2倍成本。 如果计算出的新成本低于邻居的当前成本则更新邻居成本并将邻居加入开放列表。 重复直到开放列表为空。最终得到一个积分场其中每个格子的值代表从该格子到目标点的最小累积移动成本。步骤3生成流场向量场这是最关键的一步根据积分场为每个格子计算一个指向目标的最佳移动方向向量。核心方法梯度下降。对于格子(x, y)查看其8个邻居的积分值。移动方向应指向积分值降低最快的方向即成本下降最陡的方向。 具体计算方向向量可以通过中心差分法近似求得 向量XCost(x−1,y)−Cost(x1,y) 向量YCost(x,y−1)−Cost(x,y1) 然后对(向量X, 向量Y)进行归一化得到一个单位长度的方向向量。 这个向量即表示单位站在(x, y)时下一步最应朝向的方向。