How Collisions Work in Games 

For anyone curious, this is how bullet hit detection works in Valve shooters (Team Fortress, Counter-Strike etc.): The bullets are "hitscan", meaning they have no travel time or physics. They go in a straight line and connect instantly within a single frame, so the hit detection is a ray cast. In order for this ray to not have to calculate for every player hitbox and object, it only checks for things within the attacking player's view. Then, additionally, it only checks the large world collision box around every player and object. Only if it detects that it collided with a world collision box, it will then proceed to check for this entitity's hitbox hierarchy.

As a game developer, let me tell you how much I hate collisions...

One additional thing that could be very useful is a composite hitbox system. It's way easier to show than to explain, but I'll give it a shot. Imagine a character having a sphere around itself, this would be the only thing you'd have to test against at first. But if a collision is detected, you go down through a tree of hit-boxes. First there might be an inexpensive sphere, then a box, then maybe a couple of swept spheres. And you could continue to go down as far as you need to. Maybe somewhere in the middle you could have a bunch of stacked sphere's, culling away collision checks for 3/4 of the model, if you want highly detailed collision.

This channel is a gold mine that i have landed on.

The bit about the bullet and the wall is actually backwards (?). There are two separate issues which seem to be conflated in the video: Checking collisions between each object and checking collisions per frame vs calculating time of impact. The first issue is solved with spatial partitioning. The backwards part is regarding the second issue: if you check whether an object has already collided with another object each frame, then something moving very fast will pass through other objects ("tunneling") unless the frame rate is very high. Furthermore, calculating whether two objects have already collided is actually trivial, both mathematically and computationally (eg, with bounding spheres you can just check the distance between the centers), but checking when two objects will collide in the future is more difficult (eg, with bounding spheres you would have to project a capsule along the movement vector and check when and where those collide, or do some other tricks with minkowski differences or adjusting and performing the collision detection multiple times). Which is to say that the example #1 in the bullet wall segment is more computationally expensive and less likely to miss collisions and the example #2 is less computationally expensive and more likely to miss collisions, which is the reverse of what the video (seemingly) states.

Nice video, as always! Another tradeoff between realism and performance noticable in games is that many objects are static and don't react with rest of the world at all, even if a game uses advanced physics engine.

excellent vid, nicely explained. love your hand drawings ;)

Brilliant. That's 2 videos of yours I've stumbled across, And both times I left a little more enlightened. Thank you. Subscribed.

Great video. I love how it's not dumbed down so I actually learned a few interesting things such as the pruning trees, yet still not too complicated for a RU-vid video. Subbed

Your content is not only educational but really inspiring. Your enthusiasm on games really motivates me to keep working on mine. :)

This was really useful! I'm new to the world of programming and this was always and intrigue for me, I always wondered why not use the model directly instead of a box. This is video explains it really well! And I hope to learn more about it so I may do one way of hitbox myself !

Amazing channel! Thanks for uploading this kinds of videos!

Glad I found your channel. Very informative and nice to watch.

You deserve more subscribers and views! I like your videos!

this is awesome, can you do a vid on image processing, for example an algorithm that reads text from an image and then prints it? it would mean the world to me if you did!

Are there any books you would recommend for game design or game programming?

I love your videos,so fun and nice to watch

Great video, HappieCat! :) it would be nice to see a video where you explain a little more about quad trees and, if possible, a simple implementation in java or C++ By the way I love your channel!

Thank you very much. A very valuable and informative video.

i really really like your videos. keep it up!!

I love your videos!

One of the issues that always caught me out was detecting a collision with an object that is traveling at a velocity that would allow it to pass through another object with the intersection occurring 'between frames'. One dirty technique was to stretch the hitbox relative to the frame-rate and velocity. Things get interesting when you start dealing with probabilistic pruning for collisions that have yet to occur, leads into time/space forward looking path-finding for detecting collisions with agents moving on individual paths. Really interesting stuff, you can create path-finding AI that adjusts it's route based on collisions of objects before they have happened.

Detecting collisions is one thing, and seems fairly doable. Handling these collisions, however, is hard... Especially if your objects have rotation

awesome video! thanks!

Nice explanation ❤

Great video, thanks for sharing :)

excellent video...

Great video!

Didn't expect to hear about kd-tree here. Really interesting thanks for the video))))

Movement on platforms that are not on angle of 0 degrees would be a topic I would like to see you discuss about. Cherzz.

I am happy that with my actually knowledge I can understand this what you are talking about. I am sure you’re Idea would change lot of things in deed . I mean about violency in most of perspective. I am German also a foreigner so excuse me for errors in English language. I am also tipping from my handy because I found youre commentary awesome.

What about 2D games? Are the concepts more or less aproximately the same?

This is a good video and all, but gave it a like because of your positivity! Keep up the good work!

Hey it would be great if you can make more videos about these collision detection optimization stuff :)

Nice video!!!

Yeah! Super video! :D

You win my subscribe Thx for Quaternions in a Minute

I feel but also appreciative when I fire 400 bullets continuously and randomly while spinning around in an environment. P.S. I love how in Battlefield, a bullet can actually go between the legs of a running enemy without hitting them.

very detailed very helpful

Thanks, pretty interesting

I never knew about the last thing. Good that i watched this video

The second method can be done with moving objects only. Thus saving a lot of work

Thank you very much~

In a lot of games with physics simulation such as Havok (especially in Bethesda games for some reason) collision detection seems to introduce weird phantom forces sometimes causing players, npc's or objects to be kicked around and ragdolls sometimes to "explode". I'm pretty sure it's caused by compounding rounding errors in the collision detection, but I don't get how it gets so bad. I'd guess it's caused by the collision detection noticing that something has moved into another static object from one frame to the next, but to me the reasonable way to resolve it would be to take the speed vector of the moving object and find the surface where the center of the collision happened by following the opposite of the speed vector. Then reflect the speed vector on this surface multiply this with some elasticity factor of the two objects (thus dampening it unless it's two perfectly elastic objects) and also move the object back to this point. I don't understand how this could cause the ridiculous accelerations that sometimes throws you across all of Skyrim, even with minor rounding errors. Is it some simplifications in the collision calculations that makes it so prone to kicking players and spazz out ragdolls? Do they not use dampening or do they not use speed vectors but simply assumes speed from distance clipped per frame or something?

Fast and interesting. Thank uu

This is why I use Unity 5.6...Easily call the "OnCollosionEnter(Collision Coll){}"...Or "OnCollisionExit(Collision Coll){}", OR "OnCollisionStay(Collision Coll{}". You can also use triggers, which is where you don't actually collide with the collider but go through it as it's a trigger. OnTriggerEnter(collider Coll){} OnTriggerStay(collider Coll){} OnTriggerExit(collider Coll){}

Perfect Dark and Goldeneye actually did some sort of Model based hitbox, but the character models were low-poly. I know since you can get quite close and the aiming Reticle only turns red when it's a hit, though I think it might actually swap out a lo-res hitbox and high-res hitbox. So I'm curious if instead of a box, one used a low-poly model for collisions. Wouldn't that work well it'd be a good compromise between giant hitboxes, and frivolous calculation.

Omg how have I not heard of this channel before? I feel like I just stumbled upon a gold mine!

I learned a little about this when I was making my M.U.G.E.N. roster! Great videos you have! Love them! :D

Usefull information, 10/10 would watch again IGN confirms.

Player: [Fires Gun] Server: [Raycasts every triangle in the scene] Player: "SO MUCH LAG!"

Hey, cool video! I'm especially interested in that topic since I implemented a small rigidbody physics simulation myself. The video explains some basic principles of collision detection very well but I would make the distinction between broad- and narrowphase a bit clearer which was already hinted at with the BVH-Tree. Anyway, nice video! It's always a pleasure watching these.

I love you for the monster hunter reference XD

This even better than some serious collision detection tutorial! I

:D Wow awesome video. interesting stuff

what about a variation of the last example you use where there's both a hurt box and a bounding box? instead of the region of the map, you have each object have a box (or sphere) that takes up a bit more space than the actual character and collision detection skips over each object until two or more bounding boxes collide.

I like this video very much! Have you played: Starcraft (1&2) and Total Annihilation and/or Supreme Commander? Starcraft does the does it hit or not detection (they kinda optimized it in SC2), where TotalA and SupCom does frame by frame checking; so you can move an other unit into a projectiles path to protect whatever would've been hit otherwise. It always amazed me how Total Annihilation have such a good engine running behind it since the scope of the game can be absolutely enormous. Do you have any idea if they used some clever 'magic' to get it working?

I'm a total amateur in coding, but from watching speed runs and such, there seem to be a lot of exploits possible in collision systems based on allowing players and level geometry to collide, and then moving them apart if they are colliding. I can't tell you how many times I've seen runners say something like, "Now I can step into the wall, and technically I'm in the wall for a couple of frames and if I position myself just right then..." and *poof* they're through the wall or on the other end of the map or something like that. It would seem to me that at least with players and level geometry, the safest bet is to first check if a character's movement would place them in a collision, and if so then disallow or reverse the movement. With projectiles, though, you might as well let them move into anything and then check the results; I don't see how that could be glitched or exploited significantly in a decently-written program.

Hi, I have a question about the last part of the video. When you talk about space subdivision, I suppose you are talking about space partitioning, quad and oct trees right?

You draw so good

I know another thing about hitboxes, there Is a model then when the hitbox hits the model the hitbox doesn't pass

damn we need more videos like that i like ps4 but i hate collision its still thye same problem since ps1

we can easily in unity exp ; just make the bullet and the enemy and you can use void OntriggerEnter(2D) and write Destroy(gameObject) with this simple script we can make bullet when it collide with the enemy the bullet will destroy the enemy GameObject .... your videos are cool and simple and 100% Your explanation is understandable

"How collisions work" They don't ...

Damn..., you explained Pruning in just a minute while my prof can't do it in a whole lecture.

do people combine the 2 methods? like, calculating where the bullet will be until it hits a target and then check during that second if something enters or leaves the path?

Why not base the collisions on the path of the bullet. Only check possible collisions that fall within the path of the bullet. Because the bullet goes really fast, it is unlikely that any object will jump into the line of fire while the bullet is moving. And even if they did, the check is happening along that path many times a second, and thus would see if an object moved into the path, say a cat in front of the wall.

You're pretty good at drawing with a mouse.

You didnt mention a problem with simply checking if it is inside every frame. If you shoot a bullet into a thin wall a single frame might be enough for the bullet to jump through the wall. etc etc

im trying to make my own collesion detection because i dont like using already made collision functions idk why its more fun to create things yourself lol

If you guys want to see some amazing hitboxing stuff you should check out Warthunder, those guys at Gaijin have made an amazing job at the "penetration angles of proyectiles coming from any direction you can imagine" making the calculations of the armour, the caliber of the round fired, the tipe of amunition, the angle and more, it's just awesome and they even explain it in some videos

*Hysterically laughs in polygon collision*

I dont get the 1st method. You can calculate when the bullet hits the wall, but how do you know its going to hit this wall and not some others? Because you shoot a bullet, and you dont know if there are some walls nearby. Do you have to check for walls in some sphere?

Why use hit boxes rather than points in space? You could have a body with a number of points e.g. elbow, forearm, hand, shoulder etc... Then detect how close other points are to the object. E.g. A sword tip would have it's own point. Wouldn't the maths be simpler there as you would just assess x,y,z coordinates of two points.

Instant "like" for mentioning Dark Souls and Monster Hunter! thank you for explaining this, I have been trying to understand collision detection for a while

Yeah, the last one (space partitioning) is the most difficult part. There is a data structure named BSP-Trees which allows you to get n objects sorted by distance to a given object. The first one in O(log(N)) the remaining n-1 in O(1). These trees should be updated for every movement of an object, which can be done in O(log(N)). They should also be always balanced. BSP-B-Tree, is a possible solution. Where N is the amount of all Objects in the scene.

A question about the hitboxes: why not check if the bullet of whatever is in the hit box, and if it is then check against the model exactly - and you could also optimize to only check the region of that particular hit box, if there are multiple per model.

thx

Why not use a combination of the two techniques? Basically check once for collisions 1 second after the event. One would of course have to take into account that the targeted player could walk away from or into the collision path, but we still only have to check frames around the 1 second mark depending on the max. speed of the player.

Love watching these videos... I wish I was smart. :(

Fun fact, it is perfectly possible to use the model... at the drawing process, just build a 'box' as you go

i hope we get a ride of this problem in ps5 and next xbox

You must be great game dev ☺

Any ideas on solving the bullet through paper problem?

so what if i wanted to create a 2d game with vector art inside? would it be okay since vectors are only defined using few points and would use less computational power? or would i need squares for hitboxes?

I'm struggling to work with this very issue using VB.Net. In fact, I have developed a load array to hold all my objects that the main user-controlled object could collide with. It cycles through this every time my object moves a single frame - a testament to how fast this process is.

It would be nice to see a hardware-based converter of wire mesh to 3D vector so that collision COULD be model-based- if that was a specific chip preprogrammed function, it would be feasible to produce programs that just call on the chip to define the hitboxes rather than draw them using the mainline CPU. You could get a system that would be easier to minimize clipping errors and potentially develop more complex physics engines for, and it'd be a process that I can't see PC gaming manufacturers ever implementing due to the sheer fact that that'd be a lot of hardware space exclusively usable in game applications. Assuming it's done well in a way developers can easily understand and implement

This style of video reminds me of ViHart

what if you combine both methods that you check if its possible that someone could jump in and then just render the pairs for possible guys who could jump in.

Regressive equations, Splining, Interpolation, Ekstrapolation, FML

Actually, I use quite high poly models, but I use accurate collision at around 54-75 fps on my first person shooter game

Throwin up the Bezier Curves 😩

[Spherical Cows in a Vaccum Intensifies]

i have a doubt.. are hitboxes used in animated movies also???

great. more than little bit I guess. thx.

Couldn't you also check the speed of all players (or any unpredictable object) to calculate if the hitboxes could _reasonably_ collide during active frames. If yes, check the object again -- maybe even after earliest estimated collision time, otherwise don't bother checking cause they will never collide anyway cause it can only hit the static object at this point.

u da best

the hardest part for me is, how to separate blocks correctly (square vs square) ... l did it, but my code will be messy after adding more types of blocks

If you have n objects then there are O(n^2) pairs to check not n choose 2.

1:55 Or a cylinder shaped hitbox would be a good solution