Strategies for collisions with background

Ask anything your want about Megadrive/Genesis programming.

Moderator: BigEvilCorporation

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

Strategies for collisions with background

Post by tryphon » Mon Mar 21, 2016 1:48 pm

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.

Thanks in advance for sharing your knowledge :)

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

Re: Strategies for collisions with background

Post by r57shell » Mon Mar 21, 2016 3:15 pm

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

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

Re: Strategies for collisions with background

Post by greatkreator » Tue Mar 22, 2016 1:03 am

The simplest way to have obstacle bit-map.
0 for free space and 1 for obstacle.
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

Post by BigEvilCorporation » Tue Mar 22, 2016 3:29 pm

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

Image

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.

More info here: viewtopic.php?f=7&t=2259
A blog of my Megadrive programming adventures: http://www.bigevilcorporation.co.uk

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

Re: Strategies for collisions with background

Post by tryphon » Wed Mar 23, 2016 7:23 pm

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

Post by r57shell » Thu Mar 24, 2016 9:29 am

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

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

Re: Strategies for collisions with background

Post by tryphon » Thu Mar 24, 2016 10:36 am

That's what I had understood.

The problem with doing that is that x and y must be pixel-based, which will result in really huge arrays, and that for a given level, arrays will be different according to the size of the bounding box. So I'll end up with several huge arrays for oonly one level...

MintyTheCat
Very interested
Posts: 484
Joined: Sat Mar 05, 2011 11:11 pm
Location: Berlin, Germany

Re: Strategies for collisions with background

Post by MintyTheCat » Fri Mar 25, 2016 10:30 am

There is no need to scan the entire plane. Simply maintain a list of locals around active objects. Do collisions at the tile scale then if you get a collision determine at the pixel level.
UMDK Fanboy

Post Reply