¿Cómo debo hacer para que una matriz de objetos Bullet pueda colisionar con una matriz de objetos Zombie?

Sí, hay mejores formas de hacer esto. Estás haciendo la forma más ingenua y menos eficiente de detección de colisiones.

Hay varias cosas mal aquí. Primero, tiene una complejidad O (n ^ 2), lo cual es muy malo, pero ya lo sabes porque eso es lo que estás preguntando.

El otro problema del que quizás no se dé cuenta es el túnel. Dependiendo de la velocidad de la bala y el paso del tiempo, es posible que sus balas puedan estar en un lado de un objetivo en un cuadro, y pasar completamente a través de él y estar en el otro lado en el siguiente cuadro sin que se detecte una colisión.

Varias otras personas han sugerido un árbol quad / oct como las estructuras de datos apropiadas para solucionar el problema de complejidad que está preguntando, y no están equivocados al respecto.

Pero eso no resolverá el problema del túnel, por lo que voy a proponer una solución diferente.

Utilice un juego de franework, o tal vez un motor de juego real en lugar de tratar de escribir ingenuamente un juego desde cero.

Eres claramente un principiante, no te hagas las cosas más difíciles tratando de construir tu propio sistema de colisión.

Utilice el sistema de colisión bien probado de otra persona y concéntrese en su juego.

Como mínimo, integre algo como JBox2D: un motor de física de Java en su código y úselo para su detección de colisión de bala / zombie. Una mejor opción es usar el marco libgdx.

Podría ser una mejor opción que eso, incluso elegir un motor de juego como Unity,

¡Bienvenido al maravilloso mundo de la detección de colisiones!

Existen todo tipo de soluciones para su problema, todo tipo de árboles espaciales pueden ayudar aquí. Permítame darle un enfoque que puede funcionar bien para su caso de uso, ya que aprovecha que sus zombies son aproximadamente del mismo tamaño.

Hagamos una cuadrícula sobre su mapa, con un tamaño de celda de aproximadamente el tamaño de un zombie, para que cada zombie pueda cruzarse como máximo con 4 celdas. Ahora en cada cuadro haces esto:

HashMap > bulletsByCell;
para (Bullet bullet in bullets) {
bulletsByCell.get (cellIndex (bullet.pos)). add (bullet);
}
para (Zombie zombie in zombies) {
int [] cells = zombie.getCellIndices (); // devuelve 4 celdas
para (int celda en celdas) {
for (Bullet bullet in bulletsByCell.get (cell)) {
checkForHit (bala, zombie);
}
}
}

De esta manera, solo necesitas comprobar cada zombie con balas en su proximidad, y obtienes O (n) complejidad de tiempo.

¡Disfrutar!

Gracias por el A2A.

Te has topado con un mundo muy grande, lleno de rocas afiladas y criaturas peligrosas. El mundo de la partición espacial.

Hay muchos algoritmos y estructuras de datos que están diseñados exactamente para lo que estás hablando. Para seleccionar grandes tiradas de pruebas de colisión.

Sugiero comenzar simple.

Divide tu mundo en una cuadrícula de celdas 2D (o cubos si lo prefieres), donde cada celda es un poco más grande que los zombis. Pon un puntero a cada zombie en las celdas que lo contienen (sé que Java no usa punteros, pero quédate conmigo aquí). Mantenga esta cuadrícula 2D de listas de punteros a zombis actualizadas en cada cuadro. Luego, cuando desee probar si una bala en particular está colisionando con algún zombi, simplemente calcule en qué celda se encuentra la bala e itere a través de la lista de esa celda para encontrar un subconjunto muy pequeño de zombis con los que podría chocar y luego haga su normal prueba de colisión con esos.

Esto se llama una cuadrícula uniforme.

Tal vez un desarrollador de juegos dará una buena respuesta. No soy un desarrollador de juegos, pero que yo sepa, las técnicas para reducir el trabajo que necesita para verificar todo generalmente implican particionar u ordenar sus datos de alguna manera.

Si mantiene sus listas ordenadas de alguna manera, solo tiene que verificar los zombis que están en el área general de sus balas. Por lo tanto, puede verificar cada viñeta, pero no se molesta en verificar los zombis que están al otro lado de la pantalla en una viñeta determinada.

Incluso solo ordenar a los zombies por su posición x ayudaría a reducir la cantidad de control. Puedes dejar de pasar por la lista de zombies si superas la posición x de la bala.

Para ser realmente rápido, necesita una estructura conocida como quadtree. Esto subdivide la pantalla en cuartos, luego divide cada cuarto en cuartos, y así sucesivamente. Para encontrar qué zombis hay en la región de la bala, atraviesa el árbol hasta llegar a los zombis que se encuentran en la parte derecha de la pantalla. Así que ya no tienes que iterar sobre todos los zombies.

Un quadtree es como un árbol binario, excepto que cada nodo tiene cuatro ramas que salen de él, en lugar de dos.

Algo como esto: QuadTree.java

Pero si no tienes tantos zombis, puede que no valga la pena el esfuerzo.

Incluso con un bucle anidado sobre dos listas, puede buscar optimizaciones. No tiene sentido comprobar la coordenada y de un zombie si su coordenada x no está cerca de la bala.

No estoy seguro acerca de Java, pero en GameMaker, un motor con el que estoy muy familiarizado, hay una característica llamada parenting . Puede ejecutar una verificación para un objeto primario, y todos los objetos secundarios del padre tendrán aplicado el código resultante. Hace que sea más fácil crear el código, pero no creo que sea diferente para ejecutar el código.

Lo que haría es dividir el espacio en áreas (por ejemplo, cubos) y primero detectar qué objeto está en qué cubo, y luego colisionar solo aquellos en los mismos cubos.

Esto es solo un pensamiento: nunca he hecho una colisión masiva de objetos en la práctica.

No estoy seguro de qué tipo de juego estás haciendo, pero puedes usar particiones espaciales para tratar de eliminar rápidamente las colisiones que no pueden suceder. En 2D puedes intentar mirar un árbol cuádruple y en 3D puedes probar un árbol oct.

Bueno, supongo que usa algún tipo de coordenadas, así que intente construir una cuadrícula de modo que solo tenga que verificar cada colisión de balas con Zombies en la misma parte de la cuadrícula. Eso reduciría de n ^ 2 a n