Blobs in Games

From Red Blob Games's Blog

Simple map generation #

Update [2016] I have an updated interactive version of this technique here, with sample code.

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).

Labels: maps , project

Flash 10: drawTriangles() disappointments #

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:

1. (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.
2. (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.
3. (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:

1. 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.
2. 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).
3. 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.
4. 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:

1. A Bitmap object.
2. A polygon drawn with beginBitmapFill.
3. A Bitmap object rotated 90 degrees clockwise.
4. A polygon drawn with beginBitmapFill, rotated 90 degrees.
5. Two triangles drawn with drawTriangles, and u/v range from 0 to 1.
6. Same as 5, except u/v adjusted by 1/64.
7. Same as 5, rotated 90 degrees.
8. 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.

Labels: flash

Parallel World Simulation #

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:

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

Labels: design , ideas

Storytelling with Comics #

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:

1. 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?

2. I played Passage, a game that represents time as a spatial dimension.

3. 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?

4. 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.

5. 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.

Update: [2012-04-02] See Storyteller, an interesting experimental game that's based on directly manipulating comic strips to build a story.

Update: [2017-03-08] Final Fantasy XV uses photos of significant events to tell a story.

Labels: ideas

Noise in game art #

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.

Labels: flash , noise

Switching to Flash 10 #

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: [2012-02] [2010-03] Flex 4 is out, and includes updated documentation, and downloadable documentation. Like Flex 3, it targets Flash 10 but can also be used for earlier versions of Flash.

Update: [2013-04] This seems to be the new command line Actionscript compiler, for Flash 11 / Stage3D / AIR.

Labels: flash , programming

Road representation #

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:

1. “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.

2. 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.

3. 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:

1. 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.

2. 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.

3. 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!)

4. 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.

5. 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.

6. 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.

7. 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.

Labels: project

Following multiple paths in RPGs #

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:

1. 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.

2. 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.

3. 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.

Labels: design , ideas

Throwing away code #

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.

Labels: programming

Transport Tycoon: modular airports #

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.

Update: [2012-08-18] There's a modular airport mod for Cities XL.

Update: [2019] It's ten years later and we now have some airport simulation games! Check out SimAirport and Airport CEO.

Labels: ideas