# Collision detection question

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

## Recommended Posts

Ok, I've been going over various tutorials on collision detection and the like and I'm becoming familiar with the requirements (I have a math degree so the math isn't an issue), but I have one question. How do you avoid having a huge matrix of distances between all objects on a game level that are subject to collision? I mean, you always have to know where everything is (relative to everything else) and the only way to know if a collision detection event is probable is to keep track of ALL relative distances and continuously update them. What are the techniques for the pre-collision detection? I'm thinking of an array of distances between eligible objects (pretty much everything) that updates rows and columns only for any object that moves. If the object moves, all relative distances between it and anything it can collide with are updated. The problem with THAT, however, is what happens with a narrow object that you teleport PAST, for example. I was orginally thinking of some kind of signed distance, but this only works if the area behind the object collided with is a forbidden area. But this is a different question than the first. So, I kind of have a couple questions here. 1. How do you track distances between all objects on a game level without gigantic arrays? Or can you work around having to track these distances? 2. What do those distance numbers really break down to? If anyone has links to info on this I would greatly appreciate them! P.S. I'm coding in C

##### Share on other sites
I'm not particularly familiar with the method you're proposing, but I don't think the collision detection problem is typically approached that way in games. Usually there's a broad phase and a narrow phase; there are multiple algorithms you can use for each, and which to choose depends on the circumstances. If I'm understanding your post correctly, it seems you're suggesting maintaining a table of the distances between all objects in the simulation and updating it dynamically. I doubt this would be practical, or even feasible, and in any case there are many more commonly used and, I think, better approaches. If you need more specific advice, perhaps you could describe your environment (2d, 3d, terrain, indoors, etc.) and what sort of objects you want to support in your collision detection code.

##### Share on other sites
Well, my question was posed generally but the specific environment simulation is 2-D, though the graphics are fake 3-D iso. I'm only concerned at the moment with the simple case of bounding circles, line segments, and points. For example, I have approaches in mind that give me a continuously updated closest-point-of and distance-to any given segment from any given point. But my question is, how can I exclude segments (or any objects generally) without knowing their distance to the object in question anyway? Don't I end up doing the calcs no matter what? And doesn't this become even more of an issue if it's a fast moving game with lots of object speed? My lack of experience shows here.

I have found a load of tutorials and explanations on the collision event itself, but not so much on how to keep track of all the objects generally PRE_COLLISION, the initial collision warning criteria, and what goes into that part of the code/design.

##### Share on other sites
Well, I don't want to just say outright that distance-tracking is not the way to go; in fact, the general idea forms the basis of various feature-tracking algorithms that have been developed at one time or another. However, these methods aren't really used much in practice, at least these days, and are limited in that they are primarily discrete algorithms and may suffer from artifacts such as tunneling and popping.

A more typical approach is to choose an appropriate narrow-phase algorithm, and an appropriate broad-phase algorithm (this latter term may be a good one to google for if you're seeking more info). Narrow-phase algorithms include closest-point tests, solving quadratics for swept circles and spheres, the separating axis theorem (SAT), the Gilbert-Johnson-Keerthi algorithm (GJK), etc. Broad-phase algorithms include sort and sweep, and various spatial partitioning techniques such as BSP trees, quadtrees and octrees, and grids.

Take your 2d circle, segment, and point problem as an example. I see two good choices for the narrow-phase. If your objects don't move too fast, you can use discrete collision detection and response using closest-point functions, which is quite easy to code. If the objects do move quickly, you would probably have to implement a swept circle algorithm. As for the broad-phase, if the objects are roughly the same order of magnitude in size, a simple grid would probably suffice.

Anyway, these are just some ideas to consider.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 14
• 11
• 28
• 15
• 39
• ### Forum Statistics

• Total Topics
634835
• Total Posts
3019539
×