3

我有一个任务是用 AI 做一个 tron 游戏。我和我的团队几乎成功了，但我们正在努力寻找一个好的启发式方法。我们教过 Voronoi，但它有点慢：

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 三角测量吗？

4

2 回答 2

5

看看Google 的 AI Challenge 的事后分析。

于 2013-04-29T12:46:34.393 回答
1

好吧，我正在考虑重新设计我的旧 Wurmeler 游戏（包括 AI）所以我在寻找新想法时遇到了你的问题所以这是我对旧 AI 的见解

  • Wurmeler 与 tron 类似，但许多 slover 和 worms 转动顺畅
  • 游戏空间是 2D 位图
  • 每个 AI 都非常简单……愚蠢，……
  • 但导航比我好
  • 除非他们被其他玩家关闭
  • 或压碎成局部最小值/最大值
  • 但他们仍然很有趣

好的，现在每个决策动作中的 AI 算法：

  1. 从蠕虫创建一些光线

    • 一个在运动方向
    • 少数向左转了某个角度（5度步即可）
    • 少数人向右转

  2. 评估光线长度

    • 从蠕虫直到它到达边界
    • 或其他蠕虫路径曲线

  3. 使用最大规则改变航向

这个旧的 AI 只维护导航，但我想实现更多（这还没有完成）：

  1. 将地图划分为正方形部分

    • 每个部分将具有已填充空间的平均密度
    • 所以如果可能的话，人工智能会选择填充较少的区域

  2. 添加策略

    • 导航（已经完成）
    • 逃跑（如果太近和落后，远离附近的玩家）
    • 攻击（如果在相对平行的路线上并且太靠近和在前面）

  3. 可能是从光栅到矢量的转换

    • 应该加快光线追踪和碰撞检测
    • 但是随着长度的增加可能会变慢...必须尝试一下
    • 可能使用现场算法
于 2013-11-04T20:38:03.810 回答