English Amiga Board


Go Back   English Amiga Board > Coders > Coders. Language > Coders. Blitz Basic

 
 
Thread Tools
Old 17 June 2018, 14:33   #101
Master484
Registered User
Master484's Avatar
 
Join Date: Nov 2015
Location: Vaasa, Finland
Posts: 323
Quote:
This sounds like a good use case for macros - effectively automated loop unrolling, where you can leave your code referencing the macro, and the compiler will insert the subroutine at compile time for you.
Yeah I know about macros, and some day I'll probably try to learn how to use them.

Quote:
I need to check the syntax but you should be able to replace the direction change "multiplication by - 1" with a negation and an addition (dir = (~dir) + 1). Assuming two's complement.
I'll check if this is possible, but I'm not sure if that sort of variable change trick from positive to negative and vice versa can be done.

Quote:
I only ask because some times I know it seems strange but seems to be quicker sometimes than spaghetti, especially when you have loops in loops.
Hmm, I don't know why that would happen, but I guess it's possible, and this is one thing that could be tested.

Quote:
That's just absurd. Are there any edge cases RectsHit must handle? Otherwise I can't understand how Acid Software could come up with a library routine that is slower than basic.
The 4 IF method means the technique where 4 nested IF..End IFs are used, and where the checks dont progress to the next IF unless the previous IF was true.

Although RectsHit is faster in the case where the collision actually happens, in most non-collision cases the 4 IFs is faster.

I made a quick test that compared RectsHit against the 4 IF.
Code:
loop=0

x = 5
y = 5
a = 5
b = 5

Repeat

If RectsHit (x,y,16,16,a,b,16,16) then hit = 1

If x + 20 > a
 If x < a + 20
  If y +20 > b
   If y < b +20
    hit = 1
   End If
  End If
 End If
End If

loop + 1

Until loop = 1000
Results for RectsHit:

Hit happens = Frame 3 Vpos at 240
No hit = Frame 3 Vpos at 80

Results for 4 IF method:

4 IFs processed, hit happens = Frame 4 Vpos at 28
4 IFs processed, no hit = Frame 3 Vpos at 274
3 IFs processed, no hit = Frame 3 Vpos at 106
2 IFs processed, no hit = Frame 2 Vpos at 239
1 IF processed, no hit = Frame 2 Vpos at 67

---

So only if the checks progress to the 3rd IF, then RectsHit is faster.

But when you have a scenario where bullets randomly bounce in screen, then the first IF always eliminates approximately half of the bullets.

Because the first IF makes an "is bullet right side larger than target left side" check, then all smaller x values cause a fail, and the checks dont progress past the first IF. On a scenario where all bullets and objects are at random places in the screen, this means that about 50 % of the bullets will fail this first test.

And for those 50 % of bullets that pass the first test, then comes the second IF, that checks "is bullet left side smaller than target right side". This second check eliminates almost all cases in the screen, because with these X checks we have actually cheked entire two halves of the screen, and only a very small "corridor" still remains between the targets left and right wall + some small offsets.

And the 3rd and 4th IF checks only happen for those objects that are inside this corridor. This is the worst case scenario, and the point where speed starts to drop in comparison to RectsHit. But it happens so rarely, that it doesn't matter.

---

Another benefit of the 4 IF is that you can have many versions that check things in different order. For example if player bullets travel upwards only, then for them it makes sense to make the "Is bullet top side smaller than target bottom side" first, to maximize the cases where the checks stop at the first IF.
Master484 is offline  
AdSense AdSense  
Old 17 June 2018, 17:08   #102
Retro1234
Bo Bo

Retro1234's Avatar
 
Join Date: Jun 2006
Location: 5150
Posts: 3,911
4 IF method lol - Bounding Box and it should be more like 8 IFs or the use of up/down symbol or your checking 1 box against only one point of the other box.

I still find it unlikely to be faster than inbuilt collision.

Last edited by Retro1234; 17 June 2018 at 17:14.
Retro1234 is offline  
Old 18 June 2018, 13:43   #103
Master484
Registered User
Master484's Avatar
 
Join Date: Nov 2015
Location: Vaasa, Finland
Posts: 323
Quote:
I still find it unlikely to be faster than inbuilt collision.
Believe it or not, it's true.

The speed of the 4 IFs is based on the fact that in most cases it only checks one or two IFs. The third and fourth IF almost never get executed.

But despite this, this is a true and accurate bounding box collision method.

The logic of how this 4 IF collision check works is reverse: instead of trying to find out if a collision has happened, it tries to find out the first condition where we can rule that a collision HAS NOT happened, and it tries to do this as fast as possible, with the least amount of checks possible.

If the screen has 100 bullets and 100 targets, then in 50 % of the cases the first IF is enough, because almost 50 % of the time bullet X will be smaller than target X. And the second IF does the same check but for other X direction, this time checking if bullet X is bigger than target X. And therefore after the second IF has been executed, 80 % to 90 % of the bullets have failed the test, because they were in the areas where a collision with the target cant happen. And so the last two IFs only happen for some 20 % to 10 % of the bullets, and these two last IFs check the targets in the narrow vertical corridor in the screen that still remains.

Quote:
checking 1 box against only one point of the other box
I don't think this would be any faster. There would still need to be 4 IFs, because we would be checking 4 box walls against one (X,Y) point. So 2 checks for X axis and 2 checks for Y axis.

One method that would be faster would be if both boxes would have a XY point in the middle, and we would check the X and Y distance difference of the two points. But such a mathematical operation results in either a negative or positive value, like this:

X1 = 50
X2 = 70

X1 - X2 = -20
X2 - X1 = 20

But if there would be a fast way or a fast command to convert values from negative to positive and the other way around, then this would be the method to use.

---

And also I tested the Gosubs inside a For...Next, and I didn't see any speed boost for using Gosubs. But I only tested a simple case of two nested For...Nexts, where I put the inner one to a gosub.

---
---

But anyways I have found one other way to speed up the demo that I posted: I divided the screen into 4 "hit zones", and gave each enemy a variable that tells in which zone it is. And then I added a 5th IF to the 4 IF checks, which checks the bullets zone vs enemys zone. This ruled out 75 % of collisions cases right away, and brought a nice speed boost, although not as much as I hoped.

I'll post the updated demo version soon.
Master484 is offline  
Old 18 June 2018, 15:04   #104
Shatterhand
Warhasneverbeensomuchfun

Shatterhand's Avatar
 
Join Date: Jun 2001
Location: Rio de Janeiro / Brazil
Age: 35
Posts: 2,930
Quote:
One method that would be faster would be if both boxes would have a XY point in the middle, and we would check the X and Y distance difference of the two points. But such a mathematical operation results in either a negative or positive value, like this:

X1 = 50
X2 = 70

X1 - X2 = -20
X2 - X1 = 20

But if there would be a fast way or a fast command to convert values from negative to positive and the other way around, then this would be the method to use.
This really could be fast, but like you said (and I also proved it here), the ABS command is incredibly slow. There should be some way to do it faster.
Shatterhand is offline  
Old 18 June 2018, 15:09   #105
E-Penguin
Banana

 
Join Date: Jul 2016
Location: Darmstadt
Posts: 570
Only four checks are required to test overlaps of two axis-aligned bounding boxes.

The "zones" concept is analogous to the "cells" approach, but with vary large cells. There's probably a happy medium between cell/zone size and memory/computation tradeoff. I'm going to propose 16, as it's a nice power of 2
E-Penguin is offline  
Old 18 June 2018, 16:42   #106
Retro1234
Bo Bo

Retro1234's Avatar
 
Join Date: Jun 2006
Location: 5150
Posts: 3,911
4 point on a bullet only checks 1 point on an enemies that's no good.
Retro1234 is offline  
Old 18 June 2018, 16:46   #107
Shatterhand
Warhasneverbeensomuchfun

Shatterhand's Avatar
 
Join Date: Jun 2001
Location: Rio de Janeiro / Brazil
Age: 35
Posts: 2,930
Quote:
Originally Posted by Retro1234 View Post
4 point on a bullet only checks 1 point on an enemies that's no good.
Look at Master484 code again. He is testing bounding box against bounding box with just 4 ifs.
Shatterhand is offline  
Old 18 June 2018, 16:48   #108
Retro1234
Bo Bo

Retro1234's Avatar
 
Join Date: Jun 2006
Location: 5150
Posts: 3,911
Ok I haven't looked, you can do it if you check the distance in-between otherwise your only checking one box against one pixel of the other object.
Retro1234 is offline  
Old 18 June 2018, 16:52   #109
Shatterhand
Warhasneverbeensomuchfun

Shatterhand's Avatar
 
Join Date: Jun 2001
Location: Rio de Janeiro / Brazil
Age: 35
Posts: 2,930
His code is written above.

Code:
If x + 20 > a
 If x < a + 20
  If y +20 > b
   If y < b +20
It's testing a 20x20 box against another 20x20 box.
Shatterhand is offline  
Old 18 June 2018, 17:57   #110
Retro1234
Bo Bo

Retro1234's Avatar
 
Join Date: Jun 2006
Location: 5150
Posts: 3,911
Not sure
Just Width
IF X or X+Width > A-1 and < A+Width2 : Then hit
Retro1234 is offline  
Old 18 June 2018, 20:09   #111
E-Penguin
Banana

 
Join Date: Jul 2016
Location: Darmstadt
Posts: 570
Quote:
Originally Posted by Shatterhand View Post
This really could be fast, but like you said (and I also proved it here), the ABS command is incredibly slow. There should be some way to do it faster.
You should be able to test the status register after the subtract and if negative negate the result. I'm not near a compiler right now but something like...
Code:
Function FastAbsDiff{a.w, b.w}
;a is in d0
;b is in d1

sub.w d1, d0 ;result in d0
bmi .resultIsNegative

AsmExit ;end statement if result is positive 

.resultIsNegative 
neg d0 ; negate it
AsmExit ; 

End Function

NPrint FastAbsDiff{3,4}
--edited to add--
Close; this seems to work. Use in place of ABS(a - b)
Code:
Function.w AbsDiff{a.w, b.w}
  SUB.w d1, d0
  BMI adIsNeg
  JMP adReturn
adIsNeg:NEG.w d0
adReturn: AsmExit
End Function

NPrint AbsDiff{100,3}
NPrint AbsDiff{3,100}
prints 97 in both cases

-- edited again to add... --
I've done a quick compare to ABS(a-b) and the performance is practically identical. Damn.

Last edited by E-Penguin; 18 June 2018 at 21:58.
E-Penguin is offline  
Old 19 June 2018, 19:14   #112
Master484
Registered User
Master484's Avatar
 
Join Date: Nov 2015
Location: Vaasa, Finland
Posts: 323
Quote:
I've done a quick compare to ABS(a-b) and the performance is practically identical. Damn.
Thanks for doing the tests with the ABS function.

I have tried to solve this problem on paper, trying to come up with formulas for counting the distance between X1 and X2, that would always bring either a negative or positive value as a result, no matter in which order the two values are, but it seems to be impossible.

---



But an updated version of the demo is now ready, and the ADF with source is in the attachment of this post.

It now uses the Display library instead of Slice library, and lots of small improvements have been made. The structure is better and code faster.

Also I added some sprites, press 7 and 8 to activate them. The Display Librarys CustomSprites command is used to multiplex all 8 sprites once at VPOS 100, which brings 16 sprites to screen. But the limitation of this method is that placing sprites to that multiplex Y line causes side effects. But surely it can be used for something.

The four hit-zones method that I mentioned is not used, because it caused "dead-zones" to the screen where collisions didn't register, and the speed increase in collisions was pretty much negated by having to count the zones for every object each frame.

I also tested sorting both the enemies and bullets by the Y-axis with the SortList command, and then tried to use this to limit the amount of list browsing. But the sorting took too much time, and the result was too slow, even if just the enemy collection was sorted each frame.

But, despite this, the program is now faster. The performance now is this on standard A500 without fast RAM, with cycle exact ON:

Drawing speed at 50 FPS:

Enemies: 29
Bullets: 43

Collision speed at 50 FPS:

1 enemy vs 37 bullets
10 enemies vs 14 bullets
16 enemies vs 8 bullets

---

So it's just a small improvement, it can do 1 or 2 bullets more depending on case, but better than nothing.

And the HIT text is still drawn every frame, so maybe 1 bullet is lost this way.

But the key to understanding these figures is that checking all bullets against just one target is very fast. It's only the 10 vs 10 scenarios that cause serious slowdown.

So we can have a game with many aliens, like 16, and the aliens can easily shoot 10 bullets, if the only collision check needed for those bullets is against the player.

But when player shoots, this is which causes the slowdown, because now all bullets have to checked against all aliens, and there aren't any real way to avoid this.

And so I think that the key to achieve good speed is to handle player bullets vs aliens collisions with the fast Blitz sprite collision commands as much as possible. I'm pretty sure this is the way it's done in every Amiga shooter that runs at 50 FPS. So either aliens or the player bullets need to be sprites. If both are BOBs, then the collision check cant use the sprite collisions commands, and slowdown is unavoidable.

So with this engine we could maybe have a game with 16 BOB enemies + maybe 10 enemy BOB bullets + player as a sprite + at least 6 player bullets made with sprites + maybe some more bullets or aliens or other stuff made with the sprite multiplexing trick. And that would still surely run at 50 FPS.
Attached Thumbnails
Click image for larger version

Name:	CollisionTestV71_002.png
Views:	42
Size:	17.0 KB
ID:	58604  
Attached Files
File Type: zip CollisionTestV71.zip (36.7 KB, 8 views)

Last edited by Master484; 19 June 2018 at 19:28.
Master484 is offline  
AdSense AdSense  
 


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

Similar Threads
Thread Thread Starter Forum Replies Last Post
SetCol/DoColl-How to test collisions with different sprites against different colors? Shatterhand Coders. Blitz Basic 1 12 January 2017 18:51
Quickest code.... Galahad/FLT Coders. Asm / Hardware 10 01 January 2017 17:23
[REQ:ASM] Sprite collisions basics jman Coders. Tutorials 5 03 September 2011 00:07
What is the quickest way Doc Mindie support.WinUAE 6 17 October 2007 21:15
Disable Sprite Collisions DeAdLy_cOoKiE Retrogaming General Discussion 4 24 March 2006 17:56

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 16:39.


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