Jump to content
  • Advertisement
Sign in to follow this  

Collision Detection Question/Methods

This topic is 4223 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

A bit of background for those interested in helping me out here: I'm a 4th yr college student with a good background in C/C++ and object oriented design. In addition to the typical cirriculum I've done a lot of poking around on my own and been messing around learning the basics of directX, openGL, and just creating games in general. So far I've got a couple simple games under my belt (like the asteroids clone) and a nifty particle engine. The last real thing I'm having problems with is a nice way to represent game objects in such a way as to handle the collision detection in a nice accurate and efficient manner, prefferably with an entity engine or somthing similar to manage both new objects and their properties. This question has multiple angles so allow me to elaborate a bit. I'm trying to figure a good way to do collision detection for (each of these separately): asteroids-type games tetris-type games rpg-type games (like final fantasy 1 style) I don't mean a 'good way' like shpereical or square bounding boxes, I mean more conceptually how to setup the system and represent the objects. I have read most of the material on this site and many more and I'm still somewhat stumped at a good way to do these things, any help or insight would be appreciated. Thanks!

Share this post

Link to post
Share on other sites
Objects are typically surrounded by a 'collision shape'. A sphere/circle, box, polygon, convex hull, ect... Then collision detection is performed between shapes. Dynamic objects are typically relatively small in size, and in the same order in size as well, so the collision test can be accelerated using a dynamic space partitioning technique (sweep and prune for example).

The static world can be represented in various ways, usually a collision map, that can be a large quantity of collision shapes, or segments, triangles, polygons... The collision test gainst the world can be accelerated using BVH (bounding volume hierarchies), or other space partitioning techniques pertinent to your game setup (2D grid, quadtree, ...).

Collision between objects are usually performed between pairs of objects other a single frame. The collision detection algorithm will return information about the type of collision, and collision parameters (points of contact, plane of collision, time of collision, ect...). Then a collision response is performed to resolve the collision between the pair of objects (push the objects apart, blow one up...). Then another pair of objects is tested, and so on, until all potential pairs of colliding objects are done.

Collision with the world is performed by finding the part of the map near the player (this is where the space partitioning is beneficial), and the similar to the object-object collision, some collision information is returned, and the object reacts so the collision against the world is resolved.

the collision system for a tetris game is completely different from a collision system for an asteroid clone. a tetris game would probably have a 2D grid representing the cells that are already filled with blocks, and then you check the cells that the falling piece overlaps to detect a collision.

a collision system for an asteroid clone would be based on polygon intersection. Your asteroids are represented by a polygon shape, your ship as well, and you test for intersection between the ship polygon and the asteroid polygons. The bullets would simply be moving points, that you can test to see if they are contained inside an asteroid polygon.

conceptually :

- Collision object
- Collision shapes[]
- Type (bullet, spacship, asteroid, world, ...).
. various uses.
- Filter out collisions that should not be performed (eg bullet vs bullet).
- Each types of objects are inserted inside a different collision map.

- Collision Shapes
- Sphere
- Polygon
- Point
- Segment
- Box
- Segment
- Polygon

- Collision Bounding volume
- used to spacially sort a objects quickly inside a collision map
- bounds a collision object roughly
- bounding sphere
- bounding box

- Collision map
- Sorts collision Bounding volume spacially
- sweep and prune
- 2D grid
- Quadtree
- BSP tree

- Collision Result
- Shape 1
- Shape 2
- Point of contact on shape 1
- Point of contact on shape 2
- Normal of collision
- time of collision

- Collision Response
- Collision Result as input
- Typically, the collision response has a callback to perform custom results
- Blow up object 1
- play a collision sound
- play a hurt animation
- perform a rigid body response to get an accurate physical response
- ect....

Share this post

Link to post
Share on other sites
here would be a typical collision loop, very basic.

for (i = 0; i < numObjects; i ++)
std::list colliders = object.FindPotentialColliders();

for(int j = 0; i < colliders.size(); i ++)
Collision::Result result = object.Collide(colliders[j]);


Share this post

Link to post
Share on other sites
To the previous poster: I saw the book posted in another thread and I will certainly be buying it when I am able (go go poor college student!).

To oliii, thanks a bunch. You've given me a swath of new keywords to research (like collision map and the BVHs) and I believe with these I can figure the rest of my problems out. The interesting thing that is for most my searching done on this site I did not find anything about those particular topics. Maybe I'm blind and just missed it.. *shrug* but thanks again!

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!