algorithm - algoritmo - ¿Cómo se manejan los objetos que se mueven entre quads cuando se usan quadtrees?
quadtree matlab (2)
Estoy tratando de usar quadtrees para detección de colisión en un juego que estoy haciendo, pero no estoy seguro de cómo manejar objetos que podrían estar moviéndose entre diferentes quads.
La única forma en que puedo pensar es aclarando todo el árbol en cada fotograma, y luego agregando todo nuevamente, pero parece que eso puede hacer que la CPU sea más intensiva y poco eficiente. ¿Revisa cada objeto en cada fotograma para ver si se ha movido fuera del límite de su cuadrángulo actual, y si es así, quítelo y léalo? De nuevo, parece que puede ser bastante ineficiente porque estarías realizando controles de colisión en cada objeto en movimiento en cada fotograma.
Además, con respecto a los quadtrees pero sin relación con los objetos que se mueven en ellos, ¿cómo manejas múltiples objetos en el mismo quad? La mayoría de los sitios que he leído sobre ellos dicen que solo deberías tener uno, tal vez dos, objetos en un quad, y si obtienes más que eso, apúntalos hacia abajo en el árbol. ¿Qué pasa si tienes una situación como esta ? Tienes tres círculos y todos están en los bordes del nivel debajo de ellos para que no puedan ir más abajo, pero hay tres todos en el mismo nivel, que la gente dice que no deberías tener.
La eliminación / re-adición se puede optimizar moviendo hacia arriba el árbol cuádruple en lugar de eliminar por completo el elemento del árbol y luego volver a agregarlo, es decir, pasar al cuadrante "principal" y luego agregar el "padre" - si no cabe en el "padre", ve al "abuelo", etc.
En cuanto a su segunda preocupación, necesitará cierta flexibilidad, si los 3 están en un filo, entonces no puede bajarlos, pero eso debería ser (perdón por el juego de palabras) un caso marginal.
No creo que sea particularmente ineficiente implementar su sugerencia: verifique si un objeto se ha movido fuera de su árbol cuádruple y, de ser así, quítelo y vuélvalo a agregar. Cualquier objeto que se mueva de un cuadro al siguiente necesitará realizar alguna detección de colisión, ¿no es así? Y las operaciones quadtree solo se llevan a cabo si se mueven los quadtrees, y el tiempo de CPU que se gasta allí probablemente se ve eclipsado por el tiempo de la CPU, haciendo el más preciso "¿Toca el objeto A un objeto B?" cómputos. Entonces no sé que puedes hacerlo mejor.
En su segunda pregunta: no sé cómo otras personas implementan quadtrees, pero permito que los objetos ocupen más de un quadtree, precisamente por la razón que usted ha dado en su diagrama (cuando un objeto se extiende a ambos lados de un límite). Por lo tanto, un objeto tiene una "lista actual de quads" en lugar de un "quad actual".