That Was Random

August 20th, 2010

Here’s something new. Or rather, something very old. I introduce to you CruzEditor, my new Flash editor for the classic Kroz series of games.

CruzEditor - New Level Editor For Kroz

Over a year ago, I made a BAR implementation file for characterizing Kroz level designs from the source code files released by Apogee in 2009. But I never really did anything with the results–until now. Pictured here is the opening scene from Lost Adventures of Kroz.

Well, the original Kroz graphics weren’t that good. The editor is still under development, and the game engine for the remake is still a ways off. I intend to re-release a modernized version of all seven original episodes, eight if you include Kingdom of Kroz II. I also want to develop some more adventures of my own and enable others to do so.

As of this point, all of the Kroz source code files now work with CruzEditor, including all ordered and all unordered levels. See the unordered levels below:

Unordered Level 1
Unordered Level 2

These are unordered levels, created after pushing the “Test Generate” button. If you keep pushing the button, a new random level will be generated.

Scott Miller’s original random-level generation routine was very simple. It just involved selecting a random pair of coordinates for each item that needed to be placed on the grid.

But this was problematic for those levels, like the ones shown here, that were filled wall-to-wall with enemies, walls, or other items.

Whenever a spot on the grid was not empty, the coordinates had to be rejected, and a new pair picked instead. This made the level generation process very slow for levels that ended up rejecting lots and lots of coordinates.

I decided to employ a better level generation process: the random list algorithm. With this, you treat each grid square as a list item, and have a probability (in this case, about 1 in 1,500) that any one square will be picked next for placement. Then, after placement occurs, you remove that square from the available squares, and then run a reduced probability on the rest of them. The next placement would be 1 in 1,499, the next 1 in 1,498, then 1 in 1,497, etc. all the way down to 1 in 2 and 1 in 1, if the grid needs to be completely filled up.

A smaller list like this ten-item one can help to visualize:

ABCDEFGHIJ : Pick C
ABJDEFGHI : Pick A
IBJDEFGH : Pick G
IBJDEFH : Pick E
IBJDHF : Pick F
IBJDH : Pick B
IHJD : Pick J
IHD : Pick I
DH : Pick D
H : Pick H

The algorithm is fastest if the last item in the list is moved to fill the “gap” made by removing the item selected. You could also perform a slower memory block transfer to preserve the original order, but this is moot because the list will ultimately end up shuffled.

With no rejected coordinates, it runs pretty fast.

Do you like the look and feel of this editor? I will make it available to everyone eventually. That we never had an editor for Kroz in the first place was a disappointment–a problem which I intend to remedy.

Posted in Conversions, Game Design | No Comments »

Patchmaker International

June 14th, 2010

Hi folks. Since I started at GD, I’ve been away from the blog, but here’s a format I’ve been working on for a while: IPS, or International Patching Specification.

My last entry about ROM hacking only discussed what a person does to make a hack. But with a mind for distribution, no hack would ever legally pass muster without some sort of patching scheme. This involves a format that facilitates patching, and software applications that can make and apply such patches.

A patch file contains only changes to a file. Suppose you have version A and version B of a file: the patch, once applied to A, will “transform” A into B, provided you have version A to begin with.

The most common type of patch file used in ROM hacks is IPS, and for good reason:

1) It’s common.
2) It’s simple.
3) It works well with small binaries.

A number of utilities exist to apply patches, such as IPSWin.exe. It applies patch files with IPS extensions to whole ROMs or other files. Generally speaking, you cannot distribute the whole ROMs legally to another person, but you can distribute the patch, which contains only changes you’ve made personally.

There is a lot of legal gray area here. But I’m not concerned with that–and neither should you. What concerned me was that I never found many utilities that could make IPS files in the way I wanted.

I went to work on BARfly and made a new I.F. called IPS.BAR. This file actually has three functions rolled into one:

1) It characterizes patch records of an existing IPS file.
2) It allows you to patch a file using version A of a file and an IPS file.
3) It allows you to make an IPS from version A and version B of a file.

It’s #3 that is most useful to me. I had to give it some thought, because there are some nuances to making a patch have a small size. Run-length encoding is supported in IPS, so I took advantage of that whenever possible.

When testing it out, I was shocked to discover that in some cases, IPS.BAR generated patch files nearly half the size of some of the originals I’ve found online!

Anyway, I’m satisfied with the utility, and I encourage anyone who wants to learn about IPS to check out the new file on my website. Download it here: http://www.chriskallen.com/barfly/IPS_Patch_File.bar.

I will note that the instructions are not that straightforward because they involve some copying, pasting, and deleting. This is because BARfly’s original charter was to characterize data formats. Its utility in performing more complex file operations is limited as a result. I will be changing this soon, of course. Having a schema have diverse file inputs and file outputs raises the “BAR” significantly–pun intended.

Tags: , , , ,
Posted in Uncategorized | No Comments »

Reverse Engineering with Style

April 13th, 2010

Folks, it was only a matter of time before I would talk about this subject. I’ve covered many different types of data formats, including secondary storage, network communications, and representation in RAM. But what about executable files?

If you’ve evaluated BARfly, you’ll know that the software is merciless. It doesn’t know when it’s being pushed too far. If you want to represent machine code instruction sets with it, you’re perfectly welcome to do so. Machine language is just another data format.

I won’t go into all the ethics of (or reasons for) reverse engineering. I will say this, though: most of the time, license agreements you sign when you purchase software or hardware have a clause forbidding the reverse engineering of your newly acquired property. Please obey those.

Now that I’ve said that, let’s talk about reverse engineering with style.

When a program’s source code is compiled and linked, it becomes machine language, a series of bytes that, when interpreted, tell a processor what to do. A machine language “instruction,” as it is known, generally has the form of an operational code (often known as an “opcode“), followed by one or more optional “mod bytes” that influence the performance of the opcode.

Most programmers nowadays don’t know about machine language. This is because compilers and linkers are so good anymore, and optimization so reliable, that everyone just thinks, “I’ll just create the source code and have the compiler handle the tough translation tasks.” Unless you’re tasked with making or modifying the compiler itself, you normally don’t need to know about the target instruction set.

But if you are performing reverse engineering, you’ll need to know about every instruction set you want to work with. Each computer manufacturer uses its own instruction set and has its own interface for programming the hardware, which isn’t necessarily linked to the instruction set.

Why do you need to know this info? Because once machine language is generated, it can’t be immediately molded back into source code. Machine language instructions tend to be simple operations. The equation A = B + C * D / E would require at least 5 different instructions.

As you can imagine, reverse engineering requires both a significant knowledge base and a whole lot of patience. The quality of the tools used in the process can make a huge difference in overall effectiveness.

A short list of tools you have:

  1. DEBUG: A very elementary disassembler and debugger, present since the early days of DOS.
  2. IDA Pro: A sophisticated, platform-independent graphical disassembly suite.
  3. Various off-the-shelf tools: Varying functionality and usefulness.
  4. Emulators: Programs designed to run a simulated version of the actual machine in a “box,” whose input and output can be easily manipulated.

DEBUG and similar disassemblers operate on the principle that any portion of memory can be reverse-engineered, as long as you know (a) the starting address, and (b) the range over which the code needs to be reverse-engineered. This is the “forward only” principle.

IDA Pro and similar tools operate on a “follow the path only” principle. Instead of linearly (and blindly) stepping through instructions in a memory buffer, IDA Pro allows you to keep track of the stack frame, the call tree of the program, the references to local and global variables, jump labels, etc. Generally, output from applications like IDA Pro are more useful than the “forward and blind” applications like DEBUG.

Programmers have made custom disassemblers that try to get around some of the limitations of DEBUG and/or IDA Pro. These tools have varying strengths and weaknesses, which I will discuss shortly. Finding the right tool can make a world of difference.

Emulation is the last resort of reverse engineering. With an emulator, you can get a realistic state of the processor and its memory at all times. DosBox is a common emulator for 16-bit DOS applications. Emulators are also commonly used to play classic games built for antiquated hardware; MAME is the best-known example.

The biggest strength of the “forward-only” principle in reverse engineering is that you cover all bases–you reach all portions of code, regardless of how they are actually covered. The weaknesses include possibly disassembling non-code (resulting in gibberish), straddling valid opcodes (resulting in incorrect disassembly), and limited ability to interpret the results.

The core strength of the “follow the path only” principle is that only the paths actually discovered through natural flow from points of entry will be disassembled. This yields much more useful and valid output than forward-only, and allows applications like IDA Pro to display all sorts of useful diagrams and relationships. The weakness of path-following is that it is restricted to just known points of entry and deterministic paths (not all code is deterministic).

I’m going to provide a case study in reverse engineering, using my own experience. I’ve already done a ROM hack total conversion with Metroid Master, but I wanted to do the next ROM hack without relying so much on others’ tools. This time, I decided to reverse engineer the code by building my own disassembler.

(NOTE: I feel I can safely talk about reverse engineering 8-bit Metroid because it’s been 25 years since it was popular. If I were talking about hacking Wii games, Nintendo might not like what I’m doing.)

There are many quality 6502 disassemblers out there. I’m mostly used to Intel’s x86 family of instruction sets. But the 6502 processor was once widely used, so learning it was something I absolutely had to do.

The rationale behind creating my own disassembler is that I wanted to circumvent the weaknesses of the existing disassemblers. My disassembler performs limited emulation, and can generate multiple types of readable assembly from machine language.

While 6502 disassembly output usually looks like this…

0001FFB0: sei
0001FFB1: cld
0001FFB2: ldx #$00
0001FFB4: stx $2000
0001FFB7: stx $2001
0001FFBA: lda $2002
0001FFBD: bpl $0001FFBA
0001FFBF: lda $2002
0001FFC2: bpl $0001FFBF
0001FFC4: ora #$FF
0001FFC6: sta $8000
0001FFC9: sta $A000
0001FFCC: sta $C000
0001FFCF: sta $E000
0001FFD2: jmp $C01A

…my disassembler, NESDis, can display it like this:

label_07_FFB0:
07/FFB0: 78 P |= F_INTERRUPT_DISABLE;
07/FFB1: D8 P &= ~F_DECIMAL_MODE;
07/FFB2: A2 00 X = 0×00;
07/FFB4: 8E 00 20 m[0x2000] = X; // PPU Command
07/FFB7: 8E 01 20 m[0x2001] = X; // PPU Command
label_07_FFBA:
07/FFBA: AD 02 20 A = m[0x2002]; // PPU Read
07/FFBD: 10 FB if (!(P & F_SIGN)) goto label_FFBA;
label_07_FFBF:
07/FFBF: AD 02 20 A = m[0x2002]; // PPU Read
07/FFC2: 10 FB if (!(P & F_SIGN)) goto label_FFBF;
label_07_FFC4:
07/FFC4: 09 FF A |= 0xFF;
07/FFC6: 8D 00 80 m[0x8000] = A; // MMC1 Control
07/FFC9: 8D 00 A0 m[0xA000] = A; // MMC1 CHR-ROM 1
07/FFCC: 8D 00 C0 m[0xC000] = A; // MMC1 CHR-ROM 2
07/FFCF: 8D 00 E0 m[0xE000] = A; // MMC1 PRG-ROM
07/FFD2: 4C 1A C0 goto label_0xC01A

Same machine language, but the assembly output looks COMPLETELY different. I think opcodes are much more readable if put into C-language equivalents. Wouldn’t you agree?

Critical hardware port programming is revealed. Original machine language and readable assembly are displayed concurrently. Addresses and bank numbers are known. More importantly, paths are followed in a similar way as IDA Pro, meaning that they need not be dumped in a linear order (they can be dumped hierarchically).

BUT…determinism is always an issue. Most instruction sets, including both x86 and 6502, have indirect jump opcodes. This constitutes a serious problem because the path to which to jump or call is determined at run-time. Emulation can help find the valid addresses, but it’s almost impossible to know all the valid addresses unless you watch every path being followed at run-time, which is usually not worth it.

Fortunately, programmers rarely get fancy with such opcodes for just any reason. A programmer will generally implement an indirect jump or call for one of the following reasons:

  1. Callback or “hook” procedure. Equivalent to a C-language pointer to a function.
  2. Switch control block. C-language “switch” statements can use a “jump table” to quickly direct program control to a wide variety of locations based on a scalar input. This is most economical when there are many scalar input choices that are numerically close to each other (e.g. 5, 6, 7, 8, and 9).

These are very specific circumstances. Therefore, the number of indirect jump opcodes in a program tends to be very few. When confronted with an indirect jump opcode, I had to perform manual inspection to figure out what the processor was trying to do:

label_07_C510:
07/C510: 0A A <<= 1;
07/C511: A8 Y = A;
07/C512: B9 1F C5 A = m[0xC51F + Y];
07/C515: 85 0A m[0x0A] = A;
07/C517: B9 20 C5 A = m[0xC520 + Y];
07/C51A: 85 0B m[0x0B] = A;
07/C51C: 6C 0A 00 indirect_jump(ia(0x000A));

What does this mean? Well, roughly translated, it means “use the value of Y as an index into a jump table.” Fortunately, the jump table is located immediately after the indirect jump opcode. I’ve found that the jump addresses, also co-located, evaluate to the following:

{ 0xC531, 0xC552, 0xC583, 0xC590, 0xC5B6, 0xC5C3, 0xC45C, 0xC45C, 0xC45C }

NESDis stops when it encounters an indirect jump opcode, because of lack of determinism. But you can pick any point of entry with NESDis. The next time I ran NESDis, I chose the point of entry as the first entry in the jump table, 0xC531. And lo! An entirely new set of paths was revealed:

label_07_C531:
07/C531: A0 00 Y = 0×00;
07/C533: 84 31 m[0x31] = Y;
07/C535: C8 Y++;
07/C536: 84 1D m[0x1D] = Y;
07/C538: 20 5D C4 funccall_0xC45D();
label_07_C53B:
07/C53B: 20 3E A9 funccall_0xA93E();
label_07_C53E:
07/C53E: 20 58 C1 funccall_0xC158();
…

By combining the results of individual NESDis outputs, we can eventually build a complete picture of the Metroid source code.

Individuals who are interested in reverse engineering now have an idea of where to begin. Of course, there are many other advanced tricks, but they have to be discovered on one’s own time.

I strongly suggest you check out emulation central, http://www.zophar.net, for more information.

Tags: , , , , , , , , , , , ,
Posted in Conversions, Game Design, Reverse Engineering | 6 Comments »

Programming Made Easier with the Right Formats

March 26th, 2010

We’re going to go WAY back in my programming career this time. I’m almost embarrassed, in fact, to be mentioning this. My first real attempt at action game programming was making a game out of a silly paper drawing that my friends and I had worked on, called a “Torture Course.” Screenshot is below.

Torture Course

It looks like your typical “get through a dungeon full of traps without dying” type of game. More or less, it’s true. ASCII characters plopped on the screen, leaving much (okay, just about everything) to one’s imagination.

Incredibly, a game this early in my programming career (circa 1991) had sound programming, mostly in the form of creative effects when your character gets zapped, stabbed, burnt, cut up, etc.

But how was the level information stored? How did I edit it? How to test it?

Heh heh…well, folks, I hadn’t yet learned that you can actually call API functions to save and load information. What’s that, you say? You can SAVE your designed data and LOAD it later?

If you don’t believe that the level was generated ENTIRELY by code, just look at a sampling of how the BASIC code was constructed:

19 I$ = INKEY$: IF I$ = “y” OR I$ = “Y” THEN SYSTEM ELSE IF I$ = “n” OR I$ = “N” THEN 0 ELSE GOTO 19
20 I$ = INKEY$: IF VAL(I$) > 6 OR VAL(I$) < 1 THEN 20 ELSE TYPEVAL = 0: CHAIN "intermis.bas"
49 L = 40: FL$ = CHR$(15)
50 A = 2: B = 1: C = 102: SQ = 6: F1 = 26: F2 = 26: F3 = 30: F4 = 30: UP = 1: LEFT = 1: F$ = "M": T1 = 3: T2 = 6: WP1 = 10: WP2 = 25: JUMP = 2: H = 3: LF = 1
60 LA$ = CHR$(175): W$ = CHR$(219): U$ = CHR$(24): D$ = CHR$(25): R$ = CHR$(17): L$ = CHR$(16): LS$ = CHR$(176): WP$ = CHR$(254): V$ = CHR$(179): LN$ = CHR$(196)
61 CLS : COLOR 8: LOCATE 1, 1: PRINT STRING$(45, W$); : LOCATE 8, 1: PRINT STRING$(45, W$); : LOCATE 8, 40: PRINT " "; W$; " "; W$; " "
62 FOR X = 2 TO 7: LOCATE X, 1: PRINT W$; : LOCATE X, 9: PRINT W$; : LOCATE X, 16: PRINT W$; : LOCATE X, 24: PRINT W$; : LOCATE X, 45: PRINT W$: NEXT
63 LOCATE 2, 2: COLOR 10: PRINT V$; " "; V$; " "; V$; " "; V$; " "; : COLOR 6: PRINT WP$; SPC(13); : COLOR 8: PRINT W$; : COLOR 6: PRINT WP$; : COLOR 8: PRINT " "; W$; " "; : COLOR 10: PRINT V$; : COLOR 8: PRINT "oooooo "; LS$; " "; LS$
64 LOCATE 3, 2: COLOR 10: PRINT V$; " "; V$; " "; V$; " ": LOCATE 3, 16: PRINT " ": LOCATE 3, 32: PRINT V$: LOCATE 4, 2: PRINT V$; " "; V$: LOCATE 4, 27: COLOR 8: PRINT W$; W$; " "; : COLOR 10: PRINT V$
65 LOCATE 5, 2: PRINT V$: LOCATE 5, 28: COLOR 8: PRINT LS$; " "; : COLOR 10: PRINT V$; : LOCATE 6, 28: COLOR 8: PRINT W$; " "; : COLOR 10: PRINT V$: LOCATE 7, 2: COLOR 12: PRINT U$; U$; U$; U$; U$; U$; U$; : COLOR 8: PRINT W$; : COLOR 14
66 PRINT LS$; LA$; LA$; LA$; LA$; LS$: LOCATE 7, 24: COLOR 8: PRINT " "; LS$; " "; : COLOR 10: PRINT V$;

Ha ha ha ha he he ha ha ha–oh, whoops. I gotta continue this entry. You can continue laughing if you want. If a software engineer in his right mind would ever code like this, he would have to be under one intense deadline. Obviously, coding discipline and coding standards are very important, neither which I had even heard of back then.

If only I had thought ahead of time how to put the program’s architecture together. But when you have only your own resourcefulness, every line of code you write is a proof of concept in some fashion. I will note that programming courses on the level of what I was trying to do were NOT offered at my schools. So I improvised.

Walls and movers were drawn on the screen with for…next loops. If…then statements were used to check for collisions. And I mean a LOT of If…then statements. One for each wall segment or obstacle. The Torture Course bears a striking resemblance to a game known as “Escape from Epsilon,” which at the time, I had never seen. But the creators of THAT game had it together. I clearly did not.

It would have been far better if I had designed the levels in a text editor, with various symbols representing the walls and obstacles. It would have been much better if I had simply chosen an intra-code gridded format, like what Scott Miller did with Kroz. Making my own independent level editor would have been excessive, though. Especially when you consider that I’d have to create an entirely new format.

Speaking of which, there are a LOT of game design formats out there. Since every game is its own beast (and often its own programming masterpiece), it’s reasonable to assume that just about every game has its own custom formats, specific to JUST that game. Well, sort of. The resources used to create games are now a lot more standardized than before: GIF, BMP, JPEG, PNG for images, MPEG, MOV, and AVI for video, WAV, AIFF, and MP3 for audio.

But the level designs for games are all over the place. I’ve got several of my own: NIB, NGR. There are FR files, UNR files, MAP files, and the list goes on. Savegame formats? Once again, all over the place. What do these mean? Should we care?

Granted, there are somewhat standardized level design formats. A software engineer must decide on the ease of implementation when figuring out how to store the formats. I’ve mentioned how BARfly can transform text into binary with the formats used in Brian’s Journey. But really, a designer needs to start out with concepts, and not so much formats.

What is the designer trying to represent? If it’s a static 3-D map, try using an off-the-shelf editor. If it’s a standard 2-D grid, try using an off-the-shelf editor. If you need to start adding game-specific features that no off-the-shelf formats support, think about XML or other text-based formats. There should be no shame in starting out a level design with multiple formats per level. After all, many maps are designed in such a fashion: static elements on one layer, and actors and dynamic elements in additional layers, which are placed at pre-map based on a specific context.

Software engineers are supposed to be resourceful. Use text when you want to edit quickly and experiment. Use off-the-shelf editors to generate static designs.

But whatever you do, DO NOT create your own level editor unless you think it’s value-added in terms of time. It can save loads of time if the editor and the game app are the same program, but remember, the cost of developing the editor is something you can’t get back. Try to figure it out:

Is (Cost of Editor Creation) + [(Less Time Editing) * (Total Number of Levels)]

less than or greater than [(More Time Editing with COTS editor and text files) * (Total Number of Levels)] ?

In my case with the Torture Course, and in Scott Miller’s case with Kroz, a single change to a single level feature required a recompile of the ENTIRE program. And back in the day, compile times were not fast. That adds to your development and testing time!

In the case of Nibbler, an intra-game level editor allowed much more rapid development and testing of levels, even though it’s just a compressed gridded format.

I guy I know named Josh uses text files to script when enemy ship formations appear in his side-scrolling shooter. Is that wrong? He has claimed it could be viewed as lazy, but I think, what’s a more straightforward way to fine-tune level features than to modify a text file?

There is no consistent answer to how you should use formats to make your development job easier. But if you ask the right questions, you’ll be in good shape.

But one thing is clear: good riddance to “FOR X = 2 TO 7: LOCATE X, 1: PRINT W$;” !!!!

Tags: , , ,
Posted in Conversions, Game Design, Vintage LF8R | No Comments »

Local File Manipulation with Flash

March 1st, 2010

For the last several months, I’ve brought myself up to speed on the Flash platform. This a very common environment for the creation of animation, movie clips, and games that are designed to play in an embedded application. This usually means a web browser.

I find Flash useful for game programming, because it’s cross-platform and doesn’t require a separate download. Give someone a link, and -BAM- they’re playing the game. That’s all you need.

But (and there’s always a “but”)…

What about loading and saving of data files to secondary storage?

The general trend for language runtime development is to add more features, give more flexibility, run on more target platforms, etc. Basically you start small and conquer more territory over time. For Flash, it’s no different: it used to be just a sandboxed environment with arcane scripting, focusing mostly on the animation side of things. Then animation expectations got bigger, with a third dimension. Then people wanted more high-level language features; AS3 is now a lot more akin to Java than ever before. Then people wanted full control over files, local and remote. And control over cookies. And the ability to network remotely. And the ability to–

Whoa, whoa, whoa, whoa! Slow down! Are we talking about a sandboxed environment anymore? It seems like you can do anything from Flash now, including program viruses that infect the moment the animation plays! That’s a risk that Adobe has realized and tried to mitigate.

The Flash security settings are actually designed with a lot of foresight. The Adobe AIR platform, created to act as a Flash-based runtime on the server, can do just about anything with files, much like Java, .NET, Perl, or PHP. If your web server supports AIR, the sky is the limit.

But an SWF in your web browser is another story. The sky is NOT the limit–you can only climb a few feet up the mountain if you’re not using AIR. If a Flash SWF file is run as an embedded control in the browser, you don’t have as much control over networks or files. Mainly:

1) Accessing client data, like cookies, is much harder.
2) Network-based communications face many restrictions (can’t “bot” users who run SWF files).
3) Files can be read with URLRequest, URLLoad, etc. But writing to them is nearly IMPOSSIBLE.

Point #3 has been the biggest disappointment to me in terms of game programming. Writing back data to the web server, even if it’s just a dopey high score list, is WAY harder than I think it should be. But it’s also understandable. Flash is an animation platform–Adobe wants to keep it that way. Would-be virus programmers be damned.

But…what if I just want to make an online level editor and save my work that way? You mean I can’t even do something as simple as fopen, fwrite, and fclose in the same freaking directory as the SWF?

I’m a resourceful sort of person. I didn’t want to believe Flash was so restrictive. And it turns out, it’s not.

There are roundabout ways to save data. The Flash security settings, by default, let you access HTML pages and data files in the same directory as the SWF. You just need to be tricky about how you “read” a file.

In the case of http://www.chriskallen.com, the answer lies in PHP. The following Flash code uses sendToURL to “load” a PHP file. But notice that we’re putting a GET variable, text1field.text, into the URL:

function xferClick(e:MouseEvent):void
{
//Compose URL.
var urlstring:String = text2field.text;
var varstring:String =
"?parameter=" + text1field.text;

//Send request (don't check result).
var myrequest:URLRequest = new URLRequest(urlstring + varstring);
sendToURL(myrequest);
}

This means that we’re loading a dynamic web page–a PHP web page–by virtue of a custom input in a GET variable. Unlike non-AIR Flash, PHP can manipulate files locally. As part of the web page “load,” the server-side PHP script gets executed, causing the GET variable to be “saved.”

The SWF can read the data back by invoking URLRequest. No problem!

What does the user see when sendToURL is invoked? Depends on the browser. Since HTTP is stateless, the user might notice that the status bar indicates web traffic. Nearly invisible web traffic, but to be sure, it’s there.

I’ve got my strategy for loading and saving files. Yours can be the same, or it can be much different. You could use Perl instead of PHP. You could install the AIR runtime on the web server, if you have that ability (I don’t). You could use ASP or JSP. The list goes on and on.

Did someone say something about a sandbox?

Tags: , , , , , , , ,
Posted in Files on the Web Server | 2 Comments »

Getting that image file to your screen

January 28th, 2010

Something we take for granted: image files.

What are image files? How do we get to look at them? We use them all the time, for a variety of reasons, but how do you get from point A, a data file in storage, to point B, the pixels on your computer screen?

When people think of images, they normally think that the computer will just do whatever it takes to display the image, leaving us full control over what we do with the picture once it is rendered. They look at a file on the disk, click on it, and see an image thumbnail pop up. “Good and well,” a person will tell himself, “Because I know that this filename is associated with this picture. End of story.”

It’s unfortunate that image formatting is taken for granted so much. Computers have to do a LOT of things in order to go from an image file to a picture on the screen. Formats are very important to displaying an image, and the inability to display the image, even if only the thumbnail can’t be seen in an explorer window, will frustrate users immensely.

What happens when an image is processed, even when displaying just a thumbnail, is this:

1) File format must be identified. Tags and headers in the file identify the file as a BMP, a JPEG, a PNG, a TIFF, etc.
2) Dimensions (width and height), pixel depth (8-bit, 32-bit, etc.), palettes, and other information must be collected and stored in a format that best promotes the display of the image data on the computer screen.
3) The pixel data itself must be unpacked. There might be compression, or not, meaning a variety of algorithms could be used to get the unpacked pixel data.
4) The unpacked pixel data must be translated into the computer screen’s target format. Pixel depth conversions are the most common types of translation, for example, 8-bit to 16-bit. Re-ordering of the pixels within the bitmap (flipping or rotation) is also common.
5) The computer blits the pixels to the screen. This step is itself a complex process, because it might be a raw transfer of bytes, or the image might be scaled up or down in size to fit into a specific window, or it might be dithered or anti-aliased, or it might require transparency or alpha-blending.

And these steps apply only to raster formats. Vector formats also require the CPU to effectively “draw” the image from scratch, using a series of internal commands stored within the file. For example, SVG, CGM, or WMF.

That’s a lot of work behind the scenes! And the worst part of it is that if any part of these steps break down for a particular file format (for example, TIFF), you can forget about “seeing” the image. That’s it. Over. No room for error.

Obviously, the above problem I have outlined provides a strong incentive to standardize image formats. There’s nothing wrong with that, of course. But software developers are still their own worst enemies here: they continue to develop more formats, and enhance old formats, over time.

The massively disparate mechanisms used to read, draw, and render so many types of image formats has made it difficult for developers to support so many types of formats. Core formats like GIF, JPEG, and BMP are widely supported, but each format has its own unique applications, strengths, and weaknesses. So you can’t ever have a “master” format. If you WANTED to have a “master” format, you would end up creating another format…which means–you guessed it–you’re contributing to the problem.

The fundamental issue here is not that developers are bad people, or that operating systems have flaws in them that prevent all image formats from being viewed and used. The issue is knowledge, and lack of education. To make a decent image reader or writer, you need lots of programming code, usually optimized code, which accomplishes a specific task. And who has the ability to write or understand this code? Just the hardest-core of the already hard-core software developers, who also contribute to the problem.

BARfly confers an advantage to developers and other technical folks: it exposes the “guts” of an image file. It lets you know what’s “really” in it, letting you dissect or even edit the contents that paint programs will not touch. The long-planned “ImageMaker” protocol is not yet available in the software, but once it is, you will have, for the first time ever, a development platform capable of supporting every type of image file ever made, or ever could be made.

Until then, we’ll just have to be content with an elite group of uber-nerds who mercilessly change formatting rules with no prior notice and hold massive contempt for everyone else. Okay, I made that last part up. But the problem is known–we just need to finally start getting around to fixing it!

Tags: , , , , , , , , , ,
Posted in Conversions | No Comments »

Why Randomize?

December 18th, 2009

I’m going to talk about a format-related topic that isn’t strictly related to BARfly. It deals with the formatting of early video games with randomly set-up designs, and how they were able to accomplish lots of replay value with “a different style of game every time you play.”

To design a game to be more enjoyable, you try to make the experience as unique as possible whenever the game is played or replayed. One of the ways you do this is to randomize some parts of a game. Mainly, the map design, the character placement, the protagonist’s starting position, and the order of appearance of items or other objects.

But why did some games employ this and not others? And why is randomization mostly a thing of past games and not more modern ones?

In part it’s because the programming and design effort necessary for a quality-controlled, randomized game environment requires more time and resources, but this isn’t a huge issue for the most part. The real reason so many early games had randomization was because of compression. You don’t have a lot of memory to store your map and character data–let’s see, how do we best represent a level design with less?

The answer was often to just remix the level differently every time, because that way, you don’t require a lot of memory to store static designs. I’ve already mentioned Diablo, Kroz, and Vintage Hyperactive, all games with randomizations. But I’d like to talk about some games that came out even earlier, with far less obvious implementations of randomization.

The first example is Impossible Mission. Below are screenshots of the game, which, by themselves, are static, meaning they look the same every time you play the game. But the rooms, as they appear in the overall map, are in different locations in the game each time you play. Think of each room as a very large “brick” that can be “moved around” at will.



There are other randomizations, too, like robot AI, puzzle piece locations, and puzzle piece appearance and interlock abilities. I’ve talked in depth about this game on my Impossible Mission tribute site, so I won’t repeat too much. But I will say that the Commodore 64 developer, lacking a whole lot of memory with which to store maps, would have had an incentive to make an algorithm for level generation instead of a static map, which takes up more memory.

The next example is far less obvious. This is Tarzan, for the ColecoVision. You might think, do entire screens get moved around like “bricks” like in Impossible Mission? Well, no. It’s a lot more subtle than that.

The top (trees and vine background) and bottom (jungle floor and rivers) each have a set of “lanes” that can feature a sequence of individual background terrain segments. It’s not a total mishmash of disparate terrains, of course: quality steps are implemented to ensure that smooth transitions between ground, water, and tree are always present.

It certainly doesn’t LOOK like randomly generated terrain. But each conventional screen is different, every time you play the game. The basic “appearance” of the terrain doesn’t change much, but each screen is unique save a handful of scripted screens, which are statically put together.

When such quality games have random level generation, it inevitably makes me wonder why some of the most impressive games with level design out there did NOT have random designs. In particular, I would have loved to see randomization in the maps for games like Metroid or Zelda. After all, these games also had to compress data, and it should come as no surprise that they employed some of the same compression strategies.

But you can’t always get what you want. Budgets and deadlines often determine what a software developer is allowed to do, and static design allows for more consistent human-supervised quality control.

Of course, game design has gotten so advanced anymore, and there are such incredible tools at the developer’s disposal, that it’s a wonder that randomization is not more standard fare these days. Budgets are bigger; teams are larger. Maybe starting with my planned game Brian’s Journey, we can trend towards randomization?

Tags: , , , ,
Posted in Conversions | No Comments »

MDB.BAR: Making a database out of…a database

November 18th, 2009

Since mid-September, I’ve hosted a limited BAR I.F. of the Microsoft Jet database format, or MDB. This I.F. breaks the database records into appropriately-sized chunks, identifying various fields.

Of course, the first I.F. for MDB only allows one to look at data table format information. It does not support the “magic row-column” formula used to extract the data, which is to say, you can plug in a record number, a column number, and then you’ve got your data for that row-column combination.

I’m working to correct this, which will allow a person to get information out of any field in a data table. But even this seems like it’s too limited. So you get the information out of row 3, column 7. What does this mean? Most people reference records by a primary key, which is one or more of the columns. Oftentimes, non-key fields must be searched, with each matching record returned. And, of course, let’s not forget that columns are usually referred to in queries by name, and not by number.

BARfly would do wonders to extract entire data tables at once, given this modification. But what would it mean to use a BAR I.F. to manage the database file like you would expect an actual database to be managed? What would you have to do?

Well, I’m not going to discuss all the details, because it would take too long. So I’ll limit my focus to just a fundamental operation programmers and DBAs routinely perform on databases: the select query.

Queries can be written in many forms, but I’m just going to focus on MDB’s preferred format, which is called SQL. A SQL query has the following general form:

SELECT alpha,gamma,beta FROM greekdb.alphabetletters WHERE (caps=”true” AND highlite<>“yellow”) ORDER BY delta

Roughly translated, we want to extract a variable number of records, with three columns (”alpha”, “gamma”, and “beta”) per record returned, from the table “alphabetletters,” which belongs to database greekdb. Limit the records returned to those whose column “caps” has a true value, and whose column “highlite” has any value other than yellow. Finally, order the results, ascending, by the contents of the “delta” field in each returned record.

Any decent SQL processing system will take a database query and strip it down to the fundamental inputs that really matter in the query itself. Once all the text is read and understood, the database query looks more like this to the query handling logic:

Search database 2, table 5, for records where (column 10 is true and column 12 has a negative string comparison result with the text yellow). From these records, extract columns 4, 6, and 5 into the result dataset, in that order, ignoring the other columns. Finally, order the records of the result dataset using column 7 (ascending by numeric comparison).

Computers are nothing but numbers, and everything ultimately breaks down into a number. Once all the SQL has been translated, the real work is retrieving (or populating) all the pertinent data in the database for the user.

So, could a BAR I.F. do all that? Translate the query text, AND collect the necessary data, AND package the results in a format the user had requested? Absolutely.

BAR, remember, has decent regular expression processing capabilities, and can translate the SQL query as needed. Offset tweaking and length calculations are a fundamental part of the BAR deserialization procedure, allowing one to perform the “magic row-column” formula as many times as needed. Finally, the Deserialize functionality allows endless possibilities for data translation after nodes have already been characterized, yielding an appropriate dataset in the order the user had requested.

SQL gurus know that many queries are far more complex than the example I’ve just given. One-to-many relationships, multiple keys, internal consistency rules, etc. are not covered by the example. Clearly, I would be reinventing many wheels by making BARfly encompass nearly every possible creative query that a person could ever dream up, with few obvious returns. It’s far more worth it to use a genuine frontend, like Microsoft Access, if you need to use all the features of the database software.

But if you’re needing to perform data recovery, or if you want to perform easy translation of data without regards to internal consistency, or if you want to migrate the data into XML, UTD, or another format in preparation for a big move to a new format, or if you are writing a program that requires a light memory footprint with little need for all the advanced features of a database-access library of functions, consider the I.F. approach.

And don’t forget this–an I.F. is platform-independent.

I want to mention one more point. Microsoft has released 2.x of the Entity framework, which attempts to provide more universal access to different types of databases, with SQL Server being the preferred target. Query format is no longer important, nor is programmatic knowledge of database-specific features (Oracle has different features of SQL Server, for instance). Great stuff. But the framework does not, to my knowledge, allow anyone to customize what, exactly, the backend is. You’re locked into a predefined set of known database formats.

BAR represents the final piece of the puzzle. With BAR, there is the very real possibility of having a unique component that defines the format for a custom database backend. Having one or more implementation files act as “backend definitions” could, theoretically, allow for a framework with unfettered access to any type of data, regardless of whether or not the data accessed is even a database at all!

Tags: , , , , , , , ,
Posted in Uncategorized | 2 Comments »

Software Development Case Study!

September 30th, 2009

Now here’s something software developers will find very useful! The following is a case study on how to use BARfly to design and implement levels for a video game.

I’ve already got several video game file types supported here. In particular, WAD (for Doom), NIB and NGR (for Nibbler), and a special Kroz level extractor from source code, which I’ve mentioned in previous entries.

But what if your level designs are more complex than linear? Whether it’s in binary or text format, many developers can get by with just a linear file format. A grid speaks for itself, with or without run-length encoding, and objects can be spot-placed with coordinate pairs (or triplets). Unfortunately, many games have trickier design formats. Like these:

  1. Doom. This and other FPS games geometrically organize the points, lines, and textures. But when it comes to linking all these objects together, you’ll need a system to “compile” them into something usable before a game can be played.
  2. Abuse. Not as well-known as Doom, but still worth a mention. Abuse is a very curious beast because LISP is used to drive almost all parts of the gameplay. What is LISP? It’s a linked-list based language, one you’re likely to encounter only in grad-level computer science. Each object, each enemy, etc. has one or more “links” to another object or enemy. Pretty open-ended!
  3. Diablo. This game, and its sequel, Diablo II, have dynamic level design. This means you don’t just have a level grid or spot-placements of objects: you have patterns, probabilities, and schemes determining what a level “might” look like. Levels are mixed in a similar fashion to Nethack or Rogue, which are text-based predecessor games that influenced Diablo’s creators significantly.

Questions to ask: how do you store links and relationships between objects? How do such relationships shape the data structures and storage formats themselves? How much work must be done in the construction of the levels versus the game engine’s actual setup process?

For credibility’s sake, I have no choice but to answer the above questions myself. I’m coming out with a new game soon, called Brian’s Journey. This uses a new game engine, which, at the core, is just a platform-independent graphical wrapper around the BAR engine. To design a level in this game, you’ll need two files: a room definition file and a shape interpretation file.

Text or binary? How about both? This is a profound “gotcha” for game developers. People care immensely about the end product (the game), but the path to the end product can be impossibly bumpy. Do you make text files, which means you use just a text editor, saving time, but perhaps making visualization harder? And making a tricky text-to-binary conversion part of the engine? Or do you pack everything in binary, forcing you to construct a complex editor that few people might ever use, and even fewer like using? Giving you the advantage, perhaps, of less pre-map processing when the level is actually played?

Thanks to BARfly, you can actually have both. Here’s what the shape interpretation file looks like for Brian’s Journey:

Shape file (text)

Looks kind of like source code. In a manner of speaking, it is. Now look at what happens when BARfly loads it:

Shape file (BARfly)

Awesome. Everything’s a node. But do we really want to cycle through all that filler syntax to get at the associations we need? After running the I.F. function “Normalize,” the data looks like this:

Shape file (final)

This function strips out comments and whitespace and gives us just name-value pairs! Architecturally, a program won’t have any trouble accessing this vectored data. Here’s my actual game engine code that loads a shape interpretation file:

//Load interface to shape file.
sh8 = i.Create_BAR(”lf8r_shapeinterp.bar”);
if (!sh8) return 1;

//Load file.
if (sh8->Load(filename) < 0) return 2;

//Normalize (get rid of extra components).
assoc_count = sh8->Function_Call_L(”ShapeCharAssociations.Normalize”);

Not many lines, huh? With so much of the parsing and conversion done in the I.F., the game developer is free to keep the game’s business logic pegged to architecture, rather than low-level parsing.

Okay, great. But that was the easy part. What about the room definition file format? Here’s an snippet of a room definition file:

Room file (text)

Quite complex, indeed. The room definition has some parts ordered and some parts random–taking the best principles from Nethack, Diablo, Kroz, Vintage Hyperactive, and a variety of static level design formats. And because it’s text-based, you won’t need to design rooms in an editor (although you can later). Loading in BARfly gives you the following:

Room file (BARfly)

Do we have normalization I.F. functions here, too? We do. We run first Assimilate_Binary_Style, which removes comments, whitespace, etc…

Room file (intermediate)

…and then Normalize, which translates the remaining text-based nodes to binary-based nodes.

Room file (final)

Before, everything was a text field. Now, everything is a binary structure. If you save this file and reload it, it stays a binary file!

This is a rather novel method, from a software architect’s perspective, when translating text into binary. Traditionally, an architect will need to store text and binary fields separately, forcing a kind of “double vision” to develop. On one side you have your human-readable text, and on the other side you have your binary structures and relationships, which require their own separate architectures for processing.

But with BARfly, you can implement and test all the parsing and conversion logic without ever having to make the video game that uses it (I haven’t yet). There is no “dual architecture.” There is only one. Rather than throw away the source, you preserve the physical relationships of the nodes, and gradually “nibble around the edges” of the text architecture until it becomes a binary format.

Because the I.F for the room definition files does all the heavy lifting, the game engine only needs to deal with the binary format. Compilation isn’t just implicit as part of the level’s load process: it’s totally invisible to the game’s architecture!

Some of you sharp developers might have started to wonder what this means for games that would like to have the ability to read other games’ file formats. Currently, it’s not worth it, because you’d need to invest in a whole separate library of code devoted to reading just that other format. But if the architecture is pre-built into its own BAR implementation file? You’d just need to distribute that I.F., nothing more.

Tags: , , , , , , ,
Posted in BAR Design Strategies, Conversions, Vintage LF8R | 1 Comment »

From Data to Code and Back Again

September 8th, 2009

I have had the file INITDATA.BAR for a long time for internal use. Only today did I decide to release it to the public.

How many times has a software developer wanted to get data incorporated into storage in a local executable…only to discover that you have to use the native data-initialization syntax, very much unlike the format in which the data is stored?

You can be very patient and hand-enter the data (you’d never do it by hand unless there is only a small amount of it).

Take this example. I want to enter the following bytes as static constant data, to be used in the body of a program later: 40H 7FH 23H A8H. In C-based languages, you’d initialize an array like this:

static const char mydata[] = { 0x40, 0x7F, 0x23, 0xA8 };

But chances are, the data isn’t going to be written out as “0×40, 0×7F, 0×23, 0xA8″ or anything even remotely like it. Furthermore, you might want the data written out as short integers, signed or unsigned, in decimal instead of hexadecimal, etc.

Four bytes? Just hand-translate it. Over a hundred? Maybe not. Different base? Ugh. Wrong endian order? Super-ugh.

A simple solution, if not straightforward, is to load the data as a separate file from the disk, like this:


FILE *afile = fopen("mydata.dat", "rb");
if (afile) {
fread(mydata, sizeof(mydata), 1, afile);
fclose(afile);
}

Ah, but what about…

  1. Is pathname always relative? Should it be absolute? How do I reconcile with installation folder, etc?
  2. What if file can’t be loaded?
  3. Is file same size as declared variable? How do I resize it if source data changes? Should I dynamically allocate memory for it?
  4. What if I forget to go through all the proper value checks and closes because as a programmer I’m kind of lazy?
  5. Does this separate load step REALLY need to be done at all?

That last question is the clincher. The answer is NO.

The C++ initialized data converter is the answer. It reads a binary data file and spits out C++ initialized data. Or, alternatively, it can read initialized data and spit out binary data. It’s a two-way converter with many F8-mode selection functions.

If you’ve ever looked at how many files are in the BARfly installation folder, you’d know there are surprisingly few. BARfly uses BAR to run its architecture…but where are all the BAR-based architectural components? They’re not BAR files, and they’re not in the master registry.

The answer: INITDATA.BAR. I’ve long since made initialized data out of such components. The BARfly.exe executable has literally swallowed them.

Engineers of all stripes love the idea of making a machine work with fewer moving parts. Would you rather carry around a large package or several smaller ones? Same load. One’s a lot easier to carry.

Tags: , , ,
Posted in Conversions | No Comments »

« Older Entries