@AuroraMSX

Ok, you can use multiple swapping to sort the list (e.g. bubblesort).
The cost of one swap is the same both if you use an array of
pointes or if you use chained lists.

Assume the usual SPRT structure

               struct 	SPRT
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	

and the usual list of pointers ordered with Y coordinate

Array_SPRT_pointers:

dw 	p_record_SPRT0
dw 	p_record_SPRT1
dw 	p_record_SPRT2
dw 	p_record_SPRT3
dw 	p_record_SPRT4
....
dw 	p_record_SPRT31

If YC is the data (s#6,s#5) and YN and DYN are the data of the generic enemy, we need to find the objects in the list that respect the condition

(YN+DYN>= YC >= YN)

As the list of pointers is ordered in ascending Y, they are all adjacent: do you see this point?

If we renounce the VDP we need to find the objects in the list that respect the condition

(YN+DYN>= Y0 >= YN or YN+DYN >= Y0+DY0 >= YN)

where Y0 and DY0 are data for the main sprite.


We try to sketch the loop for bin search in both cases in order to evaluate pros and contra.
Sorry for mixing C and sjasm notation.

Let’s start from the case of :

(YN+DYN>= YC >= YN)

p_head =	Array_SPRT_pointers
p_tail	  =	Array_SPRT_pointers + 32*2
p_mid	 =	(p_tail + p_head) /2


for ( ; ; )
  {
  if   *(*p_mid + SPRT. p_Y)  < YC  
    {
    p_tail  = p_mid
    p_mid = (p_tail + p_head) /2

    }
  else if 	*(*p_mid + SPRT. p_Y) + *(*p_mid + SPRT. p_DY)  > YC  
    {
    p_head = p_mid
    p_mid  = (p_tail + p_head) /2

    }
  else break
  }

As far as I understand the pointers

p_head and p_tail,

at the break should comprise all the
pointers in

Array_SPRT_pointers

to the records for which holds:

(YN+DYN>= YC >= YN)


What do you think ? Does it works?

Quote:

What do you think ? Does it works?

Yup. No doubt about it

@Magoo
@GhostP
Have you seen the loop? Any suggestion or comments before going to ASM?

No answers. I go on.

Assume the usual SPRT structure

               struct 	SPRT
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	

and the usual list of pointers ordered with Y coordinate

Array_SPRT_pointers:

dw 	p_record_SPRT0
dw 	p_record_SPRT1
dw 	p_record_SPRT2
dw 	p_record_SPRT3
dw 	p_record_SPRT4
....
dw 	p_record_SPRT31

the C like code is

p_head =	Array_SPRT_pointers
p_tail	=	Array_SPRT_pointers + 32*2

for ( ; ; )  
{   p_mid  = (p_tail + p_head) /2      
     if   *(*p_mid + SPRT.p_Y) < YC      
        {    p_tail  = p_mid    }  
     else if 	*(*p_mid + SPRT.p_Y) + *(*p_mid + SPRT.p_DY) > YC      
        {    p_head = p_mid    }  
     else break  
}

The ASM equivalent is

ld     hl, array_SPRT_pointers
ld     de, array_SPRT_pointers + 32*2

loop:
push     hl        ;        p_head
push     de       ;        p_tail

sll     hl
sll     de
add   hl,de     ;        hl = p_mid
push  hl         ;        p_mid

ld     bc,(hl)     ;       bc = *p_mid
ld     hl,SPRT.p_Y
add  hl,bc       ;      hl = *p_mid + SPRT.p_Y
ld    a,(hl)       ;      a = *(*p_mid + SPRT.p_Y)
cp    YC
jr    nc,elseif

pop    de        ;       p_tail  = p_mid
pop    af         ;       drop previous p_tail
pop    hl         ;        p_head

jr    loop

elseif:

ld     bc, SPRT.p_DY-SPRT.p_Y
add   hl,bc      ;      hl = *p_mid + SPRT.p_DY
add   a,(hl)     ;      a = *(*p_mid + SPRT.p_Y) + *(*p_mid + SPRT.p_DY)
ld      b,a
ld      a,YC
cp     b
jr    nc,else

pop    hl         ;       p_head  = p_mid
pop    de        ;       p_tail
pop    af         ;       drop previous p_head

jr    loop

else: 

pop       af      ;       drop previous p_mid
pop       de     ;        p_tail
pop       hl      ;        p_haed

Any comment ???

In case not, the next step is to scan the list within HL and DE in order to find the sprites
such that

(XN+DNX >= XC > XN)

Quote:

What do you think ? Does it works?

Actually, there's a small flaw in the algorithm.

Quote:

(YN+DYN>= YC >= YN)

That means, that YC is not a single value you can test against; you need to test agians the edges of the range (YN and YN+DYN). And I think you've got the comparisons mixed up:

while(1) {
  if((*p_mid)->p_Y > YN+DYN) {
    p_tail = p_mid;
    p_mid = (p_head + p_tail) / 2;
  } else if((*p_mid)->p_Y + (*p_mid)->p_DY  < YN) {
    p_head = p_mid;
    p_mid = (p_head + p_tail) / 2;
  } else {
    break;
  }
}

YC is the coordinate of the collision from VDP (s#6,s#5)
XC is the coordinate of the collision from VDP (s#4,s#3)

I started depicting that two option are possible:
1) using VDP's XC,YC
2) avoiding it

where in this case we need to find all the sprites witch respect

(YN+DYN>= Y0 >= YN or YN+DYN >= Y0+DY0 >= YN)

Let me two minutes for studing you loop, I need to check.

Let's try your solution: I assume you mean YN, YN+DYN are position
and size of the main sprite (???)
the data are:

*p0Y   *p1Y   *p0y+*p0DY              *p1Y+*p1DY                *p2Y           *p2Y+*p2DY
|--------|-------|-------------|--------|-------------|----------|-------------------|
                                yn                  yn+dyn

If your loop works the solution is a list of the sole element p1Y
let's run your loop

phead = p0Y
ptail = p2Y
pmid = p1Y

loop1
as *pmid > yn+dyn thus ptail = pmid (i.e. p1Y)
pmid = (p0y+p1y)/2 (i.e. p0y)

loop2
as *pmid > yn+dyn thus ptail = pmid (i.e. p0Y) (solution lost !!)
pmid = (p0y+p1y)/2 (i.e. p0y)

loop3
as *pmid > yn+dyn thus ptail = pmid (i.e. p0Y)
pmid = (p0y+p1y)/2 (i.e. p0y)

...
No exit : infinite interactions!!!!

Still sure your loop works?? :-)

Quote:

Let's try your solution: I assume you mean YN, YN+DYN are position and size of the main sprite (???)

I guess so. I didn't introduce the names

Quote:

the data are: *p0Y *p1Y *p0y+*p0DY *p1Y+*p1DY *p2Y *p2Y+*p2DY |--------|-------|-------------|--------|-------------|----------|-------------------| yn yn+dyn If your loop works the solution is a list of the sole element p1Y let's run your loop phead = p0Y ptail = p2Y pmid = p1Y loop1 as *pmid > yn+dyn thus ptail = pmid (i.e. p1Y)

Erh, *pmid = p1Y is definitely < yn+dyn in your graph

Quote:

Still sure your loop works?? :-)

Rather

ok,

so, there is screen 5,
I readout sprite collision st. r#0, at several lines several times per frame (on the Vblank, on the line split, outside the int.,
BUT the sprite collision detection doesnt work fine.
Whenever there is a collision I set the computer to play a SFX, so I know there is collision.

However, between some lines it seems to work perfectly (likesay between y=50 and y=100,
and y=130 and y=150,
but on all the other lines there is simply no collision detection.
I made sure I never ever readout s.r#0 anywhere else (because this resets the colision bit, right)

what to do???????????

ps, everybody get ready, because it wont take long for the first test version of SPACEMANBOW 2 LEVEL 1 !!!!!!!!!

cheers !

Quote:

I readout sprite collision st. r#0, at several lines several times per frame (on the Vblank, on the line split, outside the int., BUT the sprite collision detection doesnt work fine.

Actually the manual of v9938 says that only bit F is reset reading S#0.
In theory reading S#0 multiple times per frame shold return if there are
collisions till at the point the raster has arrived in the frame, and should
not be reset untill a new raster scan starts.

In any case I am not sure how things are really working and as I have only
openMSX, the only suggestion I have is to avoid to read the collision bit
multiple times per frame.

Try reading S#0 once per frame, at the bottom of the screen,
the best is at Vblank, when all the frame is completed.

i readout s#0 once per frame \, at VBLANK (do you think using the Bios changes things???),
But sprite collision works in between certain lines (also depending 50 or 60 hrtz),

However, and this is weird, if I do not disable sprites at y=212 and enable at y=24 (scoreboard)
the spritecollision seems to be working better (still not fine)

anyone familiar with this problem?

Could you detail the whole sequence?
when do you disable sprites?
when do you read S#0 ?
and all the related stuff?

How do you read s#0 and how do you set the registers?

to make things more easy I disabled the screensplit and the backgroundscroll.

there is the VBLANK int, on which I:
put the (32) sprites on screen.

and outside the int, I:
1) have the routine which makes my ship move (using the arrowkeys)
2) make enemy enter/leave the screen.
3) readout st.r#0 for sprite collision

Thats all, and still, the sprite collision only works in between certain lines ... ???
approx. in between y=50 and y=80

and, if I put the sprite collision detection routine ON the interrupt it doesn´t even work at all........

Quote:

and outside the int, I: 1) have the routine which makes my ship move (using the arrowkeys) 2) make enemy enter/leave the screen. 3) readout st.r#0 for sprite collision

Do this:

In the int routine at vblank, before doing anything, read s#0 and store it in RAM,
put your sprites and do all the staff you need in to do at vblank.
NOTE!!
As far as I remember that the BIOS, when calls hFD9F, has already red S#0!!!
It is passed in register A, and, as far I remember, it is not jet stored in hF3E7!!!
This means that you do not need to read the VDP by yourself, just use the value in A.
Remember !! The bios, on exit from your interrupt, will store in hF3E7 any value
you pass in A. If you want meaningful values in that location, on exit, you need to
pass in A the same value you have found.


Outside the int routine use the copy of S#0 you stored in RAM.
NOTE
Take care to use some kind of synchronization between the int routine and
the main loop outside the int. This is in order to avoid to use the value of S#0
corresponding to one frame two o tree times.

wow, cool info. thanx, I´m gonna work with it right away....
bit 5 of status register 0 is used to readout spritecollision.

So, if I get your info correct, then AT VBLANK I simply do:

vblank:
bit 5,a
call z,collision
...
...
...
ei
ret