Temporal Flux Journal

[Geiger]

I have been toying with the idea of starting this thread for awhile now.  Is there any interest in seeing the sort of coding problems a program like Temporal Flux encounters, and how they are resolved?  This will involve tidbits, lengthy explanations, or anywhere inbetween.  Occasionally, I may also post a little code to better illustrate the issue.

I think there is a lot that could be said given the comprehensive nature of the program.  The primary barrier would be in my ability to adequately convey the information to the audience.  I have never posted at length on a regular basis, so I am not sure if I would be good or bad at it.

The other issue would be the irregular posting schedule.  I would only be posting when I am actually working on the project, and when interesting issues occur.

(As this primarily involves code problem solving, I have posted here.  But if this better belongs in Personal Projects, feel free to move the thread.)

---

I have been running into an issue with the original ROM running out of free space when all data records have been marked as modified, without changing the data.  This is unusual because, in theory, if none of the data has actually been changed, it should not take up any more space than it did originally.  The cause appears to be several things.

The first was somewhat easy to find.  Several of the record types lived in space not marked as usable to the program.  Even worse, some of the record types were only partially marked as usable.  For example, I had only marked the primary group of Location Maps as usable, but there are two or three smaller groups of maps stored in other places in the ROM.  Tracking this down manually would have been time consuming and error prone, comparing the list of usable space to the entire list of offsets (which contains records, unused space, and code).  Fortunately, this process could be automated.  After each of the records retrieved its data, it then checked the free space list to see if its home address was available.  If not, it popped up an error message.

Unfortunately, this does not appear to be the only problem, as even after correcting for all of the error messages, the ROM still runs out of space.  It is not immediately clear why, but I suspect it has something to do with new records being created.  Flux can split an overlapping record into two new ones, or create entirely new ones in cases where there is room for more of that type.  There is little point into looking into this because it is not falsifiable:  new records will always take up more space.  I need to make sure there are no other causes before I try to eliminate this.

Maybe Flux is not saving the records as efficiently as the original ROM, taking up more space.  This is the avenue I am currently investigating.  Hampering my progress, Flux has never saved compressed data in a matching one-to-one manner as the original game.  While it still works, the compression addresses never matched up.  The fix here appears to be surprisingly simple.  Instead of looking for matching patterns to compress from the beginning and moving forward, it seems the original tool started at the end and worked backward.  Merely changing the end I started at appears to have made it sync up and post one-to-one results.  I was so surprised that was all it took that, at first, I figured the game was not actually saving the data and was just dumping the ROM back out to file again.  I had to test it several more times and even actively debug the program and physically see it doing the work to believe it.  This will help the investigation immensely.

That is all for now.  Let me know if there is any interest in more.

[TheMage]

I'm interested! I myself have been using Temporal Flux for years. I know how to use it but damned if I know much about the coding! So anything that helps me understand it sounds good to me

[MathOnNapkins]

Interesting idea, I'd be interested to get some insight on your approach to managing how data gets saved back into the rom. Afaik Temporal Flux is not open source, right?

[Geiger]

Temporal Flux is not open source, right?

The main program is not currently open source, no.

I'd be interested to get some insight on your approach to managing how data gets saved back into the rom.

This is quite a lengthy topic, as it took me two years to get beyond the most basic saving, five years to get everything compartmentalized, and eight years to bring me to my current project-oriented design.  Do you have a more specific interest?  There is a lot of detail I could get into, I'll start with some very broad strokes here about how the data is treated.

First, its important to note that loading data and saving it are equal endpoints traveling in opposite directions.  Thinking of them as unrelated or wholly separate processes will not produce good code.  To this end, Temporal Flux employs record based loading and saving (as detailed in the Temporal Flux Plugin Architecture).  Each record contains all of the information needed to load the data and save it back, including extra pointers, custom data parsing, and more.

Each record may also have upto three states, though anything more than one is usually abstracted by the form that displays it, not something stored in permanent memory.

The most primitive state is identical to the way the record appears in the original ROM data.  Most of the 2000+ individual records Flux extracts only exist in this form as the data is simply not complex; there is no further need to parse the information.  More complex records only exist in this state briefly after being loaded or before being saved.  Examples of records in this state include Location Properties or Song Instruments.

The middle state is pre-parsed.  The data is complex, almost always not of a fixed length.  This makes it difficult to determine where a specific datum of interest is or should be located, so the data is parsed into a more readily accessed form.  Usually the data still bears a marginal resemblance to the original.  Example of records in this state include Overworld Exits (and previously Location Events).

The most complex state is totally abstracted.  Even a parsed form would be totally unusable to the display of the data (or make it much harder to use than is useful).  The data will be converted and kept in a useful form in perpetuity.  Conversion back to the original happens only in a temporary copy during save.  This state is common for compound records like Events but is also used for records as simple as Strings.  The new project approach keeps the data in this state permanently, even between sessions.  This allows for several enhancements, such as storing meta-data directly in the record.

Flux has always used First Fit for bin packing.  I had each of the separate record type saving processes manually ordered so that the typically largest record type saved first.  But as of v3.00 it uses First Fit Decreasing.  The records had been universalized, so I could tell an individual record to save instead of an entire record type.  This allowed me to put them in a sorted queue and ultimately make much better use of the ROM's free space.

Flux maintains a Free Space map.  This map contains all of the unused space, as well as all of the space used by editable, movable objects.  On Save, the unmodified records claim their space out of the map.  Then the modified records try to save themselves back to their previous home, if they can fit.  If they do not, they will save to a new location.

[MathOnNapkins]

This is quite a lengthy topic, as it took me two years to get beyond the most basic saving, five years to get everything compartmentalized, and eight years to bring me to my current project-oriented design.  Do you have a more specific interest?

The topic of most interest to me is having some kind of estimate as the program runs of whether there will be too much data when the time comes to save the ROM. As in, do you run simulations periodically or only when the time comes to save the ROM? From a user's perspective, it would be a bitch to do a bunch of editing only to find that the data generated is twice the feasible size a ROM can support (4 megabytes, 6 megabytes, whatever the practical decided limit is.) Naturally, it might not be feasible to estimate compressed data size since that could take a chunk out of processing time.

First, its important to note that loading data and saving it are equal endpoints traveling in opposite directions. Thinking of them as unrelated or wholly separate processes will not produce good code.

In my situation the data will not always be saved in the same format that it was loaded as, so I don't think it wholly applies. That is, I've made a distinction between "first time loads" and subsequent loads. The subsequent loads would always load and save data in the same format.

This allows for several enhancements, such as storing meta-data directly in the record.

That's interesting, any details on what meta-data is being stored and is it uniform across records? I'm trying to work that out in my own code currently. Typically in the case of data that I want to provide human readable names for, and perhaps also the size of the record.

Flux has always used First Fit for bin packing.  I had each of the separate record type saving processes manually ordered so that the typically largest record type saved first.  But as of v3.00 it uses First Fit Decreasing.  The records had been universalized, so I could tell an individual record to save instead of an entire record type.  This allowed me to put them in a sorted queue and ultimately make much better use of the ROM's free space.

I'm dreading the day I have to delve into that stuff. I've never been much of a sort or packing algorithms guy, as I was a math student, not a comp sci student. Currently I just save linearly and with regard to bank boundaries, which can't be good for efficiency. Course, the game I work on is Zelda 3, so it's a 1 megabyte ROM with the potential for a lot of expansion. Doesn't mean I should be wasteful either, though. For example, if all graphics and maps were saved as decompressed rather than compressed, it would instantly double the size of the ROM binary. Not that I would do that without good reason.

On another note, have you changed any of the compression formats used in Chrono Trigger? Just curious, as I've sometimes found existing formats and schemes to be sup-optimal in practice. Or in other cases they place restrictions on the user for editing data. As CT is a late model SNES game, I would expect it to be a lot more well designed and flexible, but you're the expert on that.

Flux maintains a Free Space map.  This map contains all of the unused space, as well as all of the space used by editable, movable objects.  On Save, the unmodified records claim their space out of the map.  Then the modified records try to save themselves back to their previous home, if they can fit.  If they do not, they will save to a new location.

Any insights on how that's implemented? A map of unused bytes? Or is it broken down by some size, like 256 bytes, kilobytes, etc?

[Geiger]

The topic of most interest to me is having some kind of estimate as the program runs of whether there will be too much data when the time comes to save the ROM. As in, do you run simulations periodically or only when the time comes to save the ROM? From a user's perspective, it would be a bitch to do a bunch of editing only to find that the data generated is twice the feasible size a ROM can support (4 megabytes, 6 megabytes, whatever the practical decided limit is.) Naturally, it might not be feasible to estimate compressed data size since that could take a chunk out of processing time.

Such an estimate is not especially useful, due to bank boundaries and not all of the space being together to start with.  There might be a full 64k of space left, and the record in question may only be 512 bytes long.  But knowing both of those things does not help if all of the chunks of available space are only 256 bytes wide.  Even keeping track of the largest chunk of space would not help much, unless you are saving every record back to the ROM after every modification (which would lead to serious fragmentation).  The only way to know (for sure) if a specific record will fit at modification time is to sort and fit all of the records every single time.  For a small set of records without much compression, this may be doable.  But for Temporal Flux, this can take a couple of seconds to a few minutes (depending on the number of modified records).

In Flux, this is not really a large problem anyway.  If a record cannot be fitted, it throws up an error message and the user can expand the ROM directly from within the program.  With the new project approach, even running into the 6 meg barrier is not an immediately dire problem, since all of the data will still be stored to the hard drive anyway.

That's interesting, any details on what meta-data is being stored and is it uniform across records?

Meta-data (beyond what describes a Flux file) is currently only stored on a per record basis, as I do not see any commonality across all records.  And I have only implemented it in a few areas so far as there is so much work left to get the current WIP back into working condition.  The ones that immediately come to mind are Event Command labels and also false ECs, such as a comment or functionary link.

I'm dreading the day I have to delve into sort or packing algorithms

It is not really as hard as you may think.  Quicksort is sort of universally recognized as the best algorithm, so most languages have it implemented somewhere (you usually just need to tell them how to determine which is more and which is less).  The main issue will be implementing bin packing, but its not exactly outrageous either.  It mostly consists of defining a 'bin' and means of moving onto the next one if the current one will not fit.  My 'Freespace' class is effectively a bin packer.

On another note, have you changed any of the compression formats used in Chrono Trigger?

I have given some (non-serious) thought to implementing a zip algorithm.  But I have never touched the existing compression routines because it is important that they be able to work in real time, which they already do (if it ain't broke...).  And as a general rule, I try to touch as little of the code as I possibly can, even if it would make my life easier.  Even the few minor ASM hacks I have created are entirely optional.  I try to work within the boundaries of the original engine, because the more I change it the less of the original game remains.  The point is to edit Chrono Trigger, not something I cooked myself.

A map of unused bytes? Or is it broken down by some size, like 256 bytes, kilobytes, etc?

I am probably making it sound more complex than it actually is.  At the simplest level, it is just a list of paired addresses marking the start and end of a chunk of free space.  The addresses change and new entries are added as needed when records claim their space or get fitted for saving to a new location.  The container class also has built in functions for adding space back, which requires sorting (the new entry is placed on the end initially) and possibly collapsing (if the space bridges the two entries on either side).

I can provide more detail at a later date, as I do not have immediate access to my code.
April 12, 2011, 09:06:51 AM - (Auto Merged - Double Posts are not allowed before 7 days.)
Er, what example I was going to share is not coming to me.  Is there something you would like to see?

[Geiger]

Didn't see much point in starting a new thread for this.  Why haven't I posted to this thread in eight months?  Enh, effort.  It was also unclear how much interest there was in the topic.  But I'm still working on Flux and something interesting came up (sort of).  (When is this going to get done?  The todo list is still as long as my arm, but I hope to have closed Alpha builds going by the end of the month.)

---

Implemented "Load On Demand".  This feature may go unnoticed by most.  Previously, Flux front-loaded every record in the ROM file into memory (frequently also decoding it).  This process usually only takes a few seconds, and is almost instantaneous on modern systems.

But LOD is something I have always really needed because in debug everything takes an order of magnitude longer to load.  Fifteen to thirty seconds.  This may not sound like much, but I frequently need to switch between ROMs when testing features or even just load the same ROM multiple times to check saving.  Making and checking small code changes (which happens a lot) or changing breakpoints in the debugger also costs me an additional quarter to half minute.

I have tried to implement this before, a few years back.  It didn't work too well and would have required a massive rewrite of the code (funny that) so everything got changed back.

Why did it get implemented now?  Because of a mistake I made while checking something, oddly enough.  Flux now stores its records to the project folder and reads them from there on load.  It didn't occur to me that my standard test ROM name had previously been the subject of a Reseat All Records test.  There were thousands of records to load from disk.  Reading from the disk is very slow, especially when its lots of small files.  So upon watching the release build run slower than debug typically does, I decided some changes needed to be made.

Now Flux will do a minimal amount of front-loading (fixed small or very important records) and then shift the rest of it to the background.  If the user selects something that isn't loaded yet, Flux immediately loads the requested records.  The background loader is smart enough to not load the same record twice, also.

[Geiger]

No real insight this time.  Just a warning that some bugs are bad enough to end projects, if you don't have the willpower to see it all the way through to the end.

For nearly a year now, I've been hunting a bug in the Overworld Exits.  They are suppose to synchronize with the Overworld Event code (some exits can activate events).  And the code generally looked correct to accomplish this.  And sometimes it even did, in a very limited manner.  But the vast majority of the time, they just wouldn't work.

The number of bugs I've found and fixed in this hunt would be enough to warrant their own minor version release if I weren't in the middle of a rewrite.  I haven't kept track of them all, but I'd estimate between two and three dozen.  Every time I thought I was getting close, I'd hit another bug, another detour, or another subsystem to rewrite.  There are a number of times I felt like saying "To Hell with it!" and ripping synchronization out of this one subsystem just so I could move on to one of the other dozen major items on my list.  If I were much earlier on in the project's life, I might have just thrown my hands up into the air and moved on entirely.

I have debugged stuff into the Windows kernel that I did not have source for easier than this.  This is easily the worst bug I have ever had to deal with in the entire nine years of this project, and possibly in my entire programming career.

Or at least it was.  I released the first closed Alpha of what will eventually become Temporal Flux v4.00 a couple of hours ago.  Only a month late.

[Zoinkity]

Incidentally, how well do you document what you're working on?  That's always been my bane.
There's this tiny little patch I've been working on for years now and a mysterious bug crept into it.  It causes apparently random crashes in unemulated games.  I've got it worked out the the version it first occured in, but sadly didn't actually document what changed in that version, or really at that point what was changing where.  I'm  t h i s  far away from starting over from scratch.

Have to say, your post does instill the will to trudge on.  Looking forward to the new version.

[Geiger]

Incidentally, how well do you document what you're working on?

I have a bug tracker set up, and I keep major changes on my WIP list, which eventually becomes the version list.  I also use source control.

I typically use the bug tracker for things that other people report.  Most notably, it was busiest when I had a beta team.  While I don't use it as much now, I still keep track of long term goals and ideas that won't be tackled anytime soon.  I mostly use a todo list in a local file for things I find.  And usually, if I find a bug and fix it a couple hours later, I don't bother to document it.

The WIP list is mostly for other people to know what sort of changes I have made.  But I do occasionally make references to it, if I want to know the timeframe for when something was added.  The WIP list is mostly constructed from things I finish on my todo list, though usually condensed a bit.  In that sense, it also serves as a list of accomplishments which will give a small morale boost when I look at it.

The primary type of source control I used throughout the years was just to copy all of the code into a new directory whenever I started a new version.  This will suffice for smaller projects, but is hardly optimal.  Fortunately, a few years ago a friend clued me into Perforce.  Its a bit difficult to setup and use compared to most major commercial source control, but its free (2 users), fully featured, and works pretty well once everything is going.  If you have a computer you can use as a server, understand how (real) source control works, and have a little technical know-how, I strongly recommend it.

[Geiger]

The next version of Temporal Flux will be a project-based system.  Up until now, it has been ROM based.

The difference between them is that in the latter, the ROM is king.  Everything revolves entirely around the ROM.  It is where you get and store the data.  Information is primarily kept the way it appears in the ROM.  If you want to store meta-data, you will need to find some way to attach it to the data you are keeping in the ROM.

In the former, the ROM only serves 1.5 purposes.  It is the original source of data (maybe) and it is where you store the final version of the data.  All those other concerns drop away.  Once you have done the initial data retrieval from the ROM (if you don't create everything whole cloth), it will always come from an external source file.  Meta-data can be stored directly in the source file.  Information can be abstracted as much as you want and stored that way.  The data is modified and saved to the source files.  And finally, everything will be regenerated and saved back to the ROM.  In a sense, everything becomes a lot easier to work with and accomplish.

But abstracting away from the entire ROM is very complicated.  Having meta-data and significant data abstraction requires that I have a way to process them and convert them back to something the ROM actually recognizes.  If the data is organized in an unusual fashion, I need to figure out how to store the information to file and then reliably recreate that organization the next time it is opened.  It will mean further changes, like not having all of the records open at once.  Which, in turn, means I have to come up with a new means to calculate free space since I cannot just run down the record list.  And it continues on from there.

Some (most) of that will not be in the next version though.  I don't want to take another four years before I release.  For now, it requires orienting the program around a project, for which the ROM will merely be a setting.  I need to figure out what the bare minimum for that entails.  The ROM needs to be fully dethroned, and I need to be able to grow the rest of the features in a natural way as things continue going forward.

It will be a challenge.

[LostTemplar]

Sounds terrific. I've always thought that the ROM is a pretty fragile and inflexible place to store anything until it's done. I can imagine that it'll get very complicated, but good luck :)

[Nightcrawler]

Agreed. That's a smart idea and logical evolution for the program. It will ultimately do wonders for your program's future. It should allow easier maintenance, better flexibility, and ease of expansion and features. The trade-off is it's a very different way of doing things compared to what you have and will required much effort to change (as you know). You probably wonder why you didn't think of this years ago. 

I think it's common frame of thinking trap for us to fall into at first. Everything we do revolves around the ROM. So, it's easy to design your programs and setup centering around the ROM. It seems logical. Then one day if you take a few steps back and start really thinking about it, you can start to see other options. What is the ROM really? Just a data holder? Perhaps that shouldn't be the center after-all.

I've been in a similar situation with my utilities until the light bulb turned on and I figured out I didn't have to live chained to a ROM anymore. Not to mention, what you're doing becomes much more useful and/or reusable when it's not so tightly coupled and can stand on it's own. For myself, I attribute it to evolution of my programming ability. I finally gained enough experience to start to better recognize flaws in my software design and identify better approaches. I started to see the big picture instead of the box I was typically in. I know nothing of your abilities, but wonder if it has not been much of the same for you?

[Geiger]

For myself, I attribute it to evolution of my programming ability. I finally gained enough experience to start to better recognize flaws in my software design and identify better approaches. I started to see the big picture instead of the box I was typically in. I know nothing of your abilities, but wonder if it has not been much of the same for you?

Sort of, but not exactly.  I have been a professional programmer for eleven years, and eighteen years total experience.  That doesn't take into account all the extra hours I spend on hobby projects.  Of course, you never stop learning, but my skills are pretty sharp.

In my case, its more a matter of how much time I have spent on this specific project.  Even with my current skills, by no means could I program Temporal Flux as it is today if I just started on the project.  It would probably look a bit better than v1.00 did, but it probably wouldn't be even as good as v2.00, let alone the current WIP stuff.  As you work on a project, you come up with solutions for your current issues.  And then once those are in place, you can take a step back and look for even better ways to improve it.  And so on.  Its an evolutionary process.

And its not just the project experience, but also the tools available to make things happen.  If I was still working with the .NET Framework 1.1, I wouldn't be able to do a lot of the stuff I am using in this version, or even the last couple of them.  (Oddly enough, some of the tools have gotten less useful over time, so I am still using some 1.1 stuff here and there.)  And in turn, the new solutions these tools enable push me to think about still more solutions for other issues.

[Zoinkity]

So really, you're slowly switching from a ROM hacking tool into something between a resource editor and a compiler.  Impressive!

[Geiger]

An interesting problem has popped up for me.

Generally speaking, if you are going to move your project from one computer to another and won't be back to the first one in awhile, make sure it works on the one you'll have.

Somehow, my primary project file has gotten encrypted.  I cannot even touch the file, let alone compile or even open the project.  And, for reasons I do not understand, it is keyed to only decrypt on the original computer.

I... have no idea.

[Nightcrawler]

NTFS encrypted maybe? It sounds like a case where your folder or file was set to be encrypted on the disk and you forgot (or it was done inadvertently in a clickety-click fest). It's basically transparent on the originating computer and easy to forget or ignore until you have an issue with the file somewhere else.

[Geiger]

It is definitely NTFS, and I can only imagine it happened accidentally while trying to click something away.  It is not something I would have done purposely.

Encryption is not the only reason why you will want to check your project.  Maybe external source did not get transferred.  Maybe a necessary tool is missing.  Maybe tool or system configuration is different between the two machines.  This is something that should always be checked.

Unfortunately, I was in a bit of a hurry and needed to just grab my external drive.

[Geiger]

A couple of challenging things have popped up recently in this project.

I faced the difficult decision of breaking all of the plugins, twice.  The first one resulted from changes made to move the program more fully over to parallel processing.  Previously, there was a function call available to plugins that made use of window assets to post status messages.  But window assets are not multi-thread safe.  The function had to be reworked so that it dispatched messages to the prime thread which then consumed them to post the messages.  The change is not, unfortunately, transparent, but I was hopeful that I might be able to make it so later on.  Until the project-orientation got implemented.  The approach is so different that I do not think there is a way I could abstract it away so the plugins could continue to function as before.

And here, the plugins fold back in on me and affect my project.  I have implemented the most basic level of a project-oriented approach, but there is a lot more work to do.  From the application's and user's point of view, there is little reason I could not roll out this version and finish implementing features in a point release.  But the additional features will require still more changes from plugin authors.  Which means that I can either tell them their new plugins will only work for a couple of months until the point release, or I have to treat the entire project-orientation as a fixed solid unit that can't be broken down into smaller releases.

Also, the more work I do towards project-orientation, the more required features I see decompressing out of the idea.  For example, if I am going to properly facilitate free record association, it means I am also going to need to define creating a new record... of each type of record... what that blank record looks like... a dialog to select a new record type...

Currently, I stand at .23 DNFs.  Hopefully, that number won't reach 1 before I am able to get this done.