Hey, everybody! Thanks for watching this video. If you have any questions or suggestions, please comment! I'm currently investigating solutions for 2D collision detection and response for arbitrary convex polygons, so please be patient as these examples take a bit longer to code.
omg finally!! I've been breaking my head trying to figure out how to do collisions, I even tried to check for imaginary points in front of a rectangle to see if they were inside of the platforms. Thank you!
Thank you so much for this Video! A little addition: If you have 2 collisions at once while sliding aorund a collider wich transitions into another collider, it could happen that you stuck on the first collider based on wich collider you check first. The solution is to check that collider first you are overlapping the most with.
Yeah, the only real way to prevent tunneling is if you start from a scene with no collisions and move objects back along the vector they moved into collision on until all collisions are resolved.
That is way more interesting but also way more complex. The good thing about it is that swept shapes are always convex, so you can use something like SAT or GJK to test for collision. I have a GJK example on the website, but I never implemented a collision response system for it. It only detects collision. For the response, you would have to figure out the amount of time it takes to move each shape back along its vector of movement in order to move it to the exact position just before it entered collision. It would be a fun project if I had a few weeks to fry my brain on integrated physics math. Not sure it's worth it, though. Most games are way less complicated or just use a physics engine.
this is a really good collision detection, but here is a problem. So if platforms are snapped to grid like a tile map and when the player is sliding on walls, it just gets stuck by top or bottom collision. Are there any solutions how to fix this?:)
Absolutely. This method is best for independent bodies, but when it comes to tiles there's a few ways to do it. One way is to do y collision first, then x or vis versa. That is taught in a lot of tutorials I've seen. The way I like to do it is to have specific collision shapes for my tiles. If your tile is only able to be collided with on the left side, only let it do collision on the left side. If you have a big wall on the right side of your level, those collision tiles should never result in a collision with the player's top, bottom, or left sides. You can have collision types that do top collision, top and bottom collision, left, top and bottom collision, or all sides collision if it's exposed on all 4 sides. If you are procedurally generating your level, you can determine what type a tile should be by checking its neighboring tiles to see if they are exposed or blocked by another tile and choose the appropriate collision type. I have a tutorial on this. Go to the website and search for "tile" and it should come up. I think it's "tile types".
for simple discrete AABB vs AABB you can replace the old position with the velocitiy, something like this: if(collision_detected_x) { if(velocity.x > 0) //coming from the left { //resolve collision on x } else /coming from the right { //resolve collision on x } } if(collision_detected_y) { if(velocity.y > 0) //coming from the top { //resolve collision on y } else /coming from the bottom { //resolve collision on y } }
But, check for collision with all objects in each frame is not bad? If I want, for example, the objects to collide with another objects, it would make the game performance bad... We would had a n² number of checks in each frame What should I do in this case? Thanks for the video man!
That is an excellent point and it's a real issue to consider. The solution is spatial partitioning. There are many ways to implement this in a game, but some common ways are binary, quad, and oct-trees. You can use a grid as well. Tile based games naturally take care of spatial partitioning for the world's boundaries. Many games simply limit the number of objects on screen at any given time. Your choice should depend on what type of game you are making. I personally lean towards grids and limiting sprites because those go well with tile based games. I may make videos on this topic because it is so important.
@@PothOnProgramming Thanks for the answer! I'm trying to make a grid, but the problem I have been dealing with is that it's difficult to update the objects position on the grid I would be really thankfull if you do a video about that!
I plan to, but it will be some time. An important part of that is knowing how to determine what grid cells an object occupies. Remove objects from the grid when they move and reinsert them when they stop on each cycle. But it's also important to consider that it may not pay to implement a spatial partitioning system if it's going to cost more to run than the collision checks.
You can. It's not a perfect solution mainly due to the slow down you mentioned, but also because tunneling is still possible, it's just really reduced.
The most effective solution I have seen is "sweeping" or "swept shapes". To get the swept shape, you basically form a convex hull around the points in the shape's last position and current position to form a big polygon, then test for collision with the swept shape of your other collision object. If you have a collision you move your shapes back along their movement vector until it is resolved. You can use GJK collision detection and EPA collision response to do this. That's a rather complex method, however.
Thank you for the video, unfortunately I was already wondering why the collideRectangle discards any non-colliding rectangles. In the figure showing the sweeping iteration, it can be clearly seen that tunnelling can also occur without any intersection in either the previous frame or the current frame. Also, I think not using a library for 2D vectors is not the most elegant decision. (I have to admit, I did not watch the video to the end.)
I try to stay away from libraries for the sake of keeping the js as pure as possible, but for production, yeah, it's safer and easier to use a library. Also, this doesn't cover sweeping. That would require convex polygon collision because the swept shape is no longer a rectangle. That would be the ideal way to eliminate tunneling, though. And I see your point about the early out. If you early out based on simple checks and then test the more complex cases, you might miss a more complex collision. Eventually i want to get back into making videos and a lot of my existing videos are going to get tuned up. This is probably one of those things that needs revision. Thanks for catching it.
@@PothOnProgramming Hi there, I've managed to find a working version for the sweeping problem today in Christer Eriscons Real-Time Collision detection book. Basically the IntersectMovingAABBAABB (pp. 231-232) is more or less the necessary code. It is based on the seperating axis theorem. But his example is not 100% complete (as the collision response is missing) and there is a typo in the code. A less restrictive test for intersection can be the bounding box/rectangle around the previous and the current bounding box/rectangle. In the book it is also described that it might be possible to do a sort of binary search between time positions between the previous and the current frame (which he terms interval halving). About the video, maybe I was just confused to see the sweeping figure while the problem wasn't covered initially. On the other hand it was good to have a figure to show some things that can go wrong.
@@necrowizzard1569 That's good info. The way i eventually wanted to implement it was to get the convex hulls of the two swept shapes using their current and previous positions, then use GJK collision detection to test collision. I don't think you'd need a binary tree to work out where to place shapes for the collision response. You know the amount of overlap and the direction to move both shapes. Seems like it could be done with a formula in one shot. No recursion or iteration. Just make the convex hulls, test the collision, get the response positions using the formula. Of course i don't know what that formula is. I have a working GJK implementation, but never got around to doing swept AABBs.
I don't think this is an example of tunneling. I thought tunneling were when the program doesn't run quick enough so if you for example have a really tiny platform in a 2D game you can fall through it if you have enough speed because as you kind of explained it skipped the collision by moving with a big step.
Hey, everybody! Thanks for watching this video. If you have any questions or suggestions, please comment! I'm currently investigating solutions for 2D collision detection and response for arbitrary convex polygons, so please be patient as these examples take a bit longer to code.
omg finally!! I've been breaking my head trying to figure out how to do collisions, I even tried to check for imaginary points in front of a rectangle to see if they were inside of the platforms. Thank you!
Just keep in mind that this approach is susceptible to tunneling. It's still a decent way to do platform collision though.
you just ended days of frustration trying to figure out collisions in Flutter Flame Game. Thank you.
Thank you so much for this Video! A little addition: If you have 2 collisions at once while sliding aorund a collider wich transitions into another collider, it could happen that you stuck on the first collider based on wich collider you check first. The solution is to check that collider first you are overlapping the most with.
Yeah, the only real way to prevent tunneling is if you start from a scene with no collisions and move objects back along the vector they moved into collision on until all collisions are resolved.
very helpful love the visualizing examples
Good Video and Explanation, but I would've enjoyed to hear more about of sweeping / swept volumes, instead of tips like "make it move less".
That is way more interesting but also way more complex. The good thing about it is that swept shapes are always convex, so you can use something like SAT or GJK to test for collision. I have a GJK example on the website, but I never implemented a collision response system for it. It only detects collision. For the response, you would have to figure out the amount of time it takes to move each shape back along its vector of movement in order to move it to the exact position just before it entered collision. It would be a fun project if I had a few weeks to fry my brain on integrated physics math. Not sure it's worth it, though. Most games are way less complicated or just use a physics engine.
That's what I should do for monogame! Use an object rectangle! Not a sprite list class! This makes sense!
this is a really good collision detection, but here is a problem. So if platforms are snapped to grid like a tile map and when the player is sliding on walls, it just gets stuck by top or bottom collision. Are there any solutions how to fix this?:)
Absolutely. This method is best for independent bodies, but when it comes to tiles there's a few ways to do it. One way is to do y collision first, then x or vis versa. That is taught in a lot of tutorials I've seen. The way I like to do it is to have specific collision shapes for my tiles. If your tile is only able to be collided with on the left side, only let it do collision on the left side. If you have a big wall on the right side of your level, those collision tiles should never result in a collision with the player's top, bottom, or left sides. You can have collision types that do top collision, top and bottom collision, left, top and bottom collision, or all sides collision if it's exposed on all 4 sides. If you are procedurally generating your level, you can determine what type a tile should be by checking its neighboring tiles to see if they are exposed or blocked by another tile and choose the appropriate collision type. I have a tutorial on this. Go to the website and search for "tile" and it should come up. I think it's "tile types".
I don't really understand the old and new position. I am trying to re-create it in my code but both values read the same
for simple discrete AABB vs AABB you can replace the old position with the velocitiy, something like this:
if(collision_detected_x)
{
if(velocity.x > 0) //coming from the left
{
//resolve collision on x
}
else /coming from the right
{
//resolve collision on x
}
}
if(collision_detected_y)
{
if(velocity.y > 0) //coming from the top
{
//resolve collision on y
}
else /coming from the bottom
{
//resolve collision on y
}
}
Sweeping wont work if either of the cubes rotate during the journey, will it? I mean, if the cubes can be rectangles.
But, check for collision with all objects in each frame is not bad?
If I want, for example, the objects to collide with another objects, it would make the game performance bad...
We would had a n² number of checks in each frame
What should I do in this case?
Thanks for the video man!
That is an excellent point and it's a real issue to consider. The solution is spatial partitioning. There are many ways to implement this in a game, but some common ways are binary, quad, and oct-trees. You can use a grid as well. Tile based games naturally take care of spatial partitioning for the world's boundaries. Many games simply limit the number of objects on screen at any given time. Your choice should depend on what type of game you are making. I personally lean towards grids and limiting sprites because those go well with tile based games. I may make videos on this topic because it is so important.
@@PothOnProgramming Thanks for the answer!
I'm trying to make a grid, but the problem I have been dealing with is that it's difficult to update the objects position on the grid
I would be really thankfull if you do a video about that!
I plan to, but it will be some time. An important part of that is knowing how to determine what grid cells an object occupies. Remove objects from the grid when they move and reinsert them when they stop on each cycle. But it's also important to consider that it may not pay to implement a spatial partitioning system if it's going to cost more to run than the collision checks.
can we not use loop to solve tunneling to some extent? But it will slow down the game.
You can. It's not a perfect solution mainly due to the slow down you mentioned, but also because tunneling is still possible, it's just really reduced.
The most effective solution I have seen is "sweeping" or "swept shapes". To get the swept shape, you basically form a convex hull around the points in the shape's last position and current position to form a big polygon, then test for collision with the swept shape of your other collision object. If you have a collision you move your shapes back along their movement vector until it is resolved. You can use GJK collision detection and EPA collision response to do this. That's a rather complex method, however.
@@PothOnProgramming GJK and EPA? Those are new terms, i will look into them. Thanks
@@abhinavsinghchauhan1951 I have a working GJK implementation here: pothonprogramming.github.io/content/gjk/gjk.html
Thank you for the video, unfortunately I was already wondering why the collideRectangle discards any non-colliding rectangles. In the figure showing the sweeping iteration, it can be clearly seen that tunnelling can also occur without any intersection in either the previous frame or the current frame. Also, I think not using a library for 2D vectors is not the most elegant decision. (I have to admit, I did not watch the video to the end.)
I try to stay away from libraries for the sake of keeping the js as pure as possible, but for production, yeah, it's safer and easier to use a library. Also, this doesn't cover sweeping. That would require convex polygon collision because the swept shape is no longer a rectangle. That would be the ideal way to eliminate tunneling, though. And I see your point about the early out. If you early out based on simple checks and then test the more complex cases, you might miss a more complex collision. Eventually i want to get back into making videos and a lot of my existing videos are going to get tuned up. This is probably one of those things that needs revision. Thanks for catching it.
@@PothOnProgramming Hi there, I've managed to find a working version for the sweeping problem today in Christer Eriscons Real-Time Collision detection book. Basically the IntersectMovingAABBAABB (pp. 231-232) is more or less the necessary code. It is based on the seperating axis theorem. But his example is not 100% complete (as the collision response is missing) and there is a typo in the code.
A less restrictive test for intersection can be the bounding box/rectangle around the previous and the current bounding box/rectangle. In the book it is also described that it might be possible to do a sort of binary search between time positions between the previous and the current frame (which he terms interval halving).
About the video, maybe I was just confused to see the sweeping figure while the problem wasn't covered initially. On the other hand it was good to have a figure to show some things that can go wrong.
@@necrowizzard1569 That's good info. The way i eventually wanted to implement it was to get the convex hulls of the two swept shapes using their current and previous positions, then use GJK collision detection to test collision. I don't think you'd need a binary tree to work out where to place shapes for the collision response. You know the amount of overlap and the direction to move both shapes. Seems like it could be done with a formula in one shot. No recursion or iteration. Just make the convex hulls, test the collision, get the response positions using the formula. Of course i don't know what that formula is. I have a working GJK implementation, but never got around to doing swept AABBs.
pog
Lit fam
I don't think this is an example of tunneling. I thought tunneling were when the program doesn't run quick enough so if you for example have a really tiny platform in a 2D game you can fall through it if you have enough speed because as you kind of explained it skipped the collision by moving with a big step.