направляет массу врагов сразу

Question

Я работаю над простой 2-й игрой, в которой много врагов постоянно появляются и преследуют игрока или игроков в игре python + pygame. Проблема, с которой я столкнулся, и многие люди, которые запрограммировали этот тип игры, столкнулись с тем, что враги сходятся очень быстро. Я сделал временное решение этой проблемы с помощью функции, которая толкает любых двух врагов случайным образом, если они слишком близки друг к другу. Это хорошо работает, но это алгоритм O (n^2), который запускается каждый кадр и у высоких врагов программа начинает замедляться.

Когда моя программа работает с этой функцией, враги, похоже, образуют круглый объект, который я называю «скоплением». Скопление кажется обычно эклиптическим, но может быть более сложным (не симметричным), потому что, когда игрок движется, враги тянутся в разных направлениях. Мне нравится, как ведет себя этот clump, однако мне интересно, есть ли более эффективный способ его вычисления. В настоящее время каждый враг в скоплении (часто> 100) сначала перемещается в сторону игрока, а затем раздвигается. Если бы вместо этого был способ вычислить фигуру, которую создает компромисс, и как она движется, это сэкономит массу вычислений.

Я не совсем уверен, как подойти к проблеме. Может быть возможно рассчитать, где находится граница фигуры, а затем расширить ее, чтобы убедиться, что область остается неизменной.

Кроме того, мои две функции в настоящее время используются для перемещения врагов:

def moveEnemy(enemy, player, speed): 
    a = player.left-enemy.left 
    b = player.top-enemy.top 
    r = speed/math.hypot(a,b) 
    return enemy.move(r*a, r*b) 

def clump(enemys): 
    for p in range(len(enemys)): 
     for q in range(len(enemys)-p-1): 
      a = enemys[p] 
      b = enemys[p+q+1] 
      if abs(a.left-b.left)+abs(a.top-b.top)<CLUMP: 
       xChange = (random.random()-.5)*CLUMP 
       yChange = ((CLUMP/2)**2-xChange**2)**.5 
       enemys[p] = enemys[p].move(int(xChange+.5), int(yChange + .5)) 
       enemys[p+q+1] = enemys[p+q+1].move(-int(xChange+.5),-int(yChange+.5)) 
    return enemys 

Edit: некоторые снимки экрана, как глыба выглядит: http://imageshack.us/photo/my-images/651/elip.png/ http://imageshack.us/photo/my-images/ 832/newfni.png/

http://imageshack.us/photo/my-images/836/gamewk.png/

скопление, кажется, в основном круглый объект просто растягивается (как затмение, но может растягиваться в разных направлениях), однако Curre ntly имеет прямые края из-за прямоугольных врагов.

Answer 1

Существует несколько способов сделать это, в зависимости от вашей игры. Вот некоторые идеи для повышения производительности:

1. Разрешить некоторые перекрытия.
2. Снимите проверку дистанции после определенного количества кадров.
3. Улучшите формулу проверки расстояния. Если вы используете стандартную формулу расстояния, это можно оптимизировать по-разному. Во-первых, избавиться от квадратного корня. Точность не имеет значения, только относительное расстояние.
4. Каждый блок может отслеживать список ближайших подразделений. Выполняйте расчеты между единицами в этом списке. Каждый так часто обновляйте этот список, проверяя все блоки.
5. В зависимости от того, как ваша игра настроена, вы можете разбить поле на области, например квадранты или ячейки. Единицы проверяются только на другие блоки в этой ячейке.

EDIT: Когда блоки подобраться к своей цели, он не может вести себя правильно. Я бы предложил вместо того, чтобы забирать их навстречу по точной цели издалека, что они на самом деле ищут рандомизированную ближайшую цель. Как смещение от их реальной цели.

Уверен, что есть много других способов улучшить это, в конце концов, это довольно открыто. Я также должен указать Boids и flocking, которые могут представлять интерес.

Answer 2

Вы можете определить скопление как отдельный объект с фиксированным числом пространственных «слотов» для каждого вражеского юнита в скоплении. Каждый слот будет иметь набор координат относительно центра скопления и будет либо пустым, либо будет содержать ссылку на один блок.

Новый блок, пытающийся присоединиться к скоплению, будет двигаться к самому внутреннему свободному слоту, и как только он попадет туда, он «останется в форме», его положение всегда будет занимать положение слота. Скопления имели бы радиус, намного больший, чем один блок, отрегулировали бы положение, чтобы избежать перекрытия других скоплений или ослабленных узлов, которые не пытались присоединиться к скоплению, и т. Д.

В какой-то момент вам нужно будет однако, я не уверен, что это стоит того, чтобы иметь дело с взаимодействиями для отдельных единиц в скоплении. Я думаю, что предложение Остина Хенли о разделении поля на клетки/регионы и только тестирование против единиц в соседних ячейках является наиболее практичным подходом.

Answer 3

Я думаю, что вы ищете flocking.

Answer 4

Лучшее введение в движение флокирования/рулевого управления: http://www.red3d.com/cwr/steer/. См. Прилагаемую бумагу red3d paper. И связанные OpenSteer