Circle Vs Rectangle Collisions (and TransformedView PGEX)
Vložit
- čas přidán 28. 01. 2021
- Hello! In this video I look at a really simple and accurate way to statically resolve circle vs rectangle collisions. I also introduce the TransformedView olc::PixelGameEngine Extension.
Live Demo: community.onelonecoder.com/me...
Source: github.com/OneLoneCoder/Javid...
Patreon: / javidx9
CZcams: / javidx9
/ javidx9extra
Discord: / discord
Twitter: / javidx9
Twitch: / javidx9
GitHub: www.github.com/onelonecoder
Homepage: www.onelonecoder.com - Věda a technologie
0:45 you saying "stop giggling" actually made me laugh for a few minutes and i had to rewind the video to actually hear what you're talking about
@@Leon-bp6kb We all giggled .. one way or the other ;)
Lol, I was just thinking "Will he make a cringy reference with the camera zooming in, music pausing, etc.? Nah, he's a professional gu- oh XD LOLŽ!"
Hello! 2021 Let's Go! - Audio Squeeks and pops we're not on my master upload.... (shakes fist at CZcams), and do try the real-time, no effort demo! community.onelonecoder.com/members/javidx9/CircleVsRectangle/
Lets goooo! :)
The respect channel in world c++!
Hello!
Eyyyyy been waiting for a new one! Can't wait to watch through thanks buddy
CZcams is infusing videos with subliminal messages. It's true! They are trying to reset the internet, the great reset. :D * pun *
Just when I was working with collisions on my game, wow.
He knows man, he knows. This ALWAYS happens to me
Same
20:24 there's a nasty audio artifact
Scared the shit out of me when I was watching it in bed haha. Still a great video though
Another one at around 17:07
Holy shit! Made me jump xD
Your NES series inspired me to try to write a gameboy emulator having no experience
lol Alex, I dont know if I should apologise or not, but I wish you the best of luck! XD
@@javidx9 It's fun so far, thank you!
I find the NES series a really nice description of the NES's inner workings, collected all in one place, even if not writing an emulator
One lone coder videos motivated to me to start studying coding on my free time and after start high studies of computing. Today was a bad day at studies. Lot of work, to my expectations low qualifications for great effords, incomprehensible teachers... But, see David coding has make me smile and it has remember me why I'm doing this. Thanks OneLoneCoder for all your work
This is what makes this channel so unique and fun. Smart programming with cool little tricks and clever ideas.
I really appreciate these videos , thank you
Welcome back, looking forward to hearing more about these PGE updates!
Hello, Sorry for the following silly question. Maybe i am wrong here: In the picture at 11:21 N represent the nearest point on the rectangle. So the lengh of N is the lengh between the world origin and this point N. I that case |N|
yes you are right. thanks
I stopped suffering when interacting with C ++ and loved it thanks to your channel. I wish you prosperity
This is so simple and amazingly powerful! I needed to resolve collisions between spheres and bounding boxes... And I remembered the lone coder had some great trick with the clamp function. I come to search this video and I wasn't disappointed!
It works just fine in 3d (just add the z axis).
I extended it to work with oriented bounding boxes just translating the sphere to be relative to the bounding box origin, and applying the inverted rotation matrix to it.
It worked immediately!
Thank you!
Looking closely at 0:00 you can see that the video actually starts
unlike my programs
the corner resolution is so satisfying to watch!
Just implemented by myself in Java, and it works like a charm. Thanks for explanation and for the great job !!
Man, your channel is ridiculously good, just want to say thanks. Will support when the situation allows for it! (Y)
Great stuff - this is the real start of 2021 :)
Awesome, great video Javidx9!! The Pixel Game Engine is getting better and better.
i hope you had a good break! i really love these videos
I did, thanks Squili!
Awesome how great the Pixel Game Engine has become! Great video Javid.
2021 has already been better for me than 2020. I started a new job on January 11 after being unemployed since the beginning of August. I'm a contractor working for GDIT, helping them with a software project they're developing for the US military to help make it easier to avoid friendly fire incidents.
Yay! I've been looking forward to this. :)
Hi Javid, I've been using this algorithm for collisions in my projects for about a year now, and it's worked wonders! I really appreciate you making these videos!
That said, I encountered some strange behavior a while ago, and after hours of debugging my own code I finally realized the issue actually in this algorithm.
There is an unwanted side effect of sliding along tiles, wherein the circle will round off its position on one axis as if colliding with a corner when moving into an edge where two rectangles meet.
This bug can be reproduced in the web demo:
- Position the circle just below/to the right of the line dividing any two joined rectangles.
- Hold in the axis that moves toward the rectangles and simultaneously tap and release the key that moves negatively in the other axis (left or up).
As long as you keep moving in the direction of the rectangles, you should see the circle slide along the other axis when you tap, but then resolve backward as soon as you release until it stops at the point that the other axis would start rounding a corner.
I'd love some help with this as I'm struggling to find an elegant solution to this issue. Perhaps there isn't one. Thanks again!
I think I've got a solution. When we loop through all the tiles, we use a clamp style operation to get our nearest point. In cases where two tiles are adjacent, this can result in our nearest point being off-center to the circle (due to being on the corner of the square being checked) which starts to push us around this "corner" even if there isn't one. Repeating this as we iterate, pushes us further and further to the side as we continue the loop until the centers match.
To avoid this, you can make your clamp find the nearest point in a rectangle taking the next tile into consideration as well. Simply check the next tile along each axis, and if its solid change the +1 in the clamp to a +2 to take it into account. That'll make the nearest point centered, but only when there isn't a corner, so we can still slide around things!
Make sure to check the bounds of the map so you never check a tile thats outside of the map, and only extend the rectangle in y if it isn't already extended in x (to avoid extending it into a square that covers the player if checking against a tile in the top left)!
@@Nillvy Fantastic solution, I look forward to implementing it myself!
Another amazing video. Thanks !
Thanks Unal!
The absolute mad lad made it run in webGL
It was a community effort, pretty neat huh?
A good video to start 2021 and happy New Year
Thanks Chris, Happy New Year buddy!
This video saved me hours of work. Thank you!
Glad it helped!
PGE IN THR BROWSER? Javid, you're a legend
Nice to see You. All the best
Very helpful video, as always. Thank you javidx9!
this is a really nice collision check. even though my player is literally a square it's still better than what i had before because of the way it pushes you around objects
You are a legend! Thank you for your videos
Really nice work! Thinking about using this for my project on MonoGame!
Hi David +1 as usual .. it's took me a lot of time to recognize the central point of mathematic ;-)
Hi Javid, Ian here. Nice to have you back. Also, I see that Pi 400 in the background. :D
I hope you are well rested after the break, seemed like you were fairly bust throughout the second half of last year.
Thanks, this was very helpful.
Great video! Thank you!
cannot wait for the next video
Awesome. Missed you mate.
Yeah! Finally :D
dope vid
This is also known as a Signed Distance Field. So you can easily collide a circle and any of the shapes there are analytical SDF function for, such as the ones provided on Inigo Quilez's pages. :)
20:25 That pop scared the shit out of me
welcome back!
You're my role model!
nice one
I have watched the little talk from 4:46 several times.
the "come to think of it, that is how everyone defines a circle" makes me laugh every time.
nice!
30:32 Isn't there still a bug where if a potential position lies on the nearest point your position goes to NaN? I don't think checking fOverlap for NaN does actually anything.
Reasoning:
The mag() -function is internally: sqrt(x * x + y * y). No division. On the other hand norm() returns vector / mag(vector) which can be NaN.
Line 107: If vRayToNearest magnitude is 0, then fOverlap = r - 0 > 0.
Line 111: The check passes.
Line 113 vRayToNearest.norm() divides by zero and returns NaN. vPotentialPosition.xy = NaN.
This NaN quickly cascades to all values, including fOverlap, but by this time it's too late to fix; your position is already NaN.
I'm not sure what could be a potential fix. Immediately one thinks of checking if (fOverlap > 0 && vRayToNearest.mag() != 0), but that feels wrong intuitively (since that's a collision but it's not registered). Maybe if mag() == 0, you should push vPotentialPosition just a little bit forward or backward on the ray to ensure a non-zero number.
I hope your friends gifted you algorithms on Christmas :D
What do you do if the speed is high enough to put the center of the circle inside the rectangle?
Simple but effective
Is the video about "Changing the state of the procedurally generated universe" still planned? It's honestly the most interesting thing to me. I'd be sooo happy, if you'd revisit the topic :D
hey awesome video!!! learned a lot! i found a problem when implementing it myself, if the velocity is too much, the potential position will land straight inside the square and the clamp will make "nearest" to point towards inside it instead of the wall. i had to scale the potential vector to be the player radius - [really small value], but that will have weird effects on diferent machines. i cconsidered dividing the movement vector by (int)(vec_len / radius) and adding up/checking collisions at each pass but it seems like a waste, any ideas?
(i probably implemented mine wrong to start with, thanks)
Hi, this algorithm is awesome, but I wonder is there a way to adapt it to stop the ball as soon as it hits the wall?
hi javidx9, nice video as always, i was wondering wich would be the best way to update the velocity after colliding with a wall, it can't be set to zero cause the character could be sliding along the wall, the length of the velocity is often used to handle animations
Well it depends, you can bounce by reflecting the velocity of the wall using it's normal. Sliding is accomplished by nullifying the overlap by repositioning along the velocity vector to a location out of collision.
@@javidx9 i kinda get what you mean, but sorry it takes a while to fully grasp what you are trying to say since english is not my native language, i'm working with 3d models, i use the length of the velocity to drive the play rate of the walk animation, but in this case the velocity remains unchanged after applying collision, which means the animation keeps playing at the same speed even after bumping into walls, i thought updating the velocity would be easy with all information stored in the collision logic, but it seems i'm missing something
Nice 🙂
All your BASS are belong to us!
4:10
Fun fact: Super Mario 64 actually did something similar, except with polygons instead. It worked well because it was a geometrically simple game.
Vimto product placement!
"This will be a nice and quick video because this technique is simple"
*32 minutes later* I have no idea how this works
He explained it line by line, what's not to understand?
You Said The Chanel is Back
I desperately need rectangle vs rectangle collision response for years now, when they hit in different angle and then rotate..Like when a rectangle falls on the ground in non-zero angle, you know , Box2D stuff ;)
Dot product between normalized force vector and center of gravity; multiply with force magnitude should give you the torque.
So nobody else noticed the maths at 11:23 is not correct? Javid forgot to substract the balls position from N to get another vector, lets call it D, and this vectors magnitude should be compared to the radius of the ball! In the final code it is done correctly however :).
I noticed, but I figured by that point its obvious that N is the nearest point, since I mention its relationship to D and P many many times.
@@javidx9 I understand but it can still be very misleading! The magnitude of N shouldn't be compared with R.
Compiles into WebGL now? Wow. That just turned it up to 11 :-)
Who knew TV stood for transform view, makes so much sense now, apart from my TV licence... ? (Great video many thanks :)
Hi Javid, I dont know if you would reply but I have a quick question and wanted to know your opinion because its often straight to the point. In one video you mentioned that you work somewhere at the development of robots, is c++ a valuable language in robotics because at my university they only teach us matlab mainly for those things but I know that that is not used by a lot of companies, and im interested in programming and want to learn c++ anyway but that way I kind of have more motivation to learn in a faster pace. Btw, your videos have been great to learn programming by thinking outside of the box and simple and elegant solutions so please continue what you do, its really entertaining and helpfull.
Yes, c\c++ is essential for embedded systems in general, including robotics. If you buy a robot off the shelf, often it comes with interfaces to things like ROS and Python, but if you are developing robots yourself then you need to work with microcontrollers, and that's all about C, assembly and digital signal processing.
@@javidx9 very clear, thanks for the time to answer my question!
now apply to raycasting and you have signed distance field raymarching / sphere marching
Balls colliding with balls, stop *giggling* ..
- One lone coder 2021
Yeah kinda misheard it LoL
Welcome back!
Is it just me or does your voice sound a bit muffled (for the lack of a better term) during the segments when you are on camera? As if there was a high frequency attenuation effect applied to the audio.
Thanks! Yeah the audio is a bit messy - Im using some new gear and tools, and YT didnt help with the processing. Not much I can do about it now, but yes frustrating
@@javidx9 I know how it can be. I've had my fair share of audio issues as well.
You might want to try out Audacity to process audio. It's free and open source, and it has a good feature set.
There is a bug in this. A rectangle consumes X + W - 1 and Y + H - 1 pixels. So X + W is atually 1 pixel beyond the right side and Y + H is one row past the bottom. For examplem, a 1 pixel wide by 1 pixel high rectangle only has 1 pixel, not 4 pixels.
I see...greate material to build platform for mobile robot simulator.. ;-)
What IDE are using for coding and compiler? I searched in your video library for a video on how to get started in coding, but couldn't find one.
Can you do a video on your set up?
Hi Jim, I use Visual Studio Community Edition. I don't have any "complete beginners" videos, but I do try and pitch to a wide audience. The FAQ on OneLoneCoder.com lists all the gear and software I use.
There is some problem with the source code link. Always very interesting video.
Good catch and thanks Leonardo - github.com/OneLoneCoder/olcPixelGameEngine/blob/master/Videos/OneLoneCoder_PGE_CircleVsRect.cpp
30:27 I ran into a bug implementing this today. When you call norm() it calls mag() so it can also give you undefined values. I was spawning my circles inside the rectangle they collide with and the collision pushes them out - only you get a location that's undefined so they don't exist anywhere sensible. oddly this didnt cause any crashes anywhere else (drawing them each frame, updating their AI to move them, ect) and they just 'didnt exist'.
Ive just run into this problem. Looks like mag() returns NaN, and if px or py of the ball is NaN, then the program just does not draw them. If you did solve this, please HELP.
I just figured it our. The problem is that this collision calculation works only if the centre of the circle is outside of the rectangle. Of it is inside, then the closest point of the rectangle to circle centre is the centre itself, and so Nx = 0 and Nx = 0. So the ray magnitude is equal to zero, and we get 0/0 problem, which is NaN.
Once you start talking about Vectors and Radiuses, my brain goes to single core mode.
I have a question. It is not concerning now the content of this video, but can you explain the concept of async a bit more? I am a bit familiar with c++, and since a couple of months I am diving a bit deeper into it. But the topic of threading I did not touch in C++ yet. But as I am a vb.net developer, there is this concept of async functions which are not really threads. Those can be executed in parallel, and if you await them, the GUI for example will stay responsive, so the program feels more snappy. But I don't know how this works... How can it be executed in parallel when it is not a thread? In my understanding to have code running asynchronous there needs to be another thread beside the main thread... So I am a bit confused what's going on there.
I'm a little confused about 11:00, wouldnt shifting the rectangle and point to the right increase the magnitude of N without changing the collision?
Okay I see, in the actual code vRayToNearest solves this problem
But the question is when quaternions?
Weren't they the evil in Nigel Kneale Quatermass ?
There used to be a website (5-10yrs ago), green and white, slightly outdated layout, with all possible collissions for shapes and objects.
It was something like collisiondetectionalgorithms.com, but I haven't found it for a long time..
hmm, personally I think linked triangles at the bottom level (the generated triangles for each shape) would provide a catch all solution which is ultimately more useful when passed off to a GPU
can be imported to wasm?
Got missing you, absent for some weeks.
Hi Daniel, just my usual annual break - gives me time to recharge XD
Can you do a video on triangle collisions? Preferably with collisions to circle and rectangles :D
Nice!
But if the rectangle isn't axis-aligned, it gets more complicated. Or am I missing something?
If the rectangle is rotated by X, rotate the circle's centre and velocity by -X about the reference point of the rectangle. Then proceed as before, then rotate the final position back by X about the same reference point.
@@notanotherraptor Oh yeah, right. I think that works.
This is so simple..
I feel ashamed of much of code I have written in the past
Shouldn't the resolved position of the collision lie along the initial velocity vector? I may have missed something, but the collision is resolved here by finding the position of collision and displacing the next position along the normal such that there is no overlap. However the origin of the circle in this new position does not seem to lie along the trajectory the ball would have traveled otherwise, which does not make much sense to me. Maybe I am misunderstanding something or at small enough time deltas it doesn't matter but nevertheless excellent video as always!
In theory you are right, but in practice the effect is undesirable. You just stop when you hit a wall. Many players want to be able to slide along an hug walls.
hi, how do i calculate the velocity after a collision?
Momentum is conserved, so simple MV before = MV after, given the masses and velocities in the collision
And with a few lines of code, suddenly every homebrew Pac-Man clone becomes more playable and less annoying.
lol, one can only hope XD
I think a game like Pacman doesn't need rectangle vs circle collision. Instead a rectangle vs rectangle will work fine if we ensure that the Pacman always moves a unit distance.
17:08 What's that sound?
Can you do it without the square root?
I think you could yes, since its axis aligned.
I'll just go with using Voronoi regions
would you ever attempt to make a chess engine?
do another video on Embedding Lua in C++
Hi, OLC! how about Networking part 3 source codes?)
distance field to check where is the closest object
quick sweep
you could also provide dll interface
kinda app
try giving each triangle a sphere/circle collision volume based on the vertex point, then use that when calculating distance fields for ray tracing, or fast collisions/overlaps
What the hell, I subbed a long time ago, enabled the bell and everything yet CZcams still didn't show me this video. Is the whole CZcams broken because everyone is spamming the poll exploit or what.
What about dynamic circle collision? Anyone can send some basic logic idea
I have two videos on this, Programming Balls!
4:49 LMAO)
Can you please make the same, but tiles are roads, not walls.