dirigiendo una masa de enemigos a la vez

Question

Estoy trabajando en un simple juego de 2d en el que muchos enemigos continuamente engendran y persiguen al jugador o jugadores en python + pygame. Un problema con el que me topé, y con el que muchas personas han programado este tipo de juegos, es que los enemigos convergen muy rápido. He creado una solución temporal a este problema con una función que aleja a dos enemigos al azar si están demasiado cerca el uno del otro. Esto funciona bien, pero se trata de un algoritmo O (n^2) que se ejecuta en cada cuadro y en enemigos altos el programa comienza a ralentizarse.

Cuando mi programa se ejecuta con esta función, los enemigos parecen formar el objeto redondo apodado un "grupo". El grupo parece usualmente eclíptico, pero en realidad puede ser más complejo (no simétrico) porque a medida que el jugador se mueve los enemigos son arrastrados en diferentes direcciones. Me gusta la forma en que se comporta este grupo, sin embargo, me pregunto si existe una forma más eficiente de calcularlo. Actualmente, todos los enemigos del grupo (a menudo> 100) primero se mueven en la dirección del jugador y luego se separan. Si hubiera, en cambio, una forma de calcular la cifra que crea el grupo, y cómo se mueve, se ahorraría una gran cantidad de cálculos.

No estoy seguro de cómo abordar el problema. Es posible calcular dónde se mueve el borde de la figura y luego expandirlo para asegurarse de que el área permanezca igual.

también actualmente mis dos funciones que se utilizan para mover los enemigos:

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 

Editar: algunas capturas de pantalla de cómo se ve el grupo: 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/

El grupo parece ser principalmente un objeto redondo simplemente estirada (como un eclipse pero puede ser estirado en múltiples direcciones), sin embargo, Curre ntly tiene bordes rectos debido a los enemigos rectangulares.

Answer 1

Hay varias maneras de hacerlo, dependiendo de su juego. Aquí hay algunas ideas para mejorar el rendimiento:

1. Permitir un poco de superposición.
2. Reduzca la verificación de distancia para que se realice después de un número fijo de fotogramas.
3. Mejore su fórmula de control de distancia. Si está utilizando la fórmula de distancia estándar, esto se puede optimizar de muchas maneras. Por un lado, deshacerse de la raíz cuadrada. La precisión no importa, solo la distancia relativa.
4. Cada unidad puede realizar un seguimiento de una lista de unidades cercanas. Solo realiza tus cálculos entre las unidades en esa lista. De vez en cuando, actualiza esa lista comprobando contra todas las unidades.
5. Dependiendo de cómo esté configurado su juego, puede dividir el campo en áreas, como cuadrantes o celdas. Las unidades solo se prueban contra otras unidades en esa celda.

EDIT: Cuando las unidades se acercan a su objetivo, puede que no se comportan correctamente. Sugeriría en lugar de tenerlos en casa en el objetivo exacto desde lejos, que realmente buscan un objetivo aleatorizado cercano. Como una compensación de su objetivo real.

Estoy seguro de que hay muchas otras maneras de mejorar esto, es bastante abierto, después de todo. También debo señalar Boids y flocking que podrían ser de su interés.

Answer 2

Puede definir un grupo como un objeto separado con un número fijo de "ranuras" espaciales para cada unidad enemiga en el grupo. Cada ranura tendría un conjunto de coordenadas relativas al centro del grupo y estaría vacía o contendría una referencia a una unidad.

Una nueva unidad que intente unirse a la agrupación se moverá hacia la ranura libre más interna, y una vez que llegue allí "se mantendrá en formación", su posición siempre será la posición de la ranura que ocupa. Las agrupaciones tendrían un radio mucho mayor que una sola unidad, ajustaría la posición para evitar la superposición de otras agrupaciones o unidades sueltas que no intentaran unirse al grupo, etc.

En algún momento, sin embargo, necesitaría Sin embargo, trato con las interacciones de las unidades individuales en el grupo, así que no estoy seguro de que valga la pena. Creo que la sugerencia de Austin Henley de dividir el campo en células/regiones y solo probar las unidades en las células cercanas es el enfoque más práctico.

Answer 3

Creo que estás buscando flocking.

Answer 4

La mejor introducción al movimiento del comportamiento de flocado/dirección: http://www.red3d.com/cwr/steer/. Vea el documento adjunto red3d paper. Y el relacionado OpenSteer