Sign in to follow this  

ideas about collission detect in game level

Recommended Posts

KaiNiklas    1213

i just wanne know how you would solve the collision detection in a game like counterstrike ? thinkmabout the buildings eg. so there are walls with doors - caves , and so on....
so i had 2 ideas beside coll detect with every triangle.

one is to have a invisible geometry that encapsulates every space you cant access ( walls, ... ) and use isInside() function to check every frame ( in octree of course )

second is to draw boxes above every solid element using its normals and test for pointInside() this triangle boxes - again of course with octree preselect.

i have these ideas but bevor i start implement it , imwanne hear how you do it... maybe i just did not thought of a more simple idea..


Share this post

Link to post
Share on other sites
cr88192    1570
well, if talking about the original Counter Strike, this game was using the GoldSrc engine (Valve / Half-Life), which was based on the Quake engine. so, the more general question might be, how did Quake do it?...

one partial answer comes from how the maps were represented:
they were composed of "brushes", where each brush was basically a collection of planes which would serve to define a bounded region.

for example, with 6 intersecting planes, you can make a cube.
to check something against a brush, you can essentially find its extents along the plane, and if the object is completely "above" the plane on any side, then there is no collision.

as a result, the entire inside region of a brush can be determined to be solid, with little need to know or care about individual polygonal faces.

you can also make a variety of shapes from planes, such as rough spheres or cylinders, ...

in-game though, this isn't exactly how it was done.

(this is "more or less", I am mostly going off memory here, so could be wrong on the specifics).

basically, instead, a BSP-tree was built, which divided the space up into regions along each plane. basically, you would find a plane that divides the world roughly in half, then recursively find planes to divide each sub-region in half, until ultimately there are no more planes left with which to divide the space in half.

so, at the bottom of this tree were its "leaves", each of which only had a single type of "contents" (negative magic numbers for Quake 1, bit-flags for Quake 2, with numbers >=0 identifying BSP nodes).

for example (leaf types):
empty space, solid, water (blue-tinted water), "sewer" (brown-tinted water), slime (green tinted and painful), lava (orange-tinted and more painful), sky (solid to players, causes projectiles to despawn), ...

for doing physics, you would step down the tree (using a point or bounding box), and eventually find all the leaves which the box was in contact with (and their relevant nodes/planes), and then use this to figure out which effects applied (if the box is partly inside a solid leaf, it is colliding with something, ...). effects were ordered, such that stronger effects would apply before weaker ones (for example, if something was touching both solid space and lava, the solid space would take priority, ...).

typically, it would also identify a plane which the box was sliding along, and do its physics mostly in terms of boxes sliding along these planes (mostly via eliminating movement along the plane's axis if it would lead into a solid leaf).

however, for normal entities, it was done differently, leading to the whole odd effect that there was no friction when standing on someones' head, ...

in my engine, I was lazy, and just used the brushes directly for physics instead (for "simple physics"), using a more lax (and dynamically-built) BSP tree primarily as an organizational structure (to speed up rendering and queries).

I didn't bother with slide-planes, and instead made most of the physics more simplistic:
"for this region of space, which contents flags are present?"

in the case of collision the engine then mostly just guesses possible movement planes, and uses probes to figure out if it will work ("if this object moves this way, does it still collide with something?").

Share this post

Link to post
Share on other sites
Lightness1024    933

pretty much like cr99192 said. some other games uses colliders defined by the level designers. think about UT2003 for example there is a lot of details on the walls (pipes..) but the collision is far from all of that

Indeed counter strike uses the actual display objects for collision, diminishing level designer's job. It also uses plane following to simplify dynamics computations from the user input. gravity is out of the equation and takes away a lot of instabilities due to its great values. (9.8m/s/s is... STRONG)

Also, think about the volume problem, that is the most difficult. You don't want to test anything IsInside(), you want to test a bounding volume (your player) against another volume (the world) which is much much more complex than "this point is IN or OUT the world ?" And complexity only increases when you realize that you don't even only need to decide if your "volume is IN or OUT the world", but how to make it sllide, and if you want to push it further, to avoid any chance of traversal of slim barriers at high speeds, you would even want to make it "sweeped". sweep volume collision detection is difficult. I'd rather recourse to a library like bullet to take care of it, unless you're doing your master in physics related to numerical methods for example. If you want to make a game and actually finish it... :)

I'm one to talk because I attempted to recreate an engine like the one of half life based on hammer editor's output, and attempted a sweeped collision detector/reactor using paul nettle's introduction:

unfortunately I used variable time steps and got un-masterizable reactions, as well as impossibility to climb stairs, which led me to give up.

I realize now that collision detection was just impossible to do cleanly with only one model from the start. and you need to trick everywhere, like cutting gravity when you know you are already in contact, or using probes like cr88192 said, and various dirty tricks... but it works like that in the real world.

Last advice :

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