Tron的好启发式

Question

我有一个任务，要用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三角剖分吗？

Answer 1

有关这一点，请查看the postmortem of Google's AI Challenge。

Answer 2

好吧，我正在考虑重新设计我的旧Wurmeler游戏(包括AI )，所以我在寻找新想法的时候偶然发现了你的问题，所以这是我对旧AI的见解

• Wurmeler类似于tron，但许多解算器和蠕虫平滑地转向
• 游戏空间是2D位图
• 每个AI都非常简单...愚蠢，...
• 但导航比我
• 更好，除非他们被其他玩家
• 关闭或挤入本地最小/最大
• ，但它们仍然很有趣

<代码>F215

好的，现在AI算法在每一步决策中：

1. 从蠕虫

创建几条光线

- one in movement direction
- few turned to the left by some angle (5 degree step is fine)
- few turned to the right

​

1. evaluate ray length

- from worm until it hit border
- or another worm path curve 

​

1. 使用最大值规则更改标题

这个老的AI只维护导航，但我想实现更多(这还没有完成)：

1. divide map to square sections

- each section will have the average density of already filled space
- so if possible AI will choose less filled area

​

1. add strategies

(为添加策略)

- navigate (already done)
- flee (go away from near player if too close and behind)
- attack (if on relative parallel course and too close and in the front) 

​

可以将

1. 从栅格转换为矢量

- should speed up the ray traceing and colision detection
- but with growing length may be slower ... have to try it and see
- possible use of field algorithms

​