This is a fantastic video! Thank you so much for it! Something I'd like to add is that, if you want to convert the DynamicRectVsRect to a DynamicRectVsDynamicRect you can simply take the velocity of the second rectangle and subtract it from the first one, then use that difference as the direction vector of the ray in the collision detection. Properly solving dynamic collisions however would require some soft of recursive algorithm to get it to work between more than two rectangles at a time, to solve each collision in the order in which they occur. Edit: Having now implemented the code demonstrated in this video, it works quite well, though I did stumble upon a couple of small issues that I managed to fix. First of all, tNear can sometimes become way less than 0 when moving slowly in the opposite direction due to floating point errors, in which case the player (or any object using this same collision check, I'll just say 'player' from now on for simplicity) can be snapped backwards through a wall. The solution is to say it's not a collision if tNear is less than 0, or in reality less than a small negative value, otherwise we get more floating point errors that cause some collisions to get missed instead. Ugh, floating point numbers... The second thing is the fact that the literal edge case of colliding into a corner is not handled in your code, meaning it's possible to clip through walls when you hit a corner. In your implementation, this is masked not only by the fact that it's a rare occurance but also by the fact that tNear is allowed to be negative, so if the player clips into a wall one frame then they're likely to be clipped back out the next. However, that's not the case if you don't count negative tNear values as collisions. In that case you need to handle corner collisions, -otherwise the player will be able to wall clip- (edit: I realized it wouldn't enable them to wall clip, just that the normals wouldn't be handled correctly). You could choose to make it collide in both axes if you collide with a corner depending on what you're doing, but in my case since I'm making a platformer that would just make the player get stuck on corners momentarily in case such a collision occurs, so I've chosen to handle it as vertical collision in my implementation which works better for that use case. Sorry for the huge wall of text. And again, huge thank you for making this video! It's great to finally be able to escape Unity's own collision system for simple 2D games.
How would you fix the issue with corners? Right now I am able to phase through tiles in my game by falling through a corner, and I can't seem to fix it.
@@undersquire I realized that the fix I did for handling the edge case didn't actually have an effect on being able to wall clip, because that wasn't a problem with the original code to begin with. I realized the issue I fixed was just that the normals wouldn't be handled properly if you hit an edge, which wouldn't have made you wall clip anyway. Double check your code against the code in the video because it should work just fine without any wall clipping issues. If that doesn't help, use the Visual Studio debugger to step through your code with break points and watches to understand what your code is doing, particularly what it's doing when you fall through corners. Other than that I can't really help you without seeing your code.
@@OllAxe I have already spent several days trying to debug it with no luck. The code is the same as the one in the video, so I have no clue as to what is happening. Here is my code if you wanted to take a look: pastebin/XAxXQaWC (UA-cam won't let me send the link, so add in the rest ;/ ) It seems that corners are where I am able to phase through tiles, but I am unsure as its a rare occurrence. EDIT: I am not using PixelGameEngine for my game, so there are subtle differences in the API.
@@undersquire Whew, it took a couple of hours not having access to any of the tools to be able to run and step through the code, but I think I managed to fix the bug for you the same way I fixed it for me. Here's the pastebin: Ad9urmwK All the changes I made are commented as "//FIX:" or "//NOTE:" with more info about what I changed and why. I hope that helps!
@@OllAxe Oh wow this worked! Thank you so much haha, spent way to long debugging this and your fix worked perfectly. Hopefully this can help save anyone else hours of debugging if they run into the issue.
Hi! I've found a logic bug in the "bonus side effect" you mention at 42:50 It's correct that you don't alter the velocity in the opposing axis of the one you collided with, BUT here you are altering the velocities direction!!! And if in that direction there are colliders you have excluded out (not resolving because they werent in your direction before) you are gonna clip with/ totally miss them in case of diagonal collisions with a close rectangle. Thanks a lot for your tutorial, I managed to code my own javascript implementation of your code, and my (really) ugly fix was to run the whole collision check recursively when all these conditions are met: -the object was initially moving in BOTH axes -at least one collision resolve happened This means it can run up to 3 times (per frame) when close to corners in a diagonal vel direction: First time: resolves the direction to not meet one of the axes of hypotetical corner Second time: meets the other axis of the corner, resolves Third time: still in a diagonal velocity towards corner, but since both velocities have been cut by previous adjustments, no collision is found at broad phase. There are many more efficient ways than mine to resolve this slide-clip behaviour, but I think I made a point: if you change the direction, expect eventual colliders which were still part of the group of the first broad phase cut (when you add the initial velocities to your size and simple check with everything), but were cutted out from resolving because they werent in your direction during line vs rect. Had to debug running the game loop at 2 fps to follow up what was going on with the diagonal collision at moderate/high speed and isolate the bug to get a grip of the occasional clipping.
So this is how the old Super Mario speed runs happen. When they get so good they frame-time, clip, and run through solid objects. So cool. Awesome tutorial, and it's practical for every engine.
I've done some corner clips for speed. .I"m not a great speedrunner at all, but sometimes I get a wild hair and decide to grind a level until I'm good at it.. Here's one of my recent ones.. I've taken another frame off since too ua-cam.com/video/F94cr34zu64/v-deo.html
I've been working on a game, and I was looking for a good way to detect and found my way to the case where the object is moving too fast. The vector intersection projection is exactly what I need, and you are a saint for making it so digestible.
Thank you so much for making this video! I'm working on my first project of the year at uni and implemented your system. I was struggling with all the issues you listed in the beginning too, so it was great to see you also cover them.
Honestly, thank you very much for all of the effort you put into your videos. I can't stress how valuable and amazing your content are. From the bottom of my heart, thank you! thank you! thank you!!!!!
I deleted my old comments because I finally figured out everything I was doing wrong. This video helped me figure out my AABB collisions, thank you so much!
Funny how I recently built this platformer engine and bumped into every one of the problems that were mentioned here (no surprise). Would have been a lot easier had this video existed before writing the engine. Great stuff!
I just discovered this channel while looking for a solution for a proper 2d collision detection. Although I have never coded in c++, this was easy to implement in javascript. Thank you!
I’m currently trying to work out collision detection and resolution, so this video has been super helpful. It gives me some ideas on how I can approach the problem that I hadn’t thought about. Thank you for explaining the problem so well!
Note: I've found that the double-raycasts are required as far as I can tell. The player's state doesn't change between collision checks in the initial loop, but it does when the resolutions are performed. I was getting that 'tripping' behaviour when I tried to reduce it to one check loop. Fantastic tutorial, really good explanation of the mathematics behind this sort of collision resolution, and it's portable (I followed along in C#)!
Glad you are posting this videos out here on youtube, just had a hard time porting this to 3D and joining the logic with your quad tree videos, but its finally working now!
Great video! Thanks for all the explanations and also for sharing source code. Usually with Tiled Map I used a different approach, but I want to try this approach for sure now! Hope to see you soon!
Well thats it Luca, theres a variety pf techniques and you should evaluate whats best for your needs. I feel the approach shown in the video is a "catch all" technique, but not necessarily the most optimal.
Me seeing this vídeo late in thr night: Oh, it's an hour long and I'm falling asleep, no way that I'll watch it today... Me an hour in later: Oh... that's so good!
Even though I am not a C++ coder and have I yet to get aquainted with the PGE, quite often when I'm coding other stuff myself I have these videos of yours playing on the side and I very much enjoy the mathematical and logical tricks you point out, especially when you jot them out. Also, your soothing way of speaking works like a charm. Very intriguing. 🤓
I only just started watching but I must say I'm looking forward to your video on networking. I have built a network multiplayer engine myself but I feel that it's tangled and not as convenient to use as I'd like it to be. Part of the reason why is that I can't seem to find any definitive wisdom about it online. As a result I just ended up implementing a module that manages some TCP sockets with a basic abstraction layer on top. The user still has to manually decide which variables define the game state and when to synchronize them. I would love to build a system that completely encapsulates networking, allowing the user to make a game as if it was a singleplayer game. This has been exceedingly difficult due to all the little optimizations that are necessary to make the game feel nice to play, particularly in the case of a first-person shooter with mouse controls. Anyway, I'm looking forward to this video as well. I've learned doing AABB collisions a long time ago but I'm very interested to hear someone else's perspective as finding good sources on this is still difficult.
Definitely that's is a obscure info, search for good topics or posts in forums is hard and the most cases is a variant of the same article =\ I working in a personal project for two year and I remember changed the entire struct for the networking 3 times. In my last attempt I get all my code write in c++ and make it on Go because is more elegant and easy to manage (sorry bad English)
At around 34:30, you really ought to mention that expanding the target rectangle using the dimensions of the source rectangle is taking the Minkowski Sum of the two rectangles. It's very useful and generalizes to other shapes and dimensions too. As a side note, I've been playing around with physics engines for several years now, and it's nice and very validating to see that we've come to the same conclusions about a lot of things.
Aaron Wright though you are technically correct, He describes the required math elegantly and a fancy term for the convolution of polygons can confuse and scare newbies.
The fun thing is, the swept AABB collision can be extended quite easily (well, more maths, but same vector artihmetics) to any convex polygon vs convex polygon collisions, no matter the orientation. Then you can add spheres into the mix, or more complex convex geometry (capsules, ect). If you want slopes, roughly shaped terrain, triangles, it's a great way to do it. Technically, it's all based on the the SAT (separating axis theorem), the case between two AABBs is just a special case of the more general algorithm. Similarly, the 2D case is a special case of the 3D algorithm, so extended to 3D is also trivial, you just have many more 'axes of overlap' to check (face normals, and edge cross products). And if you want to deal with intersections, you can also use the same SAT checks for free to work out the potential intersection vectors (the vector you need to use to push the objects away from each other a minimum amount to resolve an intersection), like you did at the start with the 'non-swept' intersection detection. What I find hard, is the problem you highlighted, resolving for the best response when you encounter multiple simultaneous collisions and intersections. Algorithmically that's can get real ugly real fast, which means, nasty unpredictable bugs and weird behaviours.
Glad you included ending thoughts about culling and optimization. I think I like your "I make a big bounding rectangle including both start and end position" approach!
I like your videos. Always interesting topics. I implemented it in Java and learnt a lot. However, I found a bug that drove me nuts. In principle, it worked, but sometimes my rectangle would jump around. E.g. my rect touches the horizontal border of the other rect then in some cases, the program would reposition my rect to horizontally align with the left border and then the right border of the other rect in quick successions, even though they are totally irrelevant at this point. Turns out, the algorithm got tripped up by a *𝙽𝚘𝚝-𝚊-𝙽𝚞𝚖𝚋𝚎𝚛* value, e.g. in case *( 𝚛𝚎𝚌𝚝.𝚢 + 𝚛𝚎𝚌𝚝.𝚑 - 𝚙𝚘𝚒𝚗𝚝.𝚢 ) == 𝟶* and *𝚟𝚢 == 𝟶* then *𝚝_𝚏𝚊𝚛_𝚢* would be zero divided by zero, and we get *𝙽𝚘𝚝-𝚊-𝙽𝚞𝚖𝚋𝚎𝚛* instead, because the computer cannot determine the sign. I needed to handle that manually: 𝚏𝚕𝚘𝚊𝚝 𝚝_𝚗𝚎𝚊𝚛_𝚡 = 𝚟𝚡 != 𝟶 ? ( 𝚡 - 𝚙𝚡 ) / 𝚟𝚡 : ( 𝚡 - 𝚙𝚡) >= 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈; 𝚏𝚕𝚘𝚊𝚝 𝚝_𝚏𝚊𝚛_𝚡 = 𝚟𝚡 != 𝟶 ? ( 𝚡 + 𝚠 - 𝚙𝚡 ) / 𝚟𝚡 : ( 𝚡 + 𝚠 - 𝚙𝚡) > 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈; 𝚏𝚕𝚘𝚊𝚝 𝚝_𝚗𝚎𝚊𝚛_𝚢 = 𝚟𝚢 != 𝟶 ? ( 𝚢 - 𝚙𝚢 ) / 𝚟𝚢 : ( 𝚢 - 𝚙𝚢) >= 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈; 𝚏𝚕𝚘𝚊𝚝 𝚝_𝚏𝚊𝚛_𝚢 = 𝚟𝚢 != 𝟶 ? ( 𝚢 + 𝚑 - 𝚙𝚢 ) / 𝚟𝚢 : ( 𝚢 + 𝚑 - 𝚙𝚢) > 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈;
I'd be interested in seeing a follow-up for non-tile based systems, because I suspect the solution would be helpful for object vs. object collisions as well as object vs. terrain collisions - though with object vs. object collisions there's the added complication that both objects could be moving, in addition to the fact that they generally cannot be guaranteed to be aligned to a grid, so I'd be interested in seeing how to treat that. I've got a few ideas I should probably try out, at least.
This is definitely a topic I think he should cover, some of the collision algorithms for arbitrary objects are quite elegant. *tl;dr:* - Pick the center of one of the objects. - Rotate both objects around that point until the object you picked is axis-aligned. - Add the velocity of the axis-aligned object to the other object so that the axis-aligned object isn't moving. - Do collision detection like normal. - Rotate collision results in reverse around the centre you chose at the start. *If you care about me rambling on for 10 hours:* The best way to get started with something like that is to do the collisions from the frame of reference of one of the objects. You axis align one of the objects, rotate the other object around its origin and add its velocity to the other object (all of this using temporary copies of the objects for the sake of collision). You can think of it like attaching a camera to one of the objects and doing the collision based on what that camera sees (the camera sees the object it is attached to as axis-aligned and not moving). Now you have an axis-aligned and stationary object, and you just do collision detection on the other object like normal. Once you get any collision information such as position and normals, you need to rotate that information in reverse since you had to rotate one of the objects to make it axis aligned. You still need to learn how to collide rotated objects with axis aligned objects, but now all your collision problems involve one stationary/axis-aligned object. Most 2D collision algorithms involving a stationary/axis-aligned object are quite simple. They usually just involve splitting the shape up into lines and testing each of the lines, and picking the line that requires the shortest distance to move to get out out of the axis-aligned object. You then repeat that until none of the lines touch the axis-aligned object. That is a very naive approach and it can be optimised a lot (for example, any line that has a normal that points away from the direction the object is moving can be ignored). You can also do a sweep collision of each line. It's a tiny bit more expensive and complicated but will give you better results for fast moving objects. I've gone a bit off topic now though so I'll stop. Hopefully this can give you an idea of search terms to look for if you're interested to research it yourself.
FWIW I made circle ←→ tile collision in my little Bomberman prototype, and I in fact expect circle ←→ circle to be easier. Circle to tile detection is fine, but resolution took a lot of trial and error... EDIT: Code here BTW: github.com/Cheaterman/Bomberman/
And I finally understand why I have NOT been visited by the bug fairy yet: I tried building a billiards game without GPU and without polygons (mostly - table geometry is still polys, but balls and pockets are not). Ray/ball intersections are done alalytically (a bit messy with sqrt()), and ball/ball intersections are the same; I use a ray for the moving ball and a sphere twice the size for the stationary/slower ball. To get collisions right, I have to try them all and then compute physics for the one that occurs first. (Ball/pocket contacts are always calculated last, because if the contact is too fast to be detected, it would be too fast to fall either.) Which means that I had the sorting already in it before testing.
This was a really dense one, but I really liked it. I'll have to watch it a coupe of times and play around with the code myself to wrap my head around it. I'm curious, how is your process of debugging? I'd be glad to watch a video of you explaining it, or going through an example like the velocity bug you mentioned.
This video was very useful, I tested the system using Unity C #, I will use it for my HTML5 game with the optimization mentioned in the last minutes of the video.
Doom has that glitch you mentioned about passing through walls. As long as you are moving fast enough for doom guy to clear the wall in a single frame, you will clip through the wall. Bouncing off the walls at a certain angle can cause acceleration to build without moving, and eventually you "void glide" through the wall. This would probably explain a lot of bugs in other games where you can fall through the world or jump through a sloped wall.
I think you may have introduced a potential bug at 38:40. You set velocity to direction and magnitude multiplied by elapsed time, then pass it into DynamicRayVsRect, where you multiply it by elapsed time again to create the ray. So effectively you've got velocity * time^2 as the length of your ray. But I don't know how much of an impact that may actually have on the calculations :)
A nice method for continuous AABB collision I've thought of is just clamping the hitbox's collision to the max of the left hitboxes right sides and min of the right hitboxes left sides in it's broadphase rect, also top and bottom etc. So far I've had no issues with the algorithm and it works at crazy speeds, not to mention the simplicity of it (only 50-60 lines) and no complex maths at all with ray casting. I got it working with moving collisions, in fact keeping the player to moving platforms is easy with a bit of extra code. Hope this helps anyone!
One simple method I used in one of my games was I checked if the right side of the first object was less than the left side of the second, than no collision. If the left side was greater than the right, no collision (checking the X axis obviously), then I check if the bottom is less than the top, and if the top is greater than the bottom. For each of these checks, I have it return false if any of them fails, this makes it much faster as most of the time, two objects are nowhere near each other and so this can make the collision routine return quickly. If all four of these checks fail, than we definitely have a collision between the two. In my game I check for a collision when the player moves. In the case of hitting a wall, I move the player, then check for a collision, if there is one, I simply move the player BACK to his previous location. So I would add the new XMove and YMove, check collision, if true (with wall), than subtract those same values. But in my game the player doesn't move terribly fast so this results in hitting a wall and no more movement in that direction. Another thing I have done is if I want the player to be able to SLIDE along a wall, than the direction the wall is in I will subtract that movement; say, the wall is in the X direction, you subtract the X so it no longer moves in that direction and only add the Y movement component (unless there is also an object there, in say, a corner) and this way, the player can slide along the wall, which is desirable for certain games. My favorite is still circular collision, but I seem to recall optimizations for AABB which makes it fast, but it's been a while. Probably the optimizations I just mentioned now that I think about it. LOL
Neil Roy Your initial four checks are exactly the same as the second method he writes at the start of the video, RectVsRect, except he does it in one line of code and relies upon the compiler using “short circuiting” when evaluating the boolean ‘and’ (&&) expressions. I’d be surprised if your version, with separate ifs and returns, was any quicker on a modern compiler.
I was wondering whether it would be useful to refine the collision detection functions to distinguish the case where two things are touching: my feeling is that this is analogous to the comparison functions you pass to a generic sorting routine which give you -1/0/+1 for . So for PointVsRect you might get 1 if the Point is inside the Rect, 0 if it's on the boundary, and -1 if it's outside: possibly the other way around, I haven't thought it through completely yet 🤔 It took me a moment at 24:15 to twig why N_y and F_y are swapped 🤦♂️
Yes you can Phil, but you need to be carefully consistent with all subsequent operations too. Its imperative to actually resolve the collision, so if they are touching, they are still in contact. This may have a knock on effect later down the line.
I tried something similar a few years ago as a project to learn java in, trying to get collision working that would recognise what sides of two rectangles hit eachother, (to get like a mario stomping mechanic) and it was a much deeper problem than I expected. I used the angles which the sprites were moving at I think.
Very interseting video ! Another method to avoid too fast moves that can pass through tiles, instead of rays, get the move vector, if the components (x,y) of vectors are greater than a tile width, subdivide move vector. Move X time, render 1 one time at the end. So instead of considerating fast moves with ray calculation, just avoid this case, and move several time (in memory) then render once at the end.
@@javidx9 Another way to do this is to write a "distance line to rectangle" calculator. This ("in a single calculation") will give negative distance for intersection, zero distance for "just touch" and positive distance for "no intersection" answer without need for any subdivision. This is of course a much more complex calculation (square root but no trig) than determining point-to-rectangle intersection.
I usually teleport the player one pixel above the y of the nearest underlying block, if the player is within its bounds, else I just let him fall according to player->y = player->y + pow(falltime,2) * g
@43:53, something about this line: "vRects[0].vel += cn * olc::vf2d(std::abs(vRects[0].vel.x), std::abs(vRects[0].vel.y)) * (1-ct)" causes my player rectangle to disappear upon contact, what's the problem here? Edit: seems to be because of "ct" being incredibly big either in the positive or negative...
Thank you Javid, I can tell you I was planning to ask you for a quadtree collision detection tutorial, with recursive call, in c++. Please give it a shot, a c++ quadtree implementation in c++. Thank you.
So many calculations per frame, so much floating-point math. I'd love find out about how people got this stuff working on much simpler computers/consoles. I imagine they had to take a lot of shortcuts.
Goodness, just what I needed! (Well, mostly, and I could have tried my best to deal with the original platformer thing 🙂) Edit: 51:20 NOO!!!!!!!! A divide by 0 will throw an exception/crash the program!!!
You're right about division by 0, except that really only happens with integer division. You can try it yourself using floats or doubles, and you should see that it behaves exactly like Javid said. The floating-point standard (IEEE 754) actually allows several different behaviors when dividing by 0, which each program can select for itself. One of those behaviors is to crash the program, but another is to make 0/0 produce NaN, +x/+0 and -x/-0 produce infinity (where x is a positive, nonzero number), and +x/-0 and -x/+0 produce negative infinity. (I may be wrong about how -0 works with this--it's not something I usually have to think about--but I think that's right.) I don't know whether the C++ standard guarantees a particular behavior, or even whether it guarantees that floating-point numbers follow IEEE 754, but in practice, every modern compiler for every language should default to this behavior. I'm unaware of any that doesn't. It is definitely worth thinking about division by 0, though, since it's clearly an edge case whether it crashes the program or not. There's a good argument to be made that it should crash the program, since getting infinity or NaN is usually a bug. In this case, however, he made sure that the infinities would implicitly produce the correct behavior and correctly interpreted the NaN.
@@iProgramInCpp And rightly so. I was only pointing out that his code really does work correctly, even in those edge cases. I'd check for zero explicitly myself, since it's so easy for division by zero to be a bug. (I happen to know that Rust guarantees this behavior on division by zero, and I'd still probably include the checks if I wrote this in Rust.)
ok so my first comment got ignored, okay you made a ray from the bottom left going top right. you colored it orange, at 24:20 you say and rather strangely the near y was where the far y should be. you didnt really explain this. why is it the near y when its clearly the far y. please i cannot continue until this is explained thank you.
I'm not a public service providing answers within 24 hours of being asked. Near time and far time are relative to the tiles axial coordinate system, which is traditionally a top left origin. Since algorithmically the sides of the rectangle are designated near or far originally based simply upon the definition of the rectangle it leads to the rather confusing switch which is puzzling you.
@@javidx9 Wow I didn't mean it like that I meant it probably got ignored cuz I didn't specify I wasn't like hurry up or anything. anyways thanks for answering. that helped.
Since you're using a raycast to test what's between the object currently and after moving, isn't it possible that you could still tunnel through a small gap in a wall? What ways would there be to go about this issue? I think it would make things a bit harder as it would maybe have to be a case separate from when you allow the object to end up inside the floor and then use the normal to shoot it upward.
Rather than do all that math on the highly limited Arduino, I run Pong at thousands of iterations per second and render about 10-20 frames per second. The screen is 128 pixels wide. So 1280 iterations per second means the ball can move across the screen 10 times in 1 second and have pixel perfect collision detection. What I do is set a flag when there's a collision so the frame is rendered so the player sees it, otherwise it just renders a fixed number of frames per second leaving the rest of the time to handle very fine movements and collision checks. By just running the game loop thousands or millions of times per second, you can high very precise collision detection without doing special math checking all sorts of stuff. You don't have to render a frame to the user every time the game loop is processed. The game loop is essentially running in bullet time while the player only sees a limited number of visual renders.
@@javidx9 Well, the paddle is moving and the ball is moving so you have to trace the path of both to see if they intersected between frames. You'd have to know the positions of everything in the prior frame and the positions in the current frame and then do the math. There could very well be a simple bit of math. My project is showing how game mechanics work using simple games and it would probably be a good project to show different approaches so you can compare. And then scale it up. One of the demos I want to make is having a bunch of balls bouncing around the screen.
Hey! I love your videos, especially your "do it yourself" philosofy. I am trying to recreate the va_args behaviour for a freestanding project but I don't really understand the process behind. Can you make a video where you explain how all this stuffs works?
That sounds like a particularly tough one. You'd basically need to create your own argument stack and pop elements from it - IMHO it's one of those things where it's pretty much sufficient to know "how it works" without trying to reproduce it yourself. It is possible - just probably not as fulfilling as spending your time developing game collisions :-)
Hi Javid. I really enjoy all your videos. I grew up with ZX Spectrum and recently started making some bad games in Z80 assembly. It made me think of you because the whole ZX Speccy screen is like a console/terminal in many ways. And I wondered if you would be able to port your ConsoleGameEngine to a ZX Speccy one day and see if you was able to make some kind of 3d shooter with wireframe vectors of something like that... Just an idea for a future video maybe :D (I would bet you have once upon a time already programmed for Speccy, as you seem a similar age to me, but if you haven't maybe you should try it just for the challenge :D )
lol Dave, I cut my teeth on a BBC Micro, so a speccy is not too far away. On the discord server we have a guy who is "porting" the engines to atari 8-bit systems XD
Hey javid! You can lower the amount of calculations and code in PointVsRect, by getting the absolute value of the cordinates and then comparing it by the width or height of the rectangle.
IDK if you will ever read this, but please, make a C++ course or a series. It's a huge request. I am a beginner and I've totally fallen in love with C++. Also, I understand what you teach. Although a lot of it goes by from the top of my head, but still I try to make sense out of things. And this is the reason I want to understand everything from ground zero from your perspective. A huge request 🙏🙏 And if you can't make a course or series, can you please at least guide me from where to start and what to do. Please.
@@javidx9 I totally didn't expect you to reply... 😅😅 Well at least can you please point me in the right direction? Where should I start CPP? How did you get started? What you did? Which resources you used... etc. Please guide me. It's a huge request. Because your videos are awesome the way of explaination is superb but a lot of it just too complex for me. So, please guide me 🙏🙏🙏
You've mentioned doing Dynamic vs Dynamic rectangle collision resolution. Is that available anywhere on your channel? Alternatively could someone recommend some good resources or point me in the right direction on this?
So I have a concern, I have a spawn system that adds monsters to my game when other monsters are taken out. When a new monster is added however & they are within the rectangle of another monster collision happens. I've tried even messing with the spawner logic to check if the new monsters location will land on top of an existing one. Tried slowing down the spawn time, tried checking collision by setting it to false for x amount of time then enabling it but still no go.. There is more, I even tried the typical overlap boolean which sort of works but doesn't at the same time. Spent 4 days approx 16 hours going back to this
Damn, this is so much useful! Thank, OCL for that kind of knowledge you spreadng and explaining in a understandable way. i thought to myself that i would've understand that whole collision routine in a reasonable amount of time if i would read some kind of paper. But you made this whole process not in the matter of weeks for me but a single hour! That is so much appretiated by me that you've earned yourself a patron here. Also i have several questions for you: first of all, i want to start my own series of tutorials but in my native language, russian it is. Can i use your material for that kind of stuff? (with references, of cource) Second, you called DynRectVsRect function twice for any dynamic object in your scene. Wouldn't it be faster to store all of the collide information in such a struct if function returned true (that would be 2 items in array in this example) then sort those structures by time and use it's information to resolve collision, saving time by not computing it again?
Thanks Vilkillian, With correct attribution you can use most of my stuff, but people who have just cloned my stuff tend to get taken down by YT or the community. As for your second point - yes its far more optimal to not call the routine twice, and I hinted at that, but the correct solution would become somewhat specific to how you have established the description of your environment - thus pointless to show here. I took generality and simplicity over optimisation in this instance.
For the second question, I create this struct: struct CollisionInfo { int index; float t_hit; olc::vf2d contactNormal; }; (These three variables is all we need to resolve the collision) Save the information in a vector std::vector collisions; /* Calculate and push if exist collission */ // Then sort them std::sort(collisions.begin(), collisions.end(), [](CollisionInfo &a, CollisionInfo &b) { return a.t_hit < b.t_hit; }); // And resolving them using the saved information for (const CollisionInfo &collision : collisions) { resolvePlayerCollision(player, collision); }
I´ve tried this for so long but i keep running into an issue where my player collides with a rectangle for 1 frame and then falls through it like its not even there, im entirely lost on this
Hello javidx9, I have a problem with this code. When the x or y component of the variable vRects[0].vel becomes 0, the object moves at an enormous speed due to division by zero in the RayVsRect function at the very beginning. How can I fix this? Thank you for your response!
hey I'm late but I think there's a problem with how you resolve the tile collision. Imagine 3 tiles that make an 'L' shape. On the first pass, the velocity ray intersects with 2 bottom tiles. Then after the first intersection check, the sorting and resolving the first collision (the right-most tile), the new velocity ray would come into contact with the remaining tile (the up-most tile). But in the second pass, the program only tries to resolve the original 2 intersections, so the newly created collision never gets resolved
I'm going to take a shot at this. Consider two rectangles: A & B with top left coordinates x1, y1, bottom right x2,y2 if Ax2 < Bx1 then no overlap if Ax1 > Bx2 then no overlap if Ay2 < By1 then no overlap if Ay1 > By2 then no overlap So could we say Collision is = not (Ax2 < Bx1 or Ax1 > Bx2 or Ay2 < By1 or Ay1 > By2) Might need to test for the distinction between and = for near misses PS i haven't yet watched the video. Perhaps a set approach, "what is the intersection of these two rectangles?" If it's null then no overlap. Imagine implementing a generic, N dimensional solver. My reach is greater than my grasp.
yeah I tried this approach even after watching this video and if you had watched you would've seen the failure javidx9 pointed out (I won't spoil it :p). This approach failed me because in my particular project (Bomberman knock-off) I need to "help the player along" making corners. Also, this only works for rectangles in 2 dimensions. If you go 3D or higher this will only do the "broad phase collision detection". Unless you are strictly playing with rectangular parallelepipeds (or paralleletopes), this approach for the near phase should feel very janky. Not even Minecraft does this.
This video works smoothly for me, but, we need to go one step further and implement Dynamic AABB with Dynamic AABB, is this solution suitable or we need another approach?
The rectangle turns yellow at 32:11 because you've got a bug in your implementation. You are testing (t_near.x > t_far.y || t_near.y > t_far.x) return false. But it just won't work if the rectangle is not square(squashed as in your video). You need to compare vectors not individual components.
There isn't a bug. The ray extends past the point of his cursor which hits the rectangle (t_hit_near > 1; where 1 is the direction vector). He resolves this issue by checking if the ray intersects the rectangle within a certain range. The range is the point of the mouse cursor or less which is why he checks if the t_hit_near is
Hey there. Really liked your videos. Can you do a tutorial that covers polygon and capsule collisions with a similar approach (rectangle-polygon, circle-polygon, rectangle-circle, etc.)?
I made a function that works this out nicely just the other day for a game i'm making. I could check transparency of the images (each pixel) and make that not trigger a collision but I feel that would take too many cpu cycles.
I built myself an Entity/Component system in Javascript (pretty much ripping off Unity), with a Transform (position, scale), AABBCollider (collision test) and Rigidbody (accel, velocity, collision resolve) components. Getting this to work in that setup is a proper headache! Its all about the order of operations I suppose, but damned be I if I cannot figure it out! Procedural big old blocks of code is sooo much easier sometimes hah.
188 Times or 3.4 rectangles per minute
Tzanislav Filipov I hope you get your bonus points :D
lol
Talk about dedication :-) - sounds like a fantastic drinking game however!
GetRect();
Drinking game : drink whenever Javid says rectangle.
I drowned. Thanks.
**looks at title** this will be good
**looks at duration** this will be GREAT
TIMESTAMPS:
03:14 PointVsRect
06:19 RectVsRect
08:25 Tile Based Collision review
12:10 Tile based limitations
14:45 Tunneling
16:05 Swept AABB Intro
16:40 RayVsRect
18:40 Find t in RayVsRect
20:00 Finding near&far x&y
21:28 Sorting multiple ray hits
27:20 RayVsRect Code
33:33 Swept AABB theory
35:33 DynamicRectVsRect moving
37:40 Multiple Rectangle tests
39:39 Testing Collision and Seperation
40:48 Collision Resolution
43:45 Playing around with more rects
44:35 Sliding bug
48:28 Broadphase naive sort
50:30 Mouse release snag bug
so this is what you do in your free time
This is a fantastic video! Thank you so much for it!
Something I'd like to add is that, if you want to convert the DynamicRectVsRect to a DynamicRectVsDynamicRect you can simply take the velocity of the second rectangle and subtract it from the first one, then use that difference as the direction vector of the ray in the collision detection. Properly solving dynamic collisions however would require some soft of recursive algorithm to get it to work between more than two rectangles at a time, to solve each collision in the order in which they occur.
Edit: Having now implemented the code demonstrated in this video, it works quite well, though I did stumble upon a couple of small issues that I managed to fix.
First of all, tNear can sometimes become way less than 0 when moving slowly in the opposite direction due to floating point errors, in which case the player (or any object using this same collision check, I'll just say 'player' from now on for simplicity) can be snapped backwards through a wall. The solution is to say it's not a collision if tNear is less than 0, or in reality less than a small negative value, otherwise we get more floating point errors that cause some collisions to get missed instead. Ugh, floating point numbers...
The second thing is the fact that the literal edge case of colliding into a corner is not handled in your code, meaning it's possible to clip through walls when you hit a corner. In your implementation, this is masked not only by the fact that it's a rare occurance but also by the fact that tNear is allowed to be negative, so if the player clips into a wall one frame then they're likely to be clipped back out the next. However, that's not the case if you don't count negative tNear values as collisions. In that case you need to handle corner collisions, -otherwise the player will be able to wall clip- (edit: I realized it wouldn't enable them to wall clip, just that the normals wouldn't be handled correctly). You could choose to make it collide in both axes if you collide with a corner depending on what you're doing, but in my case since I'm making a platformer that would just make the player get stuck on corners momentarily in case such a collision occurs, so I've chosen to handle it as vertical collision in my implementation which works better for that use case.
Sorry for the huge wall of text. And again, huge thank you for making this video! It's great to finally be able to escape Unity's own collision system for simple 2D games.
How would you fix the issue with corners? Right now I am able to phase through tiles in my game by falling through a corner, and I can't seem to fix it.
@@undersquire I realized that the fix I did for handling the edge case didn't actually have an effect on being able to wall clip, because that wasn't a problem with the original code to begin with. I realized the issue I fixed was just that the normals wouldn't be handled properly if you hit an edge, which wouldn't have made you wall clip anyway. Double check your code against the code in the video because it should work just fine without any wall clipping issues. If that doesn't help, use the Visual Studio debugger to step through your code with break points and watches to understand what your code is doing, particularly what it's doing when you fall through corners. Other than that I can't really help you without seeing your code.
@@OllAxe I have already spent several days trying to debug it with no luck. The code is the same as the one in the video, so I have no clue as to what is happening. Here is my code if you wanted to take a look: pastebin/XAxXQaWC (UA-cam won't let me send the link, so add in the rest ;/ )
It seems that corners are where I am able to phase through tiles, but I am unsure as its a rare occurrence.
EDIT: I am not using PixelGameEngine for my game, so there are subtle differences in the API.
@@undersquire Whew, it took a couple of hours not having access to any of the tools to be able to run and step through the code, but I think I managed to fix the bug for you the same way I fixed it for me. Here's the pastebin: Ad9urmwK
All the changes I made are commented as "//FIX:" or "//NOTE:" with more info about what I changed and why.
I hope that helps!
@@OllAxe Oh wow this worked! Thank you so much haha, spent way to long debugging this and your fix worked perfectly. Hopefully this can help save anyone else hours of debugging if they run into the issue.
Hi! I've found a logic bug in the "bonus side effect" you mention at 42:50
It's correct that you don't alter the velocity in the opposing axis of the one you collided with, BUT here you are altering the velocities direction!!! And if in that direction there are colliders you have excluded out (not resolving because they werent in your direction before) you are gonna clip with/ totally miss them in case of diagonal collisions with a close rectangle.
Thanks a lot for your tutorial, I managed to code my own javascript implementation of your code, and my (really) ugly fix was to run the whole collision check recursively when all these conditions are met:
-the object was initially moving in BOTH axes
-at least one collision resolve happened
This means it can run up to 3 times (per frame) when close to corners in a diagonal vel direction:
First time: resolves the direction to not meet one of the axes of hypotetical corner
Second time: meets the other axis of the corner, resolves
Third time: still in a diagonal velocity towards corner, but since both velocities have been cut by previous adjustments, no collision is found at broad phase.
There are many more efficient ways than mine to resolve this slide-clip behaviour, but I think I made a point:
if you change the direction, expect eventual colliders which were still part of the group of the first broad phase cut (when you add the initial velocities to your size and simple check with everything), but were cutted out from resolving because they werent in your direction during line vs rect.
Had to debug running the game loop at 2 fps to follow up what was going on with the diagonal collision at moderate/high speed and isolate the bug to get a grip of the occasional clipping.
So this is how the old Super Mario speed runs happen. When they get so good they frame-time, clip, and run through solid objects. So cool. Awesome tutorial, and it's practical for every engine.
I've done some corner clips for speed. .I"m not a great speedrunner at all, but sometimes I get a wild hair and decide to grind a level until I'm good at it.. Here's one of my recent ones.. I've taken another frame off since too ua-cam.com/video/F94cr34zu64/v-deo.html
I would normally find hi and hello boring and bland. But this man says it so simple yet so enjoyable
I've been working on a game, and I was looking for a good way to detect and found my way to the case where the object is moving too fast. The vector intersection projection is exactly what I need, and you are a saint for making it so digestible.
Thank you so much for making this video! I'm working on my first project of the year at uni and implemented your system. I was struggling with all the issues you listed in the beginning too, so it was great to see you also cover them.
Thanks and good luck with your uni project!
3 years and still very useful, thanks!
Honestly, thank you very much for all of the effort you put into your videos. I can't stress how valuable and amazing your content are. From the bottom of my heart, thank you! thank you! thank you!!!!!
Wow. Got some answers to questions I did not knew I had. Great video. Thank you!
Thank you so much for these videos - your simple to follow diagrams, explanations and code are indispensable - Cheers!
Hey cheers newcube!
Brings a whole new meaning to the phrase "GetRect()"
AAAAAAAAAHHHH! XDD
It always amaze me how much I can learn about a topic I thought had no more complexity. You are great!
I deleted my old comments because I finally figured out everything I was doing wrong. This video helped me figure out my AABB collisions, thank you so much!
Funny how I recently built this platformer engine and bumped into every one of the problems that were mentioned here (no surprise). Would have been a lot easier had this video existed before writing the engine. Great stuff!
Hey, you learnt this stuff the best way possible then - first hand! Nothing beats that experience.
I just discovered this channel while looking for a solution for a proper 2d collision detection. Although I have never coded in c++, this was easy to implement in javascript. Thank you!
YOU ARE THE KING OF UA-cam CODER!!!
finally a clear and working example.
I ported in javascript ... works perfectly. it seems an arcade
Thank you
This reminds me of Geometry lectures in University. Good ASMR before falling asleep, thank you.
I’m currently trying to work out collision detection and resolution, so this video has been super helpful. It gives me some ideas on how I can approach the problem that I hadn’t thought about. Thank you for explaining the problem so well!
This video deserved an upvote just for the idea of using "Vs" in function names doing comparisons. What a great idea!
Note: I've found that the double-raycasts are required as far as I can tell. The player's state doesn't change between collision checks in the initial loop, but it does when the resolutions are performed. I was getting that 'tripping' behaviour when I tried to reduce it to one check loop. Fantastic tutorial, really good explanation of the mathematics behind this sort of collision resolution, and it's portable (I followed along in C#)!
Networking? Hell yeah!
Glad you are posting this videos out here on youtube, just had a hard time porting this to 3D and joining the logic with your quad tree videos, but its finally working now!
Great video! Thanks for all the explanations and also for sharing source code. Usually with Tiled Map I used a different approach, but I want to try this approach for sure now! Hope to see you soon!
Well thats it Luca, theres a variety pf techniques and you should evaluate whats best for your needs. I feel the approach shown in the video is a "catch all" technique, but not necessarily the most optimal.
Me seeing this vídeo late in thr night: Oh, it's an hour long and I'm falling asleep, no way that I'll watch it today...
Me an hour in later: Oh... that's so good!
Even though I am not a C++ coder and have I yet to get aquainted with the PGE, quite often when I'm coding other stuff myself I have these videos of yours playing on the side and I very much enjoy the mathematical and logical tricks you point out, especially when you jot them out.
Also, your soothing way of speaking works like a charm. Very intriguing. 🤓
I only just started watching but I must say I'm looking forward to your video on networking.
I have built a network multiplayer engine myself but I feel that it's tangled and not as convenient to use as I'd like it to be. Part of the reason why is that I can't seem to find any definitive wisdom about it online.
As a result I just ended up implementing a module that manages some TCP sockets with a basic abstraction layer on top. The user still has to manually decide which variables define the game state and when to synchronize them.
I would love to build a system that completely encapsulates networking, allowing the user to make a game as if it was a singleplayer game. This has been exceedingly difficult due to all the little optimizations that are necessary to make the game feel nice to play, particularly in the case of a first-person shooter with mouse controls.
Anyway, I'm looking forward to this video as well. I've learned doing AABB collisions a long time ago but I'm very interested to hear someone else's perspective as finding good sources on this is still difficult.
Definitely that's is a obscure info, search for good topics or posts in forums is hard and the most cases is a variant of the same article =\ I working in a personal project for two year and I remember changed the entire struct for the networking 3 times. In my last attempt I get all my code write in c++ and make it on Go because is more elegant and easy to manage (sorry bad English)
At around 34:30, you really ought to mention that expanding the target rectangle using the dimensions of the source rectangle is taking the Minkowski Sum of the two rectangles. It's very useful and generalizes to other shapes and dimensions too.
As a side note, I've been playing around with physics engines for several years now, and it's nice and very validating to see that we've come to the same conclusions about a lot of things.
Aaron Wright though you are technically correct, He describes the required math elegantly and a fancy term for the convolution of polygons can confuse and scare newbies.
@@Diamonddrake true, but no reason not to throw it in there as kind of a "if you want to learn more, here's what it's called" sort of thing.
Amazing tutorial! Really helped me out in managing the player's collision and movement! Very easy to follow and explains everything thoroughly! 10/10
The fun thing is, the swept AABB collision can be extended quite easily (well, more maths, but same vector artihmetics) to any convex polygon vs convex polygon collisions, no matter the orientation. Then you can add spheres into the mix, or more complex convex geometry (capsules, ect).
If you want slopes, roughly shaped terrain, triangles, it's a great way to do it.
Technically, it's all based on the the SAT (separating axis theorem), the case between two AABBs is just a special case of the more general algorithm. Similarly, the 2D case is a special case of the 3D algorithm, so extended to 3D is also trivial, you just have many more 'axes of overlap' to check (face normals, and edge cross products).
And if you want to deal with intersections, you can also use the same SAT checks for free to work out the potential intersection vectors (the vector you need to use to push the objects away from each other a minimum amount to resolve an intersection), like you did at the start with the 'non-swept' intersection detection.
What I find hard, is the problem you highlighted, resolving for the best response when you encounter multiple simultaneous collisions and intersections. Algorithmically that's can get real ugly real fast, which means, nasty unpredictable bugs and weird behaviours.
25:04 This was the WOAH moment for me. This actually makes so much sense.
Glad you included ending thoughts about culling and optimization. I think I like your "I make a big bounding rectangle including both start and end position" approach!
I like your videos. Always interesting topics.
I implemented it in Java and learnt a lot.
However, I found a bug that drove me nuts. In principle, it worked, but sometimes my rectangle would jump around.
E.g. my rect touches the horizontal border of the other rect then in some cases, the program would reposition my rect to horizontally align with the left border and then the right border of the other rect in quick successions, even though they are totally irrelevant at this point.
Turns out, the algorithm got tripped up by a *𝙽𝚘𝚝-𝚊-𝙽𝚞𝚖𝚋𝚎𝚛* value, e.g. in case *( 𝚛𝚎𝚌𝚝.𝚢 + 𝚛𝚎𝚌𝚝.𝚑 - 𝚙𝚘𝚒𝚗𝚝.𝚢 ) == 𝟶* and *𝚟𝚢 == 𝟶* then *𝚝_𝚏𝚊𝚛_𝚢* would be zero divided by zero, and we get *𝙽𝚘𝚝-𝚊-𝙽𝚞𝚖𝚋𝚎𝚛* instead, because the computer cannot determine the sign. I needed to handle that manually:
𝚏𝚕𝚘𝚊𝚝 𝚝_𝚗𝚎𝚊𝚛_𝚡 = 𝚟𝚡 != 𝟶 ? ( 𝚡 - 𝚙𝚡 ) / 𝚟𝚡 : ( 𝚡 - 𝚙𝚡) >= 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈;
𝚏𝚕𝚘𝚊𝚝 𝚝_𝚏𝚊𝚛_𝚡 = 𝚟𝚡 != 𝟶 ? ( 𝚡 + 𝚠 - 𝚙𝚡 ) / 𝚟𝚡 : ( 𝚡 + 𝚠 - 𝚙𝚡) > 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈;
𝚏𝚕𝚘𝚊𝚝 𝚝_𝚗𝚎𝚊𝚛_𝚢 = 𝚟𝚢 != 𝟶 ? ( 𝚢 - 𝚙𝚢 ) / 𝚟𝚢 : ( 𝚢 - 𝚙𝚢) >= 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈;
𝚏𝚕𝚘𝚊𝚝 𝚝_𝚏𝚊𝚛_𝚢 = 𝚟𝚢 != 𝟶 ? ( 𝚢 + 𝚑 - 𝚙𝚢 ) / 𝚟𝚢 : ( 𝚢 + 𝚑 - 𝚙𝚢) > 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈;
I'd be interested in seeing a follow-up for non-tile based systems, because I suspect the solution would be helpful for object vs. object collisions as well as object vs. terrain collisions - though with object vs. object collisions there's the added complication that both objects could be moving, in addition to the fact that they generally cannot be guaranteed to be aligned to a grid, so I'd be interested in seeing how to treat that. I've got a few ideas I should probably try out, at least.
This is definitely a topic I think he should cover, some of the collision algorithms for arbitrary objects are quite elegant.
*tl;dr:*
- Pick the center of one of the objects.
- Rotate both objects around that point until the object you picked is axis-aligned.
- Add the velocity of the axis-aligned object to the other object so that the axis-aligned object isn't moving.
- Do collision detection like normal.
- Rotate collision results in reverse around the centre you chose at the start.
*If you care about me rambling on for 10 hours:*
The best way to get started with something like that is to do the collisions from the frame of reference of one of the objects. You axis align one of the objects, rotate the other object around its origin and add its velocity to the other object (all of this using temporary copies of the objects for the sake of collision). You can think of it like attaching a camera to one of the objects and doing the collision based on what that camera sees (the camera sees the object it is attached to as axis-aligned and not moving).
Now you have an axis-aligned and stationary object, and you just do collision detection on the other object like normal. Once you get any collision information such as position and normals, you need to rotate that information in reverse since you had to rotate one of the objects to make it axis aligned.
You still need to learn how to collide rotated objects with axis aligned objects, but now all your collision problems involve one stationary/axis-aligned object. Most 2D collision algorithms involving a stationary/axis-aligned object are quite simple. They usually just involve splitting the shape up into lines and testing each of the lines, and picking the line that requires the shortest distance to move to get out out of the axis-aligned object. You then repeat that until none of the lines touch the axis-aligned object. That is a very naive approach and it can be optimised a lot (for example, any line that has a normal that points away from the direction the object is moving can be ignored).
You can also do a sweep collision of each line. It's a tiny bit more expensive and complicated but will give you better results for fast moving objects. I've gone a bit off topic now though so I'll stop. Hopefully this can give you an idea of search terms to look for if you're interested to research it yourself.
FWIW I made circle ←→ tile collision in my little Bomberman prototype, and I in fact expect circle ←→ circle to be easier. Circle to tile detection is fine, but resolution took a lot of trial and error...
EDIT: Code here BTW: github.com/Cheaterman/Bomberman/
@@thekilla1234 Very good explanation. I managed to make it work with arbitrary angles now
Ah, finally I understand why certain bugs happened in my engine! Thanks olc for the amazing content
Let me guess, the bugs were typically an off by 1-pixel...
And I finally understand why I have NOT been visited by the bug fairy yet:
I tried building a billiards game without GPU and without polygons (mostly - table geometry is still polys, but balls and pockets are not). Ray/ball intersections are done alalytically (a bit messy with sqrt()), and ball/ball intersections are the same; I use a ray for the moving ball and a sphere twice the size for the stationary/slower ball. To get collisions right, I have to try them all and then compute physics for the one that occurs first. (Ball/pocket contacts are always calculated last, because if the contact is too fast to be detected, it would be too fast to fall either.)
Which means that I had the sorting already in it before testing.
This was a really dense one, but I really liked it. I'll have to watch it a coupe of times and play around with the code myself to wrap my head around it.
I'm curious, how is your process of debugging? I'd be glad to watch a video of you explaining it, or going through an example like the velocity bug you mentioned.
This video was very useful, I tested the system using Unity C #, I will use it for my HTML5 game with the optimization mentioned in the last minutes of the video.
Could have used this last year! I spend many nights on my cs undergrad group project trying and failing to writing a collision engine
Man, my brain melted but super interesting. I use simple position and size verification, its works but just in some occasions.
Of all the shapes, rectangles are my favorite.
I disagree. Circles are the best shapes. boobs and butts are not rectangles...
Triangles
@@thatsnuts8935 hhhh you could say eyes and moon instead
squares tho
@@wxwf934 I won't touch or feel against either somebody's eyes or the moon, so boobs and butts feel much more appropriate..
Красавчик, все працює, легендарний чувак!
THANK FOR POSTING THIS BEEN WAITING FOR SOMEONE TO EXPLAIN THIS, i tried making my own protocol collision and it is indeed not simple D:
49:06 I think a priority_queue would work well for this. Automatically gets sorted based on the comparator.
Doom has that glitch you mentioned about passing through walls. As long as you are moving fast enough for doom guy to clear the wall in a single frame, you will clip through the wall. Bouncing off the walls at a certain angle can cause acceleration to build without moving, and eventually you "void glide" through the wall. This would probably explain a lot of bugs in other games where you can fall through the world or jump through a sloped wall.
Really interesting for beginners as usual
Thank you Max!
@@javidx9 Are you planning on explaining how it works for 3d or not ?
This was great! Can't wait for the challenge of "arbitrary shape collision" video! :D :D :D
I think you may have introduced a potential bug at 38:40. You set velocity to direction and magnitude multiplied by elapsed time, then pass it into DynamicRayVsRect, where you multiply it by elapsed time again to create the ray. So effectively you've got velocity * time^2 as the length of your ray. But I don't know how much of an impact that may actually have on the calculations :)
Its not quite a bug. When i set the velocity originally its actually a change in velocity, which is an acceleration, so in this instance it is t^2
@@javidx9 Ah, I must've forgotten about that later in the video. Thanks! And thank you for making this, it's really helpful!
A nice method for continuous AABB collision I've thought of is just clamping the hitbox's collision to the max of the left hitboxes right sides and min of the right hitboxes left sides in it's broadphase rect, also top and bottom etc. So far I've had no issues with the algorithm and it works at crazy speeds, not to mention the simplicity of it (only 50-60 lines) and no complex maths at all with ray casting. I got it working with moving collisions, in fact keeping the player to moving platforms is easy with a bit of extra code. Hope this helps anyone!
Would you explain this to me a bit further? Because that sounds fairly simple and I am kinda interested :D
@@jamesheasman1594 Ok thank you very much, maybe I will try this one out :)
One simple method I used in one of my games was I checked if the right side of the first object was less than the left side of the second, than no collision. If the left side was greater than the right, no collision (checking the X axis obviously), then I check if the bottom is less than the top, and if the top is greater than the bottom. For each of these checks, I have it return false if any of them fails, this makes it much faster as most of the time, two objects are nowhere near each other and so this can make the collision routine return quickly. If all four of these checks fail, than we definitely have a collision between the two. In my game I check for a collision when the player moves. In the case of hitting a wall, I move the player, then check for a collision, if there is one, I simply move the player BACK to his previous location. So I would add the new XMove and YMove, check collision, if true (with wall), than subtract those same values. But in my game the player doesn't move terribly fast so this results in hitting a wall and no more movement in that direction.
Another thing I have done is if I want the player to be able to SLIDE along a wall, than the direction the wall is in I will subtract that movement; say, the wall is in the X direction, you subtract the X so it no longer moves in that direction and only add the Y movement component (unless there is also an object there, in say, a corner) and this way, the player can slide along the wall, which is desirable for certain games.
My favorite is still circular collision, but I seem to recall optimizations for AABB which makes it fast, but it's been a while. Probably the optimizations I just mentioned now that I think about it. LOL
Neil Roy Your initial four checks are exactly the same as the second method he writes at the start of the video, RectVsRect, except he does it in one line of code and relies upon the compiler using “short circuiting” when evaluating the boolean ‘and’ (&&) expressions. I’d be surprised if your version, with separate ifs and returns, was any quicker on a modern compiler.
I was wondering whether it would be useful to refine the collision detection functions to distinguish the case where two things are touching: my feeling is that this is analogous to the comparison functions you pass to a generic sorting routine which give you -1/0/+1 for .
So for PointVsRect you might get 1 if the Point is inside the Rect, 0 if it's on the boundary, and -1 if it's outside: possibly the other way around, I haven't thought it through completely yet 🤔
It took me a moment at 24:15 to twig why N_y and F_y are swapped 🤦♂️
Yes you can Phil, but you need to be carefully consistent with all subsequent operations too. Its imperative to actually resolve the collision, so if they are touching, they are still in contact. This may have a knock on effect later down the line.
I tried something similar a few years ago as a project to learn java in, trying to get collision working that would recognise what sides of two rectangles hit eachother, (to get like a mario stomping mechanic) and it was a much deeper problem than I expected.
I used the angles which the sprites were moving at I think.
This is a sensible optimistaion if you can avoid costly trig functions. You only need to test in the direction you are moving.
Very interseting video ! Another method to avoid too fast moves that can pass through tiles, instead of rays, get the move vector, if the components (x,y) of vectors are greater than a tile width, subdivide move vector. Move X time, render 1 one time at the end.
So instead of considerating fast moves with ray calculation, just avoid this case, and move several time (in memory) then render once at the end.
Subdivision is useful in some scenarios - the only downside is it isnt always deterministic, probably not critical but its there.
@@javidx9 Ok, thx for answer
@@javidx9 Another way to do this is to write a "distance line to rectangle" calculator. This ("in a single calculation") will give negative distance for intersection, zero distance for "just touch" and positive distance for "no intersection" answer without need for any subdivision. This is of course a much more complex calculation (square root but no trig) than determining point-to-rectangle intersection.
I really enjoy learning with your videos. Thanks a lot.
Rekt angle
no.
@@iteratedofficial yes.
@@iteratedofficial yes.
@@guy-dev 69 likes dont ruin it
@@iteratedofficial no.
I usually teleport the player one pixel above the y of the nearest underlying block, if the player is within its bounds, else I just let him fall according to player->y = player->y + pow(falltime,2) * g
@43:53, something about this line: "vRects[0].vel += cn * olc::vf2d(std::abs(vRects[0].vel.x), std::abs(vRects[0].vel.y)) * (1-ct)" causes my player rectangle to disappear upon contact, what's the problem here?
Edit: seems to be because of "ct" being incredibly big either in the positive or negative...
Thank you Javid, I can tell you I was planning to ask you for a quadtree collision detection tutorial, with recursive call, in c++. Please give it a shot, a c++ quadtree implementation in c++. Thank you.
"All of my rectangles are going to be axis aligned."
Insert WW2 joke.
Ive been searching for something similar to that *bool PointVsRect* function forever... Thanks!
Love your videos and approach dude
So many calculations per frame, so much floating-point math. I'd love find out about how people got this stuff working on much simpler computers/consoles. I imagine they had to take a lot of shortcuts.
Goodness, just what I needed! (Well, mostly, and I could have tried my best to deal with the original platformer thing 🙂)
Edit: 51:20 NOO!!!!!!!! A divide by 0 will throw an exception/crash the program!!!
You're right about division by 0, except that really only happens with integer division. You can try it yourself using floats or doubles, and you should see that it behaves exactly like Javid said.
The floating-point standard (IEEE 754) actually allows several different behaviors when dividing by 0, which each program can select for itself. One of those behaviors is to crash the program, but another is to make 0/0 produce NaN, +x/+0 and -x/-0 produce infinity (where x is a positive, nonzero number), and +x/-0 and -x/+0 produce negative infinity. (I may be wrong about how -0 works with this--it's not something I usually have to think about--but I think that's right.) I don't know whether the C++ standard guarantees a particular behavior, or even whether it guarantees that floating-point numbers follow IEEE 754, but in practice, every modern compiler for every language should default to this behavior. I'm unaware of any that doesn't.
It is definitely worth thinking about division by 0, though, since it's clearly an edge case whether it crashes the program or not. There's a good argument to be made that it should crash the program, since getting infinity or NaN is usually a bug. In this case, however, he made sure that the infinities would implicitly produce the correct behavior and correctly interpreted the NaN.
@@jeremydavis3631 That sounds great, but I'd still be cautious about this behavior (that means implementing 0 checks)
@@iProgramInCpp And rightly so. I was only pointing out that his code really does work correctly, even in those edge cases. I'd check for zero explicitly myself, since it's so easy for division by zero to be a bug. (I happen to know that Rust guarantees this behavior on division by zero, and I'd still probably include the checks if I wrote this in Rust.)
@@jeremydavis3631 Makes sense
ok so my first comment got ignored, okay you made a ray from the bottom left going top right. you colored it orange, at 24:20 you say and rather strangely the near y was where the far y should be. you didnt really explain this. why is it the near y when its clearly the far y. please i cannot continue until this is explained thank you.
I'm not a public service providing answers within 24 hours of being asked. Near time and far time are relative to the tiles axial coordinate system, which is traditionally a top left origin. Since algorithmically the sides of the rectangle are designated near or far originally based simply upon the definition of the rectangle it leads to the rather confusing switch which is puzzling you.
@@javidx9 Wow I didn't mean it like that I meant it probably got ignored cuz I didn't specify I wasn't like hurry up or anything. anyways thanks for answering. that helped.
Since you're using a raycast to test what's between the object currently and after moving, isn't it possible that you could still tunnel through a small gap in a wall? What ways would there be to go about this issue? I think it would make things a bit harder as it would maybe have to be a case separate from when you allow the object to end up inside the floor and then use the normal to shoot it upward.
Thank you for making this video, it was very educational! :)
I just wrote a system to do this not too long ago. I wonder how similar our solutions are.
same lmao, and i did it in a very similar way, just with a bit worse computational time
omg ur the frogger guy
@@123TeeMee I'm surprised someone recognized me :0
@@kneesnap1041 www.wikihow.com/Handle-Fame
@@123TeeMee I appreciate it, though I'm definitely not famous.
Rather than do all that math on the highly limited Arduino, I run Pong at thousands of iterations per second and render about 10-20 frames per second. The screen is 128 pixels wide. So 1280 iterations per second means the ball can move across the screen 10 times in 1 second and have pixel perfect collision detection. What I do is set a flag when there's a collision so the frame is rendered so the player sees it, otherwise it just renders a fixed number of frames per second leaving the rest of the time to handle very fine movements and collision checks.
By just running the game loop thousands or millions of times per second, you can high very precise collision detection without doing special math checking all sorts of stuff. You don't have to render a frame to the user every time the game loop is processed.
The game loop is essentially running in bullet time while the player only sees a limited number of visual renders.
Whilst this is all true and accurate, can you not do pong collision detection with just a handful of if() statements?
@@javidx9 Well, the paddle is moving and the ball is moving so you have to trace the path of both to see if they intersected between frames. You'd have to know the positions of everything in the prior frame and the positions in the current frame and then do the math.
There could very well be a simple bit of math. My project is showing how game mechanics work using simple games and it would probably be a good project to show different approaches so you can compare.
And then scale it up. One of the demos I want to make is having a bunch of balls bouncing around the screen.
The beard is a no-go at this station. On the other hand, you'd probably be able to rock a horseshoe mustache.
I tried that once, got tired of eating it, or waking up with half of it up my nose.
Hey! I love your videos, especially your "do it yourself" philosofy. I am trying to recreate the va_args behaviour for a freestanding project but I don't really understand the process behind. Can you make a video where you explain how all this stuffs works?
That sounds like a particularly tough one. You'd basically need to create your own argument stack and pop elements from it - IMHO it's one of those things where it's pretty much sufficient to know "how it works" without trying to reproduce it yourself. It is possible - just probably not as fulfilling as spending your time developing game collisions :-)
Hi Javid. I really enjoy all your videos. I grew up with ZX Spectrum and recently started making some bad games in Z80 assembly. It made me think of you because the whole ZX Speccy screen is like a console/terminal in many ways. And I wondered if you would be able to port your ConsoleGameEngine to a ZX Speccy one day and see if you was able to make some kind of 3d shooter with wireframe vectors of something like that... Just an idea for a future video maybe :D (I would bet you have once upon a time already programmed for Speccy, as you seem a similar age to me, but if you haven't maybe you should try it just for the challenge :D )
lol Dave, I cut my teeth on a BBC Micro, so a speccy is not too far away. On the discord server we have a guy who is "porting" the engines to atari 8-bit systems XD
@@javidx9 nice i will have to check that out. Been staying off discord for health reasons haha :D
Hey javid! You can lower the amount of calculations and code in PointVsRect, by getting the absolute value of the cordinates and then comparing it by the width or height of the rectangle.
IDK if you will ever read this, but please, make a C++ course or a series. It's a huge request. I am a beginner and I've totally fallen in love with C++. Also, I understand what you teach. Although a lot of it goes by from the top of my head, but still I try to make sense out of things. And this is the reason I want to understand everything from ground zero from your perspective. A huge request 🙏🙏
And if you can't make a course or series, can you please at least guide me from where to start and what to do. Please.
lol Thanks Uday - I do read every comment XD A tutorial series is a very popular request - Im unsure about it is my honest answer.
@@javidx9 I totally didn't expect you to reply... 😅😅
Well at least can you please point me in the right direction? Where should I start CPP? How did you get started? What you did? Which resources you used... etc. Please guide me. It's a huge request. Because your videos are awesome the way of explaination is superb but a lot of it just too complex for me.
So, please guide me 🙏🙏🙏
Another fantastic video! Thank you
as always...another great video
Just one question, how do I get the elapsed time in 38:42? I'm trying to do this is Win32 environment...
This quantum tunneling issue was the worst in my engine, i just used ray casting to determine the max position the object can travel to
Oh damn i guess great minds think alike
Subbed. Really cool explanations!!
add momentum formula for the slides p = mv so that it will also account to other velocity transfer to non static object that it collides with
That's right Paulo, its not too difficult to modify this into a dynamic rigid body simulation (providing the bodies are axis aligned rectangles)
You've mentioned doing Dynamic vs Dynamic rectangle collision resolution. Is that available anywhere on your channel? Alternatively could someone recommend some good resources or point me in the right direction on this?
How to resolve collisions with verlet integration? I need to change last_position instead of velocity.
Huge thanks, sensei, it helps a lot
Nice video Javid
So I have a concern, I have a spawn system that adds monsters to my game when other monsters are taken out. When a new monster is added however & they are within the rectangle of another monster collision happens. I've tried even messing with the spawner logic to check if the new monsters location will land on top of an existing one. Tried slowing down the spawn time, tried checking collision by setting it to false for x amount of time then enabling it but still no go.. There is more, I even tried the typical overlap boolean which sort of works but doesn't at the same time. Spent 4 days approx 16 hours going back to this
Damn, this is so much useful!
Thank, OCL for that kind of knowledge you spreadng and explaining in a understandable way.
i thought to myself that i would've understand that whole collision routine in a reasonable amount of time if i would read some kind of paper. But you made this whole process not in the matter of weeks for me but a single hour! That is so much appretiated by me that you've earned yourself a patron here.
Also i have several questions for you:
first of all, i want to start my own series of tutorials but in my native language, russian it is. Can i use your material for that kind of stuff? (with references, of cource)
Second, you called DynRectVsRect function twice for any dynamic object in your scene. Wouldn't it be faster to store all of the collide information in such a struct if function returned true (that would be 2 items in array in this example) then sort those structures by time and use it's information to resolve collision, saving time by not computing it again?
Thanks Vilkillian, With correct attribution you can use most of my stuff, but people who have just cloned my stuff tend to get taken down by YT or the community. As for your second point - yes its far more optimal to not call the routine twice, and I hinted at that, but the correct solution would become somewhat specific to how you have established the description of your environment - thus pointless to show here. I took generality and simplicity over optimisation in this instance.
For the second question, I create this struct:
struct CollisionInfo {
int index;
float t_hit;
olc::vf2d contactNormal;
};
(These three variables is all we need to resolve the collision)
Save the information in a vector
std::vector collisions;
/* Calculate and push if exist collission */
// Then sort them
std::sort(collisions.begin(), collisions.end(), [](CollisionInfo &a, CollisionInfo &b) {
return a.t_hit < b.t_hit;
});
// And resolving them using the saved information
for (const CollisionInfo &collision : collisions) {
resolvePlayerCollision(player, collision);
}
thank you very much for this video
I´ve tried this for so long but i keep running into an issue where my player collides with a rectangle for 1 frame and then falls through it like its not even there, im entirely lost on this
Love these videos!
Hello javidx9, I have a problem with this code. When the x or y component of the variable vRects[0].vel becomes 0, the object moves at an enormous speed due to division by zero in the RayVsRect function at the very beginning. How can I fix this? Thank you for your response!
hey I'm late but I think there's a problem with how you resolve the tile collision. Imagine 3 tiles that make an 'L' shape. On the first pass, the velocity ray intersects with 2 bottom tiles. Then after the first intersection check, the sorting and resolving the first collision (the right-most tile), the new velocity ray would come into contact with the remaining tile (the up-most tile). But in the second pass, the program only tries to resolve the original 2 intersections, so the newly created collision never gets resolved
and how did you fix this? Having the same problem right now
I'm going to take a shot at this.
Consider two rectangles: A & B with top left coordinates x1, y1, bottom right x2,y2
if Ax2 < Bx1 then no overlap
if Ax1 > Bx2 then no overlap
if Ay2 < By1 then no overlap
if Ay1 > By2 then no overlap
So could we say Collision is = not (Ax2 < Bx1 or Ax1 > Bx2 or Ay2 < By1 or Ay1 > By2)
Might need to test for the distinction between and = for near misses
PS i haven't yet watched the video. Perhaps a set approach, "what is the intersection of these two rectangles?" If it's null then no overlap. Imagine implementing a generic, N dimensional solver. My reach is greater than my grasp.
yeah I tried this approach even after watching this video and if you had watched you would've seen the failure javidx9 pointed out (I won't spoil it :p). This approach failed me because in my particular project (Bomberman knock-off) I need to "help the player along" making corners. Also, this only works for rectangles in 2 dimensions. If you go 3D or higher this will only do the "broad phase collision detection". Unless you are strictly playing with rectangular parallelepipeds (or paralleletopes), this approach for the near phase should feel very janky. Not even Minecraft does this.
This video works smoothly for me, but, we need to go one step further and implement Dynamic AABB with Dynamic AABB, is this solution suitable or we need another approach?
The rectangle turns yellow at 32:11 because you've got a bug in your implementation. You are testing (t_near.x > t_far.y || t_near.y > t_far.x) return false.
But it just won't work if the rectangle is not square(squashed as in your video). You need to compare vectors not individual components.
There isn't a bug. The ray extends past the point of his cursor which hits the rectangle (t_hit_near > 1; where 1 is the direction vector). He resolves this issue by checking if the ray intersects the rectangle within a certain range. The range is the point of the mouse cursor or less which is why he checks if the t_hit_near is
Very nice video, I was wondering how does this technique work with 2 moving bodies colliding? What modification would I have to make?
Hey there. Really liked your videos. Can you do a tutorial that covers polygon and capsule collisions with a similar approach (rectangle-polygon, circle-polygon, rectangle-circle, etc.)?
I made a function that works this out nicely just the other day for a game i'm making. I could check transparency of the images (each pixel) and make that not trigger a collision but I feel that would take too many cpu cycles.
I built myself an Entity/Component system in Javascript (pretty much ripping off Unity), with a Transform (position, scale), AABBCollider (collision test) and Rigidbody (accel, velocity, collision resolve) components. Getting this to work in that setup is a proper headache! Its all about the order of operations I suppose, but damned be I if I cannot figure it out! Procedural big old blocks of code is sooo much easier sometimes hah.
Great video