[flamewing]

Cooljerk, on 11 May 2018 - 06:57 AM, said:

To ask a follow up question -- what are the mechanisms used in hardware to do collision detection?

None, because the only one provided by the VDP sucks:

Cooljerk, on 11 May 2018 - 06:57 AM, said:

Isn't there a bit in the VDP status Register that can detect collision of sprites on other sprites? Does this extend to sprites on planes, tiles, etc?

This bit checks if any hardware sprite has overlapped with any other hardware sprite in their non-transparent pixels. So in Sonic 2, for example, it is set whenever Tails is on-screen because some pixels of his tails overlap with some pixels of his body.

The sprite collision bit is only ever cleared when you read the VDP status register, so you have to keep constantly reading it during active display: if you don't, all you will only know that in some point on the screen, two sprites overlapped in their non-transparent pixels. You will also have to constantly read the H/V register, so you can get an approximate position on when the collision happened. And you will have to log all of those collisions to somewhere in RAM so you can process them later: if you try to process them as they happen, you will miss others.

All of that will combine to keep the 68k occupied during the entirety of active display (or you will miss collisions), consuming a lot of CPU time. It also means you are continually poking the VDP when it is busiest, which is not good. And the further processing you will need to do after active display to figure out which correspond to different objects which should collide will eat up a lot more time, especially because a lot of the collisions will be spurious.

And to make matters worse, the position you read from the H/V register will be very coarse in X position, meaning you are likely to be wrong about the collision anyway.

Yeah, it sucks, and is totally not worth it.

Cooljerk, on 11 May 2018 - 06:57 AM, said:

Or are the type of collision checks you described done entirely in software on the CPU through math?

Entirely software.

Cooljerk, on 11 May 2018 - 09:17 AM, said:

I've tried looking through the source code to see exactly how it's done in software but I'm not sure which routines would specifically handle that sort of stuff, can you point me in the right direction?

alternatively, what sort of patterns does the software use to speed up these kinds of checks? A buckets approach to limit number of checks or what?

There are several completely different groups of collision detection routines used in these games, and they change along the games (being similar, though). They also use different strategies for optimization which were progressively added, as well as different goals of optimization. Since they are generally better commented and labelled, I will give the names of the Git S2 disassembly.

• object/terrain collision: This is a superset of what I described in the above posts; I focused on characters, and other objects tend to do it a bit differently: generally, they don't care about terrain at all, and those that do only cast one or two sensor rays at most. Except for S1 and SCD, all other games have a lookup table in the function that locates the required tile for speeding up the collision checks. Relevant functions:
  
  • Find_Tile: lower level function which locates the tile at the input position. No object calls this directly.
    
  • FindFloor, Ring_FindFloor, FindWall: calls Find_Tile, potentially finds another tile further away, inspects collision from the tiles, and returns distance until/inside terrain. No objects call these directly.
    
  • Any other functions that call the above functions: these are directly called by objects, and they generally just use the distance returned.
  
  
• object/object collision: These are platform and solid objects: objects you can stand on, push on (or be pushed by), or bump into them from below. Basically, objects where it matters which side you collided with, and which eject you out of their collision box. I am writing something this group of collisions, but I am still tabulating the information from the several games, and I am still thinking on how to make it digestible. SCD optimizes for size, and combines all object/object collision into one single function which checks the type of collision in the routine. The others tend to optimize for speed, and split off into different routines for different types of collision.
  Relevant functions: SolidObject, SolidObject_Always, SlopedSolid, SolidObject45, PlatformObject, SlopedPlatform, PlatformObject2, PlatformObjectD5, etc.
  
• object/object touch: This is a different kind of collision, which uses a different collision box, the hitbox. In a nutshell, any object which does not care the direction from which you collide with it, and which neither ejects you out of its collision box, nor carries you on top. Examples include badniks, rings in S1/SCD, all bumpers in S1/SCD, some bumpers in S2/S3/S&K/S3&K, attracted rings in S3/S&k/S3&K, etc. S3/S&K/S3&K have a subscription-based model: touchable objects add themselves to a list, and the characters check collision only with objects on the list. In S1/S2/SCD, on the other hand, check against every other object loaded. In all games, the check stops as soon as something is touched. Relevant function: TouchResponse.
  
• object/ring touch: In S1/SCD, rings are objects, and just use object/object touch. In S2/S3/S&K/S3&K, rings have their own separate per-level data for their positions, and the games check collision of each character with all rings in a certain range. Relevant function: Touch_Rings.
  
• object/special collision: S2/S3/S&K/S3&K also have routines for collision with special bumpers; I think some rocks in Lava Reef in S&K/S3&K are also not normal objects, but Neo/Tiddles probably know more. Relevant function: Check_CNZ_bumpers.

I won't get into collision in the various special or bonus stages.

[Cooljerk]

much appreciated!

[Cooljerk]

So, more of a theoretical postulate than an actual question, but flamewing (and others) mention the lack of granularity in using the vdp status register to do collison checking, which makes sense. What i am wondering is why such status flag isnt used initially as general broadphase collision detection. I see flamewing mentions the flag will be set every time tails is on screen, but lets go back to sonic 1. If all the collision detection among sprites is done in software, presumably it could be done anything during the frame, right? Is there a reason to not move the software check to, say, vblank, but only perform it if the vdp register bit is set? I.e. wait for vblank to check if the bit is set (i.e. any collision occurred) then go to a narrow phase check in software? Wouldnt that result in speedier code, as you would only be checking for collision when you would be certain it occurred? This is pretty much how modern collision detection works.

[Neo]

The HUD is made up of sprites. So every time the HUD crosses over any other sprite, it would detect a collision.

Also, the shield is also a sprite. So whenever you have a shield, it would constantly detect collisions.

Also, the invincibility stars are also sprites. So when you have invincibility, it would constantly detect collisions with Sonic. Also, there's also an extra trail of invincible stars that trail behind the main invincibility stars. So they would also detect collisions with each other and with the main invincibility stars and with Sonic.

It doesn't take much to see how a single flag for the entire screen is not a particularly efficient way to detect collisions.

[Cooljerk]

Neo, on 12 May 2018 - 06:35 AM, said:

The HUD is made up of sprites. So every time the HUD crosses over any other sprite, it would detect a collision.

Also, the shield is also a sprite. So whenever you have a shield, it would constantly detect collisions.

Also, the invincibility stars are also sprites. So when you have invincibility, it would constantly detect collisions with Sonic. Also, there's also an extra trail of invincible stars that trail behind the main invincibility stars. So they would also detect collisions with each other and with the main invincibility stars and with Sonic.

It doesn't take much to see how a single flag for the entire screen is not a particularly efficient way to detect collisions.

The concept of broad phase collision, ironically, isn't necessarily to detect collision, it's to throw out conditions when there is no collision at all. As is, the software is going to have to check collisions every frame, right? So why not use the bit to see when there are times that there are no collisions at all, and use that to skip the collision detection portions? Even in the situations you posit, at worst, you'd still be performing the checks that the software already goes through, right?

Your response is still the type I'm looking for, btw -- i.e. conditions that might throw the check for a loop, or other quibbles. Is checking that bit a particularly expensive operation or something?

EDIT: Re - HUD collisions. The bit is reset every time it's checked, right? So check the VDP Status Register, say during an H-blank immediately following the completion of the HUD drawing, so that during vblank or whenever, if the bit is set, all it tested for was the portion below the HUD. I can't particularly think of any times when collisions ever occur next to or around the HUD...

This post has been edited by Cooljerk: 12 May 2018 - 07:30 AM

[pacguy]

From what I can see, such a check would just make the game slightly slower; the odds of absolutely no sprites overlapping is so ridiculously low, that you'd be better off just disposing of the check entirely. It would only really work when there are an extremely small amount of sprites on screen, at which point you may as well just run the collision anyways (since most object slots will just be skipped, making the collision routine faster). Also, it is entirely possible to collide with invisible objects with no sprite (like path swappers). Implementing such a feature would force you to make sprites for every collidable object, wasting precious sprite slots on something that really should never have rendered in the first place.

This post has been edited by pacguy: 12 May 2018 - 11:06 AM

[MainMemory]

I don't think the path swapper does any sort of collision checks, however, there is the invisible solid block (and invisible hurt block in S3K), which, as the name indicates, has collision, and is invisible outside of debug mode, where it only shows a 32x32 sprite, regardless of how large the block actually is.

[Cooljerk]

pacguy, on 12 May 2018 - 11:01 AM, said:

From what I can see, such a check would just make the game slightly slower; the odds of absolutely no sprites overlapping is so ridiculously low, that you'd be better off just disposing of the check entirely. It would only really work when there are an extremely small amount of sprites on screen, at which point you may as well just run the collision anyways (since most object slots will just be skipped, making the collision routine faster). Also, it is entirely possible to collide with invisible objects with no sprite (like path swappers). Implementing such a feature would force you to make sprites for every collidable object, wasting precious sprite slots on something that really should never have rendered in the first place.

The worst case scenario would be a couple of extra checks for a bit, the best case scenario would be potentially dozens of checks skipped. This of course only deals with visible sprite objects, seeing as there also needs to be checks against tiles and blocks and such. Again, the goal of a broad phase collision detection scheme isn't to actually detect collision, it's to reduce the number of checks given in any single instance.

I'm wondering if there is perhaps another pattern used to reduce collision detection checks -- surely the Sonic games do not actually check every single object against every other object on screen. Even on modern computers, that is a slow process.

[pacguy]

They don't; Only the Sonic and Tails objects are checked for object collision. No non-player objects collide with other objects by default, unless you actually program them to do so. However, Sonic and Tails do both loop through most of object ram once per frame. I guess it could be optimized by having both Sonic and Tails collide in the same loop, but it'd make the code feel a bit messier IMHO.

[Neo]

Cooljerk, on 12 May 2018 - 11:24 AM, said:

surely the Sonic games do not actually check every single object against every other object on screen. Even on modern computers, that is a slow process.

flamewing already explained how this works. If only you would absorb anything of what people are trying to tell you.

[Cooljerk]

Neo, on 12 May 2018 - 11:50 AM, said:

Cooljerk, on 12 May 2018 - 11:24 AM, said:

surely the Sonic games do not actually check every single object against every other object on screen. Even on modern computers, that is a slow process.

flamewing already explained how this works. If only you would absorb anything of what people are trying to tell you.

Take note, oldbie, the trial member above is showing you up on your behavior. There is nothing wrong with asking for further clarification and if you don't have anything else to contribute beyond snark, don't post.

pacguy, on 12 May 2018 - 11:30 AM, said:

They don't; Only the Sonic and Tails objects are checked for object collision. No non-player objects collide with other objects by default, unless you actually program them to do so. However, Sonic and Tails do both loop through most of object ram once per frame. I guess it could be optimized by having both Sonic and Tails collide in the same loop, but it'd make the code feel a bit messier IMHO.

Much appreciate this response.

[flamewing]

pacguy, on 12 May 2018 - 11:30 AM, said:

They don't; Only the Sonic and Tails objects are checked for object collision. No non-player objects collide with other objects by default, unless you actually program them to do so. However, Sonic and Tails do both loop through most of object ram once per frame. I guess it could be optimized by having both Sonic and Tails collide in the same loop, but it'd make the code feel a bit messier IMHO.

Note that those are for different kinds of collision (solidity vs touch). The checks probably would not be imported by having Tails and Sonic do the touch loop together because of 2 things:

• The loop figures out Sonic's/Tails' hitbox and position once and caches it in registers, then uses these values for touch checks with all objects. Doing Sonic and Tails together would require figuring out hitbox and position for Sonic, checking touch with one object, then figuring hitbox and position for Tails, and checking touch again.
  
• The loop stops after the first touch. With the combined loop, you cannot do this or Tails will not touch any objects on a frame in which Sonic also touches.

Also, you can just convert touch to a subscription-based model like in S3/S&K/S3&K, which only check touch with touchable objects.

This post has been edited by flamewing: 12 May 2018 - 02:58 PM

[Cooljerk]

flamewing, on 12 May 2018 - 02:57 PM, said:

pacguy, on 12 May 2018 - 11:30 AM, said:

They don't; Only the Sonic and Tails objects are checked for object collision. No non-player objects collide with other objects by default, unless you actually program them to do so. However, Sonic and Tails do both loop through most of object ram once per frame. I guess it could be optimized by having both Sonic and Tails collide in the same loop, but it'd make the code feel a bit messier IMHO.

Note that those are for different kinds of collision (solidity vs touch). The checks probably would not be imported by having Tails and Sonic do the touch loop together because of 2 things:

• The loop figures out Sonic's/Tails' hitbox and position once and caches it in registers, then uses these values for touch checks with all objects. Doing Sonic and Tails together would require figuring out hitbox and position for Sonic, checking touch with one object, then figuring hitbox and position for Tails, and checking touch again.
  
• The loop stops after the first touch. With the combined loop, you cannot do this or Tails will not touch any objects on a frame in which Sonic also touches.

Also, you can just convert touch to a subscription-based model like in S3/S&K/S3&K, which only check touch with touchable objects.

Would you mind going into a bit more detail about this? Doesn't have to be as dense of a post as you made before or anything, but that sounds interesting.

[flamewing]

Cooljerk, on 12 May 2018 - 03:10 PM, said:

Would you mind going into a bit more detail about this? Doesn't have to be as dense of a post as you made before or anything, but that sounds interesting.

Objects have a field called collision flags. This field controls both the size of an object's hitbox as well as how the collision is processed. If the collision flags are zero, there is no collision. Most objects have zero in their collision flags.

In S1/SCD/S2, this means a lot of time is spent going through the object slots checking collision flags, and skipping all those with zero collision flags (which includes those empty object slots). This is done twice in S2, for Sonic and for Tails, and consumes a few thousands of cycles per character per frame when all objects are skipped.

S3/S&K/S3&K have a buffer in RAM with the addresses of all objects that are touchable, with a count at the beginning of the buffer. Each object is responsible for adding itself to the list, and the list is "cleared" after the code for Sonic and Tails code has finished executing and before all other objects execute their own coffee; this is done by setting the number of objects in the list to zero. The collision code only checks objects on that list, which avoids uselessly processing a lot of objects.

The amount of cycles saved this way is spent by having shields also check projectile deflections against all objects in this list. Hyper Sonic's hyper dash, Hyper Knuckles' for into wall, and Super Tails' flickies also use the list for checking targets.

[Cooljerk]

flamewing, on 12 May 2018 - 04:51 PM, said:

Cooljerk, on 12 May 2018 - 03:10 PM, said:

Would you mind going into a bit more detail about this? Doesn't have to be as dense of a post as you made before or anything, but that sounds interesting.

Objects have a field called collision flags. This field controls both the size of an object's hitbox as well as how the collision is processed. If the collision flags are zero, there is no collision. Most objects have zero in their collision flags.

In S1/SCD/S2, this means a lot of time is spent going through the object slots checking collision flags, and skipping all those with zero collision flags (which includes those empty object slots). This is done twice in S2, for Sonic and for Tails, and consumes a few thousands of cycles per character per frame when all objects are skipped.

S3/S&K/S3&K have a buffer in RAM with the addresses of all objects that are touchable, with a count at the beginning of the buffer. Each object is responsible for adding itself to the list, and the list is "cleared" after the code for Sonic and Tails code has finished executing and before all other objects execute their own coffee; this is done by setting the number of objects in the list to zero. The collision code only checks objects on that list, which avoids uselessly processing a lot of objects.

The amount of cycles saved this way is spent by having shields also check projectile deflections against all objects in this list. Hyper Sonic's hyper dash, Hyper Knuckles' for into wall, and Super Tails' flickies also use the list for checking targets.

Ah! THIS is the type of "speed up" I was talking about in pervious posts when I mentioned a "buckets" approach. This is precisely the type of thing I've been poking for in this topic, thanks so much!