Blobs in Games

From Red Blob Games's Blog

Titan Quest #

I've been playing an old RPG^* called Titan Quest. Two word summary: Diablo Clone. Diablo 2 was lots of fun, and so is Titan Quest.

One thing that struck me about the game design is that it keeps the game simple at the very beginning. You start out as a generic character, wearing generic clothing. The only thing you have to decide at the beginning is your name and gender. Very simple. So simple in fact I thought I was missing something when I created my character. World of Warcraft, which also delays a lot of complexity (talents, spells, mounts, etc.) makes you choose race, class, and appearance at the beginning of the game. Titan Quest is … spartan (pun intended).

As with many games, as you fight, you gain equipment. Not unusual. But what is unusual is that all the equipment drops are what the monster was wearing at the time! The caveat is that equipment is often damaged during the fight, and what drops can be of lower quality than what it was wearing originally (or it could be so badly damaged it's not useful). I'm not sure if the damage level depends on the battle. I'm also not sure if this game mechanic adds much. The equipment also can be enhanced with “runes” (like Diablo 2), except the mechanics are different, and IMO more fun. You have two weapon sets, which allows you to play both ranged and melee, or have an alternate weapon for monsters that can resist your primary.

What's I really liked was the class/talent system. At every level, you gain skill points, which can be used either for advancing general knowledge of an area (a class), or for unlocking a new skill, or for improving a skill. Many skills can only be learned if you have a lot of knowledge in that area. My initial instinct was to get a few skills and improve them a lot, so they'd be supremely powerful skills. However, the strategy guides I've read online suggest that you're better off learning the general knowledge first, and then learning the higher level skills. So this gave me an interesting tradeoff: if I learn the general knowledge (which also gives me better stats), it's delaying my gaining skills. I might have a harder time now, but the payoff is that I'll get the more powerful skills sooner. (Side note: with the expansion pack you can pay to unlearn skills.) I've decided on a middle path: I picked a small number of skills to focus on, and spend the rest getting general knowledge. As with many RPGs, as you add skills, you get more options of play style, not only statically (in the choice of skills) but dynamically (in choosing how to use combinations).

In addition to the general knowledge vs. skill choice, Titan Quest also delays the introduction of classes by tying it to the skill system. You don't choose a class until level 2, when you have skill points, because you have to use those skill points to choose an area of study. At level 8, after you've been playing the game for a while, you get to choose a second area of study. So now we have over 30 class+class combinations, but you don't have to pick until you've gotten a feel for the game.

I've been quite happy not having to make so many choices at the very beginning of the game. When I first start playing, I don't have enough information to make that choice. That means I'm often going to make a bad choice. Delaying a choice not only reduces complexity as I'm learning the game, but it allows me to make better choices. I think Guild Wars and Dungeon Siege II do something similar with their class system. Titan Quest and World of Warcraft also allow you to unlearn skills, which means you can explore more styles of play without starting over from scratch. When penalties for making a wrong choice are reduced or eliminated, people take more risks. They explore more. They try more things, and have more fun.

Aside from the interesting class system, I think the game is mostly like Diablo 2, down to potions and portals and “acts” and economy. This is a good thing. The graphics are incredible, looking like hand-drawn 2D art, except it's actually 3D. I've been having lots of fun. Unfortunately, I don't think I'll play through a second time. Unlike Diablo, the maps are hand-drawn and not random. This makes it more enjoyable the first time and less enjoyable on subsequent plays. Also, it requires the CD in the drive, and having to swap CDs with whatever game I get next is a huge barrier. Still, I'm going to get ~50 hours of gameplay for $20, and I think that's a pretty good deal.

^*Update: [2008-07-31] Some people pointed out that there's not much “role playing” in this “role playing game”, and delaying choices may be less appropriate if it's a true role playing game.

Labels: review

Shifting Game Maps #

Game worlds are typically quite static, with some games allowing you to change the world, and even fewer allowing changes that affect movement in significant ways. One of the ideas I wanted to explore was to have the world change significantly, but the coordinate system keep the player in a “reasonable” place even while the world was changing under him. The game idea is that you are playing the role of a tiny ship inside a giant creature. As you traverse the blood vessels and shoot the white blood cells of the immune system, the creature becomes more agitated. As its heart beats faster, ripples run down the arteries, and the entire creature may start moving about. The game becomes more difficult not because the enemies are tougher, but because the world itself is changing and becoming somewhat disorienting.

Turn on animation to see some movement of the map.

The article about the demo goes into more detail about the code.

Labels: ideas , maps

Interactive A* Illustration #

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

Game Design: Decreasing costs over time #

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

Transport Tycoon #

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.

Interactive illustrations #

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

Update: [2011] - I wrote this post in 2007, when Flash was my best choice for interactive diagrams I could embed into a web page. Browsers have advanced quite a bit since then and I'm using HTML5 (SVG and Canvas) for most of my new interactive diagrams.

Labels: flash

Learning Flash 9 #

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] [2010-03-25] You can download the Flash command-line compiler (Flex mxmlc) 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

Distances on a triangular grid #

As part of my article on grids, I'd like to provide basic algorithms for grids. I already know how to compute distances on square and hexagon grids, but I didn't know how to compute them on a triangle grid. I initially tried changing coordinate systems, inspired by Charles Fu's coordinate system. I normally use the coordinate system from my article on grids:

The first coordinate (which I will call u) is the position along the horizontal axis; the second (which I call v) is the position along the southwest/northeast diagonal. The Left/Right parity introduces some compliation; I let R be 1 and L be 0. This coordinate system is nice for storing maps in an array, but it's not as clean, because triangle grids have three axes but only two of them are expressed in the coordinates. For the horizontal axis I used 2u+R as the position; for the second axis I used 2v+R. I guessed that the position along the third axis would u-v. I drew some grids on paper, wrote down the u,v values, and then computed the three positional values. They behave properly for computing distances along the third axis, but the system falls apart when computing distances not on the three axes.

Frustrated, I decided to step back and approach this problem in a more principled manner. In Charles Fu's three-axis coordinate system, taking one step in the grid changes two of the coordinates and leaves the third alone. For a triangle grid, the dominating feature is the straight lines in three directions. I looked on the web for any articles describing distances on triangular grids, but didn't find any that satisfied me. This paper was promising but unfortunately gives an iterative algorithm and not a clean formula. However, it uses an interesting coordinate system, which is useful for computing distances. If you take one step in the grid, you will cross exactly one line. The distance between two locations will be the number of lines you have to cross. I wanted to use a coordinate system in which crossing a line changes a coordinate:

I want to map the u,v,R coordinates I normally use into the alternate coordinate system a,b,c, where exactly one of a,b,c changes when you cross a line. Here's where I decided to use algebra. In u,v,R space, the black triangle has coordinates 0,0,0; the triangle to the east of it has coordinates 0,0,1; to the west, -1,0,1; to the south, 0,-1,1. In a,b,c space, the black triangle is 0,0,0; the east triangle is 0,0,1; the west triangle is 0,-1,0; and the south triangle is -1,0,0.

I want a formula that computes a, and I expect it to be linear, so I write a = au*u + av*v + aR*R + constant. That's four unknowns, but we know the constant will be 0, so it's really three unknowns. To get three equations, I plug in the values for the east, west, and south triangles, then solve for the coefficients. Let's see what happens:

  For each s in (a, b, c), and each triangle i:
  si = su*u + sv*v + sR*R

  East triangle: u,v,R = 0,0,1
  s1 = su*0 + sv*0 + sR*1
  therefore: sR = s1
  
  West triangle: u,v,R = -1,0,1
  s2 = su*-1 + sv*0 + sR*1
  therefore: su = sR - s2
  
  South triangle: u,v,R = 0,-1,1
  s3 = su*0 + sv*-1 + sR*1
  therefore: sv = sR - s3

When s is axis a, we look at a for triangles 1 (east), 2 (west), and 3 (south), so a1 is 0, a2 is 0, and a3 is -1. The algebra tells us that aR = 0, au = 0, and av = 1. That means the formula is a = v. Pretty simple. Doing the same for b and c, I get b = u and c = u + v + R.

These results are simple enough that if I played with the grid enough, I would have come up with them. However the algebraic approach works for other constraints, not only the simple ones. I also used it to create a coordinate system with 2u+v+R, u+2v+R, v-u (this is 30 degrees rotated from the one above), which may be useful for other algorithms. Algebra and calculus also come in handy for defining movements (e.g., splines), growth rates, equilibria in interacting systems, and other types of interesting behaviors in games.

What is the distance between two locations in a triangular grid? Each step involves a line crossing, and we want to count steps, so we add up the line crossings along each axis (a, b, c): distance = abs(Δu) + abs(Δv) + abs(Δ(u+v+R)). This looks just like the Manhattan distance formula, but for triangles instead of squares.

Labels: grids , math , triangles

Transportation mini-game, where is it? #

A few months ago I posted about a transportation mini-game I had started. What happened to it?

I've been a bit distracted and haven't worked on it much. I did learn some Flash, and posted about command line tools for Flash, and then I went to the Game Developer's Conference, which made me think about what kind of game I was working on.

The first comparison that came to mind was Lemmings. In Lemmings, a stream of lemmings is coming into the world, and your goal is to give a few lemmings a job. Jobs include digging through the ground, floating through the air, building steps, turning other lemmings around, etc. The lemmings with jobs affect how the rest of the lemmings move through the world. In the transportation mini-game, there is a stream of packages coming into the warehouse and your goal is to direct them to their goal. You place objects like conveyor belts to change the flow of packages. As with lemming jobs, there are a variety of objects you can use. However you don't use the packages themselves to do this, and there's no terrain to modify.

More recently I ran across a series of “tower defense” games, in which a stream of monsters is walking by and your goal is to shoot them. Just as there are many types of lemming jobs, there are a variety of guns that you can place on towers. The most interesting of these games is Desktop TD, in which the monsters have to walk around the towers you build. This adds a layer of strategy: where you place your towers matters a great deal because if affects how the monsters walk around them, and where the monsters walk affects where your towers should be. In this YouTube video, you can see an example of how you can arrange towers into a maze to force the monsters to take a convoluted path to their goal:

Desktop TD is a lot of fun. It combines a building game with a shooting game. The monsters have a pathfinding algorithm controlling them, and you have to think about how your buildings will affect the results of that algorithm. You also have to think about different kinds of monsters, different kinds of towers, and whether to upgrade existing towers or build new ones.

Unfortunately after playing it for many, many hours it made me less interested in my transportation mini-game. It satisfied my desire to play a game with flowing objects. I'd still like to work on this game but I've been busy with other projects and don't know when I'll get back to it. Maybe someone working on a tower defense clone will incorporate aspects of the transportation mini-game instead, and then I can spend many hours playing their game. ;)

Labels: project

Game Developer's Conference #

Despite the talk of GDC 2007 becoming more and more like E3, I'm going to go to GDC this year. I'm interested in the Wii, DS, mobile games, online games, and web games, as well as graphics, music, sound effects, design, algorithms, and storytelling. I'm interested in just about everything but business/legal aspects; I expect that working on games will remain just a hobby for me.