Sign in to follow this  
Promit

2D Collision detection with BSPs

Recommended Posts

Promit    13246
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]

Share this post


Link to post
Share on other sites
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--

Share this post


Link to post
Share on other sites
Promit    13246
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]

Share this post


Link to post
Share on other sites
Samith    2460
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

Share this post


Link to post
Share on other sites
FReY    424
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?






Share this post


Link to post
Share on other sites
Promit    13246
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?

Share this post


Link to post
Share on other sites
Infinisearch    2971
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]

Share this post


Link to post
Share on other sites
Promit    13246
Right. That doesn't help.




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.

Share this post


Link to post
Share on other sites
Infinisearch    2971
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?

Share this post


Link to post
Share on other sites
M3d10n    170
Check the "ellipsoid collision detection" tutorials in the Articles section. They'll show you how to test a sphere/circle against a line segment.

Share this post


Link to post
Share on other sites
Promit    13246
*sigh* No. I don't understand how to traverse the BSP tree. Mainly, I don't understand what to do if a segment is across a partition line.

Share this post


Link to post
Share on other sites
jack_1313    536
If it were me I might go about managing your collisions in a slightly different fashion. As mentioned, one problem with bsp design is that if the data is large enough you may still be searching for eons trying to find a collision. The bigger the level, the larger the search. Even if the geometry was first divided into a quad tree the issue is still present, given a game world that is large enough.
At this point I shall point out that my experience with bsp concepts does not span much further than reading a few paragraphs… I do apologize if the prior paragraph is a load of nonsense or the next is similarly bad.
If I were in your situation I would take a different approach:
A dynamically allocated 2d array exists to grant fast access to the immediate geometry surrounding a given position. The array elements represent ‘sectors’ of the map. The sectors are arranged like a grid, each one not large in size. An element contains a list of pointers, of which point to line segments that lie within the corresponding sector. The array must operate so as that point p is in sector p.x / sector_width, p.y / sector_height.
To perform collision checks for circle c, one must only test against the segments found in the circle’s current sector and the eight sectors surrounding it.

Hope this helps… and sorry it’s so rushed…

Jackson Allan

Share this post


Link to post
Share on other sites
FReY    424
Okay Promit, I see what you mean now. If your swept sphere crosses the boundary, have you tried something like this?


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 )
{
CheckNode( Node.Front, s, tr, r );
CheckNode( Node.Back, s, tr, r );
}

Share this post


Link to post
Share on other sites
Promit    13246
You're a couple days late, but that's what I ended up doing. Except I'm also aplitting the ray on the boundary, since it makes swept circles much easier to deal with.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this