Members - Reputation: 874
Posted 16 March 2013 - 02:31 PM
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..
Crossbones+ - Reputation: 1554
Posted 16 March 2013 - 03:21 PM
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?").
Current Status / Downloads: http://cr88192.mooo.com:8080/wiki/index.php/BGB_Current_Status
YouTube Channel: http://www.youtube.com/user/BGBTech
Members - Reputation: 739
Posted 20 March 2013 - 09:41 AM
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: http://www.gamedev.net/page/resources/_/technical/game-programming/general-collision-detection-for-games-using-ell-r1026
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 : http://gafferongames.com/game-physics/fix-your-timestep/