Objects: How does the engine know WHEN to load them?

Discussion in 'Engineering & Reverse Engineering' started by tokumaru, Jan 19, 2008.

  1. tokumaru

    tokumaru

    Member Member
    807
    0
    16
    Rio de Janeiro
    Platformer for the NES
    Hello guys! Because of the limited number of trial posts, I'll first give you a short description of my current project, and then I'll ask the actual question, OK?

    I'm a big Sonic fan since the first game came out (not such a big fan of the newest ones, though), and 'till this day the Mega Drive/Genesis Sonic games are still my all time favorites. Since I started programming, my dream was to code a decent Sonic game from scratch.

    Since I'm a big fan of the NES, I learned how to program for it a few years back. I happen to really like the idea of pushing the system to it's limits, so I just decided to code my sonic game for the NES. I wanted to do better than the pirates that exist for the NES (Somari and Jurassic Boy), because those are pure crap (the physics, more than anything). I also wanted to do better than what was done for the SMS/GG, which are nice but have a few problems, such less-than-smooth movement, repetitive graphics, small levels... I wanted the opposite of all that, becuse I really believe we can achieve more with 8-bit hardware. So the goal is to go beyond all other 8-bit games, getting as close to the 16-bit series as much as possible.

    Everything is comming along pretty nicely: The scrolling engine works perfectly (it's able to scroll 16 pixels per frame in either direction, both if necessary), in levels that can be really large (built with 256x256-pixel "blocks" - like in Sonic 1 - each indexed by a byte in a level map of up to 1024 or 2048 bytes, depending on how much RAM I have left in the end), larger than anything I've seen on the NES. The sprite engine works well too (although I feel it could be optimized a bit). Anyway, there is still a lot of free processor time that will be used to process the active objects, as well as Sonic (or another character I'm not revealing yet), and I suppose that will be the most intensive task to perform, so the rest of the engine must be very efficient.

    I often come here and read about all the things you guys have discovered about the original engines, and I usually try to have the things in my game work in a simiolar fashion, as much as the hardware constraints permit. It's not unnusual having to rething something so that it behaves the same but is implemented in a way that requires less resources.

    I hardly go look at the disassembly of the games directly, because I don't want to copy that much. Plus, I'm not fluent in 68000 assembly (as I am with 6502 which is what the NES uses), but even when I'm able to follow the program flow with the aid of some documentation, there are a lot of details about the engine (and the Mega Drive hardware) that prevent me from fully understand the logic.

    Here's the actual question:

    Thing is that I haven't found much info about how the original engine goes about loading the objects
    and this is the first real problem I'm facing. I have thought about a few different solutions, and although all of them could've worked, they all seem to have flaws. One of them is too slow, another one imposes limitation on object placement, another needs too much RAM, and so on.

    What I'd like to know is if you guy could give me a description of how the main game engine finds in the object definitions the objects that are in range and should be loaded. By looking at Sonic 1's disassembly, I can see that this is done by the "ObjectsLoad" routine, but I'm having a hard time figuring out what it does with the object definitions.

    I'm aware the the solution used by sonic Team may not apply to my engine or to the system I'm programming, but I'm running out of ideas here, and before I decide to go on with an sub-optimal design, I decided I'd ask you guys about it.

    Thank you very much for the help!
     
  2. jman2050

    jman2050

    Teh Sonik Haker Tech Member
    633
    0
    0
    It's a bit weird, but basically, the object loader treats the level as a bunch of horizontal 'chunks' about 128 pixels wide. I MAY be wrong, but the game has two boundaries, one behind the camera and one in front of the camera. As the camera moves forward, when the farthest boundary is reached, it iterates through the object list (which SHOULD be arranged in order of location, top-to-bottom and then left-to-right) and loads all objects that fall between the farthest boundary and 128 pixels ahead of that boundary. Then the boundary is updated. Same applies to when going backward. Note that there are NO boundaries for object loading from top-to-bottom. Only horizontally. Also note that objects typically delete themselves, using a general routine that checks if it is 'out of range'

    Hope this helps.
     
  3. Upthorn

    Upthorn

    TAS Tech Member
    239
    0
    0
    The object list is only arranged in order of left-to-right, but other than that you are correct. it checks the camera coordinates, truncated to the last $80 pixels. Then it adds $240 to that, (which will be the next $80 pixel boundary past the camera), and objects in the layout between these two boundaries are loaded. There's a little more to it than that, like checking which direction the camera moved so that new objects are only loaded from the zone that just entered range, but that's the basic routine.
     
  4. tokumaru

    tokumaru

    Member Member
    807
    0
    16
    Rio de Janeiro
    Platformer for the NES
    Thanks guys. That is indeed the most logical approach to the problem. But that would require a lot of computation... specially since this system only works horizontally... if a level happens to be somewhat taller, there would be a lot of objects to process and load, vertically. In addition to spending a lot of time processing a great amount of objects, I have only 32 RAM slots for active objects (against 96 in the original game, right?).

    I'll probably go with my very first idea, where the objects were grouped by screens, and for each screen in the level map there'd be a pointer to said groups, and I'd only have to do anything when the camera entered a new screen (the "screen" is actually a 256x256-pixel block). The disadvantage is that the objects that are too close to the edges of a screen end up being loaded in the very same frame as they need to be displayed. If the object is fully inside that screen this isn't really a problem, but if any parts of it happen to cross the boundaries of the screen, those parts will suddenly appear, instead of scroling smoothly into view. It would be even worse in the case of objects that are drawn using background tiles (this is necessary because of the sprite limitations), those (the parts that crossed screen boundaries) won't even appear (the object must be loaded while the background is drawn for it to be displayed properly).

    Another option would be to do it somewhat like you guys described, but using 2 sorted lists pointing to the object definitions, one sorted by X and the other by Y coordinate. Then, after every movement of the camera, I'd make sure to adjust pointers to the first and last objects in range (that would be 128 pixels before and after the camera), in each direction. Only objects appearing in both lists should be loaded. For that I'd actually flag and unflag objects that are in range horizontally as the camera moves, so that only a small number of objects is manipulated at once. Then the complete list of vertically in-range objects is scanned, and any objects that are flagged should be loaded, because that means they are in range in both directions.

    The first option sure is faster, but I feel like trying the second one so that I don't have to worry about technical issues while placing objects around the level.

    Oh, my objects are like that too. Each one has their own routine(s), and there is a set of routines they can all use, one of them being the one that checks if they should be unloaded for being too far from the camera.

    Anyway, I'll probably work on other things for a while, until I find the optimal solution for this. If anyone happens to have any ideas, feel free to share them, any help is appreciated. Thanks again! I hope I'll have something to show you all soon! :(
     
  5. LocalH

    LocalH

    roxoring your soxors Tech Member
    3,256
    0
    16
    wouldn't you like to know
    Super Guitar Hero II
    O/T: Hey, I know you from NesDev, I'm a lurker and occasional poster there. Welcome to S2B!
     
  6. Sazpaimon

    Sazpaimon

    Tech Members Tech Member
    1,208
    0
    16
    fixed
     
  7. Upthorn

    Upthorn

    TAS Tech Member
    239
    0
    0
    If space is a concern, something you could try is just decreasing the border size. Also remember that the horizontal NES resolution is 64 pixels smaller than the Genesis res. So if you were to bring it down from 320 + 128 + 128 to 256 + 32 + 32, you've almost halved the loading area. You will end up having to load objects more often, but you'll have fewer of them in range at a time.
     
  8. nineko

    nineko

    I am the Holy Cat Tech Member
    Not to derail this topic, but are you taking in account the time you need to run the sound/music engine?
     
  9. tokumaru

    tokumaru

    Member Member
    807
    0
    16
    Rio de Janeiro
    Platformer for the NES
    Thanks!

    That's good too! =)

    Anyway, I guess I found the answer... I'm mixing my first idea with the way it works in the original game, as jman2050 and Upthorn described to me. The objects are grouped according to the 256x256-pixel block they are in, and for each of them in the level map there is a pointer to to the object definitions of that block. Then, the objects are divided in 4 sub-areas of 128x128 pixels. This way I can easily locate the objects with more precision. When the camera goes beyond the half of a 128x128 block, a new column (or row, if moving vertically) of 4 128x128 blocks is processed.

    The following is a small level of 1024x1024 pixels. There are 4x4 256x256-pixel blocks, each divided into 2x2 128x128-pixel blocks. The top left corner of the camera is marked by a "C". The 128x128-pixel blocks with an "#" inside them are the ones where the currently loaded objects came from.

    Code (Text):
    1. +---------+---------+---------+---------+
    2. |   .   |   .   |   .   |   .   |
    3. |   .   |   .   |   .   |   .   |
    4. |.........|.........|.........|.........|
    5. |   .   |#   .#   |  # .   #|   .   |
    6. |   .   |   .   |   .   |   .   |
    7. +---------+---------+---------+---------+
    8. |   .   |#   . C---------+ #|   .   |
    9. |   .   |   . | #|#   . |  |    .   |
    10. |.........|......|..|......|..|.........|
    11. |   .   |   . | #|#   . |  |    .   |
    12. |   .   |#   . |  | . | #|  .   |
    13. +---------+------|--+------|--+---------+
    14. |   .   |   . +---------+  |    .   |
    15. |   .   |#   .#   |   #.   #|   .   |
    16. |.........|.........|.........|.........|
    17. |   .   |   .   |   .   |   .   |
    18. |   .   |   .   |   .   |   .   |
    19. +---------+---------+---------+---------+
    20. |   .   |   .   |   .   |   .   |
    21. |   .   |   .   |   .   |   .   |
    22. |.........|.........|.........|.........|
    23. |   .   |   .   |   .   |   .   |
    24. |   .   |   .   |   .   |   .   |
    25. +---------+---------+---------+---------+
    This way I'm keeping most of my original design, but now the objects are loaded some time in advance before they have to be displayed, something essential for free placement of background objects. This should be fast, because hardly will I need to load objects vertically and horizontally at the same time. The big advantage is that by knowing the coordinates of the blocks I want, I can locate them directly, without having to look for them in a sorted list, which takes time.

    Space is not much of a concern when compared to computation time. Reducing the borders would result in a smaller area to process, something that should cut down the time needed to process the new objects, since there'd be fewer of them. But still, the complexity of this approach is that I must do this vertically as well, and intersecting the 2 "active areas" is the complex part.

    I don't have any music yet. I know that I should take into consideration the time needed by the sound engine, but I don't expect it to use a huge chunk of the avaliable time. I'll probably need help when the time to add sound comes, because that's something I'm not very good at... I'm much better with graphics! =)

    Currently, The worst case I've met was when both a column and a row of metatiles were updated (in practice that shouldn't happen very often), with 3 big sprites being displayed, and that used 1/3 of the total time avaliable. There are still a few sub-systems that have not been programmed yet, such as palette rotation, pattern rotation and metatile updates, but none of those is an ugly CPU-hogging loop, so I don't expect those to cause a huge impact.

    I expect the music routine to take less time than updating a row or a column, and as long as I don't have to render both in the same frame things will remain pretty balanced.

    You can see why I can't waste much time looking for objects... and why I shouldn't have many "smart" ones loaded at a time. Another option to make better use of the avaliable time is to alternate between tasks each frame, instead of calculating everything every frame... Some objects might even not need processing every frame, if they move slowly or not at all.
     
  10. Bibin

    Bibin

    DON'T LET THE SUN LAUGH AT YOU. Member
    882
    0
    0
    New York City
    Ghost in the Machine
    Can I make you some NSF's of Sonic music?
     
  11. tokumaru

    tokumaru

    Member Member
    807
    0
    16
    Rio de Janeiro
    Platformer for the NES
    Wow, thanks for the interest! =D

    I'll sure need all the help I can get when it's finally time to add the music. The problem with NSF's though is in the different sound engines they use... I most likely will use a custom sound engine in my game, one less generic, and thus more compact and faster.

    I'll probably have the help of the people at NESDEV to design this engine, and I don't know if it will be possible to make a tool to compose the songs or if that will have to be done by hand... Hell, music really isn't my area of expertise! O_o
     
  12. Tweaker

    Tweaker

    Misfits
    12,389
    0
    0
    Perhaps you might be interesting in developing a sort of NES SMPS clone? If you do, then I can strip the actual song data and use that for your port.
     
  13. Bibin

    Bibin

    DON'T LET THE SUN LAUGH AT YOU. Member
    882
    0
    0
    New York City
    Ghost in the Machine
  14. tokumaru

    tokumaru

    Member Member
    807
    0
    16
    Rio de Janeiro
    Platformer for the NES
    That NSF is great, I really like it!!!

    I can't do this by myself because I'm not good with sound. I'll probably ask for help from you guys and the NESDEV guys to get me through this one! =)

    On a side note, the game is not actually a port... it's an original game, with an original story and original levels, enemies and bosses. Well, some of the content of the original games might be present, as a sort of tribute to them. I want it to feel like one of the Gen/MD games as much as possible, but that's it.

    For this reason, I don't think I would use a direct port of the GHZ music. You get me, right? I really appreciate the will of everyone that wants to help. And if you really want to, all the help is welcome. It's just that it may be a bit early to think of something as specific as the music.

    Now that I figured out a way to handle the objects, I'm programming that solution into the engine. When I'm done, I'll put some meaningful graphics in, code a few objects, and them I'll show everyone what I got. Really, the thing is a mess right now and there'd be no point in showing it.

    I'm also really interested in what kind of things you'd like to see in this game... I always meant to ask this here, because you always have such good ideas for your hacks, and you are Sonic fans, so there really isn't anyone better to get opinions from! =)

    Soon I'll tell you all my ideas, and I'll be more than happy to hear your suggestions/criticism. Talk to you soon!
     
  15. Bibin

    Bibin

    DON'T LET THE SUN LAUGH AT YOU. Member
    882
    0
    0
    New York City
    Ghost in the Machine
    If it's not a port, then might there be multiple characters?
     
  16. nineko

    nineko

    I am the Holy Cat Tech Member
    The NES has 4 channels (well, up to 6 if you use the DMC and the VRC6 channels), I don't know how good it would be to directly use SMPS songs.

    By the way, whatever format you're going to use, and whoever is going to compose the songs, I will offer my help if you need a tracker or a converter of some sort.
     
  17. Bibin

    Bibin

    DON'T LET THE SUN LAUGH AT YOU. Member
    882
    0
    0
    New York City
    Ghost in the Machine
    I've already made some NSF's. It has 2 square wave, 1 triangle wave, 1 noise generator, one DPCM, and I'm pretty sure the rest of them are Famicom only.
     
  18. Bibin

    Bibin

    DON'T LET THE SUN LAUGH AT YOU. Member
    882
    0
    0
    New York City
    Ghost in the Machine
  19. nineko

    nineko

    I am the Holy Cat Tech Member
  20. Bibin

    Bibin

    DON'T LET THE SUN LAUGH AT YOU. Member
    882
    0
    0
    New York City
    Ghost in the Machine
    This game needs it's own thread.

    I made some more music; a bonus stage, and lots of sound effects in NSF format.