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?


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);
  (Vector.<int>([1, 2, 2, 2]),
   Vector.<Number>([100, 0, 164, 0, 164, 64, 100, 64]));

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();

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);
 (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]));

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.


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.


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:

8 test images showing various Flash drawing methods
  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).


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 #

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:

Side by side parallel universes

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: ,

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.


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:

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:

Test image without noise Test image 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);
                     0, 8, 7, true);
  var noise:Shape = new Shape();
  noise.graphics.drawRect(0, 0, size, size);
  layer.draw(noise, null, null, BlendMode.ADD);

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: ,

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: ,

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

    Road intersections can have varying numbers of lanes
    (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.

    Road drawn using Bezier curves

    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:

    Bezier offset curves can be a problem
    (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.


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:

class diagram showing specialization followed by generalization

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: ,

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.


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

Dimme's demo screenshot
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.


Animating stick figures #

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

Ninja walker test application

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 #

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:

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

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.

State diagram for mouse dragging

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:

Tradeoff between forward and rotational acceleration

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:

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

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

  3. Fly the ship around with W=forwards, S=backwards, A=rotate left, D=rotate right, Q=slide left, E=slide right, Z=reset position.

(screenshot of spaceship editor)
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.

Update: [2012-08-16] Another game that lets you design your own spaceships is Gimbal.

Update: [2012-10-15] Also see Evolving Spaceship Designs for Optimal Control and the Emergence of Interesting Behaviour [PDF], by Samuel A. Roberts and Simon M. Lucas, or watch the video.

Update: [2017-01-05] Another game that lets you design your own spaceships is Reassembly.

Update: [2019-09-17] Check out Cosmoteer, which lets you construct your own spaceships, and then the crew automatically figures out which thrusters to fire to go in the desired direction.

Labels: , ,

Game Component: Spaceship editor, part 3 #

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:

  1. Is it actually fun to fly a ship with this physics model?
  2. 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.

My spaceship flying around

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.

My spaceship flying around

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 K*V*V. 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.

Labels: , ,

Game Component: Spaceship editor, part 2 #

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 AD + WS 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.

Diagram of random output configurations

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!

I often work best when alternating between theory and practice.

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.

Diagram of restricted output configurations

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

Diagram of hypercube vertices

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.

Sometimes I work things out on paper

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, 28 is 256. Finding the one-zero outputs involved examining 215 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 28 pairs X 27 pairs to just 28 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.

Diagram of convex hulls

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.

Labels: , ,