Blobs in Games: 2007-06

From Red Blob Games's Blog

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

Distances on a triangular grid #

As part of my article on grids, I'd like to provide basic algorithms for grids. I already know how to compute distances on square and hexagon grids, but I didn't know how to compute them on a triangle grid. I initially tried changing coordinate systems, inspired by Charles Fu's coordinate system. I normally use the coordinate system from my article on grids:

The first coordinate (which I will call u) is the position along the horizontal axis; the second (which I call v) is the position along the southwest/northeast diagonal. The Left/Right parity introduces some compliation; I let R be 1 and L be 0. This coordinate system is nice for storing maps in an array, but it's not as clean, because triangle grids have three axes but only two of them are expressed in the coordinates. For the horizontal axis I used 2u+R as the position; for the second axis I used 2v+R. I guessed that the position along the third axis would u-v. I drew some grids on paper, wrote down the u,v values, and then computed the three positional values. They behave properly for computing distances along the third axis, but the system falls apart when computing distances not on the three axes.

Frustrated, I decided to step back and approach this problem in a more principled manner. In Charles Fu's three-axis coordinate system, taking one step in the grid changes two of the coordinates and leaves the third alone. For a triangle grid, the dominating feature is the straight lines in three directions. I looked on the web for any articles describing distances on triangular grids, but didn't find any that satisfied me. This paper was promising but unfortunately gives an iterative algorithm and not a clean formula. However, it uses an interesting coordinate system, which is useful for computing distances. If you take one step in the grid, you will cross exactly one line. The distance between two locations will be the number of lines you have to cross. I wanted to use a coordinate system in which crossing a line changes a coordinate:

I want to map the u,v,R coordinates I normally use into the alternate coordinate system a,b,c, where exactly one of a,b,c changes when you cross a line. Here's where I decided to use algebra. In u,v,R space, the black triangle has coordinates 0,0,0; the triangle to the east of it has coordinates 0,0,1; to the west, -1,0,1; to the south, 0,-1,1. In a,b,c space, the black triangle is 0,0,0; the east triangle is 0,0,1; the west triangle is 0,-1,0; and the south triangle is -1,0,0.

I want a formula that computes a, and I expect it to be linear, so I write a = au*u + av*v + aR*R + constant. That's four unknowns, but we know the constant will be 0, so it's really three unknowns. To get three equations, I plug in the values for the east, west, and south triangles, then solve for the coefficients. Let's see what happens:

  For each s in (a, b, c), and each triangle i:
  si = su*u + sv*v + sR*R

  East triangle: u,v,R = 0,0,1
  s1 = su*0 + sv*0 + sR*1
  therefore: sR = s1
  
  West triangle: u,v,R = -1,0,1
  s2 = su*-1 + sv*0 + sR*1
  therefore: su = sR - s2
  
  South triangle: u,v,R = 0,-1,1
  s3 = su*0 + sv*-1 + sR*1
  therefore: sv = sR - s3

When s is axis a, we look at a for triangles 1 (east), 2 (west), and 3 (south), so a1 is 0, a2 is 0, and a3 is -1. The algebra tells us that aR = 0, au = 0, and av = 1. That means the formula is a = v. Pretty simple. Doing the same for b and c, I get b = u and c = u + v + R.

These results are simple enough that if I played with the grid enough, I would have come up with them. However the algebraic approach works for other constraints, not only the simple ones. I also used it to create a coordinate system with 2u+v+R, u+2v+R, v-u (this is 30 degrees rotated from the one above), which may be useful for other algorithms. Algebra and calculus also come in handy for defining movements (e.g., splines), growth rates, equilibria in interacting systems, and other types of interesting behaviors in games.

What is the distance between two locations in a triangular grid? Each step involves a line crossing, and we want to count steps, so we add up the line crossings along each axis (a, b, c): distance = abs(Δu) + abs(Δv) + abs(Δ(u+v+R)). This looks just like the Manhattan distance formula, but for triangles instead of squares.

Labels: grids , math , triangles