Planet Color Studies

I'm continuing to work on optimal control for rockets. Practical Methods for Optimal Control and Estimation Using Nonlinear Programming looks like a very good book on the subject. I just got a copy, but I found a PDF of it online somewhere that convinced me it was worthwhile.

In the meantime here are a couple of color studies for 2D planets:





Which of the following two options would be better?

• Always show planet in cross-section
• Have a foreground layer that fades away when the player is underground

A foreground cap could add to the exploration aspect of the game by hiding underground tunnels. On the other hand I'd have to draw a spherical planet on it or something, which would be tricky to do well.

How would you write an AI rocket pilot? This is what I've been thinking about for the past few months in my spare time. I've been reading some books and papers about optimal control, and am still learning and collecting my thoughts, and writing code. So this is just a brief update.

A few years back I did some work in this direction. The rocket is treated as a point mass that can instantaneously accelerate in any direction, with a limit on the acceleration. One control problem is: given a starting state (position and velocity) and a desired final state (position and velocity), fly the rocket between the two states in minimum time. (No gravitational acceleration in this simple scenario.)

When I wrote that last page I conjectured that the optimal route would consist of accelerating in one direction for a duration and then (if necessary) accelerating in a second direction for an additional duration. (Flying two parabolic arcs, essentially.) I based this on an attempt to extend the one-dimensional optimal control, which is to accelerate in one direction at maximum for a duration, and then potentially reverse direction and accelerate for an additional duration.

Since reading some optimal control theory I've worked out enough to realize that this is not the optimal control. The optimal control turns out to be to thrust (with maximum acceleration) in the direction of a point that is moving along a straight line. The point is moving through a "control space" and you basically normalize the vector toward it and multiply that by the maximum acceleration to get the acceleration vector. You can see how the one-dimensional case extends to this, but in the two- or three-dimensional case the rocket potentially pivots through a range of directions as it accelerates. The trick, then, is to come up with the equation of motion for the control point that results in the rocket getting from the initial state to the final state.

That's all I have for now; hopefully more to follow.

iOS: New Orbit

Just ran across this iOS release. It's a brief space game called New Orbit, from a guy in Austria named Markus Hofer. I had a blast playing it for the couple of hours it took to get through it; it's currently priced at a dollar so if you have the appropriate device and like space games do check it out.

Control is straightforward; touch the screen and your rocket will accelerate in that direction. Physics is Newtonian, so there isn't any drag or maximum speed. The missions keep things fairly focused, though, so you don't have huge velocity changes. The rocket displays its current velocity vector and has a trail display. Asteroids exert gravity, so it's possible to enter stable orbit or land. Other space-game staples like mines (both the ore-extraction and munition sorts) make appearances as well. One of the nice interface touches is that off-screen asteroids are indicated with a bar on the edge of the screen. The bar's length represents the asteroid's subtended angle, so it gives you an idea (assuming you know how big the asteroid is, roughly) how far away it is.

New Orbit has the feel of being the tutorial for a much bigger game; a game that isn't made yet, unfortunately. You don't ever acquire weaponry of your own, for instance, and mining equipment is introduced in one mission and then never used again. What's there is quite polished, though.

In contrast to a lot of the 2D space games (like Flatspace or Captain Forever or Escape Velocity) this one's very story-oriented. It takes you through a linear sequence of missions without room for running around. I thought the story was very entertaining: well-written and well-voice-acted (so far as I could hear with the volume turned low); the whole game sounds like it's being acted by Arnold Schwarzenegger and his buddies since it's all read in Austrian accents. I liked that quite a bit, actually.

Hopefully Mr. Hofer and crew will develop further chapters in this game. In the meantime it's still well worth playing.

Lead, Follow, or...

(map 'map-leader-test.tga')

(player (pos 17 12))

(torch (pos 19 11) on)
(torch (pos 19 13) on)
(torch (pos 46 34) on)
(torch (pos 54 34) on)
(torch (pos 68 68) on)
(torch (pos 68 76) on)

(lamp (pos 58 51) on)
(lamp (pos 63 51) on)

(leader (patrol (pos 13 12) (pos 49 36) (pos 72 72)))

I've been plodding along on work with ThiefRL. Mostly stuff that didn't add any new gameplay. Pathfinding is a bit faster, for instance. (I cut out a ton of heap allocation during path computation.) A level loads from a combination of a bitmap and a text file now, instead of being compiled into the executable. The bitmap (an enlarged sample shown above) specifies the base ground tiles, and the text file (also shown above) specifies the rest of the objects. It's much easier to lay out a level in a bitmap editor, although I will probably eventually have to break down and write my own level editor to gain additional productivity.

Via Harry Connolly's blog I encountered an essay by author Rachel Aaron: How I Went From Writing 2,000 Words a Day to 10,000 Words a Day. I follow a bunch of writers' blogs because they deal with similar productivity issues to mine. This article has inspired me. The thrust of it is:

1. Plan what you will do before you do it
2. Keep productivity records (and examine them for trends)
3. Find something to be enthused about in each session's work

I've decided the most crucial thing to do right now is to prototype the gameplay elements I'm considering for ThiefRL but haven't yet nailed down. Think of them as the “verbs” of the game. This will enable me to figure out which things will work together which will then enable me to organize a game.

To that end I have put together a leader behavior (aka Call of Duty mode). I'm thinking that, in the early parts of the game, you might have a friendly character lead you around as part of training in how to hide, evade guards, etc. They might also point out the locations of compounds you'll be infiltrating later and give a bit of story about what they are.

The basic behavior is that the AI wants to get to a particular spot but they also want to be close to the player. Being close to the player takes priority, but once they're close enough they will head toward their goal. Once they arrive at their goal the player has to speak to them (by bumping) to trigger the next thing.

Next I'm going to adapt this into a frog-march behavior. The idea is that a guard has hold of the player and is forcing them to walk in a particular direction. It might be tremendously un-fun but I'm going to try it as it represents a possibility for softer failure conditions. It might also work as a movement tutorial in the very beginning of the game.

Circle of Enemies

Harry Connolly's third Twenty Palaces novel Circle of Enemies came out in August. As usual I read it pretty much in one go. I was dealing with my father's cancer and shipping a game for Halloween, though, and didn't get my review out at the time.

Connolly's series pits Dashiell Hammett's lowlifes against Lovecraft's horrors. Every blood-free page racks up a tab that will be reckoned before long. The monsters are inventive and varied. They're not evil, just higher than man in the food chain. Let one into our plane and you let a fox loose in a hen house. There is always someone who is willing to make gamble that they'll be able to control a monster for personal profit, though.

Ray Lilly is an ex-con who, between stints working at a supermarket, serves as muscle for a shadowy association of wizards (the eponymous Twenty Palaces society) dedicated to the undercover eradication of eldritch incursions. His wizard boss has outfitted him with some protective tattoos but doesn't otherwise place a high value on his life. Ray looks out for himself, though; a peek into a spell book at one point allowed him to construct a ghost knife, which is a laminated piece of paper inscribed with a spell. It's a bit of a “Deus Ex Pagina” in the stories but overall the magic system in this world seems well-though-out without being explained to death.

In Circle of Enemies Ray is drawn back to LA from his home in the Seattle area. Someone or something is killing the members of his old gang and they blame him (with cause). It's good to see deeper interpersonal relationships in the book. Connolly is a lot like Hammett in not romanticizing anyone; they're all just people and none too good.

I've followed Connolly since the publication of his first novel (I discovered him through the great Big Idea essay he wrote for it). He's published a prequel novel for this series which I haven't gotten to yet, and is working on a fantasy novel at the moment. I've read a bit of his short fantasy fiction and it's deliciously dark, so I'm looking forward to seeing what he comes up with.

Path Symmetry

The past couple of weeks I've been wrestling with video editing in order to put together a very short video for my father's memorial service. The state of video codecs and containers (in terms of what can go in what, and which platforms support which) is truly awful. Go software patents, eh? Spurring innovation and so forth.

Windows Movie Maker also turns out to be truly awful. I wasted way too much time. You get what you pay for, I suppose. I ended up purchasing AVS Video Editor, which I'm not linking since it also seems to be only intermittently functional.

In the meantime I came across this interesting article about speeding up A* pathfinding on a grid: Jump point search.

Daniel Harabor makes an excellent point: Having lots of equally-good paths between start and destination just kills A* performance because it must examine every possibility on the chance that one of them turns out to be superior. Here's an example of a situation where there are multiple possible paths (one of which is highlighted):

The path must consist of four horizontal moves and three diagonal moves, but they can be made in any order. Imagine a deck of seven cards, four of which say go east and three of which say go northeast. There are 7! ways you can order those cards. Since there is no difference between the go east cards or between the go northeast cards you divide out by the number of ways you can order those. This is 7 choose 3 (or 7 choose 4), which is 7! / (4! * 3!). The end result is 35 distinct paths. (One of my programming interview questions is about this sort of thing, by the way.)

Daniel speeds up A* by navigating the search space in such a way that only one style of movement is ever used: diagonal moves first, followed by the horizontal or vertical moves. His article is a bit misleading because he is plotting only the nodes that go into the "open" priority queue, and this number is vastly lower with his approach than it is in the basic A* algorithm. However! His algorithm is still looking at all the same grid squares; it's just doing less work at each.

My pathfinding implementation is designed to pick from among all the available equally-good paths with equal probability (in order to make groups of moving units move a bit more chaotically), so it isn't compatible with jump point search. (You could also imagine a pathfinding algorithm that tries to interleave the moves in a way to most closely approximate straight-line movement, which would also not be compatible with jump point search.) It has got me thinking about ways to squash symmetry out of my pathfinding, though.

16x16 Tiles

New version of ThiefRL with 16x16 tiles instead of 8x16. The graphics are still fairly temporary. Sight and hearing is circular on the grid now instead of being twice as far horizontally as vertically (which was to make things come out visually circular). I split the difference so light/sound travels further vertically and less far horizontally as before. As a result the level is probably not the best balance.