A Developer's Life Stages

I ended up writing a novel as a comment on Jamie Fristrom's blog post on Speculative Generality. Read his entry. I'm reposting my comment here.

Developing The Simplest Thing That Could Possibly Work

In Forrester Research's 10 Mistakes in Software Development, #3 is overscoping a solution and #9 is jumping into development without enough research, and we've all done it. :(

A friend consulted at a large transportation company in the Kansas City area. They'd been gearing up for a massive conversion from their existing AS/400 systems to a completely Java-based system. Remarkably, in the early stages of the project, they decided to wrap the entire JDK in their own custom framework and decreed that all developers use these wrappers exclusively. As a result of this, they obtained -

• little or no added functionality,
• more limited abstractions than the raw JDK,
• minimally tested code underlying everything,
• the requirement to train all incoming Java developers on their framework and,
• worst of all, the obligation to maintain many more thousands of lines of code.

I've observed that developers tend to progress through a number of stages in their career. These are like the stages of grief: inescapable. This is because each stage produces a set of skills and philosophies that are eventually synthesized in the seasoned software developer.

The Underengineer

The underengineer is elated at his ability to get things done quickly and be productive, disdaining others (usually the overengineer) for what they see as excessive rumination and for producing an excessive amount of code for a given task. You can count on these guys to get stuff done. Will it be done 'the right way?' Only if by accident. Underengineers are often unable to discern 'the right way,' often because they've spent little time reading and maintaining other people's code.

A developer may begin to come out of this stage when he tires of fixing or writing the same code (in different places) over and over again. Or perhaps he'll be propelled into the second stage by an enthusiastic reading of Design Patterns or a sudden grasp of UML.

The developer at this stage is fascinated by accomplishing the task at hand and it is this stage in which he learns how to code and debug.

The Overengineer

The overengineer knows that he can solve any single development task and has become fascinated by possibility. Abstraction is magical. How can any piece of code be used to solve multiple tasks? Paradoxically, this usually ends up producing more code for any one task. While the underengineer shakes his head at this, the overengineer knows that his approach will produce much less code for an entire set of similar problems. Meanwhile, the overengineer looks at the underengineer's hackery with contempt. The question the overengineer rarely asks himself, though, is will there be a large enough set of similar problems to justify this effort? And so he abstracts everything in the name of flexibility.

The overengineer is sometimes shocked to realize he's become much less productive in terms of functionality than before. He can't seem to get anything done! Still, he produces as much (if not more) code and suddenly becomes capable of building much larger systems than he could as an underengineer.

This is the stage in which the developer learns architecture and the value (and painfully, the costs) of abstraction. This is the stage of the architects of the transportation system conversion discussed above.

What kills the overengineer? Maintenance. Dependencies. Broken abstraction. Realizing that the flexiblity he built in is unused and real systems change in ways he could never have anticipated. At some point, and probably many, the overengineer will get a phone call at 2am asking him to come in and fix an issue that breaks his whole architecture. After a few of these heartbreaking moments, his world view begins to change again.

The Seasoned Developer

The seasoned developer is skilled in coding and debugging from his time as an underengineer and is a skilled architect from his time as an overengineer. What's more, he's come to understand the following:

The primary reason for abstraction is to simplify implementation for a given set of requirements.

If abstraction doesn't simplify, ditch it.

The seasoned developer also realizes that the solution domain for a given problem may extend beyond technology. People often try to use technology to solve social or organizational problems. Conversely, people frequently attempt social or organizational solutions for essentially technological problems. Recognizing these incongruities before they become a software design and implementation can help to avoid doomed projects.

The organizational problem in the transportation example above is that software architects were assigned to do a job before anyone knew what job they were to do. The proper response would be to do nothing - or better, to work on a different project until the problem domain was fully understood.

Instead they chose speculatively general busy work, incurring a much higher cost.

Spread This Number?

AACS encryption key controversy

This bad boy?

13,256,278,887,989,457,651,018,865,901,401,704,640

So where was I when all the noise about this was going on in April? Ah, illegal numbers. What will they think of next? Anything that can be represented digitally can be represented as a single (usually very large) number. Software, movies, music, etc..

That reminds me of a story I read once about a civilization that encoded all its existing knowledge as a single mark on a stick. The position of the mark on the stick divided by the length of the stick yielded a decimal number less than one. The digits of the fractional part of that number represented the totality of the civilization's knowledge in an encoded form.

Could this work?

Let's think about this. A proton has a diameter of about 1.5E−15 m. That means we'd get only about 16 decimal digits before we're measuring sub-subatomic dimensions. And Shannon tells us it would take lots of digits to represent that knowledge in any reasonable form. Actually, it would take about 2.3 million decimal digits per megabyte of data. And we're talking at least trillions of megabytes of data.

So no, there is no way - now or ever - that this could work.

Building Materials #1

The Material Abstraction

In computer graphics, Material is a fundamental concept. Like a sheet of really special stretchy wallpaper, it is the collection of elements and properties that describe the visual characteristics of a surface. This encompasses texture, color, transparency, reflection, refraction and much more. Even so, it does not usually say anything about the geometry whose surface is described by a Material.

While Material is a useful abstraction for us, as software engineers and artists, it maps poorly to modern computer graphics hardware. The Material abstraction wildly cross-cuts a large number of subsystems in a modern renderer. As a result, most easy-to-use direct implementations of this concept you're likely to encounter are slow and/or rigid. That being the case, it's a great computer science problem to examine, and any solid, easy-to-use, reasonably fast and flexible solution is useful.

Relationship to Geometry

Let's define a low-level Geometry type as simply a list of vertices and an associated description of the vertex layout. Let's call a description of a vertex layout a Vertex Format. We'll talk about these vertex layouts at length later. The vertex layout is necessary because each vertex in a Geometry can be annotated with additional information, such as texture coordinates, the normal vector of the vertex, color, or pretty much anything you want.

Since the visual appearance of a geometric surface is described by a Material, any higher level geometric abstraction such as a mesh will refer to Materials as well as Geometries. An individual Geometry will be associated with a single Material, although multiple Geometries may point to the same Material.

Unfortunately, a Material needs to know the layout of the associated Geometry. In fact much of the time, the layout and the additional information included in each vertex in the Geometry is in determined by the choice of Material associated with it. This is an unpleasant reverse dependency that tightly couples Geometry creation with a Material.

Relationship to Textures

Here, let's broadly divide the Textures category into two parts - dynamic and static. Dynamic textures are those that can be written to and modified at runtime. An example might be a frame of a video during playback. Static textures are those that we probably load from disk. They don't ever change.

Textures may have different uses. The most common, of course, is that a texture represents an image to be wrapped around a surface. However, in the age of Shaders (see below), textures can represent any two+ dimensional array of data and are frequently used to store a vector (often a per-pixel normal vector) at each pixel.

A Material can refer to static and dynamic textures.

Relationship to Shaders and Shader Constants

Shaders come in different forms. Generally, there are vertex and pixel shaders. A shader is a small program that runs on the GPU for each vertex or pixel. These days, the classic distinction between the two is blurring. In the past an assembly language that was compiled into the hardware-dependent GPU machine code was the predominant way to program shaders. Currently, higher level languages such as HLSL and Cg are more common.

Shaders are tightly coupled with the vertex layout of Geometries and the number and intent of Textures in a Material. Shader Constants are the primary method of game-to-shader communication and as a result, they tend to impose a great deal of coupling between the shader design and the design of the code that invokes it. Some shader constants really are constant (PI, for example), some will be bound to attributes of the Geometry. Others may be related to world or game state. In a lighting shader, the constants may hold the location of the five nearest light sources. Shaders usually require that the current world transform be passed in as shader constants.

Applying a Material

So how do we apply a material? It depends on what the material specifies and a lot of other things as well. We'll look at some possibilities in the upcoming parts.

Render Components for a Given Material Pass

The Impossible Dream #3

This is, of course, going incredibly slowly and that's just alright.

Script

I'm exploring an interesting architecture. I'm starting to use my script language Pair to script core parts of the game. Pair is Lisp/Scheme-like and very compact (the VM executable [compressed] is 28k without many external functions!). I designed Pair a few years ago with gaming in mind. The original intent was to use it to script many (hundreds or thousands) simultaneous events without having to make everything a state machine. Pair is multithreaded at the virtual machine level and not at the OS level, yielding very lightweight threads. To accomplish this, an explicit frame stack is maintained for function calls, and they are not implemented as C++ function calls underneath. Like Stackless Python which takes a similar approach (and is also used in gaming for its facility in concurrency), it means that Pair can (and does) support continuations because the call stack can be directly manipulated. One of these days I'll put up Pair and source.

On the Side

In the 80's in front of a house in the Kansas City, Missouri area a man built a boat. It was an incredibly tall half-built steel boat in this guy's yard. Every once in a while we'd drive by and see people working on it and a bit of progress here and there.

One day, my dad decided to stop and talk with the guy, with us little kids in tow. My brother and I took the opportunity to see the beast up close. And it was freaking amazing. To us, it might as well have been a Saturn V.

Many (and many of the best) software developers I've known have had little (or large!) projects on the side. Interviewing developers, I've sometimes asked about their side projects. It's a question that can yield great insight. Where does their passion lie? What problems attract them? What someone does with free time is what they really want to do, regardless of what they might let on in an interview.

It's an indicator of passion and of a drive to create. I've recently come to understand that these side projects also fuel the passion for our day-to-day work and inoculate against burnout. As developers, we have the power to create something from nothing. For some small portion of our time, to follow our own muse can be an exhilarating act.

Some companies, notably Google, have institutionalized this idea, giving developers a certain percent of time during office hours to work on their own projects. I'd expect Google to reap a significant innovative advantage with its policy.

What compels about software development is only partially solving puzzles and, for me, is about the joy and power of creation. Unfortunately, this power is, in part, illusion and the illusion is intensified by software's abstract nature. It nearly always seems far easier to write software than it actually turns out to be.

I'll demonstrate this illusion. Which requires more effort in man-hours: building a bridge across a medium-sized river or developing a game such as Spider-Man 3 or Madden 07? How about the Empire State building or Windows XP? I don't know the answers to these questions, but I don't believe that I can fully trust my intuition to provide them. In any event, good software requires enormous, and univerally underestimated, effort.

Maybe one of these days, I'll have another kooky neighbor, this time toiling away in his garage or barn building a Space Shuttle or something like in that goofy movie "The Astronaut Farmer" (which I have not yet seen). I'll know and he'll know and the fire department and the old ladies from the HOA will all know that it will never lift off. And I'll sit in the garage with that guy, and put the LOX and kerosene tanks together. And it will be freaking amazing.

(Updated 7/11/07)

(Rebekka and I watched The Astronaut Farmer last night and now I wish I hadn't referred to it. I'd hoped for something good, like Apollo 13 or October Sky but Astronaut Farmer was godawful. The premise was utterly absurd and the profoundly self-centered protagonist Charlie Farmer reminded me of an Allie Fox (from a great movie The Mosquito Coast) barely disguised under a veneer of sentimentalism. The best part? The rocket launches from their barn. As in a barn made of wood and filled with hay. And speaking of wood, during one of the bloopers, Billy Bob Thornton asks, in jest, if this was a film directed by Ed Wood. I was wondering the same thing.)

Moving Parts

This is where I intend to catalog (all?) the components of a commercial game. I will periodically update this post.

Why?

I've bought and read many books on game development. The bad ones are generally 1000 pages of C++ source code. The good, useful ones tend to fall into two categories.

• Narrow and deep (books that equate 'game engines' and 'rendering engines', for example)
• Broad and shallow (books that contain light sections on rendering, sound, networking, data structures, etc.)

Still, even books in the broad category aren't that broad. The reason? Books can only be so thick. My point really is that the practice of game development includes a vast array of subspecialties and I'd kinda like to enumerate them here. Hopefully with input from my readers (that's you, Mom) that I'll add. So this list will be ultra-broad with no depth whatsoever. Depth will have to wait for subsequent posts.

Now, not every game will have or need all these systems, but it's crazy just how many most games will need. So, for right now, this is a brain dump and I've only just begun..

Offline

Content Creation - tools - geometry, mesh creation
Content Creation - tools - geometry, mesh creation - offline CSG tools
Content Creation - tools - image creation
Content Creation - tools - motion capture cleaning
Content Creation - tools - higher level 'world' assembly, including assigning gameplay attributes to objects
Content Creation - tools - sound creation/mixing/production
Content Creation - tools - mission/level creation
Content Creation - tools - statistical data, skill/inventory data and attributes
Content Creation - tools - state machine creation
Content Creation - tools - script debuggers, interactive interpreters for testing
Data Management - managing generated code
Data Management - asset dependency management
Data Management - geometry processing - ie. adding attributes, triangle stripification
Data Management - texture processing - texture packing, format conversions, bit depth conversion, etc.
Data Management - asset databases (SQL, XML)
Data Management - metadata collection about assets, data mining for global performance enhancement, data mining for content creation automation, etc.
Data Management - version control systems
Code Management - Code Generation - from asset databases, other offline sources
Code Management - Build System - standard way of building the game for all developers
Code Management - Library/Component Management - system(s) for cataloging, versioning and incorporating libraries and reusable components
Code Management - version control systems
Testing Systems and Methodologies

(much more offline/pipeline side to come; the game pipeline gets far less attention than it deserves, often with disastrous results)

Runtime

System - threading libraries/primitives
System - error handling, logging, assert handling
System - string handling, regular expressions
System - elementary data structures, STL, etc.
System - fast math primitives
I/O - File - standard file i/o
I/O - File - file compression/decompression
I/O - File - loading game assets (meshes, textures, scripts, game data files, etc..)
I/O - File - low-level game asset caching
I/O - File - asset 'packaging' into larger files
I/O - File - object serialization support
I/O - Network - lobby
I/O - Network - server side
I/O - Network - event handling (see Events below)
I/O - Network - publishing player data to online services
I/O - Network - web access services
Localization Support - text databases
Memory - efficient game asset caching
Memory - memory pooling systems
Memory - garbage collection systems
Events - event handling/dispatching systems
Events - 'replayable' game state management
Events - game state represented as loadable/saveable data stream
Events - game state policies - random/deterministic, etc..
Events - game 'flow' management
Sound - Mp3, WAV, Ogg, etc. playback
Sound - runtime mixing, filters
Sound - in game capture
Sound - stereo, 5.1 surround sound
Sound - 3d audio
Input - console controller
Input - force feedback (output)
Input - spatial (Wii, SIXAXIS)
Input - mouse
Input - keyboard
Input - other (Guitar Hero, EyeToy, DDR, Donkey Konga)
Graphics - rendering - geometry processing
Graphics - rendering - geometry processing - progressive meshes and LODs
Graphics - rendering - geometry processing - efficient spatial subdivision
Graphics - rendering - shader(s), per pixel lighting
Graphics - rendering - scene graph management
Graphics - rendering - GPU based utilities for non-graphics
Graphics - rendering - geometry processing - in game CSG operations
Graphics - geometry processing - human animation
Graphics - geometry processing - motion capture
Graphics - rendering - decaling
Graphics - rendering - particle systems
Graphics - rendering - dynamic skyboxes/skydomes
Graphics - images - loading/encoding image formats - DDS, TGA, JPG, etc.
Physics - collision detection
Physics - collision detection - geometry processing
Physics - collision handling, mesh processing for non-rigid object effects
Physics - ragdoll animation
Physics - wind, environmental effects
Gameplay/AI - script
Gameplay/AI - state machine systems
Gameplay/AI - classical AI algorithms
Gameplay/AI - events - collisions, sphere of influence effects, NPC line of sight, NPC earshot
Gameplay - Cars - Damage Models
Gameplay - Cars - Driving Models
Geometry - Modeling
Geometry - Inverse Kinematics
Geometry - Rigging/Tagging/Markup
Geometry - Animation
Geometry - Procedural Animation (ie. Cloth, Hair, Jelly/Spring Models, etc..)
Geometry - Facial Performance and Lip Sync'ing
Rendering - Textures
Rendering - Shaders
Rendering - Animated textures/maps
Video - codec(s)/playback - MPEG, MJPEG, WMV, VP6, Bink, Madcow, etc..
Video - color space conversion
UI - rendering
UI - event handling systems, architecture and data
UI - script
UI - some games have a large amount of UI (ie. Madden, with its enormous UI)
UI - HUDs
Data Management - embedded SQL database (not just for plain-old IT anymore)
Embedded Control - script languages
Control - in-game gameplay tweaking utilities, runtime assets updating support

(more..)

Online Game Services

Online - lobby
Online - server side
Online - (deterministic) player position prediction and tracking (online multiplayer)
Online - publishing player data to online services
Online - web access services
Online - billing tracking for online services (online multiplayer)
Online - player data storage
Online - accessibility from PC website

(more to come, but I'm sleepy now and I want to go to bed..)

Confessions of a College Drop-Out

Numerous articles have been written about college degrees and IT careers. Here's my contribution.

I dropped out of UMKC in my junior year. It was a purely economic decision - I had a high GPA and I enjoyed school. Living at home and working my way through school making less than $8 an hour, I was broke. At my boss' urging, I applied for an entry-level job at Worldspan developing airline reservation software in assembly language for IBM mainframes. Worldspan's recruiters were skeptical, "with no degree, don't hold your breath."

Worldspan trained its engineers internally rather than attempting to recruit engineers with the required niche experience. They were filling their next class. To isolate candidates with aptitude for assembly language, they tested us. A week later they called back, "you got a perfect score!", and offered significantly more than I'd hoped for. It was a no-brainer.

Worldspan had the most effective and practical training I've encountered - either in school or at any other company. Training was a probationary period. As a result, the instructors invested heavily the class' success since failure to pass the instruction meant the trainee's dismissal. This contrasted strongly with my college experience, where instructors seemed often barely involved.

Shortly after starting at Worldspan, I met Rebekka and began spending all my time with her. We married about a year later, had our first child about a year-and-a-half after that. The question of going back to school is moot now. My school credits expired long ago.

Ryan Burkett once quoted someone who said, "The United States produces remarkably incompetent 21-year-olds and remarkably competent thirty-year-olds." It's an intriguing statement that rings true for software development.

Could I have finished my degree while working a full-time job, married and with kids? Sure, but it simply didn't make sense. Once employed in a good software development job, a bachelor's degree wouldn't make me any more money. In software and IT in general, experience rules. It has been years since I've been asked in a job or consulting interview if I have a degree. Electronic Arts offered my current job before I filled out the official application where I disclosed my level of education as High School Diploma.

For sure, a college degree is a valuable asset. The good news is that the lack of one does not necessarily spell failure.

Jet Engines

Creating high-performance technology in a competitive field? Managing your developers' weaknesses and ignoring their strengths may cost you.

Let me illustrate.

Iron accounts for 35% of the Earth's mass. And from iron comes carbon steel (iron and carbon) which accounts for 90% of steel production. As metals go, steel is cheap, abundant and easy to work with. Steel is versatile and good at most everything metals do. If steel was your employee, it would be a damn fine one. You might want all your employees to be just like steel. After all, compared to other materials, it has few weaknesses - but also few extraordinary strengths.

Steel can't do everything. It distorts at extreme temperatures. Steel is not brittle like ceramics but it's also not nearly as hard. It is much cheaper than titanium but weighs almost twice as much. It is a poorer electrical conductor than gold. And of course, steel's strength and hardness in extreme conditions doesn't hold a candle to the single crystal nickel-titanium superalloys* from which they carve jet turbine blades - albeit at enormous cost.

Every one of these other materials demonstrates incredibly high performance in a narrow space and is either prohibitively expensive or ineffective in other arenas.

Even so, it is impossible to build a modern, efficient jet engine with just typical carbon steel.

The bottom line?

Profound strength and profound weakness often come together. Yet without a spectrum of those profound strengths at your disposal, it won't be possible to develop cutting-edge technology at a competitive level.

I don't mean to say that a well-rounded developer can't also have profound strengths - I know several of these people. It's a no-brainer that you need to do what it takes to keep these gems. Reward reliable and well-rounded developers for their lack of weaknesses and, if you need their contributions, reward brittle, unorganized, high-maintenance, socially-inept (insert favorite weakness here) developers for their strengths. Or someone else will.

Notes

* Some of single crystal superalloys are nickel-iron alloys. If iron is the dominant metal in the alloy, these superalloys might be considered steel.

For More Information

Now, Discover Your Strengths

Rolls Royce Trent Aeroengine

Excellent PowerPoint of the Rolls Royce Trent Aeroengine series commercial jet engines
Rolls Royce Trent Aeroengine engine materials

Wikipedia: Iron Steel Ceramic Cermet Silicon Carbide Superalloys Complex Metal Alloy Composites

Development of Single Crystal Superalloys

The Impossible Dream #2

Previous: The Impossible Dream #1

Ground Rules

Mantra 1: The mechanic first, then the game.

It's no fun putting blood, sweat and tears into an unfun game. We structure the game around a solid mechanic - prototype first to find addictive key element(s) and elaborate. Tag is one key element we've identified.

Mantra 2: Build a game, not an engine.

I've seen a number of home and indie game projects go south stuck at the "let's build our engine" phase. Nothing overly general - we build into the code what we need to do the trick. I'm not saying there's no place for useful abstraction here, I'm saying that a general purpose rendering or game engine is not our goal.

Mantra 3: Fit the design to resources at hand.

Building an open world game at all is our first violation of this. Still, we need to embrace this reality instead of fighting it. Operating with restricted resources can force us to come up with creative solutions to problems we otherwise wouldn't have looked at. Of course, it may also prevent us from finishing anything ever.

Mantra 4: Don't underengineer or overengineer, but if you must choose one, underengineer.

Why? Because underengineering is easier to fix.


A Unflinching View

Let's start the impossible dream by looking, somewhat realistically, at our available resources and the strengths and weaknesses of our position.

Resources

• A few development hours a month divided among game design, software development and content creation.
• A powerful target platform (PC).
• Development tools - Visual C++ 2003.
• Direct3D and its auxiliary libraries (see No need for portability in Strengths, below) .
• Third party content creation tools - Milkshape 3D (registered), Unwrap3D (registered), POV-Ray.
• Open source and free resources on the web for game development.
• Free content from other sources that can be legally used in our game.

Strengths

• Strong software development skills.
• A powerful target platform (PC).
• No need for portability.
• A great deal of freely available software for offline and runtime use.

Weaknesses

• Poor content creation ability.
• Few hours to dedicate to the project - it'll be done in like one hundred years.
• Little monetary investment.

Strategies

Make the most of our particular set of resources:

• Simplicity - a simple, compelling core game. No minigames, nothing like that.
• Prototype the game mechanic first.
• Automation - machine generated content, mostly offline, possibly at runtime.
• Reuse/scavenge (to a point) freely available content generation tools and software.
• Reuse/scavenge (to a point) freely available software for the runtime.
• Seek out free content that we can legally use in game.
• Creatively adapt the game design, including character and plot, to cater to our strengths.
• Use a hooded figure for the main character, allowing us to skirt the animation issue for the main character. We can use a simple segmented model for NPC's. We can animate the hood & clothing of the main character with cloth animation, which is CPU-intensive, but nearly content-free.
• Use public domain (classical, folk music?) music for the soundtrack.

Oh, and yes, there's so much more to come.

The Impossible Dream #1

True Story

In Mexico I met a poor farmer named Miguelito who lived in the little town of Metepec (Atlixco), Puebla. Many years before, in a vision, the Holy Virgin of Guadalupe entrusted him to build a cathedral, high up on the hill above the town. She promised him that he would not die until he'd set the final stone. He quickly enlisted the help of the townspeople and over 15 years constructed a small, beautiful hilltop church. At the time Miguelito showed me the rust-colored church it was nearly complete and he explained that this meant that his time was near. His mistress had been generous enough - Miguel was 104 years old!

My Impossible Dream - My Own Open World Game

So, is it possible, working a few scant hours each week on evenings and weekends to build a (simple) open-world game by myself? We shall see. I've occasionally been working on the game since about a year before I came to EA but I think I'll make a more public spectacle out of it on this blog - to keep me motivated.

So why do I even want to do this? Because it's impossible.

Some prototype screenshots
Some generated content and concepts

Next Time: in the next installment of The Impossible Dream, we'll look at what this game will be about and how we will use automatic content generation to build our world.

Explorers and the Game of Tag

I'm partial to games of exploration. The Ultimas and their relatives were my early favorites. These days, I play games like Grand Theft Auto, Godfather, Spider-Man 2 and Oblivion.

Why? It's the joy of discovery - the pleasure of finding things out. So what makes a great open world game? In the context of video games, an open world is a toy upon which a game can be built. So first, what makes a great open world?

Big, not too big

It's no secret that we measure the size of our universe in the time it takes to cross it. The world shrinks with the inventions of the railroad, the automobile and the airplane. Unlike other open world games, the world of Superman Returns seems in turns enormous and tiny, depending on whether you are walking or flying at supersonic speeds. When a world is too big, we can spend all of our time simply getting around. Too small and it seems cramped and unimaginitive.

There must be some novelty to every distinct area or region. The 1987 game The Faery Tale sported a world of over 17,000 screens. There were so many repeating patterns of landscape and it took so long to cross that it was hard to stay interested in exploring the world. In an interview with Game Informer, Radical, in creating Hulk: Ultimate Destruction, specifically addressed this issue of variety.

Mechanics

The mechanics of a world are crucial to its experience. They are the laws of the game's universe. It is important that the game itself cannot subvert these rules. In GTA, this includes the way cars move collide and interact, that any car can be rigged with bombs and the general behavior of the people and objects that inhabit Liberty City. Another important mechanic in GTA is police response to player actions. The world of GTA is rich with mechanics largely orthogonal in purpose. It is this richness that makes GTA great. In Spider-Man 2, the central mechanic is web-swinging. The world of Spider-Man 2 is designed to be experienced through web-swinging and so it is an inseparable element of Treyarch's Manhattan. In GTA, Spider-Man 2 and Superman Returns the speed at which one is able to move through the city is variable and its 8control is in some mechanic anchored in the game world itself. This provides a sense of enormous freedom. In some of these games, this speed increases as the player progresses through the game.

Even so, at this level, the open world is still a toy. Now let's ask the question, what makes a great open world game?

The Childhood Game of Tag

Of course, GTA 3 is the prototypical open world game. Recently, I started playing it yet again and it still may be the best. What makes it fun? The underlying element is tag. The ancient children's game is incredibly simple, infinitely flexible and has strategic depth. Tag benefits from richness and complexity in a large world. The ideal tag world has nooks and crannies in which to hide from predators and from which to ambush prey. Layered on top of that, in GTA, there a number of other game mechanics, many - most? - of which are themselves variations on tag.

These layers of tag and alternating roles of hunter and hunted in GTA 3 stand in contrast to Spider-Man 2's races which also aim to capitalize on a large in-game world. Unfortunately, racing is much less fun than tag. Even though it's one of my favorite games, Spider-Man's races don't appeal to me. What appeals to me about Spider-Man 2 is the absolute euphoria of swinging and the crazy missions (levels?) like Mysterio's burning theater and the Statue of Liberty.

Tag (from Wikipedia)

Players: 2+
Rules complexity: Low
Strategy depth: High
Random chance: Low
Skills required: Running, Hiding, Observation

UML's Accidental Complexity

Accidental complexity is the complexity imposed by a given approach (in this case, a language) to solving a problem as opposed to an essential complexity of the problem itself. Recently, I documented a system I'd developed for a presentation for my coworkers. I diagrammed the class relationships in UML in Visio. Then I started swearing as I always do whenever I use UML. Now don't get me wrong, I enjoy UML and it's a valuable and useful tool when its limitations are understood.

So why does UML make me swear when I use it?

• UML is graphical and two-dimensional.


• A UML design should be readable, preferrably at a glance without too much study.


• UML is general, intended to apply with equal descriptiveness to multiple object-oriented languages.

These goals of a UML design are irrelevant to the original language implementation. And, of course, the implementation language will have its own accidental complexity whose concerns must take higher precedence. Nevertheless, readability is important. An unreadable UML diagram is a waste of everyone's time.

What effect does UML representation have in describing software designs? Since subclassing allows classes to inherit lines of association from their parents while containment does not, readable UML favors subclassing over containment/composition which, in C++ based object oriented languages (such as C++, Java and C#), is inappropriate and even wrong (later, an entry on subclassing vs. containment).

Below, an artificial abstract class is introduced to tame UML complexity. Keep in mind that this diagram represents a very simple design.

Before -



After -




The first diagram resembles an electrical circuit and its suffers from the same difficult problem - complex, multidimensional relationships flattened to a two-dimensional plane. In the second, we introduce a false abstract class simply to preserve readability.

Clearly, readable UML representation as a requirement for software design is not a useful constraint - especially when it degrades the quality of a software system. This is an issue that must be understood when using UML to design or present software systems.

Speech Impediment

(Updated 7/10/07)

Lisp (and to a lesser degree, Scheme) fascinates me. Simple in the extreme and yet incredibly powerful, it is a thing of beauty. I learned Lisp by writing Lisp interpreters and compilers - usually to embed in other applications. As an embedded language Lisp excels - it is among the easiest languages to implement. Implementing it well, however, is an altogether different proposition.

By programming language standards, Lisp (1958) is an ancient tongue. It is older than COBOL by a year and older than C by more than a decade. And it is timeless.

Don't laugh but it's the coolest thing to build a tiny and reasonably fast Lisp bytecode VM (Pair, a current project of mine that I never get to, weighs in at a mere 28K!) and then shove it inside some application and make it do all sorts of things machines were never supposed to. Like thinking, for example :).

Lisp & Scheme

muSE - Embeddable Scheme dialect and more importantly, its associated blog.
Lambda The Ultimate Programming Languages Weblog
Elk

Some Favorite Lisp and Scheme Books

Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp
Lisp in Small Pieces - Great for building Lisp interpreters and compilers.
On Lisp
Lisp
Structure and Interpretation of Computer Programs - Don't buy this classic though - it's free online.

Let Me Count The Ways (Part II)

In the Sieve of Eratosthenes post, I mentioned that at work (EA) we have an optional programming challenge every once in a while. It was started last year by Jim Hejl and it's called Hacker's Delight - named after the excellent book of programming tricks by Henry S. Warren.

I love this stuff. Why? Who knows? Anyhow, this time I wrote the challenge - Hacker's Delight #6. I chose the { 64 choose 4 } problem from Let Me Count The Ways. My fast solution was initially ~3.9ms. Since I had not yet aggressively optimized it, I did that and got it down to ~2.5ms. That solution was written completely in C++. I figured that was about as fast as it got because it turned out that ~2.5ms is (slightly) faster than memset(data, 0, 635376 * sizeof(unsigned __int64)) !!

In short order, solutions came in that were almost exactly as fast as mine with quite different algorithms. Hmm. I thought, the bottleneck is memory-processor bandwidth - ~2.5ms is simply how long it takes to write 4.8mb of data. All the other processing is swamped by that.

Even so, Jim was experimenting with SIMD approaches and had an SSE version of 'memset' that executed in about half memset's time. I started playing with that but couldn't figure out how to use that to get better performance out of my algorithm.

Then Jim tells me that he received an entry from EA United Kingdom that executes in ~1.25ms - all SIMD (MMX)! The gauntlet is down. I asked him not to forward it to me or let me see it.

So today I finally got my own MMX version to about ~1.25ms. It seems to execute slightly faster than Jim's SSE memset. While minor speed improvements may be possible (on the order of tenths of milliseconds), I'm convinced that there's no way to get significantly faster performance.

I could be wrong.

When it's all over, I will post a more detailed description of the optimization steps for those of you who are interested. For those who are not, z z z z z z z z z z...

[The related, and more detailed document Optimizing 64 Choose 4 (.pdf)]

Muddy Waters

A fascinating view of anti-pattern/pattern Big Ball of Mud and its relatives. Big Ball of Mud is the kind of horrifically structured software we have all seen and shunned throughout our careers. Software of this sort is not just poorly architected, but lacks any architecture whatsoever. Nevertheless, the authors argue, when an approach is so pervasive and universal as this one is, there must be something it does well.

Citing shanty towns as an instance of the Big Ball of Mud pattern, the authors say:

Shantytowns emerge where there is a need for housing, a surplus of unskilled labor, and a dearth of capital investment. Shantytowns fulfill an immediate, local need for housing by bringing available resources to bear on the problem. Loftier architectural goals are a luxury that has to wait.

Traditionally good architecture in software dramatically reduces maintenance requirements and failure rates. Values that traditional software architecture respect are robustness, maintainability/low cost of maintenance, performance and efficiency. To achieve these goals, the development of such software requires software architects (not cheap), more sophisticated (and therefore more expensive) developers, and, in general, more development time.

In contrast the Big Ball of Mud development style values low cost of initial development and is willing to achieve that by accepting a relatively high cost of continuing maintenance as its solutions are not robust. It requires no architects, far less skilled developers and less initial development time. However, it may also require a larger dedicated maintenance staff.