Sign in to follow this  

2D Collision Detection using Opcode

This topic is 3665 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi to all, I am programming a Diablo-like RPG-game. The graphics should be 3D, but the collision detection problem is 2D. So I need collision detection system for a set of rectangles (walls, chests etc) and circles (monsters, heroes) and some ray collision detection (arrows etc). present state is: I assume that all Rectangles and Circles have radius / side length ==1 and represent the shape by its midpoint and the information whether its a square or a rect. All bigger Objects are split into a set of 1*1 objects. I use a Quadtree to store the set of points (and pointers to the objects of course). The reasons to change that are obvious: The representation is awful for long walls (dozens of little 1x1 squares) or other bigger obstacles, and I can't handle monsters of different size. On top of that I have some performance problems with my pathfinding algorithm. This algorithm does a lot of collision checks to get out, where a monster can move. OT: I am changing the pathfinding algorithm as well atm. There are a lot of tricks and improvements I can think of, to get my own code working. But it seems to me to be a very common problem, so I am sure someone has already done this better than i will do. The idea was, to use an existing collision detection lib. As these are always 3D, I could use the third dimension for choosing different types of objects etc. The collision detection lib that seemed to fit best is OPCODE. My main problems with Opcode are: 1. I am not sure, if it is really the right solution. The Manual says, that it provides a lot of different collisions against a mesh, but i need collisions agains a set of AABB/circles. The Opcode testframework shows an example of moving cubes which are painted green if they are not colliding, else red. This is exacly what I need. I took a look at the code and saw, that the list of AABB is passed as an array -it is impossible for me to create such an array as I use a flexible data structure for my objects an copying them to an array takes to much time. Overall it seems, that opcode is specialized on colliding few moving objects against a lot of static ones. In my case, the majoritiy of obstacles is moving and the number of objects changes often. 2. I can't find any good api reference/examples/tutorials for opcode. There is only the (horrible) manual, where nearly all lines look like tris=... and nobody even says you what type you should pass. It looks like *read trough the headers and you will see the api* - did I mention, that the headers arent commented too much as well? My Questions are: 1. Is using such a collision detection lib a good idea in my case? If yes: 2a: Is opcode a good choice and can you give me a doc for it ? if no: 2b. What do you advice me ? Using another lib ? Trying to improve my existing code until is does its job ?

Share this post


Link to post
Share on other sites
I'm all for using third-party code where possible, but a general-purpose 3D collision detection library might be overkill for your purposes.

It sounds like your requirements are very modest: intersection testing between rectangles, circles, and perhaps rays in 2D. Given that this is an RPG, I'm guessing you could safely forgo continuous tests and get away with static (discrete) tests only, which simplifies things considerably.

You mentioned restricting the collision primitives so that they always have an extent of 1. I'm not sure why this is necessary. It actually doesn't even do much to simplify the algorithms in question, so I would go ahead and allow for arbitrarily sized objects if I were you (this will also solve the 'breaking up walls into a million 1x1 boxes' problem).

If you need help with the details of implementing collision tests for any of the particular pairs of shapes (box-box, box-circle, and so on), you can probably get help here. Also, there are plenty of references available on these topics that we could probably direct you to.

Now, if you did want to use a third-party solution, I believe there are at least a couple of 2D libraries out there. I'm not that familiar with Chipmunk, but I know it's a 2D physics library that (I believe) supports the primitives you mention. I don't know how easy it would be to integrate into your project, but it might be worth taking a look at.

The pathfinding is a separate problem, more or less. If you're having trouble with that (or if it's performing poorly) you might start a separate thread (in the AI forum perhaps) on that topic.

Share this post


Link to post
Share on other sites
I mentioned pathfinding because the main bottleneck are the collision checks done by the pathfinding algorithm. The problem seems to be simple, so i wanted to point out, why I need a fast ( O(log n) ) collision detection.

Checking pairs of AABB or circles is easy - the problem is, that i can't check each pair (that is O(n²), respectively O(n) to check if one specific object is colliding), so I need a data structure, that helps me to select the very few pairs that really need checking.
As i said, the restriction of extent 1 comes with tha data structure i am using atm - the quadtree. In a Quadtree each node represents a certain area. To check an object I only look at the leafes that are overlapping with the area of this object plus a margin of one. If there is an upper bound for the extent of each object (let say 4), it is still simple: I add a margin of 4 to the area of the object and check all leafes overlapping with this area. That is still O(log n). But if I allow each object to have an arbitrary size, I have to check all leafes.
So my datastructure doesnt seem to be a really good. So i have the choice to set up a new data structure or to use the code of someone else.

Share this post


Link to post
Share on other sites
Search for "broad phase".
There is a discussion about it, ie. here: http://www.gamedev.net/community/forums/topic.asp?topic_id=389367

Algorithm chosen is specific to your needs, so maybe it might not be so good to choose a general collision detection library.
I have no expiriences with opcode.

I am not an expert, but unless your objects move way too much or you have many many many objects, I would try "sweep and prune" (or "sort and sweep").
Or uniform grids are also my favourite, because they are simple :)

For the broad phase I would not use both recangles and circles, I would choose only one.

Share this post


Link to post
Share on other sites

This topic is 3665 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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