在二维网格游戏板上的移动攻击区域内寻找攻击目标空间的算法

Question

我正在寻找一个算法名称或实现，它可以从我可以攻击给定目标的有效移动列表中为我提供有效位置。

我有一个 2D 瓷砖 map 和一个英雄，他可以移动一定数量的 Action 并攻击范围内的敌人。由于 map 上的障碍物，英雄的移动区域会有所不同并且可能会出现漏洞:

在这道题中我学到了how to combine this move area with attack area to get the total "threat" range我的英雄在游戏板上发挥的作用。在这种情况下，有 2 个敌人在威胁范围内并且可以被攻击:

我正在寻找一个通用算法的名称或信息，该算法将采用:

• 威胁区域(黄色)
• 有效 Action (橙色)
• 目标位置(绿色)

并且返回橙色区域内我可以攻击给定目标的所有单元格。因为敌人施加了他们自己的威胁区域，所以我不一定需要最近的方 block - 我会检查可能的移动并为我的英雄选择威胁最小的那个移动到那里进行攻击。

Answer 1

您的 HERO 的可到达磁贴集是已知的。每个瓷砖周围都是一个威胁区域，它就像一个(凸？)多边形(菱形？)然后敌人的位置可以被认为是另一个凸多边形(在这种情况下是正方形)。在一般情况下，您想测试这些多边形是否相交，是吗？

不幸的是，这个普遍的问题似乎是more difficult比人们希望的要多。

如果我们能发现您的问题具有某些特殊属性，我们可能会更幸运。如果您的 HERO 的威胁区域始终是凸面的，那么您可以使用菱形的边界执行内部/外部测试(类似于 CGAL 的 bounded_side_2 测试)

如果您发现该方法不够好，那么您可以这样做:为棋盘预先生成一组“可攻击位置”；每个细胞都知道 HERO 可以攻击的一组其他细胞。这是时空权衡，如果您没有大的内存限制或移动障碍，那么它应该工作得很好。