@Magoo

First point:
As far as I can understand, I do not think that having movement
and collision in the same loop is the best solution.
Movement loop concerns all the active objects in the level, some of
them outside the visible window of the current screen.
The sprite list for movements should be longer than the list of the
displayed sprites.
Things get much simpler if the sole active objects are those visible on
the screen, but this is true almost only in shooter games (with fixed scrolling).
In this case, having only one list could improve things (you have less overhead),
but note that if you apply the strategy of ordering the records (eg.
according to Y coordinate), in average you need to scan only half list
for collision, where you keep scanning the whole list for movement update.
My idea about this point is to have two lists that chain the same records,
one, complete, to be run during movement update, one, shorter, to be run
during sprite visualization.

Second point:
Yes: We could avoid IX and IY, but this is a matter of code optimization,
probably, the best thing is to keep IX and IY till the end for the sake of
readability and then change the code. I think that the cost of removing
IX and IY from the code is having very crappy code at this time.
(you need to use EXX and more…)

Quote:

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).

Ofcourse it is, that's called GOOD CODING harf harf
you maybe 'ave to realign your tables to get the max out of it (read less INC HL, DEC HL)
I've dunnit with my animation routine. Only using HL as the table pointer. works like a charm all tho it requires some good analysis of your animation tables. just go with the flow honey...

I was thinking on what to do in order to implement binary search with dynamic ordered lists.
The conclusion is sad:

The only solution is renouncing to dynamic chained lists and passing to a
static list of pointers to the sprite records.

You still have a struct like this for each sprite,

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

but you need also a static array of pointers like this

Array_SPRT_pointers:

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

where the array of pointers is physically ordered accordingly to Y coordinates.

Reordering the pointer array could be not very heavy, but dynamic lists are
far better in this.
What do you think ? Is there a solution for keeping lists and implementing binary search???

reply:

ld hl,DATSPR ;spritetable
ld de,$7800 ;sprite attribute table in VRAM (I might have filled in the
wrong address, never mind that)
ld b,128 4*32) (4 sprites with: y,x,spr number, reserved)
ld c,$98 ;out port

OTIR

This is the way I used to plot all 32 spriteson the int.
the first 4 sprites are the player and the 2 options
sprite 5-14 are for 9 bullets and 1 missile
sprite 15-32 are for enemies

(does this mean that s#3-s#6 allways give coordinates of an enemy at collision?)

If the sprite collision flag is NOT set, then I can move on to the next int.
However, If it IS set and I want to use r#3-r#6 for sprite collision,
then each int. only 1 collision (the last one) can be detected.....

Is this a problem?
(If not

what do I do with s#4 and s#6?? what are the x8 and y8??

S#3 x7 x6 x5 x4 x3 x2 x1 x0
s#4 1 1 1 1 1 1 1 x8
s#5 y7 y6 y5 y4 y3 y2 y1 y0
s#6 1 1 1 1 1 1 e0 y8

and this way... if the sprite collision flag bit is set I have to
find out which sprite caused this and which sprite is coliding,
So 2 checks?????????

Or should I OUT the y,x of enemy1 (its arribute table), and
check for colision,
if no colision, then do the same for enemy2, 3, 4 etc....??

@norakomi

I go by heart. Check those info by yourself.

read

s#3 x7 x6 x5 x4 x3 x2 x1 x0
s#4 1 1 1 1 1 1 1 x8
s#5 y7 y6 y5 y4 y3 y2 y1 y0
s#6 1 1 1 1 1 1 y9 y8

Note: reading s#5 reset all registers s#3-s#6
read s#5 as last or you will lose s#6

Let:
X = x8 x7 ... x0 = (s#4,s#3)
Y = y9 y8 y7 ... y0 = (s#6,s#5)

then

XC = X -12
YC = Y -8

are the coordinates of the last point where the two overlapping sprites
collided in the screen refresh just concluded.

I remember "last point"
this means that if more than two sprites collide, you check only one collision
at time, specifically the last in the screen refresh.

I need someone that can confirm. Anyone has done tests on the subject?


Actually a very simplified routine could be

if XC and YC fall in the rectangular frame of your ship you have been hit: scan the enemy list to find who is hitting you (i.e. whose enemy's rectangular frame contain XC and YC)

otherwise

for each bullet test if XC and YC fall in the rectangular frame of the bullets: in this case you are hitting,
scan the enemy list to find who has been hit (i.e. whose enemy's rectangular frame contain XC and YC)

In this way you deal with one collision at time, but who cares !

Am I right ???? Can anyone confirm the VDP behavior???

Quote:

I was thinking on what to do in order to implement binary search with dynamic ordered lists. The conclusion is sad: The only solution is renouncing to dynamic chained lists and passing to a static list of pointers to the sprite records. You still have a struct like this for each sprite, 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 but you need also a static array of pointers like this Array_SPRT_pointers: dw p_record_SPRT0 dw p_record_SPRT1 dw p_record_SPRT2 dw p_record_SPRT3 dw p_record_SPRT4 .... where the array of pointers is physically ordered accordingly to Y coordinates. Reordering the pointer array could be not very heavy, but dynamic lists are far better in this. What do you think ? Is there a solution for keeping lists and implementing binary search???

One solution could be having yet another pointertable, in spriteinfo order (so entry X in the pointer table corresponds to entry X in the sprite info table), where each pointer points to it's corresponding entry in the Y-sorted pointer list.

This gives you fast access to the sorted list, but requires a bit more effort when you're reordering the lists.

Quote:

Quote: 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). Ofcourse it is, that's called GOOD CODING harf harf you maybe 'ave to realign your tables to get the max out of it (read less INC HL, DEC HL) I've dunnit with my animation routine. Only using HL as the table pointer. works like a charm all tho it requires some good analysis of your animation tables. just go with the flow honey...

Mind sharing some of your experience on how your tables are organized and your routines work ? Come on, dun be ashamed. We're not here to judge you

@AuroraMSX

Quote:

One solution could be having yet another pointertable, in spriteinfo order (so entry X in the pointer table corresponds to entry X in the sprite info table), where each pointer points to it's corresponding entry in the Y-sorted pointer list. This gives you fast access to the sorted list, but requires a bit more effort when you're reordering the lists.

???? I cannot understand your proposal ?????

Mine is to have an array of pointers ordered according to the Y coordinate, like:

Array_SPRT_pointers:

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

On this array I can perform binary search doing log(N) comparisons on Y.
The array needs to be phisically reorderd at each frame using for
example bubble sort.

Quote:

@AuroraMSX Quote: One solution could be having yet another pointertable, in spriteinfo order (so entry X in the pointer table corresponds to entry X in the sprite info table), where each pointer points to it's corresponding entry in the Y-sorted pointer list. This gives you fast access to the sorted list, but requires a bit more effort when you're reordering the lists. ???? I cannot understand your proposal ?????

Then probably I haven't understood the problem

I thought the problem was that, given the index number of a sprite N (the Nth entry in the sprite info table), how to find the nearest next sprite. In your solution, this is a two step process:

1. Find the entry X for sprite N in the pointer table. This search is your O(log(N)) binary search.
2. The neighbouring sprites are the sprites pointed to by entry X-1 and X+1 in the pointer table

Now, my proposal was to speed up step 1, by keeping a second pointer table, ordered by sprite number, with entries pointing to the first pointer table. SO, in the second table, sprite N has a direct reference to its entry in the first pointer table, making step 1 a O(1) process.

But re-reading the thread, I guess you're searching for a certain sprite, given an Y-coordinate, and then your proposal is fine. In that case I don't understand really your remark:

Quote:

Reordering the pointer array could be not very heavy, but dynamic lists are far better in this.

What exactly do you mean by dynamic lists? For me a dynamic list means creating a structure like (C notation):

typedef struct listentry {
    /* some-data-here */
    struct listentry *next;
} linked_list;

And that's pretty much what your pointer array is. The only difference being that the pointers are "detached" from the data ...

Quote:

Quote: Quote: 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). Ofcourse it is, that's called GOOD CODING harf harf you maybe 'ave to realign your tables to get the max out of it (read less INC HL, DEC HL) I've dunnit with my animation routine. Only using HL as the table pointer. works like a charm all tho it requires some good analysis of your animation tables. just go with the flow honey... Mind sharing some of your experience on how your tables are organized and your routines work ? Come on, dun be ashamed. We're not here to judge you

gotta dig up them specs then... should be no biggy. I might even share it with you.

Quote:

Then probably I haven't understood the problem I thought the problem was that, given the index number of a sprite N (the Nth entry in the sprite info table), how to find the nearest next sprite.

The problem is:
given the coordinates X,Y of the main sprite finte the colliding enemy

Quote:

But re-reading the thread, I guess you're searching for a certain sprite, given an Y-coordinate, and then your proposal is fine. In that case I don't understand really your remark: Quote: Reordering the pointer array could be not very heavy, but dynamic lists are far better in this. What exactly do you mean by dynamic lists? For me a dynamic list means creating a structure like (C notation): typedef struct listentry { /* some-data-here */ struct listentry *next; } linked_list; And that's pretty much what your pointer array is. The only difference being that the pointers are "detached" from the data ...

Correct!

When I say dynamic list I mean a list of records chained by pointers
(I mean exactly what you mean in your C code)
With this list it is very fast to insert an object or perform a sorting,
but it is impossible doing a binary serch.

Having a phisically array of pointers, allows binary serch but reordering
needs the phisical movement of the pointers in the array, that is havyer
that ordering the dynamic list.

Am I clearer?

Quote:

Quote: Then probably I haven't understood the problem I thought the problem was that, given the index number of a sprite N (the Nth entry in the sprite info table), how to find the nearest next sprite. The problem is: given the coordinates X,Y of the main sprite finte the colliding enemy

The main sprite also has a entry in your Y-coordinate sorted pointer array, right? So, if you keep an extra pointer to the main sprite's entry in the pointer array, the colliding sprite then has to be either the previous or the next entry in the pointer array.
O(1) search!

Quote:

Correct! When I say dynamic list I mean a list of records chained by pointers (I mean exactly what you mean in your C code) With this list it is very fast to insert an object or perform a sorting, but it is impossible doing a binary search. Having a phisically array of pointers, allows binary serch but reordering needs the phisical movement of the pointers in the array, that is havyer that ordering the dynamic list.

Is it? Re-ordering a linked list is also a matter of pointer movement.

// swap 'this' with its successor, pointed to by the .next field

   tmp = this.next;
   this.next = (this.next)->next;
   (this.next)->next = tmp;

or

// 'pointers' is an array of pointers to data elements
// the ordering of elements is determined by the ordering
// in 'pointers'

   tmp = pointer[this];
   pointer[this] = pointer[this+1];
   pointer[this+1] = tmp;

As far as I can see, there is no real difference. Insertion and deletion are more expensive in the pointer array solution, than in a 'real' linked list. But that's it.

(Yup, much clearer )

Quote:

O(1) search!

Oops! Baaaaad AuroraMSX! BS!

The list is only sorted in Y-dir. which means that the next (or previous) entry can be on the same Y coord, but still far away in the X direction and therefor not the sprite we're looking for.

That implies that a binary search will only help you find the main sprite's entry in the array. Keeping that extra pointer then still speeds up things a lot: O(1) access to the main sprite instead of O(log(N)).

From there, I'm afraid it still boils down to a linear search in both directions through the array and, worst case, you'll find that the sprite you're looking for is the first or last entry in the poin ter array :/

Quote:

Is it? Re-ordering a linked list is also a matter of pointer movement.

No, more like pointer adjustment.

Quote:

I remember "last point" this means that if more than two sprites collide, you check only one collision at time, specifically the last in the screen refresh.

Well if this is true it is not very usfull, is it?

And what if to bullets collide in your player rectangle (asuming it is kept 16x16)
to the eye you're not hit, but out of the test folows you are hit. Anoying at least.

I think it is still easier to leave the VDP for what it is and do all of the checking yourself.

And just think of the fact that the MSX has only 32 sprites, and two sprite for enemies
and player, leaving what... 16 object to check! alright mabe you have a spritesplit make it 24
objects.
A nice liked list will be more than sufficient.

And there are always other options left like spreading or reducing framerate.