collision detection for dummies

[bigmessowires]

I've got basic collision detection working, but I've run into a couple of problems I'm unsure how to solve:

 

1. Ideally my character would stop when it reaches an obstacle. But what actually happens is the character penetrates one pixel into the obstacle, the hardware detects a collision, and the character bounces back to its previous position. This looks sort of bad. Is there any clever way to prevent this, or is it just how it is?

 

2. My character uses several different player bitmaps depending on which way it's moving, and it also animates while it moves. The trouble is that for the same x,y location of the character, some bitmaps may collide with the playfield and some don't. This creates weird and undesirable effects, especially near the corners of obstacles. I might be moving vertically along the edge of a vertical wall, and when I switch to moving horizontally, the bitmap changes to a different one and suddenly the character is partly stuck inside the wall and can't escape. Maybe my collision handling is too naive? If a collision is detected, the code simply restores the player's x,y to the last good position.

[bigmessowires]

I have a few ideas about how to avoid getting stuck in the corner of an obstacle.

 

1. Don't use TIA hardware collision, use CPU collision with bounding boxes instead. Could work for some games, but impractical for most.

 

2. Use a sprite bitmap whose outline has 4-way symmetry, so no matter what axis it's flipped on when moving, it won't affect collisions with the playfield or other sprites. Shapes with a square or circle outline should be OK. Or just don't animate the sprite, and use the same bitmap regardless of which direction it's moving.

 

3. Use a second TIA object under the main character sprite that's square and the same color as the background, so it's invisible. Use this to perform bounding box collision tests. Wasteful.

 

4. Allow the character sprite to get stuck, but try to detect when this happens, and use some technique to get unstuck. Maybe increase the number of pixels you try to move each frame, or rewind to a "last known good" position and orientation, or warp to the closest respawn/recovery position. These all seem rather ugly and problematic, but I've already mostly ruled out the alternatives, so I'll probably be attempting a trick like one of these.

[bigmessowires]

Here's the code I have so far - an animated rodent exploring a maze. Collision mostly works, but occasionally he can get stuck on the outside corner of an obstacle.

 

There's no sprite for diagonal movement yet - you can move diagonally but it'll rapidly toggle between the vertical and horizontal sprites.

 

gopher-game.dasm

[+Andrew Davie]

I have never used hardware collisions. Always software for me. BITD if precision was required, then I used multiple bounding boxes, each with a "type" attached. So I could detect if a hand touched something, or if your feet were truly on the ground, etc.  I do understand the advantages of hardware for speed - but as I said, I would never use it. I like to be in control and pre-detect collisions before they *actually* happen, and re-adjust sprite/object positions so they stop/bounce exactly correctly without that overlap.

[+5-11under]

I've also only used bounding boxes. Also, I like to make sure that a bullet hitting enemy is a wider/easier hit, and a bullet hitting the player is a smaller/more difficult hit. It's especially annoying if your player dies when you've only nearly (or barely) been hit (depends on game and timing, of course).

[bigmessowires]

I can imagine using CPU collision with bounding boxes if the game is some type of shoot-em-up, but is that practical for a complex maze or "room" built with the playfield? I rejected the idea out of hand as being too difficult and slow, but maybe I shouldn't have.

 

At any rate, I finally eliminated the wall-sticking from my little demo. I wish I could say it was some clever algorithm that solved the problem, but it was really just a matter of modifying all the sprites to eliminate problem areas, which meant changing the character's appearance.

[bigmessowires]

After spending much too much time on this collision detection problem, I've concluded you were right: TIA hardware collision detection just isn't very good for obstacles that constrain movement - there's too much ugly bouncing off things and weird cases where objects can get stuck. I've reimplemented collision checking on the CPU, testing the player's bounding box against an arbitrary playfield bitmap, and it's so much smoother and better! It's too bad, because the TIA collision checking is free, but the CPU collision checking requires a ton of CPU cycles. For my purposes, I think hardware collision checking is still OK for determining when to activate or open or destroy something that the player touched, but not for constraining the player's movement.

 

colors3(3).a26

[Christopher Tumber]

Keep in mind that depending on how movement is handled, especially for sub-pixel movement (where your object moves less than one pixel per frame) you don't need to do full collision detection every frame.

 

For example, if the player only moves every 4th frame:

• Frame 1 - Player Moves - Check collision with 1st quarter of background maze
• Frame 2 - Player doesn't move - Check collision with 2nd quarter of background maze
• Frame 3 - Player doesn't move - Check collision with 3rd quarter of background maze
• Frame 4 - Player doesn't move - Check collision with 4th quarter of background maze
• Frame 5 - Player Moves - Check collision with 1st quarter of background maze

 

Additionally, you only need to check for collision against objects that are actually near the player. This is particularly useful with a static background (like a Pac-Man maze) since you can optimize this as much as needed but even with more fluid backgrounds (scrolling background) or background objects (enemy ships and bullets) it may make sense to sort or pre-parse objects so you only do collision detection against relevant ones.

 

For example:

• If player is in top, left quarter of screen only do collision detection against walls in the top, left quarter of screen
• If player is in top, right quarter of screen only do collision detection against walls in the top, right quarter of screen
• If player is in bottom, left quarter of screen only do collision detection against walls in the bottom, left quarter of screen
• If player is in bottom, right quarter of screen only do collision detection against walls in the bottom, right quarter of screen

Then you need to have four groups of bounding boxes for walls in each of those four quadrants of the screen rather than just an unsorted list of bounding boxes.

You also need a bit of overhead to determine what quarter (or smaller) section of the screen the player is in so your code can determine which set of bounding boxes to use but that's usually a very quick and simple check that may result in a huge payoff by reducing the number of collision detections you need to do by 1/4 (or more)