Page 1 of 2
How do I come about collision detection?
Posted: Wed Nov 13, 2013 4:20 am
by darkhog
How to write collision detection for player, bullets, etc.?
Re: How do I come about collision detection?
Posted: Wed Nov 13, 2013 5:01 am
by Bregalad
Code: Select all
x_collision = ( object1_xmin < object2_xmax ) && ( object1_xmax > object2_xmin)
y_collision = ( object1_ymin < object2_ymax) && ( object2_ymax > object2_ymin)
collision = x_collision && y_collision
Re: How do I come about collision detection?
Posted: Wed Nov 13, 2013 7:35 am
by tokumaru
Object x object collision uses the formula Bregalad posted. You have to keep track of the four edges (top, bottom, left and right) of your objects and compare them according to that formula. The basic idea is to make sure that the conditions that make a collision impossible aren't met. For example: if the right side of object 1 is smaller than the left side of object 2, they can't possibly be touching each other (draw it on paper and you'll understand). Small objects (such as bullets) can probably be just a point.
Collisions between objects and the level map are different. If moving right, you have to check all the background blocks from the top right to the bottom right of the object (you'll have to convert object coordinates to map coordinates - if you're not scrolling, this can be as simple as dividing them by 16 or 8), to make sure that the character is allowed to move to that position. If it isn't, you have to push it back.
Re: How do I come about collision detection?
Posted: Wed Nov 13, 2013 8:55 am
by tepples
Round object collision, such as whether an explosion is touching something, is almost as easy. Once you know the objects' rectangles overlap, subtract x2-x1 and y2-y1, take their absolute value, use a lookup table to square them (.byte 0, 1, 4, 9, 16, ...), and compare this to the square of the sum of the radii. For example, an object 8 units across and an object 16 units across will have a collision radius of 8/2 + 16/2 = 12 units, so you're checking whether (x2 - x1)^2 + (y2 - y1)^2 < 144.
Another problem comes with what direction to push an object if it is moving diagonally, or if a block has appeared behind the object. I posted a fairly general solution to this problem in
another topic.
Re: How do I come about collision detection?
Posted: Wed Nov 13, 2013 9:04 am
by Shiru
Rect collision should test is the rects are not intersect, rather than is they intersect. It is faster. Like, if (x1+width1)<x2, you already know that there is no collision, and can skip all further checks.
Re: How do I come about collision detection?
Posted: Wed Nov 13, 2013 3:12 pm
by qbradq
Before you get to object to object collision detection you really need to think about limiting the scope of collision detection. CPU cycles are at a premium on the NES, and you really can't afford to test every object against every other object every frame at 60 FPS. Instead you need to use object groups.
For instance, in a Contra-esque game, you might track the players, the player bullets, the enemies and the enemy bullets. Then your collision comparisons would only look at collisions between players and enemy bullets, and between enemies and player bullets, and between enemies and players. This significantly reduces the number of rect overlap calculations you have to do.
Furthermore, depending on the requirements of the project, you may need to move to an interleaved collision system. Example: on odd frames you calculate player bullets to enemy collisions, and on even frames you calculate enemy and enemy bullets to player collisions.
It's amazing how much of the CPU time gets spent updating positions and checking for collisions in your typical sidescroller. One way to reduce the CPU overhead is to limit one of your axis to an 8-bit value (like the Y value in SMB1, for instance). Reducing the number of 16-bit calculations will speed things up a bit.
Re: How do I come about collision detection?
Posted: Wed Nov 13, 2013 3:16 pm
by tepples
qbradq wrote:Furthermore, depending on the requirements of the project, you may need to move to an interleaved collision system. Example: on odd frames you calculate player bullets to enemy collisions, and on even frames you calculate enemy and enemy bullets to player collisions.
Thwaite does this. Collisions between a missile and an explosion are processed in even frames for even numbered explosions and odd frames for odd numbered explosions.
Re: How do I come about collision detection?
Posted: Wed Nov 13, 2013 4:57 pm
by Drag
To expand on what Shiru posted:
You have two objects: A and B. A and B have four values; the X position of the left edge, X of right edge, Y of top edge, Y of bottom edge.
Code: Select all
if A.right < B.left then goto NO_COLLISION
if A.left > B.right then goto NO_COLLISION
if A.bottom < B.top then goto NO_COLLISION
if A.top > B.bottom then goto NO_COLLISION
; If you get here, then a collision is taking place between A and B.
end
NO_COLLISION:
; If you get here, no collision is taking place.
end
What this code does is check for the possibilities that tell you there's no way a collision could take place. For instance, if the left edge of one is farther right than the right edge of the other, then you know a collision can't be taking place, and you don't need to check anything else.
Re: How do I come about collision detection?
Posted: Wed Nov 13, 2013 6:32 pm
by darkhog
Ok, now harder question: Collisions with background. Mario does collisions with blocks and ground, but not e.g. with bushes or clouds. All those are part of the background. How SMB differentiates between those?
Re: How do I come about collision detection?
Posted: Wed Nov 13, 2013 6:56 pm
by tepples
In general: When you decode your maps, you'll have to decide which tile numbers are passable and which aren't.
Specifically, SMB1 breaks metatiles into four groups depending on how they're colored in the attribute table: $00-$3F, $40-$7F, $80-$BF, and $C0-$FF. If I recall correctly, each group has a threshold: lower numbers are solid and higher numbers are passable.
Re: How do I come about collision detection?
Posted: Wed Nov 13, 2013 8:30 pm
by tokumaru
darkhog wrote:Mario does collisions with blocks and ground, but not e.g. with bushes or clouds. All those are part of the background.
The visual representation of a block should not be directly tied to its physical attributes. Most games use the concept of metatiles, blocks that are composed of several tiles (in most cases 4, arranged in a grid of 2x2), that in addition to the indices of the tiles have other attributes, like a palette index, a "type" code (solid, water, hazard, empty, etc.), a height map (for slopes), and so on. For drawing them you read their tiles and palette index in order to write to the name and attribute tables, while for collisions/physics you check their type, height maps, and so on.
Re: How do I come about collision detection?
Posted: Thu Nov 14, 2013 3:10 pm
by Bregalad
Before you get to object to object collision detection you really need to think about limiting the scope of collision detection. CPU cycles are at a premium on the NES, and you really can't afford to test every object against every other object every frame at 60 FPS. Instead you need to use object groups.
I think it's okay to do it with 8 or so objects. At least that's what I do - but objects only call the routine if they need it.
The complexity is quadratic, so this will only work for small amount of objects.
Ok, now harder question: Collisions with background.
In fact it's easier I think.
Just do something like this pseudo code :
Code: Select all
boolean check_collision(x, y)
{
map_x = object_x >> 4 (or whathever other value depending on the size of your metatile)
map_y = object_y >> 4
metatile = map[map_x][map_y]
return = meta_tiles_definition[metatile] & collision_bit (depends how exactly you implemented your metatiles)
}
topleft_bg_col = check_collision(object_xmin, object_ymin)
topright_bg_col = check_collision(object_xmax, object_ymin)
bottomleft_bg_col = check_collision(object_xmin, object_ymax)
bottomright_bg_col = check_collision(object_xmax, object_ymax)
bg_collision = topleft_bg_col || topright_bg_col || bottomleft_bg_col || bottomright_bg_col
Re: How do I come about collision detection?
Posted: Thu Nov 14, 2013 7:22 pm
by tokumaru
You should not limit collision detection to the 4 corners of your objects... if you have a character that's 24 pixels tall you can have it go straight through a 16-pixel tall block. Ideally you'd check all blocks across the whole edge of the object. For example, if the player comes running and jumps against a solid metatile like this:
Code: Select all
+------A
| |+------+
| PLA || META |
| YER || TILE |
| |+------+
+------B
/
/
------------------------
If you check just the A and B points, he'll go through the meta tile. To solve this problem you have to check all blocks from point A to point B:
Code: Select all
+------+
: META :
+------A: TILE :
| |+------+
| PLA || META |
| YER || TILE |
| |+------+
+------B: META :
: TILE :
+------+
Also, you don't need to check all 4 sides every frame. Since an object can only move in one direction horizontally and one direction vertically, you need to check at most 2 sides. If an object moves right, its left side can't possibly collide with anything, so you don't even check it. If an object doesn't move left or right from one frame to the next, you don't have to check for horizontal collisions at all (the same goes for vertical movement).
Re: How do I come about collision detection?
Posted: Thu Nov 14, 2013 7:54 pm
by tepples
tokumaru wrote:If an object moves right, its left side can't possibly collide with anything, so you don't even check it.
This is true of a static map metatile, not so much of a map that changes blocks from solid to passable and vice versa.
Re: How do I come about collision detection?
Posted: Thu Nov 14, 2013 11:21 pm
by Drag
If you're performing collision detection against a tilemap whose tiles are very simple (as in, the tiles aren't complicated to the point where a tile can be solid on one half, and empty on the other half, tiles aren't round or have funny-shaped edges, things like that), then you can take advantage of this fact, and the fact that every tile is the same size.
Let's pretend the player is 12x12, and the tiles of the tilemap are 8x8. It'll look something like this:
Code: Select all
╔══════╗
║ ║
║ ║ ┌──────────┐
╚══════╝ │ │
╔══════╗ │ PLAYER │
║ ║ │ │
║ ║ │ │
╚══════╝ └──────────┘
╔══════╗╔══════╗╔══════╗╔══════╗
║ ║║ ║║ ║║ ║
║ ║║ ║║ ║║ ║
╚══════╝╚══════╝╚══════╝╚══════╝
To check the bottom edge of the player against the tilemap, first, look at the bottom left corner of the player, down one extra pixel, and sample the properties of the tile at this point:
Code: Select all
╔══════╗
║ ║
║ ║ ┌──────────┐
╚══════╝ │ │
╔══════╗ │ PLAYER │
║ ║ │ │
║ ║ │ │
╚══════╝ └──────────┘
╔══════╗╔═══█══╗╔══════╗╔══════╗
║ ║║ ║║ ║║ ║
║ ║║ ║║ ║║ ║
╚══════╝╚══════╝╚══════╝╚══════╝
Next, move your point to the right by the width of a tile (in this case, 8 pixels), but only if it doesn't exceed the width of the player. Because you're moving by the width of a tile, you are guaranteed to be looking at the next tile over:
Code: Select all
╔══════╗
║ ║
║ ║ ┌──────────┐
╚══════╝ │ │
╔══════╗ │ PLAYER │
║ ║ │ │
║ ║ │ │
╚══════╝ └──────────┘
╔══════╗╔═══░══╗╔═══█══╗╔══════╗
║ ║║ ║║ ║║ ║
║ ║║ ║║ ║║ ║
╚══════╝╚══════╝╚══════╝╚══════╝
Moving the point by the width of a tile again will exceed the width of the player. So instead, check the bottom right corner of the player, down one extra pixel, and sample the properties of the tile at this point:
Code: Select all
╔══════╗
║ ║
║ ║ ┌──────────┐
╚══════╝ │ │
╔══════╗ │ PLAYER │
║ ║ │ │
║ ║ │ │
╚══════╝ └──────────┘
╔══════╗╔═══░══╗╔═══░══█╔══════╗
║ ║║ ║║ ║║ ║
║ ║║ ║║ ║║ ║
╚══════╝╚══════╝╚══════╝╚══════╝
If any of those tiles were solid, then the player doesn't fall. If zero of those tiles were solid, then the player falls.
Checking the other edges of the player work in a similar manner: To check the left edge of the player, start at the top left corner of the player (pushed out one pixel to the left), and move down in "tile_height" increments, sampling each pixel until you get to or move past the bottom left corner (pushed out one pixel to the left), at which point you check the bottom left corner itself. If all of the tiles at those pixels were solid, then the player can't pass through. If none of them were solid, then they player can pass through.