Хорошая эвристика для Tron

Question

У меня есть желание сделать tron ​​игру с AI. Моя команда почти сделала это, но мы пытаемся найти хорошую эвристику. Мы учили о Вороного, но это своего рода медленно:

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 секунд, чтобы сделать ход, и этот алгоритм Безразлично `звучит слишком хорошо! Мне не нужен код ... нам просто нужна идее! Спасибо!

Позже отредактируйте: Должны ли мы попробовать триангуляции Делано?

Answer 1

Просмотрите the postmortem of Google's AI Challenge об этом.

Answer 2

хорошо я рассматриваю перепроектирование моей старая игра Wurmeler (AI включая), поэтому я озадачен на свой вопрос при поиске новых идей, так что здесь мое понимание от моего старого AI

• Wurmeler похож на Tron, но много slover и черви плавно
• игровое пространство 2D растровое изображение
• каждый AI очень простой ... глупый, ...
• но навигация лучше меня
• , если они не будут закрыты другим игроком
• или раздавить в местный мин/макс
• , но все они весело

OK теперь алгоритм AI в каждом решении двигаться:

1. создать несколько лучей от Worm

   • один в направлении движения
   • несколько повернулась влево на некоторый угол (5 шаг степени отлично)
   • несколько повернута вправо

2. оценить длину RAY

   • от червя до его границы
   • или другая кривая пути червя

3. использовать максимальное правило, чтобы изменить заголовок

Этот старый AI поддерживать только навигацию, но я хочу, чтобы реализовать более (это еще не сделано):

1. делят карту на площадь разделы

   • каждая секция будет иметь среднюю плотность уже заполненного пространства
   • поэтому, если возможно ИИ будет выбирать менее заполнены площадь

2. добавить Стратегии в

   • Navigate (уже сделано)
   • Бегите (уйти от ближнего игрока, если слишком близко, и сзади)
   • (если на относительном параллельном курсе и слишком близко и спереди)

3. может быть переведено ион из растра в векторе

   • должен ускорить луч traceing и обнаружение colision
   • , но с ростом длиной может быть медленнее ... надо попробовать и посмотреть
   • возможного использования алгоритмов полевых