Jump to content
  • Advertisement
Sign in to follow this  

Real-time collision

This topic is 2223 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, guys!
I have model a scene like the map-"assault" in counter-strike 1.5.

Now, i need to do collision test, but it seems very difficult because of the complexity of the scene.

How could I do a real-time collision in the demo? Do i have to turn to game engine? or, do you have any advice for me?

Share this post


Link to post
Share on other sites
Advertisement
Normally you accelerate collision detection by placing your map (all the triangles that make it up) in some kind of scene graph such as an octree. Then you can check collision with only near objects without needing to go through every triangle in the map (basically complexity O(log n) instead of O(n)).

You can also simplify the scene first in a preprocessing step, i.e. transforming a rather complex wall which is made of several hundred triangles (for overhangs, windows, decorations, etc...) into a single cuboid (or maybe just four quads depending on how cheap you want to get), since there is no real benefit in testing the intersection of the player with every tiny feature of the wall (but what about bullets?).

If you can use a game engine that already supports that, it's probably best you use that, because fast and efficient collision detection is rather painful to implement. But there's nothing wrong with doing it yourself to learn.

Share this post


Link to post
Share on other sites
Do i have to turn to game engine?
Well, you certainly could. Of course, this would trash all your work up to now. You probably want to look for a library instead. I suggest Bullet.


Normally you accelerate collision detection by placing your map (all the triangles that make it up) in some kind of scene graph such as an octree. Then you can check collision with only near objects without needing to go through every triangle in the map (basically complexity O(log n) instead of O(n)).
Let me elaborate. In the old days (CS 1.5 might be considered oldschool) graphics and collision representation were mostly the same thing. As time progressed, the two representations started to diverge. Personally I believe that the choice of an octree for this kind of data is odd at least: it appears to me that dataset complexity belongs to the realm where BSPs reign supreme... in the end this does not matter; so many things can go wrong with collisions and physics I strongly advice against coding it yourself, not even for learning purposes.
While I appreciate the recent trend of this forum in providing more and more theorical data with big-o notations, I must note that in the end, profiling and timings are kings.

since there is no real benefit in testing the intersection of the player with every tiny feature of the wall (but what about bullets?).
Very interesting point. As a matter of fact, the player expects its avatar to move much more freely than it appears. In some cases, the floor, or even the walls might be enclosed by collision hulls to smooth out movement. In some cases, this will also help navigation.
Bullets are pretty much of a different beast.
If they leave no marks, some divergence between graphics and physics is often tolerated.
When marks are required however, this becomes pretty much a different beast. It is now required to perform testing on the real graphic mesh. I'm not sure the old way of doing this is correct. New shader-driven technologies appear less limited and faster to implement.
Again, for CS1.5, it's probably easier to just use a single representation: there's enough perf to deal with it.

Share this post


Link to post
Share on other sites
So, what i need to do is getting all triangles from all meshes in the scene, and test collision between the character and the triangles, is it right?
Is there any simple sample for me to learn it ?[/quote]
Well, not quite. That's the first step. If you did it like that it *would* work, but it would be quite slow and inefficient. The next step is to arrange your triangles in a spatial structure (BSP tree as Krohm says, which stands for Binary Space Partitioning tree), which basically allows you to say "this virtual box enclosing this bunch of triangles does not intersect the player, therefore none of the triangles inside it can intersect the player" thus allowing very fast intersection. But this is quite tricky to implement (along with the necessary maths and physics for actual collision detection) so unless you *really* want to learn how to do it you are better off using a library which abstracts all of that away from you so you can focus on the good stuff.

Share this post


Link to post
Share on other sites
I suggest to look at a physics library. It's probably the best detailed source to learn from.

While I admit I have pointed at BSP trees, I suggest against using them as well as staying away from anything involving partitioning of graphics representations. BSPs are good, but they also demonstrated to be incredibly difficult.
There have been some rants about BSPs in the past. I remember this.
I am currently quite impressed by AABB trees. SAP (Sweep and Prune) algorithms are interesting but in the end, they ran at basically the same speed on my data sets.

But let me reiterate. Stable collision detection is hard. Are you sure?

Share this post


Link to post
Share on other sites
I am busy in building the scene and other simple effect, so i have almost forget thistongue.png .

My meaning is that, supposing, i get a stair model, through it the character can walk up to another floor. So how can i do the collision between stair and character?

Is it that I get all triangles from the stair model and then use each of them to do collisionph34r.png ?

Share this post


Link to post
Share on other sites
That would be the simplest method, yes. But you will need to add some "tolerance" to height differences so that your character smoothly walks up the stairs without needing to jump. But that's the obvious method and there are several dozen possible improvements on this to improve performance, accuracy or both.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!