Blobs in Games

From Red Blob Games's Blog

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.

Labels: programming

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.

Labels: design

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 OSFlash.org, 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"/>
     <frame/>
   </movie>
   

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
           _root.createTextField("tf",0,0,0,320,200);
           // write some text into it
           _root.tf.text = "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 example.as -swf example.swf -main
   

5. Embed the SWF into a web page using the <embed> tag, as described on the haXe site:

   <html>
   <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"
     pluginspage="http://www.macromedia.com/go/getflashplayer"
   />
   </object>
   </body>
   </html>
   

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: flash , programming , project

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.

Labels: programming

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.

Labels: programming

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.

Labels: review

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.

Labels: design

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.

Labels: programming

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

Labels: review