Another Sonic Physics Guide implementation question

Discussion in 'Fangaming Discussion' started by Travelsonic, May 15, 2019.

  1. Travelsonic

    Travelsonic

    Member Member
    734
    0
    0
    So, for a fan game engine I have been developing on and off the last few years (busy life IRL ~_~) I have been wrestling with tile collision. Not so much in regards to dealing with height masks, and the like - that I am solid on.

    Right now, I have my engine set up so that collisions are checked only against tiles that are in a buffer containing the tiles on screen. Nothing too mind blowing there, seems logical as comparing against every tile in the entire tilemap would be way, way too odious.

    Problem is, I seem to have an issue where it will iterate through the buffer, and finds a tile that Sonic is colliding with that has a non-zero height mask, deals with it accordingly - then compares against the other tiles in such a way where Sonic will be on the tile briefly, and fall through, or fail to recapture the ground when he jumps off the solid tile.

    So in response to this, I made it so that if the floor sensors, midline censors, or ceiling sensors are within the bounds of said tile, then check the collisions - which seemed to work a lot better.

    My problem, however is this:

    I want my engine to replicate the original Sonic the Hedgehog engine as close as possible, and perhaps I am overthinking the hell out of things (which, given my post history here, is far from surprising) - but how does the actual game engine handle those sorts of things? Does it actually iterate through the entire tile map checking for collisions, or (more likely) does it just run through a smaller buffer of tiles to reduce how much work is done?

    It seems only Sonic's actual interaction with tiles is covered in the SPG, and not how the game handles any nitty gritty details beyond that, and I feel like there HAS to be something. ~_~
     
  2. MarkeyJester

    MarkeyJester

    My predecessors have nothing on me. Tech Member
    The coordinates of an object/Sonic are modular wrapped and shifted to reference the correct "byte" in the layout, this byte is the "chunk ID", this ID is then multiplied by the size of a single chunks' data, and used to reference the start of the chunk the object/Sonic is in, the coordinates are then modular wrapped and shifted again to reference the correct "word" in the chunk, this word is the "block ID", this ID is a combination of the block reference to use, as well as the flip/mirror status of the block, and the top & left/right/bottom collision status of the block in question (Sonic 1 will have just one top & left/right/bottom collision status, while Sonic 2 will have two of them for two different paths). Keep in mind, this is a block of 2x2 tiles, not tiles themselves so your setup might be slightly different if you are using tiles.

    The status of these blocks determines how the object/sonic will "detect" the collision (only detection that a block has any solid at all), for example the top solid is detected only if the object's Y speed is positive (the object is moving downwards). Provided the conditions are met, only then will the collisions' height mappings be taken into consideration. Assuming this is true, and the object meets the requirements, the block's reference number is used to reference against a collision map table, this is a table of "bytes", each byte represents the collision array block to detect against. If the block you are colliding with is block $24, then the $24th byte is referenced from the collision map table, assuming the byte in the collision map table you are referencing is $08, then collision array block $08 is used as the heights to collide against.

    This means not all blocks are checked against, only the block the object is coordinated against, this saves loads of time. Likewise, it checks the block from the level itself, it does not matter if that block is on-screen or not, it will always be collide-able. Your method of only allowing collision with on-screen blocks might be problematic if the objects in question are not on screen (i.e. about to spawn) or if Sonic outruns the screen in some way.
     
  3. Travelsonic

    Travelsonic

    Member Member
    734
    0
    0
    I do agree, my method may become problematic, and indeed already presented its share of noticeable issues.

    I THINK I kind of get what you're saying about how this works (the modular wrapping, shifting)… but could you elaborate a little on what exactly you mean, just in case?
     
  4. MarkeyJester

    MarkeyJester

    My predecessors have nothing on me. Tech Member
    Alright. For this example, we'll pretend the entire level is $4000x$800 (X by Y), and the levels' chunks are $80x$80 (128x128) in size (different Sonic games have different chunk sizes or different layout settings, so I've chosen the most likely and common one).

    Before I explain the modular/wrapping, I will explain the layout structure itself.

    The layout is constructed of one byte per every chunk, so a single byte in this layout represents a $80x$80 chunk in the level, that means $80 pixels horizontally and vertically is represented by 1 byte. The layout is arranged so that starting from the top left of the layout the bytes represent one chunk after another horizontally in a row until it reaches the end on the right, the level is $4000 pixels horizontally, divide that by the size of a chunk $80, you get $80 bytes of layout chunk ID's. You then start on the next row of chunks below, so that's another $80 bytes for the next row, then the next row after that is another $80 bytes, and so on...

    To know exactly which chunk an object is on, you can take the object's X and Y coordinates; for example $18F0 x $27E.

    What we'll do is divide the X coordinate $18F0 by $80, seeing as every 80 pixels is a single byte. $18F0 / $80 = $31, so the $31th byte in the layout row, is the chunk ID to read. Now you need to work out which row to check from. Each row is composed of $80 bytes each (as you might remember from the previous paragraph), so you take the Y position and divide that by $80 pixels ($27E / $80 = $4), and then you multiply that by $80 (number of bytes per row), 4 x $80 = $200. So the X is $31th byte in the row, and the $200 is the number of bytes to get to the correct starting row position (the $4th row), $200 + $31 = $231.

    $231 in the layout is the chunk that is at coordinates $1880 - $18FF x $200 - $27F.

    The division and multiply instructions for the 68k (and for most CPUs for that matter) are very slow, so a combination of shifting and ANDing are used to divide and modular wrap the coordinates. For example, to convert the X you would simply use a right shift by 7, this will perform the division of 80, but also clear the lower values, ensure that any value between $1880 and $18FF will always result in $31, you might also want to use AND to ensure that $4000 and beyond wrap back to 0, but this might be a limitation you can ignore. The Y instead of dividing and then multiplying, you would use an AND of FF80 to clear the lower values (keeping in multiples of 80) thus ensuring that $200 - $27E will always result in $200, and since the division and multiplication are both 80, you don't need to divide nor multiply, so the result is all ready. You add/OR the Y to the X and that is your relative position, here is some pseudo C code as an example:

    Code (Text):
    1. LayoutPos = ((X >> 7) & 0x7F) | (Y & 0xFF80);
    2. ChunkID = Layout [LayoutPos];
    Obviously, if your layout size is different, then you'll have different multiplication/divisions required.

    Now, this is just to get the chunk ID, you will need to use another combination of X and Y manipulation on the cordinates again to obtain the exact block within the chunk, similarly to how you would obtain the exact chunk within the layout.

    If you require more details I could write you up a full example of the entire process, but I think you might know what's going on by now.
     
  5. Travelsonic

    Travelsonic

    Member Member
    734
    0
    0
    Let's see if I understand some of this:
    So, when I think of a level map, I am really thinking of a mapping of chunks, where each chunk is a smaller mapping of blocks, and each block is a smaller mapping of tiles + height mask. The game uses Sonic's coordinates to pick out which chunk he is within, and then uses that info to find the correct block within to collide with, along with some info in the chunks themselves.

    Is that the very basic gist of it?
     
  6. MarkeyJester

    MarkeyJester

    My predecessors have nothing on me. Tech Member
    Pretty much...
     
  7. Travelsonic

    Travelsonic

    Member Member
    734
    0
    0
    Also am I correct about tile solidity (none, top, left/right/bottom or all) and the drawing direction (normal, backwards, upside down, or upside down and backwards) being stored in the block, and the plane priority being in the tile?

    Lots of Qs I know - had to stich together some of my understanding from reading info from other sources to stitch together an attempt at understanding certain things about tile drawing, planes, solidity, etc, and want to make sure I am getting it right.
     
  8. MarkeyJester

    MarkeyJester

    My predecessors have nothing on me. Tech Member
    That's pretty much it, though the tiles also have an additional flip/mirror on-top of that.

    [​IMG]

    As you can see, if a tile is flipped upside down, and then the block is flipped upside down, the tile becomes right side up. The tiles' flip/mirror is actually the graphics hardware, and the block being flipped changes the tiles' flip display.

    The collision also mirrors and flips as you'll see in the example image.
     
  9. Travelsonic

    Travelsonic

    Member Member
    734
    0
    0
    So, on top of having a draw direction flag for the block, I should add one for the individual tile as well, yes?
     
  10. MarkeyJester

    MarkeyJester

    My predecessors have nothing on me. Tech Member
    The tile flipping/mirroring is part of the hardware, the purpose of it is optimisation, allowing you to reuse tiles saving on VRAM. Since you creating this on a more advanced machine this should not be an issue for you, I think you could get away with not having flip/mirroring for tiles and still have the game accurate gameplay wise, it's a matter of perspective.

    I am merely showing you how it works, not telling you how you should do it, that's up to you~
     
  11. Travelsonic

    Travelsonic

    Member Member
    734
    0
    0
    Ah, gotchya.



    I think I will add it anyways, just because I like having that flexibility - to flip on the tile level, as well as on the block level. :D