在2D网格上创建LOS区域以追逐AI

我有一个二维网格，大约20×20，存储为一个数组。每个网格单元格可以包含一个不透明的对象或不包含。我也已经有一个algorithm来计算通过Bresenham在任何两个广场之间的LOS。

我想实现一个追逐玩家的AI游戏。我现在的规则是（重新评估每个步骤的优先级）：

如果我们可以看到玩家去得到他们（一次一步与迪克斯特拉/ A *寻路）。
如果我们看不到玩家去我们上次看到他们的地方。
如果我们看不到玩家，而且是我们上次见到他们的地方，请放弃并回家。

但是我想添加一个更进一步的规则：

如果我们看不到玩家，而且是我们上次见到他们的地方，但是只有一种方式可以隐藏起来，而不是通过我们。

这真的很难被发现。我想知道的做法是为每个网格分配一个或多个区域编号，使得在给定区域中的每个正方形都可以看到该区域中的所有其他正方形; 那么如果只有一个邻近区域的卫兵没有去过，卫兵就会进入。然而，这些区域重叠，而且即使是简单的地图也会产生大量可笑的地图（例如，由于房间中的不同部分逐渐变得可见，所以这种尴尬或困难）生成algorithm似乎至less是O（n ^ 2）或更差。或者，可以将区域计算为导航网格，但是这似乎是非常难以从网格图计算的。

有没有办法做到这一点，而不是手动在地图上提示？

总的来说，这项任务可能令人惊讶地困难; 它是美术画廊问题的一个变种，就像这个问题一样，它几乎变得更加复杂。

但是，如果你愿意接受一个有缺陷的，“足够好”的解决scheme，下面是一个： 留下一个“愿景线索” ，并评估是否只有一个不在“愿景线”旁边的出口。

当你发现目标时，开始标记你可以看到的所有单元格“visited”
在达到目标最后的已知位置后，检查您的服务水平的边界
- 如果有一个出口不导致“访问”单元格，继续到未访问的出口，并继续前进，直到分裂成两个（或更多）
- 如果有超过两个出口不导致“访问”单元，停止

持续条件示例：

| | | | <--- unvisited exit |...| |...| |...| <--- LOS -----------------+...| vvvvvvvvvvvvv......A.| <--- AI ---------------------+ ^ visited cells

停止条件示例：

  | | | | <--- unvisited exits (not contiguous) |...| | |...| | |...| v -----------------+...+------------ vvvvvvvvvvvvv......A...... ---------------------------------- ^ visited cells

这个解决scheme“足够好”的原因是因为它会遇到像这样的边缘情况的问题：

 --------------------------------- vvvvvvv......... vvvvvv.........+-+ vvvvv..........+-+ vvvv.......A...... ---------------------------------

人工智能应该在出现分裂出口的小障碍物的情况下做什么？停止？还是继续？请记住，从技术上来说，目标可能隐藏在障碍物的后面，避免被人看到，并在AI上加倍。

事实上，所有这些问题（LOS，导航）都将通过执行一些预处理而大大简化，使得几何结构更简单。然后可以按照您的建议进行操作 – 创建LOS区域 – 因为我们可以使用简化的几何体进行大量的假设。您可以决定您可以接受哪种处理。

Eric Lippert在一个方形网格中提供了一个关于用Shadowcasting计算视线的教程（当然是C＃）。

前五个会话定义了algorithm中使用的各种对象和最终代码

 private static Func<int, int, T> TranslateOrigin<T>(Func<int, int, T> f, int x, int y) { return (a, b) => f(a + x, b + y);being this: } private static Action<int, int> TranslateOrigin(Action<int, int> f, int x, int y) { return (a, b) => f(a + x, b + y); } private static Func<int, int, T> TranslateOctant<T>(Func<int, int, T> f, int octant) { switch (octant) { default: return f; case 1: return (x, y) => f(y, x); case 2: return (x, y) => f(-y, x); case 3: return (x, y) => f(-x, y); case 4: return (x, y) => f(-x, -y); case 5: return (x, y) => f(-y, -x); case 6: return (x, y) => f(y, -x); case 7: return (x, y) => f(x, -y); } }

和

 public static void ComputeFieldOfViewWithShadowCasting( int x, int y, int radius, Func<int, int, bool> isOpaque, Action<int, int> setFoV) { Func<int, int, bool> opaque = TranslateOrigin(isOpaque, x, y); Action<int, int> fov = TranslateOrigin(setFoV, x, y); for (int octant = 0; octant < 8; ++octant) { ComputeFieldOfViewInOctantZero( TranslateOctant(opaque, octant), TranslateOctant(fov, octant), radius); } }

我已经在我的Hexgrid实用程序项目中的六边形网格上调整了此代码的地形图：MIT License中的Open Source。