Blobs in Games: programming

From Red Blob Games's Blog

Jobs table implementation for r/roguelikedev project #

In the last post I mentioned that while working on my colony simulator game for the r/roguelikedev summer event, I ran into a situation where my data structures made me unhappy. I was implementing a job system, where a colonist would keep track of what job they're doing, what items they're holding, and where they are standing. It looked like this before I rewrote it:

Labels: programming , structure

Summer r/roguelikedev event #

Each summer the r/roguelikedev community has a summer event in which we all make a simple roguelike, roughly following the Python libtcod roguelike tutorial. Last year I tried to clone Dwarf Fortress in 40 hours. That was too ambitious. But I did enjoy working on a "fortress mode" project more than an "adventure mode" project, so I wanted to do something like that this year, but with a smaller scope.

• Event announcement
• Event conclusion from the participants
• Event summary from the organizers

Labels: programming

Dijkstra's Algorithm and reprioritizing nodes #

I'm working on a tutorial showing how Breadth First Search, Dijkstra's Algorithm, Greedy Best-First Search, and A* are related. I'm focusing on keeping the code simple and easy to understand. {Note: this blog post is a shorter version of a page on my site}.

While tracking down a bug in my Dijkstra's Algorithm code, I realized I had forgotten to implement the "reprioritize" case. That led me to wonder why my code seemed to work without handling that case. It turns out that case is never triggered by the graphs I'm searching over. Let me explore this …

Labels: pathfinding , programming

Porting SimBlob to the web #

I first saw Emscripten a few years ago. It compiled C++ to Javascript. My mind boggled! How cool! This year at Game Developers Conference there was a talk showing that Emscripten plus asm.js could run C++ games in the browser with good performance. I was amazed.

After publishing my article on hex grids, I decided I should do something different for a little while. I remembered Emscripten looked intriguing, and I should try it out. Could I make BlobCity, an OS/2-only game from 15 years ago, run in the browser?

TL;DR: Yes, try it out here!

Here's what I started with, a game that only runs in OS/2:

Labels: emscripten , programming , project

Playing with the dot operator #

Normally the “[]” operator is used for extracting an element out of a sequence. Sequence[Index] turns into *(Sequence+Index) in C. And since + is commutative, it’s also Index[Sequence]. Yes, you can write 3[a] and it’s the same as a[3]. Is that useful? Probably not. But it’s interesting.

I want to talk about the “.” operator. It’s taken for granted, like “[]”, but I think it’s interesting to question how it works.

Normally the “.” operator is used for extracting an element out of a record. In Python it’s two hash table lookups. Given a.x you first look up a in the current namespace (stack frame) to find a record, then look up x in the record. In many languages one or both of these steps are optimized, but I’m going to explore the straightforward unoptimized implementation.

Field lookup

Let’s consider field lookups a.x, a.y, b.n, and b.y. (Note: for simplicity I’m conflating variable names and record ids in the diagrams and sample code but they’re really separate things.) Here’s the conventional view:

In code, we can think of it like this (Python syntax):

values = {} values["a"] = {} values["b"] = {} values["a"]["x"] = 3.14 values["a"]["y"] = 2.71 values["b"]["n"] = "no" values["b"]["y"] = "yes" 

We think of the record as primary and the field as secondary. But does it have to be this way? One of the reasons this layout is preferred is optimization. In a language where record types are known, mapping from field name to offset in the record can be resolved at compile time (like this). This means we can use a simple dereference instead of a hash table lookup. For this blog post however I’m going to ignore optimizability and instead look at the alternatives.

Combined lookup

What if we put both the record id and the field name into a tuple, and made them siblings in the lookup process?

In code, we can think of it like this:

values = {} values[("a", "x")] = 3.14 values[("a", "y")] = 2.71 values[("b", "n")] = "no" values[("b", "y")] = "yes" 

Are there any downsides to this, other than optimizability? It’s a little more work to enumerate the fields of a record but you can mostly do the same sorts of things with this implementation as you can with the conventional implementation — lookup, assignment, field insertion, field deletion. This approach may be useful in some situations but I didn’t pursue it.

Record lookup

What if we made the field name primary and the record id secondary? Back in the 1990s when I was into programming languages (I’ve since recovered), I played around with this idea.

In code, we can think of it like this:

values = {} values["x"] = {} values["y"] = {} values["n"] = {} values["x"]["a"] = 3.14 values["y"]["a"] = 2.71 values["n"]["b"] = "no" values["y"]["b"] = "yes" 

One interesting idea that came out of this experimental language was the idea that the field name could be local to a module or function. (See also: symbols in Lisp packages.) With this feature, you can attach fields to records without needing subclassing. (Ruby’s mixins are some like this except they only allow methods, not data.) Records become only IDs; all the actual data is attached from the outside. (See also: database normalization.)

Imagine being able to attach per-module fields to objects. Imagine being able to treat a “field” just as you might treat an “object” in a regular language: take fields as function parameters, return them from factory functions, import/export them with modules, store them inside objects, etc.!

Use in games

Is this useful in games? I think so. I think it might be related to what entity/component systems are trying to build without having direct language support. The entities are the records and the components are the modules and local data. Consider this data:

Object-oriented systems organize this by column. There’ll be a soldier module that defines a class with x, y, and health, and a beacon module that defines a class with x, y, and color. There will probably be a game object superclass that contains x, y.

When you treat fields as first class constructs in the language, you organize this differently — by row. You’d put the x and y fields into one module, health into another, and color into a third. Code that works with soldiers would import the position and health modules. Code that works with beacons would import the position and color modules. And code that works on either would only import the position module. You can mix and match features — for example, an object with both health and color takes no additional classes or code in this system, because health and color are in separate modules. You keep traditional syntax like soldier2.health; it’s just that health might be a local field instead of a global one, visible only in modules that have imported the health field. You can attach local fields to records at run time and detach them when no longer needed.

It’s quite possible this system wouldn’t work out in practice. I never finished my programming language so I can’t point to a concrete test of the principles described here. The ideas from the experiment have definitely influenced how I write code; that’s the outcome I hope for when exploring an idea. It’s fun to take something mundane like “.” and ponder how else it could work.

Labels: ideas , programming

Switching to Haxe #

Every few years I find a new language/platform for my experiments. I’d like to share them on the web, so I (mostly) limit myself to things that run in the browser. In the 1990s I used Java. In 2004, I started looking at Flash, but continued using Java. With help from Troy Gilbert, I switched to Flash in 2006, using the Motion-Twin Flash compiler (mtasc) instead of Adobe’s compiler. I continued using Flash, switching to Actionscript 3 and Adobe’s Flex compiler, to make Flash 9 and 10 applets. I also used Javascript for some projects. In an alternate history, Actionscript 3 was a possible future of Javascript/ECMAscript but that history didn’t come to pass. It’s a decent language, with things I miss from Javascript: static types, classes, packages, imports, etc. However, it’s time for a change of language.

I’ve switched from Actionscript to Haxe, Motion-Twin’s successor to mtasc. I’ve been watching Haxe over the years but was waiting for the right time. Unlike their mtasc compiler which can be used with the same source code as Adobe’s compiler, Haxe is a new language. It compiles to Javascript, Flash, Java, PHP, or C++, so it can be used for HTML5, Flash, iOS, Android, and webOS clients, as well as C++, Java, Node.JS, or PHP servers. I’m starting to work on new projects that are likely to involve: (1) HTML5 visualizations and games, (2) simple Flash games, and (3) C++ server code, so this seems like a good time to try Haxe. There are also libraries like NME that let me compile Haxe games to Windows, Mac, Linux, HTML5, Flash, iOS, Android, Blackberry, and webOS, if I want to go beyond web projects.

The language itself is nice. In addition to the things I’d expect (closures, packages, imports, classes, etc.), it contains things I’ve missed from my SML/OCaml days: typed unions, type inference, generics, and structural subtyping. It also has other nice features: external mixins, metadata, properties, explicit inlining, and macros. Everything’s an expression; there aren’t any statements. They understand the basics of covariance and contravariance. The compiler is written in OCaml. For a recovered programming language geek like me, there’s a lot going for it. It’s no Haskell or Scala but it’s a big step up from Actionscript. It’s also very … pleasant. I’m not sure how else to describe it.

I’ve not been using Haxe long, but have already had good luck with the multiplatform part, at least for Flash and Javascript. I had an algorithm for a Flash game, and I compiled it into Javascript and used it without any trouble. Since Actionscript, Javascript, and Haxe are all related, it works well. I’m less sure about how well it will work with C++, especially when it comes to garbage collection. There are probably lots of gotchas there. I also haven’t yet figured out how to use Javascript libraries from Haxe code; for my project I went the other way, using my Haxe library from Javascript code I wrote. I’ll learn more as I go.

I think the weakest part of Haxe is the ecosystem. The developers I have talked to so far are great; the language seems to attract good people. There’s a conference, a forum, and an IRC channel. However, the community is smaller than for Actionscript or Javascript: fewer people, fewer books, fewer web sites, fewer tutorials, fewer examples, fewer libraries. A few years ago when I chose Actionscript over Haxe, it was because I thought people would be using snippets of my code in their projects, I wanted to pick a language that lots of people used. That doesn’t seem to be helping me much. Instead, people read the code and learn from it, but write their own code, or they want to use my library as-is. So the number of people using the language is less important to me now. Supporting multiple platforms is becoming more important. With the map generation project, it was frustrating to have written everything for the client (Flash) and then later needing to run it on the server (C++). As HTML5 improves, I’m targeting more HTML5 and less Flash. Both of these tell me that cross-platform is becoming more important for my projects.

My current plan is to use Haxe for code I want to run across platforms, and use Javascript, Python, and C++ for code that is platform specific.

Update: [2013-Apr] Although I still use some Haxe, I'm not using it for cross-language coding much. For my web tutorials, I write in Javascript directly, except for core data structures and algorithms which I write in Haxe or Typescript, to get classes and type checking. For Flash projects, I use Haxe as a nicer Actionscript but I don't use the cross-language features, nor do I use NME for compiling to mobile. By the time I'm ready to write a game, the landscape (Typescript, Emscripten, Asm.js, ASC 2.0) may have changed enough that I'll re-evaluate then.

Labels: flash , haxe , programming

Tutorial: probability and damage rolls #

I’ve been interested in interactive diagrams for a while now, and started playing making illustrations with HTML5. I’ve written a tutorial on using randomness for damage rolls. Implementation notes:

• I’m using Mike Bostock’s D3.js + SVG for the diagrams.
• I’m using Bret Victor’s Tangle library for diagram parameters.
• You can drag the parameters around to change the diagrams. The idea is that you can edit the parameters in the sample code, and see the diagram update too.
• The draggable numbers from Tangle work on the iPad too.
• Most (all?) Android and Touchpad browsers don’t support SVG. :-( (Maybe I should’ve used Canvas)
• Older versions of Internet Explorer don’t support SVG. :-(
• I designed the page to reformat itself for mobile browsers, narrow browsers, and wide browsers. I used CSS media queries for reformatting the text, but unfortunately had to use Javascript for redrawing the diagrams.
• Red Blob Games is where I’ll be placing my new tutorials and articles, instead of my Stanford alumni account.

At some point I’d like to go back to my existing articles and update them with interactive diagrams. I’m just not yet sure where they might be useful instead of gimmicky. I’d also like to write a tutorial about random loot drops.

Labels: math , programming

Switching to Flash 10 #

On this blog you can see some of the experiments I've been playing with. In 2004, I started looking at Flash, mostly because I'd be able to share my experiments on the web. But at the time, Flash wasn't as free or accessible, and I switched to Java. Dissatisfied with Java, I took a look at Flash again, and started writing Flash 8 code. Two years ago I switched from Flash 8 to Flash 9. Flash 9's language (Actionscript 3) is much nicer than Flash 8's language (Actionscript 2). It's a modern programming language, with classes, objects, closures, recursion, XML, JSON, etc., and was tracking ECMAscript until the Javascript folk changed direction. Flash 9's graphics libraries are nicer than Flash 8's. It supports a tree of layers, each with its own rotation, scaling, alpha transparency, shadows, and other effects.

Flash 10 uses the same language as Flash 9. Its libraries have lots more features, especially in the graphics system. There's now a low-level graphics API that offers partial 3D, higher performance, and pixel shaders. I was slow to move to Flash 9 in part because the adoption of Flash 9 was slow. It looks like Flash now has auto-updating, and Flash 10 is being installed much more widely. I'm switching all my current projects to Flash 10.

For Flash 10 I'm using the free Flex 3.3 SDK and the Flex 3.3 docs (online or download). The SDK comes with a command line compiler, mxmlc, that I run with mxmlc -target-player 10 on the “main” program, and that will also compile anything else that is used by the main class. If you want a tutorial for using mxmlc, see senoular's mxmlc beginner guide.

Flex also comes with a compilation shell, fcsh, that lets you keep the compiler in memory to avoid the 2 seconds to start it up every time you want to recompile. I wrote a wrapper around this so that whenever I save something in Emacs, it automatically recompiles. That way, my development cycle is: edit, save, and reload in the browser. It's quite nice to have a fast cycle.

I haven't played much with the Flash 10 library additions, but the first thing I used was the bitmap line support. I'm using it to draw dashed lines as striped lane dividers. I plan to read about the new library features, but not try them until I find a possible use for them in my projects.

Update: [2012-02] [2010-03] Flex 4 is out, and includes updated documentation, and downloadable documentation. Like Flex 3, it targets Flash 10 but can also be used for earlier versions of Flash.

Update: [2013-04] This seems to be the new command line Actionscript compiler, for Flash 11 / Stage3D / AIR.

Labels: flash , programming

Throwing away code #

I've been trying to get better at throwing away code. I used to be a packrat. I saved every receipt, every bill, every check, every bank statement, every page of notes I took in class, every textbook, and so on. Eventually I started letting go of most of these things. Class notes were the hardest though. I had put so much effort into them; how I could throw them out?

I realized that I was making the same mistake that I make with market prices. I expect prices to reflect the cost of making the item. But in many cases, prices reflect what it's worth to the buyer. In this case, I was saving my notes because they cost a lot to produce. But they don't have much value to me in terms of looking things up. I haven't used them in over ten years, and Wikipedia and other online sources are better references. So I finally threw away my class notes.

I find that I have the same problem with code. It takes effort to write, so I feel like I should save it. But sometimes it's the wrong code or it's solving the wrong problem. There are times when the best thing to do is to throw it away.

To make it easier to throw away code, I'm trying to reduce the cost of producing it, especially when I'm less sure about how long I'll need it or whether it's the right way to go. This is not only helpful for me psychologically, but I think it's the right thing to do engineering-wise. Note that this is the opposite of the conventional wisdom — that you should put lots of effort up front into “doing things right”, because it'll pay off later.

Keeping costs down recently paid off for me.

While playing Transport Tycoon a few weeks ago, I was thinking about modular airports, and how it related to my transportation mini-game that's on indefinite hold. I'm not working on any games right now, but instead working on little bits and pieces that might end up being part of a game. Or at the very least I'll learn a lot by working on these components. One of the open questions I've had when thinking about a transportation game is how I should represent roads and vehicles (or rails and trains). I sketched some ideas on paper, and then decided on a representation of road segments:

 public class Path { public var id:int; public var next:int; // index // Positions are in world coordinates, not Flash coordinates public var beginPosition:Point; public var beginOrientation:Point; public var endPosition:Point; public var endOrientation:Point; public var length:Number; public function Path(id_:int) { id = id_; } } 

I then set up some test segments and made vehicles go around on them:

I had convinced myself that inside an airport or container port, the vehicles could move around in loops, and that would be sufficient for a game. Even if I needed branching, I could change my Path class from having a single next pointer to multiple next pointers.

I was quite happy with the vehicle and road representation. I had a coordinate system that allowed vehicles to detect if someone's in front of them, and to slowly come to a stop before they collided. By using a loop I had eliminated the problem of start and end points.

A few days later I tried sketching out what the player would do. It turned out that there wasn't much. I spent some time thinking about why Transport Tycoon's station management was interesting, and my prototype was not, and realized that what's interesting is updating the station over time to deal with changes in the game world. If players spent most of their time on updates rather than initial design, the road shouldn't be a loop. It should support adding temporary routes, closing existing routes, demolishing routes, building new routes, and so on. Those operations work better with a completely different representation of roads. And that meant I should throw away my representation and associated code (rendering, etc.).

If you look at the class I wrote, it's trivial. Everything's public. There are no getters and setters, no methods, a trivial constructor, and no tests. I tried hard to follow YouArentGonnaNeedIt and DoTheSimplestThingThatCouldPossiblyWork. Throwing it away is easy, because there's so little work put into it. Having the old version saved in version control helps me feel okay with removing the code in the current version.

Although I'm throwing away code, there are some ideas I'm keeping. I learned some things, and the first approach is what got me thinking about the new approach. The process was valuable, even if the code was not. And I've started working on the next approach, which I'll try to keep as simple as the first one. I still have a packrat instinct, but I'm working on conquering it.

Labels: programming

Learning Flash 9 #

This week I switched from Flash 8 to Flash 9.

Since last year I've been playing with Flash 8, using the Motion-Twin command-line compiler mtasc. I was using it to write a transportation game, and I had something running and was making progress, until Supreme Commander came out. Then I went back to playing games instead of writing them. Although I'd still like to work on that game, I've found that I also want to use Flash to build interactive demonstrations of concepts I describe on my site. For example, in my article about grids I'd like to make those diagrams interactive so that you can better see how the coordinate systems work. Diagrams are now what I'm using to learn Flash; I may go back to the game later (or maybe not).

I like mtasc. However, it only supports Flash 8 (Actionscript 2), and is not going to be updated for Flash 9 (Actionscript 3). It's a dead end. Flash 9 is not only significantly faster (almost as fast as Java), but it also has major changes to the libraries. Instead of mtasc, you can use HaXe, which is a new language similar to Actionscript/Javascript/ECMAscript. HaXe looks neat (better types, type inference), but it's a different language, not Actionscript. Part of my goal is to publish my source code so that others can use it, and it's less useful to publish code that isn't usable in Actionscript. It's also less useful to publish code that requires an expensive development environment (for example, Flex, at $500). And it's easier to learn a language when there are lots of other users, posting tips. So I've been staying with mtasc; the same code works with both mtasc and the Flash 8 development environment.

Last week Rich Collins pointed me to the free command-line Flash 9 compiler, mxmlc. Wonderful! It's free, it's Flash 9, it's command line—just what I was looking for. I spent a few days learning about Flash 9, and found this tutorial and these tips to be most helpful. My initial thoughts:

• (yay) Flash 9 has much better libraries than Flash 8. The sprites (movieclips), the event handling, and the graphics commands are all nicer.
• (boo) Actionscript 3 is more verbose than Actionscript 2, with types, packages, public, override, and other annotations. It's less of a scripting language and more like Java. This is bad.
• (yay) Flash 9 is much faster than Flash 8, in part thanks to all those type annotations.
• (boo) The mxmlc compiler is significantly slower than mtasc, in part because it's written in Java, which has a high startup time.
• (boo) The mxmlc compiler is not open source.

I've been converting some of my code from Flash 8 to Flash 9, and despite the increased verbosity, I've been happy with it. If you want to use Flash 9 with free command-line compiler, start with this tutorial.

Update: [2007-07-28] [2010-03-25] You can download the Flash command-line compiler (Flex mxmlc) for free, without registration, from Adobe. Once I learned the language, the Flash 9 library reference became my #1 source of information.

Labels: flash , programming , project

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

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

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

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

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

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

Water simulation #

One of the most fun things about SimBlob is the water simulation. It isn't great though, and I keep looking for ways to make it better. Using the Navier-Stokes equations is the “right” way to simulate fluids, but they're complicated and expensive, so many people have come up with approximations or alternatives. Here are some resources:

• Fluid Dynamics Model (includes demo for Windows)
• Fluid Dynamics with Erosion
• Real-Time Fluid Dynamics for Games
• Reflections on Water Simulation
• Practical Animation of Liquids

None of their solutions directly works for me, since I'm using a hexagonal grid and have a dynamic landscape underneath the water.

[2005-07-11] Update: I tried some approaches based on the above, but they didn't work for me. It's quite possible that I'm missing an essential step in my simplification.

Labels: programming , project

Fonts in OpenGL #

GLTT looks like a fairly easy to use library for rendering TrueType fonts into an OpenGL world.

Labels: programming , project