Advanced Collision Detection Algorithms

[A-Man]

Hey! It's me again
So this time it's not a problem, but a discussion. In LF2, and most other simple games, they depend on pure rectangles or sometimes circles for collision detection. What I want to know is the most optimal algorithm to do more advanced collision detection; say collision between a rectangle and a circle, or even a collision between a trapezium and a 5+sided-polygon. I've read about some algorithms like Binary Space Partitioning and per-pixel detection, but these seemed too expensive to actually use. In popular game engines like Unity, one is able to actually trace a surface with a line strip which happens to be fast and efficient 0_o. What do you guys think? Any best algorithm out there?

[Bamboori]

im using game maker and altough it gives you the option of using collision masks other than rectangles, i hardly ever use anythign else.
the reason?
lets say you have a character that moves around in a labyrinth (top view). with a square collision box the collision may not be as accurate, but he cannot get stuck on edges. what if your mask is one pixel too far on the left so you hang on an edge? or what if you rotate your character sprite (alogn with the collision mask) and end up inside the wall?

of course there are ways to solve these problems, but im a lazy person. and: if the player doesnt know, would he really notice? maybe if the collision boxes were extremely far off.
but take the 2d street fighter games. do you see people complaining about collision detection? they still use box collision since it suffices (multiple boxes tho).

[A-Man]

Well, it is true that rectangles do the job for most attacks and stuff, but sometimes, you might face cases where it would be much more accurate and more convenient if you can do a parallelogram or something:


You see the point? That especially applies for platforming. Say you want to have a parabolic hill or stairs, or a fighting ring or anything like that, rectangles wouldn't do them justice IMO.

[Boop]

Most of this stuff is described in math(geometry?) textbooks. Especially circle collisions and stuff.

I wrote this for a crappy android(https://play.google.com/store/apps/detai...Hobo&hl=en) game I made a (long)while back: http://slexy.org/raw/s21Bsi6YvL


The hobo was a circle. Cars were polygons. To check if a circle overlaps with a polygon I just iterated over each vector in the polygon and checked if it(the vector) overlapped with the circle. There is a tiny optimisation where before checking all the vectors in the polygon I first check if the the circle is inside the rectangle at all (since you can do that pretty fast).

Code:

        for (int x = 0; x < 4; x++)
        {
            List<Vehicle> cars = this.cars[x];
            int len = cars.size();
            for (int i = 0; i < len; i++) {
                Vehicle car = cars.get(i);
                if (OverlapTester.overlapCircleRectangle(car.bounds, hobo.circleBounds)) {
                    for (int j =0; j < car.boundingPolygon.length - 1; j++)
                    {
                        if (OverlapTester.testCircleSegment(hobo.circleBounds, car.boundingPolygon[j], car.boundingPolygon[j+1]))
                        {
                            hobo.hitCar();
                            listener.hit();
                            car.hit();
                        }
                    }
                }
            }
        }
    }

Code might be terrible, but it worked .

Edit: Looking over that code, you should stop iterating over the vectors which make up the polygon if you've already found an intersection. God damn it I suck at coding T_T

[Kevin]

and for polygons:
http://www.docdroid.net/egf9/collision.pdf.html

And I just realized that the lines might be parallel xP , so before checking intersections between two lines, check if they have the same gradient m.

[A-Man]

Haha! Thanks a lot guys XD! I will let you know when I am done implementing it for the engine and will probably share the code here. (pretty sure one can implement that for LF2 as well with THIS (why hasn't that got much attention though.. I wonder..))

Edit V: Aha! Collision masks.. Lucky guy XD

[Bamboori]

...ooooor we implement it in our engines :D itd be way easier for me though since i can simply use collision masks :p