Handy collision detection

[Drag]

You can use the same solution again, and have a linked list of empty slots, so there will be no need to scan. When you need a free slot, just grab the first one and make the second one the new first, and when you free a slot you can do the opposite. Memory use will just increase by 1 byte, the one used to indicate the first free slot, because objects can't be in both lists, so you can still get away with only one byte per object indicating the next one.

Wow, never thought of this trick. That's a great idea!

Yeah, that's phenomenal!

[qbradq]

This has been a very timely discussion as I am implementing collision detection this week Here is my approach, but it is taking 42 scan lines for 8 enemies, 5 bullets and 1 player. I'd love some advice on how I can improve this.

I am basically implementing the collision grouping idea of the OP but in a different way. I have very narrowly defined criteria for what will collide with what.

1. Player projectiles with Enemy ships
2. Enemy projectiles with the Player's ship

As such I did not use the bitmask approach. Here's what I do:

Code: Select all

1. Iterate through all objects
    a. Calculate the bounds of each object in RAM (top, left, bottom, right)
    b. Place the object in a collision array based on it's type (player projectile, enemy projectile, or enemy)
    c. Make note of the player's object number when we see it
2. Iterate through all player projectiles
    a. Iterate through all enemy ships and compare bounds
    b. If there is a collision, handle it
3. Iterate through all enemy projectiles
    a. Compare bounds with the player's ship
    b. If there is a collision, handle it

This is about as efficient as I can think to make it. I am only calculating bounds once per each object and I am only comparing those bounds for unique sets of objects. My problem comes with scaling. With 8 enemies and 5 player bullets that's 40 comparisons.

I know it is possible to do very large scale object collision on the NES. Take LifeForce for example. The player can have up to 10 projectiles on the screen at any one time along with up to 30 enemies (see level 2, falling rocks segment) without slowdown.

I tried limiting my game to 30 FPS to give me more time for collision detection, but this looks simply awful. Should I keep looking at multiplexing or am I just doing collision detection poorly?

[EDIT]
Trying not to hijack the thread here, I just wanted to let others that read this later know how I resolved my problems. In the above code block I was using a subroutine to check the bounding rects. In-lining this saved about 14% of the execution time. I then multiplexed the collision detection, only processing even-numbered bullets on even-numbered frames and vice versa.
[/EDIT]

[tokumaru]

Here is my approach, but it is taking 42 scan lines for 8 enemies, 5 bullets and 1 player.

Is that just for the collisions? That time might not be so bad depending on how much you spend on the AI and background collisions (something you might not even have in a space shooter, for example).

[qbradq]

OK, I'm verging on thread-jacking at this point I'll turn the conversation more generic.

Are you all using the entire sprite area as the bounding rectangle or are you using X and Y offsets with a width and height? I am doing the latter for more accurate collision detection, but it eats CPU time due to the multiple adds.

Also, is everyone using 16-bit values for X and Y? I am using 8-bit values with two bits in the flags byte for the object that act as a ninth bit. I skip any object that is off-screen in either direction (as in I don't even generate bounding rects for them) and then clip the bounding rect to the screen. This way the collision detection code is a LOT simpler.

I am using a JSR / RTS for the collision test. I wounder if in-lining this would help much. I'll test that next.

What I would like to do is put together a best practices document for collision detection and response on the NES. Of course it would not apply for every genre, but I see this as a big barrier to entry for folks wanting to develop more complex NES homebrew.

[Drag]

There's another trick you can use to speed up bounds-checking.

If you only check the enemy's X range against the bullet's X range, and you find that they're not overlapping, then there's no way a collision can be occuring, and you don't need to check the Y range.

Same thing for Y, if the two actors' Y ranges are not overlapping, then there's no way they can be overlapping, and you don't need to check X.

Furthermore, you can write some pretty fast code by being careful with how you perform your checks.

Two actors, A and B, are colliding if both their x ranges and y ranges are overlapping:

Code: Select all

 A = Some actor
 Calculate A's hitbox here.
 B = A
LOOP:
 B++
 IF (B > last actor) THEN exit
 Calculate the X coordinates of the left and right edges of B's hitbox here.
 IF (A.left > B.right) THEN GOTO LOOP
 IF (A.right < B.left) THEN GOTO LOOP
 ; If you reach this point, A and B are overlapping on the X axis.
 Calculate the Y coordinates of the top and bottom edges of B's hitbox here.
 IF (A.top > B.bottom) THEN GOTO LOOP
 IF (A.bottom < B.top) THEN GOTO LOOP
 ; If you reach this point, a collision is occuring between A and B.
 Handle the collision.
 GOTO LOOP

This way, you can eliminate half of your calculations most of the time. If you're doing a vertical shmup, then I'd recommend doing the Y check first, then X.

This is exactly how I'm doing collision detection. Additionally, I "reworded" the conditional statements so they're always "less than" comparisons, since you only need one branch for those, versus "greater than", which requires two (remember, 6502 only has >=, not >).

[tokumaru]

Also, is everyone using 16-bit values for X and Y? I am using 8-bit values with two bits in the flags byte for the object that act as a ninth bit. I skip any object that is off-screen in either direction (as in I don't even generate bounding rects for them) and then clip the bounding rect to the screen.

You know, I was thinking about this the other day. I currently use 16-bits for all coordinates, but it might be a good idea to only check collisions for objects that are on screen and use 8 bits instead... The problem is that this works well for sprite collisions, but for background collisions you still need 16-bit coordinates...

I am using a JSR / RTS for the collision test. I wounder if in-lining this would help much.

JSR/RTS inside a loop could add to alot of extra time. I tend to inline everything that is only done in a single place... Hell, I'll even duplicate a routine if using it inlined results in significant speed increase.

[qbradq]

Quote:
I am using a JSR / RTS for the collision test. I wounder if in-lining this would help much.

JSR/RTS inside a loop could add to alot of extra time. I tend to inline everything that is only done in a single place... Hell, I'll even duplicate a routine if using it inlined results in significant speed increase.

In-lining that routine reduced the execution time by 15%! Yay!

@Drag,

Don't know why I did not think of that before. Due to my very narrow requirements this will fit very nicely. I will implement this soon.

I also implemented collision multiplexing, only doing 50% of collision detections per frame. I only consider odd-numbered bullets on odd-numbered frames and vice versa. By managing the maximum speed of the projectiles with the the minimum width of the enemies I shouldn't miss collisions.

[tepples]

By managing the maximum speed of the projectiles with the the minimum width of the enemies I shouldn't miss collisions.

Another way not to miss collisions is to extend a projectile's hitbox backward by how far it has traveled over the past frame or two.

[qbradq]

As for multiplexing collision detection I get some issues with diagonal movement of bullets. This can sometimes cause a false miss. I kinda like it though, it's sort of like grazing in modern SHMUPS.

Another way not to miss collisions is to extend a projectile's hitbox backward by how far it has traveled over the past frame or two.

Thanks for the hint Tepples, I'll implement that if I ever have issues with "shooting through a wall" as it were.

@Drag,

Don't know why I did not think of that before. Due to my very narrow requirements this will fit very nicely. I will implement this soon.

I don't know what I was thinking here. This reduces performance I still have to consider every object's bounding rect more than once, therefore caching their bounding rect in memory and running comparisons from there is more efficient.