Dividir los chunks por cuadrantes para la detección de colisiones

[danielrossyamitrano]

Se me ocurrió ayer, leyendo en wikipedia sobre entidades, que podríamos divividir de forma lógica (no necesariamente en los json, digo) al chunk en cuatro (o más) listas de mobs/props, de acuerdo a la posición de cada uno. Un mob iría cambiando de lista a medida que se fuera moviendo de cuadrante, y sólo haría detección de colisiones con otros objetos dentro de su cuadrante, de manera de agilizar esa detección. Qué te parece?

[einacio]

En este momento la lógica de colisiones ralentiza los frames significativamente o es una optimización temprana? Si no esta tirando todo abajo, yo diría de simplemente poner un comentario en el método linkeando a este issue como sugerencia a futuro

El 06/11/2015 19:30, "Daniel" notifications@github.com escribió:

Se me ocurrió ayer, leyendo en wikipedia sobre entidades, que podríamos divividir de forma lógica (no necesariamente en los json, digo) al chunk en cuatro (o más) listas de mobs/props, de acuerdo a la posición de cada uno. Un mob iría cambiando de lista a medida que se fuera moviendo de cuadrante, y sólo haría detección de colisiones con otros objetos dentro de su cuadrante, de manera de agilizar esa detección. Qué te parece?

— Reply to this email directly or view it on GitHub https://github.com/ludica-squamata/mano-gift/issues/70.

[danielrossyamitrano]

No sé si puedo decir que ralentiza. En mi PC anda todo bien, pero en la net (que tiene muchos menos recursos), anda a menor velocidad. No sé si es tema de la detección de colisiones. Como decis, se me ocurrió más bien como una optimización temprana (Git no tiene una etiqueta propia para designar la prioridad de un issue, este sería "low" en Google Code; aunque también creo que tendríamos que haber seteado unas milestones para organizar).

[danielrossyamitrano]

Ayer, como prueba, eliminé todos los props de casas y arboles, a excepción de la casa que aparece atrás del héroe ni bien arranca el mapa. Liberé los fps, y como esperaba, la velocidad aumentó de 62 a 150 fps. No sé si será un tema de la detección de colisiones ya, o de las listas de props en general.

[danielrossyamitrano]

Estuve pensando en un comentario que hiciste sobre este issue. Vos planteaste:

tenes que recorrer la lista para medir la distancia pero si cortas las listas en cuadrantes, como haces para interactuar con algo del otro cuadrante? digamos, una pared que justo queda sobre el borde

Se me ocurre una solución bastante simple. Digamos que el mob está sobre el borde de su cuadrante, y quiere interactuar con algo que está del otro lado. Simple, para interactuar (tocar, chocar con) tenes que estar mirando para ese lado, a lo cual el mob estaría comprobando colisión con todos los sprites del otro cuadrante, el que está mirando, no el suyo propio. Así se puede intereactuar con cosas que están "justo en el borde" aún recorriendo una sola lista. Qué te parece?

[danielrossyamitrano]

Me quedé pensando en este issue anoche, y me di cuenta de que dividir un chunk (1) en el número que sea va a provocar un hard limit igual con el chunk que le siga en ese mismo stage. Por lo tanto, la primera división de cuadrantes no debería ser sobre 2, sino sobre 1.5.

Y por qué digo la primera?

Pensé en la situación del comentario de arriba, pero con el personaje colocado exactamente antes del limite horizontal, pero en el centro del mapa. Es decir, en el cruce de todos los cuadrantes, lo que sería 0,0 en ejes cartesianos. Si el PC quiere interactuar con algo más allá del borde, según lo descrito arriba tendría que comprobar colisión contra los props del cuadrante que está tratando alcanzar, no el suyo propio. Pero eso igual nos deja posiblemente con dos cuadrantes enteros para escanear, cuando a nosotros lo único que nos interesa es lo que está cerca del PC. A lo cual pensé "¿Y si hubiera un sector más chico que sólo contuviera los props de ese area?". Clarametne, un prop pertenecería a más de una lista (la de su cuadrante, y la de su sector dentro de ese cuadrante, en principio). Pero este razonamiento se podría seguir hasta que cada "sector" tuviera un solo prop (un tanto extremo, pero ¿me seguis?)

La idea es que estos "sectores" funcionen en algo así como los layers de una imagen. Un mismo prop aparecería en más de un sector, pero sólo una vez por layer. Los sectores entonces serían subdivisiones de un layer, cada vez más granulada.

No sé cuantos layers necesitariamos, pero pensé que podriamos usar un nivel de granularidad para la interacción directa con los objetos, otra para la detección de colisiones, una más para el A* de los mobs, otra más alejada para los ataques a distancia, etc.