Do all bullets check hits every frame ?

A place for people with an interest in developing new shmups.
User avatar
heli
Posts: 585
Joined: Fri Sep 13, 2019 3:58 pm

Do all bullets check hits every frame ?

Post by heli »

Take by example a cave shooter, many bullets.
Do all bullets check hits every frame ?
Or is there a maximum of checks per frame ?

I read article about how they checked hex files for battle garegga to get information how to play, so maybe anyone knows here ?
I like to know what (older) games use this technique.
I know supermario1 uses this system.
User avatar
RetrocadeMedia
Posts: 16
Joined: Sat Aug 31, 2019 10:15 pm

Re: Do all bullets check hits every frame ?

Post by RetrocadeMedia »

Personally I wouldn't check collision bullet by bullet.

I would check to see if the player is hitting a bullet, not if a bullet is hitting the player.
But that's just my own two cents.
User avatar
Shepardus
Posts: 3505
Joined: Sat Dec 13, 2014 10:01 pm
Location: Ringing the bells of fortune

Re: Do all bullets check hits every frame ?

Post by Shepardus »

As long as the collision checks you're doing are simple AABB (axis-aligned bounding boxes) or circle collisions (i.e. a distance check), you should be able to get away with a naive loop through all the bullets every frame. Chances are rendering all the bullets and other objects on the screen is going to be much more expensive than the collision checks.

It is worth noting, however, that apparently Dodonpachi Daioujou only checks some of its bullets every other frame: viewtopic.php?p=648604#p648604
RetrocadeMedia wrote:Personally I wouldn't check collision bullet by bullet.

I would check to see if the player is hitting a bullet, not if a bullet is hitting the player.
But that's just my own two cents.
Effectively the same thing in a shmup, since you're going to be collision-checking many objects against one. You need to pay more attention to the algorithms and data structures you use for collision detection if you've got 3D geometry or if you've got many objects that can all collide with each other, but in a shmup you'd generally be checking the bullets for collision with a single player, i.e. you're not checking whether the bullets collide with each other.
Image
NTSC-J: You know STGs are in trouble when you have threads on how to introduce them to a wider audience and get more people playing followed by threads on how to get its hardcore fan base to play them, too.
1CCs | Twitch | YouTube
User avatar
__SKYe
Posts: 701
Joined: Tue Feb 16, 2016 1:51 am
Location: Portugal

Re: Do all bullets check hits every frame ?

Post by __SKYe »

Shepardus wrote:Effectively the same thing in a shmup, since you're going to be collision-checking many objects against one.
Precisely, you perform the same amount of work whether you go "player vs all bullets" or "all bullets vs player".
Shepardus wrote:You need to pay more attention to the algorithms and data structures you use for collision detection if you've got 3D geometry or if you've got many objects that can all collide with each other, but in a shmup you'd generally be checking the bullets for collision with a single player, i.e. you're not checking whether the bullets collide with each other.
Agreed again, a few thousand simple collision tests aren't gonna cripple your framerate on any PC made in the last decade. You can perform a very simple optimization that will probably save you quite a few cycles, though (with a few variations):
  • If you divide the screen into two halves (either horizontally or vertically), you can quickly prune any bullet that aren't in the same half as the player with a single comparison, though you have to perform the full test with the ones that are.
  • If you divide it into 4 quadrants, you can quickly prune the bullets that aren't in the player's quadrant with two comparisons.
  • You could also subdivide the screen into columns/rows and, again, the bullets that aren't in the same column/row as the player can be pruned by two comparisons. This one acts essentially as a binary search and any more than 4 columns/rows will probably not help your performance at all. At four columns/rows, it behaves similarly to the quadrants variation (two comparisons to check where an object lies), the only distinction being the way the screen is subdivided.
Don't use a standard quadtree if your game is 2D, though, unless your bullets have a complicated collision surface. The checks to see where a bullet lies is the same cost as to check if it collides with the player (AABB -- four comparisons, worse case), so you'll likely get worse performance.

Also, if you're using circle-circle intersections, and you only care whether the circles intersect (and not the distance between them), you don't have to perform the square root. The circle-AABB is the (slightly) more costly comparison, though if the player and most of your bullets have circles as collision surfaces, then it's not a problem.

As for data structures, in my opinion, a single contiguous array/pool is best both for simplicity and for cache coherency.

As an aside, measure your worse case performance (with the maximum bullets/enemies you intend to have on screen at once) to see if you actually need any of this. :)
User avatar
Sumez
Posts: 8019
Joined: Fri Feb 18, 2011 10:11 am
Location: Denmarku
Contact:

Re: Do all bullets check hits every frame ?

Post by Sumez »

Circle collisions are only an advantage if you got cheap trigonometry, so it depends a lot on your CPU.
RetrocadeMedia wrote:Personally I wouldn't check collision bullet by bullet.

I would check to see if the player is hitting a bullet, not if a bullet is hitting the player.
But that's just my own two cents.
That's entirely semantics - functionally it's the same thing.
Depending on the programming language you're using, and the platform you're targeting, what matters is the way you access the large amount of coordinates you're cycling through. If you have direct random access to every single value (preferably on the stack) rather than needing to go through pointers for every single lookup (which is what you'd normally do if treating every bullet as an object), your collision detection will be multitudes faster.

EDIT: This is kind of off-topic really.
A lot of older shooters definitely didn't check collisions on every frame. I don't have any precise data however. I'd love to know if anyone made the research.
User avatar
__SKYe
Posts: 701
Joined: Tue Feb 16, 2016 1:51 am
Location: Portugal

Re: Do all bullets check hits every frame ?

Post by __SKYe »

Sumez wrote:Circle collisions are only an advantage if you got cheap trigonometry, so it depends a lot on your CPU.
That's the thing, if you don't care about the distance between the circles, you don't need any trigonometry, only adds, subs and mults.
Sumez wrote:EDIT: This is kind of off-topic really.
A lot of older shooters definitely didn't check collisions on every frame. I don't have any precise data however. I'd love to know if anyone made the research.
Makes sense; if you perform them over two frames you halve the work that needs to be done. And depending on how fast the bullets travel (slower is better), you can still get pretty accurate results. But I don't think you need to worry about this in a PC game. :)
User avatar
Sumez
Posts: 8019
Joined: Fri Feb 18, 2011 10:11 am
Location: Denmarku
Contact:

Re: Do all bullets check hits every frame ?

Post by Sumez »

Multiplications is still very expensive on most classic arcade or console hardware. :)

OP specifically asked about older games, so I'm not sure PCs is the target?
If I were targeting modern PCs I'd absolutely use circle collisions and check on every frame, but I was actually working on a bullet hell shooter for SNES until recently, and spreading stuff out across multiple frames was very much a thing. I ended up dropping it though, as I wasn't certain I'd be able to maintain even 30fps.

The thing about accessing memory values is still a thing on modern hardware though, as RAM speeds haven't improved anywhere near as much as CPU. When trying to run a game on an X360 I had the collision detection slow down like crazy due to that limitation (it did run fine on my PC, but I still think it's an important area to optimize).
User avatar
__SKYe
Posts: 701
Joined: Tue Feb 16, 2016 1:51 am
Location: Portugal

Re: Do all bullets check hits every frame ?

Post by __SKYe »

I was explicitly thinking of PC here. :)
OP posted on another thread about making a game with DirectX so I figured he intends to use this info for his own PC game. For older hardware, I'd absolutely use AABBs as well.
Sumez wrote:I was actually working on a bullet hell shooter for SNES until recently, and spreading stuff out across multiple frames was very much a thing. I ended up dropping it though, as I wasn't certain I'd be able to maintain even 30fps.
Yeah, I think it's the more obvious way to reduce work. Dividing the screen into two halves might still help (single comparison to reduce the tests by half, on average) but more than that would likely be counterproductive. Depending on how slow some bullets move, you might even get away with a slower test rate.
Sumez wrote:The thing about accessing memory values is still a thing on modern hardware though, as RAM speeds haven't improved anywhere near as much as CPU. When trying to run a game on an X360 I had the collision detection slow down like crazy due to that limitation (it did run fine on my PC, but I still think it's an important area to optimize).
Same, the whole array being better due to cache coherency was in the context of modern hardware (CPU cycles=cheap, memory access=very slow).

I'm curious, are you in game dev professionally (if you don't mind me asking)? I can understand developing for the NES/SNES/etc as a hobbyist, since all the tools are available online, but devkits aren't very common in the wild (or so I think). :)
User avatar
Sumez
Posts: 8019
Joined: Fri Feb 18, 2011 10:11 am
Location: Denmarku
Contact:

Re: Do all bullets check hits every frame ?

Post by Sumez »

__SKYe wrote:Yeah, I think it's the more obvious way to reduce work. Dividing the screen into two halves might still help (single comparison to reduce the tests by half, on average) but more than that would likely be counterproductive. Depending on how slow some bullets move, you might even get away with a slower test rate.
Dividing the screen would require checking against one axis for every bullet, which creates a lot of overhead. It would be better to dedicate one frame entirely to collision detection, and then do all other logic on the next frame. That's similar to the SMB1 example given by OP.
I'm curious, are you in game dev professionally (if you don't mind me asking)? I can understand developing for the NES/SNES/etc as a hobbyist, since all the tools are available online, but devkits aren't very common in the wild (or so I think). :)
I'm curious about what you are asking here, but unsure what you'd need a "devkit" for, or what such a thing would even involve in this context? :)

I'm a programmer professionally, but not a game programmer. I did get one offer for a paid NES dev job at one point, but the potential employer was really unclear about the exact payment involved, so I didn't want to take the chance.
User avatar
__SKYe
Posts: 701
Joined: Tue Feb 16, 2016 1:51 am
Location: Portugal

Re: Do all bullets check hits every frame ?

Post by __SKYe »

Sumez wrote:I'm curious about what you are asking here, but unsure what you'd need a "devkit" for, or what such a thing would even involve in this context? :)
I mean for developing for the XBox 360. Or is it possible to create & run homebrews on it without a devkit?
User avatar
Sumez
Posts: 8019
Joined: Fri Feb 18, 2011 10:11 am
Location: Denmarku
Contact:

Re: Do all bullets check hits every frame ?

Post by Sumez »

Oh I misunderstood you then. :)
Yeah, during X360's active years, Microsoft launched a game creation platform using C# called XNA, which allowed people to release amateur games on the platform. It was only available in very few countries though, so I had to make a fake UK account.
XNA is still maintained as an open source fan project to this day as "MonoGame", and a few very popular games have actually been made with it.
User avatar
__SKYe
Posts: 701
Joined: Tue Feb 16, 2016 1:51 am
Location: Portugal

Re: Do all bullets check hits every frame ?

Post by __SKYe »

Ah, alright. I knew about XNA, but I thought it was just the framework used and you still had to buy/apply for a devkit.
User avatar
heli
Posts: 585
Joined: Fri Sep 13, 2019 3:58 pm

Re: Do all bullets check hits every frame ?

Post by heli »

Shepardus wrote:As long as the collision checks you're doing are simple AABB (axis-aligned bounding boxes) or circle collisions (i.e. a distance check), you should be able to get away with a naive loop through all the bullets every frame. Chances are rendering all the bullets and other objects on the screen is going to be much more expensive than the collision checks.

It is worth noting, however, that apparently Dodonpachi Daioujou only checks some of its bullets every other frame: viewtopic.php?p=648604#p648604
Thanks, only i dont see it in the article.
You know how many bullets dodonpachi checks ?
Without this trick is is impossible to make a smooth game on those older hardwares.
Important is to check every frame the same ammount of enemy bullets to get stable framerates.
You might have seen bullets pass thru your ship sometimes in some games, now u know why.

Here from interview : http://shmuplations.com/dodonpachi/
—What is the maximum number of bullets Dodonpachi can display on-screen?
Ichimura: 245. The campaign version, by the way, can put out 315.

You bet those bullets arent checked all against your hitbox.
I cant find anything about it further.

You might as well program for 2 player mode every frame checks another player, so it runs equal to 1 player mode.
User avatar
heli
Posts: 585
Joined: Fri Sep 13, 2019 3:58 pm

Re: Do all bullets check hits every frame ?

Post by heli »

Sumez wrote:Multiplications is still very expensive on most classic arcade or console hardware. :)

OP specifically asked about older games, so I'm not sure PCs is the target?
If I were targeting modern PCs I'd absolutely use circle collisions and check on every frame, but I was actually working on a bullet hell shooter for SNES until recently, and spreading stuff out across multiple frames was very much a thing. I ended up dropping it though, as I wasn't certain I'd be able to maintain even 30fps.

The thing about accessing memory values is still a thing on modern hardware though, as RAM speeds haven't improved anywhere near as much as CPU. When trying to run a game on an X360 I had the collision detection slow down like crazy due to that limitation (it did run fine on my PC, but I still think it's an important area to optimize).
Thank you, you know much.
I am intrested in optimizing for older games, older hardware, and everything that needs this trick.

On modern computers you could have a core running the collisions.
I am mostly intrested in optimizing for single core technology that gives the retro game feel.
It is to complicated for me to do multithreading, not trying to learn anything about it either.

I like to make hardware someday : since windows sucks so much and playstation wont let me in.
Those arcade PCB pictures inspired me, i like to make a simple handheld game console someday without software licensing and limitations.
If it does what saturn can do i am happy, first without 3D will work for sure.
User avatar
heli
Posts: 585
Joined: Fri Sep 13, 2019 3:58 pm

Re: Do all bullets check hits every frame ?

Post by heli »

Sumez wrote:Circle collisions are only an advantage if you got cheap trigonometry, so it depends a lot on your CPU.
For everything heavey you need box check before having a heavey function.
Circles can be cheap if you check exponential without sqrtf.
I dont know what consoles using float or integer.
NES and SNES integer for sure.

btw : i dont use C# just normal C++, it is bad all these computer things use C# only, like unity and microsoft.
User avatar
heli
Posts: 585
Joined: Fri Sep 13, 2019 3:58 pm

Re: Do all bullets check hits every frame ?

Post by heli »

I also have a rock list running collisions with eachother, that is the most heavy, here i could try a few rocks per frame also.
Or bullets that can be shot are heavy, 100 enemy bullets vs 10 player bullets is 1000 boxes per frame, not do-able.
User avatar
Shepardus
Posts: 3505
Joined: Sat Dec 13, 2014 10:01 pm
Location: Ringing the bells of fortune

Re: Do all bullets check hits every frame ?

Post by Shepardus »

heli wrote:Thanks, only i dont see it in the article.
Here:
BarfHappy wrote:To ease the check, some bullets have an oscillating flag (per bullet) that tells if the bullet is to be checked or not, hence why you sometimes miraculously survive, because it was on your ship rectangle the frame the bullet inactive.
heli wrote:Here from interview : http://shmuplations.com/dodonpachi/
—What is the maximum number of bullets Dodonpachi can display on-screen?
Ichimura: 245. The campaign version, by the way, can put out 315.
245 collision checks should be pretty inexpensive even for a 25-year-old processor. Even if you're skipping collision checks, you still need to render the sprites. At any rate, if you're making a game this is the sort of thing you'd want to run through a profiler before diving into optimizations.
Image
NTSC-J: You know STGs are in trouble when you have threads on how to introduce them to a wider audience and get more people playing followed by threads on how to get its hardcore fan base to play them, too.
1CCs | Twitch | YouTube
User avatar
heli
Posts: 585
Joined: Fri Sep 13, 2019 3:58 pm

Re: Do all bullets check hits every frame ?

Post by heli »

Ok.
I stay with the 2player optimizing and wont go any further.
User avatar
ciox
Posts: 1001
Joined: Sun Feb 12, 2012 5:29 pm
Location: Romania

Re: Do all bullets check hits every frame ?

Post by ciox »

Collisions have always been a bit dodgy in shmups, usually to the player's advantage.
Shmups pretty much never do continuous collision checking (trying to detect if a bullet "hops" completely over your hitbox in a single frame, and counting that as a hit) and combined with checking collision every other frame in some bullet hells, it means that phasing through bullets is almost a tactic and certainly a reality.
Doing a loop to see if any bullets are touching the player's ship is indeed pretty fast, not as fast as it can get with pruning techniques, but still faster than a lot of physics libs or native collision checking code from various engines.
User avatar
casualcoder
Posts: 346
Joined: Sat Apr 21, 2012 4:35 am
Location: West Coast, Canada

Re: Do all bullets check hits every frame ?

Post by casualcoder »

I had to sort this all out with the tool I just put out (VariaBULLET).

I ended up using collision detection optionally on both bullets and objects they collide with.

For example walls can detect bullets and instantiate explosions and damage (if damageable), and bullets can also detect the collision if you want to do the same.


The reason for the flexibility is it easily allows for making different explosions for different objects and bullets. Could be quite dynamic.

Also, the tests I ran (Unity) showed good performance (1000's of concurrent bullets @ 60FPS on and old system).
VariaBULLET Concurrent Bullets Test Bench


The best performance was obviously removing colliders entirely, but then you'll have to make your own pseudo-collision system which adds back some overhead.
User avatar
heli
Posts: 585
Joined: Fri Sep 13, 2019 3:58 pm

Re: Do all bullets check hits every frame ?

Post by heli »

casualcoder wrote:I had to sort this all out with the tool I just put out (VariaBULLET).

For example walls can detect bullets and instantiate explosions and damage (if damageable), and bullets can also detect the collision if you want to do the same.
You test against different objects, i think it is not needed.

if( alienlist.checkbullethit(x,y) )
{
smallexplosion->add( x,y );
DELETE( this ) // remove from list
}else
if( walllist.checkbullethit(x,y) )
{
wallexplosion->add(x,y)
DELETE( this ) // remove from list
}

I think you make it slower with this :

if( bCheckAlien && alienlist.checkbullethit(x,y) )
{
smallexplosion->add( x,y );
DELETE( this ) // remove from list
}else
if( bCheckWalls && walllist.checkbullethit(x,y) )
{
wallexplosion->add(x,y)
DELETE( this ) // remove from list
}

Maybe you do it different.
pieslice
Posts: 200
Joined: Sat Mar 01, 2008 12:15 pm
Location: Finland

Re: Do all bullets check hits every frame ?

Post by pieslice »

In Crisis Wing I just let the Box2D do the trick
User avatar
heli
Posts: 585
Joined: Fri Sep 13, 2019 3:58 pm

Re: Do all bullets check hits every frame ?

Post by heli »

pieslice wrote:In Crisis Wing I just let the Box2D do the trick
Without knowing what is going on ?
There are many tricks to make a shmup.

Score should not use itoa, it is very slow.
Dont use divides or math functions ( sometimes you need to, then do only one enemy per frame )
Check bullets 1 player per frame.
User avatar
casualcoder
Posts: 346
Joined: Sat Apr 21, 2012 4:35 am
Location: West Coast, Canada

Re: Do all bullets check hits every frame ?

Post by casualcoder »

heli wrote:
pieslice wrote:In Crisis Wing I just let the Box2D do the trick
Without knowing what is going on ?
There are many tricks to make a shmup.

Score should not use itoa, it is very slow.
Dont use divides or math functions ( sometimes you need to, then do only one enemy per frame )
Check bullets 1 player per frame.
I think what I was trying to get across is if your target system is reasonably fast (that is to say, not running on windows 98) you probably won't have a lot of issues with collision detection slowing your game <60FPS.

I think that's what pieslice was saying. It doesn't really matter if the method is costly if you can pump out thousands of checks on every frame.

Do some tests and go from there.


But for sure something has to do collision detection on every frame. Else a bullet might just go right through objects if it's fast enough.
pieslice
Posts: 200
Joined: Sat Mar 01, 2008 12:15 pm
Location: Finland

Re: Do all bullets check hits every frame ?

Post by pieslice »

casualcoder wrote:
But for sure something has to do collision detection on every frame. Else a bullet might just go right through objects if it's fast enough.
I use continuos collision detection for player bullets vs enemies ( they are fast ) and discrete for enemy bullets vs player. player hitbox is not bullet hell small but closer to raizing/batsugun so you are basically guaranteed to suffer a hit regardless the enemy bullet speed on regular game play.

also building up from very low level optimizations like worrying on score display performance sounds weird, because about 70% of performance is probably used to render gfx, 15% to object management like spawn/destroy, 5% to audio and 5% to logic, so profiling to find and then optimizing the most taxing subsystems first is really the low hanging fruit to pick
User avatar
heli
Posts: 585
Joined: Fri Sep 13, 2019 3:58 pm

Re: Do all bullets check hits every frame ?

Post by heli »

With the score is how these old games work.
Why would you waste CPU if you could program better.
The faster everything works, the more FPS you get, it all adds up.
Just take a look to the itoa code and you know why, you are also limited to a readable score of 8 or 9 digits, while my game has about 20 digits of score.
Reasons enough.

I would like to have fixed FPS like old games, 60fps + slowdown.
On single core windows this is impossible to stable run, you have to multiply by the elapsed time.

Wont that be great if your simple shooter works on old computers, it looks oldschool so if it wont work on a simple PC is a fail.
There are many people who can not afford a new computer, they can still play a game.
User avatar
heli
Posts: 585
Joined: Fri Sep 13, 2019 3:58 pm

Re: Do all bullets check hits every frame ?

Post by heli »

pieslice wrote:
casualcoder wrote: I use continuos collision detection for player bullets vs enemies ( they are fast ) and discrete for enemy bullets vs player. player hitbox is not bullet hell small but closer to raizing/batsugun so you are basically guaranteed to suffer a hit regardless the enemy bullet speed on regular game play.
What is discrete compared to continuous ?
pieslice
Posts: 200
Joined: Sat Mar 01, 2008 12:15 pm
Location: Finland

Re: Do all bullets check hits every frame ?

Post by pieslice »

heli wrote:With the score is how these old games work.
Why would you waste CPU if you could program better.
The faster everything works, the more FPS you get, it all adds up.
Just take a look to the itoa code and you know why, you are also limited to a readable score of 8 or 9 digits, while my game has about 20 digits of score.
Reasons enough.

I would like to have fixed FPS like old games, 60fps + slowdown.
On single core windows this is impossible to stable run, you have to multiply by the elapsed time.

Wont that be great if your simple shooter works on old computers, it looks oldschool so if it wont work on a simple PC is a fail.
There are many people who can not afford a new computer, they can still play a game.
stable 60fps is definitely doable on single core windows systems, either by using vsync or high resolution timers. you seem to put the blame on operating system even when the problem is more likely your lacking knowledge of how to program for windows. if your core shmup loop is coded correctly, most of the cpu time should be wasted on vsync or idling and waiting for next cycle

also for instance, if you build your unity 2d game to 32 bit, it will work for any computers at least 10 years old if it is optimized well enough
User avatar
casualcoder
Posts: 346
Joined: Sat Apr 21, 2012 4:35 am
Location: West Coast, Canada

Re: Do all bullets check hits every frame ?

Post by casualcoder »

heli wrote: What is discrete compared to continuous ?
To my understanding discrete does a per frame check and if a collider intersects with another one, it detects collision.

But in some cases, the colliders never intersect on any one frame even though their paths indicate that they should have.


Here's a visual of this in effect:

Image


In that case, I think continuous takes in account previous frame and current frame positions and determines if an intersect of the colliders SHOULD HAVE occurred. Very similar to how a raycast works, figuring in not only colliders but the invisible path.
pieslice
Posts: 200
Joined: Sat Mar 01, 2008 12:15 pm
Location: Finland

Re: Do all bullets check hits every frame ?

Post by pieslice »

What casualcoder says is correct about the collision methods.
Post Reply