En cualquier juego en 2D, debes saber en qué orden dibujar tus sprites. Por lo general, dibujas desde la parte posterior de la escena hacia el frente, mientras que los objetos anteriores están cubiertos por los posteriores. Este es el algoritmo estándar del pintor utilizado para representar la profundidad en un lienzo (digital o de otro tipo).
Por Zapyon - Trabajo propio, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14256921
La forma más sencilla de hacer un seguimiento de esto es colocando todos sus objetos en una gran matriz, ordenados por su profundidad. Así que en la escena anterior, su matriz se vería como: [Montaña, suelo, árbol1, árbol2, árbol3,…]
El problema con una sola matriz grande
El problema con una lista de visualización central es que no hay una manera fácil de averiguar qué objetos están en pantalla en un momento dado. Para hacerlo, debe recorrer toda la matriz y comprobar cada objeto. Esto se convierte principalmente en un problema si tiene un gran mundo de juegos en el que existen muchos objetos fuera de la pantalla y no debe renderizarse ni actualizarse..
Un hash espacial es una forma de almacenar sus objetos para evitar este problema. Lo bueno de usar un hash es que siempre lleva un tiempo constante averiguar qué objetos hay en la pantalla, sin importar cuán grande sea el mundo del juego.!
Ahora, la mayoría de los motores de juegos no te dejan jugar con la forma en que estructuran sus objetos internamente, pero si estás programando en un entorno donde tienes el control de los sorteos (como tu propio motor OpenGL, un JavaScript puro). juego, o más marcos abiertos como LÖVE), esto podría ser algo que valga la pena implementar.
La Alternativa: Hashes Espaciales
Un hash espacial es solo un tabla hash donde cada tecla es una coordenada 2D y el valor es una lista de objetos del juego en esa área.
Imagina que tu mundo está dividido en una cuadrícula de modo que cada objeto pertenezca a al menos una celda. Aquí le indicamos cómo buscaría algo en la posición (420,600) si tuviera esto implementado en JavaScript:
var X, Y = 420,600; // Ajustar X e Y a la cuadrícula X = Math.round (X / CELL_SIZE) * CELL_SIZE; Y = Math.round (Y / CELL_SIZE) * CELL_SIZE; // Ahora compruebe qué elementos están en esa posición spatialHash [X + "," + Y] // esta es una lista de objetos en esa celda
¡Es fácil! Inmediatamente se puede saber qué hay en esa posición. La clave es una concatenación de cadenas de las coordenadas X e Y, pero no lo hace. tener ser una cadena, ni necesita una coma en el medio; solo tiene que ser único para cada par de X e Y.
Para ver por qué esto es tan conveniente, considera cómo obtendrías los objetos en esta posición utilizando una gran matriz:
var X = 420; var Y = 600; para (var i = 0; i
Estamos revisando cada objeto, incluso si la mayoría de ellos están muy lejos, para empezar. Esto puede dañar en gran medida su rendimiento si está haciendo muchas búsquedas como esta y su gameObjects la matriz es enorme.
Un ejemplo concreto
Si aún no estás convencido de lo útil que puede ser esto, aquí tienes una demostración escrita en JavaScript puro en la que intento procesar un millón de objetos en el mundo del juego. En ambos casos, solo se representan los objetos en pantalla.
Haga clic para ver la demostración en vivo en ejecución.!
Y la versión hash espacial en vivo..
La versión de matriz única es dolorosamente lenta. Incluso si guarda los elementos que están en la pantalla para no tener que revisar todos los fotogramas, todavía tiene que revisar toda la matriz de nuevo cuando la cámara se mueve, lo que lleva a un picado severo.
El solo hecho de cambiar la forma en que almacenamos nuestros objetos de juego puede marcar la diferencia entre una experiencia fluida y un juego no jugable..
Implementando un hash espacial
Un hash espacial debería ser realmente fácil de implementar en cualquier idioma (de hecho, ¡pasar del primer ejemplo al segundo anterior solo tomó 30 líneas de código adicionales!)
Hay cuatro pasos para implementar esto como su sistema de renderizado:
Configurar la tabla hash.
Añadir y eliminar objetos en el hash..
Recoge objetos en un área determinada..
Ordena los objetos por profundidad antes de renderizarlos.
Puede ver una implementación funcional en JavaScript en GitHub como referencia.
1. Configurar la tabla de hash
La mayoría de los idiomas tienen algún tipo de tabla / mapa hash incorporado. Nuestro hash espacial es solo una tabla hash estándar. En JavaScript solo puedes declarar uno con:
var spatialHash = ; var CELL_SIZE = 60;
La única otra cosa que mencionar aquí es que tiene un margen de maniobra para elegir el tamaño de la celda. En general, el hecho de que sus celdas sean el doble de grandes que su objeto promedio parece funcionar bien. Si sus celdas son demasiado grandes, entonces estará jalando demasiados objetos con cada búsqueda. Si son demasiado pequeños, tendrá que revisar más celdas para cubrir el área que desea.
2. Agregar y eliminar objetos en el hash
Agregar un objeto al hash es solo un asunto que se ajusta a una celda, crea la matriz de celdas si no existe y se agrega a esa matriz. Aquí está mi versión de JavaScript:
spatialHash.add = function (obj) var X = Math.round (obj.x / CELL_SIZE) * CELL_SIZE; var Y = Math.round (obj.y / CELL_SIZE) * CELL_SIZE; tecla var = X + "," + Y; if (spatialHash [key] == undefined) spatialHash [key] = [] spatialHash [key] .push (obj)
Sin embargo, hay una advertencia: ¿Qué sucede si su objeto abarca varias celdas o si es demasiado grande para caber en una celda??
La solución es solo agregarlo a todos Las células que toca. Esto garantiza que si alguna parte del objeto está a la vista, entonces se procesará. (Por supuesto, también debes asegurarte de que no estés renderizando estos objetos varias veces).
No he implementado una función de eliminación en mi ejemplo, pero eliminar un objeto es solo una cuestión de sacarlo de la (s) matriz (s) de la que forma parte. Para hacer esto más simple, puede hacer que cada objeto mantenga una referencia a las celdas a las que pertenece..
3. Recoge objetos en un área determinada
Ahora, aquí está el núcleo de esta técnica: dado un área en la pantalla, desea poder obtener todos los objetos allí..
Todo lo que necesita hacer aquí es comenzar a repasar todas las celdas según el lugar donde se encuentre su cámara en el mundo del juego y recopilar todas las sublistas en una matriz para renderizar. Aquí está el fragmento relevante de JavaScript:
relleno var = 100; // Relleno para agarrar celdas adicionales alrededor de los bordes para que el jugador no vea los objetos "pop" en existencia. var startX = -camX - relleno; var startY = -camY - relleno; var endX = -camX + canvas.width + padding; var endY = -camY + canvas.height + padding; var onScreen = [] para (var X = startX; X < endX; X += CELL_SIZE) for(var Y = startY; Y < endY; Y += CELL_SIZE) var sublist = spatialHash.getList(X,Y) if(sublist != undefined) onScreen = onScreen.concat(sublist)
4. Ordenar los objetos por profundidad antes de renderizarlos
Puede que ya se haya dado cuenta de que renunciar a la idea de la gran lista de visualización también significa renunciar a la conveniente clasificación en profundidad. Tomamos objetos de nuestra cuadrícula según su ubicación, pero la matriz que obtenemos no está ordenada de ninguna manera..
Como paso final antes de renderizar, tenemos que ordenar nuestra matriz en función de alguna clave. Le di a cada objeto un valor de profundidad, y así puedo hacer:
onScreen.sort (función (a, b) return a.depth> b.depth)
Antes de finalmente rendirlo todo:
para (var i = 0; i
Este es uno de los inconvenientes de este método, que tiene que ordenar lo que hay en pantalla en cada fotograma. Siempre puede acelerar esto asegurándose de que todas sus sub-listas estén ordenadas, de modo que pueda combinarlas mientras concatena para mantener el orden.
¡Eso es! Ahora debería tener un sistema de representación que funcione (con suerte mucho más rápido)!
Otros usos y consejos
Esta puede ser una técnica realmente útil, pero como dije en la introducción, solo puedes hacer esto en un motor de juego o marco que te dé control sobre las llamadas de sorteo. Sin embargo, hay cosas que puedes usar para hacer hashes espaciales además del render. De hecho, se usan más comúnmente para acelerar la detección de colisiones (puede omitir cualquier verificación de colisión para los objetos que sabe que están muy lejos o que no están en la misma celda).
Otra técnica que es similar a hashes espaciales, pero un poco más complicada, es usar un quadtree. Mientras que un hash espacial es solo una cuadrícula plana, un quadtree es más bien una estructura jerárquica, por lo que no tiene que preocuparse por el tamaño de celda, y puede obtener más rápidamente todos los objetos en un área determinada sin tener que revisar todo. célula.
En general, debe tener en cuenta que una estructura espacial no siempre será la mejor solución. Es ideal para un juego que tiene:
Un mundo grande con muchos objetos.
relativamente pocos objetos en la pantalla en comparación con el tamaño del mundo
en su mayoría objetos estáticos
Si todos los objetos se mueven todo el tiempo, deberá seguir retirándolos y agregándolos a diferentes celdas, lo que podría incurrir en una penalización de rendimiento significativa. Era un sistema de renderizado ideal para un juego como Move or Die (casi el doble de fps) ya que los niveles estaban formados por una gran cantidad de objetos estáticos, y los personajes eran las únicas cosas que se movían.
Esperamos que este tutorial le haya dado una idea de cómo estructurar los datos espacialmente puede ser una forma fácil de mejorar el rendimiento, y de que su sistema de renderizado no siempre tiene que ser una lista lineal única.!
Share
Por Zapyon - Trabajo propio, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14256921
Accentsconagua
