don't click here

Question about S3k's collision bug

Discussion in 'Engineering & Reverse Engineering' started by FireRat, Apr 18, 2018.

  1. RetroKoH

    RetroKoH

    Member
    1,662
    22
    18
    Project Sonic 8x16
    Adding to MainMemory's suggestion, this is a fine add to the Bugs page, or maybe its own section in its entirety on the wiki, since it's fairly large and encompasses all classic games. Place a link in the bugs section to it.

    On another note, I'd suggest taking snippets of this, adding a little clarity where needed, and sprinkling it into the Physics Guide. It would be a fine addition.
     
  2. MarkeyJester

    MarkeyJester

    Original, No substitute Resident Jester
    2,192
    405
    63
    Japan
    Absolutely outstanding flamewing! The effort you've put into explaining every detail about the issues, complete with not only screenshots, but animated shots too, is going above and beyond.

    You have added to your legacy of achievements, well done~
     
  3. Fantastic explanation. Though, I wondered--why can't Knuckles 'slide' or 'land' from his glides when he's on an object? What about S2K? Does that just use S2's collision?
     
  4. RetroKoH

    RetroKoH

    Member
    1,662
    22
    18
    Project Sonic 8x16

    I'm curious on whether or not Sonic 3 Unlocked has info on this. I'd reckon this is related to some of the other minor nuances Knuckles see between these different versions. The possibility of it relating to collision is certainly possible though, monitor collision was always inconsistent in the games, and in many cases totally fucked.
     
  5. flamewing

    flamewing

    Emerald Hunter Tech Member
    1,161
    65
    28
    France
    Sonic Classic Heroes; Sonic 2 Special Stage Editor; Sonic 3&K Heroes (on hold)
    You mean something like this:
    [​IMG]

    The answer is that Knuckles' sliding code only checks for terrain in regards to sliding. That, and the Player_TouchFloor routine, which is called by solid and platform object routines, kills the glide, so that it does not even have a chance to check for objects. Also, changing the Player_TouchFloor to account for these things makes several objects (such as vertical springs) not work all that well, so they also have to be modified to clear the slide/glide. There is also an issue in object collision for several objects in S3&K that makes them interact badly with a sliding Knuckles.

    There is an ancient branch of S3C with a port of my glide-on-object code, and a few other things; but I seem to remember there were some issues that went unfixed, and I never had time to investigate, so it was never merged into the main branch. SCH has a lot less issues than S3&K has because S1 and S2 were always more consistent about properly setting the registers for solid object routines.

    I am not sure about S2&K; I never looked too closely into it (most things in SCH were ported directly from S3&K, not from S2&K). I know it is a separate ROM that uses some data from S2 and S&K ROMs, but has its own code. But I am not sure how much of this code is S2 and how much is S&K; I would guess that it is closer to S2, though, given that you cannot spindash when Knuckles is ducking after falling from a glide.
     
  6. MainMemory

    MainMemory

    Kate the Wolf Tech Member
    4,735
    334
    63
    SonLVL
    KiS2 is basically Sonic 2, with slight modifications to accommodate Knuckles.
     
  7. flamewing

    flamewing

    Emerald Hunter Tech Member
    1,161
    65
    28
    France
    Sonic Classic Heroes; Sonic 2 Special Stage Editor; Sonic 3&K Heroes (on hold)
    I edited the posts with a bug I had forgotten to mention before, as well as some exceptions to the bugs involving solid or platform objects pulling or pushing characters into terrain. Still need to do the post for platform and solid object collision.

    Edit: It is now on the Wiki. If anyone has a better place for it, please move it to, or suggest, an appropriate place.
     
  8. Cooljerk

    Cooljerk

    NotEqual Tech, Inc - VR & Game Dev Oldbie
    4,505
    201
    43
    Thanks for that writeup Flamewing!

    EDIT: To ask a follow up question -- what are the mechanisms used in hardware to do collision detection? 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? Or are the type of collision checks you described done entirely in software on the CPU through math?
     
  9. AURORA☆FIELDS

    AURORA☆FIELDS

    The cute one here Tech Member
    216
    24
    18
    Finland
    AMPS
    While that VDP bit can be useful in some cases, its much more difficult to pinpoint that specifically Sonic collided with a specific objects, not to mention there is no way to use multiple colliding objects (such as Tails, some other special objects). This is why its done on software despite it being notably slower, since you can be sure what object is hitting what other object.
     
  10. Cooljerk

    Cooljerk

    NotEqual Tech, Inc - VR & Game Dev Oldbie
    4,505
    201
    43
    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?

    EDIT: Also, just checking -- does the VDP bit check for a collision on a single specific sprite against all sprites, or does it detect collision between any two sprites? I.e. if there is any collision at all, regardless of sprite?
     
  11. flamewing

    flamewing

    Emerald Hunter Tech Member
    1,161
    65
    28
    France
    Sonic Classic Heroes; Sonic 2 Special Stage Editor; Sonic 3&K Heroes (on hold)
    None, because the only one provided by the VDP sucks:

    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.

    Entirely software.

    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.
     
  12. Cooljerk

    Cooljerk

    NotEqual Tech, Inc - VR & Game Dev Oldbie
    4,505
    201
    43
    much appreciated!
     
  13. Cooljerk

    Cooljerk

    NotEqual Tech, Inc - VR & Game Dev Oldbie
    4,505
    201
    43
    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.
     
  14. Fred

    Fred

    Taking a break Oldbie
    1,563
    117
    43
    Portugal
    Sonic 3 Unlocked
    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.
     
  15. Cooljerk

    Cooljerk

    NotEqual Tech, Inc - VR & Game Dev Oldbie
    4,505
    201
    43
    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...
     
  16. Pacca

    Pacca

    ASM amateur Member
    42
    16
    8
    Labyrinth Zone
    Sonic 2 CD Remix
    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.
     
  17. MainMemory

    MainMemory

    Kate the Wolf Tech Member
    4,735
    334
    63
    SonLVL
    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.
     
  18. Cooljerk

    Cooljerk

    NotEqual Tech, Inc - VR & Game Dev Oldbie
    4,505
    201
    43
    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.
     
  19. Pacca

    Pacca

    ASM amateur Member
    42
    16
    8
    Labyrinth Zone
    Sonic 2 CD Remix
    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.
     
  20. Fred

    Fred

    Taking a break Oldbie
    1,563
    117
    43
    Portugal
    Sonic 3 Unlocked
    flamewing already explained how this works. If only you would absorb anything of what people are trying to tell you.