Ayuda para mejorar rutinas: Guardar lista de coordenadas.

[Artaburu]

Buenas,

Tengo algunas rutinas que cada cierto tiempo retomo para ver si puedo rascar unos bytes o mejor aún, unos ciclos de ejecución. De algunas de ellas he utilizado diferentes variantes que a veces no suponen mejora pero sí un triunfo intelectual por abordar el problema de otro modo.

El caso es que me gustaría encontrar otros puntos de vista o ideas para abordar estas rutinas/funciones ya que creo que yo ya estoy contaminado y siempre voy a acabar a las mismas soluciones. Esto es como un brainstorming para buscar ideas, no os cortéis. Igual la solución propuesta no es buena pero la idea de fondo es excelente y se puede desarrollar. De hecho, algunas mejoras que suelo aplicar en algunas rutinas vienen de ideas de otras que he leído que, aunque básicas (o complejas) no se me había ocurrido que podrían funcionar.

Para empezar, una sencilla. Se trata de guardar una lista de coordenadas (x,y) comprobando que no haya valores duplicados. No importa que los valores estén ordenados o desordenados, es irrelevante.


Los valores a guardar llegan en el registro DE.

Mi propuesta es la siguiente:
Usa una tabla “_tabla_de_coordenadas” en la que se marca el final de los datos con el byte &FF (no puede haber una coordenada con este valor)

Código: Seleccionar todo

_tabla_de_coordenadas:
db 1,2
db 3,4
db 8,9
db &FF

La rutina recorre la tabla hasta encontrar el valor &FF, para añadir las coordenadas nuevas. Cada valor que va encontrando antes de llegar a este &FF los compara con las coordenadas.
Según el ejemplo anterior primero encuentra el valor 1, que no es &FF así que lo compara con la coordenadax (D). Si no coincide sigue leyendo porque no habrá coincidencia. Si coincide comprueba el siguiente byte con la coordenaday (E). Si no coincide, sigue recorriendo la tabla. Si coincide termina porque la pareja de coordenadas ya existe en la tabla y no se guardan duplicados.

Resetear la tabla es fácil, se pone el valor &FF en el primer byte.

Recorrer la tabla para leer las coordenadas en una fase posterior también es sencillo, basta leer los pares de bytes hasta que encuentra que el primer byte es &FF que marca fin de la tabla.

Código: Seleccionar todo


LD D, coordenadax
LD E, coordenaday

rutina_añadir_coordenadas
LD HL,tabla_de_coordenadas ; Puedo guardar la tabla de coordenadas en una posición determinada para poder usar INC L en lugar de INC HL
bucle_recorrido_tabla_coordenadas:
LD A,(HL)
CP &FF
JP Z, add_coordenadas ;Solo se incorpora al llegar al final de los datos de la tabla
CP D
JP Z, comprobar_segundo_byte
INC HL ;inc l
INC HL ;inc l
JP bucle_recorrido_tabla_coordenadas
comprobar_segundo_byte:
INC HL
LD A,(HL)
CP E
RET Z ;los dos bytes son iguales, mismas coordenadas. No se añaden y se sale de la rutina.
INC HL ;inc l
JP bucle_recorrido_tabla_coordenadas

add_coordenadas:
LD (HL),d
INC HL
LD (HL),e
INC HL
LD (HL), &FF ;End of data
RET

[Mode 2]

¡Buenas crack!

Voy a decir una tonteria seguramente pero bueno. En un principio, lo que has puesto me parece biien pero me pregunto: ¿Con qué asiduidad usas esta rutina? ¿Cuanto puede llegar a crecer la lista de coordenadas? ¿Se suele repetir mucho una misma coordenada X?
Te lo comento porque dependiendo de la respuesta quizás sería óptimo que en alguna fase no crítica de la ejecución del juego ejecutases algún método de ordenación de la lista (lo harías por su primera coordenada) con lo que ganarías rapidez en una posterior busqueda (que ya no debería ser lineal) que es lo quizás precisamente demandas.

Saludacos.

De algunas de ellas he utilizado diferentes variantes que a veces no suponen mejora pero sí un triunfo intelectual por abordar el problema de otro modo.

¡Que gran verdad!

[Artaburu]

Lo que preguntas tiene mucha lógica, no es ninguna tontería.
Es una rutina que se ejecuta muchas veces en cada ciclo del juego ya que lo que hace es guardar los tiles que los sprites pisan. Cada sprite puede tener una media de 12 tiles que son 12 coordenadas y tendríamos 6 sprites de media. Estamos en 72 coordenadas en el peor de los casos aunque si hay sprites que se cruzan, serán menos y se repetirán.
Ordenar no es necesario porque no aporta nada y creo que consume tiempo.

[pacomix]

Mmmmh... Para el CPC bros uso un método más sencillo. En lugar de guardar las coordenadas y todo lo que implica luego buscar, comparar y recuperar el tile lo que hago es tener un buffer donde voy almacenando directamente el índice del tile. (X + (Y * HORIZ_TILES))
Luego simplemente para saber si dicho tile ha sido agregado a la lista puedes hacer dos cosas:
1.- Si tienes 128 o menos tiles puedes usar el primer bit para marcarlo como agregado y con un simple AND ya lo tienes.
2.- Usa un pequeño buffer de (HORIZONTAL_TILES * VERTICAL_TILES) bits.

Más rápido que lo que dices.
Venga! Otras alternativas!!!!!


Enviado desde mi iPhone utilizando Tapatalk

[Artaburu]

Buena idea, pero en mi caso no se si me compensa porque tengo 512 tiles en la pantalla.

De todas formas, a ver si entiendo bien tu planteamiento.
Tu buffer siempre tiene todos los índices solo que cuando sabes que lo tienes que actualizar le marcas el bit 7, por ejemplo.
No te preocupan los duplicados porque no ocurren y ademas buscarlos seria un gasto mayor que "re-marcar" un índice.
Para la restauración tienes que recorrer todos los indices y ver si toca restaurar o no.

Esta parte es la que a priori me desencaja a mí porque tendría que recorrer una tabla de 512 registros de 2 bytes, pero voy a hacer unos cálculos por si me compensa a la larga. Para pocos tiles claramente no pero igual para muchos sí.

[Artaburu]

Le he dado otra vuelta y creo que no entendido bien tu solución, pacomix. Se me escapa algo.
Si guardas el índice veo dos opciones, que tengas una tabla de indices en la que dices si está marcado o no. O una tabla en la que vas añadiendo indices según aparezcan, pero revisando que no se haya introducido ya previamente.
Voy bien?

[pacomix]

Más o menos. Estoy en el curro pero con el móvil. Cuando llegue a casa te lo posteo al detalle. Cuantos tiles diferentes usas? O sea... de cuantos tiles se compone el tileset?


Enviado desde mi iPhone utilizando Tapatalk

[Artaburu]

Más o menos. Estoy en el curro pero con el móvil. Cuando llegue a casa te lo posteo al detalle. Cuantos tiles diferentes usas? O sea... de cuantos tiles se compone el tileset?


Enviado desde mi iPhone utilizando Tapatalk

Tranqui no hay prisa. Estoy igual que tu

Tiles diferentes pueden ser 255 pero en el proyecto que tengo entre manos se queda en unos 120

[ronaldo]

La alternativa que propone pacomix de crear un array de bits sería la primera solución que propondría implementar. Es muy sencilla de hacer y será mucho más rápida que almacenar y buscar coordenadas. Además, puedes añadir 2 bytes para almacenar los desplazamientos del primer y último byte distintos de 0 en el array.

La idea sería se resumiría así:

• Crear un array de tantos bits como tiles tengas en pantalla. Por ejemplo, para 40x30 tiles necesitarías 1200 bits = 150 bytes.
• Poner todos los bits a 0.
• Cada vez que un tile resulta tocado, poner el bit correspondiente a 1, con un OR. (Si es el tile (10,20), 20*40+10 = 810. Bit 810 = 1).
• No necesitas verificar si ya ha sido tocado antes o no, porque es más lento que ponerlo a 1 sin más. Si ya estaba a 1, a 1 se quedará igualmente.
• Puedes mejorar la rutina para poner varios bits seguidos a 1 de una sola tacada. También puedes hacer una rutina para "dibujar un cuadrado de bits" sobre el array. Sería como un putsprite sobre el array, pintando un cuadrado. Esto sería mucho más rápido.
• Restaurar los tiles sería coger los 1s y repintar en pantalla, a la vez que se van dejando a 0 en el array. Aquí es donde veo útiles los desplazamientos al primer y último byte distintos de 0 en el array de bits. Así el bucle de repintado no perdería tiempo con los 0s iniciales y finales, que son potencialmente muchos.

En CPCtelera hay rutinas de manejo de arrays de bits con código muy optimizado en ensamblador. Te pueden valer como punto de partida. Además, puedes incluso mejorarlas si presupones un array alineado en memoria y que no supere los 256 bytes. Tienes el código aquí:

• cpct_setBit
• cpct_getBit

Si quieres podemos elaborar un ejemplo y vemos cómo queda.

[Artaburu]

He empezado ha preparar una rutina en base a lo que habeis comentado pacomix y tu, Ronaldo. Por ahora me he centrado en usar bytes en lugar de bits, aunque va a ocupar 512bytes el mapa en lugar de 64. La gestión de bits es algo más compleja y lenta, aunque tengo que ver si compensa por el ahorro de memoria.

Esta tarde he hecho unos cálculos rápidos y pinta bien para números altos de tiles a restaurar. Para 10 o 12 no merce la pena pero para 40 o 50 sin duda que sí.

Ya os mostraré los resultados.

Y gracias porque me habeis ayudado mucho

[ronaldo]

Usar un array de bits en lugar de bytes es lento, sí, pero no creas que es muy lento. Con la rutina que te he puesto en el enlace (cpct_setBit), tendrías un coste de 53 ciclos por cada vez que hagas set. En igualdad de condiciones, con un array de bytes tardarías 10 ciclos (LD DE, #array : ADD HL, DE : LD A, #1 : LD (HL), A).

Esto, teniendo en cuenta que cpct_setBit no está optimizada para alineamiento en memoria, y que no está pensada para hacer el "putsprite" como te había comentado. Si se hace una rutina similar que rellene un cuadrado de bits en la matriz, probablemente el coste no sería más del doble de hacer lo mismo en bytes, con la ventaja de ahorrar 7/8 de memoria.

De todas formas, empezar haciéndolo con bytes es una buena idea, porque ayuda a ir reflexionando mucho más sobre el método y puede aportar muchas nuevas formas e ideas .

[Artaburu]

No descarto acabar montando el sistema con array de bits pero como bien dices, hacerlo con bytes es más fácil para entender.... Y depurar, que estas cosas consumen mucho tiempo humano

Más que la puesta a 1, me preocupa la lectura porque son muchos bits a comprobar cada vuelta del bucle aunque el array de bits tiene la ventaja de que puedo analizar bloques de 8, si el byte es 0 no hace falta que analice cada bit del byte.

Tengo un buen entretenimiento para unos días y visto el buen resultado creo que luego iré poniendo otras rutinas que creo que se pueden mejorar

[pacomix]

A ver si me explico mejor desde un teclado esta noche. Si usas 128tiles o menos pues te queda libre un bit que puedes usar para marcarlo como pintado o no y así agregarlo o no a la lista de tiles a pintar. Claro que tendrás que cambiar tu rutina para que le aplique la mascara correspondiente a la hora de recuperar el índice de tiles z


Enviado desde mi iPhone utilizando Tapatalk

[pacomix]

Nada. Que voy justo de tiempo. A ver si lo explico bien desde el móvil y no se me borra el mensaje.

En tu caso.
TILE_MATRIX Es un array de X * Y bytes cuyo contenido será el índice del tile a dibujar en pantalla. Si tienes 128 tiles estás usando máximo 7 bits por lo cual podrías usar el que te sobra para marcarlo como agregado o no a la lista de dibujado.
TILE_PAINT Una pila donde iras almacenando el índice del array TILE_MATRIX a dibujar.

Crea una rutina que recabe los tiles a dibujar haciendo lo siguiente:
- Por cada sprite dame que tiles toca. (INDICES DE TILE_MATRIX)
- por cada tile
- si el bit 7 no esta seteado
- setea bit7 del TILE de TILE_MATRIX
- Agrega el índice del TILE en TILE_PAINT (índice de TILE_MATRIX)

Rutina de dibujado:
Por cada TILE_PAINT:
- Resetea el bit7 del índice del TILE en TILE_MATRIX
- Vuelca el TILE en pantalla

Ya está. Tal y como lo tienes ahora es la forma más sencilla y que menos espacio te ocupará en memoria aunque haya que escribir un pelín más de código.

Si tienes más de 128 tiles entonces necesitarás claramente un bit array aunque puedes usar bytes y así puedes almacenar más datos de cada TILE tal y como si es plataforma, si ha sido pisado x un enemigo, si es una puerta, o lo que se te ocurra.

En mi caso es un poco diferente ya que tengo 32 tiles y 4 bits restantes donde almacenó si el TILE hay que pintarlo dado la vuelta, si es obstáculo vertical, si es obstáculo horizontal y si ha sido o no agregado para pintar.

Esta información también te la puedes organizar de forma diferente reservando un rango de tiles específico para cada tipo y usando máscaras para extraer también la info.

Espero haberte sido de ayuda.

@Ronaldo le echaré un vistazo a la rutinas de bits que dices ya que me pueden ser muy útiles si ya las tienes optimizadas:)

Saludos!


Enviado desde mi iPhone utilizando Tapatalk

[Artaburu]

Lo tengo claro, Pacomix. Algo así voy a intentar montar. Tengo que retocar bastantes cosas pero creo que es el buen camino.