Bounding Boxes

[Celius]

I'm working on a sub-engine for handling sprite objects, and of course, I've come up to collision, and I'm kind of stuck. I know what I'm trying to do, I just need to think of a way that's much less sloppy and a lot faster. I'm constructing bounding boxes around each of the meta sprites, and I am going to keep track of the X/Y coordinates of each corner in RAM. The idea is to check if any of the bounding boxes are overlapping.

Right now, this is only for sprite to sprite collision. Sprite to BG collision detection is a lot easier, since I will be having a copy of what's on screen in RAM. I'll also be handling every object one at a time, so it's not too complicated for sprite to BG. I looked at the threads about collision here, and I came across a really good idea. Someone mentioned organizing coordinates from low to high to easily eliminate sprites that aren't colliding with whatever you're comparing it to. While this is a good idea, it seems that this is still an extremely long process.

It would take a really long time to compare every coordinate on one bounding box with every coordinate on another. The bad part about that is that's only for 2 objects. The main reason I think this is so complicated compared to BG collision is that I already have a copy of what metatiles are on screen in RAM. Those will ALWAYS be in a fixed 16x16 pixel location. If you check whether or not sprites are in the same 16x16 pixel feild, you can end up with collisions like Bugs Bunny's Birthday Blowout, where you hit the enemy and they're about 16 pixels away from you. So you pretty much have to do precise comparisons.

I feel like if I do all these comparisons, I'm wasting so much valuable time. I also feel like I'm going about doing things in a really sloppy way. Does anyone have any ideas on checking bounding box overlapping without wasting so much time? I'll be brainstorming ideas, but I just wanted to know what everyone else thinks.

[tepples]

For one thing, you could keep a list of active sprites insertion-sorted by X or Y coordinate. Then you can compare each sprite only with other sprites near it in that dimension.

How many objects per screen are you talking about?

[tokumaru]

It really depends on the type of the game too... in platformers, such as my Sonic engine, the objects only need to collide with the player, and never with each other. This sure makes things easier because each enemy/object will check if it collided with the player, and by the time all the objects have been processed (just once) everything is done. Most enemies/objects don't even need to collide with the background, and when they do it's just by a single central pixel or so.

I imagine that other kinds of games will need to check for object vs. object collisions, and that could be very slow, depending on the amount of objects loaded at the time.

I suggest you think about it and decide what types of collisions must be checked for. I doubt an object will collide with every type of object, so you could have a few flags assigned to each type of object, and the object being processed will scan the list of active objects, checking for collisions only with the relevant types of objects.

If you are making a tiled RPG, where each character occupies a block and no one else can enter it, you'd have to be aware of everyone's positions. But this could be solved in a simpler way than with bounding boxes: a simple array could indicate if a square is used or not, and no character can enter an occupied square. Most RPG's only need really simple collision detection, because of their grid nature.

[Celius]

I'm working on an action game right now, pretty much exactly like Castlevania: Symphony of the Night. But the objects just have to check if they're colliding with the player, or the weapon. So I need to check for collision for two objects, basically. By organizing their coordinates from low to high, it shouldn't take THAT long, but I was just thinking maybe it could take less. But yeah, if I had EVERY object collide with each other, it would be a nightmare.

EDIT:

How many objects per screen are you talking about?

There are at most 15 objects on screen. 2 of them are the player and the weapon, 5 of them are enemies, and the rest are used for items/hearts.

[tokumaru]

But the objects just have to check if they're colliding with the player, or the weapon.

Then do it like I do... Since there is only one player and one weapon, the enemies should check for these collisions. In my game, there is a list of active objects, each one has a code and whatever other information they need that fits in the 20 bytes of RAM I give each one of them. Every frame, I'll scan this list, reading the codes of the objects and using the code as an index into a table that has the addresses of the routines of each object. Only when this code is executed the enemy itself will check for the collisions that are important to it.

In your case, enemies will look at the player and at the weapon. You can even have routines to do this... you could pass the coordinates of the bounding box of the enemy as parameters to a routine that will verify if that box overlaps with the player's, and will return a flag as a result. You can also have a routine that will do the same, but with the weapon. The weapon routine can even check what's the current weapon (supposing it changes along the game) and take into account the different kinds... it would be able to handle even projectiles and all...

This way you wouldn't need to sort anything... and each object will only call the collision routines if they need to.

Bounding box collision detection can be quite fast... it takes more time to calculate the coordinates of the boxes than checking if they overlap. In fact, the best kind of bounding box collision detection I've seen checks for all the cases where a collision cannot happen, and if they all fail, the collision happened. This is good, because most of the time there is no collision happening.

And you can optimize it according to the type of your game. If your game is a side-scroller where the player moves from left to right, the first thing you should check in the collision detection routine is if the left edge of the enemy is larger than the right edge of the player. Most of the time, this first step alone will indicate that a collision cannot happen. This already eliminates one of the 4 things you have to check for in order to detect collision:

1. Is the left edge of the enemy larger than the right edge of the player? (if yes, the enemy is to the right of the player)
2. Is the right edge of the enemy smaller than the left edge of the player? (if yes, the enemy is to the left of the player)
3. Is the bottom edge of the enemy smaller than the top edge of the player? (if yes, the enemy is above the player)
4. Is the top edge of the enemy larger than the bottom edge of the player? (if yes, the enemy is below the player)

If any of the above is true, there was no collision. If they are all false, a collision happened. Just place the least likely conditions to happen at the top of the routine, like I said before, and you'll be optimizing it for you type of game.

[Celius]

Oh! I was thinking about it backwards, where I would check for collision from the player. But checking with enemies is A LOT better. And also, in the starting post of this thread, I mentioned that I saw someone check for no collision instead of checking for collision. I also thought this was a great idea. So yeah, I think that'll about do it for now. Thanks guys!

EDIT: I hesitate when I say I'll only have two objects that need checking. The player will be casting magic as well as attacking. Also, there will be subweapons, so there could possibly be around 5 objects to check instead of 2. This is where things get a little more complicated. I think I can handle it though.

EDIT 2: I had a typo. I meant to say I WAS thinking about it backwards, not I WASN'T.

And besides. Would this be a good routine to go by?

Code: Select all

 lda EnemyLeftEdge
 cmp PlayerRightEdge
 bcs NoCollision       ;If the left edge of the enemy is farther than the Player's Right edge, there is could be no collision.
 lda EnemyRightEdge
 cmp PlayerLeftEdge
 bcc NoCollision       ;If the Player's Left edge is beyond the enemy's right, there's no way there could be a collision.
 lda EnemyTopEdge
 cmp PlayerBottomEdge
 bcs NoCollision       ;If the Player's Bottom Border is above the top of the enemy, there is no way for collision.
 lda EnemyBottomEdge
 cmp PlayerTopEdge
 bcc NoCollision       ;If the player's Top edge is below (Greater than) the enemy's bottom edge, there can be no collision.
 lda EnemyStatus
 ora #CollidedWithPlayer
 sta EnemyStatus
 rts
NoCollision:
 lda EnemyStatus
 and #NoCollisionWithPlayer   ;NoCollisionWithPlayer is the opposite of CollidedWithPlayer (CollidedWithPlayer EOR #$FF)
 sta EnemyStatus
 rts

[tokumaru]

Yeah, the idea is pretty much it. I don't know if you can get away with 8-bit math though... it's up to your engine and how you handle positions, so you're the one to decide, but keep in mind that you might have problems with objects near/past the edges of the screen. I try to use the actual coordinates of the objects within the level for any interactions among them, not their screen coordinates, as these are not very reliable.

I think it's possible for each enemy to check for collisions against 3 to 5 objects... specially if you keep the order of the tests optimized. If possible, make some of the collidable objects be just a single pixel, instead of a box (I mean just for collisions, the sprites can have many pixels, of course). This should be possible with things small and fast, like bullets. Single pixels are faster to check because you don't have to calculate the 4 edges of the object, you just use that single point.

Another thing I noticed is that you set a flag that's part of the enemy's status when it hits the player... sometimes you may actually want that, such as in games where the enemies step back after hurting the player, but you'll sure want to set a flag for the player too, so that it knows it was hurt.

Another thing I'm thinking about right now is that you might not need a separate collision check for the weapon. If this weapon is something the player holds, you may get away with just expanding the player's collision box to include the weapon. If a hit was detected, you'd then check if the player and the enemy are facing each other, so you know the attack was successful, otherwise, the player was hit. This sure takes away some of the precision, if for example the enemies are able to duck so that the player's attacks do not hit them, this won't work.

It might be simpler to just check if the player is attacking or not, and if so, test for a collision with the weapon. I guess you gotta test this and see what works best! =)

EDIT: I just read how you'll distribute the active objects... if only 5 of them can be enemies, I don'tthink you'll have problems with the collision tests. The items can just check for collisions with the player, right? This will make things simpler too.

[Celius]

I could just make the player and the weapon one object, but that would set many limits. For instance, I couldn't have projectile weapons that way. I want to make the engine as flexible as possible.

Also, I was thinking about what you said for 1 pixel collision points. I will definitely keep that in mind. However, I don't know if I can use this for too much. Perhaps hearts, which are 1 tile in size. But something like a sword would not be a very good idea. My default character now is going to be slashing with his sword (Not stabbing), so if I were to have somewhere close to the end of the sword be the collision point, the point might extend past the enemy if the enemy is really close, resulting in no collision when there should be one. Two objects would make this pretty much 100% reliable.

The thing I'm worried most about is having too many objects on screen. I'll have to cut down on the hearts/items and make room for subweapons/magic. I haven't really started coding for this yet, I'm just getting the ideas together. I'm making all of these subengines seperately, and in the end, I'm going to combine them. Hopefully this won't be a disaster like my other projects (I tried making everything at once).

[blargg]

I wrote a quick demo that is able to check for collisions with a fixed-size player object and variable-sized objects using only 25 clocks per object. This demo has 63 objects bouncing off the player object, using about 14 scanlines of time (the bar on the right shows how many are used for collision checking). Has NES ROM and asm source (nesasm, but easy enough to change to another assembler).

nes_collisions.zip

At its core, the collision check usually only does one comparison per object. It checks the X axis first, since that is more likely to rule out a collision than the Y axis. I'll limit discussion to the X axis, since the Y axis is handled the same.

Code: Select all

    Px = player x position
    Pw = player width
    Ex = enemy x position
    Ew = enemy width

To see if there is any overlap, you only need to find whether Px falls between the range Ex-Pw to Ex+Ew, not including the end points:

Code: Select all

          Ex
---O#############O------
   |--Pw--|--Ew--|

There is a way to quickly find whether a value is within the range 0...N-1, just do an unsigned compare with N, and if the value is >= N, then it's not in that range. This example finds whether A is in the range 0...9:

Code: Select all

    cmp #10
    bcs out_of_range
in_range:
    ; 0 <= a < 10
    ; ...
out_of_range:

Since negative values are equivalent to large positive values, if we can somehow get the indicated values below when Px is at that position, we can do the range check with only one comparison:

Code: Select all

          Ex
---O#############O------
   |--Pw--|--Ew--|
....0123456789ABC...

We can get this with Px+Pw-1-Ex. The value to compare with is Pw+Ew-1. The single comparison becomes (Px+Pw-1-Ex) < (Pw+Ew-1). Most of this can be precalculated, as long as the player width never changes. When an enemy is created, Pw+Ew-1 can be calculated. Before the collision loop, Px+Pw-1 can be calculated, leaving only a subtraction of Ex and a comparison to the width expression:

Code: Select all

    lda pw_ew_1
    sec
    sbc enemy_x,x
    cmp enemy_w,x
    bcc hit
no_hit:
    ; next enemy

The sec can be eliminated as well, by ensuring it is either always set or clear at that point, and adjusting pw_ew_1 as necessary (if carry is always clear, you need to add an extra 1 to pw_ew_1 before the loop).

[jargon]

My own personal best method to do bounding box collision:

Sorry no 6502 version of mine.
Elliptical/Ellipsoid method is on the way tho.

btw both 2d and 3d for both Blitz Basic and C source return 1 for a collision and 0 if not.

x,y,z is position in pixels.
w,h,d is size in pixels.

remember if your sprites are located via center point you need to subtract half with w,d,h from x,y,z

you can subtract the right shift one bit each of w,d,h as needed in order to do this.

also if your bounding region is smaller than the actual sprites or larger than them, then you need to set x,y,z as lowest value range contained in the region, with w,h,d set as the width, height, depth of the span of the region from lowest included pixel/voxel to highest included pixel/voxel.

Code: Select all

/*
//As follows is the Keal method for 2d box collision.
//Copyright 2007 12/12 Timothy Robert Keal
//Credit 'Timothy Robert Keal alias jargon' somewhere
//if you use this code or a derivative thereof.
*/

;Blitz Basic Source
Function collide(x,y,w,h,x2,y2,w2,h2)
	Local flag=0
	If x>=x2 And x<x2+w2 Then flag=flag Or $1
	If y>=y2 And y<y2+h2 Then flag=flag Or $2
	If x2>=x And x2<x+w Then flag=flag Or $4
	If y2>=y And y2<y+h Then flag=flag Or $8
	flag=(flag And $3) Or (flag Shr $2)
	flag=(flag And $1) And (flag Shr $1)
	Return flag
End Function

//C Source
char collide(int x,int y,int w,int h,int x2,int y2,int w2,int h2){
	char flag=(x>=x2 And x<x2+w2)?0x1:0x0;
	flag=flag|((y>=y2 And y<y2+h2)?0x2:0x0);
	flag=flag|((x2>=x And x2<x+w)?0x4:0x0);
	flag=flag|((y2>=y And y2<y+h)?0x8:0x0);
	flag=(flag&0x3)|(flag>>0x2);
	return (flag&0x1)&(flag>>0x1);
}

Code: Select all

/*
//As follows is the Keal method for 3d box collision.
//Copyright 2007 12/12 Timothy Robert Keal
//Credit 'Timothy Robert Keal alias jargon' somewhere
//if you use this code or a derivative thereof.
*/

;Blitz Basic Source
Function collide(x,y,z,w,h,d,x2,y2,z2,w2,h2,d2)
	Local flag=0
	If x>=x2 And x<x2+w2 Then flag=flag Or $1
	If y>=y2 And y<y2+h2 Then flag=flag Or $2
	If z>=z2 And z<z2+d2 Then flag=flag Or $4
	If x2>=x And x2<x+w Then flag=flag Or $8
	If y2>=y And y2<y+h Then flag=flag Or $10
	If z2>=z And z2<z+d Then flag=flag Or $20
	flag=(flag And $7) Or (flag Shr $3)
	flag=(flag And $1) And ((flag Shr $1) And $1) And (flag Shr $2)
	Return flag
End Function

//C Source
char collide(int x,int y,int z,int w,int h,int d,int x2,int y2,int z2,int w2,int h2,int d2){
	char flag=(x>=x2 And x<x2+w2)?0x1:0x0;
	flag=flag|((y>=y2 And y<y2+h2)?0x2:0x0);
	flag=flag|((z>=z2 And z<z2+d2)?0x4:0x0);
	flag=flag|((x2>=x And x2<x+w)?0x8:0x0);
	flag=flag|((y2>=y And y2<y+h)?0x10:0x0);
	flag=flag|((z2>=z And z2<z+d)?0x20:0x0);
	flag=(flag&0x7)|(flag>>0x3);
	return (flag&0x1)&((flag>>0x1)&0x1)&(flag>>0x2);
}

[jargon]

MediaPlague :: Keal's Collision Methods

(btw if you haven't already i highly suggest setting JavaScript for mediaplague.com turned on in your browser's exceptions list)

btw i ain't writing the C code for ellipses, it's too much work,

i suggest using the normal bounding box method in the prior post first as first pass to cut down processing cycles for ellipsoidal collision.

btw this will help for writing an all int version of the ellipse collision code for 6502:

6502.org :: Integers Root

(thank scanty for that 6502 integer square root url)