# Collision detection question...

21 replies to this topic

### #1 PacManPlusOFFLINE

PacManPlus

River Patroller

• 4,312 posts
• Atari 7800 Developer
• Location:Florida

Posted Thu Dec 30, 2010 6:39 AM

Hello all:

Does anyone have a good algorithm (that applies to the 7800) to check collision between a 'ball' sprite and a background character (tile)? I'm trying to come up with one, as the major problem is I also need to know *where* the ball hit the tile (i.e. the left side, right side, top, or bottom). Sometimes the ball moves pretty fast so by the time I get to check there may be a false reading of the ball having a 'top' and 'left' collision (for example) when in all actuality it's the same tile and not two different ones. (The ball is so deep in the tile from moving fast that the top of it *and* the side are in the same tile).

Bob

### #2 kenfusedOFFLINE

kenfused

Stargunner

• 1,313 posts
• Location:Columbus, Ohio

Posted Thu Dec 30, 2010 7:12 PM

Hello all:

Does anyone have a good algorithm (that applies to the 7800) to check collision between a 'ball' sprite and a background character (tile)? I'm trying to come up with one, as the major problem is I also need to know *where* the ball hit the tile (i.e. the left side, right side, top, or bottom). Sometimes the ball moves pretty fast so by the time I get to check there may be a false reading of the ball having a 'top' and 'left' collision (for example) when in all actuality it's the same tile and not two different ones. (The ball is so deep in the tile from moving fast that the top of it *and* the side are in the same tile).

Bob

Is knowing if it is closer to the top or closer to the left good enough? If not, maybe the position of the ball last checked or the vertical and horizontal speed could be used?

### #3 Harry_DodgsonOFFLINE

Harry_Dodgson

Moonsweeper

• 405 posts
• Location:SE Michigan, USA, Earth

Posted Fri Dec 31, 2010 9:39 AM

Hello all:

Does anyone have a good algorithm (that applies to the 7800) to check collision between a 'ball' sprite and a background character (tile)? I'm trying to come up with one, as the major problem is I also need to know *where* the ball hit the tile (i.e. the left side, right side, top, or bottom). Sometimes the ball moves pretty fast so by the time I get to check there may be a false reading of the ball having a 'top' and 'left' collision (for example) when in all actuality it's the same tile and not two different ones. (The ball is so deep in the tile from moving fast that the top of it *and* the side are in the same tile).

Bob

Is knowing if it is closer to the top or closer to the left good enough? If not, maybe the position of the ball last checked or the vertical and horizontal speed could be used?

When you get a collision, see which direction the ball is heading to help determine where it hit first. You may need to back it up a fraction as well.

### #4 EricBallOFFLINE

EricBall

Dragonstomper

• 774 posts

Posted Sat Jan 1, 2011 8:58 AM

If the ball is moving more than 1 pixel per frame, but less than one tile per frame, then you first do a simple bounding box to see if the ball is inside the tile. Then you do a line intersection between the line the ball is moving along and each of the tile's sides.

### #5 PacManPlusOFFLINE

PacManPlus

River Patroller

• Topic Starter
• 4,312 posts
• Atari 7800 Developer
• Location:Florida

Posted Sat Jan 1, 2011 5:07 PM

Thanks Guys:

Your advice reaffirmed me to go back to what I started with. It originally didn't work, but this time it's much better. I know there are still a few places to fix, but the majority of the ball/playfield collisions are ok.

(See attachment)

Unfortunately, this speed is the fastest the ball can go without beginning to move through walls, etc. So there is some more to figure out. As it is, I've still seen it go through a wall once or twice

This is going to be a pinball/breakout hybrid. As you can see from the attachment, I started with the BombBee playfield - but that's just to test with. This playfield will not be in the final product. It's going to be along the same lines of BombBee/GeeBee/CutieQ, but with some functional differences. Also, I plan on holding a playfield design contest because I want 32 different screens to advance to.

The paddles do work (on the real thing), but there is no paddle/ball detection yet.

I figure I should get the 'paddle' games out of my system.

### #6 PacManPlusOFFLINE

PacManPlus

River Patroller

• Topic Starter
• 4,312 posts
• Atari 7800 Developer
• Location:Florida

Posted Mon Jan 3, 2011 7:08 PM

I think I got it, although the ball cannot move faster that 2 pixels horizontally - due to the 'top' of the ball being in the same character. Problem is (for example) if the ball is moving at a velocity of 3 pixels horizontally to the right and 2 pixels horizontally up, the ball *could* (and has) been 3 pixels deep in a vertical wall - making the 'top' of the ball inside the same wall. Now, being that the ball is moving 'right' and 'up' they are both valid positions, so it acts on both directions, sending the ball back in the direction it came instead of just negating the 'x' velocity.

Also,

Attached is the fastest speed currently the ball can travel. Let me know if you see any 'abnormal' behaviour.

Thanks,
Bob

### #7 PacManPlusOFFLINE

PacManPlus

River Patroller

• Topic Starter
• 4,312 posts
• Atari 7800 Developer
• Location:Florida

Posted Thu Jan 6, 2011 7:30 AM

YES

I changed to 320B mode, and the collision detection is *much* better.

Now I just have to deal with Kangaroo mode, and the fact that when transparency is on, you lose the third color.

...looks better too:

Bob

### #8 Propane13OFFLINE

Propane13

Stargunner

• 1,525 posts
• Location:Charleston, SC

Posted Thu Jan 6, 2011 10:17 AM

Looks good!

Is there a tutorial on how to code for paddles?

That may be an easy way for me to get back into Arkanoid.

-John

### #9 Propane13OFFLINE

Propane13

Stargunner

• 1,525 posts
• Location:Charleston, SC

Posted Thu Jan 6, 2011 10:42 AM

Oh, btw, I saw the same thing in Arkanoid.
Eventually, yes, you end up with a speed limitation.
If you demo Arkanoid, and just let it go faster and faster, eventually, it gets into weird states where it can't do collision detection well, and the ball may either miss tiles or do some weird things.

I tried getting around it by keeping track of the ball direction, and hit 2 routines based on that.
So, for example, if going up and left, I would do the left collision check, followed by the up collision check.
When going up and left, I would check the up-left pixel and see if it hit on my grid.
I'd check all of the positions along the top, and all along the side.
If memory serves, it's a 3x5 ball, so I checked 7 places. If there was a hit, it would stop checking, and rotate velocity accordingly.

I can dive in and share some source code if you're interested.
Note that it wasn't perfect-- there was a bug somewhere in there, but I didn't figure it out before putting that project on hiatus.

-John

### #10 DracIsBackOFFLINE

DracIsBack

River Patroller

• 4,725 posts

Posted Thu Jan 6, 2011 11:46 AM

YES

I changed to 320B mode, and the collision detection is *much* better.

Now I just have to deal with Kangaroo mode, and the fact that when transparency is on, you lose the third color.

...looks better too:

Bob

Any chance there is a BIN? Looks cool! :-)

### #11 MordOFFLINE

Mord

River Patroller

• 2,001 posts

Posted Thu Jan 6, 2011 2:00 PM

Oh, btw, I saw the same thing in Arkanoid.
Eventually, yes, you end up with a speed limitation.
If you demo Arkanoid, and just let it go faster and faster, eventually, it gets into weird states where it can't do collision detection well, and the ball may either miss tiles or do some weird things.

Would trying to include a "phantom ball" slightly ahead of the real ball help with collision detection when going really fast? The phantom not actually being displayed, just it's coordinates being used to calculate a potential collision to react on (Since if you waited until the next frame, the real ball would be past the current phantom's position and probably too far into the block to accurately detect a proper collision.

No idea if it'd work or not as I haven't tried it before. Just a random thought.

### #12 gambler172OFFLINE

gambler172

River Patroller

• 2,782 posts
• none
• Location:germany

Posted Thu Jan 6, 2011 2:31 PM

Hi Bob
Wow a pinball.....But i would prefer joystick.
greetings Walter

### #13 PacManPlusOFFLINE

PacManPlus

River Patroller

• Topic Starter
• 4,312 posts
• Atari 7800 Developer
• Location:Florida

Posted Thu Jan 6, 2011 4:43 PM

Hi Guys:

John - here is the paddle code *ONLY WORKS IN DLIs* I tried moving it, got a blank screen

BIG Thanks to DEBRO for giving me this code...

```DLITOP
LDA     #\$00
STA     DLITEMP                 ;THIS IS THE LINE COUNTER THAT'S USED TO FIGURE OUT WHAT ZONE WE ARE IN
LDA     #\$01
STA     DLIFLG                  ;THIS JUST TELLS THE NEXT DLI THAT WE ARE AT THE BOTTOM
LDA     #\$00
STA     INPTCTRL                ;THIS NEEDS TO BE DONE TO START THE PADDLE DISCHARGE

LDY     #73                     ;THE NUMBER OF RASTERS I NEED FOR FULL RANGE OF PADDLE MOVEMENT (YOUR MILEAGE MAY VARY)
DLIPLOOP
STA     WSYNC                   ;ENSURE THE BEGINNING OF A LINE
BMI     DLISKIP0                ;PADDLE NOT BEING USED - SKIP
STY     OUTP0                   ;SAVE CURRENT RESISTANCE
DLISKIP0
BMI     DLISKIP1                ;PADDLE NOT BEING USED - SKIP
STY     OUTP1                   ;SAVE CURRENT RESISTANCE
DLISKIP1
LDA     DLITEMP                 ;GET CURRENT RASTER
LSR                             ;DIVIDE BY 4 TO GET CURRENT ZONE (I THINK THE ABOVE PADDLE ROUTINE TAKES 4 LINES)
LSR
TAX
LDA     ZONCOLOR,X              ;GET THE COLOR FOR THIS ZONE
STA     Z0C3                    ;UPDATE IT
INC     DLITEMP                 ;INCREMENT THE RASTER COUNT
DEY                             ;DECREMENT THE PADDLE DISCHARGE COUNT
BNE     DLIPLOOP                ;DO IT ALL AGAIN.
```
My DLL is set up with one interrupt at the top (for the above code) and one at the bottom (to do VBlank stuff).

I think at this point the collision detection is where I want it.

Thanks guys for the compliments and the advice.

@Walter - I may add joystick support later on.

Here's the .a78 and bin, now with paddle collision detection (only the top paddle though, as I still have the ball rebounding from the bottom of the screen).

Still not sure what I'm going to do about the 'Kangaroo' issue though...

Bob

### #14 DracIsBackOFFLINE

DracIsBack

River Patroller

• 4,725 posts

Posted Sat Jan 8, 2011 6:34 PM

Thanks for the BIN. Game definitely has a neat look to it! Nice to see you coding again, PacManPlus

River Patroller

• 4,337 posts
• Location:Portland, Oregon

Posted Sat Jan 8, 2011 8:21 PM

I like the look a lot.

### #16 PacManPlusOFFLINE

PacManPlus

River Patroller

• Topic Starter
• 4,312 posts
• Atari 7800 Developer
• Location:Florida

Posted Sun Jan 9, 2011 5:58 PM

Pretty soon I will move this to the appropriate place in the 7800 forum, but I want to do the following first:
- Animation of the bumpers and spinners
- points for spinners
- ball seems to get 'stuck' a lot
- hitting all 'bonus' lights incrementing a multiplier

Here are a few more screenshots for now:

Thanks again... I know I'm not doing the great work that GroovyBee is doing, but I'm doing what I'm capable of.
Bob

River Patroller

• 4,337 posts
• Location:Portland, Oregon

Posted Sun Jan 9, 2011 8:05 PM

Better than I can do! And it really does look good. Don't beat yourself up on that stuff.

I'm kind of fixated on the more square pixel look, and your game, fonts, etc... has it! I gotta get a good 7800 to play on again. Doing paddle games is really great! They are my favorites.

Are you gonna leave the paddles white?

Edited by potatohead, Sun Jan 9, 2011 8:06 PM.

### #18 LendorienOFFLINE

Lendorien

Stargunner

• 1,136 posts
• Location:Milwaukee, Wisconsin

Posted Mon Jan 10, 2011 10:10 AM

Thanks again... I know I'm not doing the great work that GroovyBee is doing, but I'm doing what I'm capable of.
Bob

Good Gravy!

Don't denigrate yourself! You've released some great stuff and your contributing more to the 7800 homebrew scene than almost everyone else short of a couple people. Believe you me, you're up there int the pantheon of 7800 gods.

I have to say that this pinball/breakout hibred thing really looks to be a neat idea. I'm really looking forward to seeing what the end product is like.

Edited by Lendorien, Mon Jan 10, 2011 10:10 AM.

### #19 gambler172OFFLINE

gambler172

River Patroller

• 2,782 posts
• none
• Location:germany

Posted Mon Jan 10, 2011 12:57 PM

Hi Bob
You do really great work.And a pinball for the 7800 was missing......
greetings Walter

### #20 PacManPlusOFFLINE

PacManPlus

River Patroller

• Topic Starter
• 4,312 posts
• Atari 7800 Developer
• Location:Florida

Posted Fri Jan 14, 2011 11:43 AM

Thank guys

I've made quite a bit of progress on this, but the only area I'm having an issue with is ball movement. It was getting stuck *quite a bit* and I'm trying to find good angles and speed increases. If I can get past this, I only need to create the playfields. Like I stated before, I plan on having 32 playfields. Not sure yet if they will be random or played straight through.

Wish I could find a good table of x and y ball movements (including rebounds and the like). It seems silly to 'reinvent the wheel' as I'm sure this was already done somewhere.

Thanks,
Bob

### #21 GroovyBeeOFFLINE

GroovyBee

Games Developer

• 8,467 posts
• Busy bee!
• Location:North, England

Posted Fri Jan 14, 2011 11:55 AM

I've made quite a bit of progress on this, but the only area I'm having an issue with is ball movement. It was getting stuck *quite a bit* and I'm trying to find good angles and speed increases.

Can you explain the algorithm/logic you've come up with for movement/hit detection so far?

### #22 PacManPlusOFFLINE

PacManPlus

River Patroller

• Topic Starter
• 4,312 posts
• Atari 7800 Developer
• Location:Florida

Posted Fri Jan 14, 2011 12:29 PM

Sure!

I'll break this up into two parts: collision and ball properties

For collision, I have a table of each tile, and what to do if the ball hits the top, left, right and bottom of each tile. Please note that there are only 128 tiles (not 256) because I'm using 320B mode with two-byte character mode which only leaves me with half the normal number of characters:

```;  THESE ARE THE TABLES FOR WHAT TO DO WHEN THE BALL HITS A CERTAIN CHARACTER FROM EACH SIDE (UP,RIGHT,LEFT,DOWN)
;  THE OPTIONS ARE AS FOLLOWS:
;  MAKE Y NEGATIVE (PAIED WITH BIT 1 BELOW)
;  |MAKE X NEGATIVE (PAIRED WITH BIT 0 BELOW)
;  ||ANIMATE CHARACTER (I.E. BUMPER) (NEED CHARACTER)
;  |||CLEAR CHARACTER BALL HIT (NEED CHARACTER)
;  |||||SWAP X AND Y VALUES (BOUNCE ON A 45 DEGREE ANGLE)
;  ||||||MAKE Y POSITIVE
;  |||||||MAKE X POSITIVE
;  ||||||||
;  XXXXXXXX```

ACTBALLL
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000

.byte %11101100,%10101000,%10101001,%01101000,%00101000,%00101001,%01101110,%00101010,%00101011
.byte %01101000,%00101000,%00101001,%01101000,%00101000,%00101001
.byte %00001000,%01011000,%01011000,%01011000,%00001000,%00001000
.byte %01000000,%01000000,%11000100,%01000000,%01000110,%00000000,%01000000,%01000000
.byte %01000000,%01000000,%01000110,%11000100,%01000000,%01000000,%01000000,%01000000

.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000
.byte %00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000
.byte %00011000,%00011000,%00011000,%00011000,%00101000,%00101000
ACTBALLR
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000

.byte %11101100,%10101000,%10101001,%01101000,%00101000,%00101001,%01101110,%00101010,%00101011
.byte %01101000,%00101000,%00101001,%01101000,%00101000,%00101001
.byte %00001000,%00011001,%00011001,%00011001,%00001000,%00001000
.byte %00000001,%10000101,%00000001,%00000111,%00000001,%00000000,%00000001,%00000001
.byte %00000001,%00000001,%00000111,%00000001,%00000001,%00000001,%00000001,%00000001

.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000
.byte %00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000
.byte %00011000,%00011000,%00011000,%00011000,%00101000,%00101000
ACTBALLT
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000

.byte %11101100,%10101000,%10101001,%01101000,%00101000,%00101001,%01101110,%00101010,%00101011
.byte %01101000,%00101000,%00101001,%01101000,%00101000,%00101001
.byte %00001000,%10011000,%10011000,%10011000,%00001000,%00001000
.byte %10000000,%10000101,%11000100,%10000000,%10000000,%00000000,%10000000,%10000000
.byte %01000110,%11000100,%10000000,%10000000,%10000000,%10000000,%10000000,%10000000

.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000
.byte %00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000
.byte %00011000,%00011000,%00011000,%00011000,%00101000,%00101000
ACTBALLB
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00000000,%00000000,%00000000

.byte %11101100,%10101000,%10101001,%01101000,%00101000,%00101001,%01101110,%00101010,%00101011
.byte %01101000,%00101000,%00101001,%01101000,%00101000,%00101001
.byte %00001000,%00011010,%00011010,%00011010,%00001000,%00001000
.byte %00000010,%00000010,%00000010,%00000111,%01000110,%00000000,%00000010,%00000010
.byte %00000111,%01000110,%00000010,%00000010,%00000010,%00000010,%00000010,%00000010

.byte %00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000,%00000000
.byte %00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000
.byte %00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000,%00011000
.byte %00011000,%00011000,%00011000,%00011000,%00101000,%00101000

Here is the Character map that goes with the above table:

Now, regarding ball movement, what I *did* have until today was a routine to take each bit from the table above and act on it:
```CHGBSWAP
LDA     TEMP6                   ;THE VALUE FROM THE TABLE ABOVE
AND     #\$04                    ;ARE WE SWAPPING VALUES?
BEQ     CHGBNEGX                ;NOPE, SKIP
LDA     BALLYDIR,X              ;YES
PHA
LDA     BALLXDIR,X
STA     BALLYDIR,X
PLA
STA     BALLXDIR,X
CHGBNEGX
LDA     TEMP6
AND     #\$40                    ;MAKE X NEGATIVE?
BEQ     CHGBNEGY                ;NOPE, SKIP
LDA     BALLXDIR,X
BMI     CHGBNEGY                ;X IS ALREADY NEGATIVE
EOR     #\$FF
CLC
STA     BALLXDIR,X
CHGBNEGY
LDA     TEMP6
AND     #\$80                    ;MAKE Y NEGATIVE?
BEQ     CHGBPOSX                ;NOPE, SKIP
LDA     BALLYDIR,X
BMI     CHGBPOSX                ;Y IS ALREADY NEGATIVE
EOR     #\$FF
CLC
STA     BALLYDIR,X
CHGBPOSX
LDA     TEMP6
AND     #\$01                    ;MAKE X POSITIVE?
BEQ     CHGBPOSY                ;NOPE, SKIP
LDA     BALLXDIR,X
BPL     CHGBPOSY                ;X IS ALREADY POSITIVE
EOR     #\$FF
CLC
STA     BALLXDIR,X
CHGBPOSY
LDA     TEMP6
AND     #\$02                    ;MAKE Y POSITIVE?
BEQ     CHGBPOINT               ;NOPE, SKIP
LDA     BALLYDIR,X
BPL     CHGBPOINT               ;Y IS ALREADY POSITIVE
EOR     #\$FF
CLC
STA     BALLYDIR,X
```

I had three variables to work with as far as these went: X Direction, Y Direction, and FrameSkip (the number of frames to skip before moving the ball).

What I am doing today and I am in the middle of, is trying to create a table of ball movements, and just read from that table. I have split the 'FrameSkip' into separate X and Y values. Being that the 'X' value can't really go past 2 pixels per movement (in either direction) before causing problems - (because the X direction already moves in 2-pixel increments in 320 mode), I have to play with the \$FE,\$FF,\$01,\$02 values, along with the FrameSkipX value to get different ball movements. In the Y direction, I can use up to 3 pixels per movement before causing issues. This leaves \$FD,\$FE,\$FF,\$01,\$02,\$03 and the FrameSkipY values to get different ball movements. And I have to swap / negate all of these directions as well.

Just trying to find the correct algorithm.

Thanks,
Bob

EDIT - crap - the 'code' tag removed the percent signs...

Edited by PacManPlus, Fri Jan 14, 2011 12:35 PM.

#### 0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users