Accurate collision detection with tile block background

The place for codemasters or beginners to talk about programming any language for the Spectrum.
Post Reply
dwinters18
Berk
Posts: 20
Joined: Sat Dec 01, 2018 6:45 pm

Accurate collision detection with tile block background

Post by dwinters18 » Sun Dec 09, 2018 2:44 am

Hello,

If I have a game screen made up of 16x16 tiles, and using 16x16 sprites (that are actually 24x16 as each sprite has four pre-shifted frames) - what is the most accurate way of doing collision detection (for example as seen in this URL - https://goo.gl/images/j2dq5z )

So as the sprite is using pre-shift frames then at some point I would need to check two map blocks below as opposed to just one other wise the sprite could appear to fall through a platform for example - i'm not quite sure of best way to go about it.

Any help at all appreciated.

D
0 x

Ralf
Dynamite Dan
Posts: 1304
Joined: Mon Nov 13, 2017 11:59 am
Location: Poland

Re: Accurate collision detection with tile block background

Post by Ralf » Sun Dec 09, 2018 10:50 am

I would say most accurate colision detectionwould be pixel perfect detection. You check if any of the sprite pixels overlap any tile pixel. In some cases it's easier than you would think, see later in this post :)

Another standard detection is "rectangle based detection". There are two objects, they have their positions, they have their width and height which makes a rectangle and you check if their rectangles overlap. It's quite easy when it comes to calculations so it's widely used but may be less precise, especially in case of oval and more complicated shapes:

The balls don't collide but their rectangles do, false colision detection:
Image

Going back to pixel pefect method, it could be really complicated but I know the trick with XOR operation:

1. Draw sprite using OR merging with background
2. Draw the same sprite at the same place using XOR merging with background
3. Compare results. If there is some overlap, even by a single pixel, then there will be difference between OR and XOR result:

Image

Hope it was helpful.
1 x

dwinters18
Berk
Posts: 20
Joined: Sat Dec 01, 2018 6:45 pm

Re: Accurate collision detection with tile block background

Post by dwinters18 » Sun Dec 09, 2018 11:10 am

Thanks for that information.

Do you have any similar suggestions for map tile blocks that form the play area, as your advice seems to be for sprite to sprite which is great thank you as info I didn't know so always helpful!

D
0 x

User avatar
R-Tape
Site Admin
Posts: 2579
Joined: Thu Nov 09, 2017 11:46 am

Re: Accurate collision detection with tile block background

Post by R-Tape » Sun Dec 09, 2018 1:08 pm

dwinters18 wrote:
Sun Dec 09, 2018 2:44 am
Hello,

If I have a game screen made up of 16x16 tiles, and using 16x16 sprites (that are actually 24x16 as each sprite has four pre-shifted frames) - what is the most accurate way of doing collision detection (for example as seen in this URL - https://goo.gl/images/j2dq5z )

So as the sprite is using pre-shift frames then at some point I would need to check two map blocks below as opposed to just one other wise the sprite could appear to fall through a platform for example - i'm not quite sure of best way to go about it.

Any help at all appreciated.

D
Are you using ASM or C? (your link is to a churrera game).

I used to hate doing block collision detection—it took me ages to get it right!

It depends how you're doing your sprites. If it's something like this, then you will always have the xy coordinate of the top left corner of the sprite (regardless of how many chars it occupies). You can use that to convert to its position in a block map. The sprite can straddle two tiles at a time, so you need to check below left, and below right.

Image

Check underneath left: get XY, add 16 to Y, see if it's a solid of empty block (e.g. block #0 is empty, 1 is solid)
Check underneath right: get XY, add 16 to Y, add 15 to X, check block.

If both are block 0, the sprite can fall. Similar for left/right/up, check two positions with a given displacement.

Is it the principle, or code examples you're after?
0 x

dwinters18
Berk
Posts: 20
Joined: Sat Dec 01, 2018 6:45 pm

Re: Accurate collision detection with tile block background

Post by dwinters18 » Sun Dec 09, 2018 1:13 pm

Hi,

Thanks for that. Makes sense - it was the principal I was after which you have provided thank you. I was overlooking the obvious!

D
0 x

User avatar
R-Tape
Site Admin
Posts: 2579
Joined: Thu Nov 09, 2017 11:46 am

Re: Accurate collision detection with tile block background

Post by R-Tape » Sun Dec 09, 2018 1:24 pm

Cool. BTW I fixed an important typo, it should be add 15 to X.
0 x

dwinters18
Berk
Posts: 20
Joined: Sat Dec 01, 2018 6:45 pm

Re: Accurate collision detection with tile block background

Post by dwinters18 » Sun Dec 09, 2018 1:26 pm

Ok great thanks.

I am using pre-shifted sprites as per (i think!) that tutorial you linked to, so I presume your method works for that?

D
0 x

User avatar
R-Tape
Site Admin
Posts: 2579
Joined: Thu Nov 09, 2017 11:46 am

Re: Accurate collision detection with tile block background

Post by R-Tape » Sun Dec 09, 2018 1:41 pm

dwinters18 wrote:
Sun Dec 09, 2018 1:26 pm
I am using pre-shifted sprites as per (i think!) that tutorial you linked to, so I presume your method works for that?
Yep, but it's not exclusive to that. As long as you're keeping track of the xy of the visible bits of the 3 character wide sprite somehow, you have a reference for its position in a map.
0 x

Joefish
Manic Miner
Posts: 634
Joined: Tue Nov 14, 2017 10:26 am

Re: Accurate collision detection with tile block background

Post by Joefish » Sun Dec 09, 2018 4:39 pm

As an example, for falling between blocks, you can take the X pixel co-ordinate of your sprite's top-left corner, round it down to the nearest 16-pixel block position (divide it by 16, bit-shift it right four times, or simply AND 0xF0) then check the block below for solidity.
Then take the X pixel co-ordinate of your sprite again, add 15 (for the right-hand edge of your sprite), then round that number down and do the same check for a solid block below.
That way, if your sprite spans two blocks, you end up checking both of them. If it's exactly centred over one block, you just end up checking the same block twice.

The same goes for left/right movement - check the top edge of your sprite for collision, then the bottom edge, when moving left or right.
Or, for simplicity, you could just check the bottom two corners of your sprite; where your sprite's feet are going. This gives you the sort of collision detection you get in Bubble Bobble, where you can run past and jump up through overhead blocks, but you can't walk through a solid vertical wall. It's a neat model if you only have one block type in a platform game, rather than Manic Miner's distinct solid walls and soft platforms.

If you're using two-pixel pre-shifting, then maybe you're working with a 128x96 screen co-ordinate system instead of 256x192. In which case just halve all the numbers I just said.
0 x

Post Reply