Fast way of converting screen coordinates to HW Sprite control words

[DanScott]

So I found this code (by Leffman) in another thread.. it's a nice way to do it, but was concerned about the cycle count considering there are a couple of 8 bit shifts in there..

move.w  #50, d0    ; x position
move.w  #100, d1   ; y position
move.w  #20, d2    ; height

add.w   #$80, d0   
add.w   #$2c, d1   
add.w   d1, d2     
clr.b   d3         

lsl.w   #8, d1     ; move vertical start bit 8 in place
addx.b  d3, d3     

lsl.w   #8, d2     ; vertical stop bit 8
addx.b  d3, d3     

lsr.w   #1, d0     ; horizontal start bit 0
addx.b  d3, d3     

move.b  d0, d1     ; make first control word
move.b  d3, d2     ; second control word

I was thinking of precalculating some tables of X & Y values, where i know that all sprites will be 8 or 16 pixels high (or have tables for different heights of sprite). This is because I intend to re-use many of the same sprites multiple times down the screen (think..enemy bullets for example), so need to process these as quick as possible

		;	d0 = Screen X , d1 = Screen Y

		lea	HW_SpriteXTable,a0
		lea	HW_SpriteYTable,a1

		add.w	d0,d0
		add.w	d0,d0
		move.l	(a0,d0.w),d0
		add.w	d1,d1
		add.w	d1,d1
		or.l	(a1,d1.w),d0

anyone else ever addressed this issue before?

[Leffmann]

Originally Posted by DanScott

anyone else ever addressed this issue before?

Why, yes, I have actually!! Something like this maybe:

XTable
  rept 320
x   set REPTN+$80
    dc.b  0, x>>1, 0, x&1
  endr


YTable
  rept 256
ys  set REPTN+$2c
ye  set ys+8
    dc.b  ys&255, 0, ye&255, ((ys>>6)&%100) | ((ye>>7)&%10)
  endr

[DanScott]

Yes Exactly like this.

I was actually creating the tables in code...silly me...

[Asman]

Originally Posted by DanScott

		;	d0 = Screen X , d1 = Screen Y

		lea	HW_SpriteXTable,a0
		lea	HW_SpriteYTable,a1

		add.w	d0,d0
		add.w	d0,d0
		move.l	(a0,d0.w),d0
		add.w	d1,d1
		add.w	d1,d1
		or.l	(a1,d1.w),d0

You can save few more cycles. Most obvious is change lea table,ax into lea table(pc),ax (saving 4 cycles, 8 in total). But is possible to save another 4 cycles. Its a bit tricky and I think that would be works. Put first table somewhere and next one after 65kb block then is possible to use only one ax register with swap

		lea	HW_SpriteXTable(pc),a0
		add.w	d0,d0
		add.w	d0,d0
		move.l	(a0,d0.w),d0
		add.w	d1,d1
		add.w	d1,d1
		swap	d1
		or.l	(a0,d1.l),d0  

HW_SpriteXTable: ; offset 0
;...
;end of table

;$1000-$500 free of data storage

;offset $10000
;here starts table y

[DanScott]

I think that "swap" is just going to put the offsets as $00000000,$00040000,$00080000 etc..

Actually, the lea of the tables will be done once outside the main sprite processing loop, so will be able to load into 2 registers..

Now the next thing.. how to maintain a list of sorted (in Y) sprites...

Perhaps when a sprite moves, to move it up or down the list depending on if it moves past another sprite?

I would guess that only 1 or 2 sprites would be inserted into the list at any given frame, so could insert them in the correct position.

[Photon]

Consider making all sprites the same height (the height of the highest sprite for that channel[-pair]. Saves copying spritedata into the right place of the chain. I always thought that kind of double work was unattractive for Amiga. But ofc it also offers to set the control words after waits in the Copper, and to cover the spacing you can point to a single screen-high blank sprite. The DMA cost is lower than what basically equates to a bob routine to build the chain of sprites

[Leffmann]

Originally Posted by DanScott

Now the next thing.. how to maintain a list of sorted (in Y) sprites...

Perhaps when a sprite moves, to move it up or down the list depending on if it moves past another sprite?

I would guess that only 1 or 2 sprites would be inserted into the list at any given frame, so could insert them in the correct position.

Bubble-sort with a simple insertion when adding a new sprite. If you regularly add many new sprites, then it may be better to just append them to the end of the list and use Insertion-sort for everything.

Bubble and Insertion are bad for general purpose sorting, but they are great for this because they come close to O(n) complexity when the list is almost sorted.

[DanScott]

Originally Posted by Leffmann

Bubble-sort with a simple insertion when adding a new sprite. If you regularly add many new sprites, then it may be better to just append them to the end of the list and use Insertion-sort for everything.

Bubble and Insertion are bad for general purpose sorting, but they are great for this because they come close to O(n) complexity when the list is almost sorted.

Yes, the list would pretty much be kept in a reasonable sorted order, requiring not too many passes to actually re-sort it when sprites change their position in relation to other sprites.

[Leffmann]

I have a working example here now, it multiplexes 50 small objects across 4 sprites, with about 1 object dropped per frame.

The sprites are just "chains" of the same object repeated vertically, and after sorting I assign the objects from top to bottom to each sprite in turn.

It needs about 2-3 milliseconds of time per frame on an A500, but the code can still be improved.

[DanScott]

That's looking great already

I'm currently investigating the process of sorting "already nearly sorted" lists fast

My HW sprite routine that I am working on right now, is currently inserting new sprites at an already sorted position in the list. Then after all sprites are moved in their update, the list is still pretty much in sorted order... maybe only a very few sprites have actually change position relative to each other. This makes re-sorting the list very quick in one pass (even bubble sort would have to do a minimum of 2 passes if even only 2 sprites switch sorting order.. i think.. i may be wrong )

Also, as the sprite information will contain a lot more than just positions and velocities (flags, control info etc..), I am not swapping big chunks of data in the sort, but maintaining a sorted list of ptrs to the data Just have to swap longword pointers

[Asman]

Originally Posted by DanScott

That's looking great already

I'm currently investigating the process of sorting "already nearly sorted" lists fast

My HW sprite routine that I am working on right now, is currently inserting new sprites at an already sorted position in the list. Then after all sprites are moved in their update, the list is still pretty much in sorted order... maybe only a very few sprites have actually change position relative to each other. This makes re-sorting the list very quick in one pass (even bubble sort would have to do a minimum of 2 passes if even only 2 sprites switch sorting order.. i think.. i may be wrong )

Also, as the sprite information will contain a lot more than just positions and velocities (flags, control info etc..), I am not swapping big chunks of data in the sort, but maintaining a sorted list of ptrs to the data Just have to swap longword pointers

I have questions.
1) How many objects you mean ? Max 100 ?
2) range of y position is between 0 and 255 ? Or it's rather uword value ?

[DanScott]

Currently I have max of 32 sprites, distributed between 2 hardware sprites

of course, I can change my equate to MaxNumSprite equ 100

X & Y positions are signed word values in fixed point 12:4

32 is ample even for nearly bullet hell style

[Leffmann]

I played a bit with larger objects of different sizes and found that it's difficult to get away with, even when you multiplex over many hardware sprites. There's too much surface that blinks off the screen, and for too long.

In my example the objects are just bouncing off the walls randomly, to have something to try it with, but I think multipexing like this works much better for "bullet hell" where you typically have showers or explosions of small bullets that move away from eachother.

[DanScott]

Back on the "plexing" and just did a simple bubble sort for now.. it's pretty efficient for nearly sorted lists.. bullets are generally moving down the screen, or towards the player, so not many will switch order that often

Here's the sort routine.. maybe someone can see some glaringy obvious optimisation that I have missed (I am not sure an insertion sort would be any quicker, as the whole list will need iterating ,and then more checks up through the list for the insert.. perhaps there would be less swaps? don't know...)

		move.w	Var_NumberOfSprites(a5),d6	; Get number of sprites in list
		subq.w	#2,d6				; Subtract 2 for dbf value
		blt.s	.NoSort				; No sorting required if number of sprites is 1 or less 

		lea	Var_SpritePointerList(a5),a3	; Get pointer to start of our sprite ptr list
.SortLoopOuter
		move.l	a3,a0				; a0 = start of sprite ptr list
		moveq	#0,d1				; d1 = flag (will be set to 1 if a swap occured)
		move.w	d6,d7				; d7 = loop counter (number of sprites-2)
.SortLoopInner
		move.l	(a0)+,a1			; Get address of sprite data 1 in a1
		move.l	(a0),a2				; Get address of sprite data 2 in a2
		move.w	EB_YPos(a1),d0			; Get Y position of sprite data 1 in d0
		cmp.w	EB_YPos(a2),d0			; Compare Y position of sprite data 2 with Y position of sprite data 1 (in d0)
		ble.s	.NoSwap				; Important!! Less than OR equal = No Swap.. otherwise swaps forever equal values....
		move.l	a2,-4(a0)			; Store sprite 2 pointer where sprite 1 pointer was stored
		move.l	a1,(a0)				; Store sprite 1 pointer where sprite 2 pointer was stored
		moveq	#1,d1				; d1 = 1.. There has been a swap
.NoSwap
		dbf	d7,.SortLoopInner		; Loop through all sprite pointers
		tst.w	d1				; Check the d1 flag
		bne.s	.SortLoopOuter			; If flag is not 0, there was a swap in the last pass, so need to pass through again
.NoSort

[Don_Adan]

Originally Posted by DanScott

Back on the "plexing" and just did a simple bubble sort for now.. it's pretty efficient for nearly sorted lists.. bullets are generally moving down the screen, or towards the player, so not many will switch order that often

Here's the sort routine.. maybe someone can see some glaringy obvious optimisation that I have missed (I am not sure an insertion sort would be any quicker, as the whole list will need iterating ,and then more checks up through the list for the insert.. perhaps there would be less swaps? don't know...)

Only small optimisation:

		move.w	Var_NumberOfSprites(a5),d6	; Get number of sprites in list
		subq.w	#2,d6				; Subtract 2 for dbf value
		blt.s	.NoSort				; No sorting required if number of sprites is 1 or less 

		lea	Var_SpritePointerList(a5),a3	; Get pointer to start of our sprite ptr list
		moveq	#0,d1				; d1 = flag (will be set to -128 if a swap occured)
.SortLoopOuter
		move.l	a3,a0				; a0 = start of sprite ptr list
		move.w	d6,d7				; d7 = loop counter (number of sprites-2)
.SortLoopInner
		move.l	(a0)+,a1			; Get address of sprite data 1 in a1
		move.l	(a0),a2				; Get address of sprite data 2 in a2
		move.w	EB_YPos(a1),d0			; Get Y position of sprite data 1 in d0
		cmp.w	EB_YPos(a2),d0			; Compare Y position of sprite data 2 with Y position of sprite data 1 (in d0)
		ble.s	.NoSwap				; Important!! Less than OR equal = No Swap.. otherwise swaps forever equal values....
		move.l	a2,-4(a0)			; Store sprite 2 pointer where sprite 1 pointer was stored
		move.l	a1,(a0)				; Store sprite 1 pointer where sprite 2 pointer was stored
		moveq	#-128,d1			; d1 = -128.. There has been a swap
.NoSwap
		dbf	d7,.SortLoopInner		; Loop through all sprite pointers
		add.b 	d1,d1				; Check the d1 flag
		bcs.s	.SortLoopOuter			; If flag is not 0, there was a swap in the last pass, so need to pass through again
.NoSort

[DanScott]

thanks just saw it..

it is little things like this that I tend to miss

[Asman]

Other obvious optimization is when EB_YPos = 0.

I found another one: (based on Don_Adan post #15 - cheers Don ).

		move.w	Var_NumberOfSprites(a5),d6	; Get number of sprites in list
		subq.w	#2,d6				; Subtract 2 for dbf value
		blt.s	.NoSort				; No sorting required if number of sprites is 1 or less 

		lea	Var_SpritePointerList(a5),a3	; Get pointer to start of our sprite ptr list
		moveq	#0,d1				; d1 = flag (will be set to -128 if a swap occured)
.SortLoopOuter
		move.l	a3,a0				; a0 = start of sprite ptr list
		move.w	d6,d7				; d7 = loop counter (number of sprites-2)
.SortLoopInner
		move.l	(a0)+,a1			; Get address of sprite data 1 in a1
		move.l	(a0)+,a2				; Get address of sprite data 2 in a2
		move.w	EB_YPos(a1),d0			; Get Y position of sprite data 1 in d0
		cmp.w	EB_YPos(a2),d0			; Compare Y position of sprite data 2 with Y position of sprite data 1 (in d0)
		ble.s	.NoSwap				; Important!! Less than OR equal = No Swap.. otherwise swaps forever equal values....
		move.l	a1,-(a0)			; Store sprite 1 pointer where sprite 2 pointer was stored
		move.l	a2,-(a0)			; Store sprite 2 pointer where sprite 1 pointer was stored
		moveq	#-128,d1			; d1 = -128.. There has been a swap
.NoSwap
		dbf	d7,.SortLoopInner		; Loop through all sprite pointers
		add.b 	d1,d1				; Check the d1 flag
		bcs.s	.SortLoopOuter			; If flag is not 0, there was a swap in the last pass, so need to pass through again

[Don_Adan]

Next small optimisation:

		move.w	Var_NumberOfSprites(a5),d6	; Get number of sprites in list
		subq.w	#2,d6				; Subtract 2 for dbf value
		blt.s	.NoSort				; No sorting required if number of sprites is 1 or less 

		lea	Var_SpritePointerList(a5),a3	; Get pointer to start of our sprite ptr list
.SortLoopOuter
		move.l	a3,a0				; a0 = start of sprite ptr list
		move.w	d6,d7				; d7 = loop counter (number of sprites-2)
.SortLoopInner
		move.l	(a0)+,a1			; Get address of sprite data 1 in a1
		move.l	(a0),a2				; Get address of sprite data 2 in a2
		move.w	EB_YPos(a1),d0			; Get Y position of sprite data 1 in d0
		sub.w	EB_YPos(a2),d0			; Compare Y position of sprite data 2 with Y position of sprite data 1 (in d0)
		ble.s	.NoSwap				; Important!! Less than OR equal = No Swap.. otherwise swaps forever equal values....
		move.l	a2,-4(a0)			; Store sprite 2 pointer where sprite 1 pointer was stored
		move.l	a1,(a0)				; Store sprite 1 pointer where sprite 2 pointer was stored
.NoSwap
		dbf	d7,.SortLoopInner		; Loop through all sprite pointers
		tst.w	d0				; 
		bgt.s	.SortLoopOuter			; If flag is not 0, there was a swap in the last pass, so need to pass through again
.NoSort

Due im not branch expert, im not sure if bgt or bhi is oki for tst.w d0. But im not sure if it will be works oki, perhaps not.

[Asman]

@Don_Adan. Please add my optimization to your post #18. Thanks.

@DanScott - I'm not sure but if in list there is only one swap then loop will be done twice instead of one time, right ?

[DanScott]

No sure if that change in #18 will work. the sub from d0, will only test for the last sub in the d7 dbf loop

Won't the (A0)+,(A0)+ then -(A0),-(A0) bring A0 back to it's original value.. A0 needs to be +4 for the next iteration

Yes, if there is only one swap, it will pass through again. This is why perhaps an insertion sort would be better.. it can do it in one pass.. but there are extra overheads in the insert upwards routine