English Amiga Board


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

 
 
Thread Tools
Old 23 January 2019, 00:10   #21
Chrille
Registered User

 
Join Date: Sep 2018
Location: Germany
Posts: 13
Quote:
Originally Posted by zero View Post
Do you need a linked list? Why not just build a linear list every frame as you go through rendering objects?

Actually it might be faster to avoid the list entirely. If your collision map is only 40x32 (8x8 tiles on a 320x256 screen) just allocate 1.2k of RAM to it and have one byte per block. Write a 1 to any block with an object in it, and then you can test for collisions with all objects with a single check of one byte. No need to clear it, just write a 2 into it next frame and check for that.
This was a very dynamic bomberman clone. You could play it with up to 10 players at once. In theory there was no maximum of objects per 16x16 Pixel tile or the maximum number of objects would be very high, i.e. more than 10 objects (players) per 16x16 pixel tile. And most of the objects do not move, for example bombs are not moving unless there was an impulse from somewhere (e.g. from a assembly line).

Another reason was the main platform was for 68020+ (A1200 AGA) and AFAIK there it does not matter if you access a byte or longword (both are single memory accesses).

But your suggestion could be very good for a shoot'em up like inviyya, especially the part, write a value for one frame and increase the value the next frame. May be you have to go through the array and clear a part of the array to avoid wrong collisions after 255 frames ...

Last edited by Chrille; 23 January 2019 at 00:46.
Chrille is offline  
Old 23 January 2019, 11:58   #22
Steril707
OCS rocks!

 
Join Date: Sep 2016
Location: Amiga Island
Posts: 619
Quote:
Originally Posted by zero View Post
Actually it might be faster to avoid the list entirely. If your collision map is only 40x32 (8x8 tiles on a 320x256 screen) just allocate 1.2k of RAM to it and have one byte per block. Write a 1 to any block with an object in it, and then you can test for collisions with all objects with a single check of one byte. No need to clear it, just write a 2 into it next frame and check for that.
I have a system like this running for the background checks.

The "speed problem" with this is, that you need to translate the x and y positions to the collision map with shifts and additions. Or do you have any better way to handle this that I just don't see at the moment?

I am not really sure if this is much faster then a simple cmp cascade per object.
Steril707 is offline  
Old 23 January 2019, 12:54   #23
Chrille
Registered User

 
Join Date: Sep 2018
Location: Germany
Posts: 13
Quote:
Originally Posted by Steril707 View Post
I have a system like this running for the background checks.

The "speed problem" with this is, that you need to translate the x and y positions to the collision map with shifts and additions. Or do you have any better way to handle this that I just don't see at the moment?

I am not really sure if this is much faster then a simple cmp cascade per object.
At least you could optimise the size of this collision map, do not take this "odd" value like 40 and take instead an even value like 64. This would be a single shift instead of multiple shifts and additions or a single multiplication.

IMHO A comparsion of these two approaches is worth. Especially when you have to compare many objects with other many objects. But when you have only a single object which muste be compared to all objects, it is not worth.
Chrille is offline  
Old 23 January 2019, 13:04   #24
roondar
Registered User

 
Join Date: Jul 2015
Location: The Netherlands
Posts: 745
The problem with more complicated systems for collision detection is that you do fewer checks, but the checks themselves become more expensive. It all depends on how complicated each check and how many objects are involved is what is actually faster.

Case in point, the grid mentioned in the previous few posts definitely works, but might need extra writes/reads when objects don't align neatly to a tile or are bigger than a single tile. I'd guess such an approach suits games like Bomberman better than a shoot em up due to the 'tiled' nature of a Bomberman game (most objects are one tile in size and most objects occupy exactly one tile).

IMHO for small numbers of objects and the game running on a basic 68000, a simple loop doing a bunch of compares if probably the best idea. The main 'trick' there is to choose the correct axis to test first so as to remove as many objects from the rest of the compare as early as possible. I'd suggest always testing one full axis first as that removes most objects using one or two compares (consider the size of the ship vs the screen) and only requires three or four compares in a smaller number of cases.

For as few as 10 enemies, I'd say that it'll be pretty hard to beat the best case scenario of a compare loop (i.e. 10x cmp & branch which'll cost something like 20-30 cycles a go) and even the worst case (i.e. 10x 4 compares & branches costing about 100 cycles a go) will be hard to beat. Consider how many cycles a 68000 would take to update a single grid entry in the tiled approach vs doing a compare & branch:

Code:
; There are multiple implementations possible here, I've chosen to assume a single dimension array containing the pointers to each Y offset into the tilemap exists and each tile takes up one byte. Also note the code below is very much simplified - with this code you can't actually tell what you've collided with, only that you have collided with something.

; X in D0, Y in D1, pointer to Y offsets of tiles in A1 to skip multiply requirement
; First column is number of cycles taken
14	asr.w	#4,d0		; divide X by 16
10	asr.w	#2,d1		; divide Y by 4
 8	and.w	#$fffc,d1 	; clear lower 2 bits of Y to get offset into Y-array
18	move.l	0(a1,d1),a2 	; Y coordinate in A2
14	move.b	#1,0(a2,d0) 	; Set tile to 1 to indicate a present object
--+
64 cycles

For reference, a compare & branch takes
12	cmp.w	d(an),dn
10	db<cc> or b<cc>	.lp
--+
22 cycles
As discussed, the grid might require multiple writes depending on object alignment and size and will likewise frequently require multiple tiles to be tested for the actual collision.

Do note that I'd agree the grid will work (much) better as more and more enemies get added as the overhead is relatively static, but I'm not really convinced it'll actually be faster when testing only 10 objects vs the player.
roondar is offline  
Old 23 January 2019, 14:46   #25
zero
Registered User

 
Join Date: Jun 2016
Location: UK
Posts: 229
Quote:
Originally Posted by Steril707 View Post
The "speed problem" with this is, that you need to translate the x and y positions to the collision map with shifts and additions. Or do you have any better way to handle this that I just don't see at the moment?
Don't you calculate a lot of that stuff for the blitter anyway?

Another option might be to add an extra hidden bitplane that just has a collision map. It doesn't get displayed so doesn't eat up DMA cycles, but obviously adds extra load on the blitter. It depends where your bottleneck is.

I said you can check collisions every other frame, for some stuff like maybe the scenery it could be even less than that. In Super Mario Bros it only checks for collision with the flag pole at the end of the level every 27 frames! Stuff like updating the score isn't high priority.
zero is offline  
Old 23 January 2019, 14:48   #26
Chrille
Registered User

 
Join Date: Sep 2018
Location: Germany
Posts: 13
@roondar:
okay, your example was quick and dirty But your example is more expressive than my writings

You can optimize a lot in your example:
If this is run in a loop, you can put all constants to free data registers and save 8 cycles.

Anoter approach is, you could avoid a lookup tables, if the collision map width is a power of 2, e.g. use a map-width of 64 instead of 40 or 32 instead of 20. And use instead a single shift instruction. Yes, this will also consume a lot of time.

We are going d'accord that for a single player object it is not beeing worth. On the other side you may have many bullets, that also need a collision detection with background and enemies. And depending on the design enemies could also interact with other objects or background. Then you have to do the calculation to a screen map anyways.
Chrille is offline  
Old 23 January 2019, 14:55   #27
zero
Registered User

 
Join Date: Jun 2016
Location: UK
Posts: 229
Quote:
Originally Posted by roondar View Post
Case in point, the grid mentioned in the previous few posts definitely works, but might need extra writes/reads when objects don't align neatly to a tile or are bigger than a single tile. I'd guess such an approach suits games like Bomberman better than a shoot em up due to the 'tiled' nature of a Bomberman game (most objects are one tile in size and most objects occupy exactly one tile).
The tile method massively reduces the number of tests though.

For example, say you fill tiles with an index number for each enemy. Now rather than testing every player bullet against every enemy, you just do read per bullet to see which enemy it hit. The number of writes per enemy scales with enemy size, but so does the blit time which is going to be a far bigger issue than a few memory writes.

No need to do read-modify-write either, don't worry about over-writing as enemies rarely overlap and when they do it's not clear which one should be hit anyway. No need to clear the grid, just keep toggling bit 7 in your writes/compares.

Also don't worry too much about accuracy. With a fast moving game the player won't notice. When you look at most shoot-em-ups from the 80s and early 90s the collision detection is less than pixel perfect, certainly for enemies, and the small hit boxes obscure that fact. You can do a more accurate bounding box for the player only if required.
zero is offline  
Old 23 January 2019, 15:35   #28
roondar
Registered User

 
Join Date: Jul 2015
Location: The Netherlands
Posts: 745
Quote:
Originally Posted by Chrille View Post
@roondar:
okay, your example was quick and dirty But your example is more expressive than my writings

You can optimize a lot in your example:
If this is run in a loop, you can put all constants to free data registers and save 8 cycles.

Anoter approach is, you could avoid a lookup tables, if the collision map width is a power of 2, e.g. use a map-width of 64 instead of 40 or 32 instead of 20. And use instead a single shift instruction. Yes, this will also consume a lot of time.
I agree my example can be optimised a bit, but it's not that relevant (nor always easy - you might need those registers you wish to use elsewhere and a power of two grid limits you in other ways even though it is usually faster to shift left by several places than it is to lookup via a table - which itself is faster than requiring a multiply).

The point is that you add on extra overhead for keeping track of the grid and then later reading back from the grid. Even if this is fairly small, it's still extra time you have to make up for in the actual collision testing. For large numbers of objects such an approach makes perfect sense but for smaller numbers I'm still unconvinced.

Remember, my code only shows a single access - it's fairly likely you'll actually need to do four accesses during store (objects that are not tile aligned need up to four tiles in the grid 'set') and again during read. Which either requires additional code to check for how many tiles to set or means taking the 'hit' of always setting four tiles regardless of alignment. Neither is optimal, both take quite a bit of extra time.

All in all, I'm pretty certain that the per object cost is going to be much higher when using a grid. It will be made up for when you check larger numbers of objects, but the question remains how many objects (on average) you'd need for it to make sense.

Quote:

We are going d'accord that for a single player object it is not beeing worth. On the other side you may have many bullets, that also need a collision detection with background and enemies. And depending on the design enemies could also interact with other objects or background. Then you have to do the calculation to a screen map anyways.
The last version of the grid (as presented) does not seem to be suitable for bullet-to-enemy collisions as is, because it doesn't seem to track what object is where (only that some object is at some position) so you'd have no way of knowing how to handle the bullets. The earlier concept of the linked list does work here, as could a version that notes object numbers somehow - but both of those are more complicated so require extra objects to be faster.

Don't take me wrong, I do feel a tile based system is a good way to make things faster, but it requires the right circumstances to be viable. Simply put, I'm just not so sure that 12 enemy objects is enough for it to be 'winning' and I'm not in a position to write the code to test it at the current time. So it could be faster, but I'm not feeling it yet.


---
Quote:
Originally Posted by zero View Post
The tile method massively reduces the number of tests though.

For example, say you fill tiles with an index number for each enemy. Now rather than testing every player bullet against every enemy, you just do read per bullet to see which enemy it hit. The number of writes per enemy scales with enemy size, but so does the blit time which is going to be a far bigger issue than a few memory writes.
I realize this fully and don't dispute it. However, you do need up to four index writes per enemy due to alignment issues and, as I've said before, the actual reading/writing of the grid does cost more and this extra time spent must be 'won back' by having the now more expensive tests being so small in number as to cost fewer cycles than the 'cheaper' test that needs to run more times.

This is the core of my point - I'm not disputing fewer tests are needed, just pointing out that a simple bounding box test is really rather cheap and this, coupled with there only being about 12 objects to check, limits the gains that can be made this way.

But again, given enough objects and optimal code, I certainly agree a grid will outperform a simple bounding box loop.

Quote:
No need to do read-modify-write either, don't worry about over-writing as enemies rarely overlap and when they do it's not clear which one should be hit anyway. No need to clear the grid, just keep toggling bit 7 in your writes/compares.
I'm not convinced you never need to do any clearing. I'd agree you can mostly avoid it, but the devil is in the details and a life lost due to a non-existent enemy colliding with the player is a pretty big no-no. Perhaps I'm just not seeing how you can guarantee you don't need a clear more than anything else.

Quote:
Also don't worry too much about accuracy. With a fast moving game the player won't notice. When you look at most shoot-em-ups from the 80s and early 90s the collision detection is less than pixel perfect, certainly for enemies, and the small hit boxes obscure that fact. You can do a more accurate bounding box for the player only if required.
That depends on the situation. I'm pretty certain players would notice bullets skipping through enemies, which is a possible problem given that bullets tend to move fairly quickly. However, for player vs enemies or scenery you are most certainly correct.

Last edited by roondar; 23 January 2019 at 15:52. Reason: Added reply to zero
roondar is offline  
Old 23 January 2019, 16:45   #29
Master484
Registered User
Master484's Avatar
 
Join Date: Nov 2015
Location: Vaasa, Finland
Posts: 340
Some time ago there was discussion about collisions in the Blitz forum too:
http://eab.abime.net/showthread.php?t=92900

In that thread we found out that the "Player Bullets" type objects were by far the biggest slowdown causer, because 10 bullets vs 10 aliens needed 10*10 = 100 checks, and those 100 checks were multiplied further by the complexity of the checks themselves.

Back then I made a small test program, and the "bounding box version" of it could handle the following collision amounts per frame on A500:

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

These were the worst case "all vs all" checks, and only half of the bullets were checked each frame. Demo was dual PF, enemies were 16*16 and bullets 8*8, and drawing and moving them + doing those checks took the whole frame.

But I wonder if this is a good result? How many "all vs all" collisions checks could one expect to do in a game made 100% in assembler, using basic bounding box checks? Would it be more than those values, or something similar?
Master484 is offline  
Old 23 January 2019, 16:59   #30
zero
Registered User

 
Join Date: Jun 2016
Location: UK
Posts: 229
Quote:
Originally Posted by roondar View Post
I realize this fully and don't dispute it. However, you do need up to four index writes per enemy due to alignment issues and, as I've said before, the actual reading/writing of the grid does cost more and this extra time spent must be 'won back' by having the now more expensive tests being so small in number as to cost fewer cycles than the 'cheaper' test that needs to run more times.
You don't need to do 4 writes. Just ignore the alignment issues, make the player shots a 4x4 grid if necessary. It actually helps to make the player shots large and fast here.

The tests aren't more expensive either. Calculate the grid index, which you need to mostly do for the blitter set up anyway, and then check one number. Compare to doing up to four tests per object on screen.

Quote:
coupled with there only being about 12 objects to check, limits the gains that can be made this way.
That I have to agree with, for a small number of objects a bounding box check will be faster.

But is the number of objects small? Say 10 enemies, 5 enemy bullets, 5 player bullets. You need to check:

Player to 10 enemies
Player to 5 enemy bullets
5 player bullets to 10 enemies (total 50)

So that's 65 checks, before you even started with player to scenery, and player bullets to scenery.

Quote:
I'm not convinced you never need to do any clearing. I'd agree you can mostly avoid it, but the devil is in the details and a life lost due to a non-existent enemy colliding with the player is a pretty big no-no. Perhaps I'm just not seeing how you can guarantee you don't need a clear more than anything else.
You may be right, but you can combine clearing with clearing bobs or just throw the blitter at it. I guess it's that threshold where it becomes faster again.

Quote:
That depends on the situation. I'm pretty certain players would notice bullets skipping through enemies
You have the same problem with bounding boxes. Of course you have to make the hit box larger for player bullets. Again, many shooters do this, favouring the player's shots. Players seem to like having massive, overwhelming fire power with big, fast bullets.
zero is offline  
Old 23 January 2019, 17:57   #31
Steril707
OCS rocks!

 
Join Date: Sep 2016
Location: Amiga Island
Posts: 619
Quote:
Originally Posted by Master484 View Post
]

In that thread we found out that the "Player Bullets" type objects were by far the biggest slowdown causer, because 10 bullets vs 10 aliens needed 10*10 = 100 checks, and those 100 checks were multiplied further by the complexity of the checks themselves.

)
I think that's my problem here...
Steril707 is offline  
Old 23 January 2019, 18:06   #32
roondar
Registered User

 
Join Date: Jul 2015
Location: The Netherlands
Posts: 745
Quote:
Originally Posted by zero View Post
You don't need to do 4 writes. Just ignore the alignment issues, make the player shots a 4x4 grid if necessary. It actually helps to make the player shots large and fast here.
Making the player bullets bigger to compensate simply moves the problem one step. Instead of 4 writes and 4 reads you're suggesting 1 write and 16 reads. Surely you can see why this is not optimal?

Furthermore, while I agree you don't need 100% accuracy, what you're suggesting really is very inaccurate: a 4x4 grid for bullets means you'll hit enemies well over 64 pixels away from the bullet ! That level of inaccuracy will, IMHO, be notable even in a fast game.

TBH I'm not even sure this 4x4 thing isn't a typo on your end. I'm assuming you meant 2x2 for the remaining part of my reply.
Quote:

The tests aren't more expensive either. Calculate the grid index, which you need to mostly do for the blitter set up anyway, and then check one number. Compare to doing up to four tests per object on screen.
Combining object collision updates with the Blitter is an interesting idea.

However, 'mostly' here feels like more than a bit of an overstatement. The only part you get to do during Blitting a bob that is similar enough to be useful is the X coordinate to X address offset conversion vs X to X grid offset (both are divisions by 16). Y coordinates won't work as they are not grid based at all for the Blitter, nor will the actual offset into the grid. I'd really be surprised if this actually saves you all much compared to separately calculating the grid (if anything at all) once you take into account that most Bob Blitting routines I've seen use quite a few registers already and you're now squeezing extra stuff in.

Testing itself is at least 'as expensive' as you yourself point out just above here that you need to check more than one entry on top of needing to write additional information into a grid. A simple bounding box test requires 4 compares (max), but only one compare (min). The grid method requires at least a number of tests that is equal to a 'worst case' bounding box test (i.e. at least 4 compares because we check objects vs a 2x2 grid). The grid also requires you to calculate what element of the grid to check during collision detection, which is not needed at all for the bounding box.

Quote:
That I have to agree with, for a small number of objects a bounding box check will be faster.

But is the number of objects small? Say 10 enemies, 5 enemy bullets, 5 player bullets. You need to check:

Player to 10 enemies
Player to 5 enemy bullets
5 player bullets to 10 enemies (total 50)

So that's 65 checks, before you even started with player to scenery, and player bullets to scenery.
Indeed, if you have 20 objects quite a lot of tests are needed.

Now, in the grid you'll have to calculate grid locations and write 20 objects to the grid (assuming the level of inaccuracy you feel is OK actually works out in 'the real world') and do 24 grid location calculations + tests (4 tests per player/bullet). You can probably optimise the testing grid location calculations by doing one calculation per object and using offsets instead of doing 4 calculations though.

So yes, the grid does quite a bit fewer comparisons+writes than the bounding box will. The question I have is still: are 44 grid operations more or less expensive than 65 bounding box operations (which basically means running between 65 and 260 cmp's plus branches) and can you actually get away with dealing with the grid in the way you suggest and still have a game that has collision detection that is 'good enough'.

It's clear you feel the answer is that the grid as you describe it is 'good enough' and cheaper.

Whereas I feel you're overestimating the cost of the bounding box checks vs working with grid (even though it does seem likely that up to 260 compares is probably slower than 44 grid writes or checks + location stuff) and more importantly overestimating just how inaccurate collision detection can be before it starts being too inaccurate to be fun.

Without actual tests, I don't think either of us are going to shift position much here. But, as I said before - given enough objects (whether this is 10, 20, 30 or 100) the grid will win. It's all about where this threshold is and if the grid as you describe it is 'good enough'. Considering the difference in tests done at the worst case (i.e. 44 vs 260) I'm conceding the grid as you describe it will likely be faster. But I'm still not convinced about the accuracy.

Quote:
You may be right, but you can combine clearing with clearing bobs or just throw the blitter at it. I guess it's that threshold where it becomes faster again.
Indeed.

Quote:
You have the same problem with bounding boxes. Of course you have to make the hit box larger for player bullets. Again, many shooters do this, favouring the player's shots. Players seem to like having massive, overwhelming fire power with big, fast bullets.
Bounding boxes have the same problem, this is true. But you'll clearly have them far less often when you use 'real coordinates' vs 'grid coordinates + ignoring alignment'. And again, making the boxes bigger only counts for so much before it becomes a distraction.

Remember: many, many Amiga games are criticized for having poor collision detection.

---
Quote:
Originally Posted by Master484 View Post
But I wonder if this is a good result? How many "all vs all" collisions checks could one expect to do in a game made 100% in assembler, using basic bounding box checks? Would it be more than those values, or something similar?
It all depends, really. The display+Bobs in your example will take up quite a bit of raster time in your example (somewhere like 67-80% of all raster time will be taken up by doing just the blits and displaying the screen, depending on how big the screen is exactly and how the Bobs are blit).

If the bounding box check is run 128 times you should still have something like 10-15% of raster time left. This may not sound like much, but that amounts to 30% to 50% of all CPU time you had left to begin with.

Last edited by roondar; 23 January 2019 at 18:45. Reason: Added reply to Master484
roondar is offline  
Old 23 January 2019, 19:28   #33
zero
Registered User

 
Join Date: Jun 2016
Location: UK
Posts: 229
Quote:
Originally Posted by roondar View Post
Making the player bullets bigger to compensate simply moves the problem one step. Instead of 4 writes and 4 reads you're suggesting 1 write and 16 reads. Surely you can see why this is not optimal?
I think you misunderstand me here. I don't know where you get 16 reads from.

What I mean is that the bullet graphic doesn't have to match the hit box, just like the player one doesn't. Having a slightly bigger graphic helps mask the less accurate hit box.

You can do it the other way around too. Small graphic, over-size hit box for the bullet, over-size graphic and small hit box for the enemies.

Do you mean 16 reads because of the over-size player bullet hit box to cover fast movement? I guess that's true, but I bet it's more efficient than bounding box tests if you have a lot of bullets. Many shooters give the player a very high rate of fire, like Sidewinder or Xenon 2.
zero is offline  
Old 23 January 2019, 19:32   #34
zero
Registered User

 
Join Date: Jun 2016
Location: UK
Posts: 229
Quote:
Originally Posted by Steril707 View Post
I think that's my problem here...
One way of managing it is to change from "I have to do this many collision tests each time" to "this is how many collision tests I can do per frame".

So you might have a loop that does collision tests until the vertical blank interrupt triggers, and then stops. Next frame it picks up where it left off.

You may want to prioritize player bullets so that if things get really busy it favours the player.
zero is offline  
Old 23 January 2019, 20:16   #35
Master484
Registered User
Master484's Avatar
 
Join Date: Nov 2015
Location: Vaasa, Finland
Posts: 340
In Blitz Basic there is one trick that works in Dual Playfield at least, when the playfield where the objects are drawn doesn't have any background graphics.

And the trick goes like this:
1. Clear screen.
2. Draw all enemies first.
3. Then draw bullets.

But before drawing each bullet, make a check if any graphics already exist in the Bitmap at the bullets XY location. So check if the colors present at that spot are anything else than 0. And if some graphics are present, only then make the actual collision checks for that bullet.

And if bullets are small, like 8*8, then checking only one pixels color at the middle of the bullet may be enough for reasonably accurate collision.

In Blitz there are 2 commands to do this sort of color check, called "BlitColl" and "Point", I'm not sure how you would do that in ASM.

This can speed up things quite a lot, because although the color check takes time, it allows us to skip the entire "bullet vs all enemies" list browsing in all those cases when the color at the bullets XY position was 0. And most of the time this is true, because 99 % of the time bullets don't hit anything, and when they do, they usually instantly die.

However this trick only works when there are no background graphics, so the game is Dual PF with backround GFX and game objects in separate playfields.

But maybe it could also work in a 16-color single PF game, if the screen is mostly black space, or if the palette is adjusted in such a way that only certain colors would cause a bullet collision and others would not.
Master484 is offline  
Old 23 January 2019, 22:42   #36
Steril707
OCS rocks!

 
Join Date: Sep 2016
Location: Amiga Island
Posts: 619
Quote:
Originally Posted by zero View Post
One way of managing it is to change from "I have to do this many collision tests each time" to "this is how many collision tests I can do per frame".

So you might have a loop that does collision tests until the vertical blank interrupt triggers, and then stops. Next frame it picks up where it left off.

You may want to prioritize player bullets so that if things get really busy it favours the player.
I think thats the kind of out of the box thinking idea that I needed.

Thanks, Zero...
Steril707 is offline  
Old 24 January 2019, 00:45   #37
roondar
Registered User

 
Join Date: Jul 2015
Location: The Netherlands
Posts: 745
Quote:
Originally Posted by zero View Post
I think you misunderstand me here. I don't know where you get 16 reads from.
It’s certainly possible I misunderstood. I got the 16 reads from your statement that you could make the player bullets a 4x4 grid.

Quote:
What I mean is that the bullet graphic doesn't have to match the hit box, just like the player one doesn't. Having a slightly bigger graphic helps mask the less accurate hit box.

You can do it the other way around too. Small graphic, over-size hit box for the bullet, over-size graphic and small hit box for the enemies.
I agree this can help, but only to a point. If the hit box becomes too large it will be notable. Perhaps this problem occurs later than I think.

Quote:
Do you mean 16 reads because of the over-size player bullet hit box to cover fast movement? I guess that's true, but I bet it's more efficient than bounding box tests if you have a lot of bullets. Many shooters give the player a very high rate of fire, like Sidewinder or Xenon 2.
Of course and I never disputed this. I only disputed the accuracy of the grid system (as you presented it) being good enough and the overhead being super small. We’re actually agreeing for the most part.

—-
@Steril707: one thing to think about is the way you structure data. If collision detection is your bottleneck, it might be worthwhile to make sure your data is stored in such a way you can access it using (an) or (an)+ instead of d(an) or d(an,ix), or perhaps use multiple address registers so you might be abl to avoid using lea in the loop (i.e. have separate one dimensional arrays containing object x and y coordinates rather than using a single array containing both, or storing data in such a way you can make use of movem.w to speed things up, etc). Or perhaps store it in such a way a single move.l or cmp.l can be used instead of two move.w/cmp.w commands.

These micro optimisations won’t make things twice as fast and definitely are bordering on hacks, but it can result in a nice speed up nonetheless.

Last edited by roondar; 24 January 2019 at 01:20.
roondar is offline  
Old 24 January 2019, 10:48   #38
Steril707
OCS rocks!

 
Join Date: Sep 2016
Location: Amiga Island
Posts: 619
@Roondar: I will keep that in mind when I do my final optimizations session late in the project.. Thank you...
Steril707 is offline  
Old 24 January 2019, 11:37   #39
zero
Registered User

 
Join Date: Jun 2016
Location: UK
Posts: 229
Quote:
Originally Posted by roondar View Post
It’s certainly possible I misunderstood. I got the 16 reads from your statement that you could make the player bullets a 4x4 grid.
Ah, that was my fault. I meant 2x2. I was thinking 4 tests and it got mistranslated between by brain and the keyboard :-)
zero is offline  
Old 08 February 2019, 05:15   #40
buzzybee
Registered User

 
Join Date: Oct 2015
Location: Landsberg / Germany
Posts: 182
For RESHOOT R I tried several ways of speeding up collission detection, and now end up with this solution:


- Polling CLXDAT for a some very basic checks, for example if the player sprite is in contact with other sprites and / or background
- If yes, in case of player sprite collision, code checks player position with bounding boxes of other objects using the 68020s CMP2-command. RESHOOT R is AGA-only, so why not. This results in a very small query loop:

Code:
  
	move objcount,d7
	bra chkPlyColLoop
chkPlyCol
	;  bounding box for colcheck
	move.w objectListX(a3),d1; loop through list of objects, get x-coord 
	sub.w a4,d1		; sub players x coord / preloaded earlier
	cmp2.w (plyBoundBox,pc),d1
	bcs.b chkPlyColLoop
	move.w objectListY(a3),d0; get y-coords of objects
	sub a5,d0; sub players y coord
	cmp2.w (plyBoundBox+4,pc),d0
	bcc.b spriteHit; collision detected
chkPlyColLoop
	dbra.b d7,chkPlyCol
....
plyBoundBox	; collission box
	dc.w -31,-24	; x-bound left / right 
	dc.w -46,-38	; y-bound up / down
There are a bunch of other optimizations to speed things up:

- Code builds list of bounding box coords for each hitable (!) object each frame. This list structured in such a way that it is small and enables fast comparisons between players bullets and hitable objects with cmp2
- Player vs. background collision. Background is structured in such a way that only collisions between Player Sprite and Bitplane 1 triggers CLXDAT. So the player ship can go over some terrain and hit explosions without any further cpu overhead. Only if player sprite hits Bitplane 1, further bounding box check is needed
buzzybee 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
Games with collision detection disabling cheat? alkis21 Retrogaming General Discussion 9 03 January 2018 05:54
Fast(est) method for bounding box collisions? MickGyver Coders. Blitz Basic 2 02 October 2017 22:17
Possible problem with Collision detection ! amilo3438 support.WinUAE 5 11 January 2017 19:35
Collision Detection sandruzzo Coders. General 5 10 June 2016 13:50
Collision detection: 2 doubts nandius_c Coders. Asm / Hardware 6 30 November 2014 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 13:37.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, vBulletin Solutions Inc.
Page generated in 0.08747 seconds with 13 queries