# How is the "scope" of collision detection generally handled?

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

## Recommended Posts

Just something I've been thinking about and now I've come to the point where I could actually use some info on it so: I'm making Pacman right now. The player-map collision detection works by comparing against the tiles directly next in the line of Pacman's movement. That's not so hard to do. Now I'm doing CD for the pills and I'm wondering: Is it customary for something like this to check for collisions between Pacman and EVERY pill on the map or would that be considered wasteful because obviously Pacman can only ever be in contact with a pill that's A. Right next to him, B. In front of him, so you're doing unnecessary checks. I would've done the pill CD the same as the map tiles but since the pills don't occur at completely regular intervals (not on top of walls for example) and since they were in a std::vector instead of a 2-dimensional array I decided to go down another route. Basically: Is it common/acceptable/adequate for a game such as an RTS or a top-down shooter for example, to check objects against EVERY SINGLE RELEVANT OBJECT on the current level?

##### Share on other sites
I think in this case it would be faster to check all pills, (if they are not alligned to a grid in any way). you could quickly discard any pills that are not close to pacman but there is really no point - the only reason for this is when an object has complex geometry and performing a collision detection would be more expensive than checking its bounding box(or sphere) first. If you align them to a grid then you can't get much faster than:

if(pills[pacman.y][pacman.x])
{
pills[pacman.y][pacman.x] = false;
// remove pill
}

##### Share on other sites
If there's a small number of objects (like in pacman) then checking all objects against each other is going to be quick and easy. The number of collision checks is roughly half the number of units squared. That means for 10 units you'll be doing 50 tests, but for 1,000 units you'll be doing 500,000 tests.

The first obvious optimization is that you only need to test the units which have moved against all others. There's no point doing a collision check on two stationary objects.

Another simple option to reduce the number checks required for more complex games is to store a list of pointers to objects in each tile of the map. You then only need to check against objects that are in the appropriate tiles, and update the lists in the tiles when they move.

There are also more complex spacial subdivision strategies like quadtrees, but you probably won't need them for a simple 2D game.

##### Share on other sites
Hmmm... k.

The way I have it now is that the map is divided into 15*15 tiles and at every intersection of 4 passable tiles there's a pill. So for the Pacman-map collision I used Pacman's position to get the position of the tiles around him that needed to be checked.

I thought about doing the same thing for the pills but I had 2 problems:
1. The vector is 1-dimensional. You can't make 2d vectors, right? Well I could probably figure this bit out anyway, wouldn't be so hard I suppose.
2. The placing is irregular so determining the number in the vector of the pill based on the position of the player would have to be done differently.

Is there an efficient way of making it so that if it's like this:

Pill-Pill-Pill-Gap-Pill

that the last one will be 2 spaces ahead of the pill before it in the vector? If I could figure that out it'd be easy. Maybe I just haven't looked at the vector class properly ^_^

Quote:
 Original post by Adam_42The first obvious optimization is that you only need to test the units which have moved against all others. There's no point doing a collision check on two stationary objects.

Hmm... makes sense. So if you were doing something like that, would you have a bool variable that you'd set to true if it moved or something?

##### Share on other sites
what is wrong with vector<vector<> >?

Note: the space is important between > > otherwise it is a shift operator not a vector of vectors.
well ok you probably want vector<*vector<> > but still you can compose containers however you like. I tend to use maps of maps as categorizers. kind of like map<states,map<cities,map<names,addresses> > >

##### Share on other sites
ok, there's commonly two approaches:

1. grunt or 'sheer power'
2. optimized

for something like pacman, that is incredibly cpu-easy, i would just go with the grunt approach, since the number of detections will still only be small.
so, if you had an array of objects (bots or collidables), you could simply check if any corner of the source object overlaps the rectangular region of the dest object. so you would have four checks. slightly optimised would be only checking a point on the edge in the direction that the source (pacman in this case) is moving, since he won't collide with something behind him. this would reduce by 4 the number of comparisons. however, if you have ghosts, which typically move, you would leve the four comparisons in and only check pacman against ghosts (not other way round, since that would be redundant and waste of cpu). another words, you just whip through one big for() loop, with a few if statements such as:

for i:=0 to 99 do
if (pacmanx>=targetx)and(pacmanx<=targetx+target width)and
(pacmany>=targety)and(pacmany<=targety+targetheight) then
[handle collision]

it's when you come to coding complex games where EVERY test is critical cpu-wize that you really HAVE TO optimize everything you do, and approach the whole code structure with optimisation in mind from the get-go.

ie, say you had some intense 3D pacman where there were events happening in all dimensions, and 90% of your cpu time was going into rendering the GFX, you would take into account only those events CLOSE BY your pacman, and ignore more distant ones, as one optimisation approach. you would also set up your data structures in ways that allow really fast comparisons, and this is where things like binary trees, etc come into play. serious games require serious thougth with regards to optimsation, but from what i gather of your project (2d pacman) you can completely ignore it and just go the brute-force way. I've done pacman myself as an early game years ago, and it worked sweet on the computers of that time with really crappy code structure.

I guess the most important point i can make here is DONT MAKE YOUR CODE MORE COMPLEX THAN IT HAS TO BE. i think its more important to complete a game and enjoy it than to worry too much about whether YOUR approach is 'typical' or industry-standard. once you've written a few games, THEN start considering optimisations and standard practice as you will soon find that you won't be able to write complex without them!

hope this helps!

##### Share on other sites
sorry, in collision code there should also be:

if (pacmanx+pacmanwidth>=targetx)and(pacmanx+pacmanwidth<=targetx+targetwidth)
same for y, etc

having BOTH these detections avoids having to check ghosts against pacman.

##### Share on other sites
Quote:
 Original post by Sean_Seanston1. The vector is 1-dimensional.
With a little bit of math you can index into a one dimensional array using a pair of x,y coordinates. You can see an example of someone using such a technique (albeit for an unrelated problem rather than collision detection) in this article for example.

##### Share on other sites
Alright cool, thanks guys.

Think I've a clearer idea of what to do now.

One more question for future reference though:
Let's say I made a relatively large top-down game something like Blood Omen Legacy Of Kain or Smash TV. Would it still be fine just to loop through all enemies? I suppose you'd just have a separate vector for every "level" or screen's enemies and loop through that. Would it even be any more complex than Pacman? Since, while all enemies would be far more complicated than a pill, you're still just comparing the boxes of each object.

As for vectors: Would lists actually be better? I thought I heard that lists were better when you were removing elements from the middle rather than the end, which obviously you would be doing in the majority of gaming uses for STL containers. I know it probably doesn't make a difference at this level but just for curiosity ;)

##### Share on other sites
*shrug*

I would say you could start implementing by just looping through all your bad guys on the map, and profile things as you go. If you determine that you're wasting too much time checking collisions between far-away objects, then work on something simple that will reduce the amount of checks. For 2D you should be able to get away with something really simple, like subdividing the map into a couple of sectors and only checking for collisions between objects in the same sector. Really any method based on spatial partitioning should work: you just need to take advantage of the fact that collision detection is only concerned with objects that are very close to each other.

##### Share on other sites
Quote:
 Original post by Sean_SeanstonAs for vectors: Would lists actually be better? I thought I heard that lists were better when you were removing elements from the middle rather than the end, which obviously you would be doing in the majority of gaming uses for STL containers.

Not necessarily. If the order doesn't matter you can remove from the middle and replace it with one from the back of the vector, which you then erase.

Also, lists maintain lots of little pieces of memory, meaning they can be slower if you perform a lot of add and remove operations.

##### Share on other sites
Are we really talking about the traditional Pac-Man video game, from 1980? People didn't use the term "collision detection" back then. You probably have a few tile types, one of which is "passable with a pill" and one of which is "passable without a pill". Pac-Man only moves in whole tiles (although the transition is smoothly animated). When Pac-Man arrives at a tile that is marked "passable with a pill", make a little sound, increase the score and change the tile to "passable without a pill".

Why make it more complicated?

##### Share on other sites
Hmm... wouldn't have thought of that.

That actually does sound simpler. Thanks, I'll probably leave it how it is for now but I'll keep that in mind in future :)

##### Share on other sites
in my game Warzone2D (warzone2d.tripod.com), I don't actually use bounding rectangles for collision detection as I personally find probs. I've found a much much much better way, and that is with proximity detection.
so in my code I just determine the absoulute distance from the center of my bots to one-another (or to items, etc) and use this.
eg using trig, you just do a test like:

if (distbetween(sx,sy,dx,dy)<=[5 pixel eg]) then // process collision code

where distbetween() looks like this:
sx,sy (source bot x,y)
dx,dy (dest bot x,y or item x,y)

distance:=sqrt(sqr(abs(dx-sx))+sqr(abs(dy-sy)));

note the use of absolute function abs() since we don't care about relative position just absolute distance between.

it's a really cool way of doing missile firing collisions too, since with the rectangular region you run into big problems when dealing with rectangles of vastly different sizes. eg your big rocket rect and a relatively small target object rect: there will often be a case where the four rectangle points totally overlap the smaller rect, which means you need to test not only the bigger rect against the smaller but also the smaller four points against the bigger. using proximity detection you can ignore all this garbage.

##### Share on other sites
@at_lowe: a proper AABB-check should take that into account, and it's actually fairly simple. In pseudo-code:
bool Collision(Box a, Box b){	return	a.x < b.x + b.width &&		a.x + a.width > b.x &&		a.y < b.y + b.height &&		a.y + a.height > b.y;}
Anyway, your proximity check (which is essentially a circle-circle check) can be optimized by removing the (expensive) sqrt call and comparing to the squared radii instead:
bool Collision(Circle a, Circle b){	deltaX = a.pos.x - b.pos.x;	deltaY = a.pos.y - b.pos.y;	return	(deltaX * deltaX) + (deltaY * deltaY) < (a.radius * a.radius) + (b.radius * b.radius);}

##### Share on other sites
- If you only have 100-200 objects in your game level optimization probably isn't necessary.

- 2D Vectors are fine, in fact they are used often. vector<vector<int>> then just treat it like a 2d array.

- for lists vs. vectors, lists are much slower for access. But then, in a small homebrew game the difference isn't large enough to matter. Usually, vectors are the better choice since they are significantly faster to access and you get the convenient vector[i] notation. If you need to delete from the middle of a vector just put the end item in that slot. Only use lists if they get inserted/deleted from the middle very often.

captain P:

er, ok!

##### Share on other sites
Well I just decided to loop through all the pills since there's probably no point doing anything else unless it's for experience but even then Pacman would probably be a bad place to test something anyway.

Right now I've got the pills working, the ghosts in and the ghosts can exit the starting box and find their home corners properly. Yay. And I didn't even use anything complicated like A*, woot.

##### Share on other sites

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

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628702
• Total Posts
2984299

• 23
• 10
• 9
• 13
• 13