Help to optimize collision algorithm
BlitzMax Forums/BlitzMax Programming/Help to optimize collision algorithm
| ||
| Take a look at the below algorithm. Assuming it is working and all. Can you see any speed optimizations that can be done in the code? Does it take memory or cpu to set all those variables at the start? Should I have those as arguments in the function instead? Would that make any difference? Any optimization tips are welcome. ' Check a Line against a Line ' Returns a point if they overlap, null if they do not ' This should be a very fast Algorithm. Method LineOverlap:Point2D( Line:Line2D ) Local Ax# = StartPoint.X Local Ay# = StartPoint.Y Local Bx# = EndPoint.X Local By# = EndPoint.Y Local Cx# = Line.StartPoint.X Local Cy# = Line.StartPoint.Y Local Dx# = Line.EndPoint.X Local Dy# = Line.EndPoint.Y ' Calculate a lot of values ' Their names is unesential ' I name them A,B,C and so on ' This it to make the math easier ' to manage and overlook. Local E# = ( Bx - Ax ) Local F# = ( Dy - Cy ) Local G# = ( By - Ay ) Local H# = ( Dx - Cx ) Local Q# = E*F - G*H If Q = 0 Then Return Null' Can not divide by Zero Local A# = ( Ay - Cy ) Local B# = ( Dx - Cx ) Local C# = ( Ax - Cx ) Local D# = ( Dy - Cy ) Local R# = (A*B - C*D)/Q If R > 1 Return Null If R < 0 Return Null Local C# = (A*E - C*G)/Q If C > 1 Return Null If C < 0 Return Null Local IntersectX# = Ax + R*E Local IntersectY# = Ay + S*G Return Point2D.Create( IntersectX, IntersectY ) EndMethod |
| ||
| Concentrating on Return Point2D.Create( IntersectX, IntersectY ) is where you will get most benefit, that is if likelihood of collisions is high. If so, I would add a cache to the Point2D object so it recycles from a preallocated cache of objects rather than calling New. if q>0 then changing: Local R# = (A*B - C*D)/Q If R > 1 Return Null If R < 0 Return Null Local C# = (A*E - C*G)/Q If C > 1 Return Null If C < 0 Return Null to: Local R# = (A*B - C*D) If R > q Return Null If R < 0 Return Null Local C# = (A*E - C*G) If C > q Return Null If C < 0 Return Null will save some divides. |
| ||
| Brilliant! How did you do to come up with that? :) I was first thinking of having one separate function for overlap; True or False and one which returns the point of impact. I did not know creating an object took any considirable time (thought about declaring a variable) so I figured I could just as well use the same. I'll make them separate then (Overlap and Collide). Thanks |
| ||
| What if you add a bounding box check at the start? |
| ||
| Ah true. I'll do that at a higher level. Is not a distance check faster than bounding box? I read that one could avoid the Sqr() when you calculate the distance and instead compare it to the square of the amount they overlap, like I tried to do above. Can I optimize that one more? |
| ||
| Just realised a circle does not have a very good fit for a line. I will use a box check. Does anyone got an optimized algorithm for that, does blitzmax have any built-in collisions except the image-layer ones? RectsOverlap(x1,y1,w1,h1,x2,y2,w2,h2) ? |
| ||
| Wave, have you seen my collision tutorials? May give you some ideas. http://www.blitzmax.com/Community/posts.php?topic=59723 |
| ||
| Nice assari. I have never seen circle v box before, very useful. I'll use those "quicker" collision methods before the more expensive poly or line checks I do. I'm working on a polygon collision module. I use layers in a similar fashion to the imagecollide. Basically you add objects ( polygons ) to different layers, then you can check these layers for collisions against eachother and choose the type of collision and what collision response (if any) you want the physics module to apply. If you know how to make a circle against polygon check that would be superb :) |
| ||
| Circle to Poly by Oddball in codearchives |
| ||
| Oh that will be of great help. Typical I did not check it out sooner :P |
| ||
| Here's an idea, not sure if it'll work or be faster... You are trying to check two lines against each other to see if they overlap. So, Find the angle from X1,Y1 to X2,Y2 of the first line. This is how much the first line is rotated. You now want to use this angle to `virtually` rotate the viewing space so that the first line becomes a flat horizontal line. To do this all you need to do is `transform` the second line by rotating it by the original angle of the first line, pivoted at the center of the first line. You can now assume that the top or bottom of the screen represents the first line and the second line will still be at the same angle to it. Since you can figure out the length of the first line easily, you then just have to check if the second line intersects the top/bottom of the screen. You could just check of the coords of the second line are below the bottom of the screen on one end and above it on the other end. If you know the line overlaps the bottom of the screen in some way, you just need to know the ratio between X and Y differences for the second line so that you can take the amount of X step for that line and multiply it by the distance to the bottom of the screen. That should give you a final X coordinate where the line intersects and if Y ends before the screen bottom you know they don't intersect. You could then transform the coord back into the original space by -angle and that's your intersection coords. Something like that. Not sure if this is explained right or is going to work, maybe more steps involved, but I am wondering if this might be faster than your current math solution. Also you can find the X and Y differences ie X2-X1 and Y2-Y1 for the second line and divide them to get the X ratio ie an XStep# value, then take the coords for one end of the second line and subtract that from the height of the screen. Then multiply the X step by the distance from the second line's Y coord and the screen bottom, or by the length of the second line if smaller. I |
| ||
| Maybe, but I doubt the work is worth it :) |
   |