[PSP] Lista para bliteo (en C)

En ANSI C está implementado el algoritmo de ordenación quicksort, que te puede ayudar a ordenar los sprites según su profundidad:

Ejemplo de uso de qsort en C

Para mi lo más recomendable es tener a parte una lista ordenada según Y de punteros a esas estructuras.

webez escribió:Para mi lo más recomendable es tener a parte una lista ordenada según Y de punteros a esas estructuras.

Eso está claro, el problema que que no se cómo hacer la lista en sí y eso es lo que me gustaría saber.


Chano Marrano he estado mirando eso del qsort pero a parte de no comprenderlo demasiado, no se me ocurre cómo hacer uso de él, si no es molestia podrías ilustrarme un poco? Gracias

Si sólo vas a hacer la ordenación una vez (al cargar el nivel), cualquier algoritmo de ordenación te vale) como la que te han dicho (explicación http://www.conclase.net/c/librerias/funcion.php?fun=qsort ) o te lo implementas tu.

Si van a existir inserciones que deben estar ordenadas continuamente durante la partida, es mejor algo tipo lista, pudiendo usar desde algo sencillo como lista simples o algo más completo como un arbol binario o una lista doblemente enlazada.

El algoritmo quicksort sirve para ordenar un array de elementos (en tu caso, un array de descriptores de sprites).

Puedes crear un array como el siguiente:
spriteInfo *orden[MAX_SPRITES];

donde spriteInfo* son punteros a las estructuras en la que almacenas la información relativa a sprites, y MAX_SPRITES es el número máximo de sprites que puede manejar tu motor. Recuerda que debes rellenar el array con los punteros a las estructuras.

Antes de transmitir los sprites a la pantalla, si detectas que algún sprite se ha movido, debes ejecutar:
qsort(orden, MAX_SPRITES, sizeof(spriteInfo *), compararPosicionSprites);

Y la función compararPosicionSprites a implementar sería la siguiente:

int compararPosicionSprites(const void *_a, const void *_b)
{
spriteInfo *a = (spriteInfo *) _a;
spriteInfo *b = (spriteInfo *) _b;

return ( ((a->posY * RES_X) + a->posX) - ((b->posY * RES_X) + b->posX) );
}

donde RES_X es la resolución horizontal de la pantalla y posX y posY las coordenadas de los sprites.

Muchas gracias por las respuestas. webez, tus soluciones son buenas, el problema es que mi nivel de prograación no está al mismo nivel y de ahí que cualquier cosa que se aleja un poco de los ifs y los whiles ya me confunde por eso preguntaba cómo crear una lista... porque todavía no se hacerlo correctamente (esperemos que en verano con más tiempo le metamos un estudio serio al C y me deje de programar a modo autodidacta xq hago aguas)

Chano Marrano, al final he usado el qsort (aunq me lo han tenido que explicar aún más detenidamente de nuevo) y he conseguido tener los enemigos ordenados cómo quería (es decir, muchas gracias tio) haciendo así
qsort(tEnemigos, MAXENEMIGOS, sizeof(struct stObjeto), comparar_elementos);

Si no te importa, me podrías decir si es posible y cómo hacer uso de ésto con otros miembros de mi struct que no comparten el nombre[], como son jugador, arbol, bidon ... etc

Yo había pensado en redireccionar todos los miembros a otra struct que si que los numerara cómo tu dices y luego blitear, pero no se si ésto es posible, es una burrada que se comería la memoria de la PSP ... ni cómo hacerlo al fin y al cabo.

Espero vuestras respuestas cómo agua de Mayo, muchas gracias a todos!



PD:el juego ya lo tengo portado a PSP, sólo queda el problema de la ordenación y un par de paridas y de gráficos para sacar la primera beta.

La verdad es que no he entendido la pregunta . ¿Puedes repetirla, explicándola un poco mejor?

La lista de orden contiene punteros a estructuras, no el contenido de las estructuras, así que el tamaño que ocupa en memoria es muy pequeño. Si manejas por ejemplo 1000 enemigos, la lista almacena 1000 punteros, y suponiendo que cada puntero ocupe 4 bytes, la lista sólo ocupa unos 4KB. Además, que yo sepa, la PSP tiene 32MB de RAM (o por ahí anda), así que muy gorda la tienes que liar para quedarte sin memoria.

Realmente me he explicado horriblemente... a ver si ahora más pausadamente...

La cosa está en que no se cómo podría hacer una lista de orden que apuntara a objetos con nombres distintos.

Ahora tengo la función actuando con todos los objetos del struct llamados tEnemigos[un número]
declarados así:
stObjeto tEnemigos[MAXENEMIGOS];

también tengo otros objetos actuando en el juego, como es el personaje principal, árboles:
stObjeto jugador;
stObjeto arbol;
... etc.

Lo que no se es cómo hacer una lista con punteros que los señalen a todos sin que sea imprescindible que tengan el mismo nombre ( osea, que estén en la lista indistintamente: jugador, arbol, tEnemigos[1], tEnemigos[2], tEnemigos[3], tEnemigos[4], tEnemigos[5]...

Que por ejemplo si el jugador está entre dos enemigos se blitee el enemigo de arriba primero, luego el jugador y al final el otro enemigo.

Espero haberme explicado mejor ahora, y perdón por hacer preguntas tan básicas, pero es que los punteros y las listas los tengo atravesados y no doy pie con bola.

Saludos!

Al ser del mismo tipo puedes hacer un vector de punteros a esas struct (independientemente del nombre) y ordenar ese vector. Tendrias que cambiar la función de comparación para que trabaje con punteros en lugar de con el propio dato.

Para hacer algo en C lo primero que debes saber bien son los punteros o poco podras hacer.

Entonces el array a crear es el siguiente:
stObjeto *orden[MAXENEMIGOS + MAXARBOLES + MAXHECESDEMONO + ...];

así con todos los elementos que tengan sprites asociados, y rellenarlo de esta forma:

for(i=0; i< MAXENEMIGOS; i++)
orden[i] = &tEnemigos[i];
for(; i< MAXENEMIGOS + MAXARBOLES; i++)
orden[i] = &tArboles[i - MAXENEMIGOS];
for(; i< MAXENEMIGOS + MAXARBOLES + MAXHECESDEMONO; i++)
orden[i] = &tHecesDeMono[i - (MAXENEMIGOS + MAXARBOLES)];
for(; i< MAXENEMIGOS + MAXARBOLES + MAXHECESDEMONO + ...; i++)
orden[i] = &tHecesDeMono[i - (MAXENEMIGOS + MAXARBOLES + MAXHECESDEMONO)];
...

De todas formas, ordenar los sprites sin hacer referencia a la entidad a la que se refieren sería una solución más elegante y eficiente.

Como te han comentado, si necesitas ordenar los sprites de forma rapida, lo mejor es utilizar el procedimiento indexado, donde creas una tabla de indices (punteros, en este caso) que señalan a los elementos
y ordenarlos en funcion de su profundidad.

Pero es raro que tengas que proceder asi, ya que usualmente, los sprites se dibujan por capas y cada capa tiene una prioridad distinta.

Por ejemplo, yo estoy trabajando con 4 capas de sprites: layer 0, son sprites de fondo, que tienen funcion "decorativa" y no intervienen en el juego, mientras que layer 1, son objetos como paredes, suelos, techos, layer 2 serian otros objetos con los que puedo interactuar, como puertas, muebles, escaleras, etc (los personajes, serian layer 2 en mi caso, pero dibujados despues de estos objetos y en el orden de prioridad que yo fijo) y layer 3 serian objetos que se superponen a personajes y objetos.

Asi de esta forma, tu asignarias un dato de layer a tu sprite, que estableceria el momento en el que se debe de dibujar y lo que harias es hacer un bucle que recorriera del layer 0 a layer 3, dibujando solo los elementos correspondientes.

De esta forma, ganas velocidad y te resultara mas facil de trabajar (incluso si por alguna razon, necesitases recurrir a la ordenacion, la informacion de layer te serviria para discriminar que sprites quieres ordenar o no)

El problema de las capas es q para segun q juego no sirve, o no es tan facil como decir capa 2 o capa 3. En un juego de corte lateral sin profundidad es perfecto, objetos al fondo y personajes/enemigos por encima, pero si el juego tiene profundidad y personajes/enemigos son la misma capa ya necesitas ordenar la Y, o aunque sean distintas capas, en cada frame necesitas saber si el sprite tal esta por encima del otro o no

Para una PSP, usar listas enlazadas para ordenar los sprites sólo debería ser necesario si vas a hacer un hell shmup o algún otro juego en el que se muestren una burrada de sprites.

El algoritmo qsort tiene un orden de complejidad de O(n*logn) a O(n*n) dependiendo de la elección del pivote inic¡al, y la implementación en C intenta que en la mayor parte de los casos se escoja el pivote bueno.

Suponiendo que tengas que ordenar unos 100 sprites (ya que no hace falta ordenarlos todos, por ejemplo los sprites de los marcadores van a estar siempre por encima de los demás), en la mayoría de los casos el algoritmo qsort tiene un orden de complejidad O(200). La PSP no debería tener ningún problema en manejar la ordenación de sprites de esta forma.

En definitiva, que en este caso usar listas enlazadas no compensa los dolores de cabeza que te llevas.

Eskematico escribió:El problema de las capas es q para segun q juego no sirve, o no es tan facil como decir capa 2 o capa 3. En un juego de corte lateral sin profundidad es perfecto, objetos al fondo y personajes/enemigos por encima, pero si el juego tiene profundidad y personajes/enemigos son la misma capa ya necesitas ordenar la Y, o aunque sean distintas capas, en cada frame necesitas saber si el sprite tal esta por encima del otro o no

Lo que no entiendo, es lo de ordenar la Y ¿para que cojones sirve eso?

Y lo digo muy en serio.

Si un sprite se solapa con otro, lo que necesitas es conocer la prioridad del sprite (que se la asignas a mano) y no la Y, puesto que ordenar la Y lo unico que haria es asignar una prioridad arbitraria en funcion de la altura y presentar tal vez, un objeto en primer lugar cuando deberia ser en ultimo.

Si dos objetos tienen la misma profundidad, ya deberian estar ordenados para su presentacion y tener establecido quien va primero y recurrir a una ordenacion en funcion de la altura, es una chapuza sin sentido, en mi opinion (pues tanto monta, monta tanto dibujar primero un objeto u otro, si ambos tienen la misma prioridad y si no la tienen, el programador ya decidió que prioridad tenia el grafico en cuestion)

Recurrir a una ordenacion por Y, es como tirar una moneda al aire

Hermes escribió:Lo que no entiendo, es lo de ordenar la Y ¿para que cojones sirve eso?

Imagina el típico pueblo del Final Fantasy VI de la Super Nintendo, con vista cenital.



Ahora imagina los sprites de un protagonista y un NPC, que tienen la misma prioridad respecto al fondo.

Si el protagonista va a hablar con el NPC desde arriba, el sprite del prota debería mostrarse por debajo del del NPC. Pero si decidimos que el protagonista va a hablar con el NPC desde abajo, el sprite del prota debería mostrarse por encima del del NPC, por lo que debemos de hacer un cambio de prioridad de alguno de los dos sprites.

Por lo tanto, en este caso no se pueden ordenar los sprites previamente para su presentación.

Además, aparte de la coordenada Y también hay que tener en cuenta la coordenada X a la hora de ordenar los sprites.

Chano Marrano escribió:

Imagina el típico pueblo del Final Fantasy VI de la Super Nintendo, con vista cenital.



Ahora imagina los sprites de un protagonista y un NPC, que tienen la misma prioridad respecto al fondo.

Si el protagonista va a hablar con el NPC desde arriba, el sprite del prota debería mostrarse por debajo del del NPC. Pero si decidimos que el protagonista va a hablar con el NPC desde abajo, el sprite del prota debería mostrarse por encima del del NPC, por lo que debemos de hacer un cambio de prioridad de alguno de los dos sprites.

Por lo tanto, en este caso no se pueden ordenar los sprites previamente para su presentación.

Además, aparte de la coordenada Y también hay que tener en cuenta la coordenada X a la hora de ordenar los sprites.

Lo que me cuentas es un caso aislado que no requiere la ordenacion de TODOS los sprites y que se trabaja por prioridades perfectamente (en este caso, se compara si colisionan y se establece la prioridad de ambos en funcion de su posicion, que como tu mismo dices, podria depender de X tambien)

Entiendo que en funcion de la posicion de un sprite, en ciertos juegos se cambie la prioridad, pero no que se use la Y como norma para representar todos los sprites, que es lo que me ha parecido entender aqui

En el caso del ejemplo está claro que no haría falta usar un algoritmo de ordenación. Pero puede haber casos en los que colisionen 8 o más sprites con el sprite protagonista, aparte de que también colisionen entre ellos.

En este caso se podrían realizar las ordenaciones a mano, pero es mucho más sencillo y seguro reordenarlos todos de forma automática mediante algún criterio como el de las coordenadas. Además, la pérdida del rendimiento al ejecutar un quicksort pequeño no tiene por qué ser tan grande, así que como decía antes la mejora del rendimiento no compensa los dolores de cabeza .