保卫萝卜4：从攻击范围到算法逻辑
2022/05/312907 浏览脑洞专区
众所周知，塔防游戏中的“塔”，是有攻击范围的。本文将使用保卫萝卜4中的火瓶子进行模拟，分两部分展示其底层算法逻辑。
↑ ↑ ↑ 火瓶子 ↑ ↑ ↑
------分割线------
Part1：对建筑物的攻击范围
1.算法分析：
鉴于建筑物为静态存在，我们可以近似地使用Dijkstra算法来判定攻击范围。Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题，主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
每一个地图，可以看成一个已知大小的二维矩阵，只要确定了中心点（塔的位置），然后向上下左右四个方向展开搜索，规定中心点的数值为0，下一个格子的数值为本格子的数值加1。对于地图上的每一个格子，算出到达这个格子的最短路径，最终遍历完所有的格子之后，获得最短的路线。
2.实例演示：
↓ ↓ ↓ 一级火瓶子 ↓ ↓ ↓
↓ ↓ ↓ 二级火瓶子 ↓ ↓ ↓
↓ ↓ ↓ 三级火瓶子 ↓ ↓ ↓
3.建模总结：
限定直线 y=0 和 y=x 在第一象限所围成的区域（含边界），各等级火瓶子有以下攻击范围。一级火瓶子：(1,0)，(1,1)，(2,0)。二级火瓶子：(1,0)，(1,1)，(2,0)，(2,1)。三级火瓶子：(1,0)，(1,1)，(2,0)，(2,1)。
Part2：对兔子的攻击范围
1.算法分析：
由于兔子会在路径上匀速移动，我们可以使用碰撞检测算法来判定攻击范围。碰撞检测是建立在碰撞体上的，而碰撞体是对一个物体“边界”的确切描述。它描述了每个需要进行碰撞检测的物体的边界，并依靠数学方法判断这些边界是否相交，进而产生碰撞检测的结果。
兔子的碰撞体可近似看成一个圆（或者是一个圆角的正方形），火瓶子的攻击范围也是一个圆，恰好构成了最简单的一类碰撞体——圆形碰撞体。根据初中数学的勾股定理，以及两圆相交的判定定理，即可获取其有效的攻击范围。
2.实例演示：
↓ ↓ ↓ 一级火瓶子 ↓ ↓ ↓
↓ ↓ ↓ 二级火瓶子 ↓ ↓ ↓
↓ ↓ ↓ 三级火瓶子 ↓ ↓ ↓
↓ ↓ ↓ 2D碰撞检测 ↓ ↓ ↓
↓ ↓ ↓ 巨呆兔和呆萌兔的对比 ↓ ↓ ↓
↓ ↓ ↓ 模型高度对比 ↓ ↓ ↓
3.建模总结
圆形碰撞体拥有最简单的计算过程，在运动速度够快（或形状够圆）的情况下也不会有太大的违和感，所以这种碰撞体在弹幕游戏和塔防游戏中应用广泛。对于巨呆兔而言，它所在的路径 并不在火瓶子的攻击范围内，但它的2D模型中心点却在路径上方，且其半径比呆萌兔的模型半径大，所以火瓶子完成了“不可能”做到的降维打击，呆萌兔幸运地逃过一劫（笑）。
------分割线------
如果有小伙伴对本文感到疑惑，或者想与楼主作进一步的探讨，欢迎在评论区留言哦~