Rutina Colisión entre sprites

[Artaburu]

Os dejo una revisión de la rutina de colisión de sprites (suponiendo los sprites como rectángulos) que mejora en rendimiento a la que he estado usando hasta ahora (comprobando individualmente cada coordenada de un sprite respecto al otro).

Suponiendo los siguientes datos que definen los sprites:
-sprite 0: x0, y0, a0 (ancho), b0 (alto)
-sprite 1: x1, y1, a1 (ancho), b1 (alto)
La explicación la dejo solo con la coordenada x, con la y es exactamente igual. La rutina lo que hace es mirar si la coordenada x0 del sprite 0 está dentro del rango x1-a0 a x1-a1, si está dentro de ese rango los sprites se tocan, en caso contrario no.
El rango x1-a0 a x1-a1 sería el rango límite juntando los dos sprites hasta que se rocen en coordenada x así que se mira si la x0 está en ese rango, en cuyo caso habría colisión. A ver si el siguiente esquema ayuda a entender la idea:

Colisión:
x0>=(x1-a0) AND x0<=(x1+a1)
O visto de otro modo, no hay colisión si:
x0<(x1-a0) OR x0>(x1+a1)
Que es lo que mira la rutina en realidad, y normalmente será más rápido (y habitual) mirar si no colisionan que si lo hacen.

Código: Seleccionar todo

;sprite 1 -> IX
;ix+8: x1
;ix+9: y1
;ix+2: ancho sprite 1
;ix+3: alto sprite 1

;sprite 2 -> IY
;iy+8: x2
;iy+9: y2
;iy+2: ancho sprite 2
;iy+3: alto sprite 2

     Ld a, (ix+8) ;A=xo
     sub (iy+2) ;x0-a1
     ld d,a
     jp nc,s0012
     xor a
s0012:
     cp (iy+8) ;x1<x0-a1? está fuera
     jp z, s0013 ;x1<A FUERA
     jp nc, no_collision ;x1<A FUERA
s0013:
     ld a,d
     add (iy+2)
     add (ix+2) ;xo+a0
     dec a
     cp (iy+8) ;x1>xo+a0? está fuera
     jp c, no_collision ;x1>A+a0+a1 FUERA

     Ld a, (ix+9) ;A=yo
     sub (iy+3) ;y0-b1
     cp (iy+9) ;y1<A? está fuera
     jp nc, no_collision ;x1<A FUERA
     add (iy+3)
     add (ix+3) ;Y=y0+b0
     dec a
     cp (iy+9) ;y1>y0+b0? está fuera
     jp c, no_collision
collision:
     scf
     ret
no_collision:
     xor a
     ret

[ronaldo]

Genial, Raúl . Creo que es una parte del código en la que todo el mundo tiene que pararse a pensar e implementar muchas veces.

Para complementar tu código y explicación, justo tengo un vídeo explicando en clase las proyecciones de los rectángulos y el razonamiento de comprobar la no-colisión. Creo que puede ayudar a entender tu rutina y lo que explicas en tu boceto. En la misma lista de reproducción tengo algunos vídeos más sobre mejora del rendimiento de comprobación de colisiones por estadística de ejes, y algunos detalles sencillos sobre implementación (no optimizado, pues es simplemente para construir la implementación por primera vez, entendiendo lo que se hace):



Todavía está pendiente trabajar en el tema de particionamiento del espacio para evitar calcular colisiones de todos-contra-todos cuando tenemos muchos objetos en el mundo.

[Pentapolín]

Todo esto me resultará de gran ayuda en mi aprendizaje del ensamblador.
Muchas gracias por compartir vuestra sabiduría

[ronaldo]

Os dejo una revisión de la rutina de colisión de sprites (suponiendo los sprites como rectángulos) que mejora en rendimiento a la que he estado usando hasta ahora (comprobando individualmente cada coordenada de un sprite respecto al otro).

Le he dado una vuelta a tu rutina con algún cambio en la forma en que se hacen las matemáticas y he hecho una versión que parece mejorarla un poco. La mejora depende de si la versión que he hecho te sirve, en la forma en que hace las comprobaciones, sobre todo cuando considera contacto en 1 solo pixel/byte (según se use). Por otra parte, esta nueva versión devuelve únicamente un estado del bit de acarreo (NC para colision, C para no-colision). No usa los registros para devolver nada.

He hecho un programilla con el que es muy fácil testear ambas en WinAPE. Sólo hay que copiarlo, poner un breakpoint en el call y usar el temporizador de WinAPE + F8 para ver lo que tarda en cada caso cada rutina. He hecho unas pruebas con distintos casos y ambas funciones parecen funcionar bien, con la única diferencia de algunos casos límite de 1 pixel/byte de colisión, como decía antes.

En la versión nueva también he puesto comentarios respecto a los giros matemáticos que he usado. Espero que se entiendan. Si hay alguna duda, preguntadme y veo de explicarlos mejor. Ahí os dejo todo:

Código: Seleccionar todo

;; sprite 1 -> IX
;; ix+8: x1
;; ix+9: y1
;; ix+2: ancho sprite 1
;; ix+3: alto sprite 1

;; sprite 2 -> IY
;; iy+8: x2
;; iy+9: y2
;; iy+2: ancho sprite 2
;; iy+3: alto sprite 2
org &4000
run start

;;------------------------------------------------------------------------
;; TEST DATA: 2 Rectangles defined according to defined entity structure
;;------------------------------------------------------------------------
rect_1:
ds 2 ; -----
db 2, 3 ; w, h
ds 4 ; -----
db 1, 1 ; x, y

rect_2:
ds 2 ; -----
db 2, 3 ; w, h
ds 4 ; -----
db 1, 1 ; x, y

;;------------------------------------------------------------------------
;; MAIN TEST PROGRAM
;;------------------------------------------------------------------------
start:
ld ix, rect_1
ld iy, rect_2
call check_newv
jr c, nada ;; No_colision
coll:
ld a, &FF ;; RED: Collision
db &DA ;; False Carry-jump
nada:
ld a, &0F ;; BLUE: No-Collision

ld (&C000), a ;; Draw
infinite:
jr infinite


;;-----------------------------------------------------------------------
;; Check collision between IX and IY rectangles
;; Costs: [22, 33, 53, 63]us (from 1 to 4 checks)
;; -> Collision costs 63us
;; -> No collision from 22us to 63us
;; RETURN:
;; (NC) Collision: Return with Carry flag off
;; (C) No-Collision: Return with Carry flag on
;;-----------------------------------------------------------------------
check_newv:
;;------------------------
;; X1 X2
;; [--A1--] [--A2--]
;;------------------------
;; if (X1 + A1 < X2 + 1) then no_collision
;; 0 < (X2 + 1) - (X1 + A1)
;; 0 > (X1 + A1) - (X2 + 1)
ld a, (ix+8) ; [5] A = X1
ld c, a ; [1] C = X1
add (ix+2) ; [5] A = X1 + A1
ld b, (iy+8) ; [5] B = X2
inc b ; [1] B = X2 + 1
sub b ; [1] A = (X2 + 1) - (X1 + A1)
ret c ; [2/4] If Carry, no_collision

;; A = X2 + 1 - X1 + A1
;; B = X2 + 1
;; C = X1
;;------------------------
;; X2 X1
;; [--A2--] [--A1--]
;;------------------------
;; if (X2 + A2 < X1 + 1) then no_collision
;; 0 < (X1 + 1) - (X2 + A2)
;; 0 > (X2 + A2) - (X1 + 1)
inc c ; [1] C = X1 + 1
ld a, b ; [1] A = X2 + 1
add (iy+2) ; [5] A = X2 + A2 + 1
dec a ; [1] A = X2 + A2
sub c ; [1] A = (X2 + A2) - (X1 + 1)
ret c ; [2/4] If Carry, no_collision

;;------------------------
;; Y1 Y2
;; [--H1--] [--H2--]
;;------------------------
;; if (Y1 + H1 < Y2 + 1) then no_collision
;; 0 < (Y2 + 1) - (Y1 + H1)
;; 0 > (Y1 + H1) - (Y2 + 1)
ld a, (ix+9) ; [5] A = Y1
ld c, a ; [1] C = Y1
add (ix+3) ; [5] A = Y1 + H1
ld b, (iy+9) ; [5] B = Y2
inc b ; [1] B = Y2 + 1
sub b ; [1] A = (Y2 + 1) - (Y1 + H1)
ret c ; [2/4] If Carry, no_collision

;; A = Y2 + 1 - Y1 + H1
;; B = Y2 + 1
;; C = Y1
;;------------------------
;; Y2 Y1
;; [--H2--] [--H1--]
;;------------------------
;; if (Y2 + H2 < Y1 + 1) then no_collision
;; 0 < (Y1 + 1) - (Y2 + H2)
;; 0 > (Y2 + H2) - (Y1 + 1)
inc c ; [1] C = Y1 + 1
ld a, b ; [1] A = Y2 + 1
add (iy+3) ; [5] A = Y2 + H2 + 1
dec a ; [1] A = Y2 + H2
sub c ; [1] A = (Y2 + H2) - (Y1 + 1)
ret ; [3] If Carry, no_collision
; If No-Carry, collision
;; Collision: Return with Carry flag off (NC)
;; No-Collision: Return with Carry flag on (C)


;;-----------------------------------------------------------------------
;; Check collision between IX and IY rectangles
;; First Version of Artaburu
;; Measured Costs: [29, 50, 64, 68]us
;;-----------------------------------------------------------------------
check_arta:
ld a, (ix+8) ; [5] A=xo
sub (iy+2) ; [5] x0-a1
ld d, a ; [1]
jp nc, s0012 ; [3]
xor a ; [1]
s0012:
cp (iy+8) ; [5] x1<x0-a1? está fuera
jp z, s0013 ; [3] x1<A FUERA
jp nc, no_collision ; [3] x1<A FUERA
s0013:
ld a, d ; [1]
add (iy+2) ; [5]
add (ix+2) ; [5] xo+a0
dec a ; [1]
cp (iy+8) ; [5] x1>xo+a0? está fuera
jp c, no_collision ; [3] x1>A+a0+a1 FUERA

ld a, (ix+9) ; [5] A=yo
sub (iy+3) ; [5] y0-b1
cp (iy+9) ; [5] y1<A? está fuera
jp nc, no_collision ; [3] x1<A FUERA
add (iy+3) ; [5]
add (ix+3) ; [5] Y=y0+b0
dec a ; [1]
cp (iy+9) ; [5] y1>y0+b0? está fuera
jp c, no_collision ; [3]
collision:
scf ; [1]
ret ; [3]
no_collision:
xor a ; [1]
ret ; [3]

Por cierto: no tengo ni idea de porqué, pero la etiqueta [ code ] del foro se me come los espacios y los tabuladores en lugar de dibujarlos. Así el código sale hecho unos zorros. Adjunto una versión en documento de código fuente para que sea más cómodo de descargar, leer y usar.

check_collisions_amstrad.zip

Rutina de comprobación de colisiones entre rectángulos en Z80 (Amstrad).
Function to check collisions between two rectangles on Z80 (Amstrad).

(1.42 KiB) Descargado 47 veces

[Artaburu]

Gracias Fran

La voy a estudiar y la usaré si me cuadra. No tengo muy claro a qué te refieres en contacto en un solo byte, pero lo entenderé al mirar tu rutina.

[Artaburu]

Pues va perfecta para lo que necesito así que, con tu permiso, paso a utilizarla a partir de ahora que es más rápida, compacta y por lo tanto, óptima.
La meteré también en la cpcrslib si das tu OK

[ronaldo]

Pues va perfecta para lo que necesito así que, con tu permiso, paso a utilizarla a partir de ahora que es más rápida, compacta y por lo tanto, óptima.
La meteré también en la cpcrslib si das tu OK

Faltaría más. Puedes usarla donde quieras y cómo quieras. De hecho, parte de la rutina es tuya, porque la he elaborado a partir de la primera que has pasado

En caso de necesitarlo, puedes hacerla aún más compacta cuando el espacio importa: las comprobaciones de eje X e Y son iguales salvo por el desplazamiento de X e Y. Con sólo las 2 primeras comprobaciones puedes hacer las 4 de esta forma:

Código: Seleccionar todo


check_collision_both_axis:

;; Check X axis
ld ix, rect_1
ld iy, rect_2
call check_one_axis
ret c ;; No collision

;; Check Y axis
inc ix
inc iy
call check_one_axis
ret c ;; No collision

collision:
;; Código para colision
ret

Como los valores de Y y H están justo 1 byte después de X y W, basta con usar el código de las 2 primeras condiciones de la rutina y llamar 2 veces, con ese INC IX e INC IY que hacen que la segunda llamada coja Y y H. Así la rutina quedaría casi en la mitad de espacio. También eso tendría la ventaja de poder comprobar a veces el eje X primero y otras el eje Y, lo que en algunos juegos puede ganar si descartas estadísticamente antes por un eje u otro en según que partes del juego.

De hecho, esto último es importante. Es bueno modificar la rutina para que compruebe primero X o Y en función del tipo de juego. Siempre se debe comprobar primero el eje donde se colisiona menos estadísticamente, así se descarta más rápido y se ahorran muchos ciclos. En un juego tipo AMC, por ejemplo, interesa comprobar primero X y luego Y, mientras que en un Mission Genocide, interesa mirar primero Y y luego X.

[Artaburu]

Lo de optimizar rutinas resulta adictivo, he probado y me daba no colisión en un caso de estar en coordenadas negativas (en mi caso es posible porque tengo sprites cortados por la izquierda). Si no me equivoco, con este juego de datos tu rutina no detecta colisión:

Código: Seleccionar todo

;;------------------------------------------------------------------------
;; TEST DATA: 2 Rectangles defined according to defined entity structure
;;------------------------------------------------------------------------
rect_1:
ds 2 ; -----
db 2, 2 ; w, h
ds 4 ; -----
db -1, 7 ; x, y

rect_2:
ds 2 ; -----
db 2, 2 ; w, h
ds 4 ; -----
db -2, 7 ; x, y

Código: Seleccionar todo

check_arta:
ld a, (iy+8) ;[5]
ld b,a ;[1]
dec a ;[1]

sub (ix+8) ;[5]
add (iy+2) ;[5]
ret m ;[4/2] RET NO COLIS
;[21]

ld a,(ix+8) ;[5]
add (ix+2) ;[5]
sub b ;[1]
dec a ;[1]
ret m ;[4/2] RET NO COLIS
;[16]

ld a, (iy+9) ;[5]
ld b,a ;[1]
dec a ;[1]
sub (ix+9) ;[5]
add (iy+3) ;[5]
ret m ;[4/2] RET NO COLIS
;[21]

ld a,(ix+9) ;[5]
add (ix+3) ;[5]
sub b ;[1]
dec a ;[1]
;ret m ;[4/2] RET NO COLIS
ret ;[3]
;[15]

;[73]

[ronaldo]

La rutina está diseñada considerando todos los números como positivos. Aún así, funciona con positivos y negativos. El caso en el que falla, el que has puesto, es porque uno de los números es positivo y otro negativo en esta operación: ;; 0 > (X1 + A1) - (X2 + 1). Al ser X1 + A1 = 1 y X2 + 1 = -1, hace una operación 1 - (-1) = 2, con resultado correcto pero con acarreo activado.

Se pueden hacer modificaciones para calcular las colisiones teniendo en cuenta esos casos. Sin embargo, mi preferencia es trabajar siempre en positivo. Si las coordenadas pueden estar fuera de la pantalla, lo que haría es un cambio de coordenadas desplazando el eje. Es decir, consideraría las coordenadas de los personajes en un rango [0 - 100] en lugar de [0 - 80], por ejemplo. En este caso [0-10] sería fuera de la pantalla por la izquierda y [90-100] fuera de la pantalla por la derecha. Con esto se pueden hacer todos los cálculos siempre en positivo, lo que simplifica la lógica en muchos casos.

A la hora de dibujar, sólo hay que restar 10 a las coordenadas para deshacer la traslación y así pintar en coordenadas de pantalla.

[LexSparrow]

Estos hilos son los que molan. Gracias por compartir estas cosas en abierto

[Artaburu]

La rutina está diseñada considerando todos los números como positivos. Aún así, funciona con positivos y negativos. El caso en el que falla, el que has puesto, es porque uno de los números es positivo y otro negativo en esta operación: ;; 0 > (X1 + A1) - (X2 + 1). Al ser X1 + A1 = 1 y X2 + 1 = -1, hace una operación 1 - (-1) = 2, con resultado correcto pero con acarreo activado.

Se pueden hacer modificaciones para calcular las colisiones teniendo en cuenta esos casos. Sin embargo, mi preferencia es trabajar siempre en positivo. Si las coordenadas pueden estar fuera de la pantalla, lo que haría es un cambio de coordenadas desplazando el eje. Es decir, consideraría las coordenadas de los personajes en un rango [0 - 100] en lugar de [0 - 80], por ejemplo. En este caso [0-10] sería fuera de la pantalla por la izquierda y [90-100] fuera de la pantalla por la derecha. Con esto se pueden hacer todos los cálculos siempre en positivo, lo que simplifica la lógica en muchos casos.

A la hora de dibujar, sólo hay que restar 10 a las coordenadas para deshacer la traslación y así pintar en coordenadas de pantalla.

Sí, la verdad es que operar siempre con números enteros positivos es lo ideal, hasta ahora yo tenía una solución como la que indicas, sumando 10, pero en lugar de en el dibujado lo hacía en la colisión. En el dibujado me resultaba más sencillo detectar el corte en 0 para calcular desplazamientos aprovechando que la diferencia con 0 me da el ancho/alto a cortar, por ejemplo.

Y, precisamente mirando el corte con el eje de coordenadas de un sprite vi que podía trasportarlo a la colisión entre sprites optimizando la forma de calcular (a fin de cuentas, la colisión contra un eje fijo es una particularización de colisión entre sprites).

[Fran123]

Refloto,

Al actualizar la posición (vértice x1,y1) de una entidad que voy a tener en cuenta para mirar colisiones, calculo las coordenadas del vértice opuesto (x2,y2) con lo que la suma ya la dejo hecha.