Choosing algorithms #

Game developers can't always find their algorithms in an algorithms textbook. Academic algorithms tend to be general purpose and often aren't the best choice for games. For example, compare textbook image scaling algorithms to hq4x. Hq4x is very impressive! How could the textbooks have missed it? It's because it's not general purpose. It is designed to work on hand-drawn low-color sprite graphics in games, whereas the textbook algorithms work on all sorts of images. Another example is path-finding algorithms. Dijkstra's algorithm is a general-purpose algorithm; A* came out of AI research (which is slightly closer to game programming) and is a little more specialized. But there are plenty of techniques used in games that aren't found in the textbooks. They take advantage of game-specific knowledge: the structure of maps, the characteristics of moving units, etc.

The general purpose algorithms are a good place to start but don't limit yourself to them. There might be a specialized algorithm that works better for your problem, or it may be worth the effort to design your own algorithm.


Water in strategy games #

In just about every city-building strategy game out there, water is static. It doesn't flow; it doesn't affect much; it doesn't change with seasons; and you can't change it. In 1994, I started the Simblob project to experiment with water flow in games, among other things. You could build canals and dams and dikes, divert waterways, and flood the opponent's cities. Well, you would've been able to if I had ever gotten around to implementing the opponent. The problem was that playing with water was way too much fun! I implemented heavy rains, droughts, floods, sedimentation, and erosion. Playing the game was lots of fun too, even though there was very little “game” actually implemented. In the end all I had done was work on graphics and water simulation, and I decided to stop working on it and start something else.

I still think water simulation has enormous potential for a strategy game. Imagine diverting your opponent's main source of water, so his crops fail and his people revolt. Or an enemy operative damaging your main dam, and you scrambling to repair it before it breaks, destroying your cities. Water is incredibly important in real cities, and it should be important in building-based strategy games.

Battle for Atlantis is a strategy game coming out in 2007 that has water simulation. Here's a quote from their web site:

For the first time in the history of RTS, a full physical model of water space will be created. The water has stopped being a “dead area” – a non-interactive flat mirror good only ship sailing. Real waves and tsunamis, flood and destruction of the landscape by water, river flows and waterfalls, splendid underwater effects – all this gives an enormous scope of creation and makes the game world of Atlantis as real as never before.

It sounds promising! 3dgamers has some screenshots. I just hope the water simulation is used more for gameplay than for graphical effects.


Learning Flash 8 #

Back in 2004, I attempted to learn Flash programming, but failed to find free tools, and ended up writing Java applets instead. I was unhappy with Java for a number of reasons, but the main one was that Java applets are clunky on web pages compared to Flash objects, and as a result more people have Flash than Java. A few months ago Troy Gilbert pointed me at, which has a list of open source Flash development tools (thanks Troy!). I eventually found the free and fast Motion-Twin ActionScript compiler (mtasc), but had a lot of trouble using it. The tutorials I found on the web for Flash development assume you're using the Macromedia development environment, which I'm not, so they weren't much help. I finally figured out what I was doing wrong.

I'm used to a certain development model: you write a program, (optionally) compile it, then run it. This might be considered “old school” by people writing Windows and Mac apps. When writing Windows and Mac apps, you put the source code with various resources (icons, graphics, music, dialog boxes, etc.) into a “project”, which gets compiled into an executable. In the “old” style of development (used for C++, Java, Python, Perl, Basic, Ruby, etc.), your program reads in resources after you run it. That's how I've been writing my games. Flash seems to follow the “new” style of development, in which lots of resources, not only source code, get combined into one package.

The open source mtasc compiler only compiles Flash (ActionScript) source code. It does not handle the resources that have to be assembled into a compiled Flash file (SWF). The mtasc tool will compile your source code and update a SWF file with the compiled code, but you can't use mtasc to create SWF files; they have to exist already. For that, you normally use the (commercial) Flash development environment from Macromedia. If you want to fully work in an open source world, you need another way to assemble resources. The swfmill tool can do this: it converts an XML file listing resources into a SWF file. With swfmill my toolset is complete.

The other thing that's confusing (for me) about Flash development is that it seems to be designed around movies, and every Flash program has a “frame rate”, even if it's not a movie. For now I'm ignoring this and just setting a low frame rate.

The summary of what I've learned so far about open source Flash development:

  1. Create an XML file that describes the resources you need. I'm using the example XML file in Mark Winterhalder's well-written tutorial on the swfmill site:
    <?xml version="1.0" encoding="iso-8859-1" ?>
    <movie width="320" height="240" framerate="12">
      <background color="#ffffff"/>
  2. Compile the XML file into an SWF file:
    swfmill simple example.xml example.swf
  3. Create an ActionScript file with your script. I'm using an example I found on the mtasc site:
    class prototypes {
        static var app : prototypes;
        function prototypes() {
            // creates a 'tf' TextField size 320,200 at pos 0,0
            // write some text into it
   = "Hello world !";
        static function main(mc) {
            app = new prototypes();
  4. Compile the ActionScript into your existing SWF file, using the -main flag to have it automatically call the main() function:
    mtasc -swf example.swf -main
  5. Embed the SWF into a web page using the <embed> tag, as described on the haXe site:
    <body bgcolor="#cccccc">
    <object classid="clsid:d27cdb6e-ae6d-11cf-96b8-444553540000"
      width="320" height="200" id="test">
    <param name="movie" value="example.swf" />
    <embed src="example.swf" width="320" height="200" 
      name="test" type="application/x-shockwave-flash"
  6. See the results in a browser. Hooray!

For me, getting started is the hardest step. Once I have something running, development becomes easier. Now that I have a Flash program running, my next steps are to set up my development environment, then learn about the Flash libraries. I've been wanting to learn Flash programming for a long time, but I kept getting stuck. I'm quite glad I finally put the pieces together, and I hope the above description helps others get started.

Labels: , ,

Software pricing #

(Warning: this post doesn't have a point; it's just me thinking aloud.)

Most products have some fixed costs and some marginal costs of production. The fixed cost would be the factory; the marginal cost would be the labor, materials, transportation, packaging, marketing, etc. The price of the product usually starts out high, and competition brings it down over time to be close to the marginal cost (at least according to economic theory).

Creative products like music, novels, and movies typically have high fixed costs and low marginal costs. As technology has improved, the marginal cost of music, novels, and movies has gone down close to zero, and we now have a great deal of piracy. Software is similar to music, novels, and music, except that the marginal cost has been close to zero for a very long time, and the software industry has had to deal with the problem of piracy for longer. Economic theory suggests with good competition, the price of these products should eventually go down close to the marginal cost. For all of these products, the sellers have tied the product you really want (for example, a song) to something physical (a CD), and the physical object has a non-zero marginal cost. However, with electronic distribution, people want the music without paying for the CD, the movie without a DVD, a novel without a book, and software without the installation CDs and manuals. The marginal cost of distribution is close to zero, so in theory, the price should eventually get to zero.

The open source community sometimes argues that the price of software should be zero (to match the marginal cost), and that developers can earn money selling services and support. There's a major problem with this: the incentives are completely messed up. If a developer makes more money when more support is needed, there's an incentive to make the product require more support. Products will end up harder to use and contain less documentation. There's also no strong incentive to offer new features for free, because you're not getting paid for new versions of the software.

With MMORPGs we're seeing a lot of experimentation with software pricing. This is possible because the software is virtually useless without connecting to the service. World of Warcraft charges for the software plus for the service. They crack down on people who want to offer their own service (alternate free servers) because they make most of their money from the service they offer, and don't want competition. World of Warcraft also charges for expansions (which are rare). With Guild Wars the software is free (you can download it from their site for free), but access to different services (areas of the world) costs a fixed fee. Those services do not carry a monthly fee. With ArchLord the software costs money but there's no monthly fee. Second Life (which isn't technically a game) makes money both by renting areas of the virtual world and by selling virtual currency, which you can use to buy in-game goods and services. Games can also make money by selling in-game items, upgrades, status, etc. MMORPGs can tie the game to the service, and then charge for the service. However they are not making their software open source, because they do not want competitors to create compatible services.

Most games however do not have the option of charging for services, and it is difficult to charge for support in a consumer-level product (consumers get angry and feel that they deserve free support). So game developers are stuck with piracy, just like makers of music and movies. We want to recover the high fixed cost of developing the product, so we charge for the software, even though the marginal cost is close to zero. Consumers are more willing to buy software that comes in a physical package, so we include a box, installation CD, a manual, etc., all of which reduces sales and profits. Alas.

There is one more thing we might want to explore. Music, games, movies, etc., are all emotional experiences, and they're worth more to people when the emotions are greater. One way this works with music is to use concerts, association with movies or TV shows, branded products associated with the band, and other sorts of tie-ins. With movies, the same movie is worth more when people go watch it together at the theatre than when they watch it alone years later on network TV. A novel is more valuable when your reading club is reading it right now and you want to participate in their discussions. These products are more valuable at certain times than at others. Watching a TV show the night it airs is more valuable because I can talk to my friends about it; watching it later (with TiVo) is less valuable. What can we do with games? I think the fan sites are a big help. Frequent updates and developer involvement in forums can help too. The Movies let users upload their creations (not their games) to the site. The Sims lets you download objects created by others. Even in a single player game, you can offer something that lets people connect to each other. When they're sharing an experience, it will have more emotional value. And that is something that could reduce piracy—you're not just buying a game; you're buying access to a community.

I think piracy will always be with us, but I think the open source model is unlikely to work for games. Charging for support gives a perverse incentives to developers to make things work badly or confusingly. Charging for service might work for some types of games, and the MMORPG developers seem to be exploring the options. I think the way to approach the problem is what many game developers already do partially without realizing it: offer multiple experiences at different prices. Offer a free demo that has a substantial part of the game and no support; this matches the marginal cost of the software alone. Offer the full version without annoying copy protection (why do so many developers make their paying customers get a worse game than the pirates get??). Make a ”special edition” that appeals to the least price sensitive and most rabid fans. Offer special products (t-shirts, trinkets, etc.) that tie in to the game. Make a community site that people actually like (so that they don't go to other sites for the information they want), and make all or some of it open only to people who bought the game. Make sure the developers are involved with the community site. Change the model from selling software to selling enjoyment. Look at other businesses that do this (amusement parks, movie theatres); they sell the basic product at a lower cost and then sell extras (such as food and drinks) for a much higher price than the marginal cost of those extras. Price-sensitive customers get annoyed by this, but it works for the business because they're not just paying for a drink; they're paying extra for the enjoyment of the drink in that location.

We need to consider the entire experience of playing a game, not only the software, as a potential source of revenue, and then figure out how to best recover the high fixed costs of making the game, and also allow for a low marginal price so that we can get a large audience. We need to consider that games don't need to be played in isolation; people talking about a game with their friends or even with strangers can add to the experience. We need to consider that different people are willing to pay different amounts for the experience. It's the entire experience we're selling, not just a box with software.

Rules of Algebra fail with floats #

One thing to be careful about when programming games is relying on the rules of algebra. Simple laws like the Associative Law and Distributive Law don't always work when using floating point numbers. I'll give some Python code to demonstrate, but these problems are with floats, not with Python.

  • Distributive Law. We've been taught that a * (b + c) == (a * b) + (a * c).
    a, b, c = 0.111, 0.201, 0.305
    s1 = a * (b + c)
    s2 = (a * b) + (a * c)
    print '%.08f - %.08f = %.08f' % (s1, s2, s1 - s2)
    print '  equal? %s' % (s1 == s2)

    These are the results:

    0.05616600 - 0.05616600 = -0.00000000
      equal? False

    The difference looks like 0, but it's not. The two sums are not equal. To see the problem, change the format specifier %.08f to %g.

  • Associative Law. We've been taught that a + (b + c) == (a + b) + c. When some of those are negative and some are positive (and occasionally even when they're all positive), the results won't be the same.
  • Additive Inverse. We've been taught that a + b - b == a.
    a = 1e-30
    b = 1e+30
    print a, a + b - b, (a + b - b) == a

    The result is that (a + b - b) != a. You can look at this example as a special case of the Associative Law.

To some of you these problems will seem obvious and not a big deal for most applications. Why do I bring it up in this blog? Loss of precision can open up exploits in multiplayer games. Let's consider a game in which you can trade with someone else, and the total amount of money is represented as a float. If player A has a large amount of money a, he may be able to send a very small amount x to B (who has b) without it affecting his own amount. We can have a + b < (a - x) + (b + x), which means this exploit creates new money out of nowhere.

If you're using floating point numbers, be sure to use double precision. Alternatively, use integers or fixed point arithmetic to avoid some of these issues. If you do a lot of math in your game, be sure to learn about numerical programming. There are a lot more issues than the simple ones I describe here.


Using oscillation to speed learning #

I've been reading Without Miracles. I had just read about children learning labels. The example was a child looking at a bird and then being told it was called a "bird", then looking at a different bird and being told it was a "bird". The child then has to generalize and consider that other small flying creatures are likely to be "birds" as well. However, upon seeing a butterfly and being told it was not a bird, the child then has to refine his understanding of what a "bird" is.

This form of learning, with overgeneralization followed by correction, may well be faster than undergeneralizing. For example, what would happen if the child only believed the two creatures he saw were birds, and did not label other small flying creatures as birds until explicitly told they were birds? He'd learn slower.

I was at the beach, looking at tide pools, when I realized there's a similarity to the child's learning. Rivers flow in one direction (usually) and have a certain amount of life in them. Beaches have water flowing in both directions, due to waves (short time scale), tides (medium time scale), and seasons (long time scale). The diversity of life in tide pools is far greater than what I've seen in rivers.

In the case of the child's learning, generalization (classifying everything as a bird) is one direction and correction (being told that some creatures previously thought to be birds are not) is the other direction. Could it be that oscillation leads to faster "learning" than a steady stream?

The advantage of learning and then correcting mistakes is that you can learn faster than if you were learning cautiously enough to avoid making mistakes. Many AI algorithms are of the cautious sort. It may be that it'd be better to have our games learn patterns very quickly and then keep a set of exceptions. For example, in Simulated Annealing, we slowly lower the temperature until the system stabilizes. It may be better to quickly lower the temperature, then raise it again, and continue oscillating for some time. In Neural Networks we change the neuron parameters very slowly. It may be better to change them quickly, then change them back if needed.

I'm enjoying the book a great deal but I haven't yet figured out how I might use this for my own games. My intuition tells me that there's something very useful here, but I haven't pinpointed anything specific.


The Guild 2 #

Yesterday I took a look at the demo for The Guild 2. It's a strange game. It's somewhat like The Sims in that you have a character that has relationships with other people in the game, and you can start a family. It's somewhat like a role playing game in that you have classes, skills, abilities, attributes, experience points, combat, etc. It's somewhat like a city-building strategy game in that you can build mines, businesses, houses, and so on. The graphics and music are nice. The world feels alive—there are people wandering around, with jobs and relationships and government positions and alliances and feuds. While standing around, a random person came up to me and gave me a cake. I'm very impressed with the game world.

The problem is that someone forgot to design a fun game. In trying to do lots of different styles of games, it does none of them well.

The game is rather tedious. You have to keep track of your relationships with everyone else. These seem to be influenced by your position in society, your family, your religion, who you work for, and who works for you. It has more detail than The Sims (for example, you can buy objects and give them as gifts to someone) and more relationships to keep track of than in Tropico. The problem is that there's too much information, and you can't act on most of it. You only indirectly influence it. This is something that is impressive and thus appealing to game designers, but it's not actually any fun.

To run a business, you have to click on your cart, send it to the market, buy raw materials (prices are set by supply and demand) by dragging them into your cart, then send the cart back to your shop, drag the materials from the cart to the shop's inventory, click on an employee, and tell him to make an item. Then you wait for a while, and once the item is ready, you drag the item to the cart, send the cart to the market, and drag the item to the market stall to sell it (prices are set by supply and demand). It's impressive, but it's boring. Imagine if Warcraft had done this—you'd have to tell each orc to walk to the mine, pick up a tool, mine for metal, pick up the metal, carry it back to the storehouse, and then walk back to the mine. You have to do this for each business you run in The Guild 2. Although there is a way to set this on auto-pilot, there never should've been this much detail. The programmers wasted too much time with this.

There's also combat, positions in government, bribery, assassinations, thievery, a legal system (including court cases), and lots more complexity to this game. That's the real problem: there's too much to keep track of and do, and too little reward for doing it. You get to play out the drudgery of living as a serf in the Middle Ages. I can't even describe how bad the UI is.

There are also some amusing things in the game. Every building has a name: Better Homes, Lumpy & Liquid, The Hot Spot, Raw Iron Raw Power, A Waste of Paint, Roof Included, The Funny Farm. The help text is often strange:

... Scholars are also not adverse to compliments and gifts and will even let themselves be persuaded to dance.

Once the initial awkwardness has faded one can oft soften a reluctant scholar with soft embraces and gentle kisses, bewitch him in private conversation or even climb into a tub with him. But beware of using too much imagination in your courting, for scholars seldom appreciate variety.

There are odd player skills: Master of manure, Pack mule, Kama Sutra master, Exploiter, Great preacher, Deep sleep, Local club president, Face of innocence, Dorian Grayish. The description for the "Strong hair growth" skill starts out like this:

You have been blessed by nature with a curious biological phenomenon: whenever you must rot in the dungeon because of some misdeed, your hair begins to grow at a breathtaking speed. After a few hours, you look as though you have been mouldering for 30 years. ...

Even though the game doesn't look like it'll be any fun for most people, I do recommend that game developers try out the demo. Look for things that you might think would be cool in a game: multiple genres (from role playing to real time strategy to business simulation to action/combat), deep and complex simulation (relationships, businesses, employment, politics, law), open-endedness, etc. Try to figure out whether they are actually fun for a player or merely impressive to a developer. I would have loved to design and write a game like this. It's so impressive that it's sad to see that it's not at all fun.


World of Warcraft Analyses #

The PlayOn project at Xeroc PARC has been analyzing WoW data and then posting it on their blog. (These people get to play games at work!) Thanks to richardt for the link. Some findings I found interesting:

They computed the fraction of time each class joins a group. As you might expect, Priest was in a group much more often than any other class. Priests also level up faster than other classes. But that seems to be an anomaly. In general, people in groups level more slowly.

People are more likely to be at a level that's a multiple of 10, probably because there are certain rewards at levels that are multiples of 10, or there are penalties (such not being able to play on lower-level Battlegrounds). So people at a level just before those levels will play extra hard and people at those levels will try to avoid leveling. Leveling time in general is roughly proportional to the level, so you get a quadratic effect. There's a spike at level 40, most likely because that's when you can buy a mount.

Warriors are the most popular class at low levels. Hunters are the most popular class at high levels. Shamans are the least popular class. Humans are the most popular race. Orcs are the least popular race, despite them having the best dance moves.

It's a fun blog to read.


Ruby scares me #

Every time I take a look at Ruby, I am simultaneously intrigued and disgusted. Today I was looking at it once again, pondering the Camping framework for writing web apps, and ran across this explanation of how it works:

Behind the scenes, Camping actually reads its own source file (with the __FILE__ handle) and does a search and replace on all instances of Camping. It then evals the result and runs your app with the modified code!

— from O'Reilly's Ruby column

Argh!! On one hand, I feel like I shouldn't need to care how something is implemented. But I see this sort of thing (building and evaling code) so often in Ruby that it makes me worry that the language is incapable of expressing the abstractions that people actually want to build, and it might also be incapable of expressing the things I want to build. I guess I grew up treating eval as something to use only as a last resort. The only place I felt okay using eval was Scheme, where it took program trees instead of strings. Ruby still intrigues me though, so I'll probably try a project in Ruby at some point.


An old classic: Settlers II #

Settlers II has been remade for its 10th anniversary. I've tried out the demo and it reminded me of all the things I liked about Settlers. The game is somewhat unusual. It's a building+war game, like Age of Empires, Tropico, Command & Conquer, etc., but its emphasis is on building and not on war.

One of the unusual features is the transportation model. In most games of this sort, people walk around wherever they need to go, and you can build roads to speed up their movement. In Settlers, you must build roads, and every road segment has a settler assigned to it. That settler will move goods back and forth along the road. You have to carefully plan your roads to handle the traffic; roads can become bottlenecks. Making road segments long means you use up fewer settlers and allows faster travel; making them short means you get a higher capacity. Roads also become paved and can have donkeys to increase capacity.

The transportation model changes the implementation strategy for the game. Usually you run a pathfinder (like A*) for each of the peasants, and combine that with a movement algorithm to avoid local obstacles. This can get expensive when you have lots of peasants. Each peasant handles a single type of good, usually assigned by you. For example, you might assign a peasant to be a miner; the pathfinder will find a path between the mine and the warehouse. There is no further distribution of goods; it goes into a global store that can be accessed instantaneously from anywhere. In Settlers, the peasants are not using the pathfinder. Instead, the pathfinder is used for materials and goods. They are physical objects that have locations and can move around. They can be put in a warehouse, but they have to be moved to the location where they get used. The peasants and road segments serve as capacity restrictions. If a good needs to move from one place to another and the road it needs to travel on is “full”, it waits for the road segment (and associated peasant) to free up. This works somewhat like a packet-switched computer network.

How do the goods “decide” where to go? A local approach would be to make each good perform pathfinding to its destination. Pathfinding on the road graph will be much faster than pathfinding on a grid, because there are far fewer segments and connection points. But how do they find their destinations? We could either keep a list of points that require certain goods, or we could build an influence map. It's possible with an influence map to not even need pathfinding. I'm not sure what Settlers actually does.

Another difference between Settlers and other building games is that the Settlers economy has much longer chains of production. Forests can be cut to produce wood. Wood are milled into wooden boards. Boards are used to build farms and other buildings. Farmland is used to raise crops, yielding grain. Grain is milled into flour. Wells produce water. Flour plus water is baked into bread. Grain plus water is turned into beer. Fishermen use fishing poles to catch fish. Hunters use spears to catch animals. Animals taken to the slaughterhouse become meat. Meat, fish, and bread are fed to miners. Miners can mine for coal, iron, granite, and gold. Coal and iron can be smelted into steel. Steel is taken to the metalworks to make tools such as spears, and to the armory to make swords and shields. Granite is turned into stone. Stone is used to make new types of buildings. Gold is turned into gold coins. Gold coins, swords, and shields are given to soldiers. Soldiers are needed at watchtowers, which expand your territory. The economy is complex.

Also unlike other building games, you don't control any of your people directly. You can indirectly control them by building things. To go to war, you need soldiers, but you never explicitly recruit or place soldiers; they are produced whenever you have enough of the needed goods (gold, beer, sword, shield). You can influence what gets transported by choosing a transportation priority for each type of good (this is like QoS for TCP/IP), and you can set the priority of having soldiers vs. builders.

At the start of the game, you don't need to worry about the full economy. For example, you can't build tools without steel, which requires coal and iron, which requires miners, which requires bread and meat, which requires grain and water and animals, which requires flour, which requires farms, which requires wooden boards, which requires wood. Instead, your initial warehouse includes many types of goods, from which you can jumpstart your economy. You don't need to make rarely used items like tools until later in the game, when your settlement is large. It's a nice way to gradually introduce complexity to the player.

It would be nice to be able to see general trends, like whether I'm building up more bread than I need, or whether people are perpetually low on water. It's hard to manage everything in your head by checking manually. If I were in charge of a town like that, I'd hire some people to gather information and alert me when something's wrong. Overall though it's a very interesting game, and not like other games I've played, so I think it's worth exploring.

Update: [2006-07-21] Sören M points me to a design document about transportation in Widelands (a game much like Settlers II).


A Tale in the Desert 3: First Impressions #

A Tale in the Desert is a rather odd game. It's a MMORPG based in ancient Egypt. There aren't any monsters to fight. Instead, you perform tasks like gathering, mining, farming, weaving, fishing, and so on. You use the materials you gather to make equipment, which you can use to make more complex materials and objects. Eventually you can build sculptures, buildings, and monuments. The game has a story to it, with a beginning, middle, and end. You and everyone else in the game is part of that story. The ending depends on the actions of all the players.

It's quite different from anything else I've seen. Although games like World of Warcraft have gathering and crafting tasks, the focus there is combat, whereas in this game, it's all about gathering, crafting, building, trading, and socializing. The tasks you need to perform can depend on what others have done. For example, you may need to build something larger than what anyone else nearby has built. Once you build it, your object remains in the world, visible to everyone. As I wandered around the game world, almost every object I saw was something created by a player. As a new player, I needed to find areas that weren't already occupied, so that I could set up the equipment I needed. Some of the basic resources (wood, sand, mud, grass, stone, etc.) are shared, so it helps if you set up a workspace away from others. As far as I can tell though, workspaces have a short lifespan, so you work in an area for a while and then move on.

The tasks you need to perform can also depend on other players. For example, you may need to build an sculpture and leave it out in the open so that passers-by can vote on whether it's attractive or an eyesore. Or you may need to talk to people and convince them of some cause. Or you may need to get people to join your guild. The social aspect is important; other people aren't there only to help you fight monsters. There's also the ability to propose new laws and get signatures/votes; if the new law gets passed, the game developers will implement it (remember LambdaMOO?). I didn't explore that aspect of the game.

The graphics aren't great, although they didn't bother me much. There's very little sound or music, and that hurts the game a great deal. Sound effects are incredibly important. The UI is awful. It looks like it was designed by programmers: there's lots of abstraction and generality, like scrollbars, arbitrarily sized dialogs, deep menu hierarchies, and an attempt to make everything vague so that it's reusable in other contexts. For example, to dry out grass and turn it into straw, you need to Drop the grass. This is “cool” in that it reuses an existing function, but I think the UI would be better with the task explicitly listed. The UI also offers very little feedback about objects and actions. There are lots of objects around. Some are usable and some are not. You won't know until you click and get a menu. There are lots of places where you can't do something, but it won't tell you that you can't until after you've attempted to do it. For example, when planting flax seeds, it allowed me to plant a second seed too close to the first, then it told me it was too close. Mark the area in red or something to give people early feedback about whether their actions are going to succeed. Don't let me do something that's not allowed.

Another problem with the UI, at least for a beginner like me, is that it doesn't really give you any hints about what to do. There's a huge list of tasks, but no way to learn how to perform them. For example, I was supposed to learn Carpentry. How should I do that? I have no idea. There's no tutorial as far as I can tell. I ended up going to the web and searching for the information. How was I to know that I should find the "SArch" building (whatever that stands for) and click on it?

I played for several hours and got through the ~30 starter tasks, with a lot of help from the web. That opened up new possibilities of projects I could do. However the game felt rather tedious and uninspiring. Let's see... I need 100 bricks. I'll collect mud, straw, and sand, then stand around for 10 minutes making bricks. Boring. There's no challenge in that. It's not interesting. It's likely that the social aspect makes up for it (the crowd I talked to was much friendlier and more mature than in any other game I've been in), but I didn't stick around long enough to find out.


World of Warcraft: First Impressions #

I've been playing World of Warcraft (WoW). It's the MMORPG to try. Last year I played around 250 hours of Guild Wars, but it's not really an MMORPG; it's somewhat like Diablo 2, which is multiplayer, but not massively so.

To get a good feel for WoW, I played over 50 hours over the past 10 days. I tried out 6 of 8 races (Alliance: Human, Night Elf, Gnome, Dwarf; Horde: Troll, Tauren), 6 of 8 character classes (Druid, Hunter, Paladin, Rogue, Warlock, Warrior), 4 of 12 professions (Mining, Skinning, Cooking, Fishing), and 1 talent (Marksmanship). I visited all 6 major cities (Stormwind, IronForge, Darnassus, Ogrimmar, Thunder Bluff, Undercity) and 3 of 4 Goblin cities (Ratchet, Gadgetzan, Booty Bay). I played mostly PvE, but also tried out PvP, both out in the open and in 1 of the 3 PvP instances (Warsong Gulch). I visited 1 of 36 PvE “instances” (Ragefire Chasm) and 12 of 40 major regions on the map (The Barrens, Durotar, Mulgore, Thousand Needles, Dun Morogh, Elwynn Forest, Westfall, Redridge Mountains, Teldrassil, Stranglethorn Vale, Tirisfal Glades, Darkshore). I tried out 1 minor quest from 2 special events (Midsummer Festival and Scourge Invasion).

Overall, I thought the game was well done. It's much more complex than Guild Wars and there are lots of different styles of play. Guild Wars offers character classes plus secondary classes, giving essentially 15 different combinations, although the choice of which class is primary and which is secondary gives each of those combinations two styles. WoW offers 40 combinations of races and classes. The races affect your appearance and give you bonuses and skills; the classes affect your clothing and give you bonuses and skills. Within each character, Guild Wars offers 4 attributes and plenty of skills influenced by those attributes; WoW offers attributes but also 3 talent trees and plenty of skills influenced by them. In Guild Wars, the attributes can be changed to suit each mission or area; thus, you don't have to choose which to specialize in. In WoW, attributes are influenced by race and class, but can be modified by items and spells. The talents are permanent choices, and thus you treat them like races and classes, and have 120 combinations of races, classes, and talents. So already WoW has a much richer set of choices (“builds”) in characters. But wait, there's more! In WoW, you also have professions, which are non-combat activities, such as Skinning (get leather or other materials from animals), Leatherworking (to turn leather into items), and Enchanting (to add magic to items). As you use the skill, you become more proficient in it, and that allows you to do more things with it (for example, when you are better at Skinning, you can skin from higher level animals). You can choose 2 of 9 main professions, plus up to 3 side professions. This raises the combinations of character builds to 4320, although in practice, only around 14 of the 36 combinations of professions make sense, so there are a “mere” 1680 character builds you might want to play. In Guild Wars, your weapon choices are largely determined by your character class. In WoW, they're influenced by class but you can learn to use new types of weapons. There are 16 types of weapons (such as Swords, Wands, Bows, etc.), and each character class starts out knowing some of them, and can learn up to 4 to 15 of them (varies by class). Once you choose a weapon, it increases the number of character builds to nearly 12,000. Compare that to 15 in Guild Wars and you'll get a sense of how rich this game is. I barely scratched the surface with what I tried out.

Each race has a starting location in the world. There are 8 races and 6 starting locations. This greatly increases replay value. In Guild Wars, there's one place everyone starts and explores, so the second time through you're not seeing anything new. In WoW, you can play 6 times and see brand new scenery each time. The WoW world is huge, varied, and non-linear; Guild Wars in contrast is fairly linear, much smaller, and has 5 types of areas (pre-Searing, post-Searing, jungle, desert, volcano). Different areas have monsters of different levels, so you can't venture in to the higher level areas without being killed. With several of my characters I did however manage to sneak by some monsters and get to high level areas, where one hit from a monster would kill me. There are special areas called instances. These are areas that are separate for each group of people playing. In Guild Wars, all areas other than the cities are instances; in WoW, most areas are not, so you can see lots of other people doing things unrelated to your party's actions (seeing other people is fun!).

There's just so much to do in World of Warcraft, and so many styles of play, that it's no wonder people spend huge amounts of time playing. There are also lots of repetitive actions that lead to variable results; this activates the gambling portions of the brain. For example, when performing quests to retrieve items, you will sometimes get the item and sometimes not; when killing monsters, you will sometimes get treasure and sometimes not; when fishing, you will sometimes get l fish (which can be eaten to gain health) and sometimes you will get treasure; when improving skills sometimes you will gain a skill point and sometimes not. Everything you do works this way; it's no wonder it's addictive.

The game was pretty smooth when it ran. Several times though the realm I was on would be down, and I couldn't log on. When I was on though everything was smooth and (as far as I could tell) bug-free. Blizzard seems to be pretty good at this.

I enjoyed the game but in the end I wasn't addicted to it (despite playing 50+ hours in 10 days). The main problem I saw was that the reward was far too low for the amount of time I spent. Running from place to place is really time consuming. At higher levels you can buy creatures to ride on, and this lowers travel time, but the reward is less pain rather than something rewarding in its own right.

The quests were often repetitive and boring. For example, I had a quest to go kill some ostrich-like monsters. It took a while to run out to that location and kill them. When I got back to town, I got a small reward and then was told to go out and kill some lions. I had to go back to the same area I was just in, kill lions, and go back. I was then told to kill some dinosaurs. I had to go back to the same area I was just in, kill dinosaurs, and go back. After that the series of hunting quests continued in a slightly different location with slightly different animals (zebras, more lions, more birds, and more dinosaurs). There were probably at least 15 quests like this. Another line of quests involved killing some variant of kobold, going back to town, then being told to kill a different variant of kobold in that same area, then going back to town, then being told to kill yet another variant of kobold in the same area. These kinds of quests really stretch out gameplay, because you have to run back and forth every time; you can't get get the next quest until you've finished the previous one. Occasionally the quest would be more interesting (for example, collecting dinosaur eggs while killing the dinosaurs), but it only seemed slightly interesting because the quests were boring.

I do like the whimsy in the game. There are lots of cultural references, silly items, etc. The dances are fun (for example, the orcs dance like MC Hammer). The graphics look cartoony, making the game feel more fun and less serious.

With the trial account I played, I couldn't participate in some of the interesting aspects of the game, like the auction system. In Guild Wars, you have to wander around, asking people for things to buy or sell. It's chaotic and it was so much of a pain, I rarely traded with anyone. With the WoW auction system, I think I would trade much more. Comparing trading in the two games really demonstrates how important efficient markets are. I also couldn't really get involved in guilds, which are apparently a lot of fun (but have high time requirements).

On my last day, I sold all my items and found that I had earned around 2.6 gold (26,000 copper pieces). This amount of wealth was unimaginable to me a few days earlier. The scale of wealth seems to go up exponentially. For example, a bag that can hold 8 items costs 4 times as much as a bag that can hold 6 items. Small increases in power come at a large increase in price. I think this is a good game design, but it felt strange to me. Despite getting so much, the last few days were just not much fun. Since I had only a short time left before my trial account was cancelled, I decided to kill off my main character in a most spectacular way. I went to the top of Thunder Bluff, the highest cliff I had found in the game, set myself on fire, and jumped off, to my death.

It's a very interesting and rich game. It's just not for me. It takes too much time and wasn't rewarding enough. If I were paying the monthly fee, I would feel like I had to play a lot to get my money's worth, and I'd end up playing even when it wasn't fun. The other problem I have with playing games online is that real-life interruptions can lead to my death in the game. If you have kids, you're going to have real-life interruptions. So I'll go back to playing Oblivion occasionally, and doing other projects (like writing a transportation game, going on scenic drives, and writing web articles). I do encourage people to try out the free trial (either from FilePlanet or by getting an invitation from someone who already plays), because it's an interesting game for game developers to study. I'm glad I tried it out. And I'm glad I didn't become addicted. :-)


Playing Oblivion #

In case you've been wondering why this blog (and progress on my game) has been quiet lately, it's because I've been playing The Elder Scrolls IV: Oblivion. It's a fun game, in part because the NPCs do their own thing, and it's fun to watch them.

Tonight I was running north along one of the main roads, and a bandit jumped out to rob me. He jumped a bit too late, for I kept running with a bandit on my tail. I met another bandit, who also started chasing me. I then met a third bandit and continued to run. I then saw two of them turn and start chasing a woman on horseback. She delivers the newspaper daily to all the cities. She screams and starts to flee downhill. I turn around and start chasing the bandits, not because I want to save her, but because I want to watch the chase scene. After chasing her down the hill to the bay, they noticed me and started chasing me instead. She fled to the south and I went to the north. I decided to escape by swimming across the bay. To my amazement, they started swimming too. I have a magic item that doesn't require me to breathe underwater, so I went underwater and hoped they would drown. They didn't. They periodically came up for air. As I reached the other side of the bay, I looked down and saw the two of them coming up for air, then diving again. I wasn't able to escape.

I decided to turn east and head for a fort. Many forts contain monsters, and these monsters often fight humans, including bandits. Not all of my enemies are friendly towards one another. At the fort was a troll, a mudcrab, and a bear. I jumped up to a high perch and watched the two bandits defeat the three creatures. I then decided to lead them to a nearby cave. Along the way the bandits killed a wolf, and at the cave they met a minotaur and an ogre. In Oblivion, ogres are incredibly strong. It was here that I expected the bandits to meet their end. Instead, they fled! They swam across the bay, out of my trap.

I chased the bandits across the bay. I lost one of them, but saw the other one run up a hill. I chased him for a while but eventually he got away. I went back across the bay to the minotaur and ogre, and led them to a nearby goblin cave. It took three goblins to kill them. Now I have one goblin remaining. I took him to another cave, inhabited by a rival tribe of goblins. Four goblins from the rival tribe killed the one goblin I led there. I now had four goblins chasing me. So I took them back to the first goblin tribe's cave. I kept running back and forth, not actually fighting, but just leading goblins to each others' caves, and the hordes wiped each other out.

Playing this way is amusing.

Having played for 130 hours, I'm about halfway through Oblivion. It's an interesting game for a game programmer to play. You can guess what techniques they used for their AI, and then run experiments to see what happens. I'm probably not playing the way they meant the game to be played.


Do people really want innovation in games? #

People seem to complain that games (and movies) are all the same—that there isn't enough innovation. I suspect though that people don't really want innovation. Guitar Hero is innovative. Wii is innovative (watch the Wii video from E3). But if you enjoyed some game, don't you want more like it? Or would you rather take your chances with something random?

In the field of machine learning, there is the notion of exploration vs. exploitation. As you learn things, you want to take advantage of what you've learned. If you never exploit what you've learned, why bother learning it? Why bother learning to read if you're never going to read? However you can't only spend your time doing what you know. You also want to spend some of your time exploring new things. Otherwise you may not discover something better than what you know. 100% exploitation is a mediocre strategy. 100% exploration is a bad strategy. You really want some of each.

In game development, movies, books, etc., it would be a shame if there were no sequels or games similar to existing games. That would mean that if someone discovers something good, we never do that again. On the other hand we don't want only sequels. I think games like Guitar Hero, Gish, The Sims, Everquest, and Puzzle Pirates demonstrate that there is innovation out there. Some people are arguing that there isn't enough. Others are arguing that there shouldn't ever be sequels. It's hard to know what the “right” amount is. I do believe that the way the free market works, there will be slightly less innovation than is optimal. It's not zero though. And I don't believe that you can force the market to innovate more. Ironically, a market with lots of small independent game companies is likely to produce less innovative games than a market with behemoths like EA. But that's a story for another day.

I find that of the games I've gotten recently (Black and White 2, The Movies, Guild Wars, Oblivion), I've enjoyed the innovative games less. I think that's because the sequels have more refinement in them, and that makes them better than the innovative games, which haven't been tried out on a large scale and don't yet have the feedback needed for improvement. I'm trying to spend around 10-20% of my time playing innovative games, in part because I like to study them as a game programmer, but also because I want to spend some of my time exploring new things.

Innovation isn't dead. It just produces lots of junk, which is what it should do. If all innovative games are good, people aren't experimenting enough. Sequels aren't bad. If we never had sequels, we'd never be able to polish the rough gems found in the innovative games.


Prediction, Chaos, and Order #

When you play a game, can you predict what's going to happen? I think being able to predict everything makes the game boring. Being able to predict nothing makes winning unrewarding. It becomes a game of chance rather than a game of skill. It's games in between that I'm interested in.

I want skill to be important, so that winning is rewarding, but make each instance of the game different, so that you can play repeatedly. How can you make the game somewhat unpredictable?

  • Multiplayer. If you add other humans, and humans are hard to predict, then we can't predict the outcome of the game. I think however that this isn't sufficient. If the opponent is good and the game predictable, you can predict what the opponent should do. Tic-Tac-Toe is an example of a game that's multiplayer but boring.
  • Complexity. In some games, the game world is so complex that a human cannot accurately predict what will happen, even if everything were known. Chess is an example of a multiplayer game in which the entire game board is known, but it is not possible for a human to determine the best move.
  • Randomness. If some aspects of the game are random (for example, the roll of the dice), the game will be different each time. If there's too much randomness, then the winner is essentially random. If there's too little, then each game will essentially be the same. But if you get it just right, then the player's skill demonstrates how he reacts to the game. There's also randomness in physical games. For example, when playing golf there's some randomness in where the ball goes, just from unpredictable variation in the stroke, and factors like air density and wind.
  • Information Hiding. Some information about the game world can be hidden from the player, and the player's skill can be used to infer aspects of the hidden information. You can hide the initial game world (for example, the cards initially dealt to each player), the opponent's moves (for example, the cards discarded by an opponent), or the result of randomness (for example, the cards drawn from a shuffled deck during the game).

Many games combine more than one of these. For example, Chess combines complexity and multiplayer. Poker combines information hiding, multiplayer, and randomness. Civilization combines all four.

When playing a game that involves randomness, it is important to note that skill is not the only factor; “luck” matters as well. In the NCAA tournaments starting this week, as with all sports games, you cannot conclude that the winner is a better player. You can only conclude that the winner is likely to be a better player. That's why rematches are useful—they let you be more confident in who's better.

My transportation game involves randomness and complexity, and I am undecided about information hiding. It's a single player game, and I am not planning multiplayer. After all, I will be the only player.


Transportation game, models #

I'm trying to use stocks and flows to create a model for my transportation game. Stocks correspond to nouns and flows correspond to verbs. At first I thought businesses would be stocks and the transportation of goods would correspond to flows. But I could also see the businesses as flows (since they consume and produce things) and the cargo areas and trucks as the stocks. Or maybe both trucks and businesses are flows, and only cargo areas (loading docks) and warehouses are stocks. Or maybe the cargo itself is the stock.

When it comes to a game, the player's decisions (and the AI's decisions) can directly affect flows, but not stocks. You can change the rate of production in Warcraft by hiring more peons, researching technology, etc. Production of gold is a flow. You do not directly change the amount of gold you have (except by buying something, but I think that's an instantaneous flow). Gold is a stock. There's no decision to be made with a stock—it just exists. There is a decision to be made with each flow, because you can throttle it back from its maximum. There are other decisions to make as well, but the basic resource management decisions (for gold, wood, soldiers, etc.) are about flows, not stocks.

In my game, the player controls the movement of trucks and the AI controls the businesses. The decisions are based partly on how much of each resource is available. I'm planning to treat trucks as stocks and the loading/unloading of them as flows. Businesses will be flows, but their cargo areas will be stocks.

The transfer of cargo is not enough to make an interesting game. The player will also need to make decisions about infrastructure and placement of transportation systems. The actual loading and unloading of trucks is boring; it's likely that an AI agent, acting on behalf of the player, will make those decisions. I still don't have a clear idea of where I'm going with this game, but it's already led me to some interesting topics (operations reseach, system dynamics, supply chain management).


Impolite game: Spellforce 2 #

I no longer play Guild Wars, Black and White 2, or The Movies, so I've been looking for another game to buy. Battle for Middle Earth 2 and Spellforce 2 both looked interesting, so I downloaded their demos.

Spellforce 2 won't start the demo unless I install StarForce. What's the point of copy protecting a demo? And worse, StarForce is awful and I am not buying games with it. So Spellforce 2's demo goes into the recycle bin, and I'm trying out Battle for Middle Earth 2, which looks and sounds nice. It seems to use SafeDisc, which is perhaps not as bad as StarForce, but still annoying. It also has lots of splash screens that can't be aborted by pressing Esc or Enter or Space or by clicking the mouse. Why do games tell you to use NVidia/ATI and Intel/AMD? Do they really want to tell 75% of their audience that they've chosen badly? I haven't found a major commercial game as friendly as Guild Wars. Fortunately Guild Wars is about to release an expansion pack, so perhaps I'll wait for that.


Transportation game, basic objects #

picture of example business

I wanted to start with something simple for my transportation game. I want to explore the transportation of goods between businesses. I created a simple model:

  • Business. Each business (labeled B in the diagram) can consume and produce items. For example, a steel mill consumes iron and produces steel. Some businesses only consume; some only produce. In my initial implementation, there is only one producer (a dock, where goods are imported from other areas) and one consumer (a retail store, where goods are bought).
  • Cargo. The goods and materials are put into containers (crates, boxes, pallets, etc.) and the containers (labeled C in the diagram) are moved around the game world. Each container represents some amount of material or goods. In my initial implementation, there is only one type of cargo (“goods”) and only one size of container.
  • Loading Areas. A business may not consume goods as soon as they arrive, and it may produce goods that are not immediately picked up. Loading areas (labeled A in the diagram) are a place for cargo to be stored.

I haven't yet chosen good terminology. Is it business or building? Is it cargo or container or goods? Consistent use of terminology will help in picking good names in the code. I want to choose names that are general enough to cover a wide variety of cases.

I think the model has some nice properties. It's very general, so it can apply to many different kinds of businesses. For example, a warehouse is a business that produces the same thing it consumes, and consists almost entirely of loading areas. The loading areas make it easy for the player to see when the transportation system is working too fast or too slow. However, there are a lot of unanswered questions at this point. Does each type of cargo require its own loading area? Does a business buy from just anyone or does it choose its suppliers? How are perishable goods represented? I will leave these questions for later and focus on the simple case: one producer, one supplier, one type of cargo.


Selecting objects in a 3d world #

Once I can move around in my game world, the next step is to interact with objects. I need to determine what object, if any, the mouse points at. There are three general approaches I know of:

  • OpenGL picking. In OpenGL, you can use “selection mode” to identify which object the mouse points at. This involves assigning a number to each object using glPushName/glPopName, then re-rendering the portion of the scene very close to the mouse pointer using gluPickMatrix and glRenderMode(GL_SELECT), then looking at the object numbers that were rendered by reading from the glSelectBuffer array. In theory, you can re-render using exactly the same rendering code. In practice, you want to skip expensive operations like setting up textures, drawing outlines, using shaders, etc. Once you determine what object was drawn at that location, you still don't know exactly where the mouse points. I used this approach in SimBlob 2 and was somewhat unhappy with it. It's easy but it's sort of ugly.
  • Raycasting. The mouse pointer is a 2d location, and it translates into a ray in 3d space. In theory, the ray begins at the camera and goes back into the distance. In practice, the ray begins at the near plane of the viewing frustum and goes through the far plane. You can use gluUnProject to determine where the ray is; use z==0 for the near plane and z==1 for the far plane. Raycasting works well if you have kept the geometry of all of your objects; it's more of a pain if you generate it on the fly (as I did in SimBlob 2). You have to implement ray-object intersection for all of your object primitives (triangles, boxes, etc.), and it helps if you have a scene graph or spatial partitioning tree so that you don't have to intersect the ray with every object in the world. Once you perform the intersection, the closest hit tells you not only which object is involved but where on that object the mouse points. This approach requires the most work but it's the most reliable and has the best accuracy.
  • Depth buffer. Just about everyone is using the depth buffer in a 3d program. Once you render your scene, OpenGL has the depth (z) value at every pixel. You can ask for the z value with glReadPixels. You can then compute the world space location of the mouse pointer using gluUnProject and the z value you just read. The final step is to determine what object is at that location. This approach is easy, but the depth buffer doesn't have much precision, the precision varies among graphics cards, and the depth buffer is altered when using polygon offsets, so it's not reliable. Another disadvantage is that translucent objects get in the way because they show up in the depth buffer.

I started out using the depth buffer approach, but I've switched to raycasting. The depth buffer has too little precision to give me the accuracy I wanted. I also wanted to distinguish between game objects (selectable) and translucent annotations (not selectable), and the depth buffer doesn't give me that level of control.

Labels: ,

Navigating a 3d world #

As I implemented navigation in my 3d world, I had a set of choices to make about how navigation should work. There's a camera with some position (x, y, z) pointing in some direction (θ, ρ) and some type of lens (field of view). That gives me 6 variables for the player to control, and that seems like too many.

  • Scrolling (Panning). If you scroll “up”, what direction does the document go? In most GUI systems, the document goes down. Try it out in your web browser. As you drag the scroll bar up, the document moves down. However, some types of documents move the opposite way. Try visiting Google Maps and drag the map around. As you drag the mouse up, the document (map) moves up. The difference is in what you are dragging. In most applications (including web browsers), you are dragging the view. If you move the view up, you move towards the top of the document, which means the document moves down. If however you're dragging the document, it goes in the other direction. I have been playing Black and White 2 lately, and in it you drag the map. I initially chose to drag the document (map), but then changed it to dragging the view (camera).
  • Scroll controls position or velocity. If you drag the mouse pointer, does it control the position of the scrolling or the speed? If you have Firefox or Opera, try the autoscroll feature and compare it to using the scrollbar. Autoscroll controls the speed; the scrollbar controls the position. The advantage of controlling the position is that it feels easy to control, especially when combined with dragging the document. The advantage of controlling the velocity is that you can move around the entire game world without repeatedly lifting the mouse, dragging across the screen, then lifting the mouse again. Some applications offer both. Google Earth and some OpenGL demos let you drag to control the position, but if you let go while still dragging, it sets the velocity. I find this very hard to control. I chose to make mouse dragging control only the velocity.
  • Rotation. The camera direction has two degrees of freedom, whether you use angles or vectors, so you need two controls for full control of it. Some games restrict the camera, and thus may only need one or zero controls. I chose to fully allow rotation around the z axis and offer minimal control over rotation of the other axis (looking up and down). Given rotation, there is a choice of rotation point. Black and White 2 is unusual in that it rotates and zooms around the position you point to with the mouse. It gives more control but I found it disorienting. I instead chose to rotate around the center of the screen. The best rotation point is likely to be something closer to the camera than what I've chosen, but rotating around the center of the screen is easier to implement.
  • Type of zoom. There are two approaches to zooming. You can change the lens. A “telephoto lens” has a small field of view and corresponds to “zoomed in”; a “wide-angle lens” has a large field of view and corresponds to “zoomed out”. (I'm being a bit imprecise; see this article and the comments if you want the details.) You can also change the position. Moving the camera close to the subject makes it “zoomed in”; moving it far from the subject makes it “zoomed out”. These two approaches are not equivalent. I chose to keep the lens fixed and move the camera around for zooming. Dragging the mouse up or down moves the camera up or down, which also rotates the view somewhat. When the camera is up high, it's rotated to point top-down; when it's near the ground, it's rotated to point forwards.

I started with 6 variables to control. Dragging the mouse occurs in 2 dimensions, allowing control of 2 variables per button or modifier. For a typical strategy game, god game, or city builder, the player can move around the entire map, so you probably want to control camera position (2 or 3 variables), camera direction (1 or 2 variables), and zoom (1 variable). For a first person shooter, the camera must remain at the player's location, so you'd probably want to control camera rotation (2 variables) and zoom (1 variable). For a third person RPG, you probably want camera rotation (1 variable) and zoom (1 variable).

My game is a simulation, so I want to move the camera in at least 2 dimensions, plus 1 variable for rotation and 1 for zooming. I don't allow changing the camera lens, so instead zooming involves changing both the camera height and rotation. That leaves me 4 variables to control with mouse drags. I'm reserving the left mouse button for interacting with game objects. I've chosen to assign the right button to scrolling (2 variables); and the middle button to rotation (1 variable) and zooming (1 variable). These mouse dragging rules make the mouse dragging always control the camera, not the map. They're simple and self consistent. They aren't perfect, but I'm happy with them so far.

Labels: ,

Rough sketch for a transportation game #

As I thought about the things I learned working on the SimBlob project, I realized that I hadn't explored a lot of the topics I originally wanted to explore. I spent my time playing with environmental simulation (water, weather, fires, dams, floods, vegetation, etc.) and never got to anything else. I decided to start over and focus on a few topics in a simple game. In my new project I'm going to explore economic simulation and transportation networks. I have a rough idea of where I'm going, but as I learn things, I expect that the design will change.

There are lots of transportation/economic/city games out there: Railroad Tycoon, Transport Tycoon, SimCity, Simutrans, Locomotion, Transport Giant, Traffic Giant, Industry Giant, LinCity, A-Train, Capitalism, The Settlers, Mobility, and probably many more. There are also many projects in development (some abandoned): Transport Empire, OpenCity, 3DTT, Widelands, Zugspiel, and of course, BlobCity.

My intent is not to clone one of those games, but instead to explore economic and transportation models by writing a game. Throughout history, transportation has affected the development of business and vice versa. The Phoenicians used ships to transport goods, and built a trading empire that lasted a thousand years. The Romans built roads and aqueducts. The Arab empire was based on trade between the east and the west, using caravans and ships. In the United States, railroads greatly altered the flow of goods and linked the west and east coasts. The Panama Canal and Suez Canal helped goods flow by ship. In the late 20th century, advances in transportation made possible the rise of FedEx and the flow of cheap goods from the Asia Pacific region. The use of standard shipping containers linked ship, rail, and truck transportation systems together. None of the games I've tried explore all of these ideas. Have you ever seen a crossdock or Less-than-Truckload shipping in a computer game? I've been fascinated with these topics and would like to explore them in a simulation game.

The basic idea of the game is that businesses trade with each other using an inefficient transportation network (such as people carrying boxes on foot), and the player can offer better forms of transportation. As transportation gets cheaper, the businesses make more money, so they expand. The number of businesses goes down, but the size of the businesses goes up. Increased volume and a change in business structure means the player has to adapt. The player has to choose among hand delivery, hand trucks, carriages, gasoline powered trucks, large trucks (semi-trailer trucks), rail, and ships. As volume goes up, the basic unit being transported gets larger as well, from individual products to boxes to pallets to containers. Upgrading too early is wasteful; upgrading too late is inefficient. Reliable transportation infrastructure can affect how businesses and cities develop. The player has to choose areas of the world to develop, structures to use for each type of good (central distribution, multiple hubs, point to point), sharing among multiple types of goods, temporary storage (warehouses), and modes of transport. As times change, the player has to monitor the efficiency, health, and profitability of the networks and choose which to upgrade, replace, or dismantle. I'm really not sure whether such a game would be fun for anyone but me. I tend to like logistics in games.

Given that game programming is just a hobby of mine (and I have plenty of other hobbies), I think the basic idea is too ambitious for me to attempt at first. Instead I'll design a simpler game and work on that. I've found in the past that if I take big steps, I'm more likely to fall, so I've learned to take small steps. I also don't want to spend forever on this game; I have plenty of other topics I want to explore. Once I've decided my next steps, I'll post them here.

Labels: ,

Getting started, 3d world #

I'm starting a new game project, not because I think I'll write a cool game, but because I want to explore some ideas (economic simulation and transportation networks). I decided to use 3d graphics for two reasons:

  • I want to learn more 3d programming. I've played with GL and OpenGL for a long time but I've never been completely comfortable in a 3d world. Each time I write an OpenGL program, I learn more about 3d graphics programming.
  • Ease of programming. I believe it's easier to work in a 3d graphics system than in a 2d graphics system, until you get to the point where you want artwork. Since I don't expect to have nice artwork, I think 3d graphics will be easier. The graphics card handles things like isometric views, filling polygons, gradients, lighting, and textures. There are simple approaches for mapping screen coordinates to game coordinates and back, because the graphics card does the mapping. It's very simple to alter the appearance of objects for highlighting and mouse manipulation; you can just change the color or lighting. And the CPU is freed up for doing things like AI and world simulation.

I started out writing a simple GLUT program that set up a window and the camera, then drew a simple triangle. Once I got it running, I added stub code for the standard set of GLUT callbacks (mouse handler, keyboard handler, window resize handler). I changed the scene from a simple triangle to a square grid, added a mouse handler that highlighted the current square, and made the right mouse button drag the camera around. I then started refactoring the simple GLUT program into modules (mouse, camera, timer, vector algebra, etc.), added simple lighting, improved the camera dragging code, and added some cubes to the scene. I implemented collision detection between rays and boxes and then used that to highlight the object the mouse pointed to.

Working a little bit each night, I've spent a week on all of this. It's all graphics code and no real game code. Have I gotten stuck in a “tar pit”? No, although there are some things like lighting and gradients that are dangerous to spend too much time on, I think this initial time setting up the 3d world will be well worth it later on.

When I work with programming languages, I really appreciate having an interactive prompt. Lisp, Scheme, and Python are much more approachable because they have this. I can just start Python and inspect variables, create and change objects, explore, test, etc., all without having to go back to my code and insert new commands. You can also do this with interactive development environments (like Smalltalk's). I want something similar at the game level, where I can move around freely and click on an object to see all of its properties. I'd like to create, destroy, and modify objects as the game is running. I don't expect to build all of this at the very beginning, but having an infrastructure that exposes all the game objects in a uniform way will help me later on. How much do I really need at this point though?

Two of the approaches used to uniformly represent 3d objects are scene graphs and spatial partitioning (BSP trees, octtrees, bounding box trees, etc.). Scene graphs are useful for representing changes to lighting, scale, rotation, translation, color, material, textures, and objects with shared components. For example, instead of representing a complex soldier 3d model for each soldier object, you'd store it once and have it occur multiple times in the scene graph, each time with a different rotation and position. Spatial partitioning is useful for collision detection. For example, instead of testing every vehicle against every other vehicle to see if any of them collided, you would partition space into smaller areas and only test vehicles if they are in the same part of the game world. Both scene graphs and spatial partitioning can also be used to render only the objects that are visible in the scene; this can greatly speed up the rendering.

I've decided that the number of objects in my game is small at the moment and is likely to stay small for some time, so I will use the brute force approach. I'll test against every object for collision detection, I'll render every object and let the graphics card figure it out, and I'll replicate geometry (vertices, colors, normals, etc.) for each object. At some point I may need scene graphs and spatial partitioning, and I'll go back and add them in. Code that depends on whether I have a list or a scene graph should remain as isolated as possible, so that I can switch later.

Having written a minimal 3d world rendering system, I'm ready to go back to designing more of the game. While exploring new ideas, I tend to alternate between design and implementation. What I learn from implementation feeds back into the next round of design, and working on the design lets me step back from the implementation to see the big picture.

All the code for this game is open source, under the MIT license.


Getting started, again #

I'm starting a new game project. First, I made a list of my goals (which mainly involve trying out new things). Then I sketched out the idea for a game and thought a little about how it would play and what I would learn by programming it.

Before starting to program though, I started by setting up my programming environment:

  1. Version control. I set up a Subversion repository on local disk. Later: set up a remote repository, either on a web server or using some code hosting service like Sourceforge.
  2. Makefile. I set up a simple Makefile that should work on Linux, Mac OS X, and Windows/Cygwin, using conditional compilation to isolate the platform-specific rules. Later: figure out automake or makemake or one of those other cross-platform build configuration systems.
  3. Notes file. I created a text file where I will keep all my notes. It needs to be something easy to edit and search through. Later: use a wiki?
  4. Backups. I have a script that uses rsync over ssh to copy the Subversion repository to another machine. Later: get an off-site backup solution.
  5. Install VMWare. VMWare offers their Player for free, and they also offer an Ubuntu Linux image for download. It was very easy to set this up. After Ubuntu started up (inside VMWare, running inside Windows XP), I had to install a few more packages (g++, OpenGL+GLUT development libraries, GNU make), but after that I was able to test my code on Linux. I don't have a similar setup to test on the Mac. Later: set up a script that will periodically sync with the Subversion repository, attempt to compile, and email any error messages to me.

After setting up the development environment, I wrote a simple 3D application. I find it much easier to extend existing code than design everything up front and write it all at once, so I start by writing a very simple program that I can then extend.

My next step on the design side will be to write down a more detailed description of the game world, what the player is supposed to do, and why the task is fun/challenging. My next step on the implementation side will be to figure out how I want to represent the game world.


Change of Direction #

As I worked on SimBlob 2 and learned more about 3D graphics, I started changing the game from hexagonal to triangular grids. I then got distracted and started writing an article about grids for my game programming site. While writing the article I realized that there are so many other topics I wanted to explore with SimBlob, and never got around to them. Why?

I spent most of my time in SimBlob 1 (1994-1998) exploring terrain generation, hexagonal maps, water flow, erosion, multithreaded programming, and GUI libraries. I spent most of my time in SimBlob 2 (2002-2005) exploring terrain generation, hexagonal maps, water flow, erosion, and 3D graphics libraries. There's a lot of overlap there. I ended up exploring a lot of the same ideas again. I love those topics, but they've become “tar pits” for me. I get stuck, tweaking and trying out new variants, trying to make it just right. In the end I've learned something and had a lot of fun but haven't gotten much done. Since I am writing games as a hobby, that's just fine, right?

The trouble is that when I get stuck doing one thing repeatedly, I am not spending my time trying out new things. I want to use games to explore environmental simulation, business simulation, city simulation, transportation systems, autonomous agents, machine learning and AI, control theory, and emergent behavior. Of these topics, I've spent most of my time focusing on environmental simulation. I think that was fine the first time, but after recognizing the tar pits in SimBlob 1, I created them again in SimBlob 2, and ended up getting stuck again on the very same topics.

I've decided to stop working on SimBlob 2 and start working on a new game. I'm avoiding the tar pits I've had in the past (terrain, water flow, erosion, hexagon/triangle grids) by having a completely flat grid with square tiles and no water. Sometimes doing something quite different is just what you need. I want to explore 3D graphics some more, but the main focus will be on economic simulation and transportation systems. I expect to find new tar pits to get stuck in. :-)


Polite games #

A few months ago I mentioned that Guild Wars is polite, and as a result, I play a lot more. I still play Guild Wars occasionally. It's so easy to start up, and I don't have to go find the CD.

The two games I've gotten since then are The Movies and Black and White 2 (both from Lionhead Studios). Both of them have long startup sequences. They show me splash screens and advertisements (for Intel and ATI) every time. Then only after the splash screens are shown does the game start loading. At the very least the game should load while the splash screens are up! In addition, the CD has to be in the drive for the game to start. That means it's a major pain to go back and forth between the games.

I find that I'm playing the polite game more than the impolite games. If I'm in the mood to play a game but I have to go find the CD, I'm less likely to play that game. And every time I have to sit there looking at the Lionhead Studios logo, I'm reminded of the company that makes me sit there instead of taking me straight to the game.

Another impolite practice used by many game companies is to use nasty copy protection techniques. I don't get games from the file sharing networks, but it makes me unhappy that pirates are getting a better game experience than I am! (Copy protection gives people more incentive to get a pirate copy instead of buying the game.) What I find totally weird is that StarForce copy protection is even used for game demos. What's the point of making a free demo uncopyable?? StarForce remains on my system even though I've uninstalled the King Kong demo. That's awful. I'm not going to buy any of those games now.

You can find instructions for removing StarForce on this StarForce Boycott site.

Make your software polite, and I'll use it more. Make your software rude, and I'll avoid it.

Update: [2006-03-12] After removing the StarForce drivers, I discovered that my CD-ROM drive was in "PIO" mode instead of "DMA" mode like it should be. This is a symptom of StarForce having been on my system. I uninstalled the IDE drivers in Windows XP and rebooted, and it reinstalled them in DMA mode. PIO mode on some newer drives causes damage over time; I don't know if my drive has suffered any damage.


SRE on the web #

Ten years ago, I lost the source code to Solar Realms Elite (SRE), a game I had worked on. Since then, many people have wanted to build a clone. I've tried to help them, both through email and by posting what I remember about the game's design. However, most of the projects had not gotten very far.

Yanick Bourbeau has built a web version of SRE called Imperium Galactica (which also happens to be the name of an older, unrelated game). It's fairly complete and offers a few things SRE did not (like simultaneous play by several players). I've been playing for a few days and it's fun! The game isn't quite balanced yet, but that will take a little bit of time to fine tune. Try it out!