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:
- 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
swfmillsite:<?xml version="1.0" encoding="iso-8859-1" ?> <movie width="320" height="240" framerate="12"> <background color="#ffffff"/> <frame/> </movie>
- Compile the XML file into an SWF file:
swfmill simple example.xml example.swf
- Create an ActionScript file with your script. I'm using an example I found on the
mtascsite: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(); } } - 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
- 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>
- 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
%.08fto%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