English Amiga Board


Go Back   English Amiga Board > Coders > Coders. Asm / Hardware

 
 
Thread Tools
Old 04 March 2016, 16:12   #1
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Belgrade, Serbia
Posts: 319
Fast way of converting screen coordinates to HW Sprite control words

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

Code:
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


Code:
		;	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?

Last edited by DanScott; 04 March 2016 at 17:06.
DanScott is offline  
Old 04 March 2016, 19:52   #2
Leffmann
 
Join Date: Jul 2008
Location: Sweden
Posts: 2,197
Quote:
Originally Posted by DanScott View Post
anyone else ever addressed this issue before?
Why, yes, I have actually!! Something like this maybe:

Code:
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
Leffmann is offline  
Old 05 March 2016, 11:35   #3
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Belgrade, Serbia
Posts: 319
Yes Exactly like this.

I was actually creating the tables in code...silly me...
DanScott is offline  
Old 05 March 2016, 13:11   #4
Asman
68k

Asman's Avatar
 
Join Date: Sep 2005
Location: Somewhere
Posts: 654
Quote:
Originally Posted by DanScott View Post
Code:
		;	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
Code:
		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

Last edited by Asman; 05 March 2016 at 14:01. Reason: added missing (pc)
Asman is offline  
Old 05 March 2016, 15:41   #5
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Belgrade, Serbia
Posts: 319
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.
DanScott is offline  
Old 06 March 2016, 00:52   #6
Photon
Moderator
Photon's Avatar
 
Join Date: Nov 2004
Location: Hult / Sweden
Posts: 4,591
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
Photon is offline  
Old 06 March 2016, 03:16   #7
Leffmann
 
Join Date: Jul 2008
Location: Sweden
Posts: 2,197
Quote:
Originally Posted by DanScott View Post
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.
Leffmann is offline  
Old 06 March 2016, 11:32   #8
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Belgrade, Serbia
Posts: 319
Quote:
Originally Posted by Leffmann View Post
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.
DanScott is offline  
Old 06 March 2016, 20:37   #9
Leffmann
 
Join Date: Jul 2008
Location: Sweden
Posts: 2,197
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.

Last edited by Leffmann; 27 March 2018 at 21:26.
Leffmann is offline  
Old 10 March 2016, 10:52   #10
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Belgrade, Serbia
Posts: 319
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
DanScott is offline  
Old 11 March 2016, 00:04   #11
Asman
68k

Asman's Avatar
 
Join Date: Sep 2005
Location: Somewhere
Posts: 654
Quote:
Originally Posted by DanScott View Post
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 ?
Asman is offline  
Old 11 March 2016, 00:14   #12
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Belgrade, Serbia
Posts: 319
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
DanScott is offline  
Old 11 March 2016, 01:16   #13
Leffmann
 
Join Date: Jul 2008
Location: Sweden
Posts: 2,197
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.
Leffmann is offline  
Old 15 March 2016, 12:49   #14
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Belgrade, Serbia
Posts: 319
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...)


Code:
		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
DanScott is offline  
Old 15 March 2016, 14:04   #15
Don_Adan
Registered User
 
Join Date: Jan 2008
Location: Warsaw/Poland
Age: 50
Posts: 1,083
Quote:
Originally Posted by DanScott View Post
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:

Code:
		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
Don_Adan is offline  
Old 15 March 2016, 14:14   #16
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Belgrade, Serbia
Posts: 319
thanks just saw it..

it is little things like this that I tend to miss
DanScott is offline  
Old 15 March 2016, 14:40   #17
Asman
68k

Asman's Avatar
 
Join Date: Sep 2005
Location: Somewhere
Posts: 654
Other obvious optimization is when EB_YPos = 0.

I found another one: (based on Don_Adan post #15 - cheers Don ).
Code:
		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

Last edited by Asman; 15 March 2016 at 14:55. Reason: added information about on which version source is based
Asman is offline  
Old 15 March 2016, 14:51   #18
Don_Adan
Registered User
 
Join Date: Jan 2008
Location: Warsaw/Poland
Age: 50
Posts: 1,083
Next small optimisation:

Code:
		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.

Last edited by Don_Adan; 15 March 2016 at 14:56.
Don_Adan is offline  
Old 15 March 2016, 14:58   #19
Asman
68k

Asman's Avatar
 
Join Date: Sep 2005
Location: Somewhere
Posts: 654
@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 ?
Asman is offline  
Old 15 March 2016, 15:28   #20
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Belgrade, Serbia
Posts: 319
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
DanScott is offline  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Translating sprite coordinates to playfield coordinates nandius_c Coders. Asm / Hardware 15 01 August 2014 00:17
32 and 64 bit sprite control words question FrenchShark Coders. General 8 10 January 2008 03:32
Cpu problems...in other words, BRAIN oldpx support.Hardware 2 24 March 2003 23:01
Swear words Kodoichi project.EAB 19 14 December 2001 01:53

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 07:19.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2018, vBulletin Solutions Inc.
Page generated in 0.09865 seconds with 12 queries