I haven't had the time and energy to work on a full game (the transportation game is on hold) but instead I'm playing with lots of little ideas, some of which turn into demos. This week's idea is to algorithmically generate layouts for space stations or space bases, so that they all look different. Originally I had a lot more variety in mind, but for the demo, I only implemented simple radial layouts:

(example radial space base layout)
(This is an example layout produced by the Flash demo)

I wrote some notes about the algorithm, the source code, and how to use this in a game.

Update: [2008-12-02] I forgot to mention my motivation: I was looking for something very simple that would compile to a small size and generate “programmer art”. The layout and rendering for this compiles to under 5k, and I'd guess that it could be under 3k for something more specialized. The small size and large variety makes this a reasonable thing to include in a browser-based game.

Labels: , ,

The brain is a complex organ with complex processing. But it's slow. Early AIs were written to explore the highest level of brain functions — things like planning, logic, natural language, creativity, problem solving, mathematics. Like the higher levels of the brain, solving these problems is slow. In game AI, planning and pathfinding are examples of the higher level processing, and these are often slow.

In the body, when fast reactions are needed, we have reflexes: a fast but dumb reaction that occurs before the brain can fully process and respond to a signal. The classic example is putting a hand on a hot potato – you will pull your hand away before the brain even receives the pain signal. Many reflexes are handled by the spinal cord, before the signals reach the brain.

The body has both:

  • A global slow, smart system: processing in the brain
  • A local fast, dumb system: reflexes closer to where the input occurred

In game AI we can often do the same. An example is in games where pathfinding is slow, and has to be split up among several frames. We need to give instant feedback to the player when the unit is clicked. If pathfinding is slow, then we need something else in its place. In some games, you'll see animation and sound for the unit getting ready to move. But the reflex-inspired approach would be to have a secondary pathfinding system that's fast and dumb, and have the unit start following that path right away. The most straightforward approach would be to start moving in a straight line; another approach would be to see if any nearby units are moving to the same general area, and start following them. The slow, smart system can fix the path later. In some cases you don't need the smart system at all because the dumb path is fine. That way, you can get both instantaneous action and good paths.

In planning tasks we also have places where reflexes can be useful. For example, suppose three different squads are attacked simultaneously. Their reflex action should be to fight back. In the background a slower processing task can analyze these three positions, the size of the attacking forces, and the information gathered from scouting. It can guess what the enemy is going to do next, and order all three squads to fall back to a safer position. Fire first, then fall back, instead of waiting for the analysis before performing any action.

Lots of games already use these techniques. They're part of a general pattern: use both slow/smart and fast/dumb event handlers, so that you can react quickly and then go back and react smartly in cases where you need it.


When I'm interacting with my computer, there's a range of interfaces I use. On the “high” end, there are full screen specialized UIs sometimes with specialized controllers. I have a highly customized World of Warcraft interface that's tuned for the special keyboard I got for playing games. These UIs typically use your full attention, and you don't do anything else on the computer at the same time. On the “low” end, there are simple interfaces that are usually text-based and line-at-a-time. Twitter and instant messaging let me send and receive short lines of text. These UIs typically use very little attention, and sit unobtrusively on the side while you do something else.

Most games I see are on the “high” end. They have specialized interfaces that you have to learn, and you're not often multitasking. Browser based games are somewhere in the middle. They're not using up the full screen, they have simpler UIs that fit with the browser's UI, and you can have other things going on at the same time, although you'll probably ignore them if the game requires your full attention.

For some kinds of games I think it would make sense to have multiple interfaces to the same game. Outside of games, you see examples like EBay, which has a main interface (through a web browser), some “rich client” applications that you can download, and mobile phone alerts. They all access the same database. You can get more out of the rich client, but it's not something you run all the time. You do have the mobile alerts on all the time, but you can't do very much with that interface. Also look at television shows like Lost or Heroes, which have a main “rich” interface through the TV show, but also expose other aspects of the show through their web site, novels, discussion forums, comic books, and games. The Matrix series of movies had other aspects of the storyline revealed in comics, anime, and video games.

What kinds of games would benefit from multiple clients? I think it's most useful in games that have interactions with other people. In these games, things can be going on when you're not playing. A lightweight client would be useful for finding out what's going on, and perhaps inducing you to play with the full interface. You already see notification of this sort in a very simple setting: play-by-email Chess or Go. There's the game itself, and there's a lightweight communication mechanism (email) that lets you find out what's going on. But I'd like to see this in a lot more games. For example, in Halo 3, it would be nice to see if my buddies are playing online. Imagine an IM bot that showed in its status message how many buddies were online. Even better, what if you could talk to that bot to chat with your buddies in the game, and see their replies in the IM window. That way you could see what was going on, even if you're not able to play right away. And if you saw that your buddies have been playing quite a bit, you might go into the living room and boot up the XBox. Second Life, World of Warcraft, and any other game with a chat interface might benefit from having chat interoperate with an IM client.

Another kind of game I'd like to see with multiple clients is persistent world games. There are things going on in the world when you're not playing, and it'd be nice to keep track of these. For example, in my brother's game, Barren Realms Elite, you'd send attack forces out to distant worlds, and the attack would happen at some time, usually when you weren't playing. It'd be nice to have a web page or RSS feed or gadget (Mac Dashboard, Vista sidebar, etc.) that showed me the status of my attack force and the outcome of the battle. These days, MMOs are the most obvious sort of game where this would be useful. In World of Warcraft, I'd like to know that Stormwind City is under attack by 60 Horde, or that my guild just defeated the bosses of Karazhan. The state of the world could be displayed in a web page, and major attacks could be sent as IM or email or RSS alerts.

Another sort of interaction I'd like with a game is for part of the game – not just status or chat – to be accessible in a lightweight client. In EVE Online, I'd like to track the economic game – my buy and sell orders, as well as production – even when I'm not in the full game client. EBay mobile alerts likely increase people's usage of EBay; my guess is that having that lightweight client that lets you track your EVE Online business dealings would make you play EVE Online more.

Even in single player games, there are some interactions with other people. For example, suppose a new high score in Scrabulous was sent to all your Facebook pals. That'd both remind people to play Scrabulous, and it would also encourage everyone to try to beat that high score. Scrabulous is a Facebook game, but you could imagine doing the same with other games. If XBox achievements were sent to my Facebook account, it'd be more fun to get those achievements than if people saw them only when they turned on their XBox.

To summarize, I'd like to see a lot more games with multiple interfaces. Some ideas are:

  • Status (web, IM status) to passively see what's going on in the game, even when I'm not there.
  • Alerts (RSS, email, IM, SMS texting) to actively be notified of major events in the game.
  • Chat (IM, email) to allow communication between people playing right now and people who might not play until later.
  • Play (web) to allow playing some subset of the game through an interface that I can use when I'm doing other things.

For some, the lightweight game will augment the full game. Many will end up participating in only the lightweight part of the game. For others, the lightweight game will be a gateway that leads them to try and enjoy the full game. I think that's a good thing. Not everyone uses all the EBay clients; not everyone who watches Heroes reads the comic books and plays the online games; not everyone who watched The Matrix also played the game. Different people will participate in different ways. Use an interface that's simple and widely accessible to complement the interface that's rich but not there all the time. We'll have much more interesting games when lots more people participate in them.


One of the things I’ve been wondering about in WoW is that real relationships tend to have multiple social circles, but in WoW I’m forced to have just one guild. That leads to barriers between groups, and competition between groups for members.

I‘d like to see multiple orthogonal social groups in games. Second Life for example has groups that you can join, but you can be in multiple groups at a time. Each group has its own chat channel. In addition you’re in an informal family group. You can choose your first name but there are a small number of last names available for each batch of new players. When you see a stranger with the same last name, you have a connection with them, without having joined any of the same groups. The explicit links (groups) are augmented with implicit links (last names). In games, classes and races and professions could serve a similar purpose. In practice though I rarely see people make connections based on last names or classes or professions or race. Perhaps it’s because there are too many people in each group, so you don’t feel kinship.

In an epic MMO, there are events in a shared history that could form implicit social links. For example, if a game has large, difficult battles, all the participants in a battle form an implicit social group. If a game has a way to build things, the people who built in the same town have a connection with each other. If a game has an economy, the people in the same business or frequent trading partners have a connection. When I’m in a town and pass by someone who has a shared history with me, I‘d like to see an icon or color so that I know I have a connection with this person. I might wave or give them a beneficial spell or interact in some other way. A shared chat channel or mailing list might be nice too. Instead, in WoW, I walk by strangers and don‘t care about them.

If we had many different ways for people to build social connections, and reinforce them with game features, we’d end up with a much richer social structure in games.


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.


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.

(diagram showing a moving corridor for a dungeon crawl game)
(This is a screen shot of the Flash demo.)

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

Labels: ,

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

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.