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?

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
}

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.

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_42
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.

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?

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> > >

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!

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.

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 ;)