Sunday, July 22, 2012

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:

SVG diagrams may not show up in feed readers - view original.varsStack FrameName“a”“b”Recordrec1Record “a”Field“x”“y”Value3.142.71vars:rec1->rec1:rootrec2Record “b”Field“n”“y”Value“no”“yes”vars:rec2->rec2:root

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?

GvarsStack FrameName“a”“a”“b”“b”Field“x”“y”“n”“y”Value3.142.71“no”“yes”

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.

GvarsStack FrameName“x”“y”“n”FieldxField “x”Record“a”Value3.14vars:x->x:rootnField “n”Record“b”Value“no”vars:n->n:rootyField “y”Record“a”“b”Value2.71“yes”vars:y->y:root

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

Thursday, July 05, 2012

For one of my projects I wanted to calculate the areas that are visible from the player. In a 2d top-down game or an isometric game you can calculate visibility and lighting in 2 dimensions and store it in a bitmap. As usual I got distracted by writing about the algorithm. I've spent too much time on writing it up so I'm going to publish it even though I'm not quite happy with the explanation. I can revise it later.

Here's the algorithm for 2d visibility along with a demo and source code.

Notes about the process

Part of what took a long time was going back and forth between the demo and the tutorial. The demo showed some concepts, then the tutorial tried to explain them. Then I realized that I'm missing some concepts and need to update the demo to show them. This took quite a bit of iteration.

A nice side effect of trying to explain the algorithm is that it helped me improve the algorithm. In an earlier version, sorting lines of different sizes didn't work well. It wasn't a problem in my project because all the lines were the same size, but in the demo it was an issue. While trying to explain this I found a better way to sort the lines so that it worked on all lengths. Another corner case that doesn't work well is when the lines intersect. This also doesn't happen in my project but it can happen in the demo. I decided the solution would complicate the demo code too much (I want it to be reasonably readable) so I instead detected those corner cases and marked them in the demo.

The other thing that took so long was that I kept rewriting the UI portion. The original version was for an isometric game, and used shaders to project the light map onto the 3d world. Next I wrote a Haxe + Canvas implementation to run as part of the article, but decided that I should write the UI in Javascript directly because I was more familiar with it. I kept the core algorithm in Haxe (shared with my Flash projects) and wrote the UI in Javascript + d3.js + SVG. It was easier to work with but it ran too slowly on the iPad, and as much as I love d3, this isn't a great fit. So I then wrote a JqueryUI + Canvas implementation. That too was slow but after learning more about Canvas I was able to speed it up to run reasonably on the iPad. I learned a lot by trying different languages and libraries; I hope not to spend several months on the next tutorial.

Other articles

After writing this for my project I decided to look around and see what other people have done. I didn't find a comprehensive survey of techniques but there are several interesting techniques out there. Here's the raw list from my notes; I haven't spent the time to categorize or evaluate them (sorry!). I've also added to the list after posting my page.

Labels: ,

Saturday, June 16, 2012

WoW auction house
(image from NecroRogIcon on Flickr)
, CC BY 2.0

I used to play the auction house part of World of Warcraft. I noticed that when I want something as a trader, I'm often willing to wait the 24-48 hours with a “bid” offer. But when I'm crafting or just wanting to play, I'm less patient, and I prefer the immediate gratification of the “buyout” offer. When I was selling, I'd just set the bid to be slightly below the buyout, but I'd also have multiple overlapping offers at different prices, different time periods, and different stack sizes.

There's an asymmetry between the buyer and seller in WoW's auction house. Sellers don't need immediate gratification. Buyers do. The “buyout” feature is used a lot. There's no corresponding “sell immediately” feature.

This isn't a new observation. EBay started as an auction site but now has a lot of traffic using “buy it now”. The difference is that in WoW, buying something is even more immediate — you walk to your mailbox and have a shiny new sword waiting for you — with no waiting for shipping.

If I were designing an efficient marketplace for a game focused on the buyer, I'd simplify. If all I want to do is buy a Fire Sword, what do I need to know? The lowest price. I don't need to know all the listings and who made them. I don't need to know the listing time period. I don't need to know all the higher prices. I don't need the complexity of bidding and the waiting time.

What do I do with the following table? Decide which item I want. Also, decide whether to pay more to get an item now or wait a bit and pay less. Also, if waiting a bit, there are multiple options for how long to wait and what the price is. Also, estimate the risk that I may not win the auction because someone outbids me. Also, should I buy two at a discount and then re-sell one of them?

ItemNumberLevelLow bidCurrent bidBuyoutTime LeftSeller
Fire Sword1331374514:31Stoneplanter
Fire Sword132339519:27Azlishan
Fire Sword131861781:35Morianna
Fire Sword2533748838:03Flyv
Fire Sword133438608:53Sven
Ice Sword41811031304:39Linkshot
Ice Sword411010514910:30Mordn
Ice Sword41951091453:46zxcv

What do I do with the following table? Decide which item I want and whether I'm willing to pay that price. That's all.

ItemLevelLowest price
Fire Sword345
Ice Sword4130

On the other hand, complexity adds friction. And friction adds inefficiency. And sometimes you want inefficient markets because they're more interesting for gameplay. The trading game is fun! You can play with multiple prices, different stack sizes, overlapping time periods, cornering markets, hedging, reselling for profit, etc. It's just not a great interface for someone who just wants to buy a sword. Unless trading is a big part of the game, I'd want something really simple. Tell me what I can buy and what the price is.


Thursday, May 03, 2012

I’m becoming somewhat pessimistic about the game industry. [Warning: these thoughts are a bit fuzzy.] Here’s what is going through my mind:

  • The demand for games has gone up dramatically in the past few years. Wii, Steam, XBLA, mobile, browser, tablet, and social games have brought in lots of new players.
  • High profile successes like Farmville, Angry Birds, and Minecraft have made more people interesting in making games.
  • New platforms and the rise of indie gaming has brought in lots of new game developers.
  • Making and distributing games is easier than ever, especially on some of the new platforms. The barriers to entry have come down.
  • Venture capital, angel investors, and Kickstarter are enabling more game developers to build games.

The demand won’t continue rising as fast as it has been, but supply, lagging behind, will continue to rise for a few years. We’ll end up with too much supply.

What happens when we have rapidly rising demand, but the supply hasn’t caught up? Profits rise and economic surplus goes to the producers (developers and publishers). That brings in more developers. What happens when demand levels off, and developers are pumping out lots of new games? Profits fall and surplus goes to the consumers.

Making things worse, in some markets there’s a “winner take all” effect. There are just too many games to evaluate them all, so I’m going to turn to recommendations. If you play Draw Something instead of Storylines, then I’m more likely to play Draw Something instead of Storylines. If you play Castleville instead of Idle Worship, then I’m more likely to play Castleville instead of Idle Worship. If you play Terraria instead of Junk Jack, then I’m more likely to play Terraria instead of Junk Jack. The games that are played most get written about the most, get on the top of the app store lists, and get recommended more by friends. Those games will get played even more. It’s a “rich get richer” feedback loop.

In a winner take all market, there will continue to be big hits — the Farmvilles, the Minecrafts, the Skyrims, the Angry Birdses. Everyone will see the hits and think they’re going to make it big too. The problem with seeing only the hits is that it skews expectations. If all you see is the head of the distribution, you can’t tell how long the tail is. How many kids expect to make it into the sports big leagues, and how many make it? How many people expect to make it big in Hollywood, and how many actually do? How many people expect to win the lottery, and how many do? How many garage bands make it big? You tend to hear about the successes more than the failures. This will draw even more people into game development.

There will be more games than anyone can keep track of. If your game isn’t succeeding, you need more marketing, more press, more paid introductions, lower prices, and more gameplay for free. You need your game to succeed over all the others, so you need to pour more money into it. This money will be raised both investors, from Kickstarter-like systems, and internally by publishers with deep pockets.

I worry that it’s not sustainable. The other guy invests more in marketing, and then you have to invest more in marketing. You end up running in place, with ever-increasing costs. Eventually the people putting money into projects will see that most of them aren’t paying off. That money will dry up. And a lot of game companies will collapse.

On the flip side, it’s going to be great for consumers. Players will get more entertainment for less money. Why play game X for $5 when I can play a similar game Y for free? There’s always another game around the corner. If you want more polished games you can find them. If you want more innovation you can find that too.

I’m looking forward to seeing a million games out there. I just worry a bit about the people making them. Three times as much revenue divided among (guessing) ten times as many developers? Some will do well; most probably won’t. Am I too pessimistic?

[2014-05-12] See this comment from Dan Cook and this article from Jeff Vogel.

[2016-11-17] See this blog post from Dan Cook


Sunday, April 15, 2012

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

Friday, February 24, 2012

Some of you have sent me feedback on my polygon map generation blog post series (part 1, part 2, part 3) and questions about how it could be used in your own projects. Here are some thoughts on how to extend the map generator:

  • I want to generate a tile map, but this project only generates polygons. The map generator uses polygons to create structure, but that structure can be converted back into tiles or bitmaps. The developers of Realm of the Mad God wanted a 2048 X 2048 tile map. They wanted the elevation and moisture data in a 2-dimensional array so that they could generate their own biomes, monster zones, and vegetation. The solution is to render the polygons into a bitmap, and then extract the color data into an array. The source code includes a function makeExport() to export the polygons in array format, but I omitted this from the demo, for simplicity. Here’s a demo with the export feature enabled.
  • I want to generate the map on the fly, like Minecraft. The main reason I used the polygon approach was to create large scale structures: mountains, rivers, roads. A purely local map generator has no knowledge of other areas, and thus does not generate good large scale structures. A possible solution is to use both. Use something like the polygonal map generator to generate the large scale structure with low resolution, exporting thresholds and other parameters. Then use a local Perlin map generator that uses those parameters to generate the small scale structure at high resolution. For example, you might use the polygon map structure to generate a 1000 X 1000 biome map, and then each of those 1,000,000 zones could itself be a 1000 X 1000 locally generated map. That’d give you a 1,000,000,000,000 tile map that you can generate on the fly, with only 1 MB of additional storage for the large scale structure. I’ve done a few experiments along these lines but don’t have anything to show yet.
  • I want to have objectives, quests, goals, etc. on the map. This is one reason polygons are so appealing: they produce a notion of “area” or “zone” that you can use for creating high level game structures like towns, quests, or territory to conquer. The demo used the structure to create roads. Realm of the Mad God uses the structure to place quests. The ways you can use the polygons are game specific so it was hard to make a good demo for it.
  • I want to implement pathfinding. If you’re rendering the polygon map into a tile map, you can use these two levels for hierarchical pathfinding. Use Floyd-Warshall to precalculate all paths between all polygons, then use A* or another algorithm to compute the local paths on the tile map.
  • I want to have unpassable terrain. In Realm of the Mad God, all biomes except lakes were walkable, so I didn’t implement interesting obstacles in the map generator. I think the types of unpassable terrain will vary by game, but both polygons and edges should be useful high level structures to make unpassable areas like cliffs, mountains, caves, lakes, fences, walls, and chasms.
  • I want my designer to draw the island shape. The map generator can handle any boolean assignment of polygons as land or water. I included four algorithms (Radial, Perlin, Square, Blob) to demonstrate that it’s not tied to a single algorithm. You can write your own code in the IslandShape class, including something that uses a custom hand-drawn shape.
  • I don’t want the mountains centered. I experimented with non-centered mountains, but for Realm of the Mad God they wanted the mountains in the center, for gameplay reasons. I think non-centered mountain ranges would be more interesting, and I believe they would work well in this map generator. The main constraint is that that river algorithm requires a monotonically decreasing elevation from the mountains to the ocean (e.g. no local minima). In practice that means you could move the mountain range to one side or the other, but the river algorithm would get confused by valleys with no outlets. A more complex river algorithm could handle local minima.
  • The borders between polygons are too noisy. This is controllable by a parameter, NoisyEdges.NOISY_LINE_TRADEOFF. I should have made this controllable in the demo. It should vary by biome, elevation, and moisture level.

In my git stash I have several other experiments I’d like to play with one of these days. I don’t plan to experiment more until I am helping another project that needs maps. It’s easy to dream up things people might need. It’s much more rewarding to work on the map generation when I know it’s being used in a game.

[Updated 2012-04-11 to clarify that “render to bitmap” then converts the elevation and moisture data into arrays, which are exported.]

Labels: ,

Monday, January 23, 2012

Last month I described the reasons I don’t like the maps in Skyrim. Below are some maps from Kingdoms of Amalur: Reckoning, a game that’s been compared to Skyrim.

Here’s the world map in the game:

It shows where I am, the areas I’ve discovered so far, my current destination, areas of the world along with their names, and ways to travel between areas/zones. The map uses light shading and subtle texturing to keep the main areas clear and readable. Non-walkable areas are darker and strongly shaded to distinguish them from the main areas.

Here’s a local area map in the game:

It shows where I am, portals, merchants, healers, NPCs (white circles), dungeons, roads (main and side), shrines (green circles), and things I’ve spotted but not investigated yet (brown boxes). The investigation spots only show up if I’ve leveled up an exploration skill. In the northwest an area is dark because I haven’t explored it yet. Walkable areas are tan or gray, with subtle texturing. Non-walkable areas and unexplored areas are dark.

Here’s another area:

It shows larger and smaller roads, two bridges, a river, and monsters I’ve spotted. The monsters only get placed on my map if I have leveled up an exploration skill. Several areas fade to black because I haven’t explored them yet.

I love these maps! They are clean and easy to read. They show what’s important. They omit irelevant details (clouds, rocks, trees, plants). They’re updated as I explore and discover new things. They help me figure out where to go and how to get there.

How well do these maps answer the questions from my post about Skyrim’s maps?

Player questionAmalurSkyrim
Where have I been?places, zones, roadsplaces only
What areas have I missed?area map onlyarea map only
What have I done?nono
Where can I find resources?some *no
Where can I get some product/service?yesno
What do I want to return to?nono
Where have I been told to go?one questall quests
What are the main areas?zones onlyzones, lakes, rivers, towns
What locations have I been told about?(don’t know)places only
How do I get to a specific place?yesno
How long would it take me to get somewherenono
What dangers are along various paths?in area map only *no
Where are events occurring?N/AN/A
What has changed?nono
What did I miss?N/AN/A
* requires leveling up an exploration skill

I only played the demo for a short time, so it’s possible I’ve missed some aspects of the maps in Kingdoms of Amalur. I’m finding the maps to be much more useful than the ones in Skyrim.

Labels: ,

Sunday, January 22, 2012

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