I’m working on a 2D game where the environment is made up of 2D polygons. They’re just a collection of edges and normals defining the 2D shape. I would like to do collision against them using Panda.
I’m basically just trying to collide a sphere or some simple object against the edges of the polygonal volume – edges, not the surface of the polygon itself.
Is this possible with Panda’s collision system or should I be doing my own?
I’m not sure I see how pygame helps… it seems to have simple bounding rectangle collision but nothing past that.
It’s not the implementation of this that’s my problem – I’m just wondering if it’s possible to do it within Panda’s collision system.
Ahh… I’m new, generally, so not an authoritative source of information. I think you’re looking for pixel perfect collision detection, as opposed to a bounded collision detection solution…
This may work with what you’re trying to do 
If I understand what you’re asking, then yes, this will work with panda. You should be able to link them together pretty easily.
A pixel perfect solution would definitely do it if I were using 2D images, but the way I’m doing it I’m building the world out of 2D polygons. So… I think the polygonal tests will be the only way.
The more I think about it the more I think it would just be simpler in the long run to write it myself. Panda’s collision/physics is definitely designed for 3D, so trying to use it for 2D only would probably just cause me more pain than it’s worth.
Thanks for the help, though!
The easy way using panda would be to define an “into” collision object for one polygon (such as a sphere) and break the other polygon up into a set of line segments, which can be used as “from” collision objects. Remember that it doesn’t really matter which object is the “from” and which is the “into” as long as each have different roles.
If the polygons lie on (for example) the XY-plane at height Z=0 then this reduces to a set of 2D line segment and circle intersections that will work with Panda’s 3D operators.
I agree with Arkaein.
Panda doesn’t care if it is a 3d or 2d.
Correct me if I’m wrong
The way I’d approach this collision problem is similar to the way region detection is frequently handled in 3D games. Essentially, the question you want to answer is: Is the thing I’m checking against the environment overlapping one of my polygons? This is a very similar question to the 3D question “Is the thing I’m checking in a specific room?”
I would create one or more collision rays as from objects, attached to the thing you have moving through the scene (which I’ll call your ‘avatar’). Have these rays pointing into the scene—meaning from the camera’s point of view, they’re points. You probably want to offset them a bit towards the camera (i.e. give them, say, y=-1 instead of y=0) so that there aren’t boundary conditions to consider.
Now set your from mask on the rays (and attach them to the proper handlers) and set your into mask on your environment to the same mask. When the 2D coordinate described by the ray’s x and z origin overlaps a polygon, the ray will be penetrating the polygon in the y-axis and a collision will register.
Note that depending on what you’re trying to do, it may be easier to actually model a strip of 3D ground (i.e. extrude all your polys in the y-axis) and do your collision tests against those surfaces. It’s probably conceptually simpler, and if you hide the extruded portions it looks the same.
Best of luck!
-Mark
Using the segments as “from” objects is a really interesting idea! I hadn’t thought of it from that perspective. But, if I’m remembering correctly, there’s a limit on the number of “from” objects a traverser can use… I might be wrong on that.
The idea of testing with a ray pointing INTO the screen is really creative. I hadn’t thought of approaching it that way. I’ll try implementing it that way and post the results.
Thanks!
That’s semi-correct. While there is no hard-limit on the number of from objects, there is a limit from a performance standpoint.
In the most naive implementation, collision is the ‘handshaking problem;’ once per frame, every object in the scene must ask every other object “Hey, am I colliding with you?” Computer scientists will tell you that this is a somewhat inefficient algorithm; the runtime is O(n^2). O in this context is “big-oh,” it’s a symbol computer scientists use when they talk about how fast an algorithm can run. This is just a fancy way to say that if I have n objects, I have to do at most n*n collision checks. This result gets big even for small values of n; not fun if every wall can be collided against!
Panda offers two optimizations for this. The first is the implicit optimization of sorting the world into a big tree; Panda knows that if it considers a sphere around all the objects in the tree, and your object isn’t colliding with that sphere, then it also can’t be colliding with the objects in the tree. So it can ignore testing many individual objects by instead testing against big spheres calculated at each branch of the render tree. This is a great optimization except for some degenerate cases (like everything being on top of everything else). But it still requires every object to at least try to collide with every single other object in the scene. This is totally unnecessary; two pieces of ground on opposite ends of the map, for example, would never collide with each other—and even if they did, why would you care?
That’s where Panda’s explicit optimization comes in. Panda has you divide the collision problem into ‘from’ objects and ‘into’ objects. Then instead of checking every object against every other object, it only needs to check every from object against every single into object. If your set of from objects is small (like, say, a single player avatar), then this is a big win; the runtime complexity collapses from O(n^2) to O(m*n), where m is my from objects and n is my into objects—for every new from object I add, I need to make n more ‘from-into’ checks, and for every new into object I add, I need to make m more ‘from-into’ checks. The less from and into objects you have, the lower m and n are, and the faster your collision pass runs.
So there’s not a hard upper-limit on from objects; the limit is that if you have too many of them, you defeat the from-into optimization and your collision problem approaches O(n^2) complexity. Usually, it’s best to just use as many from objects and into objects as you think you need, and if the game is running way too slow, come up with a way to get the same result using less from and into objects.
I hope that all helps. Best of luck with your project; can’t wait to see it!
-Mark
Ah, okay. Apparently the 32 limit doesn’t apply past Panda 1.1.
I guess the main performance hit I’m looking at by treating the edges as from objects is that it can’t discard large amounts of them using hierarchical bounding volumes?
Is there a significant traverser overhead, or would it make sense to do an initial traversal using bounding volumes for the sets of edges, then additional traversals for each set of potentially colliding edges?
nostgard, just curious, how many objects are we talking about? I ask because you should have no problem with several dozen segmented polygon “from” objects and another several dozen sphere “into” objects. Sphere-segment intersections should be quite fast, and unless your polygons are very complex this shouldn’t get to be more than about 1000 intersection tests per frame (a little high, but probably doable). The best way is to try it and find out. Start with the simplest, correct method you know, and only worry about optimization if it actually turns out to be a bottleneck.
If you do need to optimize yourself you can start with sphere-sphere intersections on all objects and only enable the line segments collision objects when another object starts to get close to it. Assuming that actual collisions aren’t too frequent then in most frames you’ll likely have less than 100 collision test.
I’m not sure yet… I’d say worst case scenario would be 50 environment polygons averaging 200 segments each. So, per frame, something like ~10,000 “from” segments testing against 30 “into” swept circles (3D capsules in Panda’s case, I guess).
With bounding sphere tests that would probably be whittled to 30 traversals of 100-600 “from” segments testing against 1 “into” capsule.
As you say, it is just something that has to be tested. My questions were more out of curiosity than anything else – I already wrote my own collision tests that I plan to use instead. But, I do plan to try it using Panda’s collision as well for others to draw from.