2D Collision detection with BSPs
I'm trying to design a 2D game, and I want to make the level itself a collection of arbitrary lines positioned in space. What I need, though, is to be able to quickly collision detect these lines against swept circles and figure out where to stop those circles (which represent objects, obviously).
I have no real idea how to do this.
I think there's enough info around that I can construct a BSP tree of my level, so that's not a problem. But I don't really know how to collision detect it. I'm willing to assume that all of the walls are convex hulls. But I really don't know anything about this, and I'm having trouble finding resources that aren't about doing exactly what I want...but in 3D and using Q3 maps.
By the way, rectangles instead of circles would be fine too.
(On second thought, some examples of how to create the BSP would be appreciated as well...but it's secondary.)
[Edited by - Promit on August 5, 2004 5:41:19 PM]
This may be way out of my league, as I know nothing of BSPs, but just wanted to throw up an idea.
I'm assuming what you're trying to do is have characters be stopped when they walk against walls. There are a few approaches, but to keep it simple, I just keep track of the "outside" of the wall, and if the circle collides with the line, then I move the circle along the wall's normal until it is just outside of the wall. So actually, rather than stopping the player before he walks in the wall, I simply reposition him back out if he has walked into the wall. But if this is done before the call for drawing, then the player appears to always remain outside of the wall.
If you're interested in the exact mathematical way of doing this, I could go into it as well, but I have a feeling I may be answering the wrong question entirely.
--Vic--
I'm assuming what you're trying to do is have characters be stopped when they walk against walls. There are a few approaches, but to keep it simple, I just keep track of the "outside" of the wall, and if the circle collides with the line, then I move the circle along the wall's normal until it is just outside of the wall. So actually, rather than stopping the player before he walks in the wall, I simply reposition him back out if he has walked into the wall. But if this is done before the call for drawing, then the player appears to always remain outside of the wall.
If you're interested in the exact mathematical way of doing this, I could go into it as well, but I have a feeling I may be answering the wrong question entirely.
--Vic--
Quote:Original post by Roof Top Pew Wee
but I have a feeling I may be answering the wrong question entirely.
Well, in short, yes.
Checking a collision between any given sphere-line pair is trivial. The problem is when you have several hundred of those pairs. I wanted to implement a 2D BSP (or in fact, any kind of tree), but I really don't understand hwo to collision detect with it.
[Edited by - Promit on August 6, 2004 8:31:53 AM]
Are you saying you don't know how to do collision detection to find which lines are in the BSP, or what? I don't get what you mean when you say "I don't really know how to collision detect it".
If you mean you don't know how to find which node a line belongs to, then I would just put a bounding sphere around the line (I'm assuming that when you say line, you really mean segment) and check if that bounding sphere for the line is within the BSP node's rectangle. Check against every leaf node, and put a pointer to the line or whatever in every node that the line could potentially be in. If you mean lines, not segments, then just check each line for a collision with all of the segments that make up the BSP node's rectangle, check every leaf node, and put a pointer to the line in every node that the line hits.
If you're having trouble constructing the BSP tree, well then I'm not really sure. I'm assuming that a BSP tree is like a quad-tree..only each node has two children instead of four. In that case, just make the head node of the BSP tree have a rectangle the size of entire world, then in the first subdivision make the head nodes two children each be half of the head node. Then divide each child into two and so on.
I'm wary of going into too much detail because I have a feeling you already know everything I'm saying and I'm not answering your question :p Well, if this is what you're looking for then I hope it helps :D
If you mean you don't know how to find which node a line belongs to, then I would just put a bounding sphere around the line (I'm assuming that when you say line, you really mean segment) and check if that bounding sphere for the line is within the BSP node's rectangle. Check against every leaf node, and put a pointer to the line or whatever in every node that the line could potentially be in. If you mean lines, not segments, then just check each line for a collision with all of the segments that make up the BSP node's rectangle, check every leaf node, and put a pointer to the line in every node that the line hits.
If you're having trouble constructing the BSP tree, well then I'm not really sure. I'm assuming that a BSP tree is like a quad-tree..only each node has two children instead of four. In that case, just make the head node of the BSP tree have a rectangle the size of entire world, then in the first subdivision make the head nodes two children each be half of the head node. Then divide each child into two and so on.
I'm wary of going into too much detail because I have a feeling you already know everything I'm saying and I'm not answering your question :p Well, if this is what you're looking for then I hope it helps :D
Basic BSP collision detection algorithm:
1) root = BSPtree.root
2) if root node is NULL, no collision occurred, exit.
3.) Test shape against root node shape.
4.1) if shape collides with root node, a collision occurred, exit.
4.2) if shape is on left of root node
root = root.left_child_node
4.3) if shape is on right of root node
root = root.right_child_node
5.) goto 2.
Hope that helps. Do you need help constructing the BSP tree too?
1) root = BSPtree.root
2) if root node is NULL, no collision occurred, exit.
3.) Test shape against root node shape.
4.1) if shape collides with root node, a collision occurred, exit.
4.2) if shape is on left of root node
root = root.left_child_node
4.3) if shape is on right of root node
root = root.right_child_node
5.) goto 2.
Hope that helps. Do you need help constructing the BSP tree too?
Eh...I don't think I'm phrasing my question too well...maybe a side effect of still being in the conceptual stage.
Let's see. I have a 2D world composed of line segments. To construct a BSP, I choose a segment (random, closest to middle, whatever) and extend it to slice the entire world into two halves. I classify every other line as either in front or behind (and slice lines that intersect). Do the same for every half space until I reach leaf nodes that have no more lines in their half spaces. That's correct for basic construction, right?
Now, I need to do collision detection against this tree. If we simply take a segment and attempt to decide whether it collides with the world, you can start at the top of the tree. Classify the start and end points. If they are both on the same side, recursively slide down just that half of the tree. If they are on opposite sides, go down the tree, starting with the side that the start point is in. I still more or less know what's going on at this point.
Here's the problem. I need to do this collision thing for spheres. Given a start and end point, I need to determine where the sphere would hit the wall and stop. I've read about expanding the walls inward and using them for line collision...but that seems overly complex. Isn't there a simpler way? How is this generally done?
Let's see. I have a 2D world composed of line segments. To construct a BSP, I choose a segment (random, closest to middle, whatever) and extend it to slice the entire world into two halves. I classify every other line as either in front or behind (and slice lines that intersect). Do the same for every half space until I reach leaf nodes that have no more lines in their half spaces. That's correct for basic construction, right?
Now, I need to do collision detection against this tree. If we simply take a segment and attempt to decide whether it collides with the world, you can start at the top of the tree. Classify the start and end points. If they are both on the same side, recursively slide down just that half of the tree. If they are on opposite sides, go down the tree, starting with the side that the start point is in. I still more or less know what's going on at this point.
Here's the problem. I need to do this collision thing for spheres. Given a start and end point, I need to determine where the sphere would hit the wall and stop. I've read about expanding the walls inward and using them for line collision...but that seems overly complex. Isn't there a simpler way? How is this generally done?
Depending on how big you expect your levels to be you might want to quadtree the level first and then bsp each quad to minimize tree traversal for collision. If your levels are going to be huge, traversing one big tree for each collision check seems like it could become expensive real fast. So setup BSP's within each quad of the quad-tree and then cache which quad each dynamic object is in.
edit - btw unless i'm mistaking your meaning it seems to me you're more stuck on collison response than detection. When you detect a collision, just determine the depth of interpenetration, just move the object in the -V (v being velocity which you already have in [end_pos - start_pos]) direction the appropriate amount. BTW I'm under the assumption that your BSP will have four cuts for a rectangular object, meaning you'll have to collide with more than one plane in order to see if a collision occured in the first place.
[Edited by - Infinisearch on August 6, 2004 1:26:55 PM]
edit - btw unless i'm mistaking your meaning it seems to me you're more stuck on collison response than detection. When you detect a collision, just determine the depth of interpenetration, just move the object in the -V (v being velocity which you already have in [end_pos - start_pos]) direction the appropriate amount. BTW I'm under the assumption that your BSP will have four cuts for a rectangular object, meaning you'll have to collide with more than one plane in order to see if a collision occured in the first place.
[Edited by - Infinisearch on August 6, 2004 1:26:55 PM]
Right. That doesn't help.
I've got that BspNode structure that represents a single node in the tree.
Segments is an array of line segments (with vectors start and end) that represent all of the line segments that are colinear with the Line Partition (Partition is of the form ax + by + c = 0).
So I've set up a function something like this:
The problem is the last TODO. I don't have any real idea of what I'm supposed to do there.
public class BspNode { public Line Partition; public BspNode Front; public BspNode Back; public Segment[] Segments; } I've got that BspNode structure that represents a single node in the tree.
Segments is an array of line segments (with vectors start and end) that represent all of the line segments that are colinear with the Line Partition (Partition is of the form ax + by + c = 0).
So I've set up a function something like this:
public static class TraceResult { boolean Collision; float Frac; Vector2D End; } //determine the collision point of s with the world public void CheckNode( BspNode Node, Segment s, TraceResult tr, float r ) { int Side = ClassifySegment( Node.Partition, s ); if( Side == Classify.Front ) { CheckNode( Node.Front, s, tr, r ); } else if( Side == Classify.Back ) { CheckNode( Node.Back, s, tr, r ); } else if( Side == Classify.Across ) { //TODO: determine if a collision occurs and where } }The problem is the last TODO. I don't have any real idea of what I'm supposed to do there.
your segment are defined by start-end points which can be easily converted to lines perpendicular to the slope of the associated bsp node. once converted (on the fly, loadtime) just plug origin of sphere into newly generated line equations, and figure if you are within said segment. Is this the answer to what you're asking?
Check the "ellipsoid collision detection" tutorials in the Articles section. They'll show you how to test a sphere/circle against a line segment.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
