Blobs in Games

Kingdoms of Amalur game maps

2012-01-23T17:38:00.001-08:00

Last month I described the reasons I don’t like the maps in Skyrim. Below are some maps from Kingdoms of Amalur: Reckoning, a game that’s been compared to Skyrim.

Here’s the world map in the game:

It shows where I am, the areas I’ve discovered so far, my current destination, areas of the world along with their names, and ways to travel between areas/zones. The map uses light shading and subtle texturing to keep the main areas clear and readable. Non-walkable areas are darker and strongly shaded to distinguish them from the main areas.

Here’s a local area map in the game:

It shows where I am, portals, merchants, healers, NPCs (white circles), dungeons, roads (main and side), shrines (green circles), and things I’ve spotted but not investigated yet (brown boxes). The investigation spots only show up if I’ve leveled up an exploration skill. In the northwest an area is dark because I haven’t explored it yet. Walkable areas are tan or gray, with subtle texturing. Non-walkable areas and unexplored areas are dark.

Here’s another area:

It shows larger and smaller roads, two bridges, a river, and monsters I’ve spotted. The monsters only get placed on my map if I have leveled up an exploration skill. Several areas fade to black because I haven’t explored them yet.

I love these maps! They are clean and easy to read. They show what’s important. They omit irelevant details (clouds, rocks, trees, plants). They’re updated as I explore and discover new things. They help me figure out where to go and how to get there.

How well do these maps answer the questions from my post about Skyrim’s maps?

Player question	Amalur	Skyrim
Where have I been?	places, zones, roads	places only
What areas have I missed?	area map only	area map only
What have I done?	no	no
Where can I find resources?	some *	no
Where can I get some product/service?	yes	no
What do I want to return to?	no	no
Where have I been told to go?	one quest	all quests
What are the main areas?	zones only	zones, lakes, rivers, towns
What locations have I been told about?	(don’t know)	places only
How do I get to a specific place?	yes	no
How long would it take me to get somewhere	no	no
What dangers are along various paths?	in area map only *	no
Where are events occurring?	N/A	N/A
What has changed?	no	no
What did I miss?	N/A	N/A
* requires leveling up an exploration skill

I only played the demo for a short time, so it’s possible I’ve missed some aspects of the maps in Kingdoms of Amalur. I’m finding the maps to be much more useful than the ones in Skyrim.

Tutorial: probability and damage rolls

2012-01-22T18:16:00.001-08:00

I’ve been interested in interactive diagrams for a while now, and started playing making illustrations with HTML5. I’ve written a tutorial on using randomness for damage rolls. Implementation notes:

I’m using Mike Bostock’s D3.js + SVG for the diagrams.
I’m using Bret Victor’s Tangle library for diagram parameters.
You can drag the parameters around to change the diagrams. The idea is that you can edit the parameters in the sample code, and see the diagram update too.
The draggable numbers from Tangle work on the iPad too.
Most (all?) Android and Touchpad browsers don’t support SVG. :-( (Maybe I should’ve used Canvas)
Older versions of Internet Explorer don’t support SVG. :-(
I designed the page to reformat itself for mobile browsers, narrow browsers, and wide browsers. I used CSS media queries for reformatting the text, but unfortunately had to use Javascript for redrawing the diagrams.
Red Blob Games is where I’ll be placing my new tutorials and articles, instead of my Stanford alumni account.

At some point I’d like to go back to my existing articles and update them with interactive diagrams. I’m just not yet sure where they might be useful instead of gimmicky. I’d also like to write a tutorial about random loot drops.

Skyrim and game maps

2011-12-07T12:14:00.000-08:00

I've been playing Skyrim lately. A lot of Skyrim: over 70 hours in 3 weeks. Naturally, I had some thoughts on the maps in the game.

Read the article on my main site.

Side note: I'm not really happy with my blog format. It's designed around updates, but many of my writings are more “reference” style articles that I'll update over time. With the polygon map posts, I experimented with formatting the content twice, once for the blog and once for the site. That led to fragmented discussions, and it was also a lot of extra work for me. For some posts I experimented by having a reference-style post only on the blog, but these didn't fit well into the main site. For this post I'm experimenting with the opposite — I'm keeping the content on the main site, but using the blog only as a pointer to it.

Crafting graphs

2011-10-17T21:13:00.000-07:00

I’ve only played a few games with crafting, but the basic approach seems to be that I collect some materials and then combine them into what I want to make. In some games the recipes are in the game; in others I have to find them on a wiki. Many games have multi-step crafting, where I can use a crafted item as a material to craft another item.

In a game where I find crafting materials randomly (e.g. Dungeons of Dredmore), the question I want to answer is which of these items do I want to make with what I have, or do I want to wait?. For example, if I find a Gel in Terraria, this is what I can make, sometimes by combining Gel with something else:

In a game where I can choose to find materials (e.g. Terraria) or buy materials (e.g. World of Warcraft), the question I want to answer is what materials do I need to make what I want? For example, if I want a Hero’s Hat in Terraria, this is what I need:

Both of these are subsets of a crafting graph, which may be rather complex and difficult to show on the screen at once. This is an approximate graph for Minecraft crafting:

I either want to look forwards from the materials I currently have or I want to look backwards from the items I want to make. Games typically give me a UI that only shows a single step forwards. They can’t show the entire crafting graph because it’s typically too complex.

I’d like better ways to interact with the crafting graph:

In games with a complex crafting graph, help me explore it in the game so I don’t need to use a wiki to find the information.
In games where I’m discovering crafting recipes, help me track what I’ve learned and what I’m missing.
In games where I’m able to pick which materials to find, help me track goals like “make Hero’s Hat” that translate into subgoals like “find 9 seeds from the Jungle”.
In games where I’m unable to pick which materials to find, consider adjusting the loot drop rates to favor materials that would be useful for the goals I’ve set.

In the good old days, RPGs didn’t explicitly track the map or quests for you. Instead, you did it yourself, on paper. These days, RPGs have removed much of the mundane aspects of tracking things by automatically remembering things for you. There are nifty interfaces for maps, skill/tech trees, quests, subquests, lore, and so on. I’d like to see that sort of thinking applied to crafting.

Polygon map generation, part 3

2010-09-06T15:19:00.000-07:00

In the previous blog posts (part 1 and part 2), I described generating random polygonal maps with elevation, moisture, biomes, and rivers. For some games, those maps are sufficient. However, in other games I want to hide the polygon structure. In this blog post I'll describe how to render the polygons into a game map that doesn't look polygonal, and conclude with the demo and source code.

The full article is here. There's also a demo and source code.

Noisy Edges

Recall from earlier that there are two graphs: one for Voronoi corners (1, 2 in the diagram below) and edges (blue lines), and one for polycon centers (A, B) and Delaunay edges (red lines) between them:

I wanted to add some “noise” to the the straight lines. I tried making them move randomly, but sometimes lines would cross, and I realized I needed to constrain them so that they would never cross each other. The second thing I wanted was to make sure that the lines had as much space to wander as possible.

I realized that points A, 1, B, and 2 form a quadrilateral, and I could constrain the wanderings of the line segment to that quadrilateral:

I further divided the quadrilateral into four quadrilaterals. Two were usable for the red (Delaunay) edge and two for the blue (Voronoi) edge. As long as the lines stayed within their allocated space and met in the center, they'd never cross each other. That takes care of constraining them.

The entire map can be divided up into these quadrilateral regions, with no space left over:

That ensures that the noisy lines aren't constrained any more than necessary. (I wonder if these quadrilaterals would be useful for game mechanics.)

I can use any noisy line algorithm that fits within these constraints. I decided to subdivide the quadrilaterals recursively and stitch line segments together within the small quadrilaterals into a complete edge. The result is here:

The noisiness is tunable, and I have examples at segment size 7, segment size 4, and segment size 1. In the map demo I use segment size 1 for rivers and coastlines, 3 where biomes meet, and 10 elsewhere.

More noise

I'm generally a fan of noise in game art, and wanted to add a little bit of noise to these maps as well. In a real game map the noise might reflect vegetation or small variations in terrain. In the demo I just filled the screen with a random noise texture, and smoothed the colors between adjacent polygons:

However, with a bit more random noise, we can generate this (described in the full article):

Here's a rendering with 16,000 polygons, noisy edges, a noise texture overlay, and simple lighting:

Demo

I wrote a Flash demo to explore the generated maps:

The simplest way to explore the maps is to click Random and the various View options.

Try the demo!

In a shape number like 85882-3, 85882 chooses the overall island shape and 3 is the random number seed for the details (random points, noisy edges, rivers, lava). You can type in a shape number and press Return to generate that map. The demo also shows some unfinished features that may be useful for some games: lava, roads, and watersheds.

Source

I've placed the Actionscript source under the MIT license; it's available on github. There's an overview page describing what's in these blog posts, along with notes about the code. I don't expect that the code will be immediately useful to anyone, but it might be a useful starting point if you'd like to use these techniques for making your own game maps. The diagrams are built with 300 polygons, the demo uses 2000, and the code can go much higher, although I've not tried above 16,000.

If you find the ideas or code useful, I'd love to hear about it!

Update: [2010-09-22] I added a noisier rendering, which is described in the full article.

Polygon map generation, part 2

2010-09-05T14:29:00.000-07:00

In the previous blog post I described creating polygon island maps. Given random points, Voronoi diagrams with Lloyd relaxation produce a nice set of polygons. The polygons, their edges, and their corners can be represented as two related graphs. Given a random shape, those polygons can be marked as land, ocean, or lake. In this blog post I'll describe how to add elevation, rivers, moisture, and biomes to make the maps interesting.

The full article is here. There's also a demo and source code.

Elevation

The most realistic approach would have been to define elevation first, and then define the coastline to be where the elevation reaches sea level. Instead, I'm starting with the goal, which is a good coastline, and working backwards from there. I set elevation to be the distance from the coast. I originally tried elevations at polygon centers but setting elevations at corners worked out better. Corner-to-corner edges can serve as ridges and valleys. After calculating the elevation of corners, the polygon elevation is the average of the elevation at the corners.

Water polygons don't count towards the distance. This is both because I expect lakes to be flat instead of sloped, and because this tends to build valleys around lakes, which helps guide rivers towards lakes.

One problem with the simple definition is that some islands have too many mountains and others have too few. To fix this, I redistribute the elevations to match a desired distribution, which has more low elevation land (coastline) than high elevation land (mountains).

Elevations always increase from the coast to the mountains. That means that for any location, going downhill will eventually lead to the ocean. This diagram shows the steepest downhill direction from every corner:

By following the downhill arrows from any location, we eventually reach the ocean. This will be useful for rivers but may also be useful for calculating watersheds and other features.

I had two main goals for elevation:

Biome types: high elevations get snow, rock, tundra; medium elevations get shrubs, deserts, forests, and grassland; low elevations get rain forests, grassland, and beaches.
Rivers flow from high elevations down to the coast. Having elevations that always increase away from the coast means that there's no local minima that complicate river generation.

In addition, games may define their own use of elevation data. For example, Realm of the Mad God uses elevation to distribute monsters.

Rivers

Rivers and lakes are the two fresh water features I wanted. The most realistic approach would be to define moisture with wind, clouds, humidity, and rainfall, and then define the rivers and lakes based on where it rains. Instead, I'm starting with the goal, which is good rivers, and working backwards from there.

The island shape determines which areas are water and which are land. Lakes are water polygons that aren't oceans.

Rivers use the downhill directions shown earlier. I choose random corner locations in the mountains, and then follow a path down to the ocean. The rivers flow from corner to corner:

I tried both polygon centers and corners, but found that the corner graph made for much nicer looking rivers. Also, by keeping lakes flat, elevation tends to be lower near lakes, so rivers naturally flow into and out of lakes. Multiple rivers can share the lower portion of their path, but once they join, they never diverge, so tributary formation comes for free. It's simple and seems to work pretty well.

Moisture

Since I'm working backwards, I don't need moisture to form rivers. However, moisture would be useful for defining biomes (deserts, swamps, forests, etc.). Since rivers and lakes should form in areas with high moisture, I defined moisture based on distance from fresh water:

As with elevation, I redistribute moisture to match a desired distribution. In this case, I want roughly equal numbers of dry and wet regions. In this map generator, moisture is only used for biomes. However, games may find other uses for the moisture data. For example, Realm of the Mad God uses moisture and elevation to distribute vegetation.

Biomes

Together, elevation and moisture provide a good amount of variety to define biome types. I use elevation as a proxy for temperature. Biomes first depend on whether it's water or land:

Ocean is any water polygon connected to the map border
Lake is any water polygon not connected to the map border
- Ice lake if the lake is at high elevation (low temperature)
- Marsh if it's at low elevation
Beach is any land polygon next to an ocean

For all land polygons, I started with the Whittaker diagram and adapted it to my needs:

Elevation	Moisture
Elevation	Wet					Dry
High	Snow			Tundra	Bare rock	Scorched
Medium-high	Taiga		Shrubland		Temperate desert
Medium-low	Temperate rain forest	Temperate deciduous forest		Grassland		Temperate desert
Low	Tropical rain forest		Tropical seasonal forest		Grassland	Subtropical desert

Here's the result:

These biomes look good in the map generation demo, but each game will have its own needs. Realm of the Mad God for example ignores these biomes and uses its own (based on elevation and moisture).

In the last blog post I'll describe how I get from this biome map to maps like this: (or even this!)

Update: [2010-09-22] I replaced the last diagram on this page with what I originally wanted but didn't finish in time for the blog post. At the time of posting, I used this image instead.

Polygon map generation, part 1

2010-09-04T08:37:00.000-07:00

I wanted to generate interesting game maps that weren't constrained to be realistic, and I wanted to try some techniques I hadn't tried before. I usually make tile maps but this time I decided to make polygonal maps. Instead of 1,000,000 tiles, what could I do with 1,000 polygons? I think the distinct player-recognizable areas might be useful for gameplay: locations of towns, places to quest, territory to conquer or settle, pathfinding waypoints, difficulty zones, etc.

There were three main things I wanted: good coastlines, mountains and rivers. For the coastline, I wanted to make island/continent maps that are surrounded by ocean, so that I don't have to deal with people walking to the edge of the map. For the mountains, I started with something simple: mountains are whatever's farthest from the coastline. For the rivers, I started with something simple: draw rivers from the coast to the mountains.

The full article is here. There's also a demo and source code.

Polygons

The first step is to generate some polygons. I picked random points and generated Voronoi polygons, which are used for lots of things, including maps. Here's an example of random dots (red) and the polygons that result:

The first problem is that polygon shapes and sizes are a bit irregular. Random numbers are more “clumpy” than what people expect. What I really want is semi-random “blue noise”, not random points. I approximate that by using Lloyd relaxation, which is a fairly simple tweak to the random point locations to make them more evenly distributed. Here's the result after running Lloyd relaxation twice:

Compare it to running once or fifty times. The more iterations, the more regular the polygons get. Running it twice gives me good results but every game will vary in its needs.

[2010-09-22] The second problem with the polygons is that some edges are very short. For games where boundaries between polygons matters, having short edges is a problem. We can adjust the edge lengths by moving corners, but we lose the Voronoi properties. Since I'm using Voronoi only to generate polygons, and do not need to preserve the Voronoi properties, I move the corners to the average of the polygon centers they touch. Note: I added this code after the initial blog post, and did not update diagrams to show this step.

Map Representation

I'm representing the map as two related graphs: nodes and edges. The first graph has nodes for each polygon and edges between adjacent polygons. It represents the Delaunay triangulation, which is useful for anything involving adjacency (such as pathfinding). The second graph has nodes for each polygon corner and edges between corners. It contains the shapes of the Voronoi polygons. It's useful for anything involving the shapes (such as rendering borders).

The two graphs are related. Every triangle in the Delaunay triangulation corresponds to a polygon corner in the Voronoi diagram. Every polygon in the Voronoi diagram corresponds to a corner of a Delaunay triangle. Every edge in the Delaunay graph corresponds to an edge in the Voronoi graph. You can see this in the following diagram:

Polygon A and B are adjacent to each other, so there is a (red) edge between A and B in the adjacency graph. For them to be adjacent there must be a polygon edge between them. The (blue) polygon edge connects corners 1 and 2 in the Voronoi shape graph. Every edge in the adjacency graph corresponds to exactly one edge in the shape graph.

In the Delaunay triangulation, triangle A-B-C connects the three polygons, and can be represented by corner 2. Thus, corners in the Delaunay triangulation are polygons in the Voronoi diagram, and vice versa. Here's a larger example showing the relationship, with Voronoi polygon centers in red and corners in blue, and the Voronoi edges in white and the Delaunay triangulation in black:

This duality means that I can represent the two graphs together. Edges are the key. Each edge in a normal graph points to two nodes. Instead of representing two edges in the two graph separately, I made edges point to four nodes: two polygon centers and two corners. It turns out to be quite useful to connect the two graphs together.

With the combined representation, I can now use the Relationships Between Grid Parts sections of my article on grids. They're not grids so I'm not assigning grid coordinates, but many of the algorithms that work on grids also work here, and the algorithms that work on graphs also work here (on either of the two graphs).

Islands

The second step is to draw the coastline. I used a simple function to divide the world into land and water. There are many different ways to do this. You can even draw your own shapes, e.g., a skull island. The map generator works with any division of points, but it forces the outer layer of polygons to be ocean. Here's an example that divides the world into land and water:

A simple flood fill starting from the border of the map can determine which water areas are oceans (connected to the border) and lakes (surrounded by land):

In the next two blog posts (part 2, part 3) I'll describe how I add elevation data to build mountains and valleys, add moisture data for lakes and rivers, render the map so that it doesn't look polygonal, and conclude with the demo and source code. Together, elevation and moisture produce a good range of terrain and map features. The goal is to produce maps like this:

Update: [2010-09-22] Since the original blog post, I added a corner adjustment step to lengthen short edges. Just as Lloyd relaxation improves the polygon sizes, I needed to adjust the edge lengths. The adjustment does not preserve Voronoi properties, but I'm not using those properties so it worked out. I didn't update diagrams to reflect this change. I also improved map rendering and replaced the last diagram on this page. I originally wanted to have a rendering that didn't show the polygons at all, but couldn't get it to work in time, so at the time of the blog post I used this rendering instead. The rendering technique is described in the full article but not in the blog posts.

Map rendering: cutting corners

2010-08-20T16:11:00.000-07:00

I was drawing tile maps in Flash and found a cheap trick that improved the appearance of the maps, so I thought I'd share. Here's how I had been drawing the tile map:

In a bitmap-based graphics engine, you can smooth the edges of the tiles either by adding transition tiles (see this article or this article or this article) or by using a blending mask between adjacent tiles.

Flash, OpenGL, and DirectX are vector-based engines. The bitmap techniques still work, but there are new possibilities available. I'm drawing each square tile by filling a square polygon with a bitmap texture. The engine doesn't care that it's square; it works on any polygon. I'm taking advantage of this with what I call “vertex displacement”:

I look at the four tiles touching each vertex. If three of them are the same and the fourth is different, I move the vertex to expand the area of the three common tiles and shrink the area of the uncommon one. It's easier to see the effect with the polygon borders:

It turns out there are other fun things you can do with this trick. For example, a little bit of random noise on each vertex makes for a map that looks a little more hand drawn:

I've also used it to animate the boundary between the ocean and the beach. I added vertex displacement to my simple map generator; see the demo (Flash). Try changing the corner setting to adjust how much the corners get moved when three tiles are the same, and the random setting to adjust how much vertices get randomly moved. I have a separate demo (also Flash) to show the animated coastline.

The technique has its limitations. Terrain boundaries that don't fall on a 45° angle look wavy (see example). Some terrain types shouldn't meet in this way. And the biggest limitation is that it only applies when the terrain texture has no major features (such as trees, rocks, etc.). But it's a cheap enough trick that it's worth keeping in my toolbox.

Teleological vs. ontogenetic map generation

2010-06-13T09:06:00.000-07:00

Edit: The feedback from comments is that the names “teleological” and “ontogenetic” aren't good fits. I agree. There's an interpretation in which the terms work but there are also other ways to interpret them where it doesn't make sense. I had gotten the terms from the procedural content wiki, but in the future I'll avoid using these terms. I've changed the blog text to use “bottom up” and “top down”. Thanks for the feedback.

Long ago, I spent years working on the terrain generation for a game I worked on. I used earthquake faults, volcanoes, soil erosion, lava, river erosion, sediment deposition, water flow, weather simulation, vegetation (affected soil, which affected erosion), forest fires, floods, continental uplift, and other physical processes. This is the ~~teleological approach~~ bottom up approach to making maps.

To make good maps, I'd change parameters and run it to see if the maps looked good. I'd go back and change parameters again and again. Ideally I'd write a search/evolutionary algorithm that explored the parameter space. To do that I need to write code to determine whether a map will look to my eye, and I never did figure that out. I knew it when I saw it.

The other approach to map making is ~~ontogenetic~~ top down. Start with the structure you want to see, and make algorithms produce that directly and fill in the details. This is what I did with last year's simple map generation project. I had seen Perlin Noise, and thought, hm, that looks vaguely like a map — let's see how much work it takes to turn it into a map. Not much, it turns out!

For the past month I've been working on a new map generation project. I wanted island/continent maps with rivers, and Perlin Noise wasn't a good fit for that. I tried making random mountains come out of the ocean, and then using water flow algorithms to carve out rivers. I've been tweaking and testing, tweaking and testing, tweaking and testing, and finally realized that I'm back to using bottom up algorithms. It's incredibly addictive. It feels right: erosion, mountains, gravity, and all the other “realistic” things that form terrain.

The trouble is that I really don't need all of that. I'm working on 2D Flash games, and I don't need terrain; I need maps. It doesn't need to be completely realistic. It just has to be interesting. So I'm stepping back a bit and switching back to the top-down approach. I'm drawing some maps that I like, and then I'll find algorithms that generate maps like those, instead of modeling physical processes that produce realistic terrain. I think this will lead to better maps with less work.

Update: [2010-09-04] See my newer blog post to see the beginning of the new map generation project.

Varying game difficulty

2010-04-08T14:46:00.001-07:00

Contrast is commonly used for visuals and sometimes for music but you can also use it for game difficulty. The usual pattern in nature is slow rises and sharp falls.

The stock market tends to slowly go up and occasionally drop dramatically.
When you build a sand castle on the beach, you slowly make it larger, and then suddenly a wave destroys it all.
Forests grow slowly, and once in a while a fire will wipe out large sections of forest.
Stress slowly builds up in rock faults, and then an earthquake will suddenly release a large amount of stress.

In games we see this same pattern. Think of how many games you've seen that start off slow, build up, and then have a “boss” fight, followed by the relative calm of the next area. The difficulty or excitement might look a lot like a stock market plot.

One major difference between games and the patterns in nature is that you can't always predict the falls in nature. I've seen some games where a boss is unexpectedly followed by another boss, but usually you roughly know what's going to happen after a boss fight. In games where encounters are dynamically generated, it might be interesting for the encounters to follow a pattern like those seen in nature. More randomness with slow increases and sudden drops could make games more exciting.

Retro art: breaking the rules

2010-02-28T17:14:00.000-08:00

When you play a game with retro graphics, there are some things you expect. Pixelated graphics. Sprites. Limited color palette. At first glance, Realm of the Mad God has retro graphics like many other games:

However, Alex of Wild Shadow Studios put in several things that don't fit the usual retro graphics approach. The above screenshot shows that the world map and its pixels rotate with the player, while the trees, players, and monsters stay axis-aligned (like billboards in 3d games). Weapon projectiles move in any direction, not only the usual 4 or 8 that you might expect from a game on a tile grid.

Less apparent is the variable scale. The “pixels” aren't simply magnified by a fixed amount. Each object has its own scale, which you can see in this screenshot by comparing the trees:

Something that's easy to miss is that some effects have a shower of “pixels”. In this composite of three screenshots, you can see red “blood splatter” and some green remains of something that exploded (I think):

Also easy to miss is how the water effect breaks expectations of retro game art. The sprites themselves are pixelated, but the alignment doesn't match the map. With this, Alex produces water animation. Look closely at the sand and water boundary, and you'll see that the “pixels” don't match up:

One of the neater effects in this game is the 3d dungeon walls. The ground, tops of walls, and sides of walls are all rendered with pixel art. In this screenshot you can see one of the players is behind the wall:

I drew some examples of things that could be interesting but aren't actually in the game at this time: dissolve effects (teleportation?), shadows (to show height), shearing (to show motion), rotated body parts or weapons (for improved animation), and outlines (to improve contrast or show effects like damage or buffs):

The sprite art we got from Oryx is pixel art, but in a vector graphics engine there are lots of things you can do with the sprite art. For Realm of the Mad God, Alex played with rotation, scale, alignment, and 3d to produce some neat effects that you don't normally see in games with retro graphics.

Simple map generation

2010-01-30T19:13:00.000-08:00

My friends Alex and Rob at Wild Shadow Studios entered the TIG Assemblee competition. In the first 30 days, artists create art assets, and in the second 30 days, programmers create games with those assets. Alex and Rob decided to write an MMO in those 30 days. They asked me about generating game maps.

In the past I had generated outdoor terrain maps by using randomness, erosion, and water flow (see the Simblob Project). However there was a terrible trap in there. I spent years refining the terrain generation system, and far too little time working on combat and the game itself. I had fun, but I never finished that game.

Wary of my tendencies to work on one aspect of a game too much while neglecting everything else, I decided this time to do something simple. I started with Perlin Noise. I generated both a moisture map and an altitude map:

To ensure that some areas are dry and some areas are wet, I renormalized the moisture map to try to produce equal areas of every moisture level. I also renormalized the altitude map to produce far more flat and low lands than high altitudes, following a quadratic function. After renormalization every random map has a reasonable mix of land types.

From these I defined simple rules that assigned a vegetation. High altitudes are snowy mountaintops and low altitudes are ocean or beach. In between, the moisture determines how green or yellow the land is. Since most altitudes are not reflected in the map coloring, I added some shading so that it would be easier to see the mountains and valleys:

There were two things I wanted to add. The first was noise. I find noise to add to the visual appeal, and in this case it would also decrease the sharp boundaries between different terrain types. Compare this map to the original:

The second thing I wanted to add was wind. In many parts of the world, wind picks up moisture from the ocean and spreads it over the land. At mountains, much of this moisture is extracted from the wind and dropped as rain:

You can see this pattern in the United States, with winds out of the west dropping moisture in Oregon and California, passing over the Sierra Nevada mountains, leaving Utah and Arizona rather dry. In Australia, the winds come from the east, hit the Great Dividing Range, leaving the eastern coast wet and the interior of the continent dry. In South America, the winds come from the east but don't hit mountains until the Andes, so the rain falls over most of the continent, giving us the Amazon rainforest. I wanted the mountains in the game map to affect the moisture levels. I added a wind algorithm that spreads moisture from west to east and generated this map:

You can see that the dry areas in the northwest are now green, and the southeast, where the moisture is blocked by mountains, is dry. It seems more “realistic” but I think the players don't really notice such things.

In the demo app you can click on the minimap to see the zoomed area, change the number of wind algorithm iterations (then press Update), randomize the map seed (the Randomize button), or type in a random number seed and press Update. I find that 83980, 59695, 94400, 92697, 30628, 9146, 23896, 60489, 57078, 89680, 10377, 42612, and 29732 are seeds that produce decent maps. The demo differs a little bit from what we used in the game but the overall map shape and features are the same.

For Realm of the Mad God we exported the map and then made vegetation and monsters based on the terrain characterstics. The tree density was higher in jungles than on hills, rocks mostly were on mountains, and dead trees littered the deserts. Monsters too were terrain-specific at first, but they ended up spreading throughout the land. On top of the map we added random temple ruins and were hoping to make those areas special in some way, but ran out of time.

Looking back on this project, there were lots of things I did that don't really matter to the players. I tried to make the algorithms “scale independent” so that I could generate maps of different sizes and they'd end up with similar features, but in practice we only wanted maps of 2048x2048. The noise, which looks good in the overview map, looks awful when playing the game, so we ended up smoothing it out. I tried to make a two-step process that would generate the large scale features with one algorithm and the details with a different algorithm, and I never got that working well; I ended up just generating everything with the large scale algorithm. I had a river algorithm that carved out canyons, and I didn't get it working well enough in time for the game contest. I tried several ways to make the edges of the map into oceans (so that players would never reach the edge of the map) but none of them worked out, and players didn't seem to mind reaching the edge. The edges of the map never worked out right because bands of weirdness would form (you can see this in the demo). The simplest thing would've been to cut off the edges.

There were also lots of things I'd like to add, but probably shouldn't because I should move on to other projects. It would've been nice to create a map rating algorithm that could automatically pick out maps that look good (plenty of water, beach, mountains, variety, etc.). But for Realm of the Mad God we just looked at a bunch of maps and picked seed 72689. It was a pretty nice looking map, except the peninsula turned out to be a little frustrating for players, and we don't want the bosses to spawn on islands that players can't reach. For the expansion pack we'll probably just pick a few random seeds that look good and make maps from them. It would've been nice to automatically pick spawn points for players and monsters but those too were just placed manually. It would also be nice if there were some landmarks and regions with names so that the players could talk about where they were.

Try the game and see how different it feels to be exploring the map in the game than it does to look at it in the demo app. For example, the god monsters live on the mountains; it's much easier to see where these are on the map than to figure it out while playing the game. I think the 30 day time limit really helped keep me focused on things that would be useful for players. After the contest was over I found I was spending time on much less important things. I'm planning to stop working on the map generator for now, and only revisit it if there are specific features I need to add. The source is available under the MIT license (however the Oryx tileset is not licensed the same way so the version I put on github uses solid colors instead).

Flash 10: drawTriangles() disappointments

2009-11-08T16:50:00.000-08:00

I've been switching to Flash 10 for my game experiments. Flash 10 offers new graphics APIs, and opens up new approaches for how to deal with game objects. I wanted to compare these approaches:

(Flash 9) Use multiple Sprite objects for hierarchical layers, filters, rotation, and translation. It's convenient to have one or more Sprites per game object, and then move and rotate them without having to manage them manually. For vector drawing, I can use beginFill and lineStyle with (Flash 10) drawPath. For bitmap (textured) drawing, I can use beginBitmapFill, or there's a special Bitmap class for rectangular bitmaps.
(Flash 10) Manage my own list of objects, and then build up a vector of IGraphicsData objects, and pass that to Graphics.drawGraphicsData. This puts the burden on me to handle translation and rotation, and I don't see a great way to add filters. Here too I can use either beginFill + lineStyle or beginBitmapFill for vector or bitmap drawing.
(Flash 10) Manage my own list of objects, build up a vector of vertices and another vector of texture coordinates, and use Graphics.drawTriangles. I have to handle translation and rotation of the vertices, but Flash will handle the translation, rotation, and scaling of the textures.

Note that there's actually a lot more flexibility than just three options. There are three ways to draw polygons (lineTo, drawPath, or drawTriangles), two object management approaches (using Sprite, or managing the list manually), and whether to defer drawing using IGraphicsData. Which approach should I use for a game like my spaceship demo?

Convenience

One of the things I love about Flash is that drawing is pretty convenient, especially with Sprite objects, bitmap handling, translation/rotation, easy filters like drop shadow, and vector drawing. For example:

var s:Sprite = new Sprite();
s.beginBitmapFill(texture, null, false, true);
s.drawPath
  (Vector.<int>([1, 2, 2, 2]),
   Vector.<Number>([100, 0, 164, 0, 164, 64, 100, 64]));
s.endFill();

To rotate or translate the game objects, set the s.x, s.y, and s.rotation fields. When you need a new game object, instantiate a Sprite and insert it into the hierachy; when you want to remove one, remove the shape. Flash handles the rest.

With Flash 10, the IGraphicsData interface lets you store graphics commands in objects, and then draw with them later. You can either call commands similar to the Flash 9 API, or you can store graphics data in a more direct form. Once you've assembled all the graphics objects, you can draw them all using Graphics.drawGraphicsData.

v[0] = new GraphicsBitmapFill(texture, null, false, true);
v[1] = new GraphicsPath
   (Vector.<int>([1, 2, 2, 2]),
    Vector.<Number>([100, 0, 164, 0, 164, 64, 100, 64]));
v[2] = new GraphicsEndFill();
graphics.drawGraphicsData(v);

You can draw each of these to a separate Sprite, or you can assemble them all into one big vector and make a single call to Graphics.drawGraphicsData. The main value I think is to be able to batch them up, so I decided to make a single call, but that means I need to manage translation and rotation myself. Instead of creating new graphics data objects, you can update them every frame. Each of my game objects can keep a reference to where in the graphics data array it is represented, and then when I want to update the game object, I can change the corresponding GraphicsPath object. For rotation, I need to edit the path and also the bitmap rotation in the GraphicsBitmapFill object.

Adding and removing game objects is a little trickier. Either I can rebuild the entire vector every time, or I can build something similar to a memory allocator, so that I can reuse parts of the vector. I haven't yet decided how I'm going to handle this (my tests so far have a fixed number of game objects).

The Flash 10 Graphics.drawTriangles interface is somewhat inconvenient when working with 2D data. It requires that all polygons be decomposed into triangles (not hard to do but it's an extra step). The function takes a list of vertices, a list of indices that point into the vertex vector, and texture coordinates.

graphics.beginBitmapFill(texture, null, false, true);
graphics.drawTriangles
 (Vector.<Number>([100, 0, 164, 0, 164, 64, 100, 64]),
  Vector.<int>([0, 1, 2, 2, 3, 0]),
  Vector.<Number>([0, 0, 1, 0, 1, 1, 0, 1]));
graphics.endFill();

Here too I need to handle translation and rotation myself, by updating the vector. However I don't need to rotate the bitmaps because drawTriangles takes care of this for me. Adding and removing objects is similar to the previous case, in that I need to handle it myself.

Overall, the traditional API is most convenient, but deferring the drawPath by putting it into a GraphicsDataPath is convenient too. The drawTriangles interface is least convenient, except for not needing to rotate bitmaps.

Performance

I've found that my intuition hasn't been a great guide for understanding Flash performance. My intuition told me that approach 1 (Sprite objects) would be slower than approach 2 (global graphics data list), and approach 3 (triangles) would be fastest of all.

I wrote a test program that drew 400–1000 square objects on the screen at once and moved them around. I also put in options for rotation (because many of the objects in the spaceship demo were rotating), use bitmap or vector graphics (I like noise in art and bitmaps seem to be the way to make that), using outlines for vector graphics (I like outlines!), and animating bitmaps.

My general conclusions, for this style of game:

Vector graphics are faster than bitmap graphics (especially when rotation is involved), but that using outlines on the vector graphics slows them down, about as much as bitmaps do. Also, if the vector graphics have any additional complexity, the bitmaps end up being faster. Since I almost always want outlines or some other edge effect, bitmaps shouldn't cost me that much, and they'll give me a lot more options for adding details.
Using the separate Sprite objects is about the same speed as using a single IGraphicsData vector. Sprite objects are more convenient. However, once I want animation, the IGraphicsData approach shines: I can swap in alternative paths and bitmaps at no cost, whereas with drawing directly, I have to redraw to get animation (it's possible that I can create lots of Sprite objects and then swap them out but I haven't tried this).
For consistent frame rates, it's best to minimize allocation, and reuse some objects. The IGraphicsData objects, the vector of them, and the vectors fo vertex and index data all can be reused from frame to frame, with additional complexity to track where everything is.
With the triangle API, I can put all my textures into one big bitmap, and then access them using texture coordinates. This allows me to make a single drawTriangles call. However, using hundreds of of GraphicsBitmapFill and GraphicsDrawPath objects is suprisingly faster than using a single drawTriangles call. I was unable to make the triangle approach faster.

The performance of drawTriangles (even when I used GraphicsTrianglePath) was a disappointment. My thanks to Alex from Wild Shadow Studios for his help in understanding the APIs and performance.

Rendering

It wasn't enough for drawTriangles to be slower for this type of game. I've also had issues with the bitmap rendering. Here's a 64x64 test image drawn in several ways:

A Bitmap object.
A polygon drawn with beginBitmapFill.
A Bitmap object rotated 90 degrees clockwise.
A polygon drawn with beginBitmapFill, rotated 90 degrees.
Two triangles drawn with drawTriangles, and u/v range from 0 to 1.
Same as 5, except u/v adjusted by 1/64.
Same as 5, rotated 90 degrees.
Same as 6, rotated 90 degrees.

Note that images 1 and 2 look the same. This is as it should be. If I believe the documentation, image 5 should look the same as 1 and 2. But it doesn't.

As far as I can tell, drawTriangles is assigning a u/v coordinate of 1.0 to be pixel 62 instead of pixel 63. If you look closely, you can see the gray pixels are getting blurred (stretched). A “fix” for this is in image 6, where I set the u/v coordinate to 1.0 + 1/64, so that it picks pixel 63. With this hack, the image matches the reference image 1.

Images 3 and 4 are the same as 1 and 2, but rotated 90 degrees clockwise. Images 7 and 8 are the same as 5 and 6, rotated 90 degrees clockwise. Notice that 7 is incorrect (it should match 3), but it's incorrect in a different way than 5. Instead of losing the yellow and blue edges, it loses the green and yellow edges. The hack in image 6, when applied to 8, fails. That means it's not as obvious as pixel 62 instead of 63; there must be a weirder issue that I don't understand.

These issues with drawTriangles rendering make it hard to recommend for 2D graphics. I don't need everything to be exactly the same, but I do plan to draw 1-pixel outlines around my sprites, and drawTriangles can't preserve the outline. Even worse, as I rotate my game's objects, the outlines will appear and disappear.

The drawTriangles API also has some weird effects when using Flash's built in zoom function (right click and choose Zoom In). It also doesn't seem to be happy when using bitmap fills with repeat set to true. And it doesn't seem to handle texture scaling as well as the regular APIs (it's possible they aren't using mipmaps).

Conclusions

For both convenience and performance for games like my spaceship demo, I think I should have every game object store some IGraphicsData objects, and also store a vector of all of them. I had thought that drawTriangles might be better, but it's both slower and less convenient. It also doesn't look as good. I think I might take a look at drawTriangles for 3D perspective graphics, or if I had lots of triangle data, but for 2D or orthographic 3D, I think it's probably not the best choice for me right now.

Parallel World Simulation

2009-08-18T16:00:00.000-07:00

When playing long simulation/strategy games like SimCity, Roller Coaster Tycoon, or Civilization, I often have “what if” questions: what if I built an airport there? what if I invaded Albania? what if I switched to solar power? what if I built extra police stations?

My usual answer is to just keep wondering. However if I'm very motivated I can save the game, try something, save it again, go back to the first save game, try the other option, and then compare the results. It's rather tedious, so I don't do it much.

It might be interesting to bring the “what if” gameplay into the game itself, instead of being outside of it, as save games. Games like Chronotron and Braid allow you to go back and try something else, and even see past paths while you're playing through again. Halo 3 heatmaps aggregate information from a huge number of games. I think these ideas apply to simulation/strategy games too.

Imagine if you could “split” the timeline into two and watch parallel worlds evolve simultaneously:

If it's just a matter of running parallel worlds, I could do this by running the game twice, in two side by side windows. However if it was integrated into the game there's some potential for interesting gameplay:

The game could run two worlds all the time. Every 5 minutes the game could ask you which world is better, and then copy that world to both windows. You could run experiments but they're all limited to 5 minutes. You'd be able to learn by experimentation and then use that knowledge in the future.
The game could run one world most of the time, but then in a world-splitting event, split into two. In one world you'd be asked to destroy; in the other, to build. You'd gain bonus points for maximizing the difference between the worlds.
The game could let you play in one window and show in the other window the accumulated plays from your previous games on the same map, or perhaps from other people's games. Differences in play would be highlighted, and you'd gain points for novel play styles. In Halo, you might get a bonus for a sniper shot from a location where few people succeed making a sniper shot.
In a multiplayer setting, each player could play in her own world for a few minutes, and then the game would ask everyone to vote for their favorite world other than their own, and then that world would become the baseline for the next round of play. It might be possible to integrate this into a Facebook game that you play asynchronously with your friends.
If playing against a computer AI, it might be fair to let the computer player occasionally choose which world it prefers. The strategy would then be to set up a world that appears to give you a disadvantage without actually doing so. The Chess equivalent would be to intentionally sacrifice a rook in order to set up a winning move.

I'd love to see games explictly tackle parallel worlds, individually and in aggregate.

Storytelling with Comics

2009-07-26T15:06:00.001-07:00

In my post about drawing ninjas, I mentioned that I had an idea for blending comic books and games, and I was trying to figure out where that idea came from. Most of the ideas I have are combinations of other ideas, and occasionally they're an idea I saw a long time ago, absorbed, completely forgot about, and then had it surface again. I think this idea was sparked from a combination of things:

After reading Scott McCloud's Understanding Comics, the comparison of time and space stuck in my head. Games, videos, and audio present a sequences temporally, but books and comics present those temporal sequences by laying them out spatially. Are there games that use the spatial layout of time?
I played Passage, a game that represents time as a spatial dimension.
I played A Tale in the Desert, a massively multiplayer game in which a story unfolds from the collective actions of players. I had also played World of Warcraft, in which all the regular monsters get reset too often to make a lasting difference, but even there I saw story-worthy events (huge raids on cities, large social activities). But how are these recorded?
I got a new computer, which came with a neat little program called Comic Life. This application makes it easy to create comic strips and add thought/speech bubbles.
I played Oblivion, in which I'm playing through a story. The quest NPCs know what part of the story I'm on, and can react appropriately. But it's a big open world and I can do lots of things, including side quests for various guilds. Unfortunately the tale of what I actually did isn't anywhere; what's encoded in the game is what I'm supposed to do on the main quest.

The Sims and Spore are also storytelling games but the stories I read were outside the game itself. In strategy games, I want to see the history of battles on the map. In adventure games, I want to see the history of my progress, not only successes but also failures. Sports games aren't just about who won but about the great events during the games. In Chess I often want to see just the key moves that turned the game. Some of these games have timelines or replays or screenshots, which help with what I'm looking for, but they don't go far enough.

Comic books seem like a nice medium for recording history. At the extreme, I could imagine using the comic book format for both the history and the “live” game. The rightmost panel would be the game, and the other panels would show what you've done:

As you play, “screenshots” of the significant events turn into static panels, which scroll off to the left. At the end of each chapter/level you can go back and see the history of what you did. At the end of the game you can go back to see the entire game history, and then if you want, you would annotate it (with speech bubbles etc.) and share it with friends. You could click on those panels to show a replay of that event. The are plenty of open questions here: what are the most significant events? What screenshot do you pick to convey the event? How many events do you want to capture? Should you ask the player to replay the event and pick the best point? Does this format give people enough context to understand the story? Will anyone want to share these stories?

It was with that idea in mind that I started working on the ninja animation. However, I lost interest in that (I seem to lose interest in lots of things I start) and don't know if I will ever return to it. I still think keeping history and stories hasn't been explored enough in games, and in just about every game I play, I can think of features that would help with history/stories. Storage has become very cheap; let's record a lot more.

Noise in game art

2009-06-28T18:08:00.000-07:00

If you look at the artwork in old 2D 8-bit games, you see a lot of noise and dithering in the hand-drawn bitmap art. For an example, take a look at the grass or concrete in this Transport Tycoon screenshot:

When the gaming world moved to 3D 32-bit vector art, we lost some of that level of detail. We got lots of smooth areas. Eventually we mostly got the detail back by applying textures to the polgons. However, it often looks worse to me than the old hand-drawn art.

With my Flash experiments, I've been playing with 2D procedural vector art, and I've been trying to figure out how to make it look nicer without drawing textures by hand. The simplest thing I found has been to apply noise to the art. On the left is some terrain without noise and on the right is some with noise:

I like the noisy version much better.

The noise layer is fairly easy to apply; I use BitmapData.noise() to generate it, and then use BlendMode.ADD to add it to the original layer.

  var noiseTexture:BitmapData = new BitmapData(128, 128);
  noiseTexture.noise(Math.round(Math.random()*65536), 
                     0, 8, 7, true);
  var noise:Shape = new Shape();
  noise.graphics.beginBitmapFill(noiseTexture);
  noise.graphics.drawRect(0, 0, size, size);
  noise.graphics.endFill();
  layer.draw(noise, null, null, BlendMode.ADD);
  noiseTexture.dispose();

It's nice in that it inherits the color already there; the noise doesn't impose its own colors. However, this only works nicely on my background terrain, and it feels somewhat slow on my low-end machine.

For foreground sprites, the noise layer doesn't move when those sprites move or rotate. An alternative would be to draw the noise on top of my sprites, using Graphics.beginBitmapFill(), but that would require that I have a way to compute the outline of my procedural art, so that I can draw the noise on top as a polygon. Another alternative would be to use bitmap fills for every polygon, but that requires that I have a noise bitmap for each color. And yet another alternative is to draw every polygon twice, once for the color and once for the noise.

With Flash 10 I had hoped that the pixel shaders would allow me to apply noise to anything. I played around with them a bit. The shader receives the output coordinates in a function outCoord(), and can compute a color for that location. It can optionally include parameters (like a noise bitmap). The big problem is that the output coordinates are in screen space. This means that when the sprite moves or rotates, or if you zoom in, the noise would stay fixed relative to the screen. I tried both using shaders for fills and shaders for filters, and neither gave me what I wanted.

That's a serious problem for my use. To address this problem, I can pass in additional parameters like rotation and offset. However, I have to re-fill the shape every time I change the shader parameters. Even worse, the pixel shader is recompiled every time you fill.

So it looks like pixel shaders in Flash 10 just don't do what I want. I want a way to get the pixel's location in the sprite's coordinate system, after transforms are applied, but instead I only get the screen's coordinate system.

I think my best bet for performance is to not apply noise to vector backgrounds (applying noise to a bitmap won't impact performance). This will make me sad but smoothness matters a great deal. I should also try using tiles to see if that is any faster. For foreground objects, it's probably not too bad to draw everything twice, but I'll have to test this. It may not matter if I switch to bitmap sprites eventually; they'd let me draw a lot more details.

Switching to Flash 10

2009-06-20T16:19:00.001-07:00

On this blog you can see some of the experiments I've been playing with. In 2004, I started looking at Flash, mostly because I'd be able to share my experiments on the web. But at the time, Flash wasn't as free or accessible, and I switched to Java. Dissatisfied with Java, I took a look at Flash again, and started writing Flash 8 code. Two years ago I switched from Flash 8 to Flash 9. Flash 9's language (Actionscript 3) is much nicer than Flash 8's language (Actionscript 2). It's a modern programming language, with classes, objects, closures, recursion, XML, JSON, etc., and was tracking ECMAscript until the Javascript folk changed direction. Flash 9's graphics libraries are nicer than Flash 8's. It supports a tree of layers, each with its own rotation, scaling, alpha transparency, shadows, and other effects.

Flash 10 uses the same language as Flash 9. Its libraries have lots more features, especially in the graphics system. There's now a low-level graphics API that offers partial 3D, higher performance, and pixel shaders. I was slow to move to Flash 9 in part because the adoption of Flash 9 was slow. It looks like Flash now has auto-updating, and Flash 10 is being installed much more widely. I'm switching all my current projects to Flash 10.

For Flash 10 I'm using the free Flex 3.3 SDK and the Flex 3.3 docs (online or download). The SDK comes with a command line compiler, mxmlc, that I run with mxmlc -target-player 10 on the “main” program, and that will also compile anything else that is used by the main class. If you want a tutorial for using mxmlc, see senoular's mxmlc beginner guide.

Flex also comes with a compilation shell, fcsh, that lets you keep the compiler in memory to avoid the 2 seconds to start it up every time you want to recompile. I wrote a wrapper around this so that whenever I save something in Emacs, it automatically recompiles. That way, my development cycle is: edit, save, and reload in the browser. It's quite nice to have a fast cycle.

I haven't played much with the Flash 10 library additions, but the first thing I used was the bitmap line support. I'm using it to draw dashed lines as striped lane dividers. I plan to read about the new library features, but not try them until I find a possible use for them in my projects.

Update: [2010-03] Flex 4 is out, and includes updated documentation. Like Flex 3, it targets Flash 10 but can also be used for earlier versions of Flash.

Road representation

2009-06-08T16:00:00.000-07:00

Playing Transport Tycoon, I've recently been setting up multimodal transport, where a bus will transport passengers from the bus stop in the middle of town to the train station outside of town (because once the towns in Transport Tycoon get big, it's hard to buy up enough land to build a train station or airport). The trains then take people to the nearby airport, which is even farther away from town for noise and space reasons. It would be fun to design those airports yourself, but Transport Tycoon gives you only a few rectangular predesigned airports.

The real trouble with playing Transport Tycoon is that it makes me want to write a transportation game. I'm too busy to work on a full game right now, but I want to experiment with small pieces of games. I thought it'd be fun to design container ports that mix truck, train, and ship traffic. While trying to break that down into smaller problems, I decided to work on roads: representing them, simulating vehicle movement, and drawing them. Someone asked me: why use grids? I love grids. I think a lot about grids. Even when I used splines for roads, the endpoints were on grid edges. I recently updated my A* pages about non-grid maps, and it seems like this project would be a good fit for a non-grid representation.

As I mentioned in the last post, I'm trying things quickly and am happy to throw them away if they don't work out. I'm now on the fourth design, which uses a two-level graph structure. The first graph is used by the player to edit the world. You'll place nodes and then connect them with edges. The second graph is used by pathfinding for vehicles to move along lanes. Each connection point generates one node per lane. Intersections export edges corresponding to all the ways a truck can go straight or turn, and roads export edges for going straight and for changing lanes. The rough plan is to have three kinds of objects:

“Anchor” objects like intersections and truck stops export connection points. The anchors act like nodes in the first graph and generate edges in the second graph. For example, a 4-way intersection will export 4 connection points.
Connection points have a position, orientation, and lane configuration. They don't show up in the first graph but generate nodes in the second graph. The lane configuration is the number of lanes in each direction. For example, a connection point might specify 2 lanes going one way and 1 lane going the other way.
Roads are attached to existing connection points and can follow a spline curve. Roads do not export their own connection points, but only can attach to anchor objects. They act as edges in the first graph and generate edges in the second graph.

Unlike the previous three designs, in which I quickly ran into trouble, this design has held up for a few weeks, so that's a good sign. The subproblems are:

How do I represent connection points? I decided to keep the position, orientation, and the number of lanes going into and coming out of the anchor object. It's a very simple struct and it'll be easy to change.
How do I represent intersections? I've limited myself to 4-way straight intersections (90 degree turns). Each side can have its own in/out lane configuration.
How do I draw intersections? For roads, there's a double yellow line in the center, a dashed white line between lanes going the same direction, and a solid white line on the side. There's a stop line where vehicles come to a stop. If there are right-only and left-only turn lanes, then there will be solid white lines separating those (not implemented yet). There may be arrows drawn to show which ways a vehicle can turn (not implemented yet). The size of the intersection itself is a rectangle as small as possible (not implemented yet).

(Try the demo!)
How do I represent roads? I'd normally say cubic splines. However, since Flash supports drawing quadratic Bezier curves, it'd be nice if I could draw the roads using Flash instead of implementing my own curve rendering, so I'm going to use a spline with quadratic Beziers. There are ways to approximate cubics with quadratics but I'll see how far I get with quadratics alone. The lane configuration at the ends of the roads is determine by the anchor points, and the road handles the change in configuration. It might even be useful to have a lane configuration at each spline handle.
How do I draw roads? The roads again have the same yellow and white stripes as in intersections. However, this is where I ran into some trouble. I want the lane stripes to be parallel. This is done by taking the original curve and constructing an “offset curve”. Unfortunately, offsets of Bezier curves are not Bezier!

This could be a major problem. The more I dug into this problem, the more papers I found. It turns out that it affects various industries use Bezier curves (not only quadratic) for representing curves, and they use approximations for offset curves. I found papers mentioning circular arcs, Pythagorean hodograph curves, Hausdorff distance, and a few other things, but in the end I decided that what mattered was not whether the curve is exactly correct but whether it looks reasonable.

I drew the Bezier curve and the constructed somewhat-parallel Bezier curves, and it turns out it looks okay at low curvatures but not high curvatures:

(Try this demo.)

I think it'll be reasonable to restrict the curvature of the road, and then I can use Flash for drawing the roads and lane markers. A new problem arose: although Flash 10 allows bitmap line drawing (this is how I draw the “dashed” lane divider lines), the bitmap orientation is fixed and does not curve as the line does. I'm not yet sure how much of a problem this will be.
How do I move along roads? With Bezier curves, the movement isn't uniform; I need to adjust for arc length. Most likely I'll turn each lane path into a series of points, and then move linearly between them. If that doesn't look good then I'll try something else.

One thing I'm considering is using circular arcs instead of Bezier curves. Arcs are fairly easy to understand and have simple movement. Offset curves from circular arcs are also arcs. Also, arcs are commonly used in real roads. Arcs can be approximated with Bezier curves.
How do I handle collisions? Open Transport Tycoon's “path based signals” have vehicles reserve the path ahead of them. Grids make this easier because you can reserve grid spaces (although OTTD is a little smarter than this and can allocate half-grids). Without grids, I could either precompute all intersecting road segments and mark them all occupied whenever one of them is reserved, or I could use polygon intersection to watch for vehicles colliding. The first approach uses planning; the second is purely reactive. I think a reactive system would lead to traffic jams.

Road representation turns out to be a fun problem. As the code stabilizes, I'm pushing it out to github and I'll put demos into the wiki. It's all under the MIT license so feel free to use it for anything. My next step is to determine how the roads and anchors connect to each other. That problem may help me decide on Bezier curves vs. arcs.

Following multiple paths in RPGs

2009-05-31T16:35:00.000-07:00

Last year at GDC I was talking to the Wild Shadow Studios guys about traditional classes in fantasy RPGs (ranger, wizard, barbarian, cleric, etc.). Some of our complaints about classes in many multiplayer RPGs:

Classes come with roles such as “tank”, “healer”, “ranged”, “melee”, “crowd control”, etc. If you want to join a group that needs a tank, but your class is about melee damage, you can't join the group.
The beginning of the game is a bad time to choose a class, which impacts you for the entire game. It's too early in the game to know what style of play you might like or what kind of roles are needed/useful. By the time you can make this decision it's too late; you've already invested lots of time into the game. Either you throw all that away or you keep playing the class that's not best for you.
Every class's play style can be considered “content”, and by choosing just one the player is missing out on other styles of play. As a game developer, if you have 5 classes, and players only play one of these on average, you're spending a lot of money on “content” that most players won't see, especially if armor/weapons are written for just a few classes in mind.

In Diablo 2, you picked a class but you could also customize that class by choosing skills as you level up. For example, Barbarians could choose skills such as Taunt or Double Swing. The skills had level requirements and prerequisites; for example, Double Swing was only available if you already had Bash. The trees were divided into three specialties per class; each of these effectively acts as a sub-class, so you had 15 styles of play instead of just 5 classes. The skills available to you were fairly limited at the beginning of the game, so you're not overwhelmed, and you don't have to make your choices at the beginning. This partially addresses complaint #2.

In Guild Wars and Titan Quest, you get to pick two classes. Multiclassing has been around since the D&D days, but these two games makes two classes the default and one class an option. Multiple classes can help with complaint #1, since everyone has two roles. It also helps with complaint #3, by adding lots of variety without having to create new content around it.

In Silverfall, World of Warcraft, and Titan Quest, I can change my skills later in the game, but not my class. WoW also has hybrid classes such as druid and shaman that can perform multiple roles. This also helps slightly with complaint #1, but it's quite a hassle. (Recently, WoW introduced “dual specs”, which help quite a bit by letting you set up two sets of skills that can be swapped with one button.) Being able to change my skills later greatly increased my desire to experiment. In Diablo 2, I would pick skills based on the recommendations of others. Decisions you can't change are more likely to be conservative. But in WoW, I am much more willing to try out new things, because I can undo them.

In Dungeon Siege II, there are skill trees but no classes. You essentially define your class by choosing skills along the way, but you don't have to decide anything at the beginning of the game. Titan Quest also delays the decision-making of your first and second classes. Either approach addresses complaint #2.

Another way to address all three complaints is to have more than one character, each one trying out a different class and play style. But when playing these characters, you start over from scratch.

What I'd like is (a) delaying decisions about classes/skills, and (b) allowing trying out other choices after I'm “finished” with my current class. So here's the idea: as you progress in the game, you are given choices of specialties. If you later master multiple specialties, you can become a generalist. Here's a diagram:

After you've played for a short time, you get to choose weaponry or magic. I choose weaponry. After playing more and leveling up with weaponry skills, I am able to specialize again, and I learn melee. After learning all the melee skills, I specialize in swords. After a few more levels, I am now fully specialized by mastering swords, and there's no more for me to learn. This is the equivalent of “level 80” in WoW.

At this point, it's time to try the branches I hadn't tried. This could either be by starting over with a new character at the novice level; or it could be by restoring a previous savegame where I was still at weaponry (playing a “clone” in a scifi setting), and choosing the ranged path instead; or it could be by using my current character to go back and learn ranged attacks. I don't know which of those approaches would be best for a game. In any case, I'm now trying out other play styles, just as with current RPGs.

Where this design differs is that there's something gained in-game by learning multiple specialties. This is the lower half of the diagram. If I master both the sword and axe, that unlocks the halberd. If I master both ice and death magic, it unlocks wizardry skills. By playing and mastering all types of characters, I become a Master.

An open question is how you handle the huge number of skills once you've pursued multiple paths. Titan Quest and Guild Wars limit your classes to two, so that it's not too bad. WoW lets you have two sets of skills, and you can swap back and forth at any time. Guild Wars further gives you a fixed number of skills at any time, and you can swap these out when you're in a major city. In a scifi setting, such as a robot or spaceship based game, you could assign the skills to the robot/vehicle you're in, and then jump into a different robot/vehicle to swap skills (Wild Shadow Studios is working on a tank-based MMO that does this). Choosing sets of skills before you go into combat seems like a reasonable way to limit the complexity, and also encourage planning ahead.

This skill graph addresses complaint #2: you don't have to make permanent choices at all, and the choices you make come after you've been playing the game for a bit. It also addresses #3: there's a path for the player to experience all the “content” the developers create. It partially addresses #1, by allowing you to play different roles at different times. Novice players can follow a recommended path to specialize in just one “class”, whereas experienced players can experiment more and try out new combinations. I think it could be fun to play with such a system, but I'm not planning to write an RPG any time soon.

Throwing away code

2009-05-10T22:13:00.000-07:00

I've been trying to get better at throwing away code. I used to be a packrat. I saved every receipt, every bill, every check, every bank statement, every page of notes I took in class, every textbook, and so on. Eventually I started letting go of most of these things. Class notes were the hardest though. I had put so much effort into them; how I could throw them out?

I realized that I was making the same mistake that I make with market prices. I expect prices to reflect the cost of making the item. But in many cases, prices reflect what it's worth to the buyer. In this case, I was saving my notes because they cost a lot to produce. But they don't have much value to me in terms of looking things up. I haven't used them in over ten years, and Wikipedia and other online sources are better references. So I finally threw away my class notes.

I find that I have the same problem with code. It takes effort to write, so I feel like I should save it. But sometimes it's the wrong code or it's solving the wrong problem. There are times when the best thing to do is to throw it away.

To make it easier to throw away code, I'm trying to reduce the cost of producing it, especially when I'm less sure about how long I'll need it or whether it's the right way to go. This is not only helpful for me psychologically, but I think it's the right thing to do engineering-wise. Note that this is the opposite of the conventional wisdom — that you should put lots of effort up front into “doing things right”, because it'll pay off later.

Keeping costs down recently paid off for me.

While playing Transport Tycoon a few weeks ago, I was thinking about modular airports, and how it related to my transportation mini-game that's on indefinite hold. I'm not working on any games right now, but instead working on little bits and pieces that might end up being part of a game. Or at the very least I'll learn a lot by working on these components. One of the open questions I've had when thinking about a transportation game is how I should represent roads and vehicles (or rails and trains). I sketched some ideas on paper, and then decided on a representation of road segments:

  public class Path {
    public var id:int;
    public var next:int; // index

    // Positions are in world coordinates, not Flash coordinates
    public var beginPosition:Point;
    public var beginOrientation:Point;
    public var endPosition:Point;
    public var endOrientation:Point;

    public var length:Number;

    public function Path(id_:int) {
      id = id_;
    }
  }

I then set up some test segments and made vehicles go around on them:

I had convinced myself that inside an airport or container port, the vehicles could move around in loops, and that would be sufficient for a game. Even if I needed branching, I could change my Path class from having a single next pointer to multiple next pointers.

I was quite happy with the vehicle and road representation. I had a coordinate system that allowed vehicles to detect if someone's in front of them, and to slowly come to a stop before they collided. By using a loop I had eliminated the problem of start and end points.

A few days later I tried sketching out what the player would do. It turned out that there wasn't much. I spent some time thinking about why Transport Tycoon's station management was interesting, and my prototype was not, and realized that what's interesting is updating the station over time to deal with changes in the game world. If players spent most of their time on updates rather than initial design, the road shouldn't be a loop. It should support adding temporary routes, closing existing routes, demolishing routes, building new routes, and so on. Those operations work better with a completely different representation of roads. And that meant I should throw away my representation and associated code (rendering, etc.).

If you look at the class I wrote, it's trivial. Everything's public. There are no getters and setters, no methods, a trivial constructor, and no tests. I tried hard to follow YouArentGonnaNeedIt and DoTheSimplestThingThatCouldPossiblyWork. Throwing it away is easy, because there's so little work put into it. Having the old version saved in version control helps me feel okay with removing the code in the current version.

Although I'm throwing away code, there are some ideas I'm keeping. I learned some things, and the first approach is what got me thinking about the new approach. The process was valuable, even if the code was not. And I've started working on the next approach, which I'll try to keep as simple as the first one. I still have a packrat instinct, but I'm working on conquering it.

Transport Tycoon: modular airports

2009-05-04T00:11:00.000-07:00

I have been playing Transport Tycoon for a long time. It's my all-time favorite game. TTDPatch is a very impressive set of patches for the game, adding lots of new features that seem like they would be impossible to implement in a patch, especially by authors who don't have access to the source code. Open Transport Tycoon is an open source port/recreation of the game, and it's what I've been playing lately.

In Transport Tycoon your goal is to build a transportation empire using buses, trucks, trains, airplanes, and ships. The part I find the most fun is laying out tracks, railroad stations, and train signals. I think most of the players spend most of their time on railroads for this reason. I think I would enjoy the airplane and ship parts of the game more if I had some control over layout. All you can build right now is 6 predefined rectangular airports and 1 ship dock.

For several years on the Open Transport Tycoon forums, there's been talk of “modular” airports that would allow players to place hangars, runways, taxiways, and gates to build their own airport. However, airports are implemented with finite state machines that carefully manage multiple airplanes in holding patterns, landing, taking off, taxiing, going to hangars, and stopping at gates. Richk67 has created an impressive patch for custom non-rectangular airports. However his experience has been that the finite state machines are just too complex for players, and his patch is instead aimed at people making addons. Pikka has an alternate proposal, but take a look at the example state machine code for the simple airport. That's way too complex to make players deal with. There have been others who have argued that it should be possible to let players do this, if the GUI was good enough. However, Richk67 actually wrote some code and implemented custom airports, whereas most of the posters are just talking about proposals or ideas, so I generally believe him when he says that the finite state machines are too complex for most players.

My hope however was that there would be a completely different approach to airports that wouldn't involve the complex finite state machines. Playing with path based signals, a new feature in OpenTTD 0.7.0, has made me more optimistic. With the signals in the original Transport Tycoon, a train made a decision when it reached a junction with signals. The third party patches added new kinds of signals, including allowing complex logic in TTDPatch. Path-based signals work quite differently. Trains reserve tracks ahead of them and only proceed if they can make a reservation. Can we apply the same idea to airports? Instead of following a fixed state machine, we might be able to reserve space ahead of the airplane (landing flight space, takeoff flight space, runways, taxiways). I had only just started thinking about this problem when I came across Dimme's demo of a proposed player-created airport system using airplanes reserving space they want to use. In the demo (a Java app), you can place gate, runway, taxiway, and other tiles to build an airport, and then run a simulation to see how the airplanes use it. It's quite impressive! (Note: I couldn't get the jar file to run on the Mac so I had to recompile it myself, but it ran fine.)

A station I made with Dimme's demo

Dimme's demo shows that there's a different way to build airports that may not lead to the same complexity as the finite state machines. MarkyParky, who works with airports in real life, has good things to say about Dimme's demo, but also talks about holding patterns, which turn out to be more complicated than I imagined. I don't think that realistic holding patterns are necessary but it's something to think about. In any case, I don't think any of the discussions are going to go anywhere. Richk67's patch is the only code I saw, and as far as I can tell, the main developers have rejected his patch. Dimme demonstrated an alternate approach but there's no proposal for how to make it work within the OpenTTD code.

Dimme's demo is good. It's simple to use, it demonstrates the idea, and it lets you actually try building an airport to see how it works. After playing with it, I decided I wouldn't build an airport building demo. I think my ideas aren't different enough to make it worth it. However, his demo reminded me that I should be building more demos of ideas I want to explore. Coming up with ideas doesn't teach me as much as trying them out.

Animating stick figures

2009-04-13T19:26:00.000-07:00

For about 15 years now I've wanted to do something with stick figures. I never knew what. I just wanted to try animating them. The games I like tend to be isometric or top-down views; I generally don't like first person or side views. As a result, stick figure animation just never seemed useful enough to put into one of my games.

While reading Scott McCloud's books about comics a few years ago, I had an idea blending comic books and games, and it just happens to be a good fit for stick figure animation. I'm not sure I want to pursue it, but since I had spent so much time on the spaceship physics and editor, I thought it'd be a good break for me to take a break and take a look at stick figure animation. If it turns out to be fun I might explore the comic book idea a bit more.

The other thing that I've been wanting to explore is the ninja side of the pirates vs. ninjas theme. Sure, we have Ask a Ninja, but overall I think the pirates have gotten far too much attention. There are several pirate-themed games, like Sid Meier's Pirates, Puzzle Pirates, and Tropico 2 Pirate Cove, but not so many for ninjas. Talk Like a Pirate Day gets plenty of attention but the equivalent for ninjas just doesn't compare. Only the Somali pirate attacks are hurting the pirate image. So if I write a stick figure animation game, the protagonist will be a ninja fighting the evil pirates.

How am I going to make my 2D ninja stick figure move? There are are lots of approaches to character animation: forward kinematics, inverse kinematics, physical simulation, “ragdoll” physics, motion capture, etc. My goal was to make something simple and reasonable without putting in much artwork (motion capture or hand-drawn animation). My hope was that a 2D stick figure would take much less effort than the full 3D motion systems.

I wanted to try the simplest approach first, using basic geometry to move the legs. The hip and knee angles tell me where the ankle will end up. If I know where I want the ankle to be, I should be able to find the hip and knee angles. I tried approaching it as a gradient function, using hill-climbing to reach the solution, but it turns out this is overkill if you only have two angles. The femur and tibia length are known, and I know the distance between the hip and my desired ankle position. That means we know the three sides of the triangle, and can use the law of cosines to determine the angles. Simple. Ankles and wrists work out pretty nicely.

The next step was to make the figure take a step (pun intended, sorry!). I looked at some animator pages about the walk cycle I also read lots of papers about walking mechanics, including some about automatically “learning” how to walk. Along the way I discovered something cool: passive walking dynamics (see animation here), which treats walking as an inverted pendulum (your body over the supporting leg) and a normal pendulum (your free leg swinging freely). It seems to be a pretty good approximation of how people walk.

I decided the simplest thing would be to make the target ankle position follow a circle, as if you were on a bicycle, and then have the ground prevent your foot from going down. This actually looked reasonable, but the “liftoff” and “landing” of the foot didn't look right. To make them look better, I added transitions (see this page) that used the toe as a pivot point (for liftoff) and the heel as a pivot point (for landing). This definitely looked better, but the liftoff and landing have the ankle moving in circular arcs, and these don't smoothly transition into the overall circular motion. I improved it a bit more by making the ankle follow a spline that matched the arcs.

I was pretty happy with the walking animation, but several friends reminded me that in a ninja game, you're not going to spend much time seeing the ninja walk. The ninja will run, sneak, jump, kick, punch, throw stars, duck, swing, hide, and do flips, but walking? How boring. So once again I realized that I had been focusing on the wrong problem. The second thing was that my test app had a giant ninja, but in the game it'd look tiny, so all the little details like the flexing foot, the bounce in his step, or the liftoff and landing (which would be only a pixel high) really don't matter. [Edit 2008-05-13: changed “pirate” to “ninja”; thanks Anonymous for pointing out my error.]

I'm not sure where I want to go with this. The walking research papers were cool, but I didn't find research papers about gravity-defying ninja backflips. My gut tells me that the ninja doesn't obey the laws of physics, and thus I should stick to the geometrical approach instead of using a physics engine. Box2D looks pretty neat, and I'm sure I can use physics for other things in the game. But I need to first figure out how I'm going to implement ninja moves. Do I want to procedurally generate them somehow, or do I want to hand-pick the key frames? It'd be cool to generate them in a way that could take into account everything in the scene. For example, a jump kick should be able to jump on the box before jumping for the kick. But I suspect that's a lot more work than I want to tackle right now, and unless it's a key part of the game (if I end up writing a game), it's just not that important.

That brings up the question: what is the goal here? Am I doing this to satisfy my long-time dream of animating stick figures, or should I try to write a little game that can show off the comic book idea, or do I really want to write a game?

I don't know yet. So that leaves me at: I still want to do something with animated stick figures, and I still don't know what. But if I ever figure it out, I have now learned some things that might come in handy.

Flash 9 triangle gradients

2009-03-28T22:19:00.000-07:00

Flash 9 offers the beginGradientFill() method for drawing N-color 1D linear and radial gradients. However, I couldn't find a way to draw 3-color 2D gradients as seen in OpenGL.

I could compute the gradient myself and just set pixel values in a BitmapData, and then render those pixels to make my triangle. But that's no fun. It turns out BitmapData objects support lots of interesting operations like add, multiply, subtract, and even a limited form of lookup.

By incredible coincidence, triangles have three vertices and colors have three components. So you can use colors to store information about vertices. (Note that in the 3D DirectX/OpenGL shader world we do something similar by storing normal maps in color channels.) Here's what I came up with:

Make a triangle bitmap where the red, green, and blue components of the color correspond to the barycentric coordinates of that point in the triangle, scaled to 0–255 instead of 0–1. I only have to do this once.
Make a gradient array for the three colors I want at the vertices. The gradient array is 256 elements and it's merely the red, green, and blue values scaled down. At position i I'll store the color scaled to i/255 brightness.
Use BitmapData.paletteMap() to map the red, green, and blue components to the scaled colors in my three gradient arrays. The paletteMap() function adds the color values in those arrays to produce the final color.

This is what the triangle bitmap looks like. The red, green, and blue channels represent the barycentric coordinates:

The way this technique works is that paletteMap() calculates the output color at each pixel to be array1[red] + array2[green] + array3[blue], where the indices are the color components from the input array. In the input array, red+blue+green equals 255, and the three arrays have the color scaled up to 255. So this gives me interpolation between any three colors. For example, if red is 20, green is 80, and blue is 155, then the final color is array1[20] + array2[80] + array3[155] = (20/255*color1) + (80/255*color2) + (155/255*color3), which is the interpolation we want. Here's an example of what happens when we apply this to a triangle with green, purple, and yellow vertices:

I should also note that paletteMap() can take four arrays instead of three; the fourth is alpha. I tried building an Alpha+RGB quad bitmap for mapping, and then using four colors with that. Unfortunately I couldn't get it to work. I think paletteMap() uses alpha both for the map and for the blending (this is undocumented). Or maybe it's doing something else I don't understand. In any case I gave up on it.

The big downside of this technique is that you have to fill those arrays each time. In general, this could get expensive. If the triangles are small, it'd be faster to directly compute the interpolation per pixel (the "not fun" technique I mentioned at the top). However, in some situations you only need a few colors, and can precompute those gradient arrays. A friend of mine wants to use this for lighting calculations, and for white lights you can precompute all 255 light levels. I was hoping to use gradients to render a map (like the one in the spaceship editor demo), and if my maps contain only a few terrain types (grass, sand, etc.), I can precompute all my gradient arrays. I can use this technique to compute a color gradient bitmap, and then mix with those with my terrain textures using the standard blend operations.

Eventually I'll be using Flash 10, and that'll open up new techniques, especially with shaders. But for now, I'm using Flash 9 for my site, and I'll try to push BitmapData to do some things it probably wasn't meant to do.

Game Component: Spaceship editor, part 4

2009-03-22T00:39:00.000-07:00

Last year I decided that I just don't have the time and energy to work on a full game, and instead I should work on quick prototypes instead. I had planned to try an idea every few weeks. The space station generator was one of these; the spaceship editor was another. Spaceship physics turned out to be really interesting and I kept working on it. It's been months now. I have lots of other things I want to try, so I need to wrap this up, even if there's more I could do.

In the last post I talked about the physics. The final step was to figure out whether there were interesting tradeoffs that a player could make when designing a ship. I needed a spaceship editor.

I made a circle that could be dragged around with Flash's built-in draggable object feature, but I switched to handling the mouse events myself, so that I could add "snap to angle" and other constraints. It wasn't long after having a draggable circle that I made a circle for each thruster. And then two, one for the head and one for the tail. I also wanted the thruster to move as a whole if you dragged the base, but only the tip to move if you dragged the end. I overlaid these on a large version of the ship to make a ship editor. Now I could start answering the key question: are there interesting design choices?

After playing around with lots of configurations my answer was no. It's always better to put the forward thrusters near the wingtips. You don't lose any forward thrust, and you gain a great deal of rotational speed. The other thrusters were less of an issue, because they were used for less common motions.

To make this interesting I need some disadvantage of putting forward thrusters at the tips. One thing I considered was that thrusters at the edges of your ship are more vulnerable to damage. However, I don't actually have a game here, so that's not something I can easily test. So I turned to the other idea: thrusters require support that have mass. Putting a thruster far from the center requires more massive supports, which slow you down. I started with mass and moment of inertia calculations from physics, and then used tuning and experimentation to come up with something that felt reasonable. The main tradeoff I focused on is between rotational and forward acceleration, when both are from the same forward thrusters. If you move the thrusters near the wingtips, you get lots of rotation, but you need a lot of mass for the structural supports, and that slows your forward acceleration. This plot shows acceleration versus thruster distance from the center:

It shows that at least for the forward thrusters, there's a nice tradeoff between rotational and forward acceleration, and you can't get unlimited rotational power because the supports become too massive. There are lots of other things I could look at, but I think some tradeoffs depend on the game (for example, they may be completely different if the ship is in an atmosphere than if it were in space), and I'm not writing a game right now.

I eventually recognized that I could keep working on this for a long time, but I need to move on and explore other topics. I've mostly answered the question I set out to answer: if you let the player design the spaceship, are there interesting tradeoffs arising from the physics? I think the answer is yes, but probably not as many interesting tradeoffs as Spore's approach would allow. In addition, things weren't automatically interesting; I had to design a tradeoff and then tune the physics to make that tradeoff show up, and I had to be careful to avoid overpowered ships. That was unsatisfying. In a real game I imagine I'd have to manually design lots of tradeoffs for different game levels or areas of the world, and it'd be quite tough to test all the combinations. And even if I could do that, controlling sliders in a continuous tradeoff space seems less fun than picking from some really interesting manually designed items in Spore or Ur-Quan Masters. So yes, I was able to make what I set out to make, and it was fun to play with, but probably would be a lot less work and more fun to give people a few interesting choices.

The Demo

Of course after all that I should let you try designing your own ships and see what you think. Instructions:

Press T to change ships (you may have to click on the map first to get focus). The demo ships are: yellow square (4 thrusters), green square (like yellow but you can make it asymmetric), teal curved, purple curved (like teal but two thrusters are broken, so it can't fly properly), blue square (8 thrusters!), red triangle (goes fast but can't turn well). I mostly play with the yellow and blue ships.
Change the ship by dragging the thrusters and adjusting their size and orientation. As you do this, watch the graphs. The bar charts show what happens if you press one key at a time. The polygons represent your current flight envelope for two keys at a time. I find that I use the W+A and W+D combinations often, so I watch the chart in the lower left. The shaded ovals show the "target" that you want to mostly cover if you want a reasonable ship. The yellow and blue ships are easy to improve: just increase the power of the thrusters and they will fly well. The teal and red ships are slightly harder, and the purple ship is near hopeless. In a real game the number and power of your thrusters would be limited, and fuel efficiency and fuel tank size would be additional factors to consider.
Fly the ship around with W=forwards, S=backwards, A=rotate left, D=rotate right, Q=slide left, E=slide right, Z=reset position.

Try the demo.

The demo is written with Flash 10 in mind. It should work with Flash 9 but there may be some visual artifacts (due to bugs in Flash 9 that I didn't work around). There are some other minor bugs that I might fix someday.

I'm finished with the spaceship editor mini-project and haven't decided what the next mini-project will be. I really enjoyed working on the spaceship physics and editor, but I spent too much time on it, and hope to spend less time on the next mini-project.

Update: [2009-12-05] If you want to try a game that lets you create your own spaceships, check out Captain Forever. It's pretty neat.

Game Component: Spaceship editor, part 3

2009-01-27T22:25:00.001-08:00

I've been trying out a few ideas with quick & dirty demos to see if they're at all promising as part of a game. Two posts ago I talked about a spaceship editor, where you could place the thrusters, and the “AI” would learn how to pick thrusters that most closely matched your desired motion. In the last post I spent some time describing how I spent some time trying to figure out the characteristics of the ship, how I learned more about the problem I needed to solve, and some of the things I tried to find a “nice” solution to the math. I was really happy with the things I had worked on. However…

The real questions I wanted to answer were:

Is it actually fun to fly a ship with this physics model?
Is it actually fun to design a ship? In other words, are there interesting designs and tradeoffs?

Somewhere during the process I realized that getting the “nice” solution wasn't that important, and I had probably spent too much time on it. (Reading this article reminds me that I get distracted too easily on fun problems and I have trouble completing things.) I wasn't getting closer to answering the important questions. Instead, I was having fun learning some math that I had forgotten 15 years ago. Having fun learning math isn't bad; it's just not the main goal.

To answer the first question, I spent some time in various ships just flying around. My conclusion was yes, it's fun to fly around in a world by itself, but no, it doesn't seem like it'd be fun in an actual game, where there are other things to do. And that's when it hit me: all that time I spent thinking about the math might have been a waste of time (except that it was a lot of fun to learn some math); I should first make sure I can make the ships fun to fly.

I flew around a lot and thought about what bugged me. The main problem was that inertia was fun at first but it seemed to get annoying after a little while. For example, if I'm moving forwards with W, and then I rotate left with A, I'm still moving, but my jets are pointed at an angle. To stop moving you need to use a combination of S and Q. Even worse, since it's a keyboard instead of an analog controller, you can't hit the right mix of the two to make yourself stop.

In addition, it wasn't clear to me whether the controls should set acceleration, velocity, or target position. Acceleration was the most natural thing, and that's what I started with. But that means when you hit any key, you start out slow, then go faster and faster, until it's out of control. That might be realistic but it's not much fun. I switched it to setting velocity. But what velocity should I target? I arbitrarily chose some multiple K of the acceleration, so that after K time you'd reach that velocity.

I also needed to do more tuning. The mass, moment of inertia, friction, and rotation/translation tradeoffs are set arbitrarily. I had tried adjusting this but none of the parameters were quite right, and every time I changed the physics it got worse, and I had to tune to make it better again.

I tried to answer the second question (whether there are interesting ship tradeoffs) by creating several ships. Based on that experience, my answer is maybe. The ships I made are noticeably different but I have a clear favorite. If there's only one best ship then the ship editor's not going to be interesting. The problem is that the answer to the second question depends on what I do with the physics.

So I decided to work on the physics first.

I tried tackling inertia directly, with some ideas from a friend:

Inertia in World Coordinates gives me realistic physics for flying ships. This is what I had started with, and this is what I was unhappy with. When you're going north, and turn left, you keep flying north. The inertia keeps moving you north, even if you face west.
Inertia in Ship Coordinates gives me something that behaves more like a vehicle on wheels. When you're going north, and turn left, you start going west. The inertia keeps moving you forwards, whatever direction that may be.
No Inertia would mean that you only move when thrusters are fired. This is the most extreme change but if inertia is really a problem then it's worth a try.

I also tried treating rotation differently from x and y, because rotation seems to lead to some of the situations that make the ship less fun to control.

It was only after playing with the various options that I learned that I do really want inertia in world coordinates. Sometimes I just have to try something to help me learn something (also see this blog post). Having no inertia, or inertia in ship coordinates, just didn't feel fun to fly at all, and that's not what I would've predicted. I had the right form of inertia; something else was wrong.

After all the testing, I realized I wanted inertia but not the full effect. At low speeds, inertia is great, but at high speeds, inertia is less fun. With inertia alone it takes as long to speed up as it does to slow down again. It's okay if it takes a second or two to reach a high speed. But when I let go of the keys I want the ship to come to a stop pretty quickly. I added a force to slow the ship down. I tried three approaches:

Constant force decreases velocity V by up to K. This can be interpreted as surface friction.
Linear force decreases velocity V by K*V. I don't know what this might correspond to in physics, but in the calculations it corresponds to “reducing” inertia.
Quadratic force decreases velocity V by KVV. This can be interpreted as air resistance.

All three of them helped. After trying and tuning the three I decided that the linear force reduction was the most pleasant, but still not ideal. With quadratic, the problem I ran into (which I might have predicted if I were smarter) was that you can't increase your maximum velocity much if you add thrusters. Instead, it was largely determined by the air resistance. That would be fine if I were creating just one ship, but for the ship editor to be interesting, I need the number and power of the thrusters to actually matter! Constant friction left too much of your motion determined by inertia at higher speeds. The linear slowdown felt the best. I can't justify it if I were going for realism, but I'm going for fun, not realism.

I think flying the ship can be made fun. The next question to tackle is whether there are interesting tradeoffs in ship design.

Game Component: Spaceship editor, part 2

2009-01-11T13:10:00.000-08:00

In the last post, I described a fun problem I wanted to play with, and my initial attempt to solve it. I made several ships, figured out how their thrusters worked, and built a simple system for flying. The keys were W for forwards, S for backwards, Q for slide left, E for slide right, A for rotate left, and D for rotate right. Once I flew them around and saw that it was fun, and ship design might be interesting for the player, I wanted to understand better the characteristics of the ships. So I did something that often helps me: visualize the data.

In this diagram you can see the black dots are the possible outputs for the first test ship, viewed from three different perspectives. You can see that it's not completely random. There's a definite shape there. The variety of shapes is what makes this problem interesting. I plotted these for all of my test ships, and learned a lot. For example, look at the lower left plot (with the A–D + W–S axes). From it we can learn that the ship flies forwards quickly (W) but backwards slowly (S). It can rotate left (A) and right (D) slowly. Going forwards makes it easier to rotate quickly; going backwards makes it harder.

While flying the ship I noticed however that there was a second problem I hadn't appreciated at first. When choosing outputs that are “close” to the desired output, a difference of +3 to +4 is nowhere near as significant as a difference of 0 to +0.1. When the player wants zero movement, it's very important to keep it zero. If one key is pressed down, then there should be one non-zero in the output; if two keys are pressed then there should be two non-zeros. The most common case for the random input/output pairs is to have no zeros, but the most common case for the player is to be pressing just one key, and thus needing two zeros!

Because my random input/output approach was fun but didn't handle the one and two-keystroke cases well, I also looked a few different analytical approaches to compute the reverse mapping directly. I looked at the pseudo-inverse operation, which is like matrix inverse but works with non-square matrices. However, it didn't look like it would help me. I also looked at it as a linear programming optimization problem. That approach looked promising but the Simplex algorithm was more than I wanted to implement.

None of the mathematical approaches I saw directly matched the problem I was trying to solve. It's easy to add the constraint about zeros to a linear programming problem but not to the matrix pseudo-inverse. It might be made to work with the random input/output pairs, by adding some weights to the output components, but the outputs generated from random inputs almost never contained zeros, so I'm never going to get exactly what I want.

One of my habits that seems to work well for me is to alternate between working things out on paper and writing code. The ship thruster physics, the input/output pairs, and the matrix math I first worked on paper, then implemented it. So I went back to paper and pen for this problem. Can I increase the number of outputs that contain some zeros?

First I tried changing the way I picked random inputs, and favored 0 and 1 instead of evenly uniformly choosing any number between 0 and 1. That didn't help much (but I later had an insight related to this change, so maybe it was useful after all). I decided I needed to attack the problem directly. The idea of interpolating between output points was still in my head, and I used that here. If I picked two points on opposite sides of a zero plane, I could find some interpolation that was on the plane. I took pairs of the random input/output pairs and solved for any zeros on the line between them. This worked well! I now had a new set of points that had one zero in the output. By applying the algorithm again, I could find a set of outputs that had two zeros.

In this diagram you can see the black dots are the random outputs projected down to the three planes, and also the white dots, which are formed from finding the point in between two black dots that intersects the plane. The space covered by white dots is more limited than that for black dots. That's because there are some wild movements that can't be controlled if you try to restrict one of the outputs to zero.

I had up to 1000 random input/output pairs. Solving the equations for every zero plane and every pair that was on opposite sides of the plane meant I needed to solve a matrix equation around 750,000 times. It took a while but it was reasonable. Applying this again to get the outputs with two zeros would've been too slow. And I wanted this to be fast enough so that you could see the flight characteristics as you were editing the spaceship.

Have you ever noticed that you often find something or think of something only after you stop looking for it? I've noticed that this happens for me when solving problems. I had gotten stuck with the brute force technique and I needed something smarter, but I was getting nowhere. So I stopped working on the problem. A few days later, while playing a game, I had an insight that should have been obvious from the start.

All the random inputs are thruster settings from 0.0 to 1.0. We're taking matrix M and multiplying it by a vector T, which must be in a fairly small space. If there are N dimensions, T is an N-dimensional vector, and all its components are between 0.0 and 1.0. That means … the space of all valid thruster configurations is a unit N-dimensional hypercube.

A wise man once told me that it's sometimes easier to solve the general case than the specific case. I had been trying to solve the specific case, of a single input mapped to a single output. And then I'm using computational power to handle lots of them. The general case is to take the entire hypercube and transform it to the output, and see what comes out.

What comes out is a polyhedron in 3 dimensions.

This insight seemed like it came out of nowhere, while I was playing a game, killing orcs. But when I thought about it more, I think it wasn't out of nowhere. If I were smarter I would've figured it out from the very beginning, but some things I had thought touched on the hypercube approach. One clue was that when I picked random numbers for inputs, I found that it useful to bias towards 0.0 and 1.0. My experiments were guiding me towards choosing the vertices of the hypercube. Another clue was that in linear programming, you can think of the valid space as a convex polyhedron in some higher dimensional space. I had spent some time thinking about what the polyhedron represented in my problem but I wasn't able to make the connection. A third clue was that plotting the black and white dots made it look like there were simple polygons involved.

For N thrusters the hypercube has 2^N vertices. In this diagram you can see the hypercube vertices, multiplied by the matrix, do cover the space that the random points covered. As before, the black dots are the random sample. The colored dots are the vertices of the hypercube.

Instead of picking lots of random points, I should pick these points. And then I can take every pair of these and find the interpolation that has a zero output. And then I can take every pair of those and find the outputs with two zeros.

I worked this out on paper. Page after page of solving equations for test ship 1, following by plotting things out on graph paper, convinced me that this was quite promising.

I was really happy with myself. I had figured out a much more elegant solution that didn't involve random numbers.

I took the equations I solved on paper and wrote some code to solve them. I tried it out on several different ships. And then I ran into a problem. For one of my ships, with 8 thrusters, the algorithm still ran rather slowly. Why? Well, 2⁸ is 256. Finding the one-zero outputs involved examining 2¹⁵ pairs in 3 dimensions, or around 100,000 systems of equations to solve. It took a few seconds, but I hadn't gotten to the one-zero case yet, which is the really expensive one. For this ship I was almost as slow as the random point approach. The random points were slow but equally slow for all ships, whereas the hypercube vertices got worse every thruster you added. Ick. While starting a cube lamp on my desk, I realized that all the useful zeros should occur along edges, not as interpolations between two arbitrary points. I could reduce 2⁸ pairs X 2⁷ pairs to just 2⁸ pairs X 8. Much faster! However, that was only the one-zero outputs. I still had to run the interpolations again, to find the two-zero outputs. And even with the optimization that was around 1,000,000 systems of equations. I was sure there was another optimization involving surfaces instead of edges but I just couldn't figure out what it was.

So I took another break. I spent some time plotting what I had, to see if there were insights I could draw from the visualization. I plotted sets of points and found that many of them just aren't relevant because they're in the “interior” of the areas. All I care about is the perimeter. To compute the perimeter in two dimensions is a well-known problem: convex hull.

I thought about how to compute a convex hull, and it seemed rather simple. I wrote down my notes, then proceeded to see what the standard algorithms were. None of them seemed as simple as my algorithm, which meant my algorithm probably has a bug. But I couldn't see what it was, so I decided to let it wait a bit. A few days later, still unable to think of a flaw, I sketched out the math on paper, then implemented it. Although I had a few bugs in the code, the algorithm itself worked.

Once I had the convex hull algorithm available, my next step was to use it to simplify the one-zero outputs into a convex hull before finding the two-zero points.

In this diagram you can see the points that make up the convex hull. As before, the white dots are the interpolations between random points, to find positions on the zero plane. The colored points with black borders around them are the interpolations between hypercube vertices, fed into the convex hull algorithm. You can see that all the points I computed from the random set lie within the convex hull computed from the hypercube vertices.

In fact the two-zero points always occur between adjacent points in the convex hull, so I had gotten yet another optimization out of this change. However, I discovered that my convex hull algorithm does have a flaw. When there are collinear points it doesn't always remove all of them. The flaw remains in my code; it doesn't seem to be a big deal in practice, because my code is now “fast enough”. For each of the five test ships, generating the flight parameters takes less than a second.

Another thing that wasn't clear to me when I started was that when you press both W and Q, you want to go both left and forwards, but there's not a fixed ratio between the two. Sometimes you can get both and sometimes you have to make a tradeoff, and none of the techniques worked out of the box for that. I think this might be something to leave to the ship designer, once the flight characteristics are known. For example, in the above diagrams you could have a way to mark what you want a combination of keys to do.

It's been a fun journey. I've taken off some rust from my skills. And I learned a bit more about linear programming, the simplex algorithm, physics, and convex hulls.

However, I haven't yet written an editor. But I now have the physics and math worked out, so once I have an editor, you'll be able to see the flight characteristics of the ship you're editing. I'll post the demo and source here. It will be nice if there are interesting tradeoffs for the player. For example, if you put jets on the wingtips, you can rotate very quickly, but perhaps it adds a lot of mass to make the wings sturdy enough to take jets, and that extra mass slows you down in terms of forward acceleration. Once I have the editor I'll get a better feel for whether there are interesting tradeoffs to be made, and whether this would be useful to have in a game.

Game Component: Spaceship editor, part 1

2009-01-10T14:59:00.000-08:00

I've been playing Spore recently. It's an interesting game. One of the criticisms is that the physical characteristics of the things you do in the editor don't make a difference to gameplay. For example, having wide legs or narrow legs or four legs or six legs doesn't affect your speed. Only the +Speed items affect speed. Only in the Cell stage does placement matter. I read some of their reasoning behind this design and I agree with it. In a game where creativity is more important than realism, simplifying that aspect of the game will encourage people to be more creative in their designs. I know that if the number of legs actually mattered for gameplay, I wouldn't have made my creature hop around on one leg.

Although I think they made the right decision for Spore, I was inspired to explore the alternative: something where the way you design your creature matters a great deal. To fit in with the 2d top-down theme I've been using (see the space station miniproject), I'm using spaceships instead of creatures.

The main idea for this miniproject is that you'd design the ship, and then the “AI” would learn how to fly the ship you designed. For example, let's consider the following ship with four thrusters:

If you fire either thruster A or B, you'd end up rotating. But if you fire both at once, you would go forwards. Given a set of thrusters (location on the ship, direction they fire, and their maximum power), I can calculate the effect on the ship (acceleration and rotational acceleration). Initially I was calculating the force to be only what was transmitted along the A→O vector, but later I realized that because the ship is rigid, the entire force gets transmitted to the entire ship, and is independent of the location of the thruster. Since thruster A fires in direction (0, +2), the force on the ship is (0, -2). Rotation is slightly trickier, as we need to calculate torque, and take into account the rotational moment of inertia. For now I'm assuming the mass and moment of inertia are constants, but later I'll compute these based on the characteristics of the ship. The torque does take into account the position of the thruster, and we have to compute the cross product of the A→O vector (-2, 4) and the force vector (0, -2).

The forward mapping from thrusters to forces turns out to be a matrix multiplication. Each thruster is a column and each effect on the ship is a row. Doing this for each of the thrusters, we get the thruster matrix M mapping thrusters to force and torque:

M:	A	B	C	D
Fx	0	0	-0.5	0.5
Fy	-2	-2	0.5	0.5
Tq	10	-10	1.25	-1.25

Given a thruster configuration vector T, M∙T gives us the forces acting on the ship.

The real problem though is reversing that mapping. The player presses a key to move forwards, and I need to figure out which combination of thrusters best accelerates the ship forwards. What value of T leads to M*T being close to [ 0 1 0 ]?

The simplest approach is brute force. So I started with that first. I generated lots of random inputs and calculated their outputs. Then when I needed some particular output, I scanned them all and picked the input that most closely generated that output. Over multiple simulation cycles, any errors would be corrected by picking different input/output pairs. I could make this even more stable by iterating within a single simulation cycle, and interpolating among the results.

This approach worked reasonably well!

The ship behavior was interesting. My first test ship (the one I'm using for these examples) moved reasonably well forwards and backwards, and could rotate well, but it couldn't slide left and right quickly.

My second ship is a variant of the first. When moving forwards it can rotate well, but if you're stationary or going backwards the rotation is limited. When you fly it you'll see that if you want to rotate, you need to move forwards at the same time. Here's what it looks like:

My third ship had reasonable movement, and rather asymmetric: it could rotate and slide left at the same time, or rotate and slide right at the same time, but it was much slower if you rotated left while sliding right or vice versa. It looks a little different from the first two, but right now that makes no difference in the physics:

My fourth ship is a damaged version of the third ship, to see if having inoperable thrusters would make for interesting gameplay. Going forwards would also make you spin around in circles. It was fun to play with in the prototype but I'm not convinced it'd be fun in a game. You can see why it's unstable:

My fifth test ship could rotate very quickly but couldn't go backwards at all (at least until I fixed a bug in the physics calculations), so you'd turn around and go forwards in order to stop moving. This might be a ship you can't build until later stages of the game, when you've gained building points or parts or money. Just look at how much power it has:

At this point the prototype made me think there was something potentially fun for a game. You could design your own ship and make tradeoffs. The game “AI” would learn how to map your keys to thruster movements, and the player would then have to learn best to use the controls for navigation and combat. For example, having to turn a ship around to stop is unusual but you might design a ship that way if you could get lightning-quick rotation in return. You might design different ships for different levels. Or you might learn how to play a ship so well that you don't want to switch to something else with different characteristics.

I knew the ships were all different in their behaviors but I didn't understand what their limits were. So my next step was to try to understand the flight characteristics of the ships. That's for the next post.

Game Component: Radial Base Layout

2008-12-01T10:34:00.000-08:00

I haven't had the time and energy to work on a full game (the transportation game is on hold) but instead I'm playing with lots of little ideas, some of which turn into demos. This week's idea is to algorithmically generate layouts for space stations or space bases, so that they all look different. Originally I had a lot more variety in mind, but for the demo, I only implemented simple radial layouts:

(This is an example layout produced by the Flash demo)

I wrote some notes about the algorithm, the source code, and how to use this in a game.

Update: [2008-12-02] I forgot to mention my motivation: I was looking for something very simple that would compile to a small size and generate “programmer art”. The layout and rendering for this compiles to under 5k, and I'd guess that it could be under 3k for something more specialized. The small size and large variety makes this a reasonable thing to include in a browser-based game.

Reflexes and Brains

2008-11-09T08:03:00.000-08:00

The brain is a complex organ with complex processing. But it's slow. Early AIs were written to explore the highest level of brain functions — things like planning, logic, natural language, creativity, problem solving, mathematics. Like the higher levels of the brain, solving these problems is slow. In game AI, planning and pathfinding are examples of the higher level processing, and these are often slow.

In the body, when fast reactions are needed, we have reflexes: a fast but dumb reaction that occurs before the brain can fully process and respond to a signal. The classic example is putting a hand on a hot potato – you will pull your hand away before the brain even receives the pain signal. Many reflexes are handled by the spinal cord, before the signals reach the brain.

The body has both:

A global slow, smart system: processing in the brain
A local fast, dumb system: reflexes closer to where the input occurred

In game AI we can often do the same. An example is in games where pathfinding is slow, and has to be split up among several frames. We need to give instant feedback to the player when the unit is clicked. If pathfinding is slow, then we need something else in its place. In some games, you'll see animation and sound for the unit getting ready to move. But the reflex-inspired approach would be to have a secondary pathfinding system that's fast and dumb, and have the unit start following that path right away. The most straightforward approach would be to start moving in a straight line; another approach would be to see if any nearby units are moving to the same general area, and start following them. The slow, smart system can fix the path later. In some cases you don't need the smart system at all because the dumb path is fine. That way, you can get both instantaneous action and good paths.

In planning tasks we also have places where reflexes can be useful. For example, suppose three different squads are attacked simultaneously. Their reflex action should be to fight back. In the background a slower processing task can analyze these three positions, the size of the attacking forces, and the information gathered from scouting. It can guess what the enemy is going to do next, and order all three squads to fall back to a safer position. Fire first, then fall back, instead of waiting for the analysis before performing any action.

Lots of games already use these techniques. They're part of a general pattern: use both slow/smart and fast/dumb event handlers, so that you can react quickly and then go back and react smartly in cases where you need it.

Multiple clients for the same game

2008-11-03T08:56:00.001-08:00

When I'm interacting with my computer, there's a range of interfaces I use. On the “high” end, there are full screen specialized UIs sometimes with specialized controllers. I have a highly customized World of Warcraft interface that's tuned for the special keyboard I got for playing games. These UIs typically use your full attention, and you don't do anything else on the computer at the same time. On the “low” end, there are simple interfaces that are usually text-based and line-at-a-time. Twitter and instant messaging let me send and receive short lines of text. These UIs typically use very little attention, and sit unobtrusively on the side while you do something else.

Most games I see are on the “high” end. They have specialized interfaces that you have to learn, and you're not often multitasking. Browser based games are somewhere in the middle. They're not using up the full screen, they have simpler UIs that fit with the browser's UI, and you can have other things going on at the same time, although you'll probably ignore them if the game requires your full attention.

For some kinds of games I think it would make sense to have multiple interfaces to the same game. Outside of games, you see examples like EBay, which has a main interface (through a web browser), some “rich client” applications that you can download, and mobile phone alerts. They all access the same database. You can get more out of the rich client, but it's not something you run all the time. You do have the mobile alerts on all the time, but you can't do very much with that interface. Also look at television shows like Lost or Heroes, which have a main “rich” interface through the TV show, but also expose other aspects of the show through their web site, novels, discussion forums, comic books, and games. The Matrix series of movies had other aspects of the storyline revealed in comics, anime, and video games.

What kinds of games would benefit from multiple clients? I think it's most useful in games that have interactions with other people. In these games, things can be going on when you're not playing. A lightweight client would be useful for finding out what's going on, and perhaps inducing you to play with the full interface. You already see notification of this sort in a very simple setting: play-by-email Chess or Go. There's the game itself, and there's a lightweight communication mechanism (email) that lets you find out what's going on. But I'd like to see this in a lot more games. For example, in Halo 3, it would be nice to see if my buddies are playing online. Imagine an IM bot that showed in its status message how many buddies were online. Even better, what if you could talk to that bot to chat with your buddies in the game, and see their replies in the IM window. That way you could see what was going on, even if you're not able to play right away. And if you saw that your buddies have been playing quite a bit, you might go into the living room and boot up the XBox. Second Life, World of Warcraft, and any other game with a chat interface might benefit from having chat interoperate with an IM client.

Another kind of game I'd like to see with multiple clients is persistent world games. There are things going on in the world when you're not playing, and it'd be nice to keep track of these. For example, in my brother's game, Barren Realms Elite, you'd send attack forces out to distant worlds, and the attack would happen at some time, usually when you weren't playing. It'd be nice to have a web page or RSS feed or gadget (Mac Dashboard, Vista sidebar, etc.) that showed me the status of my attack force and the outcome of the battle. These days, MMOs are the most obvious sort of game where this would be useful. In World of Warcraft, I'd like to know that Stormwind City is under attack by 60 Horde, or that my guild just defeated the bosses of Karazhan. The state of the world could be displayed in a web page, and major attacks could be sent as IM or email or RSS alerts.

Another sort of interaction I'd like with a game is for part of the game – not just status or chat – to be accessible in a lightweight client. In EVE Online, I'd like to track the economic game – my buy and sell orders, as well as production – even when I'm not in the full game client. EBay mobile alerts likely increase people's usage of EBay; my guess is that having that lightweight client that lets you track your EVE Online business dealings would make you play EVE Online more.

Even in single player games, there are some interactions with other people. For example, suppose a new high score in Scrabulous was sent to all your Facebook pals. That'd both remind people to play Scrabulous, and it would also encourage everyone to try to beat that high score. Scrabulous is a Facebook game, but you could imagine doing the same with other games. If XBox achievements were sent to my Facebook account, it'd be more fun to get those achievements than if people saw them only when they turned on their XBox.

To summarize, I'd like to see a lot more games with multiple interfaces. Some ideas are:

Status (web, IM status) to passively see what's going on in the game, even when I'm not there.
Alerts (RSS, email, IM, SMS texting) to actively be notified of major events in the game.
Chat (IM, email) to allow communication between people playing right now and people who might not play until later.
Play (web) to allow playing some subset of the game through an interface that I can use when I'm doing other things.

For some, the lightweight game will augment the full game. Many will end up participating in only the lightweight part of the game. For others, the lightweight game will be a gateway that leads them to try and enjoy the full game. I think that's a good thing. Not everyone uses all the EBay clients; not everyone who watches Heroes reads the comic books and plays the online games; not everyone who watched The Matrix also played the game. Different people will participate in different ways. Use an interface that's simple and widely accessible to complement the interface that's rich but not there all the time. We'll have much more interesting games when lots more people participate in them.

Social structures in MMOs

2008-08-19T22:21:00.000-07:00

One of the things I’ve been wondering about in WoW is that real relationships tend to have multiple social circles, but in WoW I’m forced to have just one guild. That leads to barriers between groups, and competition between groups for members.

I‘d like to see multiple orthogonal social groups in games. Second Life for example has groups that you can join, but you can be in multiple groups at a time. Each group has its own chat channel. In addition you’re in an informal family group. You can choose your first name but there are a small number of last names available for each batch of new players. When you see a stranger with the same last name, you have a connection with them, without having joined any of the same groups. The explicit links (groups) are augmented with implicit links (last names). In games, classes and races and professions could serve a similar purpose. In practice though I rarely see people make connections based on last names or classes or professions or race. Perhaps it’s because there are too many people in each group, so you don’t feel kinship.

In an epic MMO, there are events in a shared history that could form implicit social links. For example, if a game has large, difficult battles, all the participants in a battle form an implicit social group. If a game has a way to build things, the people who built in the same town have a connection with each other. If a game has an economy, the people in the same business or frequent trading partners have a connection. When I’m in a town and pass by someone who has a shared history with me, I‘d like to see an icon or color so that I know I have a connection with this person. I might wave or give them a beneficial spell or interact in some other way. A shared chat channel or mailing list might be nice too. Instead, in WoW, I walk by strangers and don‘t care about them.

If we had many different ways for people to build social connections, and reinforce them with game features, we’d end up with a much richer social structure in games.

Titan Quest

2008-06-16T11:10:00.000-07:00

I've been playing an old RPG^* called Titan Quest. Two word summary: Diablo Clone. Diablo 2 was lots of fun, and so is Titan Quest.

One thing that struck me about the game design is that it keeps the game simple at the very beginning. You start out as a generic character, wearing generic clothing. The only thing you have to decide at the beginning is your name and gender. Very simple. So simple in fact I thought I was missing something when I created my character. World of Warcraft, which also delays a lot of complexity (talents, spells, mounts, etc.) makes you choose race, class, and appearance at the beginning of the game. Titan Quest is … spartan (pun intended).

As with many games, as you fight, you gain equipment. Not unusual. But what is unusual is that all the equipment drops are what the monster was wearing at the time! The caveat is that equipment is often damaged during the fight, and what drops can be of lower quality than what it was wearing originally (or it could be so badly damaged it's not useful). I'm not sure if the damage level depends on the battle. I'm also not sure if this game mechanic adds much. The equipment also can be enhanced with “runes” (like Diablo 2), except the mechanics are different, and IMO more fun. You have two weapon sets, which allows you to play both ranged and melee, or have an alternate weapon for monsters that can resist your primary.

What's I really liked was the class/talent system. At every level, you gain skill points, which can be used either for advancing general knowledge of an area (a class), or for unlocking a new skill, or for improving a skill. Many skills can only be learned if you have a lot of knowledge in that area. My initial instinct was to get a few skills and improve them a lot, so they'd be supremely powerful skills. However, the strategy guides I've read online suggest that you're better off learning the general knowledge first, and then learning the higher level skills. So this gave me an interesting tradeoff: if I learn the general knowledge (which also gives me better stats), it's delaying my gaining skills. I might have a harder time now, but the payoff is that I'll get the more powerful skills sooner. (Side note: with the expansion pack you can pay to unlearn skills.) I've decided on a middle path: I picked a small number of skills to focus on, and spend the rest getting general knowledge. As with many RPGs, as you add skills, you get more options of play style, not only statically (in the choice of skills) but dynamically (in choosing how to use combinations).

In addition to the general knowledge vs. skill choice, Titan Quest also delays the introduction of classes by tying it to the skill system. You don't choose a class until level 2, when you have skill points, because you have to use those skill points to choose an area of study. At level 8, after you've been playing the game for a while, you get to choose a second area of study. So now we have over 30 class+class combinations, but you don't have to pick until you've gotten a feel for the game.

I've been quite happy not having to make so many choices at the very beginning of the game. When I first start playing, I don't have enough information to make that choice. That means I'm often going to make a bad choice. Delaying a choice not only reduces complexity as I'm learning the game, but it allows me to make better choices. I think Guild Wars and Dungeon Siege II do something similar with their class system. Titan Quest and World of Warcraft also allow you to unlearn skills, which means you can explore more styles of play without starting over from scratch. When penalties for making a wrong choice are reduced or eliminated, people take more risks. They explore more. They try more things, and have more fun.

Aside from the interesting class system, I think the game is mostly like Diablo 2, down to potions and portals and “acts” and economy. This is a good thing. The graphics are incredible, looking like hand-drawn 2D art, except it's actually 3D. I've been having lots of fun. Unfortunately, I don't think I'll play through a second time. Unlike Diablo, the maps are hand-drawn and not random. This makes it more enjoyable the first time and less enjoyable on subsequent plays. Also, it requires the CD in the drive, and having to swap CDs with whatever game I get next is a huge barrier. Still, I'm going to get ~50 hours of gameplay for $20, and I think that's a pretty good deal.

^*Update: [2008-07-31] Some people pointed out that there's not much “role playing” in this “role playing game”, and delaying choices may be less appropriate if it's a true role playing game.

Shifting Game Maps

2008-06-10T16:37:00.000-07:00

Game worlds are typically quite static, with some games allowing you to change the world, and even fewer allowing changes that affect movement in significant ways. One of the ideas I wanted to explore was to have the world change significantly, but the coordinate system keep the player in a “reasonable” place even while the world was changing under him. The game idea is that you are playing the role of a tiny ship inside a giant creature. As you traverse the blood vessels and shoot the white blood cells of the immune system, the creature becomes more agitated. As its heart beats faster, ripples run down the arteries, and the entire creature may start moving about. The game becomes more difficult not because the enemies are tougher, but because the world itself is changing and becoming somewhat disorienting.

Turn on animation to see some movement of the map.

(This is a screen shot of the Flash demo.)

The article about the demo goes into more detail about the code.

Interactive A* Illustration

2008-02-18T15:10:00.000-08:00

A few months ago, I wrote that I was working on interactive illustrations for my A* pages. Has it taken that long? Well, I've actually had things working for a while now. I just haven't published it. Why? It turns out that my A* pages, which I wrote a long time ago, are really out of date. As I was trying to illustrate various concepts, I was trying to illustrate the concepts from my pages, but not all of them worked well in my Flash program. I eventually realized that some of those concepts are just unimportant in practice. I also discovered that the style I used in my diagrams only works for very simple maps. Once you add terrain into the maps, the visual style fails to convey the concepts I wanted to illustrate.

I haven't yet resolved these issues, which are taking a lot more time than writing the code itself. The algorithm and data structure code is complete, so I've uploaded them to my web site. You can see source code and the applet running on a square grid. The code is released under the MIT license; feel free to use it. I made the A* portion work on any graph, and included square, hexagonal, and triangular grids. This isn't the most efficient approach, but I wanted something flexible so that I could later use it in my article on grids. I haven't finished the hexagonal grid code yet; the only thing missing is the pixel coordinate to hex coordinate transformation. Enjoy!

Once I figure out the best way to display the important concepts for A*, I'll update my A* pages to use the interactive diagrams.

Game Design: Decreasing costs over time

2008-02-12T12:15:00.000-08:00

In World of Warcraft, the game evolves with patches released every few months. After the most recent major patch, 2.3, many areas became significantly easier, the UI became more helpful, the item rewards got better, and it took less time to “level up”. When the expansion was released, the “regular” items in the expansion areas were often better than the “elite” items in the regular areas. People who played the game in the early days sometimes comment on how easy things are now. (“When I was a kid, I had to walk uphill in the snow…”) The question is, is this a good thing?

I think in the context of a game like WoW, it is a good strategy.

Players who are more skilled or have more time to play get lots of rewards, and later players who are less skilled or play less get those same rewards. It seems unfair. This happens in the tech industry too. Last year Apple released the iPhone for $600, and later lowered the price to $400. Many people were upset by this. But price drops are common in the tech industry. The iPhone will be available for $30 in five years. Does that mean nobody should buy it now? No! What you're paying for it not just the product itself, but getting it earlier.

It's the same in World of Warcraft and other long-lived games. What was expensive before is cheaper now, except instead of the “cost” being in terms of money, it's in time and skill and effort. It doesn't even the playing field though. Just as the top items become available to more people, new top items are added that beat the old ones. There's a new iPhone out now. And Patch 2.4 will add new cool items for the top players to get. Those who had the top items before will find it easier to get the new items. Without these changes, I think the game would stagnate. Everyone will reach their peak potential, and there will be nothing more to get. You need change to keep the game exciting to existing players and new players, and Blizzard seems to be good at doing that.

Transport Tycoon

2007-11-13T11:08:00.000-08:00

I've been playing Transport Tycoon for a very long time. It's a simulation game involving transporting goods and passengers — the kind of game I love, and once wanted to write. I started playing again early this year, with OpenTTD (an open source “clone” of the game), and then got interested again once I tried their nightly builds with lots of new features.

The weird thing about Transport Tycoon is that the original game didn't keep my interest. The AI was horrible, and the game balance didn't work for me. It was too hard at the beginning of the game and then once you had enough money, the game was too easy. Instead, what I and others have done is come up with our own game goals, treating it more as a “software toy” than a game. In some games I avoid making any changes to the terrain; I work within its constraints to create “natural” looking routes. Other times I challenge myself to connect every city, or handle all resources of a certain type.

One of my favorites is designing high capacity routes and stations. I once built a custom scenario with around 100 coal mines and a single power station, and then designed routes that could handle all the coal. OpenTTD opens up new design possibilities, with changes to track building, station size and shape, and routing algorithms (see pre-signals and advanced signals).

One of the things I've been exploring recently is having multiple industries near one another. Instead of one station per coal mine, I can have lots of coal mines surrounding a high capacity station. Here's one of the stations I'm working on:

To increase the space I have available for coal mines, I built tunnels underneath some open space, where I'll place mines. The concrete tiles to the northeast of the station are considered station platforms, and extend the “reach” of the station. Using those as tendrils I can make the station area larger, and place more coal mines within its reach. On the other end of the line is a large station next to a power plant; all the trains go from here (and similar coal stations) to that power plant. You can see to the lower left that there are many tracks to handle the trains, plus extra space where I'll add more tracks after I add coal mines. The challenges here are keeping the trains running, dealing with breakdowns, handling the capacity, and making a nice layout.

Once I started playing with tunnels, I designed this station for passenger traffic:

It looks like two stations but it's actually one. I built a longer one, then removed the tracks in the middle. The station fits into a 20x20 space, but can handle 40 trains. As shown all the trains come in from the southeast, but it's also possible to use this station with 20 tracks handling northern traffic and 20 for southern traffic, either as a through station or as a terminal. The gap between the two blocks has to be 6 tiles, so there are 14 tiles left, meaning the trains can be at most 7 tiles (14 cars) long. I haven't actually used this station anywhere, but with the tunnels at the ends, it could be quite useful for tunneling underneath a major city.

There are lots more interesting layouts for stations and tracks. Take a look at this guide and this forum post for some examples. You can do a lot with the three signal types (each having their own algorithms); the routing is the most fascinating part of this game. This experimental station is an example of the weird things you can express with advanced use of pre-signals.

As OpenTTD adds more features, it opens up new possibilities for layout and routing. Coming soon are building tracks on slopes (allows more compact layouts), new road stations, trams, one-way roads, new airports, new types of cargo, new scheduling options, and new signal algorithms. It's not a game for everyone, but it's definitely a game for me.

Interactive illustrations

2007-07-30T14:13:00.000-07:00

When I'm taking a class, or reading a textbook, or reading an article, there's text that explains a topic, and sometimes illustrations that help visualize the material covered in the text. Sometimes there are diagrams that show things that are not in the text, and charts that summarize data sets that are not included in the text. When these materials are put on the web, those illustrations, diagrams, and charts remain as they were in print: they're static.

In class I often would wonder what would happen if something was changed. For example, in the programming languages course we saw a program and what would happen on the stack and heap to store data. What happens to the stack if you change the order in which you declare variables? I now know the answer to the question, but it would have been nice if I could somehow walk up to the board, change the program text, and watch the diagram of the stack update itself to reflect the change. Although in small classrooms you might be able to convince the instructor to do this, it's completely impractical in a large class to answer every student's question this way. I can't change things in textbooks or articles either.

But now we have the web. There's the possibility of interacting with the course material. Why don't we see much of this?

When teaching a subject, you have a set of points you want to illustrate. With an exploratory tool the student may or may not actually reach all the points you want to teach. When those points come up in an exam, the student might not be able to answer all the important questions.
It costs much more to develop interactive material than to develop static material. It's not only the cost of development but also in design.
Web technology for interactive sites (Javascript, Flash, Java) is still somewhat unpleasant and non-portable. The dominant technologies did not win for being elegant or fast or easy to use; they won for other reasons.

Web pages are still (mostly) written in the style of books and articles. This is understandable. Films were originally in the style of stage plays. It took experimentation to discover the things you can do by changing scenes, camera angles, etc. A century later, filmmakers are still experimenting, and developing new techniques (examples: showing simultaneous scenes, time lapse, bullet time, showing the same scene from different angles at different times). Web authors have experimented with frames, multiple windows, Java applets for computer algorithms, and writing entire web sites in Flash. I think there will be many more decades of experimentation.

For many years now I've been wanting to put interactive illustrations on my site. There are concepts like distance, movement, pathfinding (A*), scripting, grids, AI, and simulation that I'd like to illustrate. For example I used a Java applet to demonstrate a UI for building roads in simultation games. However I wasn't happy with it. It was a separate page, not integrated into an article that explained the concepts. Java was heavyweight and tricky to get working across browsers. Several authors have produced standalone A* exploration applets or applications, but they too weren't integrated into an article. It wasn't until I saw Raigan and Mare's article about collision detection that I saw what I wanted. Their article uses static illustrations to demonstrate concepts without using interactivity, but makes those illustrations interactive to allow the reader to explore on their own. This addresses my concerns about interactive tools not showing the student the important points. They use Flash to implement their illustrations. Flash is so lightweight that at first I didn't realize their illustrations were interactive. There's no “loading” screen and your browser doesn't slow to a crawl. I don't know how the cost of developing them though.

I had mentioned a few months ago that I haven't been working on my transportation game. It's true, I haven't. I've continued learning Flash but I'm working on diagrams for my site instead of a game. So far my experience has been rather positive. Flash has been easier to learn and use than I expected. The raw graphics libraries are nicer than what I had used before (PyGame, OpenGL, SVG, and Java2D); however, the user interface libraries (buttons, scrollbars, etc.) are worse than those in Java Swing. I especially like that the graphics libraries include things that are useful for illustrations: overlays, translucency, and bevel/glow/shadow effects. For example, you can draw an arrow overlay on top of the illustration without redrawing the illustration itself, or add a glow effect to the object you want the reader to pay attention to. Flash's performance is reasonable. The library reference is nice. There's a free command line compiler for people who don't want to use Adobe's fancy IDE. I'm enjoying it.

My first project has been developing a grid library, using the algorithms from my grid article to generate the illustrations on this page and this page. The most surprising thing for me has been that the 300k of images on those pages could likely be replaced by a 10k Flash file. So far my Flash program compiles to 6.5k, but it doesn't have a UI that lets you select various algorithms and heuristics, and it also doesn't allow you to draw your own obstacles on the grid.

I'm going to follow the style in Raigan and Mare's collision detection tutorial: using Flash to replace static illustrations, not to use Flash for the entire site. I'm also keeping the images as fallbacks for people who don't want or use Flash. Since most of the illustrations need to stand alone without user interaction, the fallback technique works well in this context. While working on the A* illustrations, I realized that my A* pages are nearly ten years old, and my thoughts on the subject have changed somewhat. I'd like to go back and update them to reflect my new thinking. But first, I'm going to add interactive illustrations.

Learning Flash 9

2007-06-29T07:46:00.000-07:00

This week I switched from Flash 8 to Flash 9.

Since last year I've been playing with Flash 8, using the Motion-Twin command-line compiler mtasc. I was using it to write a transportation game, and I had something running and was making progress, until Supreme Commander came out. Then I went back to playing games instead of writing them. Although I'd still like to work on that game, I've found that I also want to use Flash to build interactive demonstrations of concepts I describe on my site. For example, in my article about grids I'd like to make those diagrams interactive so that you can better see how the coordinate systems work. Diagrams are now what I'm using to learn Flash; I may go back to the game later (or maybe not).

I like mtasc. However, it only supports Flash 8 (Actionscript 2), and is not going to be updated for Flash 9 (Actionscript 3). It's a dead end. Flash 9 is not only significantly faster (almost as fast as Java), but it also has major changes to the libraries. Instead of mtasc, you can use HaXe, which is a new language similar to Actionscript/Javascript/ECMAscript. HaXe looks neat (better types, type inference), but it's a different language, not Actionscript. Part of my goal is to publish my source code so that others can use it, and it's less useful to publish code that isn't usable in Actionscript. It's also less useful to publish code that requires an expensive development environment (for example, Flex, at $500). And it's easier to learn a language when there are lots of other users, posting tips. So I've been staying with mtasc; the same code works with both mtasc and the Flash 8 development environment.

Last week Rich Collins pointed me to the free command-line Flash 9 compiler, mxmlc. Wonderful! It's free, it's Flash 9, it's command line—just what I was looking for. I spent a few days learning about Flash 9, and found this tutorial and these tips to be most helpful. My initial thoughts:

(yay) Flash 9 has much better libraries than Flash 8. The sprites (movieclips), the event handling, and the graphics commands are all nicer.
(boo) Actionscript 3 is more verbose than Actionscript 2, with types, packages, public, override, and other annotations. It's less of a scripting language and more like Java. This is bad.
(yay) Flash 9 is much faster than Flash 8, in part thanks to all those type annotations.
(boo) The mxmlc compiler is significantly slower than mtasc, in part because it's written in Java, which has a high startup time.
(boo) The mxmlc compiler is not open source.

I've been converting some of my code from Flash 8 to Flash 9, and despite the increased verbosity, I've been happy with it. If you want to use Flash 9 with free command-line compiler, start with this tutorial.

Update: [2007-07-28] [2010-03-25] You can download the Flash command-line compiler (Flex mxmlc) for free, without registration, from Adobe. Once I learned the language, the Flash 9 library reference became my #1 source of information.

Distances on a triangular grid

2007-06-19T14:07:00.001-07:00

As part of my article on grids, I'd like to provide basic algorithms for grids. I already know how to compute distances on square and hexagon grids, but I didn't know how to compute them on a triangle grid. I initially tried changing coordinate systems, inspired by Charles Fu's coordinate system. I normally use the coordinate system from my article on grids:

The first coordinate (which I will call u) is the position along the horizontal axis; the second (which I call v) is the position along the southwest/northeast diagonal. The Left/Right parity introduces some compliation; I let R be 1 and L be 0. This coordinate system is nice for storing maps in an array, but it's not as clean, because triangle grids have three axes but only two of them are expressed in the coordinates. For the horizontal axis I used 2u+R as the position; for the second axis I used 2v+R. I guessed that the position along the third axis would u-v. I drew some grids on paper, wrote down the u,v values, and then computed the three positional values. They behave properly for computing distances along the third axis, but the system falls apart when computing distances not on the three axes.

Frustrated, I decided to step back and approach this problem in a more principled manner. In Charles Fu's three-axis coordinate system, taking one step in the grid changes two of the coordinates and leaves the third alone. For a triangle grid, the dominating feature is the straight lines in three directions. I looked on the web for any articles describing distances on triangular grids, but didn't find any that satisfied me. This paper was promising but unfortunately gives an iterative algorithm and not a clean formula. However, it uses an interesting coordinate system, which is useful for computing distances. If you take one step in the grid, you will cross exactly one line. The distance between two locations will be the number of lines you have to cross. I wanted to use a coordinate system in which crossing a line changes a coordinate:

I want to map the u,v,R coordinates I normally use into the alternate coordinate system a,b,c, where exactly one of a,b,c changes when you cross a line. Here's where I decided to use algebra. In u,v,R space, the black triangle has coordinates 0,0,0; the triangle to the east of it has coordinates 0,0,1; to the west, -1,0,1; to the south, 0,-1,1. In a,b,c space, the black triangle is 0,0,0; the east triangle is 0,0,1; the west triangle is 0,-1,0; and the south triangle is -1,0,0.

I want a formula that computes a, and I expect it to be linear, so I write a = a_u*u + a_v*v + a_R*R + constant. That's four unknowns, but we know the constant will be 0, so it's really three unknowns. To get three equations, I plug in the values for the east, west, and south triangles, then solve for the coefficients. Let's see what happens:

  For each s in (a, b, c), and each triangle i:
  s_i = s_u*u + s_v*v + s_R*R

  East triangle: u,v,R = 0,0,1
  s₁ = s_u*0 + s_v*0 + s_R*1
  therefore: s_R = s₁
  
  West triangle: u,v,R = -1,0,1
  s₂ = s_u*-1 + s_v*0 + s_R*1
  therefore: s_u = s_R - s₂
  
  South triangle: u,v,R = 0,-1,1
  s₃ = s_u*0 + s_v*-1 + s_R*1
  therefore: s_v = s_R - s₃

When s is axis a, we look at a for triangles 1 (east), 2 (west), and 3 (south), so a₁ is 0, a₂ is 0, and a₃ is -1. The algebra tells us that a_R = 0, a_u = 0, and a_v = 1. That means the formula is a = v. Pretty simple. Doing the same for b and c, I get b = u and c = u + v + R.

These results are simple enough that if I played with the grid enough, I would have come up with them. However the algebraic approach works for other constraints, not only the simple ones. I also used it to create a coordinate system with 2u+v+R, u+2v+R, v-u (this is 30 degrees rotated from the one above), which may be useful for other algorithms. Algebra and calculus also come in handy for defining movements (e.g., splines), growth rates, equilibria in interacting systems, and other types of interesting behaviors in games.

What is the distance between two locations in a triangular grid? Each step involves a line crossing, and we want to count steps, so we add up the line crossings along each axis (a, b, c): distance = abs(Δu) + abs(Δv) + abs(Δ(u+v+R)). This looks just like the Manhattan distance formula, but for triangles instead of squares.

Transportation mini-game, where is it?

2007-04-14T13:57:00.000-07:00

A few months ago I posted about a transportation mini-game I had started. What happened to it?

I've been a bit distracted and haven't worked on it much. I did learn some Flash, and posted about command line tools for Flash, and then I went to the Game Developer's Conference, which made me think about what kind of game I was working on.

The first comparison that came to mind was Lemmings. In Lemmings, a stream of lemmings is coming into the world, and your goal is to give a few lemmings a job. Jobs include digging through the ground, floating through the air, building steps, turning other lemmings around, etc. The lemmings with jobs affect how the rest of the lemmings move through the world. In the transportation mini-game, there is a stream of packages coming into the warehouse and your goal is to direct them to their goal. You place objects like conveyor belts to change the flow of packages. As with lemming jobs, there are a variety of objects you can use. However you don't use the packages themselves to do this, and there's no terrain to modify.

More recently I ran across a series of “tower defense” games, in which a stream of monsters is walking by and your goal is to shoot them. Just as there are many types of lemming jobs, there are a variety of guns that you can place on towers. The most interesting of these games is Desktop TD, in which the monsters have to walk around the towers you build. This adds a layer of strategy: where you place your towers matters a great deal because if affects how the monsters walk around them, and where the monsters walk affects where your towers should be. In this YouTube video, you can see an example of how you can arrange towers into a maze to force the monsters to take a convoluted path to their goal:

Desktop TD is a lot of fun. It combines a building game with a shooting game. The monsters have a pathfinding algorithm controlling them, and you have to think about how your buildings will affect the results of that algorithm. You also have to think about different kinds of monsters, different kinds of towers, and whether to upgrade existing towers or build new ones.

Unfortunately after playing it for many, many hours it made me less interested in my transportation mini-game. It satisfied my desire to play a game with flowing objects. I'd still like to work on this game but I've been busy with other projects and don't know when I'll get back to it. Maybe someone working on a tower defense clone will incorporate aspects of the transportation mini-game instead, and then I can spend many hours playing their game. ;)

Game Developer's Conference

2007-03-05T22:42:00.000-08:00

Despite the talk of GDC 2007 becoming more and more like E3, I'm going to go to GDC this year. I'm interested in the Wii, DS, mobile games, online games, and web games, as well as graphics, music, sound effects, design, algorithms, and storytelling. I'm interested in just about everything but business/legal aspects; I expect that working on games will remain just a hobby for me.

Silverfall Demo

2007-02-07T21:28:00.000-08:00

I've been playing the demo of Silverfall (see the preview on IGN). Like Dungeon Siege and Titan Quest, Silverfall reminds me of Diablo 2, which I loved. It's a role-playing game in which your character goes on quests, fights monsters, collects treasures, upgrade items, learn new skills, etc. The graphics are great, or would be, if my computer was fast enough. Some of the more interesting things about it:

Graphics. The characters are surrounded by a black outline. See this screenshot (and others) on IGN. It reminds me of cartoons, where the outlines help separate the important characters from the backgrounds. It's more than this though. Silverfall's graphics look hand drawn, at every angle and zoom. I can't figure out how they did this.
Physics. It can take advantage of a physics accelerator card. I didn't see much that would benefit from physics though, and it's sort of annoying to have to install a physics library.
UI. The UI is really smooth compared to Dungeon Siege, although not quite as nice as Diablo 2 for reasons I'll list below. The use of the mouse and hotkeys is nice.
Factions. The nice twist on this type of game is Nature vs. Technology. When you complete or reject certain quests, you gain favor with either nature or technology (these are diametrically opposed). When your favor with either faction increases, you gain access to better items and skills. Also, in the story your faction becomes stronger, which changes the storyline and the appearance and buildings in the city. A third path is to favor neither side, accepting quests on behalf of both. This gives you more experience from quests, but you no longer have access to the special items from each faction.
Quests. A consequence of the nature vs. technology factions is that some quests will make you worse off. In most RPGs, the more quests you do, the better. But here, the quests can hurt your standing with one of the factions, and you can lose access to items, skills, and further quests. So you need to think about which quests you accept.
Skill Tree. Like Guild Wars and unlike Diablo, you can change your skills, at a cost. I think this increases the enjoyment of the game the first time through, because you can try out several approaches without starting over, but it may decrease enjoyment the next time through the game. It's a good tradeoff though, because it helps a large number of casual players at the expense of a small number of dedicated players.
Classes. There are races but no character classes. Instead, you can choose your skills to build your own style of character. There are skills for melee, ranged weapons, light magic, dark magic, faction (nature or technology), and your race (human, goblins, trolls, elves). This yields a large set of styles of play. I tried one which combined melee and dark magic, and a different style that combined light magic and nature skills.

It seems silly, but I think the black outlines and the hand-drawn look of the characters and other objects are a sign of something important. Before 3d accelerator cards, graphics were drawn by programmers and artists, and games had lots of different visual styles. With 3d cards, a certain style supported by the card is cheap, fast, and easy. All other styles are more expensive, slower, and harder to program. This has led to a far less diverse set of visual styles. Okami is a rare exception. (Side note: I'm not sure how the Silverfall developers implemented their outlines. At first I thought it'd be a single pass over the buffer to look for differences in Z values, but when you zoom in you can see the outlines are at the vector level, not the pixel level, so it's possibly a shader that looks for normals perpendicular to the screen. And I have no clue how they made everything look hand-drawn.) In old-style art, it was easy to identify objects. You could tell what was clickable, what was a button, where a person was, etc. Artists weren't looking for realism. They wanted to express concepts and emotions and ideas in game art. Newer games tend to be cluttered. Just look at how much harder it is to see all the objects in The Sims 2 vs. The Sims 1. Newer games are more realistic, but less artistic. The harder it is to see what's on the screen, the more effort the player makes in seeing things, and the less effort the player can make in deciding things. Although there are games like Quake and Halo where much of the challenge really is in seeing things, I don't think RPG and strategy games fall into that category. I like games where the challenge isn't in seeing the objects on the screen, but in deciding what to do. I hope the shaders in graphics cards enable game developers to explore more visual styles.

Since I'm on the subject of displaying information for players, there are several things that Silverfall seemed to get wrong:

Camera rotation. I spent way too much time rotating the camera in Silverfall (and Dungeon Siege). I spent no time doing this in Diablo. Does rotating the camera add to the game? No, I don't think it does. Yes, it's “cool” and people seem to expect it, but it didn't make the game better. In fact, it made it worse.
Zoom. You can zoom in to see your character close up. The character looks really nice when zoomed in. But this mode is useless when actually playing the game. For playing, you want to be zoomed out as much as possible. (In fact I'd like to zoom out even farther than Silverfall allows.) This means that all the effort to make the zoomed-in camera work (for example, distant objects, level-of-detail terrain, and expensive high-resolution texture art) is a waste. Unfortunately you need some of this to put on the box so people will buy your game. But it's a big waste.
Loading zones. When you travel from one zone to another, the game stops and loads the next zone. That's a minor annoyance. The big problem is that all your spells are cancelled. Techniques for avoiding loading screens are well-known. I don't mind if there's loading when you enter a tunnel or cave or dungeon. It's when you see arbitrary boundaries unrelated to the game that it becomes annoying.
Terrain. The demo takes place in a swampy region. The terrain is very bumpy. It looks like it was randomly generated (maybe Perlin noise?). The small problem is that the random-looking terrain adds nothing to the gameplay. It just gets in the way. The big problem is that the slopes that are walkable and the slopes that are not at not distinguished in any way, except by clicking and finding that your character doesn't move. At the very least the cursor should change color or shape to indicate that some area isn't accessible.
Map. This is actually a complaint about lots of games. If I were Indiana Jones and I had to go to 3 places to collect artifacts, I'm going to mark those 3 places on my map. Far too many games have a notion of an “active” quest, and only show that one place on the map. No! Make the map work like I would actually use it. Show me all the important places I need to keep track of. Let me add markers. Let me add notes. Let me draw lines. Don't make me keep a second map on paper because your map is so lame.
Quest Listing. There are some bugs in the Silverfall quest list, which I'm sure they'll fix before release. For example, it doesn't remember where you were the last time you brought up the list. A bigger problem though is that the quests do not keep track of who assigned the quest (and where). I found myself often re-reading quest descriptions, trying to guess who would have assigned such a quest. Some of them are on the map and some are not. Some of them trigger the rewards automatically and some do not. It's a mess. Just as with maps, the quest listing should match what I would do on paper. I would keep track of who gave the quest, where I need to go, and what the potential rewards are (especially related to faction). I would allow adding notes, assigning priorities, and sorting the list. For example, there was one quest I received that I was not ready to do. I'd like to move it to the end or otherwise mark it as “later” so that it doesn't clutter up the list of active quests I want to work on. And if the map shows all quests, it should also use different markers for active and postponed quests.
Trees. I've saved my biggest complaint for last. The graphics in Silverfall are great. I admit that. The problem is that the swampy area has lots of trees. In the default zoomed-out view, the canopy of trees blocks your view. So the game very helpfully hides the leaves. In addition, tree trunks block your view. So the game very helpfully hides the trees near your character. But tree trunks still block your attacks. So you now have a completely mysterious and maddening situation in which invisible objects block your attacks. Your attacks are blocked and you can't see why. This is truly bad. Just get rid of all the trees. They don't add anything to the game. Alternatively, since it's unlikely the developers will do that at this point, just let me walk and attack through the trees.

I really liked the demo of Silverfall. It's really promising and it could be lots of fun, except there are some little (easily fixed) things that really detract from the experience. Even with the flaws, the demo was more fun than most other games I've tried. I hope the developers read this post and fix these problems before release. (Oh, and if you're reading this: lose the cheesy box cover art.)

Transportation mini-game, rough design

2007-01-02T14:31:00.000-08:00

About a year ago I decided to stop working on Simblob, and started working on a transportation game (more about the design here and here). My progress has been rather slow, in part because I keep playing other games instead of writing one.

One of the components of the transportation game is the Warehouse. If you view your transportation network as a graph, the Warehouse is an internal node, the Supplies and Sinks are the endpoints, and the transport types (trucks, ships, trains) are the links. The Warehouse is a key component of your transportation system. Goods come in and goods go out. Sometimes goods are stored, repackaged, relabeled, inspected, and assembled. In the network, Warehouses can be used as:

Buffers. Goods come in, a stored for a time, and then go out. The time the goods are supplied is earlier than the time they are needed. For example, it may take several months to produce the toys that will be bought in the Christmas shopping season; those toys need to be stored somewhere until shoppers are ready to buy them.
Switches. Goods come in from several sources and go out to several sources. For example, a grocery store chain may have supplies coming in from farms, ranches, orchards, etc., and may have those same goods go out to several neighborhood stores.
Caches. Goods aren't needed all the time, and their demand is unpredictable, but when the demand is there, the customers want the goods right away. The solution is to keep some near the customers, so that when they need some, they can get it quickly.
Transformer. Goods arrive in one condition but leave in a better condition. For example, a Warehouse may add tracking, labeling, and pricing information to the goods before sending them on to stores.
Multiplexing. Goods arrive in large shipments from suppliers, but each store needs a small amount of each good. The Warehouse can repackage the goods into smaller units. For example, an electronics retailer may receive a truck full of VCRs, a truck full of TVs, and a truck full of speakers, and the Warehouse can reshuffle these into three trucks, each with VCRs, TVs, and speakers. That way only one truck has to be sent to each retail store.

Warehouses are an interesting enough part of this game that I decided to try making a mini-game out of them.

In the mini-game, the goals (switching, multiplexing, etc.) are given to you, and your job is to design the warehouse to meet those goals. Goods come in from the left and exit on the right. There are multiple types of goods, each represented by a color (or shape). Your job is to get the goods from the left to the right, while achieving your goals.

The warehouse is laid out on a grid. The basic component is a conveyor belt, which takes up 1 grid space. The conveyor belt pieces are linked into a chain that defines the flow of goods through the warehouse. What makes the game interesting (I hope) is the special pieces you can add to the conveyor belt. A color filter only allows a certain color to pass. With it you can separate a mixed flow into separate products. Similarly, a shape filter only allows a certain shape to pass (I may end up combining shape and color filters into one). A counter filter has a counter, and only allows an object to pass when the counter reaches a particular value. For example, a 3-counter filter will allow every third object to pass. These filters are used to separate a stream of objects into smaller streams. Note that a 1-counter is the same as a regular conveyor belt; it filters nothing. A mixer mixes objects from multiple streams, in some proportion. For example, a mixer can be set to take 1 green circle and 2 purple triangles, and the resulting stream will have twice as many purple triangles as green circles. A packer takes multiple objects and packs them into a single object of a different type; an unpacker takes a single object and unpacks it into multiple objects. A carousel stores objects, up to its capacity, until the output stream(s) have space for unloading objects. It can be used to even out a highly variable flow. There are more objects I can imagine: shelves, aisles, employees, forklifts, labelers, inventory trackers, etc.

The game involves a series of levels of increasing difficulty. Each level has a grid, some supplies, some demands, some parts to use to construct the conveyor belt network, and some goals to meet. The grid may have objects on it already, which cannot be moved.

At each time step, all goods (objects) move one space, according to the rules of flow:

The conveyor belt defines the directions the object can move.
An object cannot move in the direction of an incompatible filter.
An object cannot move to a spot that has an object, unless that object is about to move.
Of all directions available to move, the object chooses one at random.
If a box cannot move, it sits still. If it sits still too long, it breaks.

If you think about these rules hard enough, you'll see that they may be difficult to implement. In particular, rule #3 says that an object can move if another object can move. And that object too may be subject to this rule, leading to an entire chain of dependencies that have to be solved. I have an algorithm partially designed but I'm not yet convinced my algorithm will work; if it does not, I'll revise the rules.

The puzzles I'm less sure about, but here's what I've been thinking about:

Slow packers. Split the incoming supplies into several streams so that you can have several packers handling them, then coming the streams into one.
Irregular supplies. Demand is steady. Build a large buffer so that you can handle supplies being late.
Multiplexing. As described in the electronics retailer example, suppliers send large shipments of a single product type. Build buffers so that you'll have enough of each product type. Unpack the large supplies into small ones, mix the goods together, pack them into shipments that get sent to retailers.
Bad supply. Some of the incoming goods are faulty. The supplier will lower quality as much as he can get away with. It's too expensive to check everything, but if you check nothing, the quality will keep going down. Check some of the goods to keep quality high enough to satisfy customers.

Time, quantity, quality, costs, and profit can all be part of the goals. For example, incoming goods might cost $4/box, and outgoing goods might bring in $5/box. Each box you send through the system gives you $1 in profit. If a box breaks (due to sitting on the conveyor belt for too long), you lose the $4. You might be willing to have a less reliable system to keep costs down, or you may want to make it more reliable to minimize losses.

At this point the design is only on paper. I plan to create a prototype soon to try to judge how fun or interesting the game might be.

Choosing algorithms

2006-12-31T16:17:00.000-08:00

Game developers can't always find their algorithms in an algorithms textbook. Academic algorithms tend to be general purpose and often aren't the best choice for games. For example, compare textbook image scaling algorithms to hq4x. Hq4x is very impressive! How could the textbooks have missed it? It's because it's not general purpose. It is designed to work on hand-drawn low-color sprite graphics in games, whereas the textbook algorithms work on all sorts of images. Another example is path-finding algorithms. Dijkstra's algorithm is a general-purpose algorithm; A* came out of AI research (which is slightly closer to game programming) and is a little more specialized. But there are plenty of techniques used in games that aren't found in the textbooks. They take advantage of game-specific knowledge: the structure of maps, the characteristics of moving units, etc.

The general purpose algorithms are a good place to start but don't limit yourself to them. There might be a specialized algorithm that works better for your problem, or it may be worth the effort to design your own algorithm.

Water in strategy games

2006-12-25T23:15:00.000-08:00

In just about every city-building strategy game out there, water is static. It doesn't flow; it doesn't affect much; it doesn't change with seasons; and you can't change it. In 1994, I started the Simblob project to experiment with water flow in games, among other things. You could build canals and dams and dikes, divert waterways, and flood the opponent's cities. Well, you would've been able to if I had ever gotten around to implementing the opponent. The problem was that playing with water was way too much fun! I implemented heavy rains, droughts, floods, sedimentation, and erosion. Playing the game was lots of fun too, even though there was very little “game” actually implemented. In the end all I had done was work on graphics and water simulation, and I decided to stop working on it and start something else.

I still think water simulation has enormous potential for a strategy game. Imagine diverting your opponent's main source of water, so his crops fail and his people revolt. Or an enemy operative damaging your main dam, and you scrambling to repair it before it breaks, destroying your cities. Water is incredibly important in real cities, and it should be important in building-based strategy games.

Battle for Atlantis is a strategy game coming out in 2007 that has water simulation. Here's a quote from their web site:

For the first time in the history of RTS, a full physical model of water space will be created. The water has stopped being a “dead area” – a non-interactive flat mirror good only ship sailing. Real waves and tsunamis, flood and destruction of the landscape by water, river flows and waterfalls, splendid underwater effects – all this gives an enormous scope of creation and makes the game world of Atlantis as real as never before.

It sounds promising! 3dgamers has some screenshots. I just hope the water simulation is used more for gameplay than for graphical effects.

Learning Flash 8

2006-12-24T11:01:00.000-08:00

Back in 2004, I attempted to learn Flash programming, but failed to find free tools, and ended up writing Java applets instead. I was unhappy with Java for a number of reasons, but the main one was that Java applets are clunky on web pages compared to Flash objects, and as a result more people have Flash than Java. A few months ago Troy Gilbert pointed me at OSFlash.org, which has a list of open source Flash development tools (thanks Troy!). I eventually found the free and fast Motion-Twin ActionScript compiler (mtasc), but had a lot of trouble using it. The tutorials I found on the web for Flash development assume you're using the Macromedia development environment, which I'm not, so they weren't much help. I finally figured out what I was doing wrong.

I'm used to a certain development model: you write a program, (optionally) compile it, then run it. This might be considered “old school” by people writing Windows and Mac apps. When writing Windows and Mac apps, you put the source code with various resources (icons, graphics, music, dialog boxes, etc.) into a “project”, which gets compiled into an executable. In the “old” style of development (used for C++, Java, Python, Perl, Basic, Ruby, etc.), your program reads in resources after you run it. That's how I've been writing my games. Flash seems to follow the “new” style of development, in which lots of resources, not only source code, get combined into one package.

The open source mtasc compiler only compiles Flash (ActionScript) source code. It does not handle the resources that have to be assembled into a compiled Flash file (SWF). The mtasc tool will compile your source code and update a SWF file with the compiled code, but you can't use mtasc to create SWF files; they have to exist already. For that, you normally use the (commercial) Flash development environment from Macromedia. If you want to fully work in an open source world, you need another way to assemble resources. The swfmill tool can do this: it converts an XML file listing resources into a SWF file. With swfmill my toolset is complete.

The other thing that's confusing (for me) about Flash development is that it seems to be designed around movies, and every Flash program has a “frame rate”, even if it's not a movie. For now I'm ignoring this and just setting a low frame rate.

The summary of what I've learned so far about open source Flash development:

Create an XML file that describes the resources you need. I'm using the example XML file in Mark Winterhalder's well-written tutorial on the swfmill site:
```
<?xml version="1.0" encoding="iso-8859-1" ?>

<movie width="320" height="240" framerate="12">
  <background color="#ffffff"/>
  <frame/>
</movie>
```
Compile the XML file into an SWF file:
```
swfmill simple example.xml example.swf
```

Create an ActionScript file with your script. I'm using an example I found on the mtasc site:

class prototypes {
    static var app : prototypes;

    function prototypes() {
        // creates a 'tf' TextField size 320,200 at pos 0,0
        _root.createTextField("tf",0,0,0,320,200);
        // write some text into it
        _root.tf.text = "Hello world !";
    }

    static function main(mc) {
        app = new prototypes();
    }
}

Compile the ActionScript into your existing SWF file, using the -main flag to have it automatically call the main() function:
```
mtasc example.as -swf example.swf -main
```

Embed the SWF into a web page using the <embed> tag, as described on the haXe site:

<html>
<body bgcolor="#cccccc">
<object classid="clsid:d27cdb6e-ae6d-11cf-96b8-444553540000"
  width="320" height="200" id="test">
<param name="movie" value="example.swf" />
<embed src="example.swf" width="320" height="200" 
  name="test" type="application/x-shockwave-flash"
  pluginspage="http://www.macromedia.com/go/getflashplayer"
/>
</object>
</body>
</html>

See the results in a browser. Hooray!

For me, getting started is the hardest step. Once I have something running, development becomes easier. Now that I have a Flash program running, my next steps are to set up my development environment, then learn about the Flash libraries. I've been wanting to learn Flash programming for a long time, but I kept getting stuck. I'm quite glad I finally put the pieces together, and I hope the above description helps others get started.

Software pricing

2006-12-17T22:35:00.001-08:00

(Warning: this post doesn't have a point; it's just me thinking aloud.)

Most products have some fixed costs and some marginal costs of production. The fixed cost would be the factory; the marginal cost would be the labor, materials, transportation, packaging, marketing, etc. The price of the product usually starts out high, and competition brings it down over time to be close to the marginal cost (at least according to economic theory).

Creative products like music, novels, and movies typically have high fixed costs and low marginal costs. As technology has improved, the marginal cost of music, novels, and movies has gone down close to zero, and we now have a great deal of piracy. Software is similar to music, novels, and music, except that the marginal cost has been close to zero for a very long time, and the software industry has had to deal with the problem of piracy for longer. Economic theory suggests with good competition, the price of these products should eventually go down close to the marginal cost. For all of these products, the sellers have tied the product you really want (for example, a song) to something physical (a CD), and the physical object has a non-zero marginal cost. However, with electronic distribution, people want the music without paying for the CD, the movie without a DVD, a novel without a book, and software without the installation CDs and manuals. The marginal cost of distribution is close to zero, so in theory, the price should eventually get to zero.

The open source community sometimes argues that the price of software should be zero (to match the marginal cost), and that developers can earn money selling services and support. There's a major problem with this: the incentives are completely messed up. If a developer makes more money when more support is needed, there's an incentive to make the product require more support. Products will end up harder to use and contain less documentation. There's also no strong incentive to offer new features for free, because you're not getting paid for new versions of the software.

With MMORPGs we're seeing a lot of experimentation with software pricing. This is possible because the software is virtually useless without connecting to the service. World of Warcraft charges for the software plus for the service. They crack down on people who want to offer their own service (alternate free servers) because they make most of their money from the service they offer, and don't want competition. World of Warcraft also charges for expansions (which are rare). With Guild Wars the software is free (you can download it from their site for free), but access to different services (areas of the world) costs a fixed fee. Those services do not carry a monthly fee. With ArchLord the software costs money but there's no monthly fee. Second Life (which isn't technically a game) makes money both by renting areas of the virtual world and by selling virtual currency, which you can use to buy in-game goods and services. Games can also make money by selling in-game items, upgrades, status, etc. MMORPGs can tie the game to the service, and then charge for the service. However they are not making their software open source, because they do not want competitors to create compatible services.

Most games however do not have the option of charging for services, and it is difficult to charge for support in a consumer-level product (consumers get angry and feel that they deserve free support). So game developers are stuck with piracy, just like makers of music and movies. We want to recover the high fixed cost of developing the product, so we charge for the software, even though the marginal cost is close to zero. Consumers are more willing to buy software that comes in a physical package, so we include a box, installation CD, a manual, etc., all of which reduces sales and profits. Alas.

There is one more thing we might want to explore. Music, games, movies, etc., are all emotional experiences, and they're worth more to people when the emotions are greater. One way this works with music is to use concerts, association with movies or TV shows, branded products associated with the band, and other sorts of tie-ins. With movies, the same movie is worth more when people go watch it together at the theatre than when they watch it alone years later on network TV. A novel is more valuable when your reading club is reading it right now and you want to participate in their discussions. These products are more valuable at certain times than at others. Watching a TV show the night it airs is more valuable because I can talk to my friends about it; watching it later (with TiVo) is less valuable. What can we do with games? I think the fan sites are a big help. Frequent updates and developer involvement in forums can help too. The Movies let users upload their creations (not their games) to the site. The Sims lets you download objects created by others. Even in a single player game, you can offer something that lets people connect to each other. When they're sharing an experience, it will have more emotional value. And that is something that could reduce piracy—you're not just buying a game; you're buying access to a community.

I think piracy will always be with us, but I think the open source model is unlikely to work for games. Charging for support gives a perverse incentives to developers to make things work badly or confusingly. Charging for service might work for some types of games, and the MMORPG developers seem to be exploring the options. I think the way to approach the problem is what many game developers already do partially without realizing it: offer multiple experiences at different prices. Offer a free demo that has a substantial part of the game and no support; this matches the marginal cost of the software alone. Offer the full version without annoying copy protection (why do so many developers make their paying customers get a worse game than the pirates get??). Make a ”special edition” that appeals to the least price sensitive and most rabid fans. Offer special products (t-shirts, trinkets, etc.) that tie in to the game. Make a community site that people actually like (so that they don't go to other sites for the information they want), and make all or some of it open only to people who bought the game. Make sure the developers are involved with the community site. Change the model from selling software to selling enjoyment. Look at other businesses that do this (amusement parks, movie theatres); they sell the basic product at a lower cost and then sell extras (such as food and drinks) for a much higher price than the marginal cost of those extras. Price-sensitive customers get annoyed by this, but it works for the business because they're not just paying for a drink; they're paying extra for the enjoyment of the drink in that location.

We need to consider the entire experience of playing a game, not only the software, as a potential source of revenue, and then figure out how to best recover the high fixed costs of making the game, and also allow for a low marginal price so that we can get a large audience. We need to consider that games don't need to be played in isolation; people talking about a game with their friends or even with strangers can add to the experience. We need to consider that different people are willing to pay different amounts for the experience. It's the entire experience we're selling, not just a box with software.

Rules of Algebra fail with floats

2006-12-16T18:40:00.000-08:00

One thing to be careful about when programming games is relying on the rules of algebra. Simple laws like the Associative Law and Distributive Law don't always work when using floating point numbers. I'll give some Python code to demonstrate, but these problems are with floats, not with Python.

Distributive Law. We've been taught that a * (b + c) == (a * b) + (a * c).
```
a, b, c = 0.111, 0.201, 0.305
s1 = a * (b + c)
s2 = (a * b) + (a * c)
print '%.08f - %.08f = %.08f' % (s1, s2, s1 - s2)
print '  equal? %s' % (s1 == s2)
```
These are the results:
```
0.05616600 - 0.05616600 = -0.00000000
  equal? False
```
The difference looks like 0, but it's not. The two sums are not equal. To see the problem, change the format specifier %.08f to %g.
Associative Law. We've been taught that a + (b + c) == (a + b) + c. When some of those are negative and some are positive (and occasionally even when they're all positive), the results won't be the same.
Additive Inverse. We've been taught that a + b - b == a.
```
a = 1e-30
b = 1e+30
print a, a + b - b, (a + b - b) == a
```
The result is that (a + b - b) != a. You can look at this example as a special case of the Associative Law.

To some of you these problems will seem obvious and not a big deal for most applications. Why do I bring it up in this blog? Loss of precision can open up exploits in multiplayer games. Let's consider a game in which you can trade with someone else, and the total amount of money is represented as a float. If player A has a large amount of money a, he may be able to send a very small amount x to B (who has b) without it affecting his own amount. We can have a + b < (a - x) + (b + x), which means this exploit creates new money out of nowhere.

If you're using floating point numbers, be sure to use double precision. Alternatively, use integers or fixed point arithmetic to avoid some of these issues. If you do a lot of math in your game, be sure to learn about numerical programming. There are a lot more issues than the simple ones I describe here.

Using oscillation to speed learning

2006-11-19T14:26:00.000-08:00

I've been reading Without Miracles. I had just read about children learning labels. The example was a child looking at a bird and then being told it was called a "bird", then looking at a different bird and being told it was a "bird". The child then has to generalize and consider that other small flying creatures are likely to be "birds" as well. However, upon seeing a butterfly and being told it was not a bird, the child then has to refine his understanding of what a "bird" is.

This form of learning, with overgeneralization followed by correction, may well be faster than undergeneralizing. For example, what would happen if the child only believed the two creatures he saw were birds, and did not label other small flying creatures as birds until explicitly told they were birds? He'd learn slower.

I was at the beach, looking at tide pools, when I realized there's a similarity to the child's learning. Rivers flow in one direction (usually) and have a certain amount of life in them. Beaches have water flowing in both directions, due to waves (short time scale), tides (medium time scale), and seasons (long time scale). The diversity of life in tide pools is far greater than what I've seen in rivers.

In the case of the child's learning, generalization (classifying everything as a bird) is one direction and correction (being told that some creatures previously thought to be birds are not) is the other direction. Could it be that oscillation leads to faster "learning" than a steady stream?

The advantage of learning and then correcting mistakes is that you can learn faster than if you were learning cautiously enough to avoid making mistakes. Many AI algorithms are of the cautious sort. It may be that it'd be better to have our games learn patterns very quickly and then keep a set of exceptions. For example, in Simulated Annealing, we slowly lower the temperature until the system stabilizes. It may be better to quickly lower the temperature, then raise it again, and continue oscillating for some time. In Neural Networks we change the neuron parameters very slowly. It may be better to change them quickly, then change them back if needed.

I'm enjoying the book a great deal but I haven't yet figured out how I might use this for my own games. My intuition tells me that there's something very useful here, but I haven't pinpointed anything specific.

The Guild 2

2006-11-04T10:25:00.000-08:00

Yesterday I took a look at the demo for The Guild 2. It's a strange game. It's somewhat like The Sims in that you have a character that has relationships with other people in the game, and you can start a family. It's somewhat like a role playing game in that you have classes, skills, abilities, attributes, experience points, combat, etc. It's somewhat like a city-building strategy game in that you can build mines, businesses, houses, and so on. The graphics and music are nice. The world feels alive—there are people wandering around, with jobs and relationships and government positions and alliances and feuds. While standing around, a random person came up to me and gave me a cake. I'm very impressed with the game world.

The problem is that someone forgot to design a fun game. In trying to do lots of different styles of games, it does none of them well.

The game is rather tedious. You have to keep track of your relationships with everyone else. These seem to be influenced by your position in society, your family, your religion, who you work for, and who works for you. It has more detail than The Sims (for example, you can buy objects and give them as gifts to someone) and more relationships to keep track of than in Tropico. The problem is that there's too much information, and you can't act on most of it. You only indirectly influence it. This is something that is impressive and thus appealing to game designers, but it's not actually any fun.

To run a business, you have to click on your cart, send it to the market, buy raw materials (prices are set by supply and demand) by dragging them into your cart, then send the cart back to your shop, drag the materials from the cart to the shop's inventory, click on an employee, and tell him to make an item. Then you wait for a while, and once the item is ready, you drag the item to the cart, send the cart to the market, and drag the item to the market stall to sell it (prices are set by supply and demand). It's impressive, but it's boring. Imagine if Warcraft had done this—you'd have to tell each orc to walk to the mine, pick up a tool, mine for metal, pick up the metal, carry it back to the storehouse, and then walk back to the mine. You have to do this for each business you run in The Guild 2. Although there is a way to set this on auto-pilot, there never should've been this much detail. The programmers wasted too much time with this.

There's also combat, positions in government, bribery, assassinations, thievery, a legal system (including court cases), and lots more complexity to this game. That's the real problem: there's too much to keep track of and do, and too little reward for doing it. You get to play out the drudgery of living as a serf in the Middle Ages. I can't even describe how bad the UI is.

There are also some amusing things in the game. Every building has a name: Better Homes, Lumpy & Liquid, The Hot Spot, Raw Iron Raw Power, A Waste of Paint, Roof Included, The Funny Farm. The help text is often strange:

... Scholars are also not adverse to compliments and gifts and will even let themselves be persuaded to dance.

Once the initial awkwardness has faded one can oft soften a reluctant scholar with soft embraces and gentle kisses, bewitch him in private conversation or even climb into a tub with him. But beware of using too much imagination in your courting, for scholars seldom appreciate variety.

There are odd player skills: Master of manure, Pack mule, Kama Sutra master, Exploiter, Great preacher, Deep sleep, Local club president, Face of innocence, Dorian Grayish. The description for the "Strong hair growth" skill starts out like this:

You have been blessed by nature with a curious biological phenomenon: whenever you must rot in the dungeon because of some misdeed, your hair begins to grow at a breathtaking speed. After a few hours, you look as though you have been mouldering for 30 years. ...

Even though the game doesn't look like it'll be any fun for most people, I do recommend that game developers try out the demo. Look for things that you might think would be cool in a game: multiple genres (from role playing to real time strategy to business simulation to action/combat), deep and complex simulation (relationships, businesses, employment, politics, law), open-endedness, etc. Try to figure out whether they are actually fun for a player or merely impressive to a developer. I would have loved to design and write a game like this. It's so impressive that it's sad to see that it's not at all fun.

World of Warcraft Analyses

2006-09-10T08:43:00.000-07:00

The PlayOn project at Xeroc PARC has been analyzing WoW data and then posting it on their blog. (These people get to play games at work!) Thanks to richardt for the link. Some findings I found interesting:

They computed the fraction of time each class joins a group. As you might expect, Priest was in a group much more often than any other class. Priests also level up faster than other classes. But that seems to be an anomaly. In general, people in groups level more slowly.

People are more likely to be at a level that's a multiple of 10, probably because there are certain rewards at levels that are multiples of 10, or there are penalties (such not being able to play on lower-level Battlegrounds). So people at a level just before those levels will play extra hard and people at those levels will try to avoid leveling. Leveling time in general is roughly proportional to the level, so you get a quadratic effect. There's a spike at level 40, most likely because that's when you can buy a mount.

Warriors are the most popular class at low levels. Hunters are the most popular class at high levels. Shamans are the least popular class. Humans are the most popular race. Orcs are the least popular race, despite them having the best dance moves.

It's a fun blog to read.

Ruby scares me

2006-07-20T18:17:00.000-07:00

Every time I take a look at Ruby, I am simultaneously intrigued and disgusted. Today I was looking at it once again, pondering the Camping framework for writing web apps, and ran across this explanation of how it works:

Behind the scenes, Camping actually reads its own source file (with the __FILE__ handle) and does a search and replace on all instances of Camping. It then evals the result and runs your app with the modified code!

— from O'Reilly's Ruby column

Argh!! On one hand, I feel like I shouldn't need to care how something is implemented. But I see this sort of thing (building and evaling code) so often in Ruby that it makes me worry that the language is incapable of expressing the abstractions that people actually want to build, and it might also be incapable of expressing the things I want to build. I guess I grew up treating eval as something to use only as a last resort. The only place I felt okay using eval was Scheme, where it took program trees instead of strings. Ruby still intrigues me though, so I'll probably try a project in Ruby at some point.

An old classic: Settlers II

2006-07-12T08:25:00.000-07:00

Settlers II has been remade for its 10th anniversary. I've tried out the demo and it reminded me of all the things I liked about Settlers. The game is somewhat unusual. It's a building+war game, like Age of Empires, Tropico, Command & Conquer, etc., but its emphasis is on building and not on war.

One of the unusual features is the transportation model. In most games of this sort, people walk around wherever they need to go, and you can build roads to speed up their movement. In Settlers, you must build roads, and every road segment has a settler assigned to it. That settler will move goods back and forth along the road. You have to carefully plan your roads to handle the traffic; roads can become bottlenecks. Making road segments long means you use up fewer settlers and allows faster travel; making them short means you get a higher capacity. Roads also become paved and can have donkeys to increase capacity.

The transportation model changes the implementation strategy for the game. Usually you run a pathfinder (like A*) for each of the peasants, and combine that with a movement algorithm to avoid local obstacles. This can get expensive when you have lots of peasants. Each peasant handles a single type of good, usually assigned by you. For example, you might assign a peasant to be a miner; the pathfinder will find a path between the mine and the warehouse. There is no further distribution of goods; it goes into a global store that can be accessed instantaneously from anywhere. In Settlers, the peasants are not using the pathfinder. Instead, the pathfinder is used for materials and goods. They are physical objects that have locations and can move around. They can be put in a warehouse, but they have to be moved to the location where they get used. The peasants and road segments serve as capacity restrictions. If a good needs to move from one place to another and the road it needs to travel on is “full”, it waits for the road segment (and associated peasant) to free up. This works somewhat like a packet-switched computer network.

How do the goods “decide” where to go? A local approach would be to make each good perform pathfinding to its destination. Pathfinding on the road graph will be much faster than pathfinding on a grid, because there are far fewer segments and connection points. But how do they find their destinations? We could either keep a list of points that require certain goods, or we could build an influence map. It's possible with an influence map to not even need pathfinding. I'm not sure what Settlers actually does.

Another difference between Settlers and other building games is that the Settlers economy has much longer chains of production. Forests can be cut to produce wood. Wood are milled into wooden boards. Boards are used to build farms and other buildings. Farmland is used to raise crops, yielding grain. Grain is milled into flour. Wells produce water. Flour plus water is baked into bread. Grain plus water is turned into beer. Fishermen use fishing poles to catch fish. Hunters use spears to catch animals. Animals taken to the slaughterhouse become meat. Meat, fish, and bread are fed to miners. Miners can mine for coal, iron, granite, and gold. Coal and iron can be smelted into steel. Steel is taken to the metalworks to make tools such as spears, and to the armory to make swords and shields. Granite is turned into stone. Stone is used to make new types of buildings. Gold is turned into gold coins. Gold coins, swords, and shields are given to soldiers. Soldiers are needed at watchtowers, which expand your territory. The economy is complex.

Also unlike other building games, you don't control any of your people directly. You can indirectly control them by building things. To go to war, you need soldiers, but you never explicitly recruit or place soldiers; they are produced whenever you have enough of the needed goods (gold, beer, sword, shield). You can influence what gets transported by choosing a transportation priority for each type of good (this is like QoS for TCP/IP), and you can set the priority of having soldiers vs. builders.

At the start of the game, you don't need to worry about the full economy. For example, you can't build tools without steel, which requires coal and iron, which requires miners, which requires bread and meat, which requires grain and water and animals, which requires flour, which requires farms, which requires wooden boards, which requires wood. Instead, your initial warehouse includes many types of goods, from which you can jumpstart your economy. You don't need to make rarely used items like tools until later in the game, when your settlement is large. It's a nice way to gradually introduce complexity to the player.

It would be nice to be able to see general trends, like whether I'm building up more bread than I need, or whether people are perpetually low on water. It's hard to manage everything in your head by checking manually. If I were in charge of a town like that, I'd hire some people to gather information and alert me when something's wrong. Overall though it's a very interesting game, and not like other games I've played, so I think it's worth exploring.

Update: [2006-07-21] Sören M points me to a design document about transportation in Widelands (a game much like Settlers II).

A Tale in the Desert 3: First Impressions

2006-07-09T15:35:00.000-07:00

A Tale in the Desert is a rather odd game. It's a MMORPG based in ancient Egypt. There aren't any monsters to fight. Instead, you perform tasks like gathering, mining, farming, weaving, fishing, and so on. You use the materials you gather to make equipment, which you can use to make more complex materials and objects. Eventually you can build sculptures, buildings, and monuments. The game has a story to it, with a beginning, middle, and end. You and everyone else in the game is part of that story. The ending depends on the actions of all the players.

It's quite different from anything else I've seen. Although games like World of Warcraft have gathering and crafting tasks, the focus there is combat, whereas in this game, it's all about gathering, crafting, building, trading, and socializing. The tasks you need to perform can depend on what others have done. For example, you may need to build something larger than what anyone else nearby has built. Once you build it, your object remains in the world, visible to everyone. As I wandered around the game world, almost every object I saw was something created by a player. As a new player, I needed to find areas that weren't already occupied, so that I could set up the equipment I needed. Some of the basic resources (wood, sand, mud, grass, stone, etc.) are shared, so it helps if you set up a workspace away from others. As far as I can tell though, workspaces have a short lifespan, so you work in an area for a while and then move on.

The tasks you need to perform can also depend on other players. For example, you may need to build an sculpture and leave it out in the open so that passers-by can vote on whether it's attractive or an eyesore. Or you may need to talk to people and convince them of some cause. Or you may need to get people to join your guild. The social aspect is important; other people aren't there only to help you fight monsters. There's also the ability to propose new laws and get signatures/votes; if the new law gets passed, the game developers will implement it (remember LambdaMOO?). I didn't explore that aspect of the game.

The graphics aren't great, although they didn't bother me much. There's very little sound or music, and that hurts the game a great deal. Sound effects are incredibly important. The UI is awful. It looks like it was designed by programmers: there's lots of abstraction and generality, like scrollbars, arbitrarily sized dialogs, deep menu hierarchies, and an attempt to make everything vague so that it's reusable in other contexts. For example, to dry out grass and turn it into straw, you need to Drop the grass. This is “cool” in that it reuses an existing function, but I think the UI would be better with the task explicitly listed. The UI also offers very little feedback about objects and actions. There are lots of objects around. Some are usable and some are not. You won't know until you click and get a menu. There are lots of places where you can't do something, but it won't tell you that you can't until after you've attempted to do it. For example, when planting flax seeds, it allowed me to plant a second seed too close to the first, then it told me it was too close. Mark the area in red or something to give people early feedback about whether their actions are going to succeed. Don't let me do something that's not allowed.

Another problem with the UI, at least for a beginner like me, is that it doesn't really give you any hints about what to do. There's a huge list of tasks, but no way to learn how to perform them. For example, I was supposed to learn Carpentry. How should I do that? I have no idea. There's no tutorial as far as I can tell. I ended up going to the web and searching for the information. How was I to know that I should find the "SArch" building (whatever that stands for) and click on it?

I played for several hours and got through the ~30 starter tasks, with a lot of help from the web. That opened up new possibilities of projects I could do. However the game felt rather tedious and uninspiring. Let's see... I need 100 bricks. I'll collect mud, straw, and sand, then stand around for 10 minutes making bricks. Boring. There's no challenge in that. It's not interesting. It's likely that the social aspect makes up for it (the crowd I talked to was much friendlier and more mature than in any other game I've been in), but I didn't stick around long enough to find out.

World of Warcraft: First Impressions

2006-07-03T20:38:00.000-07:00

I've been playing World of Warcraft (WoW). It's the MMORPG to try. Last year I played around 250 hours of Guild Wars, but it's not really an MMORPG; it's somewhat like Diablo 2, which is multiplayer, but not massively so.

To get a good feel for WoW, I played over 50 hours over the past 10 days. I tried out 6 of 8 races (Alliance: Human, Night Elf, Gnome, Dwarf; Horde: Troll, Tauren), 6 of 8 character classes (Druid, Hunter, Paladin, Rogue, Warlock, Warrior), 4 of 12 professions (Mining, Skinning, Cooking, Fishing), and 1 talent (Marksmanship). I visited all 6 major cities (Stormwind, IronForge, Darnassus, Ogrimmar, Thunder Bluff, Undercity) and 3 of 4 Goblin cities (Ratchet, Gadgetzan, Booty Bay). I played mostly PvE, but also tried out PvP, both out in the open and in 1 of the 3 PvP instances (Warsong Gulch). I visited 1 of 36 PvE “instances” (Ragefire Chasm) and 12 of 40 major regions on the map (The Barrens, Durotar, Mulgore, Thousand Needles, Dun Morogh, Elwynn Forest, Westfall, Redridge Mountains, Teldrassil, Stranglethorn Vale, Tirisfal Glades, Darkshore). I tried out 1 minor quest from 2 special events (Midsummer Festival and Scourge Invasion).

Overall, I thought the game was well done. It's much more complex than Guild Wars and there are lots of different styles of play. Guild Wars offers character classes plus secondary classes, giving essentially 15 different combinations, although the choice of which class is primary and which is secondary gives each of those combinations two styles. WoW offers 40 combinations of races and classes. The races affect your appearance and give you bonuses and skills; the classes affect your clothing and give you bonuses and skills. Within each character, Guild Wars offers 4 attributes and plenty of skills influenced by those attributes; WoW offers attributes but also 3 talent trees and plenty of skills influenced by them. In Guild Wars, the attributes can be changed to suit each mission or area; thus, you don't have to choose which to specialize in. In WoW, attributes are influenced by race and class, but can be modified by items and spells. The talents are permanent choices, and thus you treat them like races and classes, and have 120 combinations of races, classes, and talents. So already WoW has a much richer set of choices (“builds”) in characters. But wait, there's more! In WoW, you also have professions, which are non-combat activities, such as Skinning (get leather or other materials from animals), Leatherworking (to turn leather into items), and Enchanting (to add magic to items). As you use the skill, you become more proficient in it, and that allows you to do more things with it (for example, when you are better at Skinning, you can skin from higher level animals). You can choose 2 of 9 main professions, plus up to 3 side professions. This raises the combinations of character builds to 4320, although in practice, only around 14 of the 36 combinations of professions make sense, so there are a “mere” 1680 character builds you might want to play. In Guild Wars, your weapon choices are largely determined by your character class. In WoW, they're influenced by class but you can learn to use new types of weapons. There are 16 types of weapons (such as Swords, Wands, Bows, etc.), and each character class starts out knowing some of them, and can learn up to 4 to 15 of them (varies by class). Once you choose a weapon, it increases the number of character builds to nearly 12,000. Compare that to 15 in Guild Wars and you'll get a sense of how rich this game is. I barely scratched the surface with what I tried out.

Each race has a starting location in the world. There are 8 races and 6 starting locations. This greatly increases replay value. In Guild Wars, there's one place everyone starts and explores, so the second time through you're not seeing anything new. In WoW, you can play 6 times and see brand new scenery each time. The WoW world is huge, varied, and non-linear; Guild Wars in contrast is fairly linear, much smaller, and has 5 types of areas (pre-Searing, post-Searing, jungle, desert, volcano). Different areas have monsters of different levels, so you can't venture in to the higher level areas without being killed. With several of my characters I did however manage to sneak by some monsters and get to high level areas, where one hit from a monster would kill me. There are special areas called instances. These are areas that are separate for each group of people playing. In Guild Wars, all areas other than the cities are instances; in WoW, most areas are not, so you can see lots of other people doing things unrelated to your party's actions (seeing other people is fun!).

There's just so much to do in World of Warcraft, and so many styles of play, that it's no wonder people spend huge amounts of time playing. There are also lots of repetitive actions that lead to variable results; this activates the gambling portions of the brain. For example, when performing quests to retrieve items, you will sometimes get the item and sometimes not; when killing monsters, you will sometimes get treasure and sometimes not; when fishing, you will sometimes get l fish (which can be eaten to gain health) and sometimes you will get treasure; when improving skills sometimes you will gain a skill point and sometimes not. Everything you do works this way; it's no wonder it's addictive.

The game was pretty smooth when it ran. Several times though the realm I was on would be down, and I couldn't log on. When I was on though everything was smooth and (as far as I could tell) bug-free. Blizzard seems to be pretty good at this.

I enjoyed the game but in the end I wasn't addicted to it (despite playing 50+ hours in 10 days). The main problem I saw was that the reward was far too low for the amount of time I spent. Running from place to place is really time consuming. At higher levels you can buy creatures to ride on, and this lowers travel time, but the reward is less pain rather than something rewarding in its own right.

The quests were often repetitive and boring. For example, I had a quest to go kill some ostrich-like monsters. It took a while to run out to that location and kill them. When I got back to town, I got a small reward and then was told to go out and kill some lions. I had to go back to the same area I was just in, kill lions, and go back. I was then told to kill some dinosaurs. I had to go back to the same area I was just in, kill dinosaurs, and go back. After that the series of hunting quests continued in a slightly different location with slightly different animals (zebras, more lions, more birds, and more dinosaurs). There were probably at least 15 quests like this. Another line of quests involved killing some variant of kobold, going back to town, then being told to kill a different variant of kobold in that same area, then going back to town, then being told to kill yet another variant of kobold in the same area. These kinds of quests really stretch out gameplay, because you have to run back and forth every time; you can't get get the next quest until you've finished the previous one. Occasionally the quest would be more interesting (for example, collecting dinosaur eggs while killing the dinosaurs), but it only seemed slightly interesting because the quests were boring.

I do like the whimsy in the game. There are lots of cultural references, silly items, etc. The dances are fun (for example, the orcs dance like MC Hammer). The graphics look cartoony, making the game feel more fun and less serious.

With the trial account I played, I couldn't participate in some of the interesting aspects of the game, like the auction system. In Guild Wars, you have to wander around, asking people for things to buy or sell. It's chaotic and it was so much of a pain, I rarely traded with anyone. With the WoW auction system, I think I would trade much more. Comparing trading in the two games really demonstrates how important efficient markets are. I also couldn't really get involved in guilds, which are apparently a lot of fun (but have high time requirements).

On my last day, I sold all my items and found that I had earned around 2.6 gold (26,000 copper pieces). This amount of wealth was unimaginable to me a few days earlier. The scale of wealth seems to go up exponentially. For example, a bag that can hold 8 items costs 4 times as much as a bag that can hold 6 items. Small increases in power come at a large increase in price. I think this is a good game design, but it felt strange to me. Despite getting so much, the last few days were just not much fun. Since I had only a short time left before my trial account was cancelled, I decided to kill off my main character in a most spectacular way. I went to the top of Thunder Bluff, the highest cliff I had found in the game, set myself on fire, and jumped off, to my death.

It's a very interesting and rich game. It's just not for me. It takes too much time and wasn't rewarding enough. If I were paying the monthly fee, I would feel like I had to play a lot to get my money's worth, and I'd end up playing even when it wasn't fun. The other problem I have with playing games online is that real-life interruptions can lead to my death in the game. If you have kids, you're going to have real-life interruptions. So I'll go back to playing Oblivion occasionally, and doing other projects (like writing a transportation game, going on scenic drives, and writing web articles). I do encourage people to try out the free trial (either from FilePlanet or by getting an invitation from someone who already plays), because it's an interesting game for game developers to study. I'm glad I tried it out. And I'm glad I didn't become addicted. :-)

Playing Oblivion

2006-06-10T22:51:00.000-07:00

In case you've been wondering why this blog (and progress on my game) has been quiet lately, it's because I've been playing The Elder Scrolls IV: Oblivion. It's a fun game, in part because the NPCs do their own thing, and it's fun to watch them.

Tonight I was running north along one of the main roads, and a bandit jumped out to rob me. He jumped a bit too late, for I kept running with a bandit on my tail. I met another bandit, who also started chasing me. I then met a third bandit and continued to run. I then saw two of them turn and start chasing a woman on horseback. She delivers the newspaper daily to all the cities. She screams and starts to flee downhill. I turn around and start chasing the bandits, not because I want to save her, but because I want to watch the chase scene. After chasing her down the hill to the bay, they noticed me and started chasing me instead. She fled to the south and I went to the north. I decided to escape by swimming across the bay. To my amazement, they started swimming too. I have a magic item that doesn't require me to breathe underwater, so I went underwater and hoped they would drown. They didn't. They periodically came up for air. As I reached the other side of the bay, I looked down and saw the two of them coming up for air, then diving again. I wasn't able to escape.

I decided to turn east and head for a fort. Many forts contain monsters, and these monsters often fight humans, including bandits. Not all of my enemies are friendly towards one another. At the fort was a troll, a mudcrab, and a bear. I jumped up to a high perch and watched the two bandits defeat the three creatures. I then decided to lead them to a nearby cave. Along the way the bandits killed a wolf, and at the cave they met a minotaur and an ogre. In Oblivion, ogres are incredibly strong. It was here that I expected the bandits to meet their end. Instead, they fled! They swam across the bay, out of my trap.

I chased the bandits across the bay. I lost one of them, but saw the other one run up a hill. I chased him for a while but eventually he got away. I went back across the bay to the minotaur and ogre, and led them to a nearby goblin cave. It took three goblins to kill them. Now I have one goblin remaining. I took him to another cave, inhabited by a rival tribe of goblins. Four goblins from the rival tribe killed the one goblin I led there. I now had four goblins chasing me. So I took them back to the first goblin tribe's cave. I kept running back and forth, not actually fighting, but just leading goblins to each others' caves, and the hordes wiped each other out.

Playing this way is amusing.

Having played for 130 hours, I'm about halfway through Oblivion. It's an interesting game for a game programmer to play. You can guess what techniques they used for their AI, and then run experiments to see what happens. I'm probably not playing the way they meant the game to be played.

Do people really want innovation in games?

2006-05-12T19:43:00.000-07:00

People seem to complain that games (and movies) are all the same—that there isn't enough innovation. I suspect though that people don't really want innovation. Guitar Hero is innovative. Wii is innovative (watch the Wii video from E3). But if you enjoyed some game, don't you want more like it? Or would you rather take your chances with something random?

In the field of machine learning, there is the notion of exploration vs. exploitation. As you learn things, you want to take advantage of what you've learned. If you never exploit what you've learned, why bother learning it? Why bother learning to read if you're never going to read? However you can't only spend your time doing what you know. You also want to spend some of your time exploring new things. Otherwise you may not discover something better than what you know. 100% exploitation is a mediocre strategy. 100% exploration is a bad strategy. You really want some of each.

In game development, movies, books, etc., it would be a shame if there were no sequels or games similar to existing games. That would mean that if someone discovers something good, we never do that again. On the other hand we don't want only sequels. I think games like Guitar Hero, Gish, The Sims, Everquest, and Puzzle Pirates demonstrate that there is innovation out there. Some people are arguing that there isn't enough. Others are arguing that there shouldn't ever be sequels. It's hard to know what the “right” amount is. I do believe that the way the free market works, there will be slightly less innovation than is optimal. It's not zero though. And I don't believe that you can force the market to innovate more. Ironically, a market with lots of small independent game companies is likely to produce less innovative games than a market with behemoths like EA. But that's a story for another day.

I find that of the games I've gotten recently (Black and White 2, The Movies, Guild Wars, Oblivion), I've enjoyed the innovative games less. I think that's because the sequels have more refinement in them, and that makes them better than the innovative games, which haven't been tried out on a large scale and don't yet have the feedback needed for improvement. I'm trying to spend around 10-20% of my time playing innovative games, in part because I like to study them as a game programmer, but also because I want to spend some of my time exploring new things.

Innovation isn't dead. It just produces lots of junk, which is what it should do. If all innovative games are good, people aren't experimenting enough. Sequels aren't bad. If we never had sequels, we'd never be able to polish the rough gems found in the innovative games.

Prediction, Chaos, and Order

2006-03-12T12:29:00.000-08:00

When you play a game, can you predict what's going to happen? I think being able to predict everything makes the game boring. Being able to predict nothing makes winning unrewarding. It becomes a game of chance rather than a game of skill. It's games in between that I'm interested in.

I want skill to be important, so that winning is rewarding, but make each instance of the game different, so that you can play repeatedly. How can you make the game somewhat unpredictable?

Multiplayer. If you add other humans, and humans are hard to predict, then we can't predict the outcome of the game. I think however that this isn't sufficient. If the opponent is good and the game predictable, you can predict what the opponent should do. Tic-Tac-Toe is an example of a game that's multiplayer but boring.
Complexity. In some games, the game world is so complex that a human cannot accurately predict what will happen, even if everything were known. Chess is an example of a multiplayer game in which the entire game board is known, but it is not possible for a human to determine the best move.
Randomness. If some aspects of the game are random (for example, the roll of the dice), the game will be different each time. If there's too much randomness, then the winner is essentially random. If there's too little, then each game will essentially be the same. But if you get it just right, then the player's skill demonstrates how he reacts to the game. There's also randomness in physical games. For example, when playing golf there's some randomness in where the ball goes, just from unpredictable variation in the stroke, and factors like air density and wind.
Information Hiding. Some information about the game world can be hidden from the player, and the player's skill can be used to infer aspects of the hidden information. You can hide the initial game world (for example, the cards initially dealt to each player), the opponent's moves (for example, the cards discarded by an opponent), or the result of randomness (for example, the cards drawn from a shuffled deck during the game).

Many games combine more than one of these. For example, Chess combines complexity and multiplayer. Poker combines information hiding, multiplayer, and randomness. Civilization combines all four.

When playing a game that involves randomness, it is important to note that skill is not the only factor; “luck” matters as well. In the NCAA tournaments starting this week, as with all sports games, you cannot conclude that the winner is a better player. You can only conclude that the winner is likely to be a better player. That's why rematches are useful—they let you be more confident in who's better.

My transportation game involves randomness and complexity, and I am undecided about information hiding. It's a single player game, and I am not planning multiplayer. After all, I will be the only player.

Transportation game, models

2006-03-12T10:58:00.000-08:00

I'm trying to use stocks and flows to create a model for my transportation game. Stocks correspond to nouns and flows correspond to verbs. At first I thought businesses would be stocks and the transportation of goods would correspond to flows. But I could also see the businesses as flows (since they consume and produce things) and the cargo areas and trucks as the stocks. Or maybe both trucks and businesses are flows, and only cargo areas (loading docks) and warehouses are stocks. Or maybe the cargo itself is the stock.

When it comes to a game, the player's decisions (and the AI's decisions) can directly affect flows, but not stocks. You can change the rate of production in Warcraft by hiring more peons, researching technology, etc. Production of gold is a flow. You do not directly change the amount of gold you have (except by buying something, but I think that's an instantaneous flow). Gold is a stock. There's no decision to be made with a stock—it just exists. There is a decision to be made with each flow, because you can throttle it back from its maximum. There are other decisions to make as well, but the basic resource management decisions (for gold, wood, soldiers, etc.) are about flows, not stocks.

In my game, the player controls the movement of trucks and the AI controls the businesses. The decisions are based partly on how much of each resource is available. I'm planning to treat trucks as stocks and the loading/unloading of them as flows. Businesses will be flows, but their cargo areas will be stocks.

The transfer of cargo is not enough to make an interesting game. The player will also need to make decisions about infrastructure and placement of transportation systems. The actual loading and unloading of trucks is boring; it's likely that an AI agent, acting on behalf of the player, will make those decisions. I still don't have a clear idea of where I'm going with this game, but it's already led me to some interesting topics (operations reseach, system dynamics, supply chain management).

Impolite game: Spellforce 2

2006-03-09T22:15:00.000-08:00

I no longer play Guild Wars, Black and White 2, or The Movies, so I've been looking for another game to buy. Battle for Middle Earth 2 and Spellforce 2 both looked interesting, so I downloaded their demos.

Spellforce 2 won't start the demo unless I install StarForce. What's the point of copy protecting a demo? And worse, StarForce is awful and I am not buying games with it. So Spellforce 2's demo goes into the recycle bin, and I'm trying out Battle for Middle Earth 2, which looks and sounds nice. It seems to use SafeDisc, which is perhaps not as bad as StarForce, but still annoying. It also has lots of splash screens that can't be aborted by pressing Esc or Enter or Space or by clicking the mouse. Why do games tell you to use NVidia/ATI and Intel/AMD? Do they really want to tell 75% of their audience that they've chosen badly? I haven't found a major commercial game as friendly as Guild Wars. Fortunately Guild Wars is about to release an expansion pack, so perhaps I'll wait for that.

Transportation game, basic objects

2006-02-26T11:46:00.000-08:00

I wanted to start with something simple for my transportation game. I want to explore the transportation of goods between businesses. I created a simple model:

Business. Each business (labeled B in the diagram) can consume and produce items. For example, a steel mill consumes iron and produces steel. Some businesses only consume; some only produce. In my initial implementation, there is only one producer (a dock, where goods are imported from other areas) and one consumer (a retail store, where goods are bought).
Cargo. The goods and materials are put into containers (crates, boxes, pallets, etc.) and the containers (labeled C in the diagram) are moved around the game world. Each container represents some amount of material or goods. In my initial implementation, there is only one type of cargo (“goods”) and only one size of container.
Loading Areas. A business may not consume goods as soon as they arrive, and it may produce goods that are not immediately picked up. Loading areas (labeled A in the diagram) are a place for cargo to be stored.

I haven't yet chosen good terminology. Is it business or building? Is it cargo or container or goods? Consistent use of terminology will help in picking good names in the code. I want to choose names that are general enough to cover a wide variety of cases.

I think the model has some nice properties. It's very general, so it can apply to many different kinds of businesses. For example, a warehouse is a business that produces the same thing it consumes, and consists almost entirely of loading areas. The loading areas make it easy for the player to see when the transportation system is working too fast or too slow. However, there are a lot of unanswered questions at this point. Does each type of cargo require its own loading area? Does a business buy from just anyone or does it choose its suppliers? How are perishable goods represented? I will leave these questions for later and focus on the simple case: one producer, one supplier, one type of cargo.

Selecting objects in a 3d world

2006-02-25T23:55:00.000-08:00

Once I can move around in my game world, the next step is to interact with objects. I need to determine what object, if any, the mouse points at. There are three general approaches I know of:

OpenGL picking. In OpenGL, you can use “selection mode” to identify which object the mouse points at. This involves assigning a number to each object using glPushName/glPopName, then re-rendering the portion of the scene very close to the mouse pointer using gluPickMatrix and glRenderMode(GL_SELECT), then looking at the object numbers that were rendered by reading from the glSelectBuffer array. In theory, you can re-render using exactly the same rendering code. In practice, you want to skip expensive operations like setting up textures, drawing outlines, using shaders, etc. Once you determine what object was drawn at that location, you still don't know exactly where the mouse points. I used this approach in SimBlob 2 and was somewhat unhappy with it. It's easy but it's sort of ugly.
Raycasting. The mouse pointer is a 2d location, and it translates into a ray in 3d space. In theory, the ray begins at the camera and goes back into the distance. In practice, the ray begins at the near plane of the viewing frustum and goes through the far plane. You can use gluUnProject to determine where the ray is; use z==0 for the near plane and z==1 for the far plane. Raycasting works well if you have kept the geometry of all of your objects; it's more of a pain if you generate it on the fly (as I did in SimBlob 2). You have to implement ray-object intersection for all of your object primitives (triangles, boxes, etc.), and it helps if you have a scene graph or spatial partitioning tree so that you don't have to intersect the ray with every object in the world. Once you perform the intersection, the closest hit tells you not only which object is involved but where on that object the mouse points. This approach requires the most work but it's the most reliable and has the best accuracy.
Depth buffer. Just about everyone is using the depth buffer in a 3d program. Once you render your scene, OpenGL has the depth (z) value at every pixel. You can ask for the z value with glReadPixels. You can then compute the world space location of the mouse pointer using gluUnProject and the z value you just read. The final step is to determine what object is at that location. This approach is easy, but the depth buffer doesn't have much precision, the precision varies among graphics cards, and the depth buffer is altered when using polygon offsets, so it's not reliable. Another disadvantage is that translucent objects get in the way because they show up in the depth buffer.

I started out using the depth buffer approach, but I've switched to raycasting. The depth buffer has too little precision to give me the accuracy I wanted. I also wanted to distinguish between game objects (selectable) and translucent annotations (not selectable), and the depth buffer doesn't give me that level of control.

Navigating a 3d world

2006-02-22T20:51:00.000-08:00

As I implemented navigation in my 3d world, I had a set of choices to make about how navigation should work. There's a camera with some position (x, y, z) pointing in some direction (θ, ρ) and some type of lens (field of view). That gives me 6 variables for the player to control, and that seems like too many.

Scrolling (Panning). If you scroll “up”, what direction does the document go? In most GUI systems, the document goes down. Try it out in your web browser. As you drag the scroll bar up, the document moves down. However, some types of documents move the opposite way. Try visiting Google Maps and drag the map around. As you drag the mouse up, the document (map) moves up. The difference is in what you are dragging. In most applications (including web browsers), you are dragging the view. If you move the view up, you move towards the top of the document, which means the document moves down. If however you're dragging the document, it goes in the other direction. I have been playing Black and White 2 lately, and in it you drag the map. I initially chose to drag the document (map), but then changed it to dragging the view (camera).
Scroll controls position or velocity. If you drag the mouse pointer, does it control the position of the scrolling or the speed? If you have Firefox or Opera, try the autoscroll feature and compare it to using the scrollbar. Autoscroll controls the speed; the scrollbar controls the position. The advantage of controlling the position is that it feels easy to control, especially when combined with dragging the document. The advantage of controlling the velocity is that you can move around the entire game world without repeatedly lifting the mouse, dragging across the screen, then lifting the mouse again. Some applications offer both. Google Earth and some OpenGL demos let you drag to control the position, but if you let go while still dragging, it sets the velocity. I find this very hard to control. I chose to make mouse dragging control only the velocity.
Rotation. The camera direction has two degrees of freedom, whether you use angles or vectors, so you need two controls for full control of it. Some games restrict the camera, and thus may only need one or zero controls. I chose to fully allow rotation around the z axis and offer minimal control over rotation of the other axis (looking up and down). Given rotation, there is a choice of rotation point. Black and White 2 is unusual in that it rotates and zooms around the position you point to with the mouse. It gives more control but I found it disorienting. I instead chose to rotate around the center of the screen. The best rotation point is likely to be something closer to the camera than what I've chosen, but rotating around the center of the screen is easier to implement.
Type of zoom. There are two approaches to zooming. You can change the lens. A “telephoto lens” has a small field of view and corresponds to “zoomed in”; a “wide-angle lens” has a large field of view and corresponds to “zoomed out”. (I'm being a bit imprecise; see this article and the comments if you want the details.) You can also change the position. Moving the camera close to the subject makes it “zoomed in”; moving it far from the subject makes it “zoomed out”. These two approaches are not equivalent. I chose to keep the lens fixed and move the camera around for zooming. Dragging the mouse up or down moves the camera up or down, which also rotates the view somewhat. When the camera is up high, it's rotated to point top-down; when it's near the ground, it's rotated to point forwards.

I started with 6 variables to control. Dragging the mouse occurs in 2 dimensions, allowing control of 2 variables per button or modifier. For a typical strategy game, god game, or city builder, the player can move around the entire map, so you probably want to control camera position (2 or 3 variables), camera direction (1 or 2 variables), and zoom (1 variable). For a first person shooter, the camera must remain at the player's location, so you'd probably want to control camera rotation (2 variables) and zoom (1 variable). For a third person RPG, you probably want camera rotation (1 variable) and zoom (1 variable).

My game is a simulation, so I want to move the camera in at least 2 dimensions, plus 1 variable for rotation and 1 for zooming. I don't allow changing the camera lens, so instead zooming involves changing both the camera height and rotation. That leaves me 4 variables to control with mouse drags. I'm reserving the left mouse button for interacting with game objects. I've chosen to assign the right button to scrolling (2 variables); and the middle button to rotation (1 variable) and zooming (1 variable). These mouse dragging rules make the mouse dragging always control the camera, not the map. They're simple and self consistent. They aren't perfect, but I'm happy with them so far.

Rough sketch for a transportation game

2006-02-20T22:18:00.000-08:00

As I thought about the things I learned working on the SimBlob project, I realized that I hadn't explored a lot of the topics I originally wanted to explore. I spent my time playing with environmental simulation (water, weather, fires, dams, floods, vegetation, etc.) and never got to anything else. I decided to start over and focus on a few topics in a simple game. In my new project I'm going to explore economic simulation and transportation networks. I have a rough idea of where I'm going, but as I learn things, I expect that the design will change.

There are lots of transportation/economic/city games out there: Railroad Tycoon, Transport Tycoon, SimCity, Simutrans, Locomotion, Transport Giant, Traffic Giant, Industry Giant, LinCity, A-Train, Capitalism, The Settlers, Mobility, and probably many more. There are also many projects in development (some abandoned): Transport Empire, OpenCity, 3DTT, Widelands, Zugspiel, and of course, BlobCity.

My intent is not to clone one of those games, but instead to explore economic and transportation models by writing a game. Throughout history, transportation has affected the development of business and vice versa. The Phoenicians used ships to transport goods, and built a trading empire that lasted a thousand years. The Romans built roads and aqueducts. The Arab empire was based on trade between the east and the west, using caravans and ships. In the United States, railroads greatly altered the flow of goods and linked the west and east coasts. The Panama Canal and Suez Canal helped goods flow by ship. In the late 20th century, advances in transportation made possible the rise of FedEx and the flow of cheap goods from the Asia Pacific region. The use of standard shipping containers linked ship, rail, and truck transportation systems together. None of the games I've tried explore all of these ideas. Have you ever seen a crossdock or Less-than-Truckload shipping in a computer game? I've been fascinated with these topics and would like to explore them in a simulation game.

The basic idea of the game is that businesses trade with each other using an inefficient transportation network (such as people carrying boxes on foot), and the player can offer better forms of transportation. As transportation gets cheaper, the businesses make more money, so they expand. The number of businesses goes down, but the size of the businesses goes up. Increased volume and a change in business structure means the player has to adapt. The player has to choose among hand delivery, hand trucks, carriages, gasoline powered trucks, large trucks (semi-trailer trucks), rail, and ships. As volume goes up, the basic unit being transported gets larger as well, from individual products to boxes to pallets to containers. Upgrading too early is wasteful; upgrading too late is inefficient. Reliable transportation infrastructure can affect how businesses and cities develop. The player has to choose areas of the world to develop, structures to use for each type of good (central distribution, multiple hubs, point to point), sharing among multiple types of goods, temporary storage (warehouses), and modes of transport. As times change, the player has to monitor the efficiency, health, and profitability of the networks and choose which to upgrade, replace, or dismantle. I'm really not sure whether such a game would be fun for anyone but me. I tend to like logistics in games.

Given that game programming is just a hobby of mine (and I have plenty of other hobbies), I think the basic idea is too ambitious for me to attempt at first. Instead I'll design a simpler game and work on that. I've found in the past that if I take big steps, I'm more likely to fall, so I've learned to take small steps. I also don't want to spend forever on this game; I have plenty of other topics I want to explore. Once I've decided my next steps, I'll post them here.

Getting started, 3d world

2006-02-20T21:05:00.000-08:00

I'm starting a new game project, not because I think I'll write a cool game, but because I want to explore some ideas (economic simulation and transportation networks). I decided to use 3d graphics for two reasons:

I want to learn more 3d programming. I've played with GL and OpenGL for a long time but I've never been completely comfortable in a 3d world. Each time I write an OpenGL program, I learn more about 3d graphics programming.
Ease of programming. I believe it's easier to work in a 3d graphics system than in a 2d graphics system, until you get to the point where you want artwork. Since I don't expect to have nice artwork, I think 3d graphics will be easier. The graphics card handles things like isometric views, filling polygons, gradients, lighting, and textures. There are simple approaches for mapping screen coordinates to game coordinates and back, because the graphics card does the mapping. It's very simple to alter the appearance of objects for highlighting and mouse manipulation; you can just change the color or lighting. And the CPU is freed up for doing things like AI and world simulation.

I started out writing a simple GLUT program that set up a window and the camera, then drew a simple triangle. Once I got it running, I added stub code for the standard set of GLUT callbacks (mouse handler, keyboard handler, window resize handler). I changed the scene from a simple triangle to a square grid, added a mouse handler that highlighted the current square, and made the right mouse button drag the camera around. I then started refactoring the simple GLUT program into modules (mouse, camera, timer, vector algebra, etc.), added simple lighting, improved the camera dragging code, and added some cubes to the scene. I implemented collision detection between rays and boxes and then used that to highlight the object the mouse pointed to.

Working a little bit each night, I've spent a week on all of this. It's all graphics code and no real game code. Have I gotten stuck in a “tar pit”? No, although there are some things like lighting and gradients that are dangerous to spend too much time on, I think this initial time setting up the 3d world will be well worth it later on.

When I work with programming languages, I really appreciate having an interactive prompt. Lisp, Scheme, and Python are much more approachable because they have this. I can just start Python and inspect variables, create and change objects, explore, test, etc., all without having to go back to my code and insert new commands. You can also do this with interactive development environments (like Smalltalk's). I want something similar at the game level, where I can move around freely and click on an object to see all of its properties. I'd like to create, destroy, and modify objects as the game is running. I don't expect to build all of this at the very beginning, but having an infrastructure that exposes all the game objects in a uniform way will help me later on. How much do I really need at this point though?

Two of the approaches used to uniformly represent 3d objects are scene graphs and spatial partitioning (BSP trees, octtrees, bounding box trees, etc.). Scene graphs are useful for representing changes to lighting, scale, rotation, translation, color, material, textures, and objects with shared components. For example, instead of representing a complex soldier 3d model for each soldier object, you'd store it once and have it occur multiple times in the scene graph, each time with a different rotation and position. Spatial partitioning is useful for collision detection. For example, instead of testing every vehicle against every other vehicle to see if any of them collided, you would partition space into smaller areas and only test vehicles if they are in the same part of the game world. Both scene graphs and spatial partitioning can also be used to render only the objects that are visible in the scene; this can greatly speed up the rendering.

I've decided that the number of objects in my game is small at the moment and is likely to stay small for some time, so I will use the brute force approach. I'll test against every object for collision detection, I'll render every object and let the graphics card figure it out, and I'll replicate geometry (vertices, colors, normals, etc.) for each object. At some point I may need scene graphs and spatial partitioning, and I'll go back and add them in. Code that depends on whether I have a list or a scene graph should remain as isolated as possible, so that I can switch later.

Having written a minimal 3d world rendering system, I'm ready to go back to designing more of the game. While exploring new ideas, I tend to alternate between design and implementation. What I learn from implementation feeds back into the next round of design, and working on the design lets me step back from the implementation to see the big picture.

All the code for this game is open source, under the MIT license.

Getting started, again

2006-02-18T17:17:00.000-08:00

I'm starting a new game project. First, I made a list of my goals (which mainly involve trying out new things). Then I sketched out the idea for a game and thought a little about how it would play and what I would learn by programming it.

Before starting to program though, I started by setting up my programming environment:

Version control. I set up a Subversion repository on local disk. Later: set up a remote repository, either on a web server or using some code hosting service like Sourceforge.
Makefile. I set up a simple Makefile that should work on Linux, Mac OS X, and Windows/Cygwin, using conditional compilation to isolate the platform-specific rules. Later: figure out automake or makemake or one of those other cross-platform build configuration systems.
Notes file. I created a text file where I will keep all my notes. It needs to be something easy to edit and search through. Later: use a wiki?
Backups. I have a script that uses rsync over ssh to copy the Subversion repository to another machine. Later: get an off-site backup solution.
Install VMWare. VMWare offers their Player for free, and they also offer an Ubuntu Linux image for download. It was very easy to set this up. After Ubuntu started up (inside VMWare, running inside Windows XP), I had to install a few more packages (g++, OpenGL+GLUT development libraries, GNU make), but after that I was able to test my code on Linux. I don't have a similar setup to test on the Mac. Later: set up a script that will periodically sync with the Subversion repository, attempt to compile, and email any error messages to me.

After setting up the development environment, I wrote a simple 3D application. I find it much easier to extend existing code than design everything up front and write it all at once, so I start by writing a very simple program that I can then extend.

My next step on the design side will be to write down a more detailed description of the game world, what the player is supposed to do, and why the task is fun/challenging. My next step on the implementation side will be to figure out how I want to represent the game world.

Change of Direction

2006-02-18T12:43:00.000-08:00

As I worked on SimBlob 2 and learned more about 3D graphics, I started changing the game from hexagonal to triangular grids. I then got distracted and started writing an article about grids for my game programming site. While writing the article I realized that there are so many other topics I wanted to explore with SimBlob, and never got around to them. Why?

I spent most of my time in SimBlob 1 (1994-1998) exploring terrain generation, hexagonal maps, water flow, erosion, multithreaded programming, and GUI libraries. I spent most of my time in SimBlob 2 (2002-2005) exploring terrain generation, hexagonal maps, water flow, erosion, and 3D graphics libraries. There's a lot of overlap there. I ended up exploring a lot of the same ideas again. I love those topics, but they've become “tar pits” for me. I get stuck, tweaking and trying out new variants, trying to make it just right. In the end I've learned something and had a lot of fun but haven't gotten much done. Since I am writing games as a hobby, that's just fine, right?

The trouble is that when I get stuck doing one thing repeatedly, I am not spending my time trying out new things. I want to use games to explore environmental simulation, business simulation, city simulation, transportation systems, autonomous agents, machine learning and AI, control theory, and emergent behavior. Of these topics, I've spent most of my time focusing on environmental simulation. I think that was fine the first time, but after recognizing the tar pits in SimBlob 1, I created them again in SimBlob 2, and ended up getting stuck again on the very same topics.

I've decided to stop working on SimBlob 2 and start working on a new game. I'm avoiding the tar pits I've had in the past (terrain, water flow, erosion, hexagon/triangle grids) by having a completely flat grid with square tiles and no water. Sometimes doing something quite different is just what you need. I want to explore 3D graphics some more, but the main focus will be on economic simulation and transportation systems. I expect to find new tar pits to get stuck in. :-)

Polite games

2006-02-06T18:34:00.000-08:00

A few months ago I mentioned that Guild Wars is polite, and as a result, I play a lot more. I still play Guild Wars occasionally. It's so easy to start up, and I don't have to go find the CD.

The two games I've gotten since then are The Movies and Black and White 2 (both from Lionhead Studios). Both of them have long startup sequences. They show me splash screens and advertisements (for Intel and ATI) every time. Then only after the splash screens are shown does the game start loading. At the very least the game should load while the splash screens are up! In addition, the CD has to be in the drive for the game to start. That means it's a major pain to go back and forth between the games.

I find that I'm playing the polite game more than the impolite games. If I'm in the mood to play a game but I have to go find the CD, I'm less likely to play that game. And every time I have to sit there looking at the Lionhead Studios logo, I'm reminded of the company that makes me sit there instead of taking me straight to the game.

Another impolite practice used by many game companies is to use nasty copy protection techniques. I don't get games from the file sharing networks, but it makes me unhappy that pirates are getting a better game experience than I am! (Copy protection gives people more incentive to get a pirate copy instead of buying the game.) What I find totally weird is that StarForce copy protection is even used for game demos. What's the point of making a free demo uncopyable?? StarForce remains on my system even though I've uninstalled the King Kong demo. That's awful. I'm not going to buy any of those games now.

You can find instructions for removing StarForce on this StarForce Boycott site.

Make your software polite, and I'll use it more. Make your software rude, and I'll avoid it.

Update: [2006-03-12] After removing the StarForce drivers, I discovered that my CD-ROM drive was in "PIO" mode instead of "DMA" mode like it should be. This is a symptom of StarForce having been on my system. I uninstalled the IDE drivers in Windows XP and rebooted, and it reinstalled them in DMA mode. PIO mode on some newer drives causes damage over time; I don't know if my drive has suffered any damage.

SRE on the web

2006-01-22T08:47:00.000-08:00

Ten years ago, I lost the source code to Solar Realms Elite (SRE), a game I had worked on. Since then, many people have wanted to build a clone. I've tried to help them, both through email and by posting what I remember about the game's design. However, most of the projects had not gotten very far.

Yanick Bourbeau has built a web version of SRE called Imperium Galactica (which also happens to be the name of an older, unrelated game). It's fairly complete and offers a few things SRE did not (like simultaneous play by several players). I've been playing for a few days and it's fun! The game isn't quite balanced yet, but that will take a little bit of time to fine tune. Try it out!

SVG woes

2005-12-30T07:57:00.000-08:00

I've been working on some new illustrations for my game programming pages. In the past I had created bitmap diagrams using Gimp or by writing custom code. This time I'm using Inkscape, which produces SVG, in the hopes that I can directly embed SVG onto the web page.

Unfortunately browser support for SVG stinks.

First, not all browsers support SVG. So you need a fallback. That's fine; I can produce PNGs with Inkscape.

Second, there's the question of whether to use <embed> or <object> tags. The answer seems to be that <object> is the “right” answer, but it crashes Safari 1.0. So I should use <embed>, right? I would, except <embed> doesn't support fallbacks.

This means that I to support browsers without SVG (by using PNG fallbacks), I have to crash the Safari browser. Ugh.

Even if that problem is solved, the next problem is that different SVG implementations support different features. Adobe's SVG plugin, Mozilla/Firefox SVG, and Opera SVG are all different. Even the very simple SVG I wrote does not work the same on all three. Opera does not seem to support text at all.

Browser vendors: it's worse to have limited SVG support than no support. With no support, the fallback will be used, and the reader will see something useful. With limited support, the reader will get a broken diagram.

Even if browsers supported SVG, the web server I use does not use the correct MIME type. It sends text/xml instead of image/svg+xml. I'm not sure how much this matters in practice though. (Side note: I find it interesting the change from text to image. This is going to generally be a confusing point with XML, since it's text underneath, but the rendering of it may not be.)

I have decided not to embed SVG on my pages (although I might link to it). I will turn SVG into PNG and embed PNG on my pages.

Black and White 2 AI

2005-12-12T19:55:00.000-08:00

I played Black and White 2 for many hours yesterday. The computer player and I were in a stalemate. The computer kept sending armies against me and I kept defeating them. I had built my town with walls around it, and then put archers on top of the walls. I was building up my strength while defending myself, in preparation for a big attack. I felt pretty safe.

After around 40 attacks, I realized that they weren't all the same. The computer wasn't using the same attackers each time. It tried the creature, archers, swordsmen, and catapults. It tried combinations of them. Sometimes it would come through my main entrance, and sometimes it would come around the back entrance to the city. The computer player also destroyed major sections of the city using the “earthquake” power, but I recovered from these too. After a while the enemy creature figured out that he should kick my wall in. His archers and swordsmen stayed back, out of range, while the creature came up and destroyed my wall, including the archers on it. After it breached the wall, the army swarmed into my town and killed half my people.

I rebuilt my wall and started to recover, but the computer's newly discovered strategy worked well. It tried several variants but kept going back to the same approach: kick down the wall, then swarm the town. This forced me to try some new strategies. Although being on the wall has advantages, it leaves the archers vulnerable when the enemy creature attacks the wall. So I moved them behind the wall. I've also learned to open my gate, wait for the enemy army to get close, then close the gate and set their army on fire. I have no good strategy for the creature knocking down my wall though, and I'm constantly losing townspeople and then rebuilding.

After a long stalemate, the computer AI learned how to attack more effectively, and now I'm having trouble keeping my city safe. I'm very impressed by the AI. I'm not sure how it's programmed, but it tried out many different things and learned which ones work the best. From the game AI techniques I've learned (genetic algorithms, neural networks, fuzzy logic, state machines, etc.), the AI in Black and White 2 seems to match most closely with what I know about reinforcement learning. It's a technique that uses online learning (observing results as the game is played) instead of training (from examples constructed ahead of time), allows both exploration (trying new things in order to learn) and exploitation (taking advantage of what you've learned), and associates rewards (like whether the attack was successful) with actions (like kicking down the wall and keeping the army away from my archers). I recommend Sutton and Barto's book if you want to learn more. It's entirely possible though that the game uses something much simpler that just happens to look impressive, but my guess is that it's using reinforcement learning.

3D Game development

2005-08-20T08:56:00.000-07:00

My game programming page contains information about platform-independent game programming topics, but when I actually write a game I need to combine that with platform-specific code. These days I use either PyGame, Java2D, or OpenGL. My favorite OpenGL resources over the last six months have been:

CodeSampler, which contains lots of examples of OpenGL code to do various things like textures, shaders, transparency, and lighting.
NeHe's Tutorials, which covers similar topics.
Gamedev.net OpenGL Articles, which includes a few random topics. Unfortunately most of the Graphics articles on GameDev are old and obsolete; they teach you how to implement algorithms that are already implemented in hardware these days.
FlipCode's Featured Articles cover many graphics-related topics but do not focus too much on OpenGL.

In addition, I've been reading Dave Eberley's Game Physics and Van Verth's Essential Mathematics for Games & Interactive Applications. These books are not primarily about graphics; they are about representing objects in 3D, manipulating them, etc. I also took a look at Stahler's Beginning Math and Physics for Game Programmers but didn't like it as much.

Water simulation

2005-07-10T08:50:00.000-07:00

One of the most fun things about SimBlob is the water simulation. It isn't great though, and I keep looking for ways to make it better. Using the Navier-Stokes equations is the “right” way to simulate fluids, but they're complicated and expensive, so many people have come up with approximations or alternatives. Here are some resources:

Fluid Dynamics Model (includes demo for Windows)
Fluid Dynamics with Erosion
Real-Time Fluid Dynamics for Games
Reflections on Water Simulation
Practical Animation of Liquids

None of their solutions directly works for me, since I'm using a hexagonal grid and have a dynamic landscape underneath the water.

[2005-07-11] Update: I tried some approaches based on the above, but they didn't work for me. It's quite possible that I'm missing an essential step in my simplification.

SimBlob 2, now for Mac

2005-07-10T08:35:00.000-07:00

I've added a Mac makefile to the download, but I haven't tested it myself. The main changes involved file paths. On Linux and Windows, OpenGL is #include <GL/gl.h>; on the Mac, it's #include <OpenGL/gl.h>. On Linux and Windows, GLUT is #include <GL/glut.h>; on Mac it's #include <GLUT/glut.h>. I admit that the Mac directory names make more sense, but it's annoying given that the include has been GL/gl.h for a decade on other systems. The other change involved the linker options; you have to specify a -framework. Thanks to my friend Richard T for figuring all of this out.

SimBlob 2, now for Windows

2005-07-03T20:29:00.000-07:00

When I started working on Simblob 2 back in 2002, I decided to use OpenGL and GLUT. Even though I was developing in Linux, I didn't want to end up in the situation I had with Simblob 1, which only works in OS/2. I finally took advantage of the portable libraries for SimBlob 2 and got it running on my new computer, which runs Windows XP.

I use Cygwin in Windows, so the Unix level libraries are fairly similar. The main difference was that the paths are different. In Linux, I used -lglut -lGLU -lGL, and the compiler was able to find all the headers and libraries. To make it run in Windows/Cygwin, I changed it to -I/usr/include/w32api -L/lib/w32api -lglut32 -lglu32 -lopengl32. Also, glext.h wasn't automatically included, so I had to insert #include <GL/glext.h>. In addition, the multitexturing functions (glActiveTextureARB, glClientActiveTextureARB, and glMultiTexCoord2fARB) don't seem to exist on my system, so I worked around that by using a single texture instead. I'll figure that one out later. I might need to use wglGetProcAddress to get those functions (unfortunately that function is Windows specific).

The one remaining problem I'm having is that when I quit the program by closing the window, GLUT's main loop doesn't exit. It instead starts eating up 100% of the CPU and never terminates. I'm not yet sure if this is a GLUT issue or a Cygwin issue. My workaround is to use Ctrl-C to exit instead of closing the window.

At the moment Simblob depends on Cygwin. You can't just run the Simblob executable; you have to have Cygwin installed. I'd like to try using the MingW option (gcc -mno-cygwin); I just need to remove some other dependencies on Unix libraries first.

I should probably spend some time learning autoconf or some other tools that help manage builds on multiple platforms.

I don't have a Mac handy, but it shouldn't be too hard to make Simblob 2 work on a Mac.

Games in Javascript

2005-07-02T08:32:00.000-07:00

A few weeks ago Google Maps got me thinking about writing simple games in Javascript. In particular, how much of The Silver Kingdoms could I implement in a browser? If I drop the terrain and make it a 2D overhead game (or possibly isometric, but that might be harder to implement), what I would need from the browser is (a) AJAX support (so the simulation can run on a server and send updates to the browser) and (b) transparent overlays for sprites. There are some nice advantages of writing in a browser. The basic graphics code is already there (image display, animation, positioning, layering) and the basic UI code is already there (mapping clicks to objects, overlapping windows, form controls). The real question is whether it's feasible—can the browser smoothly animate lots of sprites on the screen at once?

A few days later I read that someone had created a Star Wars hack on top of Google Maps. And then I saw someone had created an animated Microsoft campus invasion hack. There's now a wiki page with a list of Google Map hack game ideas.

There are only 9 sprites on the animated invasion hack, but it feels rather choppy. I'm not sure if this is a browser issue, an issue with the demo, or an issue with the Google Maps API. If it's a browser issue then it's unlikely that any nice games are going to be written on top of Google Maps. If it's a Maps issue, then a game using its own map might be feasible.

Some links I've collected while looking for ways to implement a simple game (SimCity-ish) in Javascript:

Examples for drag and drop of objects in Javascript
A drag and drop map, like Google Maps, but with your own maps
A description of the canvas element in Firefox 1.1 and Safari, which could be used for drawing graphics in the browser
A library for special effects in Javascript (including drag and drop)

I hadn't been considering using Google Maps itself, because a SimCityish game where you can't actually modify the city would be boring. I think it might be feasible to build a war or transportation game on top of Google Maps, but the game would need some notion of what the objects on the map are, and that might take some image recognition heuristics. It's unlikely I'll actually implement a real game this way, but I might try a little demo game.

Update [2005-12-16]: Take a look at this game.

Guild Wars Friendliness

2005-06-19T08:29:00.000-07:00

There's something about Guild Wars that I don't see mentioned much: it has a very friendly interface that encourages casual play.

The CD doesn't have to be in the drive. When I'm thinking of playing, I don't need to take the previous CD out of the drive, put the Guild Wars CD in, and then start the game. I can just start the game right away. Since it's no hassle, I play a lot more.
When I start the game, it goes right to the login prompt. No publisher splash screen. No developer splash screen. No video card maker splash screen. No sound library splash screen. No introductory movie. No copyright screen. No disclaimer screen. No menu. No loading progress bar. It's really quick and easy to get into the game. This encourages me to play more.
While you're playing the game there are Minimize, Maximize, Close buttons at the top right corner. This lets you easily switch to another application or run the game in windowed mode or just stop playing. It acts much more like a standard application, and it's very smooth. I feel like I can play at any time, and then switch back to whatever I was doing.

All of these seem very minor but I think they add up to something big: I'm playing Guild Wars a lot (over 200 hours). I wish all games would be this way.

Guild Wars

2005-05-04T08:59:00.000-07:00

After playing Neverwinter Nights for a few months, I got tired of it. I played the main campaigns and enjoyed them. The problem is that the mods are much harder to deal with than they should be. It takes a lot of effort to find mods that you can play (level restrictions, number of players, good ratings, etc.). It then takes more effort than it should to download and install them. They come in ZIP, EXE, and RAR formats. They come with multiple files, each of which may have to be put into a different folder. Bioware could have made mods easier by keeping all the mod files in a single folder and by standardizing on the distribution format. For example, if the game could read ZIP files, you could just download the file and put it in a particular folder and it would be ready, without unpacking it. In any case, the main problem I had was that it was hard for me to find and try out mods, so I didn't try many, and I didn't find many that I liked.

I've been playing Guild Wars this week (22 hours so far). This is an action RPG, much like Diablo, but it also has more quests. One thing that struck me was that Diablo 2 wasn't considered an MMORPG, but Guild Wars sometimes is, and the two games aren't substantially different in that respect.

Diablo 2 lets you play offline (one player) or online (one or multiple players). Guild Wars lets you play online only. This seems like a good idea. If you know that everyone's online, you can have a much quicker update cycle (those of you who waited over a year for the 1.09 Diablo 2 patch know why this matters). So far I've had 3 small updates in 4 days. Requiring online play also means you can learn how people play and make game balance adjustments frequently.

Diablo 2, in online mode, puts you in one of many chat rooms. The main purposes of this room are to chat, to find people to play with, and to trade. There are several chat rooms (presumably to avoid overcrowding), including some specifically for trading. When joining a game, you see a list of games that are at your level (Normal/Nightmare/Hell). People generally want to find a game that's not only at their level but in the same general areas. They sometimes do this by announcing their area (“Act III - Staff quest”) in the game name, but there's no easy way to filter or sort the games to find the areas you care about. Once you join a game, you don't see everyone anymore; you only see your party. Every time you join a game, the world resets—all the monsters are back, and the layout is randomized. When you leave a game, you abandon your party.

Guild Wars feels like an MMORPG because it puts you into the game right away. You're in a city, with lots of other people around, and you can see everyone walking around, talking, getting quests, etc. But these cities are essentially chat rooms. Their main purpose is for people to chat, find people to play with, and trade. Once you join a party and go out to play the game, you don't see everyone anymore; you only see your party. Every time you go out, the world resets—all the monsters are back (but the layout is not randomzied as it was in Diablo). When teleport into a city, you abandon your party.

There are of course other differences. In Diablo, you can only get quests once you go into the game. In Guild Wars, you can get quests in the chat area (cities). Since a party may want to go into a city to get quests, the party is not broken up if you walk into a city; it's only broken up if you teleport. In Diablo, if you want to trade with someone, you find them in the chat room and then you have to create a game to trade with them. In Guild Wars, if you want to trade with someone, you can trade with them in the city where you met them; there's no need to go anywhere. Also, Guild Wars has a special trading chat channel. You can tune in to both the regular and the trading channel; you don't have to go somewhere to find the traders. Guild Wars also makes it easier to find a party or to play PvP.

Why does Guild Wars keep the Diablo-style chat vs. game area distinction? I think it's for efficiency. Chat areas handle hundreds of people; game areas handle up to four. Chat areas are easier to make efficient because you don't need strict ordering of events. If you say something and I say something at roughly the same time, it doesn't matter so much which is heard first. And it doesn't matter so much if it takes 250 ms to show up. If you attack someone and I attack someone at the same time, it matters a great deal which one occurred first, and it needs to be decided and sent to all clients much quicker than 250 ms. By segregating the chat (lots of clients, loose ordering of events, high latency) and the game (few clients, strict ordering of events, low latency), you can make both efficient. If you tried to combine the two, you open up a new hard problem: what happens when you have lots of clients and you need low latency? Trying to tackle that rare but important case makes your life as a game developer more difficult. You're spending less time on other things that may have mattered more to the players.

Another thing that Guild Wars doesn't handle is massive persistence. You can only drop items in the game areas, not the chat areas. So if you drop an item, it only has to be seen by a few other clients, and it goes away as soon as you enter a city. That way you don't need to coordinate item locations among tens of thousands of clients. You can assign each city area and each game area to a separate server. Since city and game servers keep no state, you can add more servers transparently. You don't have to require players to choose a server ahead of time and then find that they can't play with their friends, who happen to live on a different server.

So far I've been really impressed with what I can infer of the design of Guild Wars. It's fast, has great graphics, and lots of fun. It's an incredibly addictive game.

Product placement and games

2004-12-04T08:52:00.000-08:00

Product Placement is a way to get your product seen without using traditional advertising. I think product placement could be used for market research too. Imagine an online game that doesn’t offer only Coca-Cola (product placement), but offers lots of drinks. You could then correlate the choice of drinks with demographic information you have about your gamers—age, gender, income, and so on. By watching activities within the game, you could correlate the choice of drinks with MUD personality types (Killers, Achievers, Socializers, Explorers); this might tell you what kinds of magazines you want to advertise in. You could see whether people who hang out together are more likely to drink the same sorts of drinks (energy boosters, soda, water, juices, etc.). You could pay some people to switch drinks and see whether others follow. You can measure correlations between products (do people who drink Red Bull also eat hamburgers?).

Does this creep you out? It should (unless you work in marketing). Product placement is what we have now, but I think in the future we’ll have people using virtual worlds as a way to run experiments on us. In virtual worlds you can measure behavior better. There is of course the question of whether product choice and behavior in the virtual world differs from the physical world, but having detailed data about a million players can complement having sparse data about a few thousand survey participants. Given that games—unlike movies—let players choose what to do, product placement in games seems like a waste. Market research seems to me to be a much more valuable way to use that opportunity.

Playing characters in games

2004-11-13T10:51:00.000-08:00

It’s actually very interesting in The Sims how the pronouns change all the time. I’m sitting there playing the game and I’m talking about, "Oh, first I’m going to get a job, then I’m going to do this, then I’m going to do that." And then you know when the character starts disobeying me, all of a sudden I shift and say "Oh, Why won’t he do that?" or "What’s he doing now?" And so at some point it’s me kind of inhabiting this little person, and I’m thinking, "It’s me, I’m going to get a job and I’m going to do x, y, and z." But then when he starts rebelling, it’s he. And so then I kind of jump out of him, and now it’s me vs. him. You know what I’m saying?

— from Celia Pearce’s interview with Will Wright

Road building applet

2004-10-31T21:29:00.000-08:00

A few months ago I had been thinking about a UI for building roads and rails. When I got Locomotion, I found that the building UI was a little bit annoying, and that inspired me to work on my UI some more. I tried Flash but couldn't find a free and easy way to get started, so I turned to Java instead. The Java documentation on Sun’s site is nice. For example, take a look at their Java 2D documentation.

After playing with it for half a day, I have an applet that lets me build roads. One of the most confusing things was figuring out how to write <object> and <applet>. Ick. (Let me know if it doesn’t work for you.)

This browser does not have a Java Plug-in.
Get the latest Java Plug-in here.

The basic idea is that roads (or rails) should be between edges, not tiles. Road segments are cubic splines between two edges. It’s a little tricky to select the right edge; I need to think about that problem a little bit more. There’s a larger version on my other page.

This building UI isn’t directly usable for games like Locomotion. It would need length and angle constraints, diagonals, bridges, and tunnels. To make it more usable, I need to add pathfinding, so that you can drag across the grid and it will figure out which segments need to be built. I will probably get bored before finishing all of that, though.

Web languages: Java

2004-10-30T23:58:00.000-07:00

Given my failure to get started writing Flash code, I decided to try Java. I downloaded Java 5.0 (which comes after 1.4, believe it or not) and Eclipse 3.0. Both of those sites need to have a much easier way to download the software. Java led me down a maze of multiple versions, marketing material, and legalese. Eclipse led me to a page of international mirrors, none of them useful (when I clicked on them, I got a big file listing and had no idea what I needed to download).

Despite some glitches (like some dialog boxes being blank and some being far wider than the screen), I got a simple applet running. My next step is to learn how to draw lines on the screen so that I can start creating a small isometric map. After that I need to learn how mouse events work so that I can let the player select tiles on the map.

The main disadvantages of Java compared to Flash are: it’s not as widespread, and it appears to be a more verbose and cumbersome language. I'd really like to do something with Java3D, but it looks like that is not installed by default on anyone’s machine. I just installed Java and I don’t have Java3D. I don’t want to ask my readers to install new software just to look at my demos. I think Java3D would be much more popular if it were installed by default.

Update: I’m not the only one who had trouble downloading Eclipse.