## Strategies for collisions with background

Moderator: BigEvilCorporation

tryphon
Very interested
Posts: 316
Joined: Sat Aug 17, 2013 9:38 pm
Location: France

### Strategies for collisions with background

I'm trying to figure out a clever way of checking collision between a sprite and background.

It's different from checking if two sprites are collidong : each sprite has a bounding box, I just have to check that they don't overlap.

For the background, I have a 2D array that follows the tilemap of the level. To make it simple let's say they are 1 if the tile is solid, 0 if not.

Let's say the collision array is like that

Code: Select all

0000000000
1100000011
1111111111
Each value represents a 16x16 tile.

If the player is at pos (120, 16) and is 10 pixels wide. Does it fall ?
If compute its coordinates in tile units : it goes from 120/16 = 7 to 129/16 = 8. Collision value at position (7, 1) is 0 but at position (8, 1) it's 1 : there's collision and the sprite doesn't fall.

What bothers me is that it's slow : I have to do these calculations for the 4 edges of the bounding box (actually, according to horizontal and vertical movement, only 2 are necessary), for all the sprites. And if the sprite is 32 pixels long, I have twice more values to read.

I was wondering if game developpers from the 8/16bits years had developped some clever technique ?

For example, I was thinking about using a table where free tiles would be associated to values representing the space before the first obstacle in each 4 directions, so that only one value should be read for a given sprite (at the cost of more calculations), I don't know if it's worth implementing.

Or is it better to store the collisions with background using bounding boxes, like for sprites, and using quadtrees ?

I'd be much interested with concrete examples of game that actually implemented such or such methods.

r57shell
Very interested
Posts: 478
Joined: Sun Dec 23, 2012 1:30 pm
Location: Russia
Contact:

### Re: Strategies for collisions with background

It's not slow. Just count in cycles of M68k
Maximum that you can do is... precalculate all that data into single array.

greatkreator
Very interested
Posts: 154
Joined: Sat May 12, 2012 7:37 pm
Location: Ukraine

### Re: Strategies for collisions with background

The simplest way to have obstacle bit-map.
Shift position coordinates of sprite for example >>3 or >>4 (depending on what background cell size you have) and get cell of the obstacle map.
Something more "clever" will be more context-dependent.
If you would like to have something flexible and "general" then it's the most common option.

BigEvilCorporation
Very interested
Posts: 209
Joined: Sat Sep 08, 2012 10:41 am
Contact:

### Re: Strategies for collisions with background

My implementation for Tanglewood is loosely based on Sonic's, see here: http://info.sonicretro.org/SPG:Solid_Tiles

The terrain is defined in an 8x8 tile-based system, pretty much like graphics tiles, with each tile consisting of 8 height values ranging from -8 to 8 (a positive value means a floor from the bottom upward, and negative value means a ceiling from top down):

Each sprite has one or more probe positions defined. On every update for the sprite, each probe is tested to see if it falls inside a valid terrain tile (testing all tiles between current position to position+velocity), and if it does the height of its X value is tested to get the total height of the floor or ceiling.

Solid (wall) tiles follow the same formula, but for simplicity and speed's sake the whole 8x8 tile is either solid, or it isn't, which is specified in a flag (top few bits) in the terrain tile ID. I could probably do the same for ceilings, since I don't really need it to be pixel perfect, which would allow me to compact the floor data a bit better.

tryphon
Very interested
Posts: 316
Joined: Sat Aug 17, 2013 9:38 pm
Location: France

### Re: Strategies for collisions with background

Thanks for the answer. I think it's equivalent to what I do (unless you use probe points more than ont tile far, but in this case your method can introduce bugs).
r57shell wrote:It's not slow. Just count in cycles of M68k
Maximum that you can do is... precalculate all that data into single array.
I'm not sure to understand... What to precalculate ?

r57shell
Very interested
Posts: 478
Joined: Sun Dec 23, 2012 1:30 pm
Location: Russia
Contact:

### Re: Strategies for collisions with background

tryphon wrote:I'm not sure to understand... What to precalculate ?
Let say we have function

Code: Select all

T getPlayerCollision(int x, int y)
It returns value of type T, representing collision type/data.
It answers to question: "what kind of collision is for player if player located at position x, y?"
It may use loops inside, going "over" several tiles, pixels etc...
If it depends only on map layout, and does not depend on player state, then
values of x, y is enough to definitely say what collision is, thus
we can do precalc:

Code: Select all

T player_coll[MAX_X-MIN_X][MAX_Y-MIN_Y]
for (int x=MIN_X; x < MAX_X; ++x)
for (int y=MIN_Y; y< MAX_Y; ++y)
player_coll[x-MIN_X][y-MIN_Y] = getPlayerCollision(x,y);
and then use player_coll[x-MIN_X][y-MIN_Y] to get actual collision data.
Ofcourse you can use tiling techniques here as well.

tryphon
Very interested
Posts: 316
Joined: Sat Aug 17, 2013 9:38 pm
Location: France