Blobs in Games

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

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

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

Labels: flash, grids

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

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

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

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

Labels: design

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Labels: flash

This week I switched from Flash 8 to Flash 9.

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

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

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

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

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

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

Labels: flash, programming, project