Legend of Zelda (RPG game)

Use this forum to share and discuss Uzebox games and demos.
User avatar
D3thAdd3r
Posts: 3222
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Legend of Zelda (RPG game)

Post by D3thAdd3r »

I suppose Chickens in Choppers was the first, which makes sense being from Cunning himself. Maybe T2K could be considered the base of what became Simple SD, I guess my memory is not so great sometimes :roll:

Yeah more ram cost...it sucks. I never thought about the possible race condition before but now that I think about it, we might be able to dodge it without another buffer. I am surprised I overlooked this, and it basically negates the entire design I had going. The buffer would not be circular in this case, but the main program is always writing ahead of the song player so it can't interfere with it. This avoids the secondary buffer and explicit lock and there is simply no race condition even if it gets interrupted in the middle of writing to the buffer. Every frame the song player sets a variable of how many bytes it used(if this is not reset to 0 by the main program, the song player will not advance next frame, until it is 0..this is essentially a lock, because the main program could be in the middle of shuffling things to the front), and the main program moves all unused bytes in the buffer to the beginning of the buffer before resetting this to 0; this will be less cycle cost than circular buffer producer->consumer copy logic anyway. Mainly the song player will just stall if there is not enough bytes by not processing, and avoid other problems possible with some other solutions. It is probably obvious, but if the song player gets off track by even a byte, a crash is extremely likely if it interprets incorrectly a byte as a Note On, and another one as an invalid patch; at least very messed up music and incorrect looping if not a crash.

Another thing that could potentially help efficiency by a large chunk is to simply use an alternative format as opposed to the large and fully featured MIDI stream. Essentially just compress MIDI events into a smaller stream, which is designed to only handle things that Uzebox games use, and nothing else. This would save on buffer size perhaps by 66%, and help performance in general by a similar measure. Now that I saw that, and I think it is true, it must be done.

I am just thinking this out right here in this message so bear with me. If you look at the current MIDI player, every events is actually ~3 bytes because of the way MIDI is(which can handle a much larger superset of what we do on Uzebox). These are the things that are supported in the current flash MIDI player:
  • *Note On event(needs channel, note, and volume)
    *Song End marker
    *Loop Start marker
    *Loop End marker
    *Program Change(requires channel and patch number)
    **(the following 4 I believe can be eliminated)
    *Volume Control(needs channel and volume...this can be built into the note on events, combined with Program Changes if very intricate control is needed..)
    *Expression(I think this is nearly dubious for our purposes and should be designed into multiple patches using Program Change if actually required..)
    *Tremolo(I feel the same about this, I don't think anyone ever needed this in the MIDI stream for a game)
    *Tremolo Rate(..I almost suspect some of this support was for the MIDI_IN keyboard feature that never really got used)
So really I see just 5 command that actually get used in Uzebox music. The most common is Note On, and the one requiring most data is Program Change. If these are all 1 byte commands, we increase spaace and SD reading efficiency by ~66%. We give up just a couple things, which based on my experience are good trades. Here is my thought on it:

Code: Select all

0b*1*AABBBBB:
   Program Change: AA = channel, BBBBB = patch(sacrifice ability for 5 channel songs...use 5th channel for effects)

0b*0*AAABBBB:
   if(AAA < 5)
      Note On: AAA = channel(0-4), BBBB = volume(sacrifice control of volume to 15 unit intervals..4 bit volume is NES equivalent, never noticed an Uzebox game that required full 8 bits)
   else if(AAA < 6)
      Marker:
         if(BBBB == 0)
            Song End marker
         else if(BBBB == 1)
            Loop Start marker
         else if(BBBB == 2)
            Loop End marker
         else if(BBBB == 3)
   else//(AAA == 7)
      if(BBBB == 8)//we could support some more small commands as well...
         ...or we could define an extension, where the next byte is more information, allowing full 8 bit volume, 5 channel triggering etc...probably not much more twisted than the existing MIDI decoder and at worst taking the same space
         ...
The 1st trade-there can only be 32 different instrument patches for the entire game, which should be enough if you put all your sound effects after the instruments..this seems no trade at all for the bit packing efficiency gained. The volume trade

The 2nd trade-there are only 16 volume levels from silence to full volume for note events, but patches will still sound exactly the same just that there is more granularity of the volumes they start at..in my experience most Uzebox games play notes of all the same volume anyway and let the patches handle it..and 16 levels is pretty good anyway(again doesn't affect patch commands at all).

The 3rd trade-now this might sound crazy, but the way the bitpacking works out(someone prove me wrong here, I would be grateful), there simply needs to be another bit to have all the above and also be able to specify Note On events for 5 channels. This does not seem a bad sacrifice anyway. Any 5 channel game should use 0-4 for instruments and the 5th channel for effects. Just a few music only demos required all 5, and this solution is not aimed at absorbing inefficiency for the sake of being used for demos.

Er..there is a 4th trade that midiconv output will need to run through an additional step for compression. I will simply make a conversion program to facilitate this and do the extra step;don't need another project messing with midiconv for now.

The last concept is attacking the huge inefficiency that is the delta time read after every single event. Instead of that, the first byte of every frame can be the number of commands that happen this frame. This has the added convenience that we can quickly calculate if we have all the bytes we need for this frame without decoding the data bytes(we know they are all 1 byte commands unless extensions are implemented). After the number of commands has been processed, the last byte specifies how many frames of "rest" happen before the next event, which is just 1 byte instead of multiple. This adds the restriction that there cannot be longer than 255 frames without an event(never seen this in an Uzebox game). If you needed that for some ridiculous reason, one could do a silent Note On followed by more rest to manually overcome this "limitation". I think this is massive, though a bit of a pain to implement. I guess when I was so optimistic about tiny buffers, I was thinking this direction but then going lazy and trying to do it easier.

Anyway maybe this is a bit much of a rant for this thread and it can be moved to a separate one if necessary. I do think this is possible, not that it is necessarily easy to do all that, but just running it through my head we are looking closer to those small buffers I originally quoted. I have been procrastinating on this for several years now :lol: Seeing as you saved the forums with your bot, I think the least I can do is to finally do this which I needed for several games anyway. Any concerns on those changes at all?

Edit-damn I overlooked the note part of Note On...not sure how to pack that into 1 byte after all..so 2 bytes for note on events!
User avatar
Artcfox
Posts: 1382
Joined: Thu Jun 04, 2015 5:35 pm
Contact:

Re: Legend of Zelda (RPG game)

Post by Artcfox »

D3thAdd3r wrote:The buffer would not be circular in this case, but the main program is always writing ahead of the song player so it can't interfere with it. This avoids the secondary buffer and explicit lock and there is simply no race condition even if it gets interrupted in the middle of writing to the buffer.
Have you thought of using a lock-free circular buffer? I wrote a tutorial explaining how the one I wrote works over on avrfreaks, and I've used it in quite a few AVR projects: http://www.avrfreaks.net/forum/tut-c-re ... r-consumer

You can write multiple bytes (a packed struct) to the circular buffer without locking anything and without having any race conditions or atomicity problems, and the consumer will never read a half-written struct.
The default implementation spins if the queue is empty, but you can easily modify that so it does something else.
D3thAdd3r wrote:Er..there is a 4th trade that midiconv output will need to run through an additional step for compression. I will simply make a conversion program to facilitate this and do the extra step;don't need another project messing with midiconv for now.
I recently rewrote midiconv in C++, and it is still relatively fresh in my mind, so let me know if I can help. It is now part of the main Uzebox git repository, and should be built by default when you do a make, since it has no Java dependencies.
User avatar
D3thAdd3r
Posts: 3222
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Legend of Zelda (RPG game)

Post by D3thAdd3r »

Artcfox wrote:I recently rewrote midiconv in C++, and it is still relatively fresh in my mind, so let me know if I can help.
Yes that is a quite nice rewrite, I may have to pick your brain on it at some point to actually make this format usable for most instead of my normal manual handling of data, copy+paste, etc.

That is an excellent write up there and I even got some points of knowledge out of there especially I did not know about that ATOMIC_BOCK for 16+ bit write, that could have uses! Looking at it, my circular buffer implementation even wasted some bytes in comparison... :oops:

Let me digest this for a bit...damn if my late night coding didn't literally make me hallucinate about a race condition where none is necessary. Good diagrams in your following post BTW. Now, I think I literally ran into this issue by having a separate byte count, where otherwise there is no race condition at all. The solution being just volatile with no locks as originally planned, before I imagined the requirement of a more exotic solution...heh, all 8 bit writes here, I think misunderstanding some other yet unknown bug in my code led me to believe this. I will redo things with this new angle.
User avatar
Artcfox
Posts: 1382
Joined: Thu Jun 04, 2015 5:35 pm
Contact:

Re: Legend of Zelda (RPG game)

Post by Artcfox »

D3thAdd3r wrote:That is an excellent write up there and I even got some points of knowledge out of there especially I did not know about that ATOMIC_BOCK for 16+ bit write, that could have uses! Looking at it, my circular buffer implementation even wasted some bytes in comparison... :oops:
Thanks, just be careful using ATOMIC_BLOCK, because that disables all interrupts. The whole reason behind the way I wrote that circular queue was to avoid disabling interrupts at all.
User avatar
D3thAdd3r
Posts: 3222
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Legend of Zelda (RPG game)

Post by D3thAdd3r »

I reimplemented it, and what do you know it seems there really is no race condition even on looping with this new design. These "race conditions" were actually that I did not take the time to walk through the song data manually to realize what was happening. The way things work, required stepping through the data manually to understand what the flash player skipped and make sure I remove those elements(spurious delta times on loops, end of song markers after end of loop markers, etc. etc.), since this does work considerably different than a non-buffered straight pointer. Basically these "race ghosts" I saw was just naive formatting of song data.

So it works and loops with a single buffer and no locks. Right now the furthest I have stress tested this is a 24 byte buffer, loading just 3 bytes per frame, on a medium tempo song from Block Boy with rapid precussion;no issues with the standard non-compressed MIDI. I think it will need to be compressed to go much lower resources than this, and I plan to. It never discards bytes even when the buffer reads "too far" since it is not aware of the MIDI format, it doesn't matter since that data after the normal song data matches the data after the loop start(format slightly changed to account for spurious deltas). Adjust the read offset in user code when it is detected, boom works! I will clean this up and do more testing to make sure, but it looks like success. Thanks Artcfox, sometimes another perspective, some info, and sanity check by someone else makes all the difference :ugeek:
User avatar
Jubatian
Posts: 1564
Joined: Thu Oct 01, 2015 9:44 pm
Location: Hungary
Contact:

Re: Legend of Zelda (RPG game)

Post by Jubatian »

For interrupts: Be careful with disabling, it normally wouldn't work too well. The video routines can only eliminate a 5 cycle jitter, so a longer than 5 cycle interrupt disable could potentially cause slight variances in the video signal. This is enough for a 16 bit read or write (two ld or st instructions between a cli and sei), but nothing more. You should possibly do that using an asm routine to make sure only the necessary instructions are placed between the cli and sei.
User avatar
D3thAdd3r
Posts: 3222
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Legend of Zelda (RPG game)

Post by D3thAdd3r »

For this it turns out no "cli" is necessary, because the song player and the main program do not modify the same things. The only thing that would be an issue of atomicity, is the loopEnd. The song player, upon detecting the 'E' marker, sets loopEnd to this position and continues on. The main program is responsible for checking this every frame, and if it has been set, make adjustments to the read pointer based on how far past this it is currently reading. Then it sets it to 0 so it doesn't re-detect it next time through, and the song player will set it again when it loops back through the song, ad infinitum. That is the closest thing to a lock required, with the new setup. The 16 bit write that happens in the song player should be atomic in all cases as far as the user code is concerned, since it runs until it is complete before returning control.

Maybe I should make a new thread to rant about this.

Edit - streaming music was developed in this thread.
User avatar
D3thAdd3r
Posts: 3222
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Legend of Zelda (RPG game)

Post by D3thAdd3r »

So streaming music I think is in some usable state for development. I am going to try and find the source MIDIs I used for the couple songs I sent and use mconvert to throw them together for use, and figure out which songs are missing...getting it to integrate with the code is going to take some skill @nicksen782 for the most part I think the sound effects are pretty good and very close to the NES version unless you have some things you notice are missing or need a bit of refactor. The only effects I know of that need work or don't exist are the PCM style for boss roars and link getting hit. I think I can get something acceptable, but for the boss roar there is no way I can emulate that iconic sound...obviously this is the right trade to make over the massive PCM space it would take(...or could we stream 1bit ADPCM in a custom HSYNC?). With music entirely offloaded, is there any possibility for say 2K for PCM, or are things very tight even with offloaded music? 2K I mean literally just for the boss roar, if it seems that important.
User avatar
nicksen782
Posts: 714
Joined: Wed Feb 01, 2012 8:23 pm
Location: Detroit, United States
Contact:

Re: Legend of Zelda (RPG game)

Post by nicksen782 »

Hey all!

Zelda is still on my mind but I am working on Bubble Bobble now. Actually, lots of ideas and techniques from Zelda I brought to Bubble Bobble. I've added new ideas and completed a few others. For example, I mentioned in a previous post that I wanted to create a sort of dynamic sprite assignment. I have that now. I can have double the sprites. I blit one half and then the other. Each time I blit them I all shift the blit order or the flicker is spread out a bit. Plus, technically I have better use of the ram tiles since all 26 (at the moment) can go to whatever is presently blit. Additionally, each character gets a 'slot'. The next available slot number is used with with new character spawn.

With these techniques I could lower the RAM_TILE_COUNT in Zelda and blit more enemies and with less annoying flicker (although there will be some by design, it will vary what is flickered.)

When I get back to Zelda I will have lots of new toys to play with!
Post Reply