Hello all !!

With 2 options and 1 missile, the ship from spacemanbow can shoot 10 bullets.
To calculate if a bullet hits an enemy 4 comparisons have to be made
1 and 2: check if bullet is within x range of enemy
3 and 4: check if bullet is within y range of enemy
This means that for each enemy 4 (comparisons)*10 (bullets)=40 cp's have to be processed.
and for 10 enemies this is 400 cp instructions.
This makes the game go slooooooooooooooow. (relatively)

Now, I have not worked with the sprite collision flag (in s#0, bit 5)
s#3 - s#6 can be used to readout x,y coord. of colliding enemy,

But how do I know which enemy collides with which enemy?

How can I update/speedup my routine using the sprite collision flag??

1) If the flag in s#0, bit 5 is OFF there is no collision, so you can skip all the collision detection routine at all

2) If s#3 - s#6 coordinates are far from your main sprite you can skip collision detection routine for your ship: you do only ONE single TEST!!! Otherwise you are dead take your time for scanning the list :-)


3) If s#3 - s#6 coordinates are far from your bullets you can skip collision detection routine for your enimies: consider each bullet idividually, if it is far from s#3 - s#6, skip it and go to the next bullet. In this way you can do one single TEST per active bullet instead of comparing each bullet with each enimy!!! Only bullets that fall within s#3 - s#6 range have to be compared with the list of the active enimies.

Do you see the gain ?

Quote:

To calculate if a bullet hits an enemy 4 comparisons have to be made 1 and 2: check if bullet is within x range of enemy 3 and 4: check if bullet is within y range of enemy

Four comparisons are only the worst case senario.

How are you comparing things? You know it is faster to check if there is no
hit then checking there is one. Considering you making a horizontal shooter
and thus most enemies come form the right with the player mostly on the left,
the first comparison could be one checking if the enemy is on the right side of
the player, if so no hit and just one check was needed.
So choose your order with care.
But you probably already knew that.

Both is better.... doing collision calculation only if there is a VDP sprite collision

Well... we all must keep in mind that even in case of a collision the checking process must
still not exceed the availeble time, we don't want slowdowns now do we?
But pixel perfect detection, right?

a "frame" type of detection is better than pixel detection

first you only needs to detect the player and bullet or whatt you place in game

no enemies collides normaly

so, the question is: will the player craft be destroyed just because a bullet collides with the fire/smoke of the propulsion of the craft?

Konami's general secret behind this...

• enemy bullets are sprites
• player bullets are patterns
• player is built up out of sprites
• enemies are patterns

if sprite collision, then it's most likely the player that got killed.

No need to check ALL objects each interrupt. u might spread it. when framerate=2/50 and each interrupt is 1/50 you'll already have 2 interrupts possible to check collision. you can even do complete collision test over 3 or 4 interrupts. WHAT is your ship hits a bullit the first int and will be checked untill the 2nd or 3th int after that. imagen; can you move THAT fast to evade the bullit? prolly not, it's on a collision course and it WILL hit ya ass.

Secondly, like GhostP said. 4 compares per object is the WORST case scenario.
When X is already of scale you don't need further checking.

So all and all, it's not THAT time consuming. just be clever and split up tablebrowsing. look for techniques to to such.
I don't think using the VDP collision check is worth it... dunno. never a big fan of that crappy sjizzle.

Using HW can skip lot of comparisons.

Before going further let's start with simple building blocks.

----------------
We build a square frame around our sprites:
Assume (x0,y0) be the coordinates on the screen of our main sprite:

(x0,y0) (x0+15,y0) (x0,y0+15) (x0+15,y0+15)
are the vertex of the frame.

This is the case of 16x16, but size can change be different,
e.g. for bullets the size could be 16x4 and the box became

(x0,y0) (x0+15,y0) (x0,y0+3) (x0+15,y0+3)

For of larger sprites you could have 16x32
(x0,y0) (x0+15,y0) (x0,y0+31) (x0+15,y0+31)

etc.

The n-th enemy is in a frame with coordinates
(xn,yn) (xn+15,yn) (xn,yn+15) (xn+15,yn+15)

The easiest case is when all the enemies have the same
size (16x16 in my case, )

----------------

We call (xc,yc)

the content of s#3 - s#6 suitably corrected (crappy bloody VDP: I remember
there are –12 and –8 correction factors, moreover I do not remember if (xc,yc)
are the coordinates of the first overlapping pixel of the two colliding sprites or
what else….)

First you need to check s#0 bit 5


If
s#0 bit 5 ==0
then
no collision
else if
x0+15>= xc >=x0 and y0+15>= yc >= y0
then
main sprite collision: look for which enemy collided


----------------

How to look for which enemy collided:


Assuming enemy and main sprites of the same dimension (16x16)

if
xn+15>= x0 >=xn and yn+15>= y0 >= yn
or if
xn+15>= x0+15 >=xn and yn+15>= y0 >= yn
or if
xn+15>= x0+15 >=xn and yn+15>= y0+15 >= yn
or if
xn+15>= x0 >=xn and yn+15>= y0+15 >= yn
then
we have for sure a collision between sprite in (x0,y0) and sprite in (xn,yn)

The same condition, in case of main sprite 16x16 and of enemies 32x64 become:

if
xn+31>= x0 >=xn and yn+63>= y0 >= yn
or if
xn+31>= x0+15 >=xn and yn+63>= y0 >= yn
or if
xn+31>= x0+15 >=xn and yn+63>= y0+15 >= yn
or if
xn+31>= x0 >=xn and yn+63>= y0+15 >= yn
then
we have for sure a collision between sprite in (x0,y0) and sprite in (xn,yn)

----------------

We need to repeat the test for each active enemy until we find the right one.

If sprites are sorted by coordinates (as GhostP suggested) we can scan
the list using binary bisection algorithm that needs log (N) comparisons instead
of full search that needs N comparisons !!!

Let’s skip this aspect for the moment and let’s focus on a necessary building block:
The implementation of the simple test:

XN+DXN>= X >=XN

We want a base routine which returns

Z if XN+DXN>= X >=XN,
NZ otherwise

From this routine it is easy to get the general test

if
xn+DXN>= x0 >=xn and yn+DYN>= y0 >= yn
or if
xn+DXN>= x0+DX0 >=xn and yn+DYN >= y0 >= yn
or if
xn+DXN>= x0+DX0 >=xn and yn+DYN >= y0+DY0 >= yn
or if
xn+DXN>= x0 >=xn and yn+DYN >= y0+DY0 >= yn
then
we have for sure a collision between sprite in (x0,y0) and sprite in (xn,yn)

----------------


We want a base routine which returns

Z if XN+DXN>= X >=XN,
NZ otherwise

Here we have the main:
….
ld b, X
ld c, XN
ld d, DXN
call test
….

here we have the routine

; TEST: in b=X, c=XN, d=DXN
; Z if XN+DXN>= X >=XN,
; NZ otherwise

test:

ld a, c
add a, d
cp b ; compare A with B, if A>=B, carry=0; otherwise if A<B, carry=1 and zero = 0
ret c ; if XN+15 < X return flag NZ
; continue if XN+15 >= X
ld a, b
cp c
ret c ; if X < XN return flag NZ

; here we have (X>=XN) and (XN+DXN>=XN)
xor a
ret ; return flag Z

Maybe this thread might help you as well with sprite collision stuff.

@Bifi: Thanks! but I feell that we can continue with this tread

----------------

Now we want a base routine which

if
xn+DXN>= x0 >=xn and yn+DYN>= y0 >= yn
or if
xn+DXN>= x0+DX0 >=xn and yn+DYN >= y0 >= yn
or if
xn+DXN>= x0+DX0 >=xn and yn+DYN >= y0+DY0 >= yn
or if
xn+DXN>= x0 >=xn and yn+DYN >= y0+DY0 >= yn
then
returns Z
else
returns NZ

This routine can be rearranged in this way

if
(yn+DYN>= y0 >= yn or yn+DYN >= y0+DY0 >= yn)
and
(xn+DXN>= x0 >=xn or xn+DXN>= x0+DX0 >=xn)
then
returns Z
else
returns NZ

----------------

Let’s start from

(xn+DXN>= x0 >=xn or xn+DXN>= x0+DX0 >=xn)

or better from

(xn + DXN>= x0 and x0 >= xn) or (xn + DXN >= x0+DX0 and x0+DX0 >= xn)


main:
….
ld b, X0
ld c, XN
ld d, D0N
ld e, DXN
call test2
….

; TEST2 coordinate:
; in: b=X; c=XN; d=DX; e=DXN
; out: Z if (XN+DXN>= X >=XN) or (XN+DXN>= X+DX >=XN)
; NZ otherwise

test2:

call test ; b=X; c=XN; e=DXN
ret z ; if (XN+DXN>= X >=XN) return Z
ld a, b ; else…
add a, d
ld b,a ; b = X + DX; c=XN; e=DXN
call test ; if (XN+DXN>= X + DX >=XN) return Z otherwise NZ
ret


; TEST:
; in: b=X; c=XN; e=DXN
; out: Z if XN+DXN>= X >=XN,
; NZ otherwise


test:

ld a, c
add a, e ; A = XN + DXN
cp b ; compare A with B, if A>=B, carry=0; otherwise if A<B, carry=1 and zero = 0
ret c ; if XN+15 < X return flag NZ
; continue if XN+15 >= X
ld a, b
cp c
ret c ; if X < XN return flag NZ

; here we have (X>=XN) and (XN+DXN>=XN)
xor a
ret ; return flag Z

I just pointed to it for the comments and info given there... I don't mind discussing stuff about it here.

BiFi: No problem! I will continue here.

------

Let'us go to

if
(yn+DYN>= y0 >= yn or yn+DYN >= y0+DY0 >= yn)
and
(xn+DXN>= x0 >=xn or xn+DXN>= x0+DX0 >=xn)
then
returns Z
else
returns NZ


We now assume something about sprites and sprite management.
Sprites are managed in a double chained list.

Each active sprite have a record with at least those fields
(forgive me I love sjasm notation)

struct SPRT
p_next_record dw next_record
p_previous_record dw previous_record
p_Y db Y
p_X dw X
p_DX db DX
p_DY db DY
p_attribute1 dw attribute1
p_attribute2 dw attribute2
etc.
etc.
ends

This means that the main character has the structure

p_next_record dw next_record
p_previous_record dw previous_record
p_Y db Y0
p_X dw X0
p_DX db DX0
p_DY db DY0
p_attribute1 dw attribute1
p_attribute2 dw attribute2
etc.
etc.

and the n-th enemy has the structure


p_next_record dw next_record
p_previous_record dw previous_record
p_Y db YN
p_X dw XN
p_DX db DXN
p_DY db DYN
p_attribute1 dw attribute1
p_attribute2 dw attribute2
etc.
etc.

In the following I must assume that each field is pointed by its name



main:
....


; Enemy_test:
; in: IX pointer to main sprite data-structure
; IY pointer to enemy sprite data-structure
; out: Z if collision
; NZ otherwise


Enemy_test:

ld b, (IX+ SPRT.p_X)
ld c, (IY+ SPRT.p_X)
ld d, (IX+ SPRT.p_DX)
ld e, (IY+ SPRT.p_DX)
call test2
ret NZ
ld b, (IX+ SPRT.p_Y)
ld c, (IY+ SPRT.p_Y)
ld d, (IX+ SPRT.p_DY)
ld e, (IY+ SPRT.p_DY)
call test2
ret

; TEST2 coordinate:
; in: b=X; c=XN; d=DX; e=DXN
; out: Z if (XN+DXN>= X >=XN) or (XN+DXN>= X+DX >=XN)
; NZ otherwise

test2:

call test ; b=X; c=XN; e=DXN
ret z ; if (XN+DXN>= X >=XN) return Z
ld a, b ; else...
add a, d
ld b,a ; b = X + DX; c=XN; e=DXN
; if (XN+DXN>= X + DX >=XN) return Z otherwise NZ

; TEST
; in: b=X; c=XN; e=DXN
; out: Z if XN+DXN>= X >=XN,
; NZ otherwise

test:

ld a, c
add a, e ; A = XN + DXN
cp b ; compare A with B, if A>=B, carry=0; otherwise if A<B, carry=1 and Z = 0
ret c ; if XN+15 < X return flag NZ
; continue if XN+15 >= X
ld a, b
cp c
ret c ; if X < XN return flag NZ

; here we have (X>=XN) and (XN+DXN>=XN)
xor a
ret ; return flag Z

Just a question: Would you update the enemies positions, using intelligent movement or not, in the same loop you use for the collision detection or not ? Personally I would.

Also isn't there a way to bypass using IX/IY. Any operations with those registers is so freaking slow (I use them in my routine but I didn't spent too much time thinking it thru).