Fastest way of doing BG tile collision detection

Discussion of hardware and software development for Super NES and Super Famicom. See the SNESdev wiki for more information.

Moderator: Moderators

Forum rules
  • For making cartridges of your Super NES games, see Reproduction.
Post Reply
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Fastest way of doing BG tile collision detection

Post by psycopathicteen »

I am wondering if it is possible to do BG tile collision on 128 objects at once without slowdown. Even though my homebrew game can certainly push a lot of sprites onscreen, I figured out that my BG tile collision routine wouldn't be fast enough for 128 objects at once, so even if I can have something like 128 explosions at once without slowdown, doesn't mean I can have 128 enemies walking on the ground at once without slowdown.

I used the screen brightness register $2100 as a quick way of benchmarking how long the routine takes on average, and it takes about 5 scanlines on average to do collision with the BG tile grid, which means that it would be capable of about 52 objects, if it wasn't doing anything else but BG collision detection.

As for the way I currently do collision detection, it's kind of a complicated mess.

-Every sprite that uses BG collision has to manually save its x and y coordinates before any other gameplay logic.
-Then it does gameplay logic
-Then it runs the BG collision detection subroutine that does the following:
-First it determines if the player or enemy is on a moving platform object, which it then adds the velocity of the moving platform to the object's position. This is to make sure that collision detection still works correctly, even when the object is on a moving platform.
-Then, using its old X-position, it determines if it is hitting a ceiling or a floor. It checks ceilings first.
-Then, it checks for floors using the bottom center point. It determines if it falls through a pass-through-bottom tile by comparing the old Y with the new Y.
-If the bottom center point is inside an empty tile, then it checks the bottom left and bottom right points for a tile with a "ledge" flag set, so it can hang off the edge of a platform without falling into a wall.
-Then it checks horizontally to either move the object on top of the slope, or it checks if it hits a slope while moving vertically. I forgot how I did this, and I would need to study my code again.
-Then it finally checks for walls. The bottom-most point on the wall hitbox moves up 16 pixels when standing on the ground to avoid getting stuck on stuff underneath sloped platforms when walking up.

I wouldn't be surprised if there was a much easier way of doing this. I'm not quite sure but I think the Mario and Sonic games just used the y-velocity sign to determine to go through a pass-through bottom tile, instead of trying to retrace the sprite from where it came from.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Fastest way of doing BG tile collision detection

Post by tokumaru »

psycopathicteen wrote: Wed Sep 21, 2022 11:11 amI think the Mario and Sonic games just used the y-velocity sign to determine to go through a pass-through bottom tile, instead of trying to retrace the sprite from where it came from.
IMO, looking at the previous Y coordinate is the correct way to do it, because it tells you without a doubt that the object moved down from above the pass-through platform and went through it... It's certainly possible that Mario and Sonic games are cheating and doing something else, but I can't say for sure. I generally prefer to do things the right way, whenever possible, but depending on our goals, cheating may be the only option.

Getting 128 complex objects working smoothly at 60Hz on the SNES doesn't sound like a very realistic goal to me, but if you're dead set on doing this, you're probably gonna have to dial the accuracy way down for as many objects as possible. I doubt you'll be able to apply the same comprehensive logic you use for players to over 100 objects in a single frame.

For slow moving objects, you can probably get away with testing collisions every other frame, but even that will only get you a fraction of the time back from half of the objects, so that alone isn't enough.
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Fastest way of doing BG tile collision detection

Post by Oziphantom »

make your platforms know which enemy is on them, and then they update the enemy when they move, this way on enemies on the platforms have to run that code and it only happens when the platform moves.

You only need to run collision when you cross a tile boundary, which can give you a fast discard.
none
Posts: 117
Joined: Thu Sep 03, 2020 1:09 am

Re: Fastest way of doing BG tile collision detection

Post by none »

Depending on the situation there's a lot of things that might work, that come to mind.
  • Separate collision logic by actor type i.e. have a different routine for player / each enemy type / each projectile type and so on. Do only the checks that are actually necessary for each type. for example, projectiles don't need to move on slopes and so on.
  • Save as much as possible with the state of your actors. For the player for example, save wether they are on the ground / in the air (separate further by rising / falling) / on a slope etc and then do the physics / collision accordingly, this way you can avoid a lot of checks you have to do every frame otherwise.
  • Use some kind of acceleration structure like a quad tree to "weed out" objects that don't need collision, this would make sense for example if you have a lot of flying enemies in the air in a large open environment.
Since your questions is about enemies in particular, it depends mainly on two factors: How intelligent / predictable their behaviour is, and how dynamic the environment is. If you have enemies with a few predetermined movement patterns like in SMW for example, and a more a loss static environment, a lot of the pathing can be precalculated, and / or you can have a few enemies share the same path.

Another example, enemies might sometimes "prepare" for a move (like for example like the silver space pirates in Super Metroid with the jump kick). Other than for telegraphing the attack to the player, during this waiting period, no collision needs to be actually done and also the game engine could prepare the path for when the animation actually plays out in advance.

Can you tell us more about what kind of enemies you are trying to create?

The same goes for the moving platform issue. If the platform is traveling along a preset path, you can probably just do the checks if you know the platform is near an obstacle, for example.

Also for moving platforms, it might make sense to actually store the position of the entities that are on the platform in terms relative to the platform, which also makes some of the physics stuff easier (i.e. accelerating, running etc can be done the same way as on "static" ground, actors travel with the platform automatically) and then just add up the platform and actor position just before doing the collision check.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Fastest way of doing BG tile collision detection

Post by tokumaru »

Oziphantom wrote: Wed Sep 21, 2022 11:15 pmmake your platforms know which enemy is on them, and then they update the enemy when they move, this way on enemies on the platforms have to run that code and it only happens when the platform moves.
I've heard of games doing platforms like this before, but I find it really weird to have the platform link to the object it carries, rather than the other way around, mainly because a platform can carry multiple objects, but an object can only stand on a single platform.

Sure you could have each platform hold a list of objects that are standing on them, but this complicates things, imposes a hard limit on how many objects it can carry, all while bringing very few benefits IMO.
You only need to run collision when you cross a tile boundary, which can give you a fast discard.
This does sound like a good optimization, at least when there are no slopes on the plane you're testing.
none wrote: Thu Sep 22, 2022 5:00 amAlso for moving platforms, it might make sense to actually store the position of the entities that are on the platform in terms relative to the platform, which also makes some of the physics stuff easier (i.e. accelerating, running etc can be done the same way as on "static" ground, actors travel with the platform automatically) and then just add up the platform and actor position just before doing the collision check.
I think this would complicate interactions between the entity riding the platform and the ones that aren't, since they'd be essentially living in different spaces.
spaceharrier
Posts: 40
Joined: Wed Jan 19, 2022 9:52 am

Re: Fastest way of doing BG tile collision detection

Post by spaceharrier »

I use 1-bit truth tables in my engine. The trade-off is space, as the truth table of two 16x32 actors can be 256 bytes, but I can get pixel perfect collision detection done in under 100 cycles, and the collision masking is redundant for most actors anyway.

If I make the detection courser, that goes down to 64 bytes per table, but at that point, I don't get much benefit over bounding box checks.
Post Reply