& Very Old Things - Part 3

So. Thus far everything I did involved nothing more than the memory editor and cheat search. In other words, something just about anybody could do. To really say that I reverse-engineered Blaster Master, I needed something a lot bigger, and I knew just what to do: I was gonna find the cause of a 21-year-old bug. There's a well known glitch in Blaster Master that on some bosses, if you or the boss is being hit when you pause the game, you (or the boss) will continue to take damage while the game is paused. This only works on some bosses, however, leaving a big question mark as to whether it's a bug or a feature (it was especially strange that it affected both player and boss); I wanted to find out.



Unsurprisingly, it's quite a bit of work to reverse-engineer something you have absolutely no info on (e.g. in computer programs you at least know OS API calls the program makes, and can use that as a starting point), especially when you're learning both the hardware and the assembly language as you go. Ultimately, it took me an embarrassingly long time to get the job done (certainly more than it was worth), and I ended up disassembling a lot more of the game than was necessary (as is often the case when you don't have any idea what you are looking for). I'll just talk about some of the more important lines of investigation, findings, and complications.

As I didn't know anything about the game, naturally the first thing was to hit "step into" and see where I ended up. I always ended up in the same place: a busy loop that checks a single value. Given the nature of this and some idea about the hardware, I reasoned that this was a loop to wait for the next vertical sync, to start on the next frame; this was confirmed by observing that address being written to from the non-maskable interrupt (vsync) handler.

From there I stepped out of the function and took a look around, writing down the various functions called after vsync. I then went about refining the list and detailing more levels of the call tree, ultimately (after all of my disassembly) resulting in the call tree and other related notes below (note the comments have a focus on things relevant to finding this pause glitch). One thing of particular importance is that there's an object-oriented handler for each object type, and the appropriate handler is called for each non-empty object table entry.

$E936 waits for vertical blank to occur
$C971: for each object calls $C8DF, decreases hit timer if nonzero, calls $C9A4, and calls $C928
-$C8DF copies object data from $400+$56 to $46 ($C925 writes life)
-$C9A4 sets hit timer back to full and decreases life in the object buffer when hit with hit timer at 0 after decrement
--$EA3A
--$EB51 saves the object-specific handler to $7A (LE)
--jumps to the object-specific handler at $C9D3
-$C928 copies object data from $46 to $400+$56
$CA4B->$EA3A->$E61B->$E63C/$EB98 unmaps $8DF6 page [the page the object handlers are], which gets mapped by the NMI handler

$EB7E NMI handler (does not branch)
$EB97 IRQ/BRK handler (stub)
$F7: controller 1 state (bits in reverse order)
$F8: controller 2 state (bits in reverse order)

For a while I did some looking around with breakpoints on the location in the object buffer where the life is stored, looking for things that modify it. Some of the information gathered this way:

Copy of object struct for current object: 46
Buffer used to hold 16-bit pointers [LE] from various tables: 7A

$53 [life of the current object] written to directly by $8DF6 in $C9A4 when damage is taken
$8C6B-8C9F, $8DDF-8DFE (inside $8D76) only executed when hit timer is 0
During pause taking hit, $C1E6->$D7A0 returns A0/N+ to $8DD5 on boss 2, but 7F/N- to boss 5

$D7A0 seems to determine whether you get hit during pause. $7E indicates whether you're being hit or not: high bit for hit, lower bits for damage taken.
$7E is written to by $D71A in ($C141->$D711) when hit by boss, $D7B2 to clear hit per frame. $D71A is not reached when paused with boss 5 because $D6CD does not return
$D6CD returns if the current object is hitting the player, throws an "exception" returning to caller of caller if not hitting (returns from $D710)

Eventually I decided to take a more systematic look at the object handler for the catacombs (overhead view) player object:

$8C38->8D98->$8DBF catacombs player object handler paused
-$C15F
-$C0FF->$EF2B sets $3E and $3F to the X and Y coordinates (in pixels on screen) of the player for $D7A0
-$C1E6->$D7A0 returns A0/N+ to $8DD5 on boss 2, but 7F/N- to boss 5, when paused and being hit. A indicates the damage player should take. highest bit of A and the negative flag indicates whether player is hit or not.
-on N+, $C216 then handles hit (including decrease life)
-$93BD
-$EA3A
-$F029
-$E63C

From this we can see that $C1E6 is the switch we're looking for, determining whether the player takes damage; though a look through the function shows a clear lack of anything resembling hit detection - it simply reads from a struct in memory at $7C, generated who knows where. So, if that isn't determined in the player object handler, maybe it was handled in the objects you can be hit by. For that reason, and to satisfy my curiosity a bit about what makes bosses tick, I decided to take a look at a boss handler function; and as I hate the crab boss so much, naturally I went with that, first.



It was about this time that I discovered that NOPing function calls was a very effective way to quickly get an idea what a function is doing. This method works poorly on computers, because of the greater number of registers and drastically greater stack usage, making such NOPs result in crashes more often than not. On the NES (or at least in Blaster Master), however, the method works very well, with crashes very uncommon.

Crab (level 5) boss unpaused object handler ($A6D0):
-$A07B: (no discernible effect)
-$A6DE: handles movement of crab and state transitioning (but not animation)
-$A7A2: spawns bubbles when necessary
--$C1F5: spawns a bubble
-$C0FF: updates crab screen position based on crab 65 position (NOPout fixes crab position where it shouldn't be, despite crab 65 object movement). affects everything onward.
-$C153->$EB51
-for each body segment (right pincer, left pincer, back):
--$C141->$D711: detection of whether player has been hit. detection of player being hit by green sprite is elsewhere.
---$D6CD: checks for collision
--$C216->$DECC (only if hit)
-$C12C: (no discernible effect)
-$C189: draws (animates?) the green sprite
-$C144->$D697: sets player damage if player hits green sprite. also handles things damaging the boss.
--$D6CD: returns on collision (either player hit by something or boss hit by something). eats the stack frame if no collision (returns to caller of caller)
-$9EB3: animates the background layer

Okay, so $D6CD is another function that looks like a good candidate. So, let's take a look and see if it's what we're looking for or another tangentially related function (don't blame me for the formatting, Blogger doesn't like indentations).

$44 = A
$00 = $3E - ($40 / 2)
$01 = $3F - ($41 / 2)
X = 0xF
do
{
A = $7E[X]
if (A > 0)
{
$45 = A
A = $7C[X] - $00
if (A <= $40)
{
A = $7D[X] - $01
if (A <= $41)
return
}
}
X -= 3
} while (X >= 0)

throw

Now that looks like a collision detection function, more or less. We can see the X coordinate, Y coordinate, width, and height of whatever it is we're comparing against at $3E-$41, respectively (this is a case of a memory region being used like a stack frame). We can also see an array of 5 structs containing the X coordinate, Y coordinate, and a thingy, respectively, starting at $7C. Clearly only the size of the "current" object is considered, and the array of thingies are just points.

Well, let's think about it for a minute. We know that this function is called 4 times for the crab boss, for the 4 different parts of the body (and that one of those is not like the others). What might collide with the boss that would be of interest? Well, the player and the player's projectiles. A bit of playing around proved this to be true: the first entry in the array is the player, the rest are the player's projectiles (limited to 4, as you can see). That third byte in the struct array indicates the amount of damage the projectile does (or 7F for the player).

So, now we have everything we need to figure out how this works. The boss object checks for collisions with the player and the player's projectiles. If it hits the former, it marks the player for damage, which is then applied by the player object handler (presumably next frame, since the player handler always gets executed before enemy handlers); if it's the latter, the boss takes damage, though only if the part hit is the green sprite, which is the hit box.

Now that we know how the collision detection and damage system works, and why bosses that are susceptible to being hit while paused also themselves can hit you while paused (the collision detection for both is one in the same); that just leaves the question of why it only operates on some bosses. Well, it was about here that I discovered that that wasn't actually true. While only some bosses can be hit (and hit you) while paused, this is not the case for projectiles. Specifically, the projectiles fired by boss 3 and boss 8-1 can hit you while paused, even though the boss cannot be hit while paused.

Well, it turns out there are two sets of object-specific handlers, one for when the game is running, one for when it's paused. Now, bullets and other things are generally not prone to the problem of dealing damage while paused, as they disappear as soon as they hit something (e.g. the bubbles spewed by the crab boss). The things that can hit you while paused appear to be exactly those objects that have pause handlers and that don't disappear after hitting you; this is the case with all susceptible bosses, plus the projectiles of bosses 3 and 8-1.
Boss object handlers:
1 (63): base $A58A, paused stub
2 (5F): $9B64
3 (61): $A196, paused stub
4 (5D): $970C
5 (65): $A6CD, paused stub
6 (5F): $9B64
7 (5D): $970C
8-1 (67): $AA34, paused stub
8-2 (69): $AC84, paused stub

While I didn't go searching for every single object handler to compare the paused and non-paused versions, I did compile a list of the ones for the bosses. Note that there is only actually a single table of handlers in memory; the address in the table points to the paused handler, while the unpaused handler is always 3 bytes afterward (3 bytes is the size of a JMP instruction). For the bosses not prone to this glitch, you can see that I've indicated the pause handler is a stub that returns immediately. For the rest, the pause handler jumps midway into the unpaused handler (after things like movement).



To illustrate this, take a look at the handler for boss 2 ($9B67):
-$A07B: (no discernible effect)
-$C01E: handles movement of boss
-if time to spawn next projectile:
--$C1F5->$D851: fork projectile from boss, giving it a new proto-object type
--$C216
-paused handler jumps directly to here
-$C0FF
-$9D77: draw and do hit detection for arms
-$C090->$D770: do hit detection for back (not hit box)
--$D711: hit detection
-$C093: do hit detection for hit box
-$9EB3: moves and animates the background

So, that's how it is. Now we know why it happens and why it only affects some things. That just leaves one more question: is it a bug or a feature? Unfortunately, the evidence is much too ambiguous to answer that clearly. While it's within the bounds of imagination that damaging the boss during pause could have been intentionally put in as a cheat of sorts, it's very hard to imagine that the same thing against the player would be intended.

Yet it's also hard to imagine that it could be a bug; while the player being hit during pause could be eliminated by a single change to the player handler (a single mistake, in other words), doing the same for bosses would require that every boss's handler be changed. Furthermore, there's the fact that only 2 of the 5 unique boss object handlers (2 of them are used for 2 bosses each, bringing the total to 9 bosses) have pause handlers, in contrast to the player and most projectiles, and without pause handlers the bosses don't even get drawn completely (and what point is there in having a pause that lets you see the boss battle if you can't see the boss?). It seems as though a lot of stuff was left out or in arbitrarily; I have to wonder if there is a deadline lurking in here, somewhere.



Various resources used during reverse-engineering:
Nintendo Entertainment System Documentation
6502 Instruction Summary
How NES Graphics Work
Comprehensive NES Mapper Document
For more info, see this big list of documents

& Very Old Things - Part 2

As for the hacking itself, this started out with simple stuff. Search memory, find special values (life, lives, gun power, boss items, etc.), and overwrite them. This was quite easy with an emulator that has a cheat search feature; you simply have it save the memory contents at the initial state, the repeatedly perform searches based on specified criteria until you've narrowed it down to 1 or a small number of possibilities. For example, finding player health was a trivial matter of searching for something that decreases each time you take damage and stays the same in between damage.



With the exception of the boss items, all of the others in this list were similarly easy to find. Boss items, however, were a bit more complicated. Because you only get the items after beating a boss, naturally this is a situation where there are likely to be a lot of changes all over RAM, as it's a major transition in the gameplay; this means that you can't narrow it down as easily. I had to try several locations, starting with the ones whose values made them the most probable to be correct (specifically ones that had a bit flipped on when the item was picked up).

However, there was one other complication figuring that one out: boss items are represented by two separate bit masks that are partially redundant. I first discovered the mask at 3FC, because that's the one that changes the bullet your tank fires after you get the first boss item; as it was a visual change, it was very easy to see that it was working. Once I found that, I checked to see if it was a bit flag, and confirmed it was, finding the flags for the second and third boss items by experimentation.

That's where things got weird. While this mask contained flags for boss items, the flags for the other boss items didn't seem to actually do anything. As well, while having the hover bit flag set caused hover power to be displayed (it's hidden prior to getting the third boss item), you couldn't actual hover. The bits here also did not make the upgrades show up on the pause screen. So, I went on, with my infinite life and gun power, and killed a few more bosses (somehow I still remember most of the maps of this game).

I found that there was a second bit mask with a completely different set of flags, one for each of the 7 items in the game. For the first 2 items, these flags did nothing more than make the item show up in the pause screen. For the third item (hover) this flag allowed you to hover, but did not show the hover power bar or allow you to accumulate hover power (so you still couldn't actually fly with this flag alone). I still can't imagine why it was done this way, but at least I figured out all the flags.

One thing that I couldn't figure out with cheat searches, however, was boss life. That is, I found it - repeatedly: it was in a different place every time (including even for the same boss). I correctly reasoned that this implied that the boss's life was not a special value, but that bosses were simply common entries in the list of objects in the game. As it turns out, so is the player; you just don't notice that because the player is always at index 0 in the object array and thus always at address 0x400, while the boss was stuck in whatever slot was available at the time. This led directly to the discovery of the object array itself. From there, I started looking at the struct that represented each object, beginning with offset 0xD: life.

As I've already pointed out that you tend to have to get clever when coding on a system with so little RAM, it shouldn't be surprising that maps are stored in a similarly clever way. As far as I can tell, there is only a single map for each area in the game (8 areas), which is 128x256 or less. However, the map is diced up and jam-packed in there such that they need to do some camera tricks when transitioning between areas (teleporting through some doors) to make sure you never see other sections that are contiguous in memory.

While I was working on it, I figured I should try to answer some long-standing questions about Blaster Master. To begin with, why does the power of your gun (what it actually shoots) not always match the gun power that's displayed? For example, if you have full gun (8 bars) and get hit, you take 1 bar of damage, but the effect of your gun falls beneath what 7 bars should give you. Many years ago I hypothesized that there were two variables for gun power; one was the one displayed, and one that was the actual effect: getting hit did a bit more damage to effect than the display.

It turned out to be simpler than that. It's a consequence of the fact that while most hits (I can't think of any counterexamples) do an integral number of bars of damage, life, gun, and hover are stored from 0-FF, in bytes. See where this is going? One bar = 20, but 8 bars = FF, not 100. In other words, the number of bars displayed is (x + 1) / 20. When you get full gun and then take a hit, your gun drops to DF; while this still displays as 7 bars, it doesn't give you the maximum gun effect (which requires E0). It's not clear whether this is a bug or a feature, though I'm kind of leaning toward a bug (specifically, an edge case the coders didn't think of, which could be easily solved).

All numbers are in hex.

Continues: 37E
Lives: DD
Gun: C3
Hover: 92
Bosses killed: 3FB. bit x = boss x+1
Boss items 1: 3FC. same values as 3FB.
Boss items 2: 99. bit 0: hover, 1: dive, 2: wall 1, 3: wall 2, 4: crusher, 5: key, 6: hyper
Homing Missiles: 6F0
Lightning: 6F1
Thunderhead Missiles: 6F2
Pause: 15

Gun Levels:
20: 2 long shots
40: 3 long shots
80: circling shots
C0: white wave shots
E0: full wave shots

Beginning of Object Table: 400. 12 slots. Slot 0 is reserved for the player. Slots 1-4 are reserved for projectiles. Enemies fill slots 5-11 as needed.

Object Struct (14 bytes)
byte @0: Object type. A few of the known object types:
3: Normal
4: Dying
5: On left wall
6: On right wall
7: On ceiling
8: Diving
9: Climbing H->V convex
A: Climbing V->H convex
B: Climbing horizontal->vertical concave
C: Climbing V->H concave
D/E/F 10/11/12: Entering/transitioning/leaving door right/left
1B: Outside tank
1D: Entering tank
84/85/86: Entering/transitioning/leaving door catacombs

byte @1: Orientation. The exact meaning of this seems to vary by object type.
Tank mode: Between 0 for left and F for right (the intermediates indicate that the tank is changing face), with the high bit set if the tank is pointing to the left
Catacombs mode: 0 for up, 1 for right, 2 for down, etc.
uint16 [LE] @2: Horizontal position. The high byte indicates the attribute-size tile, while the bottom byte is the position within that tile. The highest bit indicates that you're currently moving through a teleporting door.
uint16 [LE] @4: Vertical position
byte @6: X velocity
byte @7: Y velocity
byte @8: Attribute-size tile index on screen? This was always observed to be (Y * 0x11) + X where X and Y are relative to the tiles visible on screen.
byte @9: Hit timer: the number of ticks until the object can be hit again. Controls invulnerability, damage flashing, and also decreases gun by 1 for each tick above 1 (this causes gun power to drop smoothly rather than suddenly, though I'm not sure why they did it this way; life does not do this when damage is taken).
byte @A: Current AI state
byte @B: Frames till AI state change
byte @C: ?? (no observed effect)
byte @D: Life. For trivia value, normal tank shot does 4, hyper shot does 6, crusher shot does 8, normal catacomb shot does 1, catacomb shot with wave gun does 2, and grenades do 2.

Note that the AI state bytes in the struct are for simple enemies. Bosses have other state stored elsewhere. For example, in the above crab boss, the AI state and timer control movement but not spraying bubbles, which occurs entirely independently. The density of bubble spray, however, was directly controlled by the life of the boss; e.g. below 0x20 life (it starts with 50) it does the full sawtooth volley with dozens of bubbles.

The Story of ThunderGraft

For those who aren't familiar with it, ThunderGraft was possibly the coolest of the three modding tools I released (the other two being MoPaQ 2000 and MPQDraft). Diablo, Diablo II, Starcraft, and Warcraft II: BNE all use PCM WAV audio (22khz 16-bit if I recall correctly) for their sound effects and music. Diablo used raw PCM WAV audio, while Starcraft introduced (and the other two used) a special "WAV compression", which compressed the audio in lossy ADPCM form, resulting in a compression ratio between 3:1 and 4:1 (though at the cost of audio quality); WAV compression, however, was implemented transparently in the MPQ API - the games saw what they read and wrote to the MPQs as simply PCM, and that's all the audio streaming API was capable of playing (in other words, the audio streaming functions were identical in all four games).

ThunderGraft was a utility that added the ability for all four of these games to play MP3s and Ogg Vorbis, in addition to standard PCM WAVs; even better, it did this in a version-independent way* (the very same ThunderGraft binary worked for all versions of all of those games). Naturally this was huge, especially in the days of dial-up (which was when the modding community first became big). You could use modern audio compression formats that yielded significantly smaller file sizes and higher audio quality compared to WAV compression. Yet ThunderGraft is all but dead now. Why is that?

MPQDraft and ThunderGraft have a few things in common. They're both very simple, clean, version/program independent, and highly effective. The reason is also the same: they both rely on very clean exploits of design to do their thing, without getting into messy exploits of implementation that depend on the precise binary patched. MPQDraft exploited the priority system in the MPQ API; ThunderGraft exploited the fact that the audio streaming API was encapsulated in functions supplied in Storm.dll.

The fact that the functions were entirely contained in Storm meant that I could cleanly capture calls to them and redirect them. For cleanliness, I opted to simply replace the streaming API in its entirety. Anything less would have been version-dependent, as it would have required all sorts of messy code modifications inside Storm's internal functions.

This meant that I needed my own decoding and streaming code to replace Storm's. At the time I just coincidentally happened to have such a thing handy. Specifically, a friend of mine by the moniker Dark_Brood was writing a game engine called Aegis, and happened to have audio decoding/streaming code handy for me to plug into ThunderGraft. He sent me a static library of the code, and in it went. Easy.

Where things took a turn for the worst was when he wrote the next iteration of his game engine. This involved rewriting a whole bunch of stuff, and integrated the various systems in the engine much more tightly (e.g. added garbage collection and other global things). This meant that it was no longer possible to simply extract the audio portion of the engine.

While in theory I could have just continued to use the old version, there was a big problem: I never had the code for the original version, nor did he save a copy after rewriting the code. This is a big problem because static libraries are compiler- and version-dependent. Now the only way I could even compile ThunderGraft was on the very same version the original was compiled on: Visual C++ 6, which is some 11 years old, now, and I haven't even had it installed for many years.

Thus, the only way to resurrect ThunderGraft would be to replace the decoding and streaming system entirely, and thus far I simply haven't managed to muster the effort. After open-sourcing MPQDraft I wanted to do the same with ThunderGraft, but was unable to readily do so for the same reason.

*There is one thing that's version-dependent in ThunderGraft, as there's simply no theoretical way to do it in a version-independent way: importing of non-WAV audio files into maps with StarEdit (the Starcraft map editor). Special support for this was required for several reasons: 1. StarEdit verifies that things imported are WAVs and refuses anything else, 2. it needed to know how long the audio file was in order for triggers to work right. The audio decoding and streaming in ThunderGraft, in contrast, was truly game- and version-independent.

& Very Old Things - Part 1

Bring back any painful memories?

So, a couple days I had one of those evil, perverted urges I'm so notorious for. Specifically, I felt like doing a bit of hacking of Blaster Master. For those not familiar with it, it was an NES game published 21 years ago. A good one, in fact. But before I talk a bit about anything I did resembling reverse-engineering, let me explain the NES hardware to the best of my knowledge (which consists of what I saw in my hacking, and a bit of stuff I looked up online).

The main CPU of the NES is a modified 6502, the CPU used in various Commodore and Apple computers (not that I ever used one of those). The 6502 is a primitive CISC CPU, and in fact somewhat resembles the x86 (though more primitive). It has 3 8-bit registers: a numeric accumulator (A) and 2 index registers (X and Y). Operations generally operate on the value of A and a memory location or literal, and write the result back to A.

It has a stack, though from what I saw in Blaster Master it seems to be relatively rarely used, used mainly to save registers (though even that was pretty rare). Specifically, I didn't see much in the way of stack frames holding local variables. Functions that require local variables tended to have (dedicated) memory ranges allocated to them to be used as private buffers. For example, one address I initially thought was the boss life location actually turned out to be in a buffer region used by the function while updating objects in the object list. This kind of surprised me, as the NES has only 2 KB of RAM; I imagine this must be forced by the architecture, e.g. a lack of instructions to access the stack at a specific offset.

As for the graphics system. If you ever messed around with text mode and text graphics in DOS, the NES graphics system is similar. At the lowest level, graphics are stored as blocks called patterns. Each pattern is 8x8 pixels, 2 bits each (total of 4 colors). The NES has enough video memory for 512 patterns at a time, stored in 2 pattern tables. What exactly it does with these patterns depends. The NES has 3 graphics layers: 1 for background and 2 for sprites (1 in front of and 1 behind the background layer).

deconstructulator provides an excellent illustration for most of the things discussed here. It shows the pattern tables (note that the top half is the sprite pattern table and the bottom half is the background pattern table) and sprites along with a playable version of Super Mario Bros.; although it does not show the name/attribute tables. Refer to that from here onward.

The background layer (illustration below) is very much like the screen buffer in DOS text mode; it's a buffer of screens composed of 32x30 patterns each (indices into the pattern table), called name tables (lost in translation, perhaps?); all patterns in the background must come from the same pattern table. The NES supports up to 4 screen buffers in this way, though it only contains enough memory for 2 of them (if the cartridge doesn't supply additional memory, the game can simply set the NES to mirror the 2 screens).

However, so far each pixel only has 2 bits of color (the bits in the pattern table). An additional table, called the attribute table, supplies an additional 2 bits to the name tables, increasing the total to 4 bits, or 16 colors (though each tile on screen still has only 4 colors within it). However, the attribute table does not contain a value for every tile. Rather, it only contains 1 two-bit entry for each block of 2x2 entries in the name table (so 16x16 blocks composed of 4 patterns). This is the reason 16x16 blocks appear everywhere in NES games - that's the smallest block that can be fully independently controlled.

The background position is specified independently of the sprites. A horizontal and vertical scroll position is specified by pixel for the background, which indicates where the graphics chip should start drawing the background on screen. This is how smooth scrolling works, although implementing this can be quite a trick, as you have to essentially use the name tables as a ring buffer (even more tricky if you support scrolling in both dimensions).




A shot of the side-scrolling portion of Blaster Master (top) and the corresponding, merged name/attribute tables (bottom). The white lines indicate where the top left of the screen currently is (where the two lines cross). The visual discontinuities are caused by the way the game streams the background into the name/attribute tables on demand, filling in only what's on screen in the frame; they're stale data. The color glitches result when the current color in the attribute table for an entry does not match some of the stale patterns still in that name table for that entry (e.g. on the far left the second column of patterns is discolored because they are stale and the attribute entry now corresponds to the first column of patterns, which is on screen).

The NES supports 64 sprites, each either 1 or 2 patterns in size (8x8 and 8x16, respectively), depending on whether a global flag is set. Analogous to the attribute table, each sprite contains the 2 high bits of color (though still that allows only 4 colors per sprite). Other info each sprite possesses includes position (obviously), mirroring parameters, and whether the sprite is in the foreground or background. However, even if you can have 64 sprites, the NES only supports 8 sprites per scan line; if there is more than that, only the 8 with the highest priority are drawn (smart games can cycle through their sprites each frame, but that results in flicker).

There are, however, some tricks that can be done to circumvent some of the innate limitations (e.g. 16 colors, 16x16 blocks, 64 sprites, etc.). These often involve clever but perverse tricks related to swapping out the various things such as scroll offset or sprite data while drawing is underway. One common use of this is to draw part of the screen (the gameplay) with scrolling, while a portion of the screen on top or bottom is fixed (the score area). This can also be used to draw more than 64 sprites per frame, though there's still a limitation of only 8 sprites per scan line.



Blaster Master and others frequently use the background as a grotesque way to draw very large sprites. In the above screen shot, the boss crab is actually the background, while the bubbles, player, and energy bars are sprites (the green areas of the boss are actually sprites, as well). The crab has a couple frames of animation; each of these is on a separate screen in the name table, and every frame the scrolling position is modified. This results in the crab moving around the screen and animating, as if it were a huge sprite.

Oh, and in case you were wondering, yes, this boss frequently exceeds the 8 sprites per scan line limit (that would be 4 bubbles), resulting in the game slowing down to draw them all.

& Summer 2009 Anime Music

As with last season, I was again inspired to post theme songs that I like of current anime series. As with last season, one show's music in particular provided this inspiration - Umineko no Naku Koro ni [When the Seagulls Cry].

Umineko no Naku Koro ni really walked away with the title of best theme music of the season, between the music not being bad, and the lack of any high-caliber competition. The opening especially appeals to me because one of the musical themes I go for is modern compositions/melodies in symphonic/operatic style. The ending I suppose would be classified as fun, in rock opera style with a singer that has the perfect voice to perform the the creepy insane rambling lyrics.

Opening theme: Katayoku no Tori [One-Winged Bird]


Ending theme: La Divina Tragedia


Perhaps given the lack of serious competition I may have lowered the threshold for inclusion in this post, I dunno. Anyway, next up is Kara no Kyoukai [Boundary of Emptiness]: Garden of Sinners: Oblivion Recorder. Kara no Kyoukai is a series of movies that form a single plot line. While some of the themes are shared between all of the movies, some are unique to the movie (in this case the one that just came out a couple weeks ago).

As you can see, the video was replaced with the logo of the movie. Note that I set it to start at 0:42, which is where the theme for this movie starts. The music before 0:42 and after 4:18 is from the main theme of Kara no Kyoukai, which I think it pretty bland.

Ending theme: fairy tale


The rest all fall under the category of fun/cute. Bakemonogatari [translated by some as GhoStory, which preserves the pun] has a pretty fun ending theme with a bit of cuteness. The video of the credits seems to have been replaced with a still of the picture that's in the background during the credits.

Ending theme: Kimi no Shiranai Monogatari [Your Strange Story]


Yoku Wakaru Gendai Mahou [Comprehensible Modern Magic] has a somewhat peculiar ending theme. Like the animation during the credits (which you just know is going to get made into animated GIFs), the music is overly cute, yet strangely catchy (although I can imagine it would make some people want to kill things).

Ending theme: Made in Wonder


Finally, Hayate no Gotoku!! [Like the Wind; this is a pun on the main character's name being Hayate]; first of all, note that the sound on this video is LOUD, so you might want to turn your volume down. This one really crosses the line from cute into obnoxious. While the melody is nice and fun, the "cute" accompaniment makes me want to smash things.

I can only figure that the producer of this series is an absolute copyright Nazi, because despite quite a bit of looking I can't find a single video of this ending theme with the credits animation, which is unfortunate, because that would show you who the infernal peanut gallery is. Instead, I found this video, and I really don't know where it came from. It's called a preview, but as I only saw one copy of it, I'm thinking maybe it's a fan-created anime music video. In either case, it seemed better than the large number of others, which simply played the music to some picture (the album cover, a picture of the character singing, etc.).

Ending theme: Mankai Watashi Iro [something along the lines of My Full Bloom Form]

Introduction to Anime

As the amount I'm blogging has been decreasing for a while now, I'm noticing that the proportion I talk about anime is increasing significantly. For a while now I've listed the series I'm currently watching on the sidebar, and occasionally written anime-related posts (especially lately). This is all well and good if you're an anime watcher, and know basic things like how to find and download anime, but not so useful for people who don't know anything about anime (which are probably the majority of readers).

So, I thought I should provide a very brief introduction. "Anime" is a nontechnical term for Japanese animation. Usually what we call cartoons are intended primarily for children, while anime has no such limitation; this frees anime up to represent just about anything you can come up with, including the more serious types of things that appear here in (filmed) movies and television. Apart from that, anime is vaguely defined by the Japanese cultural themes present in it, which may give it a different feel than our cartoons, movies, or TV shows. One theme that's conspicuously absent in anime is the strong bias to have fictional stories take place in something resembling the real world, resulting in a lot more variation in setting and less adherence to realism in anime than in our movies/TV.

Okay, that wasn't as brief as I was hoping for. Next topic: where to check out anime, if you haven't seen it before (or if you've only seen cartoony children's anime). Specifically, the rest of this post is a listing of free, legal anime series available for streaming online. Generally the quality of streamed episodes isn't near as good as episodes you download, but it has the advantage of allowing you to watching instantly without having to download hundreds of megs in advance (not to mention that I don't know of any free, fully legal sources of downloadable high).

How this works is that I've essentially gone through all the streaming sites I know and made a list of all the series I've seen (or at least the ones that didn't suck so bad I'm not even willing to admit to watching them) and their genres. I threw in a couple series (marked with a *) that I haven't seen, simply because they're phenomenally popular and no list of anime would be complete without them. As anime dubs are often almost as bad as Japanese actors trying to speak English (occasionally seen in anime), I've only included links to dubbed series (marked with D) when there is no alternate subbed version available.

The genres listed are (supposedly) in order from most to least meaningful, but are all off the top of my head; as I haven't seen some of these series in many years (and some not at all), accuracy is not guaranteed (and of course it's always possible that I might simply have mislabeled something on accident). I've defined "fantasy" pretty broadly, so as to include stuff outside the typical Lord of the Rings type story (e.g. I include supernatural). "Slice of life" refers to series centered around the daily lives and activities of the main characters (most commonly school), where the activities usually resemble the life of the intended watcher to some extent. Here I use "fighting" in contrast with "action", where the former refers to things that are substantially composed of a progressive series of fights between the protagonists and antagonists (usually duels, often with named attacks, etc.), while the latter often has more general battle scenes (such as shoot-outs).

The ones I liked most, and would most recommend:
CODE GEASS Lelouch of the Rebellion. Drama, comedy, mecha, action. Note that while I and a large number of others liked it a lot, it's pretty hit or miss with people, so your mileage may vary.
Death Note. Drama, mystery, supernatural
Durarara!!. Fantasy, drama, action
Full Metal Panic! Comedy, military, action, mecha
Full Metal Panic? Fumoffu [sequel]
Fullmetal Alchemist: Brotherhood. Drama, fantasy, fighting, military
Gunslinger Girl. Action, drama
Gunslinger Girl: Il Teatrino [sequel]. Action, drama
Higurashi - When They Cry. Mystery, horror, comedy, drama, ecchi (D)
Hikaru no Go. Gaming, comedy, drama
Kannagi. Comedy, supernatural, slice of life
Last Exile. Scifi/fantasy, drama, action
The Melancholy of Haruhi Suzumiya. Comedy, parody
Mushi-shi. Supernatural, drama (D)
Noir. Action, drama
School Rumble. Comedy, slice of life, romance (D)
Spice and Wolf (both seasons). Fantasy, medieval, slice of life, comedy

The rest I've seen:
5 Centimeters per Second. Drama
11 Eyes. Fantasy, fighting, drama, ecchi
Air. Romance, fantasy, tragedy
Asura Cryin. Scifi/fantasy, fighting, mecha, drama
Aria the Scarlet Ammo. Action, comedy
Baka and Test - Summon the Beasts. Comedy, fantasy/scifi, fighting, ecchi
Bamboo Blade. Martial arts, slice of life, comedy
Beck: Mongolian Chop Squad. Music, drama
Black Butler. Supernatural, comedy, action
Black Butler II [sequel]
Bleach. Fighting, supernatural, comedy
Book of Bantorra. Fantasy, action
A Bridge to the Starry Sky. Romance, comedy, ecchi
Busou Renkin. Fighting, fantasy, comedy
C. Drama, fighting, fantasy
Canaan. Action, military
Chrome Shelled Regios. Sci-fi/fantasy, military, action
Claymore. Fighting, fantasy
Cross Game. Sports, comedy, slice of life
D.Gray-Man. Fighting, supernatural, comedy
Dance in the Vampire Bund. Fantasy, drama, action, ecchi
Darker than Black. Fighting, fantasy/scifi
Deadman Wonderland. Drama, action
Dragon Crisis. Fantasy, action, comedy
Eden of the East. Drama, romance, scifi
Erin. Fantasy, slice of life, drama
Fortune Arterial. Slice of life, supernatural, romance
Full Metal Panic! The Second Raid [sequel]
Fullmetal Alchemist [alternate]
Fractale. Sci-fi, drama, action
Fruits Basket. Fantasy, slice of life, comedy (D)
Ghost Hunt. Supernatural, horror, drama, mystery
Ghost Hound. Supernatural, mystery, psychological
Golgo 13. Action
Gosick. Mystery
Gundam 00. Scifi, mecha, action, drama*
Gurren Lagann. Mecha, scifi, action, comedy (D)
Hanasaku Iroha. Slice of life, drama, comedy
Hayate no Gotoku! Comedy, parody, fighting
Hayate no Gotoku!! [sequel]
His and Her Circumstances. Slice of life, comedy, romance
Honey and Clover. Drama, slice of life
Hyakko. Comedy, slice of life
InuYasha. Fantasy, drama, comedy, fighting
InuYasha: The Final Act [sequel]
Kanon. Slice of life, romance, comedy
Kaze no Stigma. Fantasy, fighting, comedy
Kimikiss: Pure Rouge #. Slice of life, romance
Kino's Journey #. Fantasy, philosophy
Kore wa Zombie Desu ka. Fantasy, comedy, action, ecchi
Kurokami The Animation. Fighting, martial arts, drama
The Legend of the Legendary Heroes. Fantasy, comedy, action
Lucky Star. Comedy, parody, slice of life
Maria Holic. Comedy
Monster. Drama, horror (D)
Moon Phase. Supernatural, fighting, comedy, romance
My Bride Is a Mermaid. Comedy, fantasy, parody, ecchi
My Ordinary Life. Comedy, slice of life
Myself Yourself. Comedy, slice of life, romance
Naruto. Fighting, martial arts, drama, fantasy, comedy*
Naruto Shippuden [sequel]*
NATSU NO ARASHI! Comedy, supernatural
Negima! Fantasy, comedy, ecchi, fighting,
Nogizaka Haruka no Himitsu. Comedy, romance, ecchi
Occult Academy. Supernatural, scifi, mystery, action, comedy
Okamisan. Comedy, slice of life, parody
One Piece. Comedy, action, fantasy*
Oreimo. Comedy, parody
Otome Yokai Zakuro. Supernatural, comedy, romance
Pandora Hearts. Fantasy, comedy, action
Pani Poni Dash. Comedy, school life, parody
Princess Jellyfish. Comedy
Pumpkin Scissors. Military, drama, comedy, action (D)
Rideback. Mecha, drama, military
R.O.D. The TV. Fantasy/scifi, action
Rumbling Hearts. Drama, comedy, ecchi
Sacred Blacksmith. Fantasy, action, comedy, ecchi
Saki. Gaming, drama, comedy
Samurai X [AKA Rurouni Kenshin]. Martial arts, fighting, comedy, drama (D)
Sasameki Koto. Comedy, slice of life
Seitokai no Ichizon - Student Council's Discretion. Comedy, parody
Shana. Fighting, supernatural, comedy (D)
Shigofumi: Letters from the Departed #. Drama, supernatural, psychological
Shiki. Mystery, horror, fantasy
SHANGRI-LA. Drama, scifi, action
SKET Dance. Comedy, action
Sketchbook. Comedy, slice of life
Skip Beat! Drama, comedy, romance
Slayers. Fantasy, fighting, drama (D)
Slayers NEXT [sequel] (D)
Slayers Revolution [sequel]
Slayers Evolution-R [sequel]
Sora no Woto. Slice of life, military, comedy
Special A #. Comedy, slice of life, romance
Squid Girl. Comedy
STEINS;GATE. Scifi, drama
Strain: Strategic Armored Infantry. Action, scifi, mecha, drama
Tears to Tiara. Fantasy, drama, action
Tegami Bachi: Letter Bee. Fantasy, action
Trigun. Action, comedy, scifi
Vampire Knight. Supernatural, drama
Vandread. Scifi, mecha, comedy, ecchi, action
Welcome to the NHK. Comedy, drama, psychological (D)
White Album. Drama, romance
The World Only God Knows. Supernatural, school life, comedy, romance
xxxHolic ['xxx' seems to refer to the supernatural, here]. Supernatural, drama (D)

Finally, the list of noteworthy free, legal anime sites, listed from largest selection to smallest:
Anime News Network
Crunchyroll
Hulu
Funimation
Joost

& Summer 2009 Thoughts

So, we're now several episodes into the summer 2009 anime season. I've been meaning to write mini-reviews of new series for a few seasons, now, but never got around to it; we'll see if I actually make it to the end of (writing) this post, this time.

First of all, I always get my first looks at new series from Random Curiosity's season previews. and I'll probably end up quoting some of their descriptions here (and go in the order they're listed in the preview). With the exception of one, all the ones I'm going to list here piqued my interest at least enough to give them a shot (at least the first episode).

Charger Girl Ju-den Chan [that's the official English name on CrunchyRoll; it's listed as Fight Ippatsu! Juuden-chan!! on the preview]

Preview says:

Let me start by saying that I’m not convinced that this series is anything other than a vehicle for fanservice and nudity. Originally by the author of Mahoromatic and KissXsis, Juuden-chan is a story about a clumsy girl whose job it is to inject energy into people who are depressed. If that doesn’t tip you off on what kind of series this’ll be, then maybe a visit to the official site where you can remove some of the main character’s clothing will. And then there’s the promo video (see below) that’s got the main character orgasming during a transformation sequence.

Verdict: who could say no to that? Me, for one.

Umineko no Naku Koro ni [When the Seagulls Cry]
Genre: mystery, drama, psychological
"Sequel" to Higurashi no Naku Koro ni [When the Cicadas Cry], another mystery murder series, about a rich family getting together to hash out the details of their inheritance after the patriarch dies. From there things quickly go downhill, as six people are murdered on the first night.

Higurashi, as I mentioned, was quite a strange series. I didn't particularly like the characters, nor did I like some of the excessively slapstick comedy [OMGWTF @ Higurashi Rei 1], but it had an awesome and intelligent high-level story, and it was told very well. As such, I liked Higurashi as a whole, and I've been waiting for Umineko ever since I heard about it (it was originally a game, like the Higurashi series). So far it seems to be more drama than comedy, although there's also been some of that.

By the way, I hear that the Higurashi games have just been licensed, and will be released in English pretty soon.
Verdict: definitely watching

Taishou Yakyuu Musume [Taishou Baseball Girls]
Genre: slice of life, comedy

High school girls forming a baseball team in the early 1900s. I was/am pretty wary about this one. I've seen entirely too many (which is to say a few) "cute girls do (often boy) things in cute ways" series that rely on girls being cute as the primary attraction (a genre I've named Shoukawa). E.g. while I did watch and enjoy "the definition of moe" K-ON! (girls forming a rock band) last season, it really had entirely too much moe, and I would have liked it more if it had less.

There was, however, a shred of hope with this series. Japan is in some ways even more conservative than the US, so it would be unheard of for there to be a girls' baseball team in that time (e.g. how in the first episode one girl refers to baseball as "that thing boys do"). If they could create a realistic depiction of the cultural and social clash of something like this (as opposed to simply saying "Here's some cute girls doing funny things! Watch!"), that could be interesting enough to justify watching it. So I decided to take a look and see.

Well, thus far only the first episode has been translated by a decent group, so that's all I have to go on. It wasn't bad, to sum up in a couple words. There were indeed signs of exploiting moe, but there were also signs of interesting cultural material - enough to keep my hopes alive, for the moment. I'll know more after a couple more episodes.
Verdict: still watching


Two of the girls (the rest all ran away immediately) on a field trip to watch boys play baseball, after seeing the batter nail the pitcher in the head with the ball.

Bakemonogatari [I'm told this is wordplay on 'bakemo monogatari', which would be something like Supernatural Story]
Genre: supernatural/mythology, comedy, randomness

This one I hadn't really planned to watch, though I decided to take a look after some of the WTF stuff in the first episode summary on Random Curiosity (the girl stapling the guy's cheek comes readily to mind). It's a rather weird story about a guy who encounters a number of supernatural phenomena in his daily life; in the past he himself had been a vampire, and in the time of the series he encounters a number of girls with various supernatural problems. Sounds like a dating sim adaptation to me (which was part of why I didn't initially intend to watch it), though I really hope that's not the case, as the second girl has to be in elementary school.
Verdict: still watching. I don't know if I'd say it's good; but I really hate to drop series after I've watched a few episodes, and it hasn't been bad enough to do that. It really doesn't help that it's by SHAFT, who I rather dislike; they can certainly draw pretty pictures (as you can see in the summary), but they have an incredibly distinctive artistic style that I find quite disorienting and relatively difficult to follow.


Girl #1. She can probably kill you with each of those.

Canaan [main character's name]
Genre: action, drama, fighting

Another series about an inhumanly good gunfighter girl with underworld dealings, lots of action and gunfights, and something about bio-terrorism. It sure sounds (and looks, thus far) like its girls-with-guns predecessors Noir and Madlax, though as far as I can tell it's not by any of the same people. As a matter of fact, it's an adaptation of a video game, so I suppose the fact that it seems pretty decent to even people who haven't played the game is noteworthy.
Verdict: pretty decent

Kanamemo [not too sure about this one; Kana could be the main character's name, but the only thing I could think of for "memo" is some misapplication of the English word to refer to newspapers]
Genre: comedy, slice of life

Story of an orphan girl who gets hired to work and live at a newspaper delivery place, and her daily life. That was enough to make me take a look, as slice of life comedies are one of the things I'm most into. While it's always possible I'm not giving it enough of a chance, the one episode I saw lead me to believe it was merely the sum of it's parts, as listed by AniDB (categories): coming of age, large breasts, lolicon [pedophilic], shoujo ai [lesbian], small breasts.
Verdict: taking my ball and going home. Perhaps if I'm ever desperate for something to watch I might see if the second episode was like the first; but not any time soon.

Sora no Manimani [Following the Sky? This is a really tricky name to crack, for somebody with limited knowledge of Japanese]
Genre: comedy, slice of life, romance

Another slice of life comedy, this time about a small astronomy club at a high school. Of course this one also caught my attention for something to at least check out. Out of the first two episodes it seems pretty average, as far as slice of life comedies go, though it's difficult to come up with something more cliche in anime than the harem [multiple girls that all like the male main character]. This will probably end up in the slot of "something to watch when I'm out of better stuff to watch".
Verdict: better than nothing

Spice and Wolf II
Genre: drama, comedy, romance, medieval slice of life

Based on a series of novels, this series is about a traveling merchant in the middle ages and his (sage wolf god) traveling companion. This is one of those series that features more mature topics than most, such as economics and politics. I liked the first season of it a couple years ago, and I've been looking forward to a second season ever since. If you're looking for something outside the ordinary anime, this is one to consider.
Verdict: good


Wolf and hangover. In case anybody is wondering, these are all pictures I took while watching the series, not ones taken specifically for this post.

Yoku Wakaru Gendai Mahou [something like Modern Day Magic to Be Well Learned]
Genre: comedy, fantasy

In this world, like in Serial Experiments Lain, reality is fundamentally composed of information, and like data in a computer this information can be altered; this is the nature of magic. I thought that creative take on magic was interesting enough to warrant checking out. Unfortunately, the first two episodes lead me to believe that an interesting premise is all this show has going for it, and in general it appears to be a dud; and with an average rating of 6.4 out of 10, it seems like a lot of people concur.
Verdict: on life support. If I'm feeling generous, I might watch the third episode (next week) and see if it manages to improves any.

& That Memory Leak

I'm pretty sure that a while back I mentioned a particular Firefox plugin called Feed Sidebar. It's a nice little RSS feed plugin that does exactly what I wanted an RSS plugin to do (and all others work differently). As such, I'm rather fond of it, and have been rather tolerant of its faults.

The particular fault I believe I discussed was that it leaked memory. With the ~15 RSS feeds I have on it set to update every 10 minutes, it leaked about 20 megs of memory per hour. While many would probably not find this to be a serious problem (e.g. 8 hours x 20 megs/hour = 160 megs leaked before shutting down for the day), as I tend to leave my computer running for weeks straight, this was a moderate annoyance. Left on its own, Firefox would crash about every three days due to address space exhaustion (32-bit applications have a 2 gig address space, and fragmentation can reduce the amount actually allocatable below that; I was seeing it crash around 1.5 gigs). Much more frequently, I'd start World of Warcraft and my computer would grind to a halt, as Windows really, really doesn't like it when you get > 90% memory usage (up until a month or two ago, when I have 4 gigs of RAM), and I'd have to manually restart Firefox at that point.

On one occasion I e-mailed the author about the problem; he said that he'd been looking for the leak for a while, and was stumped. Unfortunately, as I haven't done anything with Javascript (what Firefox plugins are written in) in over a decade, and I don't know the first thing about the Firefox plugin architecture, I couldn't go looking for the problem myself as I've done so many times in the past (at least 3 or 4 incidents on the blog).

However, a couple weeks ago the problem suddenly become much worse. Immediately after installing Firefox 3.5, I noticed that it was now hemorrhaging about 150 megs/hour, more than seven times as fast as in 3.0 and earlier (in fact, at first I thought it was that 3.5 was just unstable, as it crashed about every day; then I noticed that it was allocating massive amounts of memory). After verifying both that this was consistent/reproducible and that this was indeed due to the particular addon, I e-mailed the author again, with my new data.

Apparently that got a pretty quick response. A couple days later he sent me a test build he wanted me to try. After some looking, he'd come to believe that there was a bug in Firefox that was leaking SQLite resources; resources that should have been freed when an SQLite connection was closed were being leaked (it was not clear from his e-mail whether this was a new bug with 3.5, or just that the quantity of resources leaked was greater in 3.5). This test build included a workaround for it (presumably he saved the connection instead of creating a new connection every time it updates the RSS feeds, but he didn't say).

This seemed to work well. After installing it, I immediately noticed that it was not hemorrhaging memory like it did before (previously it was leaking about 25 megs each time the RSS feeds were updated, which was now gone). Rather, after a couple of days of collecting data, I concluded that it was now only leaking 1-2 megs each update (about 10 megs/hour).

It's not clear yet whether this is true leakage (which would suggest that one leak was plugged but another remains) or that this is a side-effect of the workaround. It's conceivable that Firefox might delay freeing SQLite resources as long as a connection is in use; if he's indeed keeping an SQLite connection open the whole time, we could imagine that this "leak" is not a leak (lack of resource reclamation) so much as a deferral of resource reclamation. If this is the case, this should go away after Firefox fixes the SQLite connection leak and he goes back to creating a new connection on every update.

We'll see.

Incidentally, version 4.1 of Feed Sidebar was released today; this is the version I tried a test build of. After I've had more time to collect data I'll have to see if it's leaking the same amount as the test build, or if there have been further modifications.

Useful Fact of the Day

As of a few versions, you can no longer get the nice graphical Visual Studio profiler in anything less than the most expensive Team Suite edition of Visual Studio. For most people (namely, those that don't have 6 grand to spend to get a profiler), this isn't really an option.

Fortunately, Microsoft has been kind enough to release a command-line version of the Visual Studio 2008 profiler for free. If you need a profiler, get it. Fortunately for me, I got Visual Studio 2005 and 2008 Team Suites for free through my school via Microsoft Developer Network Academic Alliance; unfortunately, I won't be able to do that with Visual Studio 2010, so hopefully they'll make the 2010 profiler available that way as well.

RIP E Terra Blog

As you can see, I've removed the link and RSS feed for the E Terra blog from the sidebar. After several years of no real content and over a year since the last post (that's even worse than this blog!), I'm finally putting it out of its misery. If I'd been a prolific writer on the development of E Terra there might have been a purpose to a separate blog, but I sure haven't been, once the class I had to create it for ended. If I have anything to say about E Terra or game programming in the future, I'll just put it here, instead.

By the way, a few semesters ago (after the class I wrote E Terra for) I got a very nice book: 3D Game Engine Design (second edition). It's largely about graphics engines, though it does have occasional other topics (e.g. that's where I learned to write a good collision detection system for E Terra). What's really nice about this book is that it's not limited to theory; while it does explain the theory behind things, it also shows how to bring everything together into a working system. Most (useless) textbooks, in contrast, simply explain the theory and (if you're lucky) give you pseudocode for each separate concept, with no advice on how to integrate everything into a complete system. If you're interested in game programming, this is by far the best book I know of (I originally found it looking through the book shelves of my graphics teacher).

& Detexify

So, somebody just linked me to Detexify, a very neat little program that reads your "handwriting" and tries to find the TeX special character that you just wrote.

Now, personally I don't have much use for such a thing, as I don't use TeX. However, it happens to be open source, which means that if I can muster the energy I'm going to try it with the set of Chinese characters and see how well it can do identifying those. If it can do that decently I have some much less theoretical uses for it...

& the Genitive

Last in the series of core cases (the four cases almost universal among languages that use grammatical case) is the genitive (the nominative/absolutive and accusative/ergative are described here, and the dative here).

Genitive Relation
The genitive relation consists of a noun phrase (the minimum noun phrase in most languages being a single noun) that modifies another noun phrase. As described by grammar books, a genitive phrase is a noun phrase that specifies or describes another noun phrase, with the result being that the genitive phrase helps to answer the question "which?" with regard to the modified noun phrase; e.g. "the girl next door's dog" (genitive in italic) answers "which dog?", "music of Starcraft" answers "which music?", etc.

As it essentially contains all manner of modifying phrases, clearly the genitive is an extremely broad relation, and there are quite a few more-specific relations that fall under the umbrella of "genitive". A semi-exhaustive listing of the various types of relations the genitive can express:

• Physical possession: "my computer"
• Abstract possession: "your happiness"
• Relational: "his wife"
• Compositional: "bottle of water", "box of nails"
• Quantitative: "half of them"
• Subjective: "her snoring"
• Objective: "its destruction"
• Purpose: "sledgehammer of castration"
• Location: "citizens of America"
• Origin: "Kazuhiro Sasaki of Japan" (for those who don't know, he's a Japanese baseball player that was recruited to play professionally in America)
  
• Affiliation: "Apple's Steve Jobs"
• Attributive: "thing of beauty"
• Topical: "Of Mice and Men"
• Appositional/classifying: "President Obama"
  

It's likely that all languages can represent all genitive relations, though the methods used in languages differ, and a single language may have multiple mechanisms that may or may not overlap. A genitive case (or multiple cases that each represent more constrained relations) is one option to represent the genitive, but a language need not have an actual case, nor are case(s) and non-case methods mutually exclusive. Japanese, for example, does not have a genitive case, while Latin (and many other Indo-European languages) has both genitive case and a variety of prepositions that allow expression of specific relations.

One very good reason for a language to have more than a single mechanism of representing the genitive is that any single such mechanism would necessarily be ambiguous. Take, for example, the English phrase "betrayal of Illidan"; with this phrase it is unclear whether the genitive is subjective or objective - that is, whether Illidan is the betrayer or the one betrayed. Other such examples can be invented based on other uses of the genitive.

Of course it's not all bad; if there were no ambiguity in language, puns would be impossible. One real-life example of genitive ambiguity comes from IRC. jfroy says 'Snow Leopard meeting' in the sense of 'meeting about [Apple] Snow Leopard', to which I reply, interpreting that as 'meeting with a snow leopard':
<@jfroy> Snow Leopard meeting over. Ow.
<enma_hinobara>Next time don't poke it
<enma_hinobara>It's not Kaity

The Genitive in English
It's arguable whether English still has a genitive case; if it does, it only exists for (some) pronouns, where it indicates a purely possessive relation (which is why it might better be called the possessive case). It does, however, have three different mechanisms for expressing genitive relations in general - the periphrastic genitive, the analytic/agglutinative genitive (both are my own terms, so don't expect to find them in a dictionary), and the possessive.

The periphrastic genitive renders the genitive phrase as a prepositional phrase with the preposition 'of', e.g "fog of war". This is the "true" genitive in English, in that it is the mechanism that can express nearly every possible genitive phrase (although some phrases may sound better using one of the other mechanisms), while the others are much more restricted in use.

The analytic/agglutinative genitive renders the genitive relation purely by shoving two (or more) nouns together, e.g. "milk carton" (compare to "carton of milk"), "wood chips" ("chips of wood"), etc. I call it the analytic genitive because the genitive relation is expressed purely analytically - through word order, rather than word form. I call it the agglutinative genitive because in more synthetic relatives of English, such as German or Old English, the modifying word(s) would be agglutinated with the modified word to form a single large word (this can sometimes produce very long compound words); for example, "girl next door" would be "Nachbarmädchen" in German (literally "neighborgirl"). In English, this type of genitive is restricted to certain types of relations, and is especially used for classification.

Finally, English has a special means of expressing possessive relations, a subset of genitive relations (it's unclear exactly how this form originated; some argue that it's an evolution of the genitive case, while others are more skeptical of that conclusion). Note here that English has a rather broad concept of possession, and as such the possessive can be used with some relations that aren't strictly possessive in nature.

The Genitive in Latin
As a relative of English, the genitive in Latin is much the same, in that genitive relations can be expressed via prepositional phrases (which are substantially similar to their English equivalents) or analytically; however, Latin also has an actual genitive case (a result of which is that it does not need a possessive structure as English does), which is used very commonly. A few examples of the genitive case in Latin:

• "agricolae [farmer, genitive] filia [daughter, nominative]": "farmer's daughter"
• "horum [these, genitive] omnium [all, genitive]": "of all these/of all of these"
• "vir [man, nominative] magnae [great, genitive] virtutis [courage, genitive]": "man of great courage"
• "fossa [ditch, nominative] decem [10] pedum [foot, genitive]": "ditch of ten feet/ten-foot ditch"
• "Rex [king, nominative] belli [war, genitive] cupidus [desirous, nominative] est [is]": "The king is desirous of war"

The Genitive in Japanese
Finally, As Japanese does not have true case, like English it uses non-case-based structures for constructing the genitive. Japanese has two genitive-marking particles - 'no' and 'na', which differ only in whether the genitive phrase is abstract (e.g. 'baka' - 'stupidity') or concrete (e.g. 'shakunetsu' - 'scorching heat') - used in the periphrastic genitive, as well as the agglutinative/analytic genitive (the genitive may or may not actually be agglutinated). However, Japanese also shows off several uses of the genitive that English and Latin do not.

Consider the rough definition of the genitive - something which specifies or defines a noun phrase; where have we heard this definition before? Well, for one, it's the definition of adjectives. In fact, a language can get by just fine with almost no true adjectives (e.g. the kind we have in English), instead opting to use one or more of the three alternate methods I talked about previously. One of these methods is to use the genitive with descriptive nouns, a method that is used extensively in Japanese and Caia (in fact, it's the primary method in Caia). A couple example from previously used words would be "baka na inu": "stupid dog" (literally "dog of/with stupidity") and"shakunetsu no koi": "scorching love" (literally "love of scorching heat").

The other structure this definition matches is apposition; that is, a restatement of something previously said for the purpose of definition or clarification, such as the italicized part in "Julius, son of Ambrose". In a previous post on the predicative, I explained that in Indo-European languages such phrases are in the same case as the phrase they restate, but that we could imagine other reasonable ways of expressing them. In Japanese such phrases may be expressed either by the analytic genitive (e.g. "kemono [beast] no sousha [player, generally of an instrument] Erin": "Erin the beast player") or the periphrastic genitive (e.g. "Hamelin no violin hiki [player]": "Hamelin the violinist" - literally "violinist of Hamelin").

Finally, some languages, such as Japanese and Caia, allow other relational phrases to be put into the genitive, where the genitive particle indicates the modification of a noun phrase, and the other relational particle specifies the precise relation of the genitive phrase (you might say the genitive particle applies top-down, while the other relational particle applies bottom-up). Some examples of this in Japanese:

• "ano [that] group to [with] no kankei [relationship]": "relationship with that group" (literally "relationship of with that group")
  
• "ano kaisha [company] to no keiyaku [contract]": "contract with that company"
  
• "Asia kara [from] no ryuugakusei [exchange student]": "exchange student from Asia" (literally "exchange student of from Asia")
  
• "Hokkaido kara no omiyage [souvenir]": "souvenir from Hokkaido"
  
• "America ye [towards/to] no monkowohiraku [opening the door; this is rendered as a noun in this phrase, not a verb, in this example]": "opening the door to America" (literally "opening the door of to America")
  
• "anata [you] ye no tegami [letter]": "letter to/for you"

& the Real World

Martial arts in a skirt, eh? I thought that kind of thing only happened in anime.

(found via http://www.darkroastedblend.com/2007/01/anti-us-north-korean-posters.html)

The Dative

The dative, or indirect object, is one of the four core cases - those cases that are almost universal in languages that have case - along with nominative/absolutive, accusative/ergative, and the genitive.

While the details vary by language, the general concept for the dative is a goal or direction of an action (especially with regard to transfer or movement), or the one perceiving an action. In the study of grammatical role, the dative roughly corresponds to the role of goal (although it may have additional uses in a given language). While English has pretty much lost its case system, the logical dative remains, usually expressed with the prepositions 'to' or 'for'.

Some examples of the various uses in several languages from Wikipedia and other sources (note that I'm mainly covering the most common uses, not ones that are specific to certain languages):

Goal of Transfer:
Latin: "Regina puellae pecuniam dat" ("The queen gives money to the girl")
Japanese: "Kodomo ni yaru" ("Give to the child")

Goal of Movement:
Japanese: "Ano hito wa gakkou ni haitta" ("That man has gone to the school")

Goal of Intent or Benefit
Latin: "Auxilio vocare" ("I call for help")
Latin: "Puellae ornamento est" ("It is for the girl's decoration")
Latin: Graecis agros colere ("To till fields for the Greeks")
Greek: "τῷ βασιλεῖ μάχομαι" ("I fight for the king")
Greek: "πᾶς ἀνὴρ αὑτῷ πονεῖ" ("Every man toils for himself")

Goal of Experience:
Latin: "Vir bonus mihi videtur' 'the man seems good to me"
Latin: "Quid mihi Celsus agit?" ("What is Celsus doing [that I am interested in]?")

One of the more peculiar uses (at least for English speakers, as I don't think English has anything like it), is the dative of possession. This renders phrases of possession as phrases of existence with the possessor in the dative. The logical basis of this usage is that in terms of grammatical role, in phrases of possession the possessor is technically classified as the goal.

Some examples:
Latin: "Angelis alae sunt" (literally "For angels there are wings"; freely "Angels have wings")
Greek: "ἄλλοις μὲν γὰρ χρήματα ἐστι πολλὰ καὶ ἵπποι, ἡμῖν δὲ ξύμμαχοι ἀγαθοί" (literally "For others there is a lot of money and ships and horses, but for us there are good allies")
Japanese: "Watashi ni tsuno ga nai" (literally "For me there aren't horns")
Tsez: "Кидбехъор кIетIу зовси" (literally "For the girl there was a cat")