Noise in game art #
If you look at the artwork in old 2D 8-bit games, you see a lot of noise and dithering in the hand-drawn bitmap art. For an example, take a look at the grass or concrete in this Transport Tycoon screenshot:
When the gaming world moved to 3D 32-bit vector art, we lost some of that level of detail. We got lots of smooth areas. Eventually we mostly got the detail back by applying textures to the polgons. However, it often looks worse to me than the old hand-drawn art.
With my Flash experiments, I've been playing with 2D procedural vector art, and I've been trying to figure out how to make it look nicer without drawing textures by hand. The simplest thing I found has been to apply noise to the art. On the left is some terrain without noise and on the right is some with noise:
I like the noisy version much better.
The noise layer is fairly easy to apply; I use BitmapData.noise() to
generate it, and then use BlendMode.ADD to add it to the original layer.
var noiseTexture:BitmapData = new BitmapData(128, 128);
noiseTexture.noise(Math.round(Math.random()*65536),
0, 8, 7, true);
var noise:Shape = new Shape();
noise.graphics.beginBitmapFill(noiseTexture);
noise.graphics.drawRect(0, 0, size, size);
noise.graphics.endFill();
layer.draw(noise, null, null, BlendMode.ADD);
noiseTexture.dispose();
It's nice in that it inherits the color already there; the noise doesn't impose its own colors. However, this only works nicely on my background terrain, and it feels somewhat slow on my low-end machine.
For foreground sprites, the noise layer doesn't move when those
sprites move or rotate. An alternative would be to draw the noise on
top of my sprites, using Graphics.beginBitmapFill(), but that would
require that I have a way to compute the outline of my procedural art,
so that I can draw the noise on top as a polygon. Another alternative
would be to use bitmap fills for every polygon, but that requires that
I have a noise bitmap for each color. And yet another alternative is
to draw every polygon twice, once for the color and once for the
noise.
With Flash 10 I had hoped that the pixel
shaders would allow
me to apply noise to anything. I played around with them a bit. The shader
receives the output coordinates in a function outCoord(), and can
compute a color for that location. It can optionally include
parameters (like a noise bitmap). The big problem is that the output
coordinates are in screen space. This means that when the sprite
moves or rotates, or if you zoom in, the noise would stay fixed
relative to the screen. I tried both using shaders for fills and
shaders for filters, and neither gave me what I wanted.
That's a serious problem for my use. To address this problem, I can pass in additional parameters like rotation and offset. However, I have to re-fill the shape every time I change the shader parameters. Even worse, the pixel shader is recompiled every time you fill.
So it looks like pixel shaders in Flash 10 just don't do what I want. I want a way to get the pixel's location in the sprite's coordinate system, after transforms are applied, but instead I only get the screen's coordinate system.
I think my best bet for performance is to not apply noise to vector backgrounds (applying noise to a bitmap won't impact performance). This will make me sad but smoothness matters a great deal. I should also try using tiles to see if that is any faster. For foreground objects, it's probably not too bad to draw everything twice, but I'll have to test this. It may not matter if I switch to bitmap sprites eventually; they'd let me draw a lot more details.
Switching to Flash 10 #
On this blog you can see some of the experiments I've been playing with. In 2004, I started looking at Flash, mostly because I'd be able to share my experiments on the web. But at the time, Flash wasn't as free or accessible, and I switched to Java. Dissatisfied with Java, I took a look at Flash again, and started writing Flash 8 code. Two years ago I switched from Flash 8 to Flash 9. Flash 9's language (Actionscript 3) is much nicer than Flash 8's language (Actionscript 2). It's a modern programming language, with classes, objects, closures, recursion, XML, JSON, etc., and was tracking ECMAscript until the Javascript folk changed direction. Flash 9's graphics libraries are nicer than Flash 8's. It supports a tree of layers, each with its own rotation, scaling, alpha transparency, shadows, and other effects.
Flash 10 uses the same language as Flash 9. Its libraries have lots more features, especially in the graphics system. There's now a low-level graphics API that offers partial 3D, higher performance, and pixel shaders. I was slow to move to Flash 9 in part because the adoption of Flash 9 was slow. It looks like Flash now has auto-updating, and Flash 10 is being installed much more widely. I'm switching all my current projects to Flash 10.
For Flash 10 I'm using the free Flex 3.3 SDK and the Flex
3.3 docs (online or download). The
SDK comes with a command line compiler, mxmlc, that I run
with mxmlc -target-player 10 on the “main” program, and
that will also compile anything else that is used by the main
class. If you want a tutorial for using mxmlc, see
senoular's mxmlc beginner
guide.
Flex also comes with a compilation shell, fcsh, that lets
you keep the compiler in memory to avoid the 2 seconds to start it up
every time you want to recompile. I wrote a wrapper around this so
that whenever I save something in Emacs, it automatically recompiles.
That way, my development cycle is: edit, save, and reload in the
browser. It's quite nice to have a fast cycle.
I haven't played much with the Flash 10 library additions, but the first thing I used was the bitmap line support. I'm using it to draw dashed lines as striped lane dividers. I plan to read about the new library features, but not try them until I find a possible use for them in my projects.
Update: [2012-02] [2010-03] Flex 4 is out, and includes updated documentation, and downloadable documentation. Like Flex 3, it targets Flash 10 but can also be used for earlier versions of Flash.
Update: [2013-04] This seems to be the new command line Actionscript compiler, for Flash 11 / Stage3D / AIR.
Labels: flash , programming
Road representation #
Playing Transport Tycoon, I've recently been setting up multimodal transport, where a bus will transport passengers from the bus stop in the middle of town to the train station outside of town (because once the towns in Transport Tycoon get big, it's hard to buy up enough land to build a train station or airport). The trains then take people to the nearby airport, which is even farther away from town for noise and space reasons. It would be fun to design those airports yourself, but Transport Tycoon gives you only a few rectangular predesigned airports.
The real trouble with playing Transport Tycoon is that it makes me want to write a transportation game. I'm too busy to work on a full game right now, but I want to experiment with small pieces of games. I thought it'd be fun to design container ports that mix truck, train, and ship traffic. While trying to break that down into smaller problems, I decided to work on roads: representing them, simulating vehicle movement, and drawing them. Someone asked me: why use grids? I love grids. I think a lot about grids. Even when I used splines for roads, the endpoints were on grid edges. I recently updated my A* pages about non-grid maps, and it seems like this project would be a good fit for a non-grid representation.
As I mentioned in the last post, I'm trying things quickly and am happy to throw them away if they don't work out. I'm now on the fourth design, which uses a two-level graph structure. The first graph is used by the player to edit the world. You'll place nodes and then connect them with edges. The second graph is used by pathfinding for vehicles to move along lanes. Each connection point generates one node per lane. Intersections export edges corresponding to all the ways a truck can go straight or turn, and roads export edges for going straight and for changing lanes. The rough plan is to have three kinds of objects:
“Anchor” objects like intersections and truck stops export connection points. The anchors act like nodes in the first graph and generate edges in the second graph. For example, a 4-way intersection will export 4 connection points.
Connection points have a position, orientation, and lane configuration. They don't show up in the first graph but generate nodes in the second graph. The lane configuration is the number of lanes in each direction. For example, a connection point might specify 2 lanes going one way and 1 lane going the other way.
Roads are attached to existing connection points and can follow a spline curve. Roads do not export their own connection points, but only can attach to anchor objects. They act as edges in the first graph and generate edges in the second graph.
Unlike the previous three designs, in which I quickly ran into trouble, this design has held up for a few weeks, so that's a good sign. The subproblems are:
How do I represent connection points? I decided to keep the position, orientation, and the number of lanes going into and coming out of the anchor object. It's a very simple struct and it'll be easy to change.
How do I represent intersections? I've limited myself to 4-way straight intersections (90 degree turns). Each side can have its own in/out lane configuration.
How do I draw intersections? For roads, there's a double yellow line in the center, a dashed white line between lanes going the same direction, and a solid white line on the side. There's a stop line where vehicles come to a stop. If there are right-only and left-only turn lanes, then there will be solid white lines separating those (not implemented yet). There may be arrows drawn to show which ways a vehicle can turn (not implemented yet). The size of the intersection itself is a rectangle as small as possible (not implemented yet).
(Try the demo!)How do I represent roads? I'd normally say cubic splines. However, since Flash supports drawing quadratic Bezier curves, it'd be nice if I could draw the roads using Flash instead of implementing my own curve rendering, so I'm going to use a spline with quadratic Beziers. There are ways to approximate cubics with quadratics but I'll see how far I get with quadratics alone. The lane configuration at the ends of the roads is determine by the anchor points, and the road handles the change in configuration. It might even be useful to have a lane configuration at each spline handle.
How do I draw roads? The roads again have the same yellow and white stripes as in intersections. However, this is where I ran into some trouble. I want the lane stripes to be parallel. This is done by taking the original curve and constructing an “offset curve”. Unfortunately, offsets of Bezier curves are not Bezier!
This could be a major problem. The more I dug into this problem, the more papers I found. It turns out that it affects various industries use Bezier curves (not only quadratic) for representing curves, and they use approximations for offset curves. I found papers mentioning circular arcs, Pythagorean hodograph curves, Hausdorff distance, and a few other things, but in the end I decided that what mattered was not whether the curve is exactly correct but whether it looks reasonable.
I drew the Bezier curve and the constructed somewhat-parallel Bezier curves, and it turns out it looks okay at low curvatures but not high curvatures:
(Try this demo.)I think it'll be reasonable to restrict the curvature of the road, and then I can use Flash for drawing the roads and lane markers. A new problem arose: although Flash 10 allows bitmap line drawing (this is how I draw the “dashed” lane divider lines), the bitmap orientation is fixed and does not curve as the line does. I'm not yet sure how much of a problem this will be.
How do I move along roads? With Bezier curves, the movement isn't uniform; I need to adjust for arc length. Most likely I'll turn each lane path into a series of points, and then move linearly between them. If that doesn't look good then I'll try something else.
One thing I'm considering is using circular arcs instead of Bezier curves. Arcs are fairly easy to understand and have simple movement. Offset curves from circular arcs are also arcs. Also, arcs are commonly used in real roads. Arcs can be approximated with Bezier curves.
How do I handle collisions? Open Transport Tycoon's “path based signals” have vehicles reserve the path ahead of them. Grids make this easier because you can reserve grid spaces (although OTTD is a little smarter than this and can allocate half-grids). Without grids, I could either precompute all intersecting road segments and mark them all occupied whenever one of them is reserved, or I could use polygon intersection to watch for vehicles colliding. The first approach uses planning; the second is purely reactive. I think a reactive system would lead to traffic jams.
Road representation turns out to be a fun problem. As the code stabilizes, I'm pushing it out to github and I'll put demos into the wiki. It's all under the MIT license so feel free to use it for anything. My next step is to determine how the roads and anchors connect to each other. That problem may help me decide on Bezier curves vs. arcs.
Labels: project
Following multiple paths in RPGs #
Last year at GDC I was talking to the Wild Shadow Studios guys about traditional classes in fantasy RPGs (ranger, wizard, barbarian, cleric, etc.). Some of our complaints about classes in many multiplayer RPGs:
Classes come with roles such as “tank”, “healer”, “ranged”, “melee”, “crowd control”, etc. If you want to join a group that needs a tank, but your class is about melee damage, you can't join the group.
The beginning of the game is a bad time to choose a class, which impacts you for the entire game. It's too early in the game to know what style of play you might like or what kind of roles are needed/useful. By the time you can make this decision it's too late; you've already invested lots of time into the game. Either you throw all that away or you keep playing the class that's not best for you.
Every class's play style can be considered “content”, and by choosing just one the player is missing out on other styles of play. As a game developer, if you have 5 classes, and players only play one of these on average, you're spending a lot of money on “content” that most players won't see, especially if armor/weapons are written for just a few classes in mind.
In Diablo 2, you picked a class but you could also customize that class by choosing skills as you level up. For example, Barbarians could choose skills such as Taunt or Double Swing. The skills had level requirements and prerequisites; for example, Double Swing was only available if you already had Bash. The trees were divided into three specialties per class; each of these effectively acts as a sub-class, so you had 15 styles of play instead of just 5 classes. The skills available to you were fairly limited at the beginning of the game, so you're not overwhelmed, and you don't have to make your choices at the beginning. This partially addresses complaint #2.
In Guild Wars and Titan Quest, you get to pick two classes. Multiclassing has been around since the D&D days, but these two games makes two classes the default and one class an option. Multiple classes can help with complaint #1, since everyone has two roles. It also helps with complaint #3, by adding lots of variety without having to create new content around it.
In Silverfall, World of Warcraft, and Titan Quest, I can change my skills later in the game, but not my class. WoW also has hybrid classes such as druid and shaman that can perform multiple roles. This also helps slightly with complaint #1, but it's quite a hassle. (Recently, WoW introduced “dual specs”, which help quite a bit by letting you set up two sets of skills that can be swapped with one button.) Being able to change my skills later greatly increased my desire to experiment. In Diablo 2, I would pick skills based on the recommendations of others. Decisions you can't change are more likely to be conservative. But in WoW, I am much more willing to try out new things, because I can undo them.
In Dungeon Siege II, there are skill trees but no classes. You essentially define your class by choosing skills along the way, but you don't have to decide anything at the beginning of the game. Titan Quest also delays the decision-making of your first and second classes. Either approach addresses complaint #2.
Another way to address all three complaints is to have more than one character, each one trying out a different class and play style. But when playing these characters, you start over from scratch.
What I'd like is (a) delaying decisions about classes/skills, and (b) allowing trying out other choices after I'm “finished” with my current class. So here's the idea: as you progress in the game, you are given choices of specialties. If you later master multiple specialties, you can become a generalist. Here's a diagram:
After you've played for a short time, you get to choose weaponry or magic. I choose weaponry. After playing more and leveling up with weaponry skills, I am able to specialize again, and I learn melee. After learning all the melee skills, I specialize in swords. After a few more levels, I am now fully specialized by mastering swords, and there's no more for me to learn. This is the equivalent of “level 80” in WoW.
At this point, it's time to try the branches I hadn't tried. This could either be by starting over with a new character at the novice level; or it could be by restoring a previous savegame where I was still at weaponry (playing a “clone” in a scifi setting), and choosing the ranged path instead; or it could be by using my current character to go back and learn ranged attacks. I don't know which of those approaches would be best for a game. In any case, I'm now trying out other play styles, just as with current RPGs.
Where this design differs is that there's something gained in-game by learning multiple specialties. This is the lower half of the diagram. If I master both the sword and axe, that unlocks the halberd. If I master both ice and death magic, it unlocks wizardry skills. By playing and mastering all types of characters, I become a Master.
An open question is how you handle the huge number of skills once you've pursued multiple paths. Titan Quest and Guild Wars limit your classes to two, so that it's not too bad. WoW lets you have two sets of skills, and you can swap back and forth at any time. Guild Wars further gives you a fixed number of skills at any time, and you can swap these out when you're in a major city. In a scifi setting, such as a robot or spaceship based game, you could assign the skills to the robot/vehicle you're in, and then jump into a different robot/vehicle to swap skills (Wild Shadow Studios is working on a tank-based MMO that does this). Choosing sets of skills before you go into combat seems like a reasonable way to limit the complexity, and also encourage planning ahead.
This skill graph addresses complaint #2: you don't have to make permanent choices at all, and the choices you make come after you've been playing the game for a bit. It also addresses #3: there's a path for the player to experience all the “content” the developers create. It partially addresses #1, by allowing you to play different roles at different times. Novice players can follow a recommended path to specialize in just one “class”, whereas experienced players can experiment more and try out new combinations. I think it could be fun to play with such a system, but I'm not planning to write an RPG any time soon.
Throwing away code #
I've been trying to get better at throwing away code. I used to be a packrat. I saved every receipt, every bill, every check, every bank statement, every page of notes I took in class, every textbook, and so on. Eventually I started letting go of most of these things. Class notes were the hardest though. I had put so much effort into them; how I could throw them out?
I realized that I was making the same mistake that I make with market prices. I expect prices to reflect the cost of making the item. But in many cases, prices reflect what it's worth to the buyer. In this case, I was saving my notes because they cost a lot to produce. But they don't have much value to me in terms of looking things up. I haven't used them in over ten years, and Wikipedia and other online sources are better references. So I finally threw away my class notes.
I find that I have the same problem with code. It takes effort to write, so I feel like I should save it. But sometimes it's the wrong code or it's solving the wrong problem. There are times when the best thing to do is to throw it away.
To make it easier to throw away code, I'm trying to reduce the cost of producing it, especially when I'm less sure about how long I'll need it or whether it's the right way to go. This is not only helpful for me psychologically, but I think it's the right thing to do engineering-wise. Note that this is the opposite of the conventional wisdom — that you should put lots of effort up front into “doing things right”, because it'll pay off later.
Keeping costs down recently paid off for me.
While playing Transport Tycoon a few weeks ago, I was thinking about modular airports, and how it related to my transportation mini-game that's on indefinite hold. I'm not working on any games right now, but instead working on little bits and pieces that might end up being part of a game. Or at the very least I'll learn a lot by working on these components. One of the open questions I've had when thinking about a transportation game is how I should represent roads and vehicles (or rails and trains). I sketched some ideas on paper, and then decided on a representation of road segments:
public class Path {
public var id:int;
public var next:int; // index
// Positions are in world coordinates, not Flash coordinates
public var beginPosition:Point;
public var beginOrientation:Point;
public var endPosition:Point;
public var endOrientation:Point;
public var length:Number;
public function Path(id_:int) {
id = id_;
}
}
I then set up some test segments and made vehicles go around on them:
I had convinced myself that inside an airport or container port, the vehicles could move around in loops, and that would be sufficient for a game. Even if I needed branching, I could change my Path class from having a single next pointer to multiple next pointers.
I was quite happy with the vehicle and road representation. I had a coordinate system that allowed vehicles to detect if someone's in front of them, and to slowly come to a stop before they collided. By using a loop I had eliminated the problem of start and end points.
A few days later I tried sketching out what the player would do. It turned out that there wasn't much. I spent some time thinking about why Transport Tycoon's station management was interesting, and my prototype was not, and realized that what's interesting is updating the station over time to deal with changes in the game world. If players spent most of their time on updates rather than initial design, the road shouldn't be a loop. It should support adding temporary routes, closing existing routes, demolishing routes, building new routes, and so on. Those operations work better with a completely different representation of roads. And that meant I should throw away my representation and associated code (rendering, etc.).
If you look at the class I wrote, it's trivial. Everything's public. There are no getters and setters, no methods, a trivial constructor, and no tests. I tried hard to follow YouArentGonnaNeedIt and DoTheSimplestThingThatCouldPossiblyWork. Throwing it away is easy, because there's so little work put into it. Having the old version saved in version control helps me feel okay with removing the code in the current version.
Although I'm throwing away code, there are some ideas I'm keeping. I learned some things, and the first approach is what got me thinking about the new approach. The process was valuable, even if the code was not. And I've started working on the next approach, which I'll try to keep as simple as the first one. I still have a packrat instinct, but I'm working on conquering it.
Labels: programming
Transport Tycoon: modular airports #
I have been playing Transport Tycoon for a long time. It's my all-time favorite game. TTDPatch is a very impressive set of patches for the game, adding lots of new features that seem like they would be impossible to implement in a patch, especially by authors who don't have access to the source code. Open Transport Tycoon is an open source port/recreation of the game, and it's what I've been playing lately.
In Transport Tycoon your goal is to build a transportation empire using buses, trucks, trains, airplanes, and ships. The part I find the most fun is laying out tracks, railroad stations, and train signals. I think most of the players spend most of their time on railroads for this reason. I think I would enjoy the airplane and ship parts of the game more if I had some control over layout. All you can build right now is 6 predefined rectangular airports and 1 ship dock.
For several years on the Open Transport Tycoon forums, there's been talk of “modular” airports that would allow players to place hangars, runways, taxiways, and gates to build their own airport. However, airports are implemented with finite state machines that carefully manage multiple airplanes in holding patterns, landing, taking off, taxiing, going to hangars, and stopping at gates. Richk67 has created an impressive patch for custom non-rectangular airports. However his experience has been that the finite state machines are just too complex for players, and his patch is instead aimed at people making addons. Pikka has an alternate proposal, but take a look at the example state machine code for the simple airport. That's way too complex to make players deal with. There have been others who have argued that it should be possible to let players do this, if the GUI was good enough. However, Richk67 actually wrote some code and implemented custom airports, whereas most of the posters are just talking about proposals or ideas, so I generally believe him when he says that the finite state machines are too complex for most players.
My hope however was that there would be a completely different
approach to airports that wouldn't involve the complex finite state
machines. Playing with path based
signals, a new feature
in OpenTTD 0.7.0, has made me more optimistic. With the signals in the
original Transport Tycoon, a train made a decision when it reached a
junction with signals. The third party patches added new kinds of
signals, including allowing complex logic in TTDPatch. Path-based
signals work quite differently. Trains reserve tracks ahead of them
and only proceed if they can make a reservation. Can we apply the same
idea to airports? Instead of following a fixed state machine, we might
be able to reserve space ahead of the airplane (landing flight space,
takeoff flight space, runways, taxiways). I had only just started
thinking about this problem when I came across Dimme's
demo of a
proposed player-created airport system using airplanes reserving space
they want to use. In the demo (a Java app), you can place gate,
runway, taxiway, and other tiles to build an airport, and then run a
simulation to see how the airplanes use it. It's quite impressive!
(Note: I couldn't get the jar file to run on the Mac so I had to
recompile it myself, but it ran fine.)
A station I made with Dimme's demo
Dimme's demo shows that there's a different way to build airports that may not lead to the same complexity as the finite state machines. MarkyParky, who works with airports in real life, has good things to say about Dimme's demo, but also talks about holding patterns, which turn out to be more complicated than I imagined. I don't think that realistic holding patterns are necessary but it's something to think about. In any case, I don't think any of the discussions are going to go anywhere. Richk67's patch is the only code I saw, and as far as I can tell, the main developers have rejected his patch. Dimme demonstrated an alternate approach but there's no proposal for how to make it work within the OpenTTD code.
Dimme's demo is good. It's simple to use, it demonstrates the idea, and it lets you actually try building an airport to see how it works. After playing with it, I decided I wouldn't build an airport building demo. I think my ideas aren't different enough to make it worth it. However, his demo reminded me that I should be building more demos of ideas I want to explore. Coming up with ideas doesn't teach me as much as trying them out.
Update: [2012-08-18] There's a modular airport mod for Cities XL.
Update: [2019] It's ten years later and we now have some airport simulation games! Check out SimAirport and Airport CEO.
Labels: ideas
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.]
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.
Labels: ideas
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:
- Make a triangle bitmap where the red, green, and blue components of the color correspond to the barycentric coordinates of that point in the triangle, scaled to 0–255 instead of 0–1. I only have to do this once.
- Make a gradient array for the three colors I want at the vertices. The gradient array is 256 elements and it's merely the red, green, and blue values scaled down. At position i I'll store the color scaled to i/255 brightness.
- Use
BitmapData.paletteMap()to map the red, green, and blue components to the scaled colors in my three gradient arrays. ThepaletteMap()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.
Labels: flash
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.
I made a circle that could be dragged around with Flash's built-in draggable object feature, but I switched to handling the mouse events myself, so that I could add "snap to angle" and other constraints. It wasn't long after having a draggable circle that I made a circle for each thruster. And then two, one for the head and one for the tail. I also wanted the thruster to move as a whole if you dragged the base, but only the tip to move if you dragged the end. I overlaid these on a large version of the ship to make a ship editor. Now I could start answering the key question: are there interesting design choices?
After playing around with lots of configurations my answer was no. It's always better to put the forward thrusters near the wingtips. You don't lose any forward thrust, and you gain a great deal of rotational speed. The other thrusters were less of an issue, because they were used for less common motions.
To make this interesting I need some disadvantage of putting forward thrusters at the tips. One thing I considered was that thrusters at the edges of your ship are more vulnerable to damage. However, I don't actually have a game here, so that's not something I can easily test. So I turned to the other idea: thrusters require support that have mass. Putting a thruster far from the center requires more massive supports, which slow you down. I started with mass and moment of inertia calculations from physics, and then used tuning and experimentation to come up with something that felt reasonable. The main tradeoff I focused on is between rotational and forward acceleration, when both are from the same forward thrusters. If you move the thrusters near the wingtips, you get lots of rotation, but you need a lot of mass for the structural supports, and that slows your forward acceleration. This plot shows acceleration versus thruster distance from the center:
It shows that at least for the forward thrusters, there's a nice tradeoff between rotational and forward acceleration, and you can't get unlimited rotational power because the supports become too massive. There are lots of other things I could look at, but I think some tradeoffs depend on the game (for example, they may be completely different if the ship is in an atmosphere than if it were in space), and I'm not writing a game right now.
I eventually recognized that I could keep working on this for a long time, but I need to move on and explore other topics. I've mostly answered the question I set out to answer: if you let the player design the spaceship, are there interesting tradeoffs arising from the physics? I think the answer is yes, but probably not as many interesting tradeoffs as Spore's approach would allow. In addition, things weren't automatically interesting; I had to design a tradeoff and then tune the physics to make that tradeoff show up, and I had to be careful to avoid overpowered ships. That was unsatisfying. In a real game I imagine I'd have to manually design lots of tradeoffs for different game levels or areas of the world, and it'd be quite tough to test all the combinations. And even if I could do that, controlling sliders in a continuous tradeoff space seems less fun than picking from some really interesting manually designed items in Spore or Ur-Quan Masters. So yes, I was able to make what I set out to make, and it was fun to play with, but probably would be a lot less work and more fun to give people a few interesting choices.
The Demo
Of course after all that I should let you try designing your own ships and see what you think. Instructions:
Press T to change ships (you may have to click on the map first to get focus). The demo ships are: yellow square (4 thrusters), green square (like yellow but you can make it asymmetric), teal curved, purple curved (like teal but two thrusters are broken, so it can't fly properly), blue square (8 thrusters!), red triangle (goes fast but can't turn well). I mostly play with the yellow and blue ships.
Change the ship by dragging the thrusters and adjusting their size and orientation. As you do this, watch the graphs. The bar charts show what happens if you press one key at a time. The polygons represent your current flight envelope for two keys at a time. I find that I use the W+A and W+D combinations often, so I watch the chart in the lower left. The shaded ovals show the "target" that you want to mostly cover if you want a reasonable ship. The yellow and blue ships are easy to improve: just increase the power of the thrusters and they will fly well. The teal and red ships are slightly harder, and the purple ship is near hopeless. In a real game the number and power of your thrusters would be limited, and fuel efficiency and fuel tank size would be additional factors to consider.
Fly the ship around with W=forwards, S=backwards, A=rotate left, D=rotate right, Q=slide left, E=slide right, Z=reset position.
Try the demo.
The demo is written with Flash 10 in mind. It should work with Flash 9 but there may be some visual artifacts (due to bugs in Flash 9 that I didn't work around). There are some other minor bugs that I might fix someday.
I'm finished with the spaceship editor mini-project and haven't decided what the next mini-project will be. I really enjoyed working on the spaceship physics and editor, but I spent too much time on it, and hope to spend less time on the next mini-project.
Update: [2009-12-05] If you want to try a game that lets you create your own spaceships, check out Captain Forever. It's pretty neat.
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.
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:
- Is it actually fun to fly a ship with this physics model?
- Is it actually fun to design a ship? In other words, are there interesting designs and tradeoffs?
Somewhere during the process I realized that getting the “nice” solution wasn't that important, and I had probably spent too much time on it. (Reading this article reminds me that I get distracted too easily on fun problems and I have trouble completing things.) I wasn't getting closer to answering the important questions. Instead, I was having fun learning some math that I had forgotten 15 years ago. Having fun learning math isn't bad; it's just not the main goal.
To answer the first question, I spent some time in various ships just flying around. My conclusion was yes, it's fun to fly around in a world by itself, but no, it doesn't seem like it'd be fun in an actual game, where there are other things to do. And that's when it hit me: all that time I spent thinking about the math might have been a waste of time (except that it was a lot of fun to learn some math); I should first make sure I can make the ships fun to fly.
I flew around a lot and thought about what bugged me. The main problem was that inertia was fun at first but it seemed to get annoying after a little while. For example, if I'm moving forwards with W, and then I rotate left with A, I'm still moving, but my jets are pointed at an angle. To stop moving you need to use a combination of S and Q. Even worse, since it's a keyboard instead of an analog controller, you can't hit the right mix of the two to make yourself stop.
In addition, it wasn't clear to me whether the controls should set acceleration, velocity, or target position. Acceleration was the most natural thing, and that's what I started with. But that means when you hit any key, you start out slow, then go faster and faster, until it's out of control. That might be realistic but it's not much fun. I switched it to setting velocity. But what velocity should I target? I arbitrarily chose some multiple K of the acceleration, so that after K time you'd reach that velocity.
I also needed to do more tuning. The mass, moment of inertia, friction, and rotation/translation tradeoffs are set arbitrarily. I had tried adjusting this but none of the parameters were quite right, and every time I changed the physics it got worse, and I had to tune to make it better again.
I tried to answer the second question (whether there are interesting ship tradeoffs) by creating several ships. Based on that experience, my answer is maybe. The ships I made are noticeably different but I have a clear favorite. If there's only one best ship then the ship editor's not going to be interesting. The problem is that the answer to the second question depends on what I do with the physics.
So I decided to work on the physics first.
I tried tackling inertia directly, with some ideas from a friend:
Inertia in World Coordinates gives me realistic physics for flying ships. This is what I had started with, and this is what I was unhappy with. When you're going north, and turn left, you keep flying north. The inertia keeps moving you north, even if you face west.
Inertia in Ship Coordinates gives me something that behaves more like a vehicle on wheels. When you're going north, and turn left, you start going west. The inertia keeps moving you forwards, whatever direction that may be.
No Inertia would mean that you only move when thrusters are fired. This is the most extreme change but if inertia is really a problem then it's worth a try.
I also tried treating rotation differently from x and y, because rotation seems to lead to some of the situations that make the ship less fun to control.
It was only after playing with the various options that I learned that I do really want inertia in world coordinates. Sometimes I just have to try something to help me learn something (also see this blog post). Having no inertia, or inertia in ship coordinates, just didn't feel fun to fly at all, and that's not what I would've predicted. I had the right form of inertia; something else was wrong.
After all the testing, I realized I wanted inertia but not the full effect. At low speeds, inertia is great, but at high speeds, inertia is less fun. With inertia alone it takes as long to speed up as it does to slow down again. It's okay if it takes a second or two to reach a high speed. But when I let go of the keys I want the ship to come to a stop pretty quickly. I added a force to slow the ship down. I tried three approaches:
Constant force decreases velocity V by up to K. This can be interpreted as surface friction.
Linear force decreases velocity V by K*V. I don't know what this might correspond to in physics, but in the calculations it corresponds to “reducing” inertia.
Quadratic force decreases velocity V by 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.