Good heuristic for Tron

Question

I have an assigment to do a tron game with AI. Me an my team almost made it but we're trying to find a good heuristic. We taught about Voronoi, but it's kinda slow :

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

We have 5 seconds to make a move and this algorithm doesn`t sound too good ! I don't need code ... we just need an ideea ! Thank you !

Later edit : Should we try Delaunay Triangulations ?

Answer 1

Have a look at the postmortem of Google's AI Challenge about this.

Answer 2

well i am considering redesigning my old Wurmeler game (AI including) so i stumped on your question while searching for new ideas so here is my insight from my old AI

• Wurmeler is similar to tron but much slover and worms turn smoothly
• game space is 2D bitmap
• each AI is very simple ... stupid,...
• but navigate better than me
• unless they are closed by other player
• or crush into local min/max
• but still they are fun

OK now the AI algorithm in every decision move:

1. create few rays from Worm

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

2. evaluate the ray length

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

3. use the max rule to change heading

This old AI maintain only navigation but I want to implement more (this is not yet done):

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

2. 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)

3. may be conversion from raster to vector

   • 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