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.
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.
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.
+Andy H I see what you're saying! I think the issue is that my examples tend to be over-simplified, which I fully admit to. I was mainly trying to illustrate that if we only consider the speed of the bullet, and the distance it travels, the prior calculation is fast. But if we try a posterior calculation, we have a lot more to check. Of course, there are many other reasons why prior calculations get messy and aren't often used, as you said. I'm still figuring out how I should balance simplifying video material at the expense of losing out on the full picture, so thanks for the feedback.
+TheHappieCat It's also possible that I simply misunderstood the video. Like I don't quite get how the "prior" calculation would actually be implemented in an actual collision system, which is maybe where the misunderstanding comes from? Like if you do a ray trace, it would be pretty fast, but obviously you need to check the trace against each object to know if the trace hit it, which in my mind makes the amount of "stuff to check" about the same as a "posterior" calculation, where you have to check the bullet's bounds against each object to know if the bullet is touching it. In either case you would drop either the ray trace or the bullet down the BVH and test against all objects it touches. I think maybe the confusion comes from you explaining the *concept* whereas I'm thinking about the *implementation*
+Andy H Yeah, I think that's it, haha, though I know my examples are definitely imperfect. I was trying to avoid talking about ray casting, which probably made it more confusing for someone who already knows how these systems work!
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.
The stuff in the real world in analog which is why lots of actual realistic stuff can happen; And the universe gives not a shit about what is going on. In a computer the calculations would fry the processor
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!
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.
'Mein Kampf' a German book which translates to 'My Jourmey' Mein Kampf is probably the best game design book ever made as it details the psychology of game design and how doing something will cause a reaction. The title is a little misleading but I'm sure that you can find a PDF of the translation if you look online.
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
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 RUclips video. Subbed
I would like to know the order of collision. Then I could resolve one collision and convert into a slider. Then later on solve the other collision. Mario64 has a bug where this order is wrong.
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 !
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?
Your description would cause a hand that goes inside the ground to bounce into the elbow, which would cause it to bounce back inside the ground while the elbow bounces into the head.. Etc etc.. Not that your description is wrong or the idea bad, but there are a lot of edge cases and in some games they either don't show up during testing (for a variety of debug reasons) or they simply don't want to spend the time it would require to fix what is essentially a (more or less) rare graphics glitch.
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.
Blazervania X Yes, in general it's the same but with the condition that you don't need to render or check if a collision happens in a 3rd dimension, only X and Y :)
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.
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.
That would work pretty well in modern games, I believe. But most games stick with straight boxes, because those are far simpler to calculate for, even if there are plenty.
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){}
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.
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.
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
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.
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.
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!
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.
Or we could accept that not every game needs a destructible level and can stick to a BSP tree for it just like in Doom. Moving Objects can overlap with sectors . No balance possible or needed. Or you mean some pressure when an object has the choice of its favorite parent? Per sector sort along some main axis (fixed).
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
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.
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
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.
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.
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.
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 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?
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?
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.
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.
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?
Well, couldn't you also just check for every hitbox, if another hitbox is inside it? Then, you do the computations for what happens when those two hitboxes collide. Wouldn't that be more efficient as well, because you're not checking every possible pair?
That's *precisely* what "checking every pair" is, isn't it? If you have boxes A,B,C you'll check: A,B [= B,A] A,C [= C,A] B,C [= C,B + you already did check B,A] [C was already checked against A and B] That's each pair OR as you put it: for every hitbox, we checked every other hitbox.
No, I meant just check every hitbox for another hitbox. if hitbox in A, check new hitbox type if hitbox in B, check new hitbox type if ... Now do you get what I'm trying to say?
The problem is that *you* as a human can tell which hitboxes are overlapping, but a computer can't. For the computer, to be able to tell if a hitbox is inside another hitbox it has to check that pair. Unless you mean grouping the hitboxes together in some sort of tree so you can check against the bigger group first, and the continue downwards, which is what the video describes towards the end. In either case, your not describing a new method, your rephrasing what the video already showed. PS the only reason you can tell which overlap is because you have a neural network that spends massive amounts of parallel computing time to determine what you see in front of you.
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
Ah, but War Thunder can afford that. Simple graphics for the surroundings and few moving objects let them implement very complex collisions and penetration computations. Especially when we're talking about in-flight part of the game.
why is it that in everyone of these videos there's someone saying... "oh your wrong because of blah blah blah". I'm no computer scientist but I wouldn't click on this video because I knew the answer to the statement on the thumbnail. Hell, I watch these videos to learn something new.
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
Unit 978 A mesh is nothing BUT a series of simple linear 3D vectors drawn from anchor points. And yes, they can be simplified to single equations, albeit very complex ones. What I'm thinking of would basically be the computer physics equivalent to supersampling- you'd take a hitbox, find the parts of an object within that hitbox, refine the many simple 3D vector lines into a single complex vector field, and use that vector field as a secondary hitbox that is solely called upon when a collision is detected from the simple hitbox, and evaluates whether or not the collision flag is tripped based on whether or not the complex hitboxes detect collision. And yes, you can totally do that through hardware. High-level graphics cards do pretty much just that all the time with supersampling, and it'd basically be the same thing on a much bigger scale. ...come to think of it, the PS3's cell processor probably would have been perfect for such a function, had it been properly demonstrated and explained to developers.
+NotAGoodUsername360 Yes but you said a wire mesh to a 3D vector ... but wire meshes are already a series of vectors. But games do not really need model perfect collision detection. Assume that there is a chip that does this collision detection there is still the overhead of updating data between the CPU and the collision chip, just like with GPUs and CPUs
Unit 978 I did say vector, SINGULAR, did I not? And yeah, they don't NEED it right now, but if VR becomes a common thing, or even interactive/pseudo-tactile holograms? Advanced collision detection will be IMPERATIVE for responsive, fine-tuned tactile interfacing. That, and it would also make building soft-body physics engines VASTLY easier and less memory intensive to build. And the response from the collision detection refiner would be binary: if [object location] = [rough hitbox area], then ([refine hitbox]; if [refined hitbox] = [object location], then [collision] = true, else [collision] = false) else [collision] = false. I know that's massively oversimplifying and needlessly complicating the collision detection algorithm logic, but if you did the entire sub-loop in hardware the computation latency would be microscopic, even when frequently called upon, as because it's binary you can easily see how you could do it all with pure conductors.
+NotAGoodUsername360 But you can't have an entire mesh be 1 3d Vector. You lose all mesh data. That is the only reason I replied. But also collision information would be needed from the chip for the physics collision response, such as how the intersection occurred.
I don't get it. Back in the Commodore C64 days, once two things had any of their pixels touch, that was a collision. How hard is it for modern computers/game engines to do that? I mean it was for only 2d games, but the same hitbox idea is still needed for 2d games today.
I'm having a problem with the pruning tree... If somebody is at the center of the game level and shoots a bullet, then it could hit anything in the four other areas, creating computational problem again... I'm missing the point, I think.
1:15 "for each object on the scene" i kinda disagree, you can simply do a basic distance check (depending on the size of the hitboxes) to see if a collision is even possible
that's a very naïve method. very common mistake. if you have 1k objects in the scene, you would need to do 1k distance check against 1 bullet. now if there's 100 bullets, you'll need to do 100k distance check every frame. very inefficient. The pruning tree method shown in the video is what being used in practice. did you even watch the video till the end?
Seyha Leonhartz first of all, you can check square distances, that requires no sqrt max(abs(x1-x2),abs(y1-y2)) highly innaccurate, but much quicker and sufficient when you know an objects biggest size second, there will never be 100 bullets at the same time unless they move very slow third, did you even read my comment?, i never said it was efficient, i KNOW its a slow method, i simply stated that it would be wrong to say you have to check every polygon or whatnot on EVERY model, when you can check the polygons on just the ones near the bullet IM NOT talking about whether its efficient, im talking about that she said "for each object on the scene" please read the comments more properly
EnderCrypt First of all, bullet isn't the only thing you need to check collision for. player characters, enemy npcs, moving platforms, grenades, and many other things that don't just collide with the player but also other objects and even themselves. Secondly, your first comment was arguing a moot point. you're offering an optimization method that she was going to talk about. she mentioned the pruning tree method that would solve the efficiency issue, and then you come in arguing on a problem that she already tell how to solve. and I feel the need to comment because I want you to know that there's a better solution right there in the video.
Seyha Leonhartz yes thats correct that she offered a better solution me: "for each object on the scene" i kinda disagree yes, it might been a "moot" point, but i just wanted to bring that 1 thing up because why not wheater its efficient or not doesent matter, it was just that quote that seemed to imply that to check each polygon for collision would imply that checking would require going through all non-static objects
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
Jazoray from what I know. The shader can't really return anything. We simply give it our vertices and matrices to modify those vertices. And that's it. The CPU needs to be in control of the actual game itself. I think?
Hey Cat, Not sure if you've done other videos on this topic or not. I'll look at your playlists . . . That said, I've been playing "Sniper Elite 4" by Rebellion and I'm very intrigued by what is going on "under the hood" with their collision detection / hit box mechanics given the way a one shot kill can work if one hits a vital organ while sniping. If you haven't played it, here is a sample of kill shots from the game ruclips.net/video/4cvCMEuHHK8/видео.html That video can make it seem like a hit = a kill every time but it doesn't, at least not on Normal or higher difficulty. Sometimes a hit will just stagger the enemy, and cause him to squat and search (and seemingly does cause some "damage" to it, which can eventually kill if enough non-lethal shots accumulate). Other times, it causes a fatal wound which doesn't immediately kill him but causes him to drop and call for help, thus allowing for one version of the "baiting" mechanic the game implements (if you "bait" an enemy and then kill them, it is worth more experience points). One thing I've always disliked in shooters is the "enemy as bullet sponge" mechanic that emerges from the use of a generalized "hit point" system. A fully realistic combat trauma model is probably never going to happen in a computer simulation that isn't specifically focused only on that topic, but something "more" realistic is always nice. It seems to me the system in SE4 is a step in the right direction, and I would love to understand what they have done to achieve this.
If you have 3 objects (A, B, C) you would only need to check for collisions for (A, B), (B, C), (A,C) because you have to consider only unordered pairs. However O(n choose 2) = O(n^2), but the actual calculations count is lower with n choose 2.
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.
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 is called bounding volume hierarchy
As a game developer, let me tell you how much I hate collisions...
but collisions love u...
Collisions hate you when you think you can play with them, they are not easy.
Alex Stradivarius I was joking bro! 😕😆
collisions are the worst
As someone who is doing an exam that relies on a tonne of collisions, it's killing me
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.
+Andy H I see what you're saying! I think the issue is that my examples tend to be over-simplified, which I fully admit to. I was mainly trying to illustrate that if we only consider the speed of the bullet, and the distance it travels, the prior calculation is fast. But if we try a posterior calculation, we have a lot more to check. Of course, there are many other reasons why prior calculations get messy and aren't often used, as you said. I'm still figuring out how I should balance simplifying video material at the expense of losing out on the full picture, so thanks for the feedback.
+TheHappieCat It's also possible that I simply misunderstood the video. Like I don't quite get how the "prior" calculation would actually be implemented in an actual collision system, which is maybe where the misunderstanding comes from? Like if you do a ray trace, it would be pretty fast, but obviously you need to check the trace against each object to know if the trace hit it, which in my mind makes the amount of "stuff to check" about the same as a "posterior" calculation, where you have to check the bullet's bounds against each object to know if the bullet is touching it. In either case you would drop either the ray trace or the bullet down the BVH and test against all objects it touches. I think maybe the confusion comes from you explaining the *concept* whereas I'm thinking about the *implementation*
+Andy H Yeah, I think that's it, haha, though I know my examples are definitely imperfect. I was trying to avoid talking about ray casting, which probably made it more confusing for someone who already knows how these systems work!
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.
The stuff in the real world in analog which is why lots of actual realistic stuff can happen; And the universe gives not a shit about what is going on. In a computer the calculations would fry the processor
Your content is not only educational but really inspiring. Your enthusiasm on games really motivates me to keep working on mine. :)
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!
+Jarmahent You mean like image/symbol recognition? Yeah, actually did a similar project to that recently
+TheHappieCat yes please
+TheHappieCat You could work at Bethesda. Godd Howard wil bess you
JuruX SayokaX : I was just thinking that!
TheHappieCat is it out yet?
excellent vid, nicely explained.
love your hand drawings ;)
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.
Are there any books you would recommend for game design or game programming?
'Mein Kampf' a German book which translates to 'My Jourmey'
Mein Kampf is probably the best game design book ever made as it details the psychology of game design and how doing something will cause a reaction. The title is a little misleading but I'm sure that you can find a PDF of the translation if you look online.
wtf
yeah, make sure to listen to Darude-Sandstorm while reading that, too.
Nel prro
@@Danicx11 hhhhhh you're funny dude !!!!!
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
You deserve more subscribers and views! I like your videos!
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 RUclips video. Subbed
Detecting collisions is one thing, and seems fairly doable. Handling these collisions, however, is hard... Especially if your objects have rotation
I would like to know the order of collision. Then I could resolve one collision and convert into a slider. Then later on solve the other collision. Mario64 has a bug where this order is wrong.
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 !
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?
Your description would cause a hand that goes inside the ground to bounce into the elbow, which would cause it to bounce back inside the ground while the elbow bounces into the head.. Etc etc..
Not that your description is wrong or the idea bad, but there are a lot of edge cases and in some games they either don't show up during testing (for a variety of debug reasons) or they simply don't want to spend the time it would require to fix what is essentially a (more or less) rare graphics glitch.
@@Sylfa How would a physics engine normally account for the situation you just described?
Brilliant. That's 2 videos of yours I've stumbled across, And both times I left a little more enlightened. Thank you. Subscribed.
Movement on platforms that are not on angle of 0 degrees would be a topic I would like to see you discuss about. Cherzz.
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.
What about 2D games? Are the concepts more or less aproximately the same?
Blazervania X Yes, in general it's the same but with the condition that you don't need to render or check if a collision happens in a 3rd dimension, only X and Y :)
Blazervania X
Way less computation as well.
Glad I found your channel. Very informative and nice to watch.
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.
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.
That would work pretty well in modern games, I believe. But most games stick with straight boxes, because those are far simpler to calculate for, even if there are plenty.
Yeah I'd glady take a tank in graphics for a nicer collision algorithm though.
The second method can be done with moving objects only. Thus saving a lot of work
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){}
Amazing channel! Thanks for uploading this kinds of videos!
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.
Usefull information, 10/10 would watch again IGN confirms.
Damn..., you explained Pruning in just a minute while my prof can't do it in a whole lecture.
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.
I love you for the monster hunter reference XD
You win my subscribe Thx for Quaternions in a Minute
This is a good video and all, but gave it a like because of your positivity! Keep up the good work!
"How collisions work"
They don't ...
ahhahahhahahaaahahahahahaahaha
I love your videos,so fun and nice to watch
I know another thing about hitboxes, there Is a model then when the hitbox hits the model the hitbox doesn't pass
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
Noobs DeSroobs And what would be the etc etc? You must realise that not everything can be covered in a short video.
Fun fact, it is perfectly possible to use the model... at the drawing process, just build a 'box' as you go
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.
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.
Didn't expect to hear about kd-tree here. Really interesting thanks for the video))))
Omg how have I not heard of this channel before? I feel like I just stumbled upon a gold mine!
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!
This even better than some serious collision detection tutorial! I
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.
Or we could accept that not every game needs a destructible level and can stick to a BSP tree for it just like in Doom. Moving Objects can overlap with sectors . No balance possible or needed. Or you mean some pressure when an object has the choice of its favorite parent?
Per sector sort along some main axis (fixed).
Hey it would be great if you can make more videos about these collision detection optimization stuff :)
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
excellent video...
Player: [Fires Gun]
Server: [Raycasts every triangle in the scene]
Player: "SO MUCH LAG!"
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.
Thanks, pretty interesting
I never knew about the last thing. Good that i watched this video
Nice explanation ❤
Thank you very much. A very valuable and informative video.
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
This style of video reminds me of ViHart
You're pretty good at drawing with a mouse.
that's because it's not a mouse
I don't think she draws with a mouse
its meant to a cat
it'd be funny if she read this while having a stylus in her hand.
she is using pen tablet.
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.
Shooting through fluffy clothes and hair does not count as hit.
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.
i really really like your videos. keep it up!!
I love your videos!
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.
Great video, thanks for sharing :)
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 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?
Great video!
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 do you draw twos as if they were alphas?
awesome video! thanks!
You draw so good
i have a doubt.. are hitboxes used in animated movies also???
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.
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.
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?
+Pio Raffaele Fina Yup!
Regressive equations, Splining, Interpolation, Ekstrapolation, FML
Any ideas on solving the bullet through paper problem?
Jozef Dujava calculate the normal, if the bullet position vector is changed it means it's a hit
Well, couldn't you also just check for every hitbox, if another hitbox is inside it? Then, you do the computations for what happens when those two hitboxes collide. Wouldn't that be more efficient as well, because you're not checking every possible pair?
That's *precisely* what "checking every pair" is, isn't it?
If you have boxes A,B,C you'll check:
A,B [= B,A]
A,C [= C,A]
B,C [= C,B + you already did check B,A]
[C was already checked against A and B]
That's each pair OR as you put it: for every hitbox, we checked every other hitbox.
No, I meant just check every hitbox for another hitbox.
if hitbox in A, check new hitbox type
if hitbox in B, check new hitbox type
if ...
Now do you get what I'm trying to say?
I'm afraid I can't follow
Well whatever then... :/
The problem is that *you* as a human can tell which hitboxes are overlapping, but a computer can't. For the computer, to be able to tell if a hitbox is inside another hitbox it has to check that pair.
Unless you mean grouping the hitboxes together in some sort of tree so you can check against the bigger group first, and the continue downwards, which is what the video describes towards the end.
In either case, your not describing a new method, your rephrasing what the video already showed.
PS the only reason you can tell which overlap is because you have a neural network that spends massive amounts of parallel computing time to determine what you see in front of you.
very detailed very helpful
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
And even Game Theory made a video talking about the physix of the game, it was sponsored but hey, it's just a theory
Marcos Barrionuevo link to the video please?
Ah, but War Thunder can afford that. Simple graphics for the surroundings and few moving objects let them implement very complex collisions and penetration computations. Especially when we're talking about in-flight part of the game.
Love watching these videos... I wish I was smart. :(
why is it that in everyone of these videos there's someone saying...
"oh your wrong because of blah blah blah".
I'm no computer scientist but I wouldn't click on this video because I knew the answer to the statement on the thumbnail. Hell, I watch these videos to learn something new.
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
+NotAGoodUsername360 It is not possible to convert a mesh into a vector... they are very different things...
Unit 978 A mesh is nothing BUT a series of simple linear 3D vectors drawn from anchor points. And yes, they can be simplified to single equations, albeit very complex ones.
What I'm thinking of would basically be the computer physics equivalent to supersampling- you'd take a hitbox, find the parts of an object within that hitbox, refine the many simple 3D vector lines into a single complex vector field, and use that vector field as a secondary hitbox that is solely called upon when a collision is detected from the simple hitbox, and evaluates whether or not the collision flag is tripped based on whether or not the complex hitboxes detect collision.
And yes, you can totally do that through hardware. High-level graphics cards do pretty much just that all the time with supersampling, and it'd basically be the same thing on a much bigger scale.
...come to think of it, the PS3's cell processor probably would have been perfect for such a function, had it been properly demonstrated and explained to developers.
+NotAGoodUsername360 Yes but you said a wire mesh to a 3D vector ... but wire meshes are already a series of vectors. But games do not really need model perfect collision detection. Assume that there is a chip that does this collision detection there is still the overhead of updating data between the CPU and the collision chip, just like with GPUs and CPUs
Unit 978
I did say vector, SINGULAR, did I not? And yeah, they don't NEED it right now, but if VR becomes a common thing, or even interactive/pseudo-tactile holograms? Advanced collision detection will be IMPERATIVE for responsive, fine-tuned tactile interfacing. That, and it would also make building soft-body physics engines VASTLY easier and less memory intensive to build.
And the response from the collision detection refiner would be binary: if [object location] = [rough hitbox area], then ([refine hitbox]; if [refined hitbox] = [object location], then [collision] = true, else [collision] = false) else [collision] = false.
I know that's massively oversimplifying and needlessly complicating the collision detection algorithm logic, but if you did the entire sub-loop in hardware the computation latency would be microscopic, even when frequently called upon, as because it's binary you can easily see how you could do it all with pure conductors.
+NotAGoodUsername360 But you can't have an entire mesh be 1 3d Vector. You lose all mesh data. That is the only reason I replied. But also collision information would be needed from the chip for the physics collision response, such as how the intersection occurred.
I learned a little about this when I was making my M.U.G.E.N. roster! Great videos you have! Love them! :D
I don't get it. Back in the Commodore C64 days, once two things had any of their pixels touch, that was a collision. How hard is it for modern computers/game engines to do that? I mean it was for only 2d games, but the same hitbox idea is still needed for 2d games today.
I'm having a problem with the pruning tree... If somebody is at the center of the game level and shoots a bullet, then it could hit anything in the four other areas, creating computational problem again... I'm missing the point, I think.
But only a small portion of the objects in the scene is overlapping into multiple bounding volumes, so you don't have to check every pair.
Actually, I use quite high poly models, but I use accurate collision at around 54-75 fps on my first person shooter game
1:15 "for each object on the scene" i kinda disagree, you can simply do a basic distance check (depending on the size of the hitboxes) to see if a collision is even possible
that's a very naïve method. very common mistake. if you have 1k objects in the scene, you would need to do 1k distance check against 1 bullet. now if there's 100 bullets, you'll need to do 100k distance check every frame. very inefficient. The pruning tree method shown in the video is what being used in practice. did you even watch the video till the end?
Seyha Leonhartz first of all, you can check square distances, that requires no sqrt max(abs(x1-x2),abs(y1-y2)) highly innaccurate, but much quicker and sufficient when you know an objects biggest size
second, there will never be 100 bullets at the same time unless they move very slow
third, did you even read my comment?, i never said it was efficient, i KNOW its a slow method, i simply stated that it would be wrong to say you have to check every polygon or whatnot on EVERY model, when you can check the polygons on just the ones near the bullet
IM NOT talking about whether its efficient, im talking about that she said "for each object on the scene"
please read the comments more properly
EnderCrypt
First of all, bullet isn't the only thing you need to check collision for. player characters, enemy npcs, moving platforms, grenades, and many other things that don't just collide with the player but also other objects and even themselves.
Secondly, your first comment was arguing a moot point. you're offering an optimization method that she was going to talk about. she mentioned the pruning tree method that would solve the efficiency issue, and then you come in arguing on a problem that she already tell how to solve. and I feel the need to comment because I want you to know that there's a better solution right there in the video.
Seyha Leonhartz
yes thats correct that she offered a better solution
me:
"for each object on the scene" i kinda disagree
yes, it might been a "moot" point, but i just wanted to bring that 1 thing up because why not
wheater its efficient or not doesent matter, it was just that quote that seemed to imply that to check each polygon for collision would imply that checking would require going through all non-static objects
EnderCrypt
Well, I don't see why you need to disagree or have anything to disagree with because she obviously know that.
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
damn we need more videos like that i like ps4 but i hate collision its still thye same problem since ps1
Yeah! Super video! :D
Why dies it have to be boxes? Why not make the actual model the hit box?
why is collision detection on a characters model surface such a problem? isn't that what we're already doing with lighting and reflection?
Jazoray nah cuz. The gpu is doin dat
Ultimate Urinater
do collision detection on the gpu then
Jazoray from what I know. The shader can't really return anything. We simply give it our vertices and matrices to modify those vertices. And that's it. The CPU needs to be in control of the actual game itself. I think?
Fast and interesting. Thank uu
You must be great game dev ☺
O witam
Nice video!!!
*Hysterically laughs in polygon collision*
[Spherical Cows in a Vaccum Intensifies]
Hey Cat,
Not sure if you've done other videos on this topic or not. I'll look at your playlists . . .
That said, I've been playing "Sniper Elite 4" by Rebellion and I'm very intrigued by what is going on "under the hood" with their collision detection / hit box mechanics given the way a one shot kill can work if one hits a vital organ while sniping. If you haven't played it, here is a sample of kill shots from the game
ruclips.net/video/4cvCMEuHHK8/видео.html
That video can make it seem like a hit = a kill every time but it doesn't, at least not on Normal or higher difficulty. Sometimes a hit will just stagger the enemy, and cause him to squat and search (and seemingly does cause some "damage" to it, which can eventually kill if enough non-lethal shots accumulate). Other times, it causes a fatal wound which doesn't immediately kill him but causes him to drop and call for help, thus allowing for one version of the "baiting" mechanic the game implements (if you "bait" an enemy and then kill them, it is worth more experience points).
One thing I've always disliked in shooters is the "enemy as bullet sponge" mechanic that emerges from the use of a generalized "hit point" system. A fully realistic combat trauma model is probably never going to happen in a computer simulation that isn't specifically focused only on that topic, but something "more" realistic is always nice. It seems to me the system in SE4 is a step in the right direction, and I would love to understand what they have done to achieve this.
If you have n objects then there are O(n^2) pairs to check not n choose 2.
If you have 3 objects (A, B, C) you would only need to check for collisions for (A, B), (B, C), (A,C) because you have to consider only unordered pairs. However O(n choose 2) = O(n^2), but the actual calculations count is lower with n choose 2.
Just noticed n!/(n-2)! reduces to n(n-1) ~ O(n^2). Oops. Whenever I see n choose k I immediately think exponential. My bad.