Я работаю над простой 2d игрой, в которой постоянно появляется множество врагов и преследуют игрока или игроков в python + pygame.Проблема, с которой я столкнулся, и один из многих, кто запрограммировал этот тип игры, состоит в том, что враги сходятся очень быстро.Я временно решил эту проблему с помощью функции, которая раздвигает любых двух врагов случайным образом, если они находятся слишком близко друг к другу.Это хорошо работает, но имеет дело с алгоритмом O (n ^ 2), который запускается каждый кадр, и при больших врагах программа начинает замедляться.
Когда моя программа запускается с этой функцией, враги, кажется, образуют круглый объект, который я прозвал «глыбой».Кажется, что скопление обычно эклиптическое, но на самом деле может быть более сложным (не симметричным), потому что, когда игрок движется, враги тянутся в разные стороны.Мне нравится, как ведет себя этот скопление, однако мне интересно, есть ли более эффективный способ его расчета.В настоящее время каждый враг в группе (часто> 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
Редактировать: некоторые скриншоты того, как выглядит сгусток: 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/
Сгусток, по-видимому, в основном круглый объект, только что растянутый (как затмениено может быть растянут в нескольких направлениях), однако в настоящее время он имеет прямые края из-за прямоугольных врагов.