Archive for May, 2008

When you think about it, the original Nintendo was an amazing system. That to this day millions of people still love the games on that old system says something about its staying power. Yet even compared to personal computers of the day, it was seriously underpowered. This of course was an attempt to keep the Nintendo low in price and accessible to a larger audience. It was an obvious success not only business-wise, but also technically.

The Nintendo had a 6502 processor, an extraordinarily common processor found in many computers at the time, running at a measly 1.79 MHz. It had a 16-bit memory address bus, which means it could only access up to 64KB of RAM at a time without special hardware. It had a whole 2KB of built-in RAM. This really isn’t a whole lot to work with. So how did such awesome games come from just that?

First, the Nintendo had a few tricks up its sleeve:

  • It had a custom-made graphics processor. Most game players these days have heard of GPUs — this was similar, though it was called a PPU (Picture Processing Unit). It was optimized to display tile-mapped backgrounds and sprites on the screen. It refreshed the screen at a consistent 60 frames per second for American (NTSC) TV’s (beat that Crysis!). With this single-mindedness, it was able to perform some amazing feats using very little data.
  • Various types of cartridges expanded the hardware capabilities of the system. It wasn’t uncommon for cartridges to include additional RAM — up to around 64kb (a lot better than 2kb!). On occasion it was battery-backed, so it could be used as save RAM. Some cartridges even expanded the graphics and sound capabilities to the system — adding interrupts, additional graphics memory, even more colors and sound channels!
  • Cartridge ROM was usually mapped to two different 16kb areas of addressable memory. For a 32kb game, that’s all you need. However, since it’s really hard to do much with 32kb for an entire game, most cartridges contained many banks and allowed you to switch between them at runtime. This allowed for a theoretically limitless cartridge size.

OK, cool, so the Nintendo was made for games, and it could be expanded on a per-game basis. But how could it pack so much into such a small amount of space? Most games these days require several gigabytes of data, so how could games fit in such small amounts of ROM?

Case in point: Metroid. The Metroid Database (thanks Ian) has a ton of information about Metroid, including some cool technical details. These guys have disassembled the ROM and commented it and added labels and symbols! Furthermore, they have a detailed page describing the level data in Metroid. Here’s a summary:

  1. Screens are divided into 8×8 tiles. Each pixel in the tile is represented by a 2-bit index into that tile’s palette (yes, each tile can only have 4 unique colors), which means that each tile takes 16 bytes. There can be up to 256 tiles loaded at a time, and they’re hard to swap out individually, so there are typically only 256 tiles per area. The whole thing takes about 4kb. The screen resolution is 256×240, which means there are 32×30 tiles on the screen. Each tile is given a 1-byte ID (since there are only 256 tiles available), so the screen map takes just under 1kb. There is some additional data needed to specify 4-color palettes assigned to each tile, which brings the total up to exactly 1kb. All of this is handled by Nintendo’s fancy PPU.
  2. Metroid further groups 2×2 tiles together, making a 16×16 meta tile. There are only 16×15 meta tiles in a screen, which cuts the map size to 1/4th (just under 256 bytes as-is).
  3. Metroid goes even further and defines arbitrary groups of meta tiles, which the author calls “structures”. They can be any rectangular-shaped areas of meta tiles that can be placed around the screen at specific points. Now screens are made up of collections of 3-byte structure identifiers.
  4. All levels in the game are divided into “rooms”, which are one screen in size. There are less than 256 different rooms in each area — some of them are repeated several times! Since there are less than 256, you can give each room type a unique 1-byte ID.
  5. The overall level structure is defined in a 32×32 map, where each entry in the map is a single byte corresponding to the room ID that should be displayed there. This takes a total of 1kb.

This is a rather insane amount of compression. With this setup, all of Brinstar (the starting area) takes up:

  • 32 bytes for the palette
  • 94 bytes for room pointers
  • 100 bytes for structure pointers
  • 2115 bytes for room data
  • 620 bytes for structure data
  • Around 4096 bytes for tile data

…adding up to 7027 bytes to encode all of the background graphics for the entire Brinstar area! For comparison, a 50×50 24-bit color Windows BMP file (without the header) is larger than this. Hell, the text in this post is almost that size! Yet it was a huge area that would take hours to fight your way through, and you would have fun doing it.

Obviously there’s more to the game than the background graphics. With its haunting music, immersive exploration, fun gameplay, and a twist at the end, Metroid is a classic among classics. Yet you got all of this with a ROM that weighed in at less than 128kb. You can fit 10 Metroids in a standard 3.5″ floppy.

It’s amazing what software engineers can do given limited constraints.

Read Full Post »

Traditional data-driven websites are usually built with a particular pattern:

  1. Client makes an HTTP request to a server component using a URL.
  2. Server component performs some operation on a data model and collects results.
  3. Results are passed to some smart templating engine (PHP, JSP, ASP, Ruby, etc.) that creates the necessary HTML and Javascript.
  4. HTML is sent back to the user to be displayed in their browser.

This is a typical application of the model-view-control (MVC) pattern. Here, the model is the what understands and manages the data. The view is the combination of the templates and the end-results displayed in the user’s browser. The controller is a server-side component that dictates the user’s flow, talks to the data model, performs validation, and passes the data to the templating engine. Large-scale websites often further dissect the model into decoupled services and run them in external processes (a service-oriented architecture, SOA). The vast majority of web frameworks follow this pattern, and it’s been with us for a while. Ruby on Rails, Struts, WebWork, PHP, ASP.NET, Spring MVC — no matter where you go, this pattern is ubiquitous.

Yet there’s something wrong here.

I’ve seen it for a long time, but I could never quite say why it felt wrong. First of all, the templates I wrote have always been messy and hard to read. It’s not atypical to find 3 or 4 languages mixed in together. Take for example this snippet of JSP code:

<select name="type">
<c:forEach items="${types}" var="type">
<option value="${type.id}" <c:if test="${item.defaultType == type.id}">selected</c:if>><c:out value="${type.name}"/></option>
<input type="button" value="Add <c:out value="${item.name}"/> to cart" onClick="addItem('<c:out value="${item.guid}"/>')"/>

This example allows the user to an item to a shopping cart, selecting a type (e.g., color or size). It automatically selects the default type for that particular item, names the Add button with the item’s name, and when the button’s clicked, it calls a JavaScript function to add the item (for validation and other checking).

Ugh, this crap is hard to read (and the font in this theme isn’t helping). The select list option has some embedded JSP that uses EL inside an HTML tag to determine if “selected” should be included or not. There’s another JSP tag inside that value attribute of <input> for displaying the item’s name, which itself contains another quoted attribute. Even worse, another attribute contains some Javascript containing another JSP tag with a quoted attribute to include the item’s GUID (and to close everything at the end requires a }”/>’)”/> ). Despite all this complexity, it still isn’t doing it correctly — it doesn’t specify how it should quote the item’s GUID inside a Javascript string! This isn’t a complaint about just JSP — no matter which templating system you use, you will end up doing this kind of thing everywhere.

Some of these occur often enough that we can abstract away some of this silliness. JSP has a handy ability to create tag libraries — custom XML tags that will output something given a set of data. They’re written in Java, which can cleanly handle the data and perform complex logic. In fact, the above example uses the JSTL – JSP Standard Tag Library. You could create your own tag libraries to quote some data properly for some context, such as a Javascript string. And when those tag libraries become too hard to read, you can create yet another library to abstract it further, ad infinitum, creating abstraction upon abstraction upon abstraction. What a mess.

Another thing — what’s the type of all this data? Everything gets flattened to a string. When the controller gets the data passed in from the form, it has to convert that data from strings into some type that the data model requires. Furthermore, data being passed to the template gets turned into strings, even though the HTML and Javascript may care what type the data is. It’s simply not possible pass an object from the controller to the view.

What about validation? It can and often does happen in 3 places: the model, view, and controller. You definitely want some validation in the model to check pre- and post-conditions. The view should check it to avoid having to wait for a full round-trip HTTP request to get errors. And the controller should check it when it converts everything from untyped strings into the typed data the model needs.

What else could go wrong here? Plenty. Note that with the above pattern, every time we need to get or set data, it dictates who the use moves through the site (i.e. presentation flow). Need to get the next piece of data? Be prepared to go to a brand new page. Some applications get around this by pre-loading a ton of data in case the user needs it, which is a Bad Thing. Newer applications use AJAX to to have Javascript contact the server and retrieve the data. Older web MVC frameworks have a hard time with this, though newer ones are getting better (gotta give some credit to Ruby for this one).

Does web application development have to be this hard? Or is there a better way to do this?

SOFEA: A New Hope

Apparently I wasn’t the only one who thought this was screwed up. Some smart folks noticed the problem, delineated the specific issues, asserted why they failed, and proposed a solution. How cool is that? Life above the Service Tier changed my life. Well, it at least explained why I always felt like an idiot making websites. Let’s see how other client-server applications, specifically so-called “rich clients”, typically do their thing:

  1. The user loads up their client application, clicking around and checking out stuff.
  2. Whenever the client needs to get or set data from the server, it makes a request to the server.
  3. The server does its thing and returns some data.
  4. The client uses the data to update the view.

Here are the differences between this paradigm and the traditional web service paradigm:

  • The Controller in this MVC pattern exists on the client, not the server. It can direct presentation flow without interchanging data with the server.
  • Data is typed throughout the entire process. The server-side exposes a contract — if you give me this data, I’ll give you this data back, with these side effects. The client creates a properly formatted message to send out, and the server returns a properly formatted message back to the client. The data aren’t just strings — they can be numbers, dates, lists, whole object hierarchies. Both the client and server understand these types and take advantage of them.
  • There are no templates containing increasingly abstracted logic. The view may have an external representation, such as HTML, XML, GUI code, or a Flash applet, but it is updated and controlled by the view’s code in response to user input and data from the server.
  • No validation needs to be performed on untyped data. The view may still choose to do some basic validation to avoid contacting the server in case of errors, but this is the only validation that needs to be done prior to having the model take a look at it.

Well, that pretty much solves all of the problems we talked about above. Huh. Neat. So how do we do this with websites? Well, up until recently it really wasn’t possible. Browsers were too primitive and strictly enforced the traditional pattern. It wasn’t until AJAX arrived that would could give it another look. Most browsers in use these days support AJAX. Some webapps such as Gmail use it to an almost frightening degree.

Why is AJAX so novel? It’s not that it’s novel — it simply allows web pages to do what rich clients have always done: contact a server behind the scenes. That alone allows us to decouple presentation flow from data interchange and move the controller from the server to the client. Furthermore, data typing and integrety can be enforced using standard web services used for service-oriented architectures. The entire view can be expressed in HTML, CSS, and Javascript — easily and efficiently served by a good web server such as Apache. This has the nice side effect that you don’t need to maintain a heavy web application container such as Tomcat to manage user sessions, control presentation flow, and coordinate with services. Using Dynamic HTML, your Javascript code can directly manipulate the view in response to user and server input — no more templates.


Life Above the Service Tier describes this model, which they call Service-Oriented Front-End Architecture, or SOFEA. It’s an enlightening read, and I highly recommend it. A website dedicated to discussion of this technique can be found at the Thin Server Architecture Working Group.

Wait a minute, you want me to use more Javascript? Are you nucking futs?

Everyone seems to hate Javascript, and for good reason. While the language itself is actually quite powerful, web browsers have traditionally mucked the whole thing up. Different browsers handle Javascript in different ways — it can be maddeningly inconsistent. For this reason, many developers try to do as little Javascript as possible to avoid the whole mess.

Fortunately, many libraries exist that help ease this pain significantly. Prototype is an incredibly powerful library that makes writing Javascript code almost easy and abstracts away much of the browser-specific badness. And as I said, the Javascript language itself is a very powerful language. It doesn’t have class inheritence, or even classes at all. Everything is an object, and you can choose to extend objects with new methods and variables. You also can pass around functions, which turns out to be an extraordinarily useful features for UI programming. Trust me, you’ll like it.

SOFEA isn’t limited to HTML/Javascript either. The same principles apply no matter how “rich” your client is for a client/server application. You can just as easily use a Flash applet using ActionScript or a Java applet if it makes sense for your website.

How practical is all of this at this time? It’s getting more so every day. A leading Java web service framework, Apache CXF, recently introduced tools that allow you to create Javascript clients from a WSDL defining the service. It uses SOAP calls and enforces data types. A strong controller framework in Javascript is still needed for large-scale websites, but it’s still possible to create impressive large-scale web applications using these techniques today.

It’s an exciting time to be a web programmer.

Read Full Post »