好的Tron启发式算法

Question

我有一个任务是制作一款带有人工智能的电子游戏。我和我的团队已经快完成了，但我们正在尝试寻找一个好的启发式方法。我们考虑使用沃罗诺伊图，但它运行速度有点慢：

for yloop = 0 to height-1
for xloop = 0 to width-1

// Generate maximal value
closest_distance = width * height

for point = 0 to number_of_points-1
  // calls function to calc distance
  point_distance = distance(point, xloop, yloop)

  if point_distance < closest_distance
    closest_point = point
  end if
next

 // place result in array of point types
 points[xloop, yloop] = point

next
next

我们只有5秒钟时间来采取行动，这个算法听起来并不好！我不需要代码......我们只需要一个想法！ 谢谢！

后来编辑：我们应该尝试 Delaunay 三角剖分吗？

- Matei

---

任何能够快速查询邻居的数据结构都可以在这里使用。查找KD树/四叉树。 - Thomas Jungblut

Answer 1

可以看一下关于Google的AI挑战的事故调查报告。

- Mihai Maruseac

---

我看了那篇文章，完全没有帮助：)) - Matei

Answer 2

我考虑重新设计我的旧Wurmeler游戏（包括AI），所以在寻找新想法的时候遇到了你的问题，以下是我从我的旧AI中获得的见解:

• Wurmeler与tron类似，但速度要慢得多，虫子可以平滑地转弯。
• 游戏空间是2D位图。
• 每个AI都非常简单...愚蠢...
• 但比我导航更好。
• 除非它们被其他玩家封闭
• 或撞到局部最小值/最大值。
• 但它们仍然很有趣。

现在是每次决策动作中的AI算法：

1. 从虫子创建一些射线

   • 一个朝向运动方向
   • 几个向左转动某个角度（5度步进很好）
   • 几个向右转动

2. 评估射线长度

   • 从虫子出发，直到它撞到边界
   • 或者撞到另一个虫子路径曲线

3. 使用最大规则来改变头部方向

这个旧的AI仅保持导航，但我想实现更多（目前还没有完成）：

1. 将地图分成方块区域

   • 每个区域都将具有已填空间的平均密度
   • 因此，如果可能，AI将选择填充较少的区域

2. 添加策略

   • 导航（已完成）
   • 逃避（如果距离玩家太近且在后面，则远离玩家）
   • 攻击（如果相对平行且距离太近且在前方）

3. 可能需要将光栅转换为矢量

   • 应该加速光线追踪和碰撞检测
   • 但随着长度的增加，可能会变慢...必须尝试并查看
   • 可能使用场算法

- Spektre