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