Arbitrary Rectangle Collision Detection & Resolution - Complete!
HTML-код
- Опубликовано: 11 июл 2020
- In this video I once and for all solve axis aligned rectangle collision detection, demonstrating algorithms to handle arbitrary size rectangle vs rectangle collisions and collision resolution, applicable to "rectangle soups" or tile map based interactions.
Source: github.com/OneLoneCoder/Javid...
Patreon: / javidx9
RUclips: / javidx9
/ javidx9extra
Discord: / discord
Twitter: / javidx9
Twitch: / javidx9
GitHub: www.github.com/onelonecoder
Homepage: www.onelonecoder.com 
Наука
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();
**looks at title** this will be good
**looks at duration** this will be GREAT
Drinking game : drink whenever Javid says rectangle.
I drowned. Thanks.
Brings a whole new meaning to the phrase "GetRect()"
AAAAAAAAAHHHH! XDD
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 ruclips.net/video/F94cr34zu64/видео.html
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!
I would normally find hi and hello boring and bland. But this man says it so simple yet so enjoyable
It always amaze me how much I can learn about a topic I thought had no more complexity. You are 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
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!
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!
what a coincidence. I was just literally programming collision methods for my project and you uploaded this video.
I guess, as long as games exists, somebody on earth is programming collision algorithms. And right now I'm writing collision system too! Good luck on your implementation!
@@kaileeann what method are you using? I'm calculating the square root of the enemy's position minus the player's position to get the distance between entitites. But I think this rectangle method is more practical.
Distance calculations using roots are useful for circular collision systems
@@javidx9 and you don't need the root if you're only comparing distances.
3 years and still very useful, thanks!
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!
Amazing tutorial! Really helped me out in managing the player's collision and movement! Very easy to follow and explains everything thoroughly! 10/10
This reminds me of Geometry lectures in University. Good ASMR before falling asleep, thank you.
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.
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!
This video deserved an upvote just for the idea of using "Vs" in function names doing comparisons. What a great idea!
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'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.
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!
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!
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. 🤓
Thank you so much for these videos - your simple to follow diagrams, explanations and code are indispensable - Cheers!
Hey cheers newcube!
YOU ARE THE KING OF RUclips CODER!!!
finally a clear and working example.
I ported in javascript ... works perfectly. it seems an arcade
Thank you
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.
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:
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 (RUclips 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.
I really enjoy learning with your videos. Thanks a lot.
This was great! Can't wait for the challenge of "arbitrary shape collision" video! :D :D :D
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:
𝚏𝚕𝚘𝚊𝚝 𝚝_𝚗𝚎𝚊𝚛_𝚡 = 𝚟𝚡 != 𝟶 ? ( 𝚡 - 𝚙𝚡 ) / 𝚟𝚡 : ( 𝚡 - 𝚙𝚡) >= 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈;
𝚏𝚕𝚘𝚊𝚝 𝚝_𝚏𝚊𝚛_𝚡 = 𝚟𝚡 != 𝟶 ? ( 𝚡 + 𝚠 - 𝚙𝚡 ) / 𝚟𝚡 : ( 𝚡 + 𝚠 - 𝚙𝚡) > 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈;
𝚏𝚕𝚘𝚊𝚝 𝚝_𝚗𝚎𝚊𝚛_𝚢 = 𝚟𝚢 != 𝟶 ? ( 𝚢 - 𝚙𝚢 ) / 𝚟𝚢 : ( 𝚢 - 𝚙𝚢) >= 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈;
𝚏𝚕𝚘𝚊𝚝 𝚝_𝚏𝚊𝚛_𝚢 = 𝚟𝚢 != 𝟶 ? ( 𝚢 + 𝚑 - 𝚙𝚢 ) / 𝚟𝚢 : ( 𝚢 + 𝚑 - 𝚙𝚢) > 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈;
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.
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.
Another fantastic video! Thank you
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.
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.
Love your videos and approach dude
Thank you for making this video, it was very educational! :)
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)
Ive been searching for something similar to that *bool PointVsRect* function forever... Thanks!
Could have used this last year! I spend many nights on my cs undergrad group project trying and failing to writing a collision engine
Subbed. Really cool explanations!!
Man, my brain melted but super interesting. I use simple position and size verification, its works but just in some occasions.
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.
Huge thanks, sensei, it helps a lot
as always...another great video
Красавчик, все працює, легендарний чувак!
Nice video Javid
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.
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 ?
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
Love these videos!
Thanks for this yet again. Now to do this in rust. :)
hi, recently found this video, very informative and useful, really hope you'll make a video on collision optimization, using binary space partitioning or quadtrees, i'd always wondered how that works
This vector stuff is nice, I used to just raycast using bresenham on each pixel and checking if it lies within the rectangle to be tested, but then again I hate using floats. But hey, it works with any shape if it's rendered to a buffer
thank you very much for this video
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.
49:06 I think a priority_queue would work well for this. Automatically gets sorted based on the comparator.
Very nice video, I was wondering how does this technique work with 2 moving bodies colliding? What modification would I have to make?
Rekt angle
no.
@@iteratedofficial yes.
@@iteratedofficial yes.
@@heylittleguy26 69 likes dont ruin it
@@iteratedofficial no.
Great video
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.
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 :-)
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.
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.)?
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.
thank you so much
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
This guy rocks
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.
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
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
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.
Thankyou!!
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.
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?
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 :)
Amazing!
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);
}
"All of my rectangles are going to be axis aligned."
Insert WW2 joke.
Beautiful
Hi, where do you get your sprite assets from? Do you draw them?
I have a question regarding checking the center of a movable rectangle with the target rectangle which is extended on all sides by half of the movable rectangle size. What I have done is I am taking top left corner of a movable rectangle and checking it against the rectangle that is extended up and left by the movable object size. It saves me a few divisions. As far as I can see my approach should be equivalent to yours.
So is there any particular reason for checks being done your way?
David, that's a great tutorial, thank you for that! I'm wondering if your approach would work for slopes. What do you think?
It could! but not without some effort first. If all your rectangles are sloped then the problem becomes trivial because these techniques shown require axis aligned boxes. When you start mixing axis aligned with non axis aligned you need more geometry.
@@javidx9 What do you mean by 'more geometry'? Ideally I'd like to mix slopes with normal tiles to make the levels more interesting to players.
A bunch more geometry calculations. Check out my polygon collisions video, it covers this.
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.
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
If the origin point of ray eventually starts inside the target rectangle, what is the best way to solve this situation? I tried this approach with a moving platform and had this problem when it change vertical direction. Any way, great work, keep posting this useful ideas.
Hi Javid! I'm developing a Game Engine in JavaScript, and I wanted to add collision just like what you did in the video. I implemented all things by myself, and everything was fine, but when I came to this problem 44:37 , I rembered you made this video, and went to take a look at the sorting algorithm you made for picking the nearest boxes to check collision with, but I didn't (and still don't) understand how it works. I know this video was published a year ago, and you probably don't remember anything about this code, or you are busy doing other things in your life, but please, when you can, please explain quickly how it works, because I've been investigating and I didn't find anything. (I'm Spanish, and I probably did some mistakes writting)
My IDE fall in love with you.
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?
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!
Well this is a new method of collision detection. Even though 3d graphics book have some hint of this.
Great video. I would be very interested in networking tutorials on your channel.
Thanks Jahoopy!
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
Out of curiosity, is there a reason you defined the rectangles as position and size instead of top left and bottom right coordinates? I know the performance is better for moving them with position and size since it is 2 adds instead of 4, but most rectangles are static where the performance for stuff like intersections and early culling is better using coordinates. Ultimately the performance difference is likely to be negligible in most cases (and looking at the code I think both methods end up equal in the swept intersection calculations) but I've always preferred using coordinates so I'm curious if there is anything else I should consider in favour of implementing them as position and size.
Personally I think that if they're stationary then like you're suggesting using a vec 4 would likely be better for performance, as you just calculate the four points only once. On the other hand I think if you want to use the size only as a constant in many calculations it makes sense to have the size seperately and that it also would improve readability as opposed to using right, top etc. Depending on your use case, I would consider having both in my rect struct/class.