PlayTechs: Programming for fun

iOS: New Orbit

2012-01-22T21:20:00.000-08:00

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...

2012-01-17T06:52:00.000-08:00

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

Plan what you will do before you do it
Keep productivity records (and examine them for trends)
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

2012-01-16T08:08:00.000-08:00

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

2011-10-31T05:27:00.000-07:00

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

2011-10-12T06:16:00.000-07:00

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.

Remembering my father

2011-10-09T22:11:00.000-07:00

Yesterday my father would have turned 65. He died two weeks ago after having had a lung and its surrounding tissue removed, as an attempt to fight the spread of mesothelioma.

James Sr. (I was a Junior) was born in 1946, second of four. When he was thirteen his father died suddenly (most likely of mesothelioma), and Jim became the "man of the house." He had his impish streak but he was also very hard-working. He knew what he wanted and he got it. He worked his way through college since his mother did not have much money. He pursued my mother from high school, despite not being the favored suitor with her family, and married her following college. He bought a Piper Cub airplane in high school (under his mother's name) which he flew out of the field at the family farm. He did not want to go to Vietnam, so he went to medical school instead. He became a renowned ophthalmologist specializing in cornea transplants, and was the chair of the ophthalmology department at Loma Linda University for a decade. He founded the Inland Eye Bank for sourcing eye tissue.

My father was a meticulous (nay, obsessive) record keeper. Ophthalmologists are gadgeteers (as sure as neurosurgeons are egotists or pathologists are grim or orthopedic surgeons are fun-loving) and my father bought pretty much every generation of IBM PC as a means of keeping his own personal surgery databases. He let me play with them when he wasn't at home and as he saw my interest he kept me supplied with programming software. He gave me copies of IBM Logo, MS QuickBASIC, Borland Turbo Pascal, and eventually Borland Turbo C. I think I first encountered Rogue (the computer game) on a PC in the eye bank offices when I was hanging around there on a weekend with him. Being raised Seventh-day Adventist I had little exposure to pop culture of any kind. Rogue was riveting; I made a copy of it on a floppy disk, took it home, and played it furtively and obsessively. I wanted to make games like this!

After the university sold its ophthalmology department to a private practice, my father did some soul-searching and decided to move to the Pacific Northwest and join up with a "cataract mill," as they were derisively called by many ophthalmologists. To cut costs, these practices devolve most of the pre- and post-op care to a supporting network of optometrists, handling just the surgery bits that the optometrists cannot do. The optometrists love this because referring a patient to a traditional ophthalmologist typically means losing future business; the ophthalmologist will just absorb the patient into their own practice. With a cataract mill the optometrist stays in the game.

Focusing on just surgery meant that my father racked up incredible numbers of them: up to twenty-five surgeries a day, adding up to a lifetime total of over 55,000. (Remember the meticulous records?) He had two surgery suites. The nurses would prep a patient in one while he was operating in the other. He'd walk in, read the patient's name off a sign, and a few minutes later they'd have their cataract out and a plastic lens implanted. By then a patient would be ready in the other room and he'd swap gloves and start over again.

This is incredibly demanding performance work in the space of a square centimeter. There is no tolerance for error. Fortunately the high volume of surgery that he was doing meant he'd seen just about everything and could react appropriately. He experimented with making improvements to his instruments and ran studies on them to see whether the modifications were effective.

They say that when you have your mid-life crisis you buy the car you had when you were a teenager. Remember the plane? Yeah. My father bought a brand-new Super Cub and flew it all over eastern Washington, Oregon, and Idaho. Every time I would visit he'd get me out in his plane and we'd range all over. We dropped in on Red's Horse Ranch (now defunct) in Minam Creek; you can only get there by horse or by plane. We dropped in on a friend's wheat farm; the neighbor boy would come racing over on his quad to get a ride. We'd chase coyotes with the airplane, buzz herds of cattle, do touch-and-go landings at the Lower Monumental dam.

Surgical careers don't tend to run long. Retirement was looming. I think my father was waiting for his 65th birthday to start thinking about what came next.

What came next, last April, was mesothelioma: a cancer of lining tissue, in this case the lining around his right lung.

There isn't any particular reason that we know of why he would have gotten it: he wasn't a smoker and hadn't been exposed to asbestos (the two major causes). My father did several rounds of chemotherapy. I sat in with him on the infusion days and was reminded of how blunt our medical instruments still are in many areas. Chemotherapy is basically poison, to be absorbed by living cells. The cancer, being more vigorously alive than the rest of the body, will hopefully take the brunt of it. There is inevitably a lot of pain, which can be addressed with opiates at the cost of addiction and reduced mentual acuity. Taking the opiates results in constipation. Vitamins are getting destroyed. Sleeplessness is common. Before you know it you're taking a giant regimen of pills and patches around the clock.

The chemotherapy didn't do anything to the cancer. A surgeon at Swedish Hospital in Seattle wanted to have a go at removing the lung; my father was relatively young and in excellent health other than the cancer. After a lot of deliberation he decided to give it a shot. He made it through the surgery but could not sleep in the next few days, which made him paranoid and combative. After sedation he deteriorated steadily until his remaining lung could not supply enough oxygen even with pure oxygen being pumped in via a respirator. We took him off life support (he had not been conscious, I think, since he was sedated three days before) and he died quickly.

Given who my father was, and who I am, it was inevitable that I would disappoint him to some extent. I didn't go to medical school (despite plenty of urging). I didn't marry a nice Adventist girl (despite being sent to an Adventist college). I didn't pick a particularly respectable line of work (and started out in Las Vegas, at that). Nevertheless he was always very good to me and seemed to get on very well with the girl I did marry.

We loved him and we'll miss him.

Resizable Windows

2011-10-04T06:40:00.000-07:00

I've just finished implementing a relatively mundane feature that's been on my to-do list for a long time: the ability to resize the game window in my Roguelike projects. I found myself always cranking up the window size during development so I could see more, and then reducing it back to 80x25 upon release. I suppose the next step would be to preserve the window layout in the registry but that comes with its own set of issues, and I want to avoid going into the registry just yet.

Here is the latest version of ThiefRL, my transplant of Thief-style stealth gameplay into a turn-based, grid-based world.

Here is the latest version of SpaceRL, my experiment in approximating zero-gravity movement through a randomly-generated, monster-infested derelict starship.

Both games are pretty simple at the moment; there's lots more that needs to be done.

Supporting resizing involved a fairly major change to the conceptual model of my roguelike framework. It used to have a virtual frame buffer of 80x25 characters. The game would write to this buffer very much like you might have written to the graphics memory in the DOS days, and the framework would display it. Now the game follows the model I more typically use in my non-roguelike games: the framework calls back to the game when it needs the screen drawn, including information about the window size. The game issues calls back to the framework to render glyphs at arbitrary positions within the window.

In ThiefRL I ended up swapping out the speech-bubble placement algorithm for something a bit simpler, in order to get it to behave well on resizing windows. The old algorithm was trying to avoid placing speech bubbles over NPCs. It used a sort of simulated annealing, but this resulted in totally different solutions every time it rendered. When resizing the window this looked pretty crazy. The new algorithm just tries to put each speech bubble on the opposite side of the player from its source, to keep a clear view of the space between the player and the speaker. If multiple NPCs say something on the same turn, though, it's possible for the bubbles to overlap.

I also took the opportunity to touch up some of the in-game note text to give it a bit more thematic flavor. There are still some notes that don't belong at all: the limerick in the heavily-guarded house, for instance. This really was just my test world for features, so it hasn't had terribly focused world-building done on it.

I received a couple of fan letters for these projects, which was very gratifying. I know I tend to lurch about from project to project as my whims dictate. ThiefRL feels like it's furthest along in terms of the quantity and quality of gameplay on offer, and in terms of it not having any particularly big technical challenges on the horizon. (Hierarchical pathfinding would be the next one I can think of.)

Next up, I think I will implement one-way windows in ThiefRL. I think I'd like to give the player more options for de-escalating a situation. One way might be to have "high windows" that you can jump out of to move from a heavily-guarded inner area to a less dangerous outer area. The guards would not be able to follow directly so you would gain some distance immediately. You would not be able to return through the high window, though, so it would preserve the difficulty of getting into the inner area.

Linear Maze

2011-09-19T07:09:00.000-07:00

Different maze-generation algorithms can produce drastically different results.Up until now, in SpaceRL I've been using an algorithm that picks a random potential connection and adds it if it is joining two disjoint areas of the maze.Here is a version that does a depth-first traversal instead. It maintains a stack of potential connections to visit. Starting at the entrance, it pushes all potential outgoing edges onto the stack (in random order), then pops edges off until it finds one that goes to an unvisited room. After adding that edge it then pushes on all the unused exits from that room, and so forth until the stack is empty.The result is a maze with a much longer, more linear main path. I'm not sure whether this is good or not, but it's different.

Barricaded Doors Release

2011-09-12T06:38:00.000-07:00

Uploaded a new version of SpaceRL.

Changes:

Once player sees a location, it stays permanently visible.
Door construction revamped to included barricaded and broken doors.
Single outside hatch on symmetry axis.
Player always starts out floating toward the entrance hatch.
Limit ship's spread away from symmetry axis.

The general algorithm for connecting the rooms is as follows:

Come up with a set of all potential adjacencies (rooms sharing a wall)
Connect all of the adjacent space rooms together (you can't see them in the final product)
Connect the ship's rooms together with “original” doors. These may or may not be passable in the final level but represent how the ship was originally constructed. The ship's interior is minimally connected, plus about 50% of the remaining adjacencies.
Doors between the inside and the enclosed outside areas are added. This is the same process as the previous step, but doing it afterward ensures that the ship's original layout would not have relied on going outside to traverse it.
Create the door to surrounding outer space. It's on the symmetry axis at the moment.
Choose from the set of “original” doors to construct a simply-connected maze through the rooms. This will be the expected traversal. These become regular doors. Note that this path may require passage through enclosed exterior areas.
Compute each room's depth from the entrance hatch when traversing via the maze.
Turn the remaining original doors into broken or barricaded doors: broken, if the traversal depth is the same on either side, and barricaded (so they can only be opened from the deeper side) otherwise.

A couple other things:

The window size is expanded from 80x25 to 120x40. It really needs to be resizable but that's been a low priority.
The number of rooms in the ship is greater: 10-100.
If you just want to look at ship layouts, use the undocumented Ctrl-A hotkey to toggle visibility of everything.

Barricaded Doors

2011-08-29T07:42:00.001-07:00

Miscellany today:

In SpaceRL, I added barricaded doors that can only be opened from one side. With these, the level generator can control the order in which the player encounters rooms in the spaceship, while allowing the player to subsequently take shortcuts across the level.

I also added a slight refinement to the way the level generator places doors. It first creates the ship's original door layout, then replaces some of those doors with barricaded or broken doors to restrict the player's travel path. Previously it was only doing one pass to establish the connectivity of the ship's rooms. With this algorithm there is a slight bit of history implied in the level, as you can see the ship's original symmetric, non-maze door layout underneath the current restricted connectivity.

Separately from this I've been experimenting with learning Javascript. It's not that bad of a language, so far. I had a C program I wrote with a friend many years ago to generate random RPG names; it was designed to be run on a web server to generate a web page. Hardly anybody does things this way any more. As an exercise I rewrote it in Javascript; the server only has to serve up the page and the client's browser does the rest. It's around 10 KB, most of which goes into the word lists. Unfortunately none of the free Google things (Blogger, Sites) are good for serving up Javascript so I can't easily demonstrate. Maybe it's time to get my own domain and hosting again.

I logged into Facebook (as I do every other month or so) and discovered that Chad Jones, an artist with whom I worked on two games over the course of four years, has written an e-book about his last decade-plus of experience working in the games industry. It's a dollar and a good read, especially for anyone thinking about going into games. It's available for Kindle and Nook. The book's called “Laid Off” which in boxed games development is the usual disincentive for shipping a product.

Symmetric Starship Doors

2011-08-01T05:35:00.000-07:00

This week I took a break from working on my lunar-lander game to go back and fix the level symmetry in a simple game I made a couple years ago.

SpaceRL (unimaginative working title) is a turn-based, grid-based, Roguelike-inspired attempt to represent zero-gravity motion; in particular, the ability to shoot a gun in one direction whilst floating in another direction. It's inspired by the cover of Tobias Buckell's book Ragamuffin:

The game is very simple at the moment: survey derelict, monster-infested starship wrecks and identify the crew remains. The basic combat maneuver is shown above: get some monsters following you, find a straight corridor, kick off, and blow them away as they pursue.

Coming up with level design that suggests a starship was an interesting challenge. I want something that appears to have been constructed along an axis of symmetry but that due to barricades and debris can no longer be navigated straightforwardly.

This week I finished making door placement be symmetric across the central axis. I also experimented with making the levels into simply-connected mazes. If there is only one way to get to each room from the entrance, the player will need to backtrack more in the process of visiting every room. Whether this is fun or not is debatable; it depends on whether revisiting rooms is interesting. I've thought about having the player eventually find the artificial gravity controls, for instance. Gravity would remove your ability to move and shoot simultaneously, which would change the experience.

The more-likely solution will be the typical thing of having shortcuts back toward the root of the tree that the player can open up. For instance, there might be a door that is barricaded from one side; once the player gets to that other side via a round-about route they can un-barricade it and take the shortcut.

Here are four versions of the same map:

Asymmetric

Symmetric

Asymmetric Maze

Symmetric Maze

The percent signs in the maps represent destroyed doors. They are there to imply that the original layout was symmetric even if the current connectivity is not. The “symmetric” level style means the generation algorithm attempts to connect matching pairs of rooms on opposite sides of the symmetry axis at the same time, rather than leaving it to chance. Without it there tend to be more destroyed doors.

Here is one more ship layout, this time with a horizontal axis of symmetry:

Caves and Orbiting Debris

2011-07-25T07:58:00.000-07:00

This week I did a couple of small experiments with the terrain generation. One was to make the base density function (before applying noise) have a couple of concentric rings with space between. The noise function breaks through between the layers to create entrances to the caves. (Actually the base density function has a couple of built-in holes between the layers too.)

I also threw in some orbiting debris to see what it feels like to fly through it. At the moment it is just discs.

The terrain generation needs to have more smarts about area accessibility. I think I'm going to evaluate the density function onto a grid roughly the size of the rocket (maybe slightly larger). Then I can do evaluation at that level to figure out which areas are accessible, and add in terrain features. One of the things I want to do is generate a couple of background layers: one that gives caves a back wall, and then another layer or two that represent far-away mountains (and maybe move with some parallax).

Gatling Gears

2011-07-19T07:15:00.000-07:00

Rose accidentally bought Gatling Gears on the PS3, so I played it. It's a twin-stick shooter in the Robotron vein, set in a steampunk world.

Copious, slow-moving patterns of bullets (“bullet hell” I think I've heard it called) are a game mechanic that came out of games like Raiden. This mechanic seems to be getting mixed in to more things these days; Outland combined it with side-scrolling platforming (and Ikaruga's phase-changing) recently, for instance.

Unfortunately Gatling Gears looks unfinished in some respects. The gameplay apart from the bosses is very monotonous. I actually found myself looking forward to the bosses which is a reversal from the usual.

The story is nearly nonexistent. There are story cards inserted between the half-dozen chapters, and printed dialog exchanges at points during the gameplay, which you're apt to miss if you are busy. What story there is seems trite and predictable. You're best off reading Scott Westerfeld's Leviathan series (my review) and imagining that story overlaid on this game. It works pretty well.

The graphics are lovely, though. I am going to go back through the game and try to figure out how the environments were assembled.

2011-07-18T08:18:00.000-07:00

Stealing the computer away from my daughter's Minecraft session to make a quick post.

I did some work on learning Blender and straight-away ran into something it can't do: individual edge/vertex beveling. It has an overall bevel modifier which can accept per-edge weights but it is not something you'd use as a poly modeling tool. Searching on the forums reveals that this has been a long-standing lack. Sigh. Well, Maya has a similarly baffling omission; you can't do proper insetting in a face in stock Maya. So they're all lacking something.

Salvage and rescue is the theme I'm working with at the moment. I'm trying to imagine how a spaceship would decompose into constituent parts in a 2D world. Here is some amateurish concept art:

I'm thinking there would be a couple of layers of spaceship: some skin pieces that could be removed, and then various modules underneath that could be salvaged for money. There might be an inaccessible background layer to the spaceship that has its skeleton, too. With 2D art it's not clear to me yet how this all goes together. Maybe the skin parts should just blast off and disappear; otherwise people will expect them to tumble like metal sheets, which they can't do.

Blender 2.5, Planning

2011-07-11T07:57:00.000-07:00

I've spent this week doing some planning. One of the things I'm thinking about is how to streamline the process of putting new things into my game. Being able to author the physical parts of them in a modeling program is one way the process could be improved. Yes: the dreaded art pipeline approaches. (Some of my friends who have been involved in startups say that the art pipeline took a lot more engineering resources than they anticipated.)

I have worked extensively with 3D Studio Max in the distant past (I used it for versions 1-3 or so), but the last eight years I've worked with Maya. Of course they're both owned by the same company now. A legitimate copy of Maya runs about $3500, so I'm going to pass on that for now. Blender, the open-source equivalent, looks like it ought to fill my needs. I've been spending time learning how to get around in it.

Blender 2.5 switches to Python 3, with considerable API rework at the same time. This makes a lot of the example code on the net obsolete. Documentation is still a work in progress, so get comfortable with the dir, list, and help commands in Python.

There are a couple of possible ways to export geometry. I'm going to experiment with having the makefile detect when a source Blender file has changed and run Blender at the command line to export it to an intermediate file. The command looks something like this:

blender -b input_file.blend --python my_export_script.py

Restarting Lander Development

2011-07-05T07:39:00.001-07:00

The past six months have been very busy at work. We also experimented with having my computer out in the family room, where the TV is.

Now it's back in the bedroom, and work's less hectic. I'm restarting work on my Thrust-alike with an eye toward getting something done and released, even if it is dirt simple.

There are so many things that need to be done it's been hard to decide where to start. At the moment I'm sorting out issues with having planets of different radii. Gravity ramps up linearly as you move from the center of the planet toward the surface, then falls off quadratically as you rise above the surface. The planet's radius was 1.0 which made that pretty simple.

After that, I will probably put a bit of effort into coming up with slightly more interesting planets to fly around. The camera continues to be a problem spot, so I'll keep trying things there.

Animal Crossing --> FarmVille

2011-02-18T09:29:00.000-08:00

I have been telling game developers for years that they were leaving money on the table by not making more games like Animal Crossing. My wife pointed out this morning that FarmVille and its ilk are pretty direct descendants of Animal Crossing, and they are indeed taking that money. I don't know how I missed that before; the similarities are obvious once you think about it.

Couple of uploads

2011-02-10T07:57:00.001-08:00

Work on various things is ongoing. In the meantime here are a couple of downloads:

A version of the Lunar Lander game that uses 16-bit vertex indices instead of 32-bit indices. May be more generally compatible. Also includes a very basic (read: annoying) rocket noise.

RelativeNeighborhood Starmap experiment. Left-click and drag with the mouse to rotate. Press space bar to generate a new map. The A key toggles between distributing stars on the surface of a sphere and in the volume of a cube.

Also, I finally bought Slay, and recommend it highly. It has a free demo of one map.

Interlocking Orbits

2011-01-30T19:55:00.001-08:00

This week has focused on figuring out whether having planets move around the sun can be fun.

Moving planets complicate the trajectory plots in a couple of different ways. The simplest is that I need to move the planets while calculating the trajectories. The harder problems are that:

Close to a planet, the trajectory ought to be plotted relative to that planet's local reference frame.
When traveling long distances, the trajectory doesn't help rendezvous with moving planets since it doesn't indicate where they will be in the future.

Moving planets also complicate the construction of the solar system, because each planet needs a path that won't collide with any of the others. They may need to be spread out more from each other. To experiment, I adapted my orrery program to generate random solar systems instead of reading data about the real one.

This one really needs to be seen in motion to appreciate it. Here's a Windows executable.

This program is just generating random orbit parameters and then using brute-force searching to see if the new orbit collides with any of the existing ones. I could undoubtedly do better but it proves the basic concepts. I do some simple checks: if one orbit's minimum distance exceeds the other's maximum distance, they can't possibly collide. Otherwise, I figure their common period (m * n / gcd(m, n)) and then integrate along that period in small steps, checking the distance between the planets at each step.

The random orbits are all generated such that their periods are all integral multiples of a common base (the innermost planets' period). There are ten discrete possible periods in the current solar system, which helps me ensure that they will interlock. I'm currently using a bit of a binomial distribution on planet size and orbit eccentricity, so you'll see few eccentric orbits and few large planets.

The current problem of interest is what gameplay purpose planetary motion ought to serve. Does territorial control mean anything in a solar system? If the planets were stationary I could imagine having planetary defenses that would form a “wall” of sorts along the boundary of a controlled region. With the planets swirling around it's not nearly as clear how that would work.

There are points in time where it is definitely cheaper to go from one planet to another; this is why Mars missions are launched approximately every two years, for instance. I don't know if having a delay element like this in a game would be fun at all, though.

“Disneyland” Solar System

2011-01-23T21:15:00.000-08:00

Following a suggestion from Kometbomb I've been experimenting with artificially attenuated gravity. Results have been encouraging. I have an attenuation factor that smoothly cross-fades a planet's gravity to zero at a finite distance from it. (It's the usual 3u² - 2u³ cross-fade, although maybe linear would be fine too.) This allows planets to have strong surface gravity without affecting distant areas, so I can pack them more closely together. It's like a Disneyland version of a solar system (or a bit like Super Mario Galaxy, as Owen suggests.)

The cross-fade attenuation doesn't start until some distance above the surface. As long as you stay under that height you can enter stable orbit around the planet.

At the moment I have all the planets sitting still. The next experiment will be to see if motion can be made to work. Planets will need to be arranged so they can't ever collide with each other, so things may end up getting spaced out more. If motion doesn't make it more fun I think the multiple planets will still be all right. I can see interesting gameplay being built from this.

Multi-planet prototyping

2011-01-17T06:51:00.000-08:00

The past couple of weeks I've been working on a prototype of multi-planet gameplay for my lunar lander game. Results are not terribly encouraging, so far.

One of the big problems is figuring out how to miniaturize the solar system without getting totally wacky gravity. On Earth's surface (if I've done my calculations right) the acceleration due to the sun is about 1600 times weaker than the acceleration due to the Earth itself. Thus it doesn't much matter where the sun is in the sky; up is always pretty much the same direction.

I would like to have a smaller, denser solar system to cut down on travel times between planets. Unfortunately in my experiments so far this results in slanted gravity as the sun and other nearby bodies move across the sky.

Our solar system has about 99.9% of its mass in the sun. Thus, there's very little gravitational influence from one planet to another. As I distribute more of the solar system's mass to the planets this makes it harder to fly between them due to the perturbations. (It would also make their orbits unstable but I'm restricting them to only pay attention to the sun's gravity.)

I'm also hitting numerical precision issues as I expand the play area, so I'm trying to track those down.

I may end up falling back to having an “overworld map” for travel between planets, similar to Gravitar. This would lose some of the wow factor that continuous flight between planets would have, but you could operate on different time scales in the two modes and reduce boredom and precision problems.

Planning for 2011

2011-01-06T08:14:00.000-08:00

In addition to working on sound over the holidays I did some unsuccessful further experiments with the game camera. I want threats to be visible on-screen whenever possible. What I tried was to collect up any turrets that are close enough to hit the rocket, and include them in the set of things that the camera frames. Unfortunately this introduces big discontinuities in the framing circle's position and size as turrets enter and leave. I have camera smoothing, of course, but even so it is much jumpier than I would like. Maybe I need different "frequency bands" of smoothing, with the threats coming and going on a much lower-frequency smoother. I don't know.

I'm in the middle of planning for the upcoming year. At my day job we are in the last couple of months of development on Infamous 2, so that will demand a fair amount of time. Nevertheless I'm going to attempt to devote an hour a night to work on my own projects; this is what novelists with day jobs do, and I'm not going to get much of anywhere on less time than that.

I'm giving up any TV watching that I used to do, as well as most videogame playing that isn't with my daughter. (By the way: it seems to me there is a major dearth of games that are great for playing with your five-year-old. Currently I'm working through Lego Harry Potter with her. This seems like a potentially underserved market.)

In the near term on the lunar lander game, I'm going to do some experiments to determine the feasibility of having multiple planets that you can fly between. This is the major purpose of rockets, after all, and it's a feature most people who've played it have suggested. The big questions are:

Will this work with the physics engine? I'm going to have several very complex objects moving around (the planets) where I used to have most of the complexity in the static part of the world.

How will gravity work out? Currently the gravity all comes from a single point source, so orbits are straightforward ellipses, and are stable. I'm not too worried about having multiple gravity sources for the player; the rocket flies around under power most of the time and doesn't care if its orbits aren't stable. The mothership can stabilize its own orbit with its thrusters; it's already doing that to some extent. I will probably have to fudge the planets themselves so that they don't affect each other, to ensure that they have stable orbits.

How will the camera work out? Currently the camera rotates so that "down" is down. If I have multiple sources of gravity then there will need to be transitions between orientations so I'll have to figure out how that works.

I will reduce the planets to simple circles for purposes of the experiment, to work out travel times, camera, and so forth.

Treasures of a Slaver's Kingdom is Now Free

2011-01-05T19:51:00.000-08:00

Good news, everybody! S. John Ross' magnificent text adventure Treasures of a Slaver's Kingdom is now free.

Play This Thing review by Emily Short
My review (not nearly as well written as Emily's)

Enjoy!

Vorbis decoding working

2011-01-05T06:20:00.001-08:00

OK, I feel like an idiot. Finally ran down the problem with my decoder, and it turned out to be due to accidentally reading the file as text rather than binary. One of the oldest mistakes in the DOS/Windows-programming book. As soon as the file read encountered the magic DOS end-of-file character it quit reading.

I still think the Ogg format's unnecessarily complicated, and I'm not sure Vorbis is the best choice for dialog lines. I don't want to pay ~4 KB per line of dialog in my game for a bunch of identical decode tables, along with the CPU and memory to unpack them every time I play a line. You could imagine putting all the lines in one Ogg stream and then seeking to the appropriate line, but that would require creating an index, something that Ogg itself doesn't provide. I may take a look at using GSM-style linear prediction compression if I can find a decent implementation.

Ogg = Lame

2011-01-04T06:44:00.000-08:00

On further debugging I am forced to conclude that the Ogg container format is lame. This is not saying anything about the Vorbis compression format; I haven't delved into that other than to note that it has quite a bit of overhead for small files, at least the way Audacity encodes it.

Here is a good explanation of the ways in which the container format is unfortunately designed. For my purposes, the main problem has to do with how packet size is encoded. They didn't want to put a fixed-size 32-bit value in the packet header because they expected typical packet sizes to be under 256 bytes. Never mind that they have at least three other wasted bytes in their header, and they chose an encoding scheme that made their header variably-sized. The encoding scheme for packet length is this (feel free to laugh): first, a count byte. Then an array of that many bytes. Each byte represents a part of the size count; to get the full size, add them all together. You are expected to set the first N-1 bytes to 255 and the last byte to the remainder. It's sort of the inverse of compression, really. They should have thought very, very hard before making their packet headers variable size. And then if they really, really thought it was a good idea they could have used the UTF-8 style of encoding arbitrary-size numbers.

The decoder I was reading followed the spec in that it assumed that a non-255 value indicated the end of the array (it isn't paying attention to the count as far as I can tell). However, all the files I've encoded with Audacity have an early packet with a non-255 value in the initial byte, followed by a bunch of 255s, followed by a non-255 final byte. The initial non-255 byte is causing the decoder to prematurely think it's reached the end of the packet.

It's telling that Wwise (an audio middleware provider with which I am familiar) supports Vorbis compression but wraps it in a RIFF-style container format (what .wav files use) instead of using the Ogg container format. (Confusingly they retain the .ogg file extension, though.) It'd be nice if there was a standard for this; I'll have to investigate.

Ogg Vorbis

2011-01-03T08:19:00.000-08:00

I have been debugging stb_vorbis.cpp, Sean Barrett's Ogg Vorbis decoding library. Somehow it is not unpacking the Huffman code tables correctly. Since it is broken on every .ogg file I've tried I think it must be somehow related to the way I'm compiling it.

Digging into the .ogg file format has been interesting. All the audio I record has identical code tables on the front (I'm encoding with Audacity), which amount to about 3.5 KB. Ogg is different from other compressed audio formats in that it doesn't have any assumed decoding tables; they all have to be embedded into the file. If you put individual lines of dialog into their own .ogg files that adds up to quite a bit of overhead (about 20% for my lines which are currently around 17 KB each).

A tidbit I learned: DVD audio is sampled at 48 KHz, rather than being the same rate as CDs (44.1 KHz). I'd wondered why PS3 games had 48 KHz audio; now I know why.

I've been thinking about how to complete my lunar lander project so I can move on to others. Part of the problem is that I haven't really settled out which direction I want to take the gameplay. More later; have to go to work now.

Rocket sound

2010-12-21T07:48:00.000-08:00

I've put together a very basic sound engine for my Lunar-lander-on-a-disc game, although it isn't in a released version of the game yet.

It's my first time using XAudio2; it went fairly painlessly. The only trouble I had was with my synchronization between the playback thread and the sound generation thread. Originally I was using an event but it was possible for the consumer to occasionally generate two events (meaning it had consumed two buffers) while the producer was busy. After this happened a couple of times (I am currently triple-buffering) the producer and consumer would wind up writing to and reading from the same buffer, with nasty-sounding results. I switched to a semaphore which keeps a count of how many unqueued buffers there are and it works fine now.

At the moment my sound engine is very, very low-level. I generate sound in small batches (17 ms at a time, one video frame's worth) and feed it to XAudio2 for playback. I'm not using any pre-recorded audio yet and I'm not really doing much signal processing yet either. Since I'm triple-buffering there are a couple frames of latency; I may shrink the buffer size to reduce that.

Now I'm trying to come up with a good, interesting rocket engine sound. All I have so far is some white noise that has been filtered with a 64-tap low-pass FIR filter. It's also shaped with a basic envelope for when the thruster is on or off.

I am currently generating the white noise at 44.1 KHz and filtering it down which is incredibly wasteful. I'm going to switch to synthesizing the noise at 11 KHz or lower and upsampling to the final rate since I am knocking out all the high frequencies anyway. I want to experiment with a dynamically-changing filter as well so I can get interesting transient effects at the start and finish of a rocket firing. I'd like to give the noise more of a 1/f or 1/f-squared shape as well since I think it might sound better (louder bass, softer treble). It's just kind of a generic hiss right now.

I've experimented in Audacity with phasing and it produces some really nice whooshy effects so I may try to come up with a way of relating phasing to what is going on; maybe do phasing based on the nozzle angle or something, so that as the nozzle sweeps back and forth you get some stereo effects.

The steering jets will get their own sound generators as well, and then it's on to impacts, weapons, and whatever else is needed.

Reviews: Sherman Alexie and Marjane Satrapi

2010-11-01T07:30:00.000-07:00

Here in the Pacific Northwest it hasn't been long since the land changed hands. A lot of sad things happened and are still happening. I used to walk over to the site of the Whitman Mission on Saturday afternoons. Some people brought religion and farming and smallpox there and got killed in 1847 and it started a series of wars. I haven't ventured into any of the area's many reservations other than passing through on the highways, but when I fly over the Yakama reservation and see the trailer homes on the barren hills surrounded by their trash collections I imagine the sadness radiating upward. (Maybe my imagination's way off, though!)

The Absolutely True Diary of a Part-Time Indian is Sherman Alexie's semi-autobiographical novel about leaving the Spokane Indian Reservation, with illustrations by Ellen Forney. Arnold Spirit (“Junior”) is fourteen when he discovers his mother's name in his geometry textbook; the school hasn't acquired new books in the last 30 years. His teacher convinces him he has to leave the reservation to fulfill his potential. Junior transfers to Reardan High in a nearby white farm town, where he and the school's mascot are the only Indians. His tribe (apart from his family) take it as betrayal. When he makes the Reardan basketball team he finds himself up against his former best friend.

“Diary” is poetic, funny, sad, and raunchy. It ought to ring true with anyone who has had to leave home and family to get where they are.

Speaking of cultural displacement, the Pacific Northwest area now has a large Iranian immigrant population, including a bunch of Baha'i.

Persepolis: The Story of a Childhood

Marjane Satrapi was in grade school in Tehran when the Islamic revolution happened. Suddenly she was forced to wear a veil and attend segregated school. Then things got worse. Her parents eventually shipped her off to France when they realized that she wouldn't be able to have the life they wanted for her.

Once she found her feet in France, Satrapi produced this beautiful black-and-white graphic novel autobiography. She's done several more volumes and an animated film. It's been a while since I read this but I recommend it highly as well if you want to know more about what's happened in Iran.

Turrets Debut

2010-11-01T06:36:00.000-07:00

Turrets make their first playable appearance in today's update to my lunar-lander-on-a-disc game, available on its website.

In addition the rocket has now been outfitted with machineries of aggression: Press right mouse button to fire projectiles out of the rocket's nose, and B to drop a bomb. Bombs start out with the same velocity as the rocket so you can use your ballistic trajectory plot to see where they will go. The nose gun has its own new trajectory plot.

Various other things have been tweaked. The landing gear now uses Chipmunk's damped-spring constraints instead of doing the spring and damping in the step itself. The damping is significantly different between the two approaches; I've tried to tune it back to be similar to before, but with less bounciness. I've also made some semi-successful attempts to tune the landing gear shock movement range to prevent inversion when you hit it sideways, but it's still doable.

The rocket doesn't activate its orientation thrusters when either of its feet are touching the ground unless the main thruster is firing. This makes landings a bit more difficult since you cannot cancel unwanted rotation quite as easily. I might try having the orientation thrusters automatically switch to rotation cancellation once you touch ground if this feels too hard.

I tried and removed missiles that accelerate continuously. They look cool but they make the game really easy, so I'm still thinking about them.

Another change is that there is now a two-planet progression. The first planet has fewer caves and fewer astronauts. The second planet is the classic one.

Work heats up

2010-10-25T08:38:00.000-07:00

Work's getting more hectic. I am plodding forward on the lunar lander game nonetheless. I've spent a little bit of time working on coming up with distinct styles of randomly-generated planets in preparation for having a series of them in the game. The big failure there was an attempt to make a loose archipelago of small asteroids. I will need to attack it in a completely different way from how I was doing it. Planet generation needs to be spun off into its own thread so the game is always responsive.

Turrets are getting tuned up now too; hopefully they will make their debut soon. Making the game more challenging is a top priority. Last night I tried making turrets wait to shoot until they can hit the rocket at its closest point; it didn't feel very good. Not enough shooting. I could make them take that point in time and space out shots before and after it but I don't think it's worth the trouble. Next I tried taking the turrets off a synchronized shooting schedule. I'd had them synchronized because I thought it would provide a good rhythm to the game but due to the varying flight times of the shots it didn't, really. Now each turret shoots as soon as it has a shot and then runs its own recharge timer. This feels pretty good. I need to work on having the turrets turn to line up their shots, which will give them an initial reaction time. That may affect how their schedule operates.

The turrets' bullets now hit the rocket. They impart a fixed impulse and a fixed amount of damage. I may fudge the impulse so it applies less torque than is physically accurate. It's cool seeing the rocket get knocked about but if it tumbles too much it just gets annoying. The bullets make use of Chipmunk's sensor shapes; they don't participate in actual collision response, just report contacts. I handle the rest. (I'm thinking of the bullets as an energy ball right now.)

Next is to give the rocket a means of fighting back and disabling the turrets. I am unsure whether I will do a bomb-dropping weapon or a shooty weapon first. Bombs are interesting from a trajectory point of view (this game is all about trajectories) but if they allow you to take out turrets from outside their range it might not be very fun. Limited inventory is the typical way to solve this. Shooting will involve aiming distinct from the aiming used to fly so it'll be an interface problem. I will probably use the same aim and have different buttons for thrust vs. shoot, but the question is what to do with the rocket's auto-rotation. You don't necessarily want the rocket spinning around while you squeeze off a few shots during an approach. I could drop auto-rotation except while thrusting; may try that. Pedro found the auto-rotation confusing. On the other hand, that's giving up some control of the rocket.

Some other similar games like Gravitron 2 (available now on Steam and XBox Live; go get it) have direct rotation control which solves the aiming problem, but it creates problems when interacting with the landscape. Gravitron's landings and impacts feel very unsatisfying to me.

Lander Game WIP

2010-10-08T07:55:00.000-07:00

Just posted a new version of my Lunar Lander game on its site.

There are only minor changes from the previous version. The braking line more accurately matches up to the powered trajectory plot, and there are indicator circles around the landing targets when they are very small.

There are some additional undocumented keys that will go away in the future, for things I am working on or experimenting with:

F1-F3 set the camera to one of three different modes (Auto, Manual, and Experimental).
F toggles a debug display of what the camera is trying to frame.
G toggles the ramp motors (ramps are not finished).
Home rescues the nearest guy instantly; useful for testing the camera framing and the end game.

Conversation starter #3

2010-09-29T08:37:00.000-07:00

Sure-fire topics for easily striking up conversations with strangers:

With guys: Shaving
With new parents: Poop
With Pacific Northwesterners: Dietary restrictions

Approximately two-thirds of Seattle-area residents (a number I just made up) have some sort of dietary restriction, whether due to ideology, allergy, or both. If you're at a party just say "No thanks, I'm gluten-free right now" and you'll be off and talking with a bunch of the attendees. "Oh yeah, I have a gluten allergy too. These cookies are too good to pass up, though."

You can cross this with the new-parent poop topic: "Yeah, we're trying cutting lecithin and nuts from her diet; her poop was looking sort of greenish and she was howling at all hours of the night."

Thanks to preschool I now know that peanut allergies can be classified into airborne and contact variants. Parents take turns bringing snacks for the class and holy cow does that afford opportunities for dietary-restriction talk.

I have uncharitable theories about why this is. The Northwest is full of tech types who believe that religion is superstitious nonsense that is beneath them. Unfortunately for all of us, the universe is capricious and hard to understand, much less control. The urge to do both is within us all, though, and it finds its way out one way or another.

My related theory is that food allergies is a religion that does not set off the "no other gods before me" alarm in Judaism/Christianity/Islam. Thus it is a good mix-in religion. The Northwest is full of people who have been transplanted from all over the world. A mix-in religion is a great way to bond people of different faiths together.

Minecraft, Layton Reviews

2010-09-27T06:13:00.000-07:00

Took a week of vacation at home; sigh, yes, a “staycation.” Amongst other things I managed to play a few computer games:

Minecraft

I've spent a ton of time playing this game. Rock, Paper, Shotgun ran a play diary which convinced me it was worth shelling out for in its alpha state. I have not been disappointed.

Here's a fan-made trailer for the game:

Minecraft (in survival mode) drops you into an infinite, randomly-generated world. Your immediate goal is to survive the nights, when various monsters come out. Once you have your basic safety assured, though, you are free to explore, dig mines for rare materials, and construct grandiose architecture. The game's in alpha and has been built by one man so far. Due to its increasing popularity he is hiring help though.

Professor Layton and the Unwound Future

Just finished this third game in the Layton series of puzzle games. It's as charming as ever; the production levels are steadily rising as the series progresses, with more voice acting and more beautiful animated movies than I remember in the previous installments.

A Layton game strings together a big collection of brain teasers with a barely-related story in which Professor Layton and his boy sidekick Luke solve mysteries. In this case they have received a message from someone claiming to be Luke from ten years in the future, requesting aid. Layton's lost love also comes into the tale; she was a scientist who died in a mysterious laboratory explosion ten years prior.

If you get stuck you can spend hint coins for increasingly specific tips. If you've played the previous Laytons, I think they've dialed back the puzzle difficulty quite a bit here. I don't mind too much; I was fairly frustrated in a few places in the first game.

A couple other games I've been playing but haven't finished:

Zak and Wiki: Quest for Barbaro's Treasure

A point-and-click adventure game for the Wii platform. Kind of fun. I'm playing through it a little bit at a time with my four-year-old.

Dragon Quest IX: Sentinels of the Starry Skies

I am generally pretty burnt out on Japanese role-playing games. This one seems like it's quite charming, despite having a very, very traditional battle system. I'm trying to save my JRPG stamina for the Ghibli-co-produced ones coming out next year so I don't know if I will finish this one.

Brake Line

2010-09-13T07:29:00.000-07:00

This weekend was busy with hiking on Cougar Mountain, attending the Puyallup State Fair (quite an Internet-savvy fair; see the URL), and having company over. My friend Pedro tried out the lunar-lander-on-a-disc game I've been gradually making. He figured out the trajectory plots quickly, but found the rocket's auto-rotation confusing. I need to get more data points on that. The rest of his complaints were things I know about and plan to fix: landings need to be more emphatic, with less bouncing and floating around. Landing targets need better visibility from orbit.

Up until now I've had three trajectory plots: the ballistic trajectory, which is where you go under gravity's influence alone; the powered trajectory, which shows where you go if you thrust continuously in your current aim direction; and a braking trajectory which shows the quickest way to reach zero velocity. This last one I have been unsatisfied with. It gives a rough idea of the turnaround point for deceleration, but I want something that gives more information. Here's what I've got so far:

The red line is the brake line. It's a closed curve made out of the points of minimum velocity for all thrust directions. In other words, if you thrust continuously in a particular direction, when your velocity reaches a minimum it will be somewhere on that curve. The powered trajectory plot's inflection point sweeps around the curve as you change its heading. (It doesn't quite touch in the picture above; this is because for my initial prototype I'm assuming a constant gravity vector for the brake line plot.) The intensity scales with the difference between the rocket's current velocity and the velocity at each point on the curve.

The goal is to kind of show you what the powered trajectory will do as you sweep it around in a full circle, without you having to do that. It is pretty much as I'd envisioned it, but I'm still learning to fly with it so I'm not sure yet about whether I like it or not. I've posted a version to the game's site if you want to try it out and weigh in with an opinion. Remember that the gravity part doesn't match up, though, so it is not yet good enough for precise maneuvering. (There's also the issue that this represents the rocket's center of mass; the actual rocket occupies space around that so you have to take that into account. I might eventually try a Minkowski sum of the rocket's bounding circle with the curve if I'm feeling ambitious.)

Ramps and Rescuee Running

2010-09-07T07:40:00.000-07:00

Work on my lunar-lander-on-a-disc game has been slow but steady. None of the pieces I've been working on are anywhere close to done. Here's a clip demonstrating where things are at:

The rocket has a couple of gangplank ramps that can be folded down. I'm still working on the physics of them. The ramps have a combination of several different constraints in the Chipmunk physics engine: They have a pin joint and a rotational limiter for the hinge, and then some sort of motor for opening and closing. I experimented with a rotational motor and a winch type of thing attached to the tip of the ramp. Ultimately the ramp hinge and motor need to be able to fail, too, if they're pushed too hard.

The little people on the surface now move toward the rocket when it's on the ground. “Toward” is a tricky concept. I thought I might be able to get away with local optimization (head in the direction on the ground that moves you toward the rocket) but quickly discovered places where they get stuck: mostly on slopes with a bit of concavity pointing toward the rocket.

I think what I will end up doing is identifying some “closest” point on the terrain and then determine the short way around the planet to reach it for each rescuee. I still need to limit their movement so they can't go around underhangs. Eventually I want them to run to avoid being directly under the rocket, and to approach the expected landing site even before the rocket has landed. Lots and lots of little details like moving more slowly on slopes, and waving only when they see you but think you might not see them, or something like that.

The main worry I have at the moment is that sitting around waiting for guys to board the rocket will be boring. Rescuing ten people before this change took me about five minutes, so about 30 seconds apiece. It looks like that time could easily double. That's not a problem so long as the player feels engaged. With the flight portion I didn't feel engaged until I decoupled the attitude control from the thrust direction so it was easier for the player to keep the rocket under thrust the whole flight.

I'm thinking about having some Starship Troopers-style spider enemies that pursue the guys on the ground. If you had to supply suppressing fire while they ran to the ship it might keep things interesting.

I also envision (although I don't know when I would implement it) having little scenarios associated with each rescue. Like you might have already-rescued guys come down the gangplank and wave people in, or maybe there'd be someone who needs carrying so they would have to go out and help with that. Little bits of pantomimed story that would spark the imagination.

The current version of the game is available on its website. The ramps go up and down with the G key (I guess I was thinking of landing gear).

A blast from the past

2010-09-02T06:40:00.000-07:00

A friend and I made a CGI script ages ago (1996, probably) to generate random names for fantasy role-playing games. We used the basic templates (e.g. Blank of Blank) but the word lists eventually got a bit silly. Have a chuckle:

RPG Game Name Generator

Bathroom Guy

2010-08-26T06:16:00.000-07:00

My quest to avoid making an art pipeline continues. I couldn't sleep last night so I replaced the landing targets with little guys that wave their arms.

These are made out of five capsules (which can have different radii at the two endpoints) and one circle (for the head). I'm still working out the relative scale of the guys to the rocket.

Next up is to make ramps that fold down from the rocket, and have the guys move aboard. They probably won't animate much yet (if any) while they move.

A Couple of YA Novels

2010-08-20T21:40:00.000-07:00

I like young adult novels because they tend to be short. There's been a discussion recently amongst independent game developers about how long people expect games to be relative to their price. One of the mistaken points I've seen made a few times is that it's only games consumers that judge their media by its length. I'm pretty sure there's a pressure in the adult fantasy/sci-fi genre for novels to be bloated, poorly edited messes. A book needs a map in the front, “Part One of the Demon Kingdoms Saga” on the back cover, and seven or eight hundred pages of typo-laden prose in between. Fortunately you can go to the young adult field and find tightly-plotted, well-characterized books that won't waste your time. Here are two:

Ship Breaker by Paolo Bacigalupi. An oil-less near future on the flooded Mississippi coast. Nailer, a child laborer (the eponymous ship breaker) falls in with a shipwrecked princess on the run. The characters are vividly drawn, the drama is intense, and the plot comes together well. Nailer's abusive father is a particularly strong villain. Not a cheery book but the atmosphere is thick and novel. Impossible to put down once started. Bacigalupi has also written a (much longer) adult novel in similar vein, The Windup Girl.

Leviathan by Scott Westerfeld. Westerfeld, already a prolific and accomplished YA writer, tries his hand at this newfangled steampunk thing. It works out pretty well, and has a sequel coming out in a couple of months. It's an alternate history version of World War I where the British have got genetic engineering down pat (with which they create the requisite steampunk dirigibles) and the Germans have gigantic walking fighting machines (because really, what universe should not have these?) Deryn, a young girl, hides her sex to enlist on a dirigible, shipwrecks and falls in with a prince on the run. Similarly un-put-downable.

Relative neighborhood graph

2010-08-20T07:59:00.000-07:00

I've been trying out various things to improve camera control, but nothing good has turned up yet.

Currently the camera frames the player's rocket and the nearest objective. This can introduce a big discontinuity when a new objective becomes the nearest. The camera controller smooths its motion so it's not horrible but I think I'd like it to anticipate the transfer better. I've been trying out things in a testbed; if you'd like to try it you can get it here. It's a Windows application. Click or drag the mouse to move around; press the space bar to generate a new point set.

A screenshot appears above. The light-colored circle represents the current framing algorithm. The larger circle is an alternate method. What I really want is for it to interpolate between those two solutions so it frames things tighter when it's close to only one target, and then expand so there is a smooth transfer to the next objective.

I've also learned about some cool graphs. The application displays the relative neighborhood graph of the points. I'm not sure if it'll be useful here but I threw it in to see what it was like. It's a subset of the Delaunay triangulation that only contains an edge if there is no third point that is closer to both of that edge's endpoints.

Long, long ago I made a prototype for a game that was ultimately canceled. The idea for the game was that you'd have a map full of towns and villages and you'd help one or the other of a trio of warring factions to conquer all the territory. You'd do this in typical third-person action game format. (It was basically Dynasty Warriors Empires, but about five or six years earlier.) In my prototype I sprinkled towns randomly on the map and then made a Delaunay triangulation to determine which towns were neighbors; the mission generator would use this to generate sortie missions from one to another across the current borders. The problem with the Delaunay triangulation is that you have all these really long edges connecting vertices around the outer perimeter, which wasn't at all what I wanted. This relative neighborhood graph turns out to be exactly what I wanted back then.

Turret aiming

2010-08-09T07:53:00.000-07:00

Progress has been slow. I've been working on making the turrets aim:

After experimenting with projectiles that are influenced by gravity I'm now experimenting with ones that aren't. The goal of the turret is to find a spot along the rocket's projected trajectory where a bullet would arrive at the same time as the rocket. The turrets in the picture are assuming that the rocket undergoes constant acceleration. They use the sum of the rocket's current thrust acceleration vector and the gravity vector at the midpoint between the rocket and the turret. This gets them pretty close in the picture shown (the endpoints of the white lines) but often it's a lot worse. There are two reasons for this: the main one is that the gravity vector's strength changes with altitude and its direction changes as you go around the planet. A second inaccuracy is that when the player is thrusting without steering, the thrust vector is automatically rotated slightly as the rocket goes around the planet. (This essentially makes the thrust direction view-relative, since the view rotates in this way.)

I'm currently replumbing things so that the turrets can examine the plotted rocket trajectory instead. It is built using forward integration (albeit with a much larger time step than the game update) so it predicts where the rocket will go almost exactly. This should allow them to aim very accurately. In the past when I've worked on aimy-shooty things I've found that it's best to make them perfectly accurate and then work from there toward something that is inaccurate in a fun way.

The exact role of the turrets is not yet clear. It's no fun when you get shot with no time to react, so they need to be ineffective at close range. Probably they will avoid shooting at all at very close range (due to fear of unwanted splash damage, let's say). Making them turn slowly, and need to sync up to tracking the rocket's trajectory before firing, should also help.

I think I will plot the intercepts of all flying projectiles with your projected trajectory, although I don't yet know exactly what that ought to look like. Ideally it would give you an idea of the best evasive directions. It's possible that having all these trajectory plots will rob the game of any required skill, but my hope is that it will instead allow players to play a much denser game. I've noticed with the trajectory plots that I fly more aggressively than I ever would without them, and I feel much more in control as a result. Without plots I fly defensively and do a lot of waiting.

Ultimately you'd be able to destroy turrets to make things easier for yourself. (There'd probably be a bombing trajectory plot as well!) I've also been thinking about having turrets drop in from space over the course of the mission; maybe key the drops to astronaut pickups so that the difficulty ratchets up as you go.

Physics library updates, continued

2010-07-26T06:34:00.000-07:00

When I started using the Chipmunk physics simulation library I did what most programmers do when confronted with unfamiliar code: I rewrote it. It was a good way to learn the ins and outs of the code, and it did integrate better with my own code, but ultimately it meant that I wasn't benefiting from other peoples' continued work on the library. The whole point of libraries is to save work.

I've fixed up the current version of the library to work with my compiler (MS Visual C++) again. Scott Lembcke has accepted the patch into the main repository, so hopefully I can save someone else some work. I've also adapted my lunar lander program to work with the updated stock library, so now I should be able to get upgrades much more easily.

The end result, of course, is that the game looks and behaves exactly the same. I have turrets in an initial state; I will now dive in and work on getting them up to fully operational status.

Physics library updates

2010-07-19T07:29:00.000-07:00

For my lunar-lander-on-a-disc program I need some intersection-testing functions that were added to the Chipmunk Physics library I'm roughly based on. Since I translated the library from C99 to C++, though, I would need to translate the new code as well. This is a maintenance pain, so this weekend I spent some time trying unsuccessfully to get the stock library into a state in which I could use it.

I like Chipmunk; it's very understandably written and sensibly designed. I'm sure its author Scott Lembcke is reading this. (Hi Scott!) The key problem seems to be that the library is written in C99, a newer dialect of C which is poorly supported by Microsoft's C compiler. Since C99 moves C toward C++ I can get by with relatively small modifications if I compile the C code as if it were C++. Still, since the main library development isn't using my compiler I can expect to have to do this regularly.

As a result I've been examining Box2D some more. It builds easily out of the box, and it's written in C++ so it should mesh better with my project. It has a different approach to collision shapes; I'd need to break down the rocket hull into a set of convex shapes, but that wouldn't be hard. The terrain might be a bit more work. Box2D doesn't support line segments as a collision primitive (although there is contributed code to do so), so I'd probably take the triangulation and merge triangles into polygons up to the 8-vertex limit.

I've got various directions I can go and it's hard to decide how much work I should spend on this. I could patch up my library and continue working on gameplay; that might be the most prudent. Ultimately I want to produce a Flash version of the game, and I think Box2D might give me some help there.

What I'm Reading

2010-07-12T08:20:00.000-07:00

I went camping this weekend, so no programming, alas. When I wasn't herding children I worked on my reading research instead.

ThiefRL, when I eventually return to it, will be getting a layer of Chinoiserie. Here's what I've been reading in preparation:

China's Old Dwellings (Ronald Knapp)
Chinese Imperial City Planning (Nancy Shatzman Steinhardt)
Strange Tales from a Chinese Studio (Pu Songling, translated by John Minford)

My brother also picked me up some architecture books on his last trip to Shanghai; they're entirely in Chinese though so I can't give the titles.

Fox spirits seem to be similar to the fairies you find in British Isles folklore. Ghosts, on the other hand, are odd; I haven't really gotten a good handle on how they work. I just finished reading a story where a ghost ended up marrying a guy and bearing him a son, so it's not clear exactly how being dead slowed her down. I've read two stories so far where a guy has a three-way with a fox spirit and a ghost; that strikes me as a bit unrealistic, especially if said guy is a shy student with no obvious redeeming qualities.

Apparently the Strange Tales were heavily commented on by “scholars” of the succeeding centuries. The translator has mostly omitted these, but left them in on one story to give a sense of what they're like. The depth of the commentary on that story was similar to what you'd find in the comments section on an Internet article. I kept expecting to see “Firsties!” or “This. So hard.”

Turrets: First Steps

2010-07-08T07:51:00.000-07:00

I've started on implementing some turrets to shoot at the player's rocket.

This is a chance to use my aiming math (here's another explanation from Scott Lembcke with graphs instead of equations). So far I have the turrets aiming without regard for acceleration of any kind. I'm searching for a combination of parameters that will make the player react while still leaving them enough time to do so. I think I will want to make the turrets smart enough to take into account the rocket's acceleration; otherwise it's too easy to dodge them by just flying through with your engine blazing. Maybe there will be different kinds of turrets with different target-leading algorithms; if they're clearly visually different it could be interesting. One would aim to hit the rocket without considering velocity or acceleration; one would aim considering only velocity; and one would aim considering both velocity and acceleration.

Having some additional projectiles is making me realize that my gravity is not very strong. The bullets don't arc much. I don't remember but I think I originally sized the gravity so it would be similar to Earth gravity based on the rough size of the rocket. Just looking at how long it takes to fall its own height when starting from rest (at sea level). After I have the turrets basically working I think I'll do a round of gravity strength experiments. Of course the rocket engine will have to be scaled accordingly; it needs to be able to deliver greater acceleration than gravity at “sea level” (where the gravity is strongest). Scaling gravity up might speed up the gameplay which could be interesting. I have it in my mind to add on-foot movement (a la Star Guard) and wheeled vehicle movement, so the gravity will need to feel OK for those too.

The projectiles need a lot of extra work. They need to go away upon intersection with the rocket, and they need to deliver an impulse and some damage. At the moment they are regular colliding bodies, so they do deliver some impulse and damage but I'd like it to be arbitrarily tunable. I think I will have the bullets “fade out” over time so they deliver less damage as they age, before disappearing entirely.

The turrets need to have their range of motion clamped so they can't shoot into the ground.

I'm weighing whether it's worth it to have my own version of the physics library (I translated it from C to C++) and keep porting vendor drops from the original, or whether I should just write the necessary shims to connect up the C library to my vector class and what-not so I can use it directly. I'm sort of inclining toward the latter. I'm also looking at Box2D again, although I haven't quite figured out how I would translate my collision shapes to their model. They have a maximum of eight vertices per convex shape, I think, so I'd need to make a bunch of shapes to represent my curved surfaces (my game's all about curved surfaces).

Auto-zoom camera

2010-06-28T06:53:00.000-07:00

I've posted a new version of my lunar-lander-on-a-disc game to its little website. The addition of an auto-zooming camera makes the game much more playable most of the time. Changes:

Auto-zooming camera (can be toggled off with Space)
Improved landing gear graphics
Tuned landing gear physics
Rocket has to be touching ground with both feet to count as landed
Display elapsed time after completing mission

Teal-’n’-Orange!

The landing gear has been adjusted so it can't invert itself on hard impacts. I still need to transmit shock through to the hull when you reach the compression limit on the landing gear; a current “exploit” is that you can survive an impact of any magnitude so long as you can absorb it completely without letting the hull touch the ground.

Line drawing is very slow on some graphics drivers, so I'm gradually replacing my uses of that. The landing gear was one; the trajectory plots are the other.

The big change this week is the camera. Most of the time it works well enough that you can complete the game without needing to manually adjust it. The algorithm right now is very simple: it frames the rocket and the nearest objective.

The biggest place where this falls down is when you need to do some close maneuvering and the nearest objective is far away. It also doesn't work if the player has something else in mind besides going to the nearest objective. I've been trying to think of better metrics but haven't hit on anything yet. I think the camera needs may change once opposing force is added, so I will probably do that next. I'll start with some simple turrets and give the rocket the ability to shoot back.

Lunar Lander: Now with Fun

2010-06-21T05:59:00.000-07:00

What a difference a couple of tweaks make!

In the comments to my last post I mentioned that the game just wasn't that fun because the player spent a fair amount of time waiting for the rocket to follow its ballistic trajectory to get somewhere. Even with time acceleration this lacked pizazz.

Before introducing the Chipmunk physics engine, the rocket was represented by a disc for collision purposes and its heading was controlled directly with the mouse. When I switched to a physically simulated rocket I got rid of direct heading control; instead the mouse set a target heading, which the rocket would steer toward using attitude adjustment jets. This allowed ground impacts to spin the rocket around, which looks cool. Unfortunately it also introduced a lag in changing the rocket's trajectory, which slowed gameplay down.

I am now trying a hybrid: I've decoupled heading control from the main thruster. The main thruster always invisibly thrusts directly in the target heading direction, while the rocket attempts to steer toward that target heading over time. This gives a good balance between the visual effects of the rocket steering or bumping into things and the increased control of direct thruster orientation. In my opinion it feels much better; as a player I feel like I can play right up to the edge of my reaction time instead of waiting around for the rocket. Here's a sample landing; note that I am thrusting nearly the entire time:

I have also reinstated a couple more trajectory plots from the original prototype, which together also greatly improve the fun. In the video above you can see three lines emanating from the rocket. The dim blue line (which has existed in all versions) is the ballistic trajectory. If you let the rocket coast without thrusting this is the path it will follow. The bright blue line is the powered trajectory. If you hold down the thruster button without steering the mouse, this is the path the rocket will follow. The red line is the braking trajectory: if you were to always thrust in the direction opposite your velocity this is the path the rocket would follow.

The braking and powered trajectories together allow you to fly with the thruster on at all times. You can see where you're going with the powered trajectory, and the braking trajectory lets you know when it's time to reverse direction and slow down. Flying with thrusters on all the time makes the game move more quickly but more importantly keeps the player engaged and feeling in control. If you need a breather you can always fly ballistically so it has a good skill-development path, I think.

The rocket landing gear has been improved a bit as well. It has shock absorbers on both leg struts now (the lower strut used to be a rigid swing-arm). This makes landing in a concavity much smoother, since that tends to pinch the feet together horizontally.

I've put another release out so you can try it if you'd like.

The trajectory plots are still works-in-progress. Besides drawing nice-looking ribbons, I plan to replace the braking trajectory with a simple icon at its terminus, and I want to toggle the highlight between the powered and ballistic trajectories depending on whether the rocket is thrusting or or not. I've also considered trying to fold the braking info into the other trajectory plots by using different colors for different segments of the trajectory. The things I've tried in that line so far haven't been useful, though.

As currently configured, rendezvous with the mothership is not too hard but it could probably stand to have some sort of heads-up display help. I haven't figured out what that might be yet. I'm sort of waiting until I get the docking mechanism (and position on the mothership) finalized more.

If you try out the prototype and have interface improvement ideas I'd love to hear them. Some sort of automated camera framing is top of my list: it's very hard to fly and manage the camera at the same time.

Mothership, version 1

2010-06-14T06:29:00.000-07:00

There's now a mothership in my lunar-lander-on-a-disc game:

At the moment it just orbits around the planet. The idea is that after landing at all the ground targets the player has to rendezvous with the mothership to end the level.

The mothershp rendezvous necessitates additional camera work and probably also some work on the trajectory plots, so that is what I'll be doing next.

Games I'm Playing

2010-06-07T07:04:00.000-07:00

The runup to E3 at work has been busy. I've been getting back to putting in an hour a night on my lunar-lander-on-a-disc, though. Not a whole lot of progress to report. There are now landing targets distributed over the planet surface which detect when the rocket lands close to them.

I recently purchased a PlayStation 3 and have been catching up with some of the games on that platform.

Uncharted 2 is very, very pretty. I find the relentless shooting a bit monotonous, but they have done an excellent job of mixing storytelling and gameplay.

I'm replaying Super Mario Galaxy with my four-year-old. It's reasonably fun.

PixelJunk Shooter is a solid little game that I'd recommend to almost anyone. Its looks belie its technical sophistication. It's one of two games I played recently to compare and contrast with my lunar lander project. Shooter sets a high bar and is making me rethink some things. For instance, they use a grappling hook to rescue astronauts, instead of landing next to them as is traditional in this type of game. The result is that the game flow moves much more quickly.

My wife's been playing Picross 3D obsessively since it came out. I finally got some time with it last night; it is really, really fun. Picross 3D uses a rather heavy-handed tutorial system to teach you the game; after playing Everett Kaser's logic games, which always stay out of your way but provide excellent hinting, it's a bit hard to take. Otherwise it's great.

Gravity Crash is the other game I played for inspiration in my lunar lander game. Unfortunately I just didn't find this one very fun at all. It feels like a total ripoff of Gravitron 2, and one of the problems they share is a tendency to add energy to the ship when colliding with the terrain. The result is that one collision can quickly spiral into being completely out of control, bouncing this way and that until the ship explodes. It suffers especially when compared directly with PixelJunk Shooter.

Flower is a nice, short little game. My four-year-old can play it fairly well. I do wish there was an option to steer with an analog stick instead of with accelerometers. About half the time you feel like the wind soaring over a field of flowers (as intended), and it is exhilarating and beautiful. The other half of the time you feel like you're trying to turn a semi truck around in an alley.

Simplified, triangulated terrain

2010-05-10T05:39:00.001-07:00

I've continued to work on the terrain for my lunar-lander-on-a-disc game. The polygons are now simplified, which cuts out a lot of little bits that result from evaluating on a grid. It also lets me dial up the grid resolution so things are smoother where they need to be. After that I dropped in my polygon triangulation code. Right now the terrain clocks in at around 4000 triangles. This is how it looks with edges shown (click to enlarge):

Now I am working on offsetting the polygons by the radius of the rocket, in order to produce new polygons representing the accessible surface (and thus possible landing sites).

The next step is to intersect the new polygons (both with each other and with themselves), which should produce new interior polygons that can be stripped by examining their signed area.

Reading Outcast SFX files

2010-05-03T06:48:00.000-07:00

I've been replaying Outcast for the umpteenth time, courtesy of Good Old Games' rerelease and still enjoy it tremendously. (Here are some of my notes about why Outcast is cool.)

In a previous post I outlined how to read the contents of the game's archive files. Here I'll describe how the audio files are stored.

Audio files have .sfx extensions and there are vast numbers of them. They are compressed using the GSM 06.10 cell phone audio compression standard. All the audio files have a 20-byte header followed by a sequence of 33-byte frames of GSM data. Since this is a cell-phone audio standard, each frame can be decoded independently.

All the headers start with the same 12 bytes: 32 54 76 98 01 00 00 00 00 00 80 3F. After this comes two 4-byte little-endian numbers: the number of bytes of data following the header, which should be divisible by 33; and the sample rate (22050 samples per second in the file I'm looking at).

Each 33-byte frame decodes to 160 16-bit samples, so the compressed data rate is around 4.5 KB per second. I used code by Jutta Degener and Carsten Bormann to decode the frames.

Here's a random snip of dialogue from the game (ilott_found_naarn_g_7-9). Ilott has just learned of his brother's death at the hands of Kroax:

I have not had a chance to play with it, but I suspect that they get some of their “alien voice” sound by monkeying with the parameters of the linear predictive coding used to compress the audio, since it is essentially modeling a vocal tract.

Hole extraction

2010-05-03T06:38:00.000-07:00

I've returned to work on my lunar lander program by spending some time on the planet generation code. It now collects closed polygons and then throws out any that have negative area, so there are no longer any inaccessible interior regions:

I lost a fair amount of code in doing this. There is no longer a BSP representation; I'll need to do that in a different way if I end up needing it. There's also not a triangulation yet either, but I have code lying around that I should be able to plug in for that.

The current top priority is coming up with landing targets. I've been trying to think of a good way to identify accessible landing targets on a random terrain like this. Ideally it would be able to find "interesting" places to land.

Reading Outcast PAK files

2010-04-25T21:46:00.000-07:00

Good Old Games just released Outcast, one of my favorite games of the late 1990s. They're selling it for $6 USD. In honor of the occasion I've dug up some of my file-format hacking notes. I'm indebted to Dmitry Andreev for much of this info.

Outcast's archive files are stored in the relatively-obscure PKWARE Data Compression Library format, a variant of Lempel-Ziv-Huffman dictionary compression with static tables for the Huffman codes. The archive file contains an uncompressed directory followed by all the files, individually compressed. Multi-byte values are stored little-endian (least significant byte first).

All Outcast files start with a 2-byte magic number: (71 6e). For .pak files this is followed by ten more magic bytes: (0 0 d3 d4 7d 9 1 0 0 0). Next is a 4-byte value indicating whether the files in the archive are compressed or not. A value of 1 means they are compressed; a value of 3 means they are not.

Next up is a 4-byte value containing the number of files in the archive. Following it comes that many variable-length directory entries. Each directory entry starts with a variable-length string (a 4-byte count followed by that many bytes; no null terminators), which is followed by the 4-byte offset from the start of the archive to the file's contents; the 4-byte compressed file size; and the 4-byte uncompressed file size.

After that is the data for the individual files. Each file is compressed separately. I used code by Mark Adler to do the decompression.

Art

2010-04-25T21:34:00.000-07:00

We played pin-the-tail-on-the-bunny at my daughter's birthday party a few months back. I drew the playing area with Sharpie on butcher paper (letters indicate where the kids put their cotton balls):

I've had acrylic paints lying around for ages and finally tried them out today:

I really have no idea what I'm doing yet with the paints. Mysteries I need to solve:

What's the best way to mix paint? I used my brush but it seems like there must be a better way.
How can you get a good gradient? There's the problem of mixing a consistent set of colors and then the problem of blending on the canvas.
How do you paint sharp edges? I originally intended for the thing that became the sun to have a sharp edge but it looked horrible so I changed tacks.

I do like that they don't stink, clean up easily, and dry quickly.

Spiral Galaxy Hack

2010-04-11T15:29:00.001-07:00

The Pinwheel Galaxy

As a sidetrack from my sidetrack I've been reading about galaxy formation (among other things). Galaxies look like a drain swirling, but when you think about it that can't be how they move or else the arms would wind tighter and tighter until they disappeared. Likewise they can't move like a pinwheel since that would require the outer tips to move much, much faster than the inner core, in direct opposition to how gravitational orbits work.

On the Wikipedia page about density wave theory I found this diagram:

The idea is that star orbits are elliptical but they are not oriented in all directions with equal probability. Instead, the orbit's direction correlates with its size. At this point I took the ball and ran my own direction with it, so abandon all hope of physical plausibility, ye who read below.

If stars were influenced primarily by the massive black hole at the center of the galaxy, and not so much by their neighbors, then they'd follow roughly elliptical orbits. This is most likely wrong, but since I had already written a solar-system orrery program with this assumption, that's what I used.

If stars followed elliptical orbits, the ellipses would not be centered as in the diagram above; instead they'd have one focus at the center of the galaxy. The stars would spend more time at the far end of the ellipse than at the near end. If the far ends of the orbits were arranged in a spiral, you'd have a spiral region of high star density, like this:

I don't know what force would cause star orbits to align in this way. If it was a symmetric process you might end up with a separate set of stars following orbits aligned 180 degrees opposite, which would produce a two-arm galaxy:

I took my solar system orrery and replaced the planets and asteroids with random stars whose orbital parameters followed these ad hoc rules:

Pick a random eccentricity. I'm using a Guassian-ish distribution around 0.35, plus or minus 0.1.
Pick a random orbit size. I'm just picking a uniform number over a range of sizes, which is almost certainly unrealistic.
Pick a random initial position in orbit as a fraction of total orbit duration. This should be uniform although you can get some cool effects when it isn't.
Compute orbit orientation as a linear function of orbit size.
Compute a star color as a linear function of orbit size as well.
I'm not tilting orbits out of plane at all right now.

To plot the stars the orbital elements have to be converted to instantaneous positions, which takes a little bit of Newton-Raphson iteration. I used David Vallado's Fundamentals of Astrodynamics and Applications for the algorithm.

Here it is in motion; you can see how the stars come and go across the spiral arms but they are denser there. I don't know if real galaxies move at all like this, though:

If you'd like to scrub time back and forth and examine individual star orbits, here is the Windows program I wrote to generate the movie:

Galaxy.zip

Use the mouse wheel to zoom and the A key to toggle animation. You can also adjust the clock by dragging individual stars around their orbits with the mouse.

Network evolution algorithms

2010-04-05T08:30:00.000-07:00

Disparate fields that all involve growing networks:

My previous posts on randomly-exploring random trees: here and here.

How often do you see a white sports car?

And, The A to Z of Awesomeness.

Transcendence 1.0

2010-03-29T07:43:00.000-07:00

Transcendence reached version 1.0 this past week, so I have been playing some of that. George Moromisato has been developing it in his spare time for the past fifteen years. Transcendence takes the basic flying and shooting action gameplay of the Escape Velocity series and enfolds it in a game that is otherwise heavily indebted to Nethack.

After picking a trader/fighter/balanced ship, you are off on a quest to reach the galactic core or some such. You get there by warping through a series of semi-random solar systems.

Each system has jump gates connecting it to the next and previous systems; exactly like the up/down stairs in Nethack. Instead of rooms forming a dungeon you've got planets which orbit around the central star(s). At the planets you'll find friendly bases with shops and quests, or hostile bases which will deploy a bevy of fighters against you. Looting wreckage supplies you with things to use or sell. There are space analogues for magic potions and scrolls of enchantment. You have a deity to whom you can make sacrifices and from whom you can request aid. You've got tinker bases that will transmute junk into items according to their own recipes. There is a gladiatorial arena for earning money by fighting other spaceships. You can even acquire robotic sidekick ships. And behind it all is the ticking clock of your fuel consumption: run out and it's game over.

Unlike Nethack the universe is not wholly hostile. Trading ships ply the major routes within each solar system, and the friendly bases may have fighters that will launch to defend their allies.

The game's interface has some holes that I wish would be patched up. It's cumbersome to examine your ship's current configuration for comparison while shopping, for instance. When you are submitting items to the tinkers for transmutation it would be nice if the list would only show things they accept; nicer still to see recipes for things so you know what to be on the lookout for when you're collecting loot. Quest management could be improved as well; there isn't currently any way (that I've found) to remind yourself of the details about what you're supposed to be doing.

I wish there were more ability to communicate with other ships in the area. Being able to respond to distress calls or request help would do a lot to make you feel more connected to the world. Also there seem to be quite a few space bases that don't really do anything which just makes the universe seem more boring. I haven't figured out what the pubs and nightclubs are for yet, and since I've never been able to figure it out I've stopped looking into them. If they ever do become useful I won't know, and that's just bad design.

On balance, though, the game does do a fairly good job of encouraging you to play just a little bit more to see what new things you will discover. It's free so give it a try if you are at all a fan of space games or roguelikes.

Grrrr...

2010-03-22T07:55:00.000-07:00

Grrrr... not much to report.

I've wondered in the past if Haskell might make a good language for writing data compilers: something to take source art and turn it into something ready to be linked into the game. My thinking was that it would allow for concise construction of parsers, good error messages when input is ill-formed, and make it easy to morph the data through multiple representations in the compile process.

I needed some vector art for my lunar lander program and thought I'd just take SVG output from Inkscape and convert it to a triangle mesh for inclusion in my game. Seems simple enough. I don't know yet what the best way to represent graph structures like triangle meshes will be in Haskell, but I can probably dodge that for now.

Step 1: Install Haskell. There is an installer called the Haskell Platform which is supposed to be a one-step install for everything you need. On Windows it really hasn't been well thought out though. It installs to the Program Files (x86) directory by default, but Microsoft really wants this directory to be read-only apart from installation, which seems to break the Haskell package-manager's assumptions about what it can do. If you try to install to a different directory it doesn't respect that. Some things go to the directory you've specified but most things land back in Program Files (x86). Very unprofessional!

Step 2: Parse SVG. SVG is an XML format. There are five or six different XML parsers in Haskell with no clear indication of which one's “the one you should be using”. I have a book that uses HaXml so I look it up. It doesn't appear to be installed, even though it's part of the standard Haskell libraries. I run the cabal package manager to install it. Can't do it unless I elevate privileges to Administrator first. OK, that works. But on the web I see there's another one called the Haskell XML Toolkit; it claims to be better than HaXml. So I try installing it. It fails trying to install the curl library. After searching around on the web I find a thread from November 2008 describing what's wrong: the curl library installer depends on running a shell script of some sort, and on having the curl C library installed! So you need Cygwin installed. Once Cygwin is required you've lost me; sorry!

I'll try this out in Python next. I have a feeling it will be ridiculously easy.

GDC 2010

2010-03-15T08:05:00.000-07:00

The Game Developer Conference came and went in a hurry. I was severely disappointed to find that Emily Short's talk was on Tuesday, before I arrived. Likewise there was a physics panel on Tuesday or Wednesday featuring folks like Erin Catto and Erwin Coumans who I would have liked to meet.

The one talk I attended that really enthused me was a half-hour introduction to R-Trees, an adaptation of B-Trees to spatial indexing. Sebastian Sylvan's main point was that our current situation, with processor speeds greatly outstripping memory access speeds (particularly random access due to cache misses) is exactly analogous to the old days of database programming where disk access was very slow. Many algorithms (like B-Trees) that were developed to mitigate disk-access problems are useful in avoiding cache misses.

There wasn't time to do much networking at the conference but I did manage to meet Andy Korth and Scott Lembcke, the duo forming Howling Moon Software and the creators of the Chipmunk 2D dynamics library that I use in my lunar-lander program. They just announced a space game under development titled “Solaro”. I'm looking forward to seeing that one.

Landing gear continued

2010-03-08T07:32:00.000-08:00

I'll be at the Game Developers Conference this year; if anyone's interested in meeting up drop me a line: mcneja at gmail.

Is there anything so lovely or useful as a critically damped spring?

The basic differential equation:

This is saying that the acceleration (the second derivative) is a weighted sum of the velocity (first derivative) and position (x), measured relative to the desired velocity and position. The weights are expressed in terms of a constant omega which indicates the spring's response speed: higher omega means faster movement. The proportions of the weights are chosen to achieve critical damping: the spring returns to its rest position as rapidly as possible without overshooting.

To solve this differential equation we form and solve a characteristic equation:

Being critically damped makes the characteristic equation work out very simply. This then allows us to construct the general solution for position as a function of time:

The constants A and B are unknowns which we determine via supplying additional constraints on the problem, which will yield a particular solution for our problem. The first constraint I'll impose is that the spring is at rest position at time zero; the idea is that the landing gear is not stretched or compressed at the instant it touches the ground:

To solve for the constant B I'll supply a second constraint, which is that the spring is being compressed with speed v0 at time zero. This is the impact velocity. To use this we'll need to differentiate our general solution:

Plugging v0 into this yields the answer for B:

Now we have an equation for the particular solution of position as a function of time:

I have to get off to work now but suffice it to say there's a lot more tedious math where this came from. The next step is to replace omega as an input constant with something more useful: the maximum acceleration we want for the given impact velocity. To find this we have to check the extrema of the acceleration function, as well as the acceleration at time zero. Turns out time zero's acceleration is bigger than any other acceleration by a factor of about 40.

After that I've been working on adding gravity's constant acceleration into the equation which messes things up a fair amount, although the math's not hard.

Landing gear

2010-02-22T07:59:00.000-08:00

I've been working through the math for landing leg shock absorbers. Given the worst-case situation that it must handle (initial contact velocity, maximum acceleration, and surface gravity), the program should determine the dimensions of the legs and the constants for the springs and damping. I'm midway through though so I don't have anything to show.

One thing's surprised me so far, if I've done the math right. If the shock absorber is a critically-damped spring, the deceleration is maximum at the moment of first contact and tails off rapidly thereafter. With an undamped spring the maximum deceleration occurs at the point of maximum compression; an underdamped shock absorber would presumably fall between these two extremes. It seems to me that the ideal landing gear would just decelerate at a constant rate, to maximize the amount of deceleration relative to the length of the shock absorber, but I don't know that any landing gear actually works that way.

Combating comment spam

2010-02-13T08:58:00.000-08:00

The quantity of comment spam has been steadily increasing. I'm now disallowing anonymous comments; we'll see if that changes things appreciably.

Hull damage

2010-02-10T21:35:00.000-08:00

Continuing to work on my lunar-lander-on-a-disc, I finally got a basic damage model implemented. After the physics system has solved for a set of impulses to satisfy contact constraints, any impulses against the hull that exceed a threshold are scaled and applied as damage. There isn't yet any visible damage; it's just hit points. But the introduction of mortality takes this a step toward being a game.

I'm still trying to come to a big-picture understanding of damage, though. It seems like, in an inelastic collision, kinetic energy is being converted to heat (or some other deformation). I think a more accurate model might decide (based on the properties of the colliders) how to divide up the energy to be absorbed by each; and that the damage would be proportional to the energy absorbed. If this is the case it seems like the damage would be proportional to the square of the relative velocity, where in my current model it's a linear relationship.

Also this week I have begun to make a parametric hull design to allow for a range of rocket shapes and sizes. Time for a product plug:

This is the Lift-Off Rocket Playset and children love it. Buy one, invite them over, and watch the fights!

A few things you can't see in the photo: The nose has a hatch that opens to reveal seats for the two astronauts. The bed is a Murphy bed; it folds up to reveal the toilet. Beside the toilet is a roll of toilet paper and some reading material. In the back is a kitchenette with microwave and coffee maker. The top and bottom doors are designed to break away under stress to avoid permanent damage. Oh, and it has a button you can press to get noise and flashing lights out of the thrusters. This toy is an almost ideal marriage of stuff boys and girls like, which means none of them will want to be left out of the struggle over it. Which is where the breakaway doors come into their own!

Here's my rough likeness:

I got myself in over my head math-wise with the parametric model and ended up backing out slightly; you don't specify the height exactly from nose to base, instead specifying it from the top to bottom of the middle section before it's beveled by the round nose and the cropped bottom.

Upgrading the physics engine

2010-02-01T07:58:00.000-08:00

I'm continuing to work on my lunar-lander-on-a-disc game.

This week I started updating my physics engine to match the latest version of Chipmunk. My physics library is basically a C++ translation of Chipmunk, so it's easiest to just look at the diffs in the source library and make equivalent changes to mine. I also took the opportunity to replace uses of cpHashSet with more idiomatic C++ (std::set and std::map). This reduces the amount of code in the library and makes it more type-safe.

Upgrading the library is my way of re-familiarizing myself with the code since I have a set of high-priority physics-related things to do:

Detect impact damage
Finish landing gear: absorb shock in all directions, have a proper foot, and break if stressed too hard
Add hydraulic entry ramps that fold down when landed

I'm also interested to examine the new constraint model to see how things are arranged. It strikes me that you might be able to unify contact constraints and joint constraints into a single set of constraints; I'd have to look at things some more to decide if that would be worthwhile though.

Initial lander terrain triangulation

2010-01-25T07:41:00.000-08:00

I'm back in the saddle again (barely) on my lunar-lander-on-a-disc program. (The latest released version is here, but does not include today's changes.) I am working on triangulating the terrain so I can draw it as a solid mass rather than an outline.

My first pass does the job and fits into the recursive framework for how I'm creating the BSP and outline, but it isn't ultimately what I'd like because it wastes a ton of triangles in the interior:

I could just triangulate the outline, and I may end up just doing that. It will result in long sliver-like triangles, which aren't necessarily a problem. If I decide I'd like to render the terrain in several discrete chunks that can be culled independently, though, I'd want something different. I don't yet have a solid vision for how the terrain ought to look, so I'm experimenting.

I think I'd like something that is similar to this but replaces clusters of solid triangles with larger ones, so I'm working out how to do that.

I also want to filter out those inaccessible pockets inside the terrain (and maybe the floating islands), so I'm trying to figure out the best way to do that. I have several representations of the terrain and it's a trick to figure out how to process them all. The outlines would be an easy thing to cull: just remove all the ones that wind in the interior direction. Fixing up the BSP to remove the pockets would be more of a challenge, though. I sort of want to flood-fill BSP leaf nodes. BSPs don't have readily accessible connectivity information between adjacent cells, though.

"Raytracing on a Grid" updated

2010-01-10T15:40:00.000-08:00

Commenter SyntaxError has spotted and corrected several bugs in the code I presented in my article Raytracing on a Grid; I mention this in case anybody used the first or second pieces of example code as a basis for their own work. The code in the article has been updated and retested.

The core of the problem was that I was failing to account for the fact that zero multiplied by infinity yields an undefined result. This happened when both endpoints had identical horizontal or vertical coordinates, which you'd think I would have caught earlier.

Mini-reviews

2010-01-04T06:10:00.000-08:00

I actually managed to play some games over the holidays, something I haven't done much of in a long time. My opinions:

Torchlight: Pretty but extremely repetitive Diablo clone. Still good for a few hours of fun.

Might and Magic: Clash of Heroes: Fantastic gameplay burdened with a generic fantasy license (saying this as a one-time Might and Magic fan). Inventing a puzzle-based battle system has been a goal of mine for a long time and I'm very impressed with the one Capybara has concocted here. I saw Critter Crunch on PSN last month and there are definite similarities. I loved the fiction surrounding Critter Crunch. Here it's the usual overwrought elves-n-paladins stuff, but you should try your best to overlook that because the gameplay's great.

Zelda: Spirit Tracks: Partway into this one. Moderately interesting. The train seems like it has potential to be a real drag.

Halo: ODST: Meh. Fight a bunch of dudes through a series of tunnels that are supposed to be a city. Some day there will be a game set in a city where you can actually go into any building and the layouts are not intentionally mazelike to compensate for hardware handicaps. This is not that day. This is essentially the Halo 3 Remix, at least in the single-player.

Assassin's Creed: (the first one) Surprisingly less polished than I would have expected given the size of the development teams in Montreal. I'm only partway into this one; I like the environments. The animation is atrocious though, with pops and hitches continually violating characters' appearance of weight.

Mass Effect: Also only partway into this one. I love their character rendering system during cutscenes. Very cinematic lighting. Of course the lip-sync brings everything crashing down. Animation is the Achilles' heel of all current CG, even $350 million epics like Avatar.

Saira: Tried the demo, decided it was a bit too frustrating for me. I loved Nifflas' previous games though. If you haven't, check them out.

Another small lander prototype update

2009-12-14T08:12:00.000-08:00

Updates will likely continue to be slight in the time leading up to Christmas.

There is a new version of the lander prototype.

Changes:

Increased rocket thrust: main nozzle by 75%, steering jets by 150%.
Added inset rocket view in upper-right corner of screen; useful when zoomed out. This will likely be replaced or augmented by indicators displayed over the rocket's location in the main display, so you don't have to look elsewhere.
Altered camera framing algorithm to emphasize the interesting band of radii on the planet. It can be made smoother than it is; just haven't finished yet.
Limited full-scene antialiasing to 4X, rather than 8X. I got really bad performance on one of the machines I tested on so this is an attempt to improve that.

Slight update to lunar lander prototype

2009-12-10T06:37:00.000-08:00

I've uploaded a new version to the website with a couple of small changes:

Tuned the steering jet controller so it doesn't overshoot
Changed X/Z zoom controls to operate continuously
Fixed camera smoothing so it doesn't lag behind the rocket

Lunar Lander: prototype version 1 released

2009-12-07T22:32:00.000-08:00

Here is the first released version of my Lunar Lander program. It runs under Windows and requires Direct3D 9 to be installed. I had hoped to have more of a game by my deadline but didn't have time to implement much, so I've tried to tie things off so it is relatively bug-free and playable. Once some of the holiday madness subsides I will make another release.

You can fly the orange, spherical rocket around the planet and attempt to make soft landings. There are a couple of control schemes of varying difficulty. Controls in a nutshell:

Steer with the mouse
Accelerate with the left mouse button
Zoom view in/out with X/Z or 1-5
Restart if you get stuck with R
Esc pauses and displays additional help.

Known issues:

Occasionally the aiming rockets will rotate the vehicle the long way around.
It is possible to get positive feedback by pressing Tab to accelerate time while simultaneously increasing the orbit size; this will blow up the simulation and require a restart.

Once again, thanks to Scott Lembke for his Chipmunk physics engine, a heavily-modified version of which lurks within. Thanks also to my testers: Tom Elmer, Seth McNeill and David McNeill. Enjoy!

I've released a couple of other little games in the past:

ThiefRL, an attempt to amalgamate Thief with Rogue
SpaceRL, a very small Roguelike exploring zero-gravity movement

Merging and sizing rocket prototypes

2009-12-07T08:05:00.000-08:00

I continue to work on my Lunar-Lander-on-a-globe. The prototype with the Chipmunk-based rigid body dynamics has been merged into the prototype with the round planet. However, the dimensions of the two were completely different: the planet has sea-level radius of one; the rocket from the other prototype had a radius of 15. I'm still attempting to get all of the physical and control parameters adjusted to make things playable.

It finally became imperative to produce a workable camera. I've left zoom control manual for now but am otherwise quite happy with what I've got. It's yet another use of a critically-damped spring, to drive the camera parameters toward their goal positions. The goal positions are chosen to interpolate based on zoom level between a small circle surrounding the rocket and a bounding circle around the planet and rocket.

Next steps are to finish tuning the physics and control parameters; implement death and reset, and add some goal landing spots. Then I think I will do a release of what I have and shift focus to holiday-related chores. Some time around Christmas/New Year I should be able to devote energy to making it into a more interesting game.

Child of Fire, Red Cliff reviews

2009-11-30T07:48:00.000-08:00

The weekend, while long, was busy. We hosted two events: Thanksgiving and my daughter's fourth birthday party. I wasted what little free time was left reading Child of Fire: A Twenty Palaces Novel and watching John Woo's historical epic Red Cliff.

Child of Fire came to my attention via John Scalzi's Big Idea series, where authors get to plug their new books. First-time author Harry Connolly wrote an entry about his book that intrigued me despite the book's atrocious name. I finally got around to picking up a copy of the book and reading it. It's very well written and I'm looking forward to his future work. Recommended if you like Dashiell Hammett or Chandler.

Red Cliff is based on a 3rd-century battle retold in the 14th century Chinese novel Romance of the Three Kingdoms. When I worked at Midway we watched a bunch of Woo's films in preparation for working on a videogame with him. A lot of his trademark Wooisms can be found in this massive historical epic (cut down to 2.5 hours for US release). For instance, in Hard Boiled Chow Yun Fat's character blasts his way out of a hospital with a shotgun in one hand and a baby in the other. The opening of Red Cliff features a very similar incident, which I'm guessing was not in the original novel. Other Woo-bits include doves (of course) and Mexican standoffs, albeit with swords rather than guns. And random slo-mo of the duplicated-frame sort.

The characters felt really stale to me. I am interested in reading the original novel now to see if they are this one-dimensional there. The two characters that I felt stood out were Kong Rong (played by Wang Qingxiang), who was the tactical genius on the rebel side; and Xiao Qiao (played by Lin Chi-ling) who holds a Helen-of-Troy position in the story but with a strong Judith moment near the end.

I'd played one or two of the Dynasty Warriors games previously so a lot of the supporting hero characters (like Guan Yu) felt familiar. It is a little odd to have my scant historical knowledge derived from there, but that's how it is!

PID controllers

2009-11-23T06:40:00.000-08:00

My brother is an electrical engineer; he's working on unmanned aircraft autopilots, among other things. He recommended using a PID controller. “PID” is an acronym for proportional, integral, derivative, the three terms that make up the control equation. The controller measures the error between current and desired position. It also maintains an integral of the error, and estimates the current derivative of the error. Then it linearly combines these three values to drive something intended to correct for the error.

I tried out a PD controller (leaving out the integral term). The error is the difference between the target heading and the current heading. The derivative of the error is then the current angular velocity. These are combined to drive the nozzle angle, which is clamped to stay within its movement range. It's an extremely simple controller but the results are much smoother than what I had before:

In the video I'm aiming the green arrow and manually firing the rocket. The rocket rotates freely in between firings. The steering algorithm is applied to the nozzle even when I'm not firing so you'll see it rotating in preparation to align the rocket with the arrow.

In terms of control I'm pretty happy with this. I may add some additional rotation jets to the rocket to allow rotation without adding large linear velocities; they would probably be controlled with the same algorithm.

Oh yeah: this PD controller is pretty much the same thing as a damped spring. The nozzle angle doesn't translate linearly into rotational acceleration but otherwise it is the same thing.

Rocket steering methods

2009-11-16T06:39:00.000-08:00

My primary lunar lander prototype (not the one shown below) does not have true rigid body dynamics yet. The rocket's heading is driven directly by mouse movement. This makes it really easy to steer the nozzle but I have been unsure about how to alter it once the rocket can actually collide with the terrain in a way that applies torque. If you are able to directly rotate the rocket that could introduce unwanted interpenetration or arbitrary launch velocities.

I have a separate prototype at the moment where I am testing out the rigid body dynamics. The rocket, at the moment, has a single steerable nozzle. It will probably be necessary to add steering jets to make it easier to fly. Right now when you apply a torque to the rocket you are also applying a hefty linear acceleration as well.

The first control method is very simple to implement. The mouse rotates the rocket nozzle; the mouse button fires it. This is demonstrated in the first clip above.

In the second control method (shown in the latter half of the movie) the mouse sets a desired thrust direction. While the rocket is firing, an autopilot steers the rocket nozzle to align thrust in the specified direction. At the moment it's snapping the nozzle to one of three positions: extreme left, extreme right, and center. This is not terribly realistic; I'm still figuring out how to make it more natural.

Landing gear

2009-11-13T06:28:00.000-08:00

(The Khrest from Perry Rhodan. Artwork by Ingolf Thaler. From Perry Rhodan Nr 278, 16 December 1967. From Winchell Chung's Atomic Rocket.)

There's a plague going around at work; I eventually succumbed. Being sick for a few days has given me the opportunity to spend a bit more time working on my lunar lander program. I have been studying a couple of 2D physics engines (Chipmunk and Box2D) because I want to add rigid-body dynamics to it.

I'd already done a previous lunar rover test with Chipmunk (it comes with a rover sample) so I added a round rocket to that to try and figure out how to design the landing gear:

In this landing gear, the upper strut is a shock absorber, while the lower strut is just a swing arm. The foot's orientation is locked to the swing arm. This is OK, but the feet are forced to slide outward as the rocket comes to rest. If they hit an immovable obstacle there is an abrupt shock to the rocket. Ideally the feet would not have any lateral force but I haven't been able to come up with a geometry for that, short of just having some pistons sticking straight down out of the rocket. Adding some shock absorption capability to the lower struts would help.

I have decided to try and use Box2D (possibly modified to use my own vector class) instead of Chipmunk. That will take some time to install. Neither engine deals with BSPs so I will probably initially represent the planet with a collection of convex polygons (which will likely take a fair amount of memory), and add support for BSPs later.

Planet terrain collision

2009-11-02T07:30:00.000-08:00

When I started my lunar lander project several years ago the planet was a smooth disc. Detecting landings and collisions involved a simple radius check. Recently I dusted off the project and made a more complex, randomly generated terrain, invalidating that collision model. After putting the kids down for quiet time yesterday, I brewed a pot of coffee and set to work adapting collision code I'd written previously for Abyss, my Ultima Underworld hacking experiment. I have something that basically works, now, which is exciting as it is a big step toward this being a playable game.

Unfortunately there isn't much to see in still images. The rocket is prevented from going into the ground, that's all. I've included a couple of random screenshots just to have something to look at. Here's a shot of the final approach for a landing. The dim blue line is the ballistic trajectory and the brighter line is the powered trajectory. It's important not to let the powered trajectory dip below ground level!

This is zoomed out a lot more and shows the chaotic nature of the terrain that I've got at the moment:

The terrain generator is very simple, and generates inaccessible pockets of air inside the planet as well as floating islands in the sky. The floating islands are kind of cool; the inaccessible caves are just taunting; I need to remove them in a post-process.

For physics purposes, the terrain is represented by a binary space partition; the BSP divides up space into about 20,000 convex polygons (depending on the random terrain), some of which are solid and some of which are air. I use sentinel values in the child pointer slots of a BSP split node to signal solid and empty leaves, so there is no storage allocated for the leaves themselves. Each split node costs 20 bytes: the three line equation coefficients and pointers to its two children.

The rocket is currently represented by a disc. (Yes, eventually it will be more complex.) To detect intersections between the BSP and this disc, I traverse the BSP tree depth-first, building a stack of the currently active splitting lines. If the disc straddles a split line, the branch not taken is saved on a stack to be visited later. Otherwise I just go down the side containing the disc.

When the recursion hits a solid leaf, the stack of active splitting lines implicitly defines the polygonal region for that leaf. I have a function that returns the smallest separating axis between this region and the disc. If it turns out that the disc and the leaf region are overlapping, I generate a contact constraint in the direction of the separating axis.

This week I also switched all the code to 32-bit floating point arithmetic; large portions of it used 64-bit precision as a holdover from my orrery project. I also was able to reduce the integration from fourth-order Runge Kutta to a second-order method (Heun's). The main place this shows differences is when orbiting under high time acceleration.

One of the remaining top priorities is coming up with an adequate camera control algorithm. I'd really like to minimize the amount of manual control necessary, so I have to figure out what is important to show. Making a more complex rocket model, with shock absorbing landing gear, is another.

Lunar lander terrain progress

2009-10-26T08:38:00.000-07:00

I've been working on the terrain and camera control for my “Lunar Lander on a round planet” project.

The planet generator now creates a BSP representation of the terrain in addition to the boundary representation, to be used for collision and contact.

I downloaded the latest version of the Box2D physics engine to use as a reference. The released version has only convex polygons and circles as its physics primitives; I would need to compose a bunch of convex polygons to make the terrain. Apparently there is an unreleased version with an edge-list primitive, which could also work for the terrain.

Box2D and Chipmunk use spatial hashing rather than BSPs. I'm not sure yet which would be best for my planet; I'm going forward with a BSP for now. I have an idea for computing contact with BSP leaf nodes using the split planes to implicitly define the convex polygon around the leaf. That ought to use memory fairly efficiently.

When I started the BSP implementation I tried to set it up such that the deepest splits would identify which of their leaves were inside and which were outside (based on the surface normal). The idea is to avoid having any storage for the leaves; only for the splits. I think that only works if your splits always lie on the surface somewhere, though. I ended up using two sentinel values to represent inside and outside leaves (instead of the one sentinel value you'd need for the other scheme) and it simplified things considerably.

Implementing ray intersection against the BSP terrain has allowed me to experiment with some camera framing algorithms. Framing the ballistic trajectory is good for some situations. One problem is that the impact point can change distance instantaneously which makes the camera jump around. I also tried shooting a bunch of rays in all directions to form some sort of idea of the locally visible terrain, but this also tends to change in jumpy ways. Currently I'm working on an algorithm that is based primarily on the specific mechanical energy, since that changes smoothly.

Generating terrain with lots of tunnels made me realize that I needed to enhance my gravitation formula to work inside the planet. The force of gravity falls off linearly as you work your way from the surface to the center.

Perlin simplex noise

2009-10-12T06:50:00.001-07:00

I'm now working on my lunar lander program again. The core idea is to adapt Thrust gameplay for a circular planet, so that orbiting is a possibility. My goal is to release something in early December.

The top priority is to get an interesting planet to land on. I am working from these sources, albeit translating everything into two dimensions:

The basic idea I'm trying out is to define a density function over the plane, and then evaluate it to find the boundary where density crosses from negative to positive. The density function can be built up out of a variety of pieces; at the moment I'm starting with a radial increase with an offset (d = r - 1):

Layered on top of that are several octaves of Perlin's simplex noise. The first two are shown below:

I convert the implicit function to a surface by subdividing a large triangle that encompasses the planet; you can see its outline (cropped by the window rectangle) in the pictures above.

Below are the results of layering the radius function with three octaves of noise:

There are lots of other things to try; this is as far as I got last night.

The next step is to build a BSP or spatial hash in order to make the terrain solid. That should not be hard. After that I will probably want to triangulate the interior and texture it; I'm still thinking about the best way to accomplish that.

The noise functions don't guarantee that everything will be interconnected. You can see free-floating bits, as well as isolated pockets of air inside the ground. It might be nice to filter out the isolated pockets, and maybe justify the floating junks of rock by rendering a background layer to suggest that it's the cross section of an arch.

Mr. Roboto

2009-10-05T07:41:00.000-07:00

The Joel Test is a good starting point for gauging the level of professionalism where you work, or are thinking of working. One of the twelve items is “Do you use version control?” While this is incredibly important on its own, there are ways you can enhance your use of it.

The Perforce revision control software comes with a sample Python script for emailing out change notifications to everyone on the team. I improved the mail formatting a bit and we run it every fifteen minutes at work. I think it's a great motivator. After checking something in I find myself looking forward to receiving the email. When someone checks in a particularly important change people will hit “Reply” and congratulate them, providing even more positive feedback.

Change notifications are good to push to the team, as opposed to being fetched from a wiki or database, because they affect people in ways both expected and unexpected. It's good to know, even in a peripheral way, what's going on. Our art team receives all the same checkin emails, and often when something goes haywire it gives them a starting point for tracking down the problem. Similarly, sometimes a coder will see a checkin email and realize that the reviewer missed something: some of the checked-in code is a duplicate of something that already exists, say. It's easy to hit “Reply” and send the information to the person who made the checkin.

We've found other uses for automated emails at work. Once a week people get an automated email summarizing their open bugs, for instance. Another emailer that has acquired a personality of its own is Mr. Roboto (so named because it signs emails “Domo arigato, Mr. Roboto” after the Styx song).

Often an artist will create an entire suite of new files—model, sub-models, textures, and so forth—but forget to check in some of them. Since they have the complete set of files on their local machine they don't see that there is a problem for everyone else. It can be tedious to track down the responsible party by hand; thus the birth of Mr. Roboto.

Mr. Roboto does a dependency analysis every fifteen minutes and identifies files that reference missing files. Then he goes spelunking in the version control database to figure out who the likely culprit is. Currently he considers two scenarios: that the missing file was deleted, or that it was not added. If the missing file is in version control but has been deleted, Mr. Roboto complains to the person who deleted it. Otherwise, Mr. Roboto complains to the last person to change the file with the broken dependency.

This catches a lot of the most common problem cases. Obviously there are scenarios where this fails. For instance, I run scripts to do automated changes to large batches of art files periodically. Once I've done that I become the last changer on those files so complaints related to them come my way. It isn't too bad, though, and it encourages us to keep everything clean. Most of the time we aren't missing files, which has not been the case on previous projects I've worked on.

Since we now run Mr. Roboto every fifteen minutes to catch problems quickly, we ended up adding a throttling mechanism so he'd only complain about any given file once a day.

Makeover Concept

2009-08-06T02:00:00.000-07:00

Been thinking about possible graphical overhaul of ThiefRL. Basic idea is to keep things very symbolic (since realism is expensive and possibly less readable) while still making them more attractive.

I'm a fan of David Macaulay's books and am attempting to ape his illustration style to some extent. The left-hand side is crappy but I was experimenting with different line weights; ideally you'd have one or two line weights in the final drawing. I also need to figure out how to lay in ground texture while keeping it distinctly in the background. There could be watercolor-style washes of pale color under the ink-work.

There is a paper texture (not a great one) and some vignetting to suggest an overhead light source. The ink lines have been filtered a bit to look like they have bled a bit into the paper. People might be represented by tokens or push-pins on top of the page. It might be interesting to have little drops of blood soak into the paper and gradually oxidize at the spots where people are injured.

Compare to original ASCII-based shot:

Not everything has been transferred to the mockup. The aspect ratio of the mockup tiles is 1:1 while the screenshot tiles are 1:2, as well. Buildings would be redesigned to not looked squished under the square aspect ratio.

I've been kicking around the idea of putting walls on the lines between squares (instead of running down square centers) while I'm at it but I'm unsure if it would be a good idea or not.

You definitely get more of a “night” feel from the original. Maybe the “blueprint” look is not the best way to go.

Screenshots

2009-07-27T06:40:00.000-07:00

Due to various computer crashes and restorations I've ended up with several different versions of some of my main projects, with the rest scattered about. I've been sorting and consolidating them all into a single set, updating where possible to compile with Visual C++ Express 2008 and Direct3D 9.

I may need to break down and buy Developer Studio again; some of my projects use MFC or WTL and neither of those comes with the Express edition. I have one project (my 64 KB shooter) which needs to compile without the C runtime library; the new compiler is producing calls to a bunch more functions such as __IAtan2. The Express edition also does not include source for the C runtime library, so I haven't yet figured out what those functions are supposed to do.

“Penultima” started out as a turn-based game written as an exercise for a Mode X sprite system based on Michael Abrash's articles. Later, I was working on a COFF-based sprite animation system under DirectDraw, where the sprites are compiled into COFF-format object files (an almost entirely redundant phrase) and linked directly into the executable. I used this project as a testbed and turned it into a real-time game, although the gameplay isn't really all there. The main character is Link from his Minish Cap outing; not my own art.

Subdivision surfaces seem like they could be a handy tool to use for level construction. Here they're used to produce a cave-like space. I plan to revisit this soon; it ought to provide a good challenge for physics simulation.

These people are attempting to mill about without hitting each other; a project where I was exploring crowd movement. I think they're pretty cute; they also show up as bystanders in my 64 KB first-person shooter.

This is Marion Wolfe, love interest from Outcast, in her funeral bier. Outcast is a fantastic game and one that I spent quite a bit of time hacking on, deciphering the file formats.

When I was working on my 64 KB FPS I thought a lot about how to construct levels from tiny amounts of data. This house is made from a very simple input file describing the floor plan, and some descriptions of the door and window features. I'd love to pick this up again and expand on it; working from floor plans is a really quick way to build an environment.

After I finished Psi Ops I had some down time so I wrote an orrery. It uses massive tables of orbital elements from JPL to position the asteroids, planets, and comets. This shot illustrates the remarkable way in which Jupiter's gravity collects asteroids at points 60 degrees ahead of and behind it in its orbit.

This is the first level of Ultima Underworld: the Stygian Abyss. Another wonderful game that I've spent many hours hacking. Once I had the dungeon rendering it turned out to be a great place to work on first-person motion dynamics. Perhaps someday this will turn into a full-fledged remake, but there would be a lot of work to get to that point.

Knarly Hexes

2009-07-13T07:51:00.001-07:00

Go try Knarly Hexes, the latest game from Everett Kaser.

It uses the same mental muscles as Minesweeper but, being a Kaser game, has more interesting logic deductions and a comprehensive hint system to teach them all.

I also played the Geneforge 5 demo this week. The game presentation has definitely improved from the last Geneforge game I played.

In terms of work, here are a set of common HDTV and notebook display resolutions, and the tile sizes that divide evenly into them. (The minimum size I did was 10; there are several smaller tile sizes that would also work.)

Resolution	Tile Size	Grid	# Tiles
1280 x 720	10	128 x 72	9216
	16	80 x 45	3600
	20	64 x 26	2304
1280 x 800	10	128 x 80	10240
	16	80 x 50	4000
	20	64 x 40	2560
1440 x 900	10	144 x 90	12960
	12	120 x 75	9000
	18	80 x 50	4000
	20	72 x 45	3240
	30	48 x 30	1440
1920 x 1080	10	192 x 108	20736
	12	160 x 90	14400
	20	96 x 54	5184
	24	80 x 45	3600
	30	64 x 36	2304

Charlemagne, Disraeli, and Jefferson combined could not have done better! (in Haskell)

2009-06-22T06:00:00.000-07:00

...but hopefully you can. I added the “in Haskell” part because I'm not sure exactly what summons the Haskelling hordes.

I finished up a first pass at translating the ancient game Hamurabi from BASIC to Haskell; I recently bought Real World Haskell and wanted to have another of my periodic goes at using the language.

The original BASIC program weighs in at 4,230 bytes and 121 lines. My port is somewhat more portly, at 10,280 bytes and 287 lines. The executable compiled by GHC is a mere 1.414 MB, which is a couple of orders of magnitude larger than the original probably would have been. Here is the source as it stands now:

-- Converted from the original FOCAL program and modified for Edusystem 70 by David Ahl, Digital
-- Modified for 8K Microsoft BASIC by Peter Turnbull
-- Ported to Haskell by James McNeill

import Char
import Random
import IO
import Text.Printf

-- Data structures

data GameState = GameState {
    year         :: Int,
    people       :: Int,
    food         :: Int, -- bushels
    land         :: Int, -- acres
    landPrice    :: Int, -- bushels per acre
    totalDeaths  :: Int,
    cumDeathRate :: Double,
    rng          :: StdGen
} deriving (Show)

data Orders = Quit | Orders {
    acresToBuyOrSell :: Int, -- negative number means sell
    acresToPlant     :: Int,
    bushelsForFood   :: Int
} deriving (Show)

data Results = Results {
    peopleStarved      :: Int,
    peopleDiedOfPlague :: Int,
    peopleBorn         :: Int,
    bushelsEatenByRats :: Int,
    bushelsPerAcre     :: Int
} deriving (Show)

data ValidateResult a = Abort String | Retry String | Accept a

-- Code

main = do
    rng <- getStdGen
    putStrLn "Try your hand at governing ancient Sumeria successfully for a 10-year term of\noffice."
    let s = initialState rng
    showResults s initialResults
    doYears s
    putStrLn "So long for now."

showResults :: GameState -> Results -> IO ()
showResults state results = do
    printf "\nHamurabi:  I beg to report to you,\n"
    printf "In year %d, %d people starved, %d came to the city.\n" (year state) (peopleStarved results) (peopleBorn results)
    printf "%s" (if (peopleDiedOfPlague results) > 0 then "A horrible plague struck!  Half the people died.\n" else "")
    printf "Population is now %d.\n" (people state)
    printf "The city now owns %d acres.\n" (land state)
    printf "You harvested %d bushels per acre.\n" (bushelsPerAcre results)
    printf "Rats ate %d bushels.\n" (bushelsEatenByRats results)
    printf "You now have %d bushels in store.\n" (food state)

doYears :: GameState -> IO ()
doYears sIn = do
    let s = chooseNewLandPrice sIn
    orders <- readOrders s
    case orders of
        Quit -> return ()
        otherwise -> do
            let (sOut, resultsOut) = applyOrders orders s
            showResults sOut resultsOut
            let fractionStarved = (fromIntegral (peopleStarved resultsOut)) / (fromIntegral (people s))
            if fractionStarved > 0.45
                then do
                    printf "You starved %d people in one year!\n" (peopleStarved resultsOut)
                    putStr finkMessage
                else
                    if (year sOut) >= 10
                        then putStr $ finalReport sOut
                        else doYears sOut

readOrders :: GameState -> IO Orders
readOrders s = do
    printf "Land is trading at %d bushels per acre.\n" (landPrice s)
    buyLand s

applyOrders :: Orders -> GameState -> (GameState, Results)
applyOrders orders state = (stateOut, resultsOut)
    where
        stateOut = GameState {
            year = (year state) + 1,
            people = peopleFinal,
            food = bushelsFinal,
            land = landFinal,
            landPrice = (landPrice state),
            totalDeaths = (totalDeaths state) + peopleDiedOfPlague + peopleStarved,
            cumDeathRate = (cumDeathRate state) + (fromIntegral peopleStarved) / (fromIntegral peopleInit),
            rng = rngOut
            }
        resultsOut = Results {
            peopleStarved = peopleStarved,
            peopleDiedOfPlague = peopleDiedOfPlague,
            peopleBorn = peopleBorn,
            bushelsEatenByRats = bushelsEatenByRats,
            bushelsPerAcre = harvestYield
            }

        landFinal = (land state) + (acresToBuyOrSell orders)

        peopleFinal = peopleBeforePlague - peopleDiedOfPlague
        peopleBeforePlague = peopleFed + peopleBorn
        peopleDiedOfPlague
            | plagueRandom < 0.15 = peopleBeforePlague `div` 2
            | otherwise = 0
        peopleFed = min peopleInit (bushelsEatenByPeople `div` 20)
        peopleStarved = peopleInit - peopleFed
        peopleBorn = 1 + ((birthRandom * (20 * landFinal + bushelsFinal)) `div` (peopleInit * 100))
        peopleInit = people state

        bushelsFinal = (bushelsBeforeRats - bushelsEatenByRats) + bushelsHarvested
        bushelsEatenByRats
            | ((ratD6 `mod` 2) == 1) = 0
            | otherwise = bushelsBeforeRats `div` ratD6
        bushelsBeforeRats =
            (food state) -
            bushelsEatenByPeople -
            ((acresToBuyOrSell orders) * (landPrice state)) -
            ((acresToPlant orders) `div` 2)
        bushelsEatenByPeople = bushelsForFood orders
        bushelsHarvested = harvestYield * (acresToPlant orders)

        (birthRandom, rng1) = randomR (1, 6) (rng state)
        (harvestYield, rng2) = randomR (1, 6) rng1
        (plagueRandom, rng3) = random (rng2) :: (Double, StdGen)
        (ratD6, rngOut) = randomR (1, 6) rng3

buyLand :: GameState -> IO Orders
buyLand s
    | maxN <= 0 = sellLand s 0
    | otherwise = do
        choice <- readValidatedNum prompt validate defaultN
        case choice of
            Nothing -> return Quit
            Just n -> sellLand s { land = (land s) + n, food = (food s) - ((landPrice s) * n) } n
    where
        prompt = "How many acres do you wish to buy (0-" ++ (show maxN) ++ ")? [" ++ (show defaultN) ++ "] "
        maxN = (food s) `div` (landPrice s)
        defaultN = 0
        validate n
            | n < 0 = Abort abortMessage
            | n > maxN = Retry $ printf "Hammurabi: Think again. You have only %d bushels of grain.  Now then," (food s)
            | otherwise = Accept n

sellLand :: GameState -> Int -> IO Orders
sellLand s acresToBuy
    | acresToBuy > 0 || maxN <= 0 = feedPeople s acresToBuy
    | otherwise = do
        choice <- readValidatedNum prompt validate defaultN
        case choice of
            Nothing -> return Quit
            Just n -> feedPeople s { land = (land s) - n, food = (food s) + ((landPrice s) * n) } (-n)
    where
        prompt = "How many acres do you wish to sell (0-" ++ (show maxN) ++ ")? [" ++ (show defaultN) ++ "] "
        defaultN = 0
        maxN = land s
        validate n
            | n < 0 = Abort abortMessage
            | n > maxN = Retry $ printf "Hammurabi: Think again. You have only %d acres.  Now then," maxN
            | otherwise = Accept n

feedPeople :: GameState -> Int -> IO Orders
feedPeople s acresToBuy
    | maxN <= 0 = plantFields s acresToBuy 0
    | otherwise = do
        choice <- readValidatedNum prompt validate defaultN
        case choice of
            Nothing -> return Quit
            Just n -> plantFields s { food = (food s) - n } acresToBuy n
    where
        prompt = "How many bushels do you wish to feed your people (0-" ++ (show maxN) ++ ")? [" ++ (show defaultN) ++ "] "
        defaultN = min maxN (20 * (people s))
        maxN = food s
        validate n
            | n < 0 = Abort abortMessage
            | n > maxN = Retry $ printf "Hammurabi: Think again. You have only %d bushels of grain.  Now then," maxN
            | otherwise = Accept n

plantFields :: GameState -> Int -> Int -> IO Orders
plantFields s acresToBuy bushelsToFeed
    | maxN <= 0 = return (Orders acresToBuy 0 bushelsToFeed)
    | otherwise = do
        choice <- readValidatedNum prompt validate defaultN
        case choice of
            Nothing -> return Quit
            Just n -> return (Orders acresToBuy n bushelsToFeed)
    where
        prompt = "How many acres do you wish to plant with seed (0-" ++ (show maxN) ++ ")? [" ++ (show defaultN) ++ "] "
        defaultN = maxN
        maxN = min landAvailable (min (2 * foodAvailable) (10 * (people s)))
        landAvailable = land s
        foodAvailable = food s
        validate n
            | n < 0 = Abort abortMessage
            | n > landAvailable = Retry $ printf "Hammurabi: Think again. You own only %d acres.  Now then," landAvailable
            | n > 2 * foodAvailable = Retry $ printf "Hammurabi: Think again. You have only %d bushels of grain.  Now then," foodAvailable
            | n > 10 * (people s) = Retry $ printf "But you have only %d people to tend the fields.  Now then," (people s)
            | otherwise = Accept n

finalReport :: GameState -> String
finalReport s =
    "In your " ++ show numYears ++ "-year term of office, " ++
    show (round (100.0 * avgDeathRate)) ++ " percent of the\n" ++
    "population starved per year on average, i.e., " ++
    "a total of " ++ show numDeaths ++ " people died!!\n" ++
    "You started with 10 acres per person and ended with " ++
    show (round acresPerPerson) ++ " acres per person.\n" ++
    comments
    
    where
        numYears = year s
        numPeople = people s
        numAcres = land s
        numDeaths = totalDeaths s
        avgDeathRate = (cumDeathRate s) / (fromIntegral numYears)
        acresPerPerson = (fromIntegral numAcres) / (fromIntegral numPeople)
        comments
            | avgDeathRate > 0.33 || acresPerPerson < 7 = finkMessage
            | avgDeathRate > 0.1 || acresPerPerson < 9 =
                "Your heavy-handed performance smacks of Nero and Ivan IV.\n" ++
                "The people (remaining) find you an unpleasant ruler, and,\n" ++
                "frankly, hate your guts!\n"
            | avgDeathRate > 0.03 || acresPerPerson < 10 =
                "Your performance could have been somewhat better, but\n" ++
                "really wasn't too bad at all. " ++
                show numHaters ++ " people would\n" ++
                "dearly like to see you assassinated but we all have our\n" ++
                "trivial problems.\n"
            | otherwise =
                "A fantastic performance!!!  Charlemagne, Disraeli, and\n" ++
                "Jefferson combined could not have done better!\n"
        (numHaters, _) = randomR (0, (numPeople * 4) `div` 5) (rng s)

readValidatedNum :: String -> (Int -> ValidateResult Int) -> Int -> IO (Maybe Int)
readValidatedNum prompt validate defaultValue = do
    putStr prompt
    hFlush stdout
    line <- getLine
    case maybeRead line of
        Nothing -> return (Just defaultValue)
        Just n ->
            case validate n of
                Accept n -> return (Just n)
                Abort s -> do
                    putStrLn s
                    return Nothing
                Retry s -> do
                    putStrLn s
                    readValidatedNum prompt validate defaultValue

maybeRead :: Read a => String -> Maybe a
maybeRead s = case reads s of
    [(x, str)] | all isSpace str -> Just x
    _ -> Nothing

chooseNewLandPrice :: GameState -> GameState
chooseNewLandPrice s = s { landPrice = newLandPrice, rng = newRng }
    where (newLandPrice, newRng) = randomR (17, 26) (rng s)

initialState :: StdGen -> GameState
initialState rng = GameState {
    year = 0,
    people = 100,
    food = 2800,
    land = 1000,
    landPrice = 0,
    totalDeaths = 0,
    cumDeathRate = 0,
    rng = rng }

initialResults :: Results
initialResults = Results 0 0 5 200 3

abortMessage :: String
abortMessage = "Hammurabi: I cannot do what you wish!\nGet yourself another steward!!!!!"

finkMessage :: String
finkMessage =
    "Due to this extreme mismanagement you have not only\n" ++
    "been impeached and thrown out of office but you have\n" ++
    "also been declared 'National Fink' !!\n"

I've tried to mimic the original functionality as closely as possible. One small addition I made was for the program to print the range of valid input numbers after a question, as well as a default number which will be used if the player just presses Enter. This makes play a bit quicker.

It really bothers me that this program is so much longer than the original. I expect newer languages to have more power for making programs easy to write and read. If you have any concrete suggestions about how to improve/shorten this code (preferably with code snippets) I would love to hear them in the comments. I know this is pretty bad code.

I've separated getting instructions from the player from updating the game state. This allows the state update to be a pure function, but also means that some of the game state update has to be simulated during the process of getting instructions, so as to predict (for example) how much grain will be available for planting after feeding people. This causes some duplication of code.

The getting-instructions part is messy; you can see four very-similarly-shaped functions named buyLand, sellLand, feedPeople, and plantFields. These correspond to the four questions asked of the player. I'd like to find a way to extract more common structure from these since they are so similar.

The question-asking functions are chained so that each calls the next, if it is necessary to go on; the last one returns the completed Orders data structure. I don't like this structure; I'd prefer one where the questions were posed more independently. Unfortunately it is possible for the game to end immediately if the player ends a negative number which complicates control flow.

I will do a Python version of this some time. I expect it will turn out a bit longer than the BASIC due to using reasonable names for things but it will likely not be anywhere near this much longer.

This week I have also become infatuated with Mike Singleton's 1984 ZX Spectrum game The Lords of Midnight. I've been playing Davor Cubranic's Java port of it. Icemark.com is a website with lots of good info about how to play the game or its sequel.

Lords of Midnight is kind of a precursor to games like Heroes of Might and Magic, where the player commands armies led by heroes across a map. The big innovation in Lords of Midnight is that everything's done from a first-person perspective. This is of mixed benefit: it's more immediate, but you will find yourself playing primarily from a map (which you would have drawn on graph paper, in the old days) anyway. Everybody loves the 3D, with the people and the sunsets and the arrows flying right at my eye! but so often it just isn't the best perspective.

The other novel thing, again with middling success, is that it attempts to give situational reports in prose, as you can see in the screenshot. This is something that I think could be greatly improved and could actually prove useful. In this style of game you have to cycle through all your living heroes at least once per day to move them. It can be difficult to remember just who has done what, and where they're headed. A summary paragraph could be really nice.

I beg to report to you

2009-06-15T07:37:00.001-07:00

I continued to work on my Haskell port of Hamurabi. (Here's a PHP version of Hamurabi that you can play in your browser.) It is nearly feature-complete; the yearly cycle works but it does not have impeachment or the final report after ten years. However it is still rather ugly. I should have something to share by next week.

I want to finish this up and move back onto ThiefRL. I've decided to bite the bullet and try a different turn order. I want to see what it's like when guards can prevent the player from getting past them, but to do that I need them to be able to see which way the player wants to move so they can intercept. So the turn order will be something like:

Display
Get player input
Get guard input (with guards looking at player input)
Resolve player's and guards' movements

The current turn order is mostly an “I go, you go” type of thing. The main exception is that guards' awareness is updated at the display point, rather than at the moment of their turn, thus ensuring that they see the world as it was displayed to the player.

Messing with Haskell

2009-06-08T07:25:00.000-07:00

This week I spent some time attempting to port the old BASIC game Hamurabi to Haskell. I'd picked up a print copy of Real World Haskell so I was looking for something to try out.

It's been a challenge, and I haven't gotten as far as I would have expected. I wish the Haskell documentation, whether online or provided with the installation, was put together better. I'd like to have ready access to a language reference, not just the auto-generated library documentation; I'd like to have lots of sample code snippets; and I'd like for it to be fully searchable.

For instance: in BASIC you can write INPUT A to read an integer from the keyboard. The closest equivalent in Haskell is read but it aborts the program with an exception if the user does not type in something that can be parsed correctly. Since I was attempting to match BASIC's behavior I needed it to be able to deal more gracefully with bad input. With Google I eventually found a thread somewhere addressing this problem.

So far my program is not ending up any smaller than the original BASIC version, which surprises me a bit. I'm having difficulty deciding the best way to structure the program. I've discovered a method that emulates BASIC's goto style pretty closely, but it doesn't seem like that's necessarily a step toward readability, because the flow of control is embedded throughout the program:


main = buyLand

buyLand =
    [choose how much land to buy with stored food]
    if bought land:
        feedPeople
    else:
        sellLand

sellLand =
    [choose how much land to sell for food]
    feedPeople

feedPeople =
    [choose how much to feed your people]
    plantFields

plantFields =
    [choose how many acres to sow with seed]
    displayYearResults

displayYearResults =
    [show what happened as a result of player's choices]
    if game not over:
        buyLand

I've omitted several additional control branches: If the user inputs nonsensical numbers the original program sometimes prints a huffy message and quits.

There is a basic game state that I pass through all the functions; it contains information that needs to persist from one year of game time to the next. There are additional bits of information that flow between some stages as well. For instance the choice of how many acres to sow with seed is needed in displayYearResults but not needed after that, so I've left it out of the main game state.

Simple as Hamurabi is, I found myself needing to step back and do an even simpler game first. Here's one where the computer picks a number and the player tries to guess it:


-- Computer chooses a number; player guesses what it is
-- Example of basic I/O

import Char
import Random
import IO

minNum = 1
maxNum = 1000

main = do
    targetNum <- randomRIO (minNum, maxNum)
    putStrLn ("I'm thinking of a number between " ++ (show minNum) ++
        " and " ++ (show maxNum) ++ ". Can you guess it?")
    guess 1 targetNum

guess :: Int -> Int -> IO ()
guess totalGuesses targetNum = do
    putStr ("Guess " ++ (show totalGuesses) ++ ": ")
    hFlush stdout
    line <- getLine
    case (maybeRead line) of
        Nothing -> putStrLn ("Give up? The number was " ++ (show targetNum) ++ ".")
        Just guessedNum ->
            if targetNum == guessedNum then
                putStrLn ("You guessed it in " ++ (show totalGuesses) ++ " tries!")
            else do
                putStrLn hint
                guess (totalGuesses + 1) targetNum
            where
                hint = "My number is " ++ lessOrGreater ++ " than " ++ (show guessedNum) ++ "."
                lessOrGreater = if targetNum < guessedNum then "less" else "greater"

maybeRead :: Read a => String -> Maybe a
maybeRead s = case reads s of
    [(x, str)] | all isSpace str -> Just x
    _ -> Nothing

This should give an idea of the level of verbosity that I'm contending with right now. Hopefully I can improve on this and come up with a clean way to structure the more complex program.

Back to work on ThiefRL

2009-06-01T07:25:00.000-07:00

I spent Sunday morning trying to get my head back into my ThiefRL project. It seems to have promise. The question is how far to push with it. I have a bunch of potential features and I'm trying to organize and prioritize them.

I decided to axe a couple of potential features in order to keep the scope feasible. I'd been thinking about having sidekicks whose movements could be planned out ahead of a heist to some extent. The benefit would have been that it would create nice inter-character relationship fodder. However it would also involve an additional game mode (the planning stage) and it's not clear to me what, exactly, they would do. I worry that if they are capable of doing the same things as the player they would just steal the fun.

The other feature I've decided to drop is the idea of open-city gameplay. I'd been considering having big open cities with compounds embedded in them for more focused gameplay. However I worry that it would be difficult to get the density of risk and reward encounters up to acceptable levels across an entire city. It could certainly be done, but I am going to focus on running the player through a series of smaller areas instead.

These things could always be added in a sequel. Thief 3 added a city hub, for instance, which connected together all of the mission levels. I remember the city portion as being moderately successful.

I got a friend of mine who is a veteran gameplay designer/programmer to try it out recently. He said it was too difficult so I have been considering solutions. Part of the problem, I think, is training the player to move diagonally around corners to gain distance from pursuers. If I had the player follow an NPC in an early mission that might help with that.

I also need more ways to get away. I've got various ideas for that, and just need to start trying them out.

Weaver Modulation

2009-05-03T20:26:00.000-07:00

...about sins of omission there is one particularly painful lack of beauty,

Namely, it isn't as though it had been a riotous red letter day or night every time you neglected to do your duty;

You didn't get a wicked forbidden thrill

Every time you let a policy lapse or forgot to pay a bill;

You didn't slap the lads in the tavern on the back and loudly cry Whee,

Let's all fail to write just one more letter before we go home, and this round of unwritten letters is on me.

(From Portrait of the Artist as a Prematurely Old Man by Ogden Nash)

The frenzied finish to inFamous has subsided and I've just finished up a week of vacation. A large part of the week was spent atoning for sins of omission: visiting the dentist, renewing my driver's license, returning clothes to stores, mopping floors, and so forth. I have been reading and thinking, too, though, and finally put fingers to keyboard in the last couple of days.

The earpiece is one of videogames' hoariest clichés. Generally there's a sexy-voiced female operative on the other end dispensing instruction, exposition, and exhortation. Infamous has it; Sly Cooper has it in nerdy-turtle form. In Psi Ops we mixed things up by using telepathy (can't tell you how many times I had to listen to what's-her-name say “I'm speaking to you in your mind, via telepathy”), but generally it's assumed to be some sort of magic radio that never fails unless the story requires it. Anyone who has used a cell phone knows this is a major simplification.

One of my childhood memories is of listening to amateur radio in the HF band. Radios in this band use single-sideband amplitude modulation because of its efficient use of both power and bandwidth. As you tune across a signal with an SSB radio you get some really interesting effects on the voice. Here's an example of a sexy-voiced female spy transmitting her report as a series of spoken numbers:

(Borrowed from this site. You may need to use Firefox or Chrome to see the embedded players; I had a lot of trouble even getting them to appear in Firefox. If they don't, you can always click on the links to the MP3 files and play them yourself.)

A lot of what you hear in this recording is noise, but the reason for the odd effects on the voices is that AM radio consists fundamentally of frequency shifting. A signal in the audible range of frequencies (20-2000 Hz, say) is shifted up by a whole lot (e.g. to 2 MHz) and then broadcast using radio waves. After receiving the signal, it is shifted back down to audible range to drive a speaker. If it isn't upshifted and downshifted by the same amount all the harmonics in the signal become misaligned with respect to each other. Human voices and our understanding of them are all about harmonics (which is why linear predictive coding works so well) so they sound pretty strange when they are out of alignment.

I'm interested in simulating what this round-trip transmission/reception does to an audio signal in the presence of noise and/or mistuning. The core part is the frequency shifting. I found an article that describes beautifully how to do digital frequency shifting using Weaver modulation. Since it is nicely illustrated and I'm still learning this stuff I refer you to it.

My three-year-old daughter supplies the audio clip for today's demonstration. (I've awakened a monster; ever since, it's been a never-ending litany of “Can we sit in front of Mommy's computer and say ‘Weaver modulation’ again?” Stage Dad, here I come!) First the original, and then a series of shifts upward and downward from there.

Original:

Here are the results of shifting this audio by a variety of frequency offsets:

Shifted down 10000 Hz:

Shifted down 5000 Hz:

Shifted down 1000 Hz:

Shifted down 500 Hz:

Shifted down 100 Hz:

Shifted down 50 Hz:

Unshifted:

Shifted up 50 Hz:

Shifted up 100 Hz:

Shifted up 500 Hz:

Shifted up 1000 Hz:

Shifted up 5000 Hz:

Shifted up 10000 Hz:

Shifted up 22050 Hz:

The recording was made using the Zoom H2 Handy Recorder, which lives up the “handy recorder” part of its name. It was a birthday gift from my wife, who researched the various options and found the one that delivers the best bang for the buck. It is also popular with music teachers in eastern Washington (my mother tells me) and my brother said he wished he'd bought one instead of whatever he did buy for field-recording classroom instruction. Highly recommended!

SpaceRL released

2009-03-16T06:08:00.000-07:00

I knew ahead of time that it would be next to impossible for me to enter this year's Seven-Day Roguelike Challenge due to my work schedule. When the call for dates went out at the beginning of the year I decided to start immediately on something small in the hopes of having it ready to release to coincide with the Challenge deadline, since deadlines are good to have. The core idea was to try and approximate zero-gravity movement in a turn-based, square-based game, as I outlined in my previous post.

Starting with the engine for ThiefRL, my unreleased stealth-based Roguelike (eh; might as well release it now), I stripped out the sound propagation, guard speech, and various other things. I kept the line-of-sight code, the pathfinding, the map structure, and the basics of the monster type. I added in a random map generator from another experiment I'd done in villa creation, and I created the basic inertia-based movement scheme.

And that is pretty much where it is now.

I spent a huge amount of time thinking about how to do predictable rigid-body dynamics so that you could push collections of objects around (or be pushed by them). In the end I had to abandon all of that in order to get something done. Currently, only you and the monsters move, and the monsters don't obey the zero-gravity movement rules.

I also spent a huge amount of time on the dungeon (a.k.a. starship wreck) generator. I'm happy with the overall shape of the spaceships. Here are some examples (click to enlarge):

The generator starts with a target number of rooms and a horizontal or vertical symmetry axis. It accretes rooms next to existing rooms. Each placed room adds its four neighbor positions (if they're not already in use) to a set of candidate positions. The next position to use is drawn randomly from that set. Thus empty positions become more likely to be used as they acquire more used neighbor positions.

Once the core room layout is created, the walls are randomly offset by up to half a room in either direction. A fixup process ensures that rooms don't overlap by picking horizontal or vertical at each intersection and forcing the walls to align in that dimension at that intersection.

Next is the crazy part. Originally I allowed doors only between rooms that were adjacent in the original grid. However, the wall-shifting can create new adjacencies. At considerable pain I created a system to identify all adjacencies and form a graph of possible room connections (doors). Then I create a simply-connected graph by randomly adding edges between unconnected components until the entire spacecraft is connected. This ensures that you can always get everywhere. After that I add a random fraction of the remaining unused edges, as well as some doors to the outside.

I got partway through cleaning up the door placement. You may notice in the maps above that some doors are placed symmetrically and others aren't. I'd like to have the underlying door structure be symmetric, and then block or destroy doors to satisfy the level connectivity requirements, which would be determined by a system that would take into account locked doors and key placement; that sort of thing. You want to make the player work a bit to get through the level.

I also got partway into implementing air ducts: an alternate movement layer which only the monsters can use. The idea is that they can't open or close the doors, so if you close the doors they will backtrack to the nearest duct and get through to you that way. I think it shows promise but I just didn't get it done in time.

I've got loads of additional feature ideas which I'd like to put in when I get more time.

The ThiefRL game I linked to above is an entirely different experience. It features a single hand-authored map at the moment, which I have been using to test out gameplay features. You can't kill anything in that game, although you do play a threat to society. I'd estimate that it's got 30 minutes to a couple of hours of gameplay in it right now, and is quite a bit more fun (I think) than SpaceRL.

Square-based, turn-based rigid-body dynamics

2009-03-01T20:07:00.000-08:00

The day job's been very busy lately. I'm finishing up a game (Infamous) which I've been working on for something like three and a half years. I've always wanted to be on a game project from start to finish, and I'm almost there. It's sobering to think of my life in chunks of this length, though. I have two daughters I didn't at the start. How many more of these do I have left in my career? etc. It's night and I'm maudlin.

At home I've been thinking, fairly fruitlessly, about how to put simple rigid-body dynamics into a Roguelike framework. This was the inspiration:

In this scene from Tobias Buckell's Caribbean-flavored space opera, the heroes propel themselves across the zero-gravity core of a space colony by pumping lead into their pursuers with a giant Gatling gun.

The other inspiration would be Space Hulk, I suppose, although I've never played it.

First, I repurposed an earlier attempt to randomly generate villas to create derelict starcraft:

I did some work on opening and closing doors using bumping alone and finally came up with something I like. Bumping a door head-on opens it; the problem was always to come up with a reasonable interface for closing the door again. What I have now is that if the door is open and you stand in front of it and diagonally bump the door frame on either side it will close again.

My other current Roguelike-in-progress uses a Ctrl-dir key chord to close doors. In this game I'm devoting the Ctrl-dir key chords to shooting; the idea is that when you're shooting you keep moving in whatever direction you were moving the turn before (floating in zero gravity). Also, you cannot change your movement direction unless you're adjacent to a wall or other mass.

I mocked up movement for the player character and it went pretty well. I threw in some really basic monsters, and as soon as I gave them enough hit points that they took several turns to kill it got interesting. You'd want to lead them to a straight corridor, kick off, and glide backward while shooting.

The “physics” seems like it has potential for some interesting gameplay. For instance there might be a monster that can't be killed, only stunned. Permanently neutralizing it would involve pushing it to the nearest hatch and committing it to the void. Or you could have crate-stacking, but IN SPACE...

I thought it ought not to be too hard to adapt a rigid-body physics system to a turn-based, square-based regime but so far it has stymied me.

The important thing, I think, is for it to be predictable to the player. Positions are constrained to squares, obviously, and I want to prohibit multiple objects in the same square. I've decided to constrain velocities to be integral in each component as well. Furthermore I'm trying to constrain velocities to be -1, 0, or 1 in each dimension. Velocities of 2 or more might be okay for some things, but experimentation is necessary.

I've tried out solving collisions and contacts using a fairly standard impulse-based solver, in floating-point, and then rounding velocities back to integers. It doesn't yield good predictability though and falls down on some fairly simple cases, like a line of crates hitting another line of crates. With the right numbers of crates you can get it so that the momentum hasn't been totally propagated throughout the stack and some crates round to zero velocity and others not, which means they move on top of each other.

Contact is a tricky concept in the grid-based environment too. Objects that are diagonally adjacent are contacting if they're moving toward each other, but not if they are moving past each other. A conventional “relative velocity dotted with contact normal” approach can't distinguish these.

You can also have objects that will move into the same square on the next turn if left alone but which aren't actually adjacent at the start of the time interval. What ought to happen in these situations?

I'm now working out some problems on paper in terms of generating sets of contact constraints and solving them as a system of linear equations. I think it might be possible to do that with rational arithmetic so that everything comes out perfectly. There are some cases I'm not sure about though.

If you have any good ideas about doing “physics” in a turn-based, square-based game, I'd love to hear them. I feel like I'm spinning my wheels on this right now.

(An academic paper on this might be titled Rigid-body dynamics with large-scale time and space discretization.)

Spirit Engine 2 (demo)

2008-12-08T08:19:00.001-08:00

I have been too busy keeping the household running this week to get any programming done.

I did manage to play the demo for The Spirit Engine 2, a largely-solo development effort. Mark Pay did the coding, design, and art, with Josh Whelchel composing three hours of music for the game. The game is a side-scrolling role-playing game set in a fairly novel universe (to my eyes, anyway) reminiscent of some of Miyazaki's movies. The production values are excellent. The writing could stand tightening in places but is nonetheless quite readable. Having not played the entire game I can't judge the overarching storylines although there appears to be some fairly heavy foreshadowing. If the mysterious overlords who manage the affairs of men don't turn out to be evil I will be stupefied with astonishment.

My main gripe is that the battle system is not explained in enough detail. It involves building chains of actions for each party member (prior to battle) and then selecting chains of actions dynamically. I don't have a good handle on how to do this, though; the tutorial didn't go into it very well. The interface for building action chains could stand to be improved as well; you can't examine the details of actions while you are assembling chains.

Another problem is that the keyboard interface seems to be an afterthought. I played mostly with the keyboard and it took me a while to figure out that I could open treasure chests, for instance, since they have to be clicked with the mouse. This wasn't explained.

Basically, the game could stand to have more focus-testing on new users to ensure that the ramp-up is smooth. Otherwise, it appears that once you are familiar with the game mechanics it will be a delightful experience.

Preparing to Triangulate

2008-12-01T06:22:00.000-08:00

When I started this blog I had a list of interesting bits of code to share. I've gotten through most of them but have held back polygon triangulation until now. It's my personal symbol of jumping the shark; once I've presented polygon triangulation I've got nothing of importance left to say. It's time to get it out of the way, though, so over the long weekend I found the code and have been dusting it off as well as rereading the sources I used when I wrote it.

The polygon triangulation problem is as follows. We have a polygon outline, which may be concave and may include holes or interior lines. It may also consist of several disjoint polygons. It does not have intersecting lines. For each edge in the outline we know whether each side is inside or outside the polygon. In addition we may have individual vertices inside the polygon which we wish to be incorporated into the triangulation.

The goal is to produce a good triangulation of the polygonal interior without introducing any new vertices. Something like this:

Polygon triangulation turns out to be useful in a lot of different situations once you've got good robust code for doing it. For instance, in last week's post on river generation I used a disc because it's easy to generate uniform random points inside the disc. It would be nice to be able to have a more interesting coastline, though. With triangulation, I can take the coast outline, turn it into a triangle mesh, and then generate a uniform random point by picking a triangle at random (weighted by area) and then a random point within that triangle.

Here are the primary sources I used in writing my triangulator:

Hopefully I'll have finished the code cleanup next week and can get started on the presentation of the triangulation algorithm.

RRT With Obstacles

2008-11-24T13:45:00.000-08:00

Last week I tried making a rapidly-exploring random tree, or RRT. Instead of starting from a single point as is typical in motion planning, I started from an entire coastline. This produced something vaguely resembling a drainage network of streams and rivers.

Because the tree grows toward each random point from the closest river or shore, it's extremely unlikely that you'd ever replicate South America, with most of the water draining to one side. This can be remedied by adding obstacles (click to enlarge):

Obstacles are defined as line segments which block line of sight between each randomly generated point and the tree. They manually specify some of the ridges on the terrain. Note that rivers will tend to cut quite close to the ends of the obstacles, so the obstacles don't represent just the highest parts of the ridges.

With my brute-force algorithm (coded in a couple of hours) the addition of obstacles slowed it down by a large amount that scales directly with the number of obstacle line segments. As the shape of the obstacles gets more mazelike, the algorithm will require drastically more iterations to fill in the tree, too, since it won't get line of sight to the inner portions for quite some time.

I also did some experiments with RRTs on a grid, where tree edges are all oriented horizontally or vertically. It turns out to bear a strong resemblance to maze-generation algorithms in that context.

Rapidly-Exploring Random Trees

2008-11-19T22:19:00.000-08:00

Time to play a bit. I just learned about rapidly-exploring random trees while reading about motion planning. They look kind of like drainage networks so I had to try them out. I created a disc (a perfectly round island, if you will) and then generated a tree in the interior. Here are a couple of example results (click to enlarge):

The gist of the algorithm is that you generate a sequence of random points distributed uniformly over the interior. For each point, find the closest point on the tree and create a new branch from there, headed toward the random query point. You don't go all the way to the query point, though; just a small step. The net result of this is that the tree tends to head toward open areas.

I've shaded the tree edges as a function of how many other edges empty into them, so you can see the big rivers are darker than their tributaries.

Eye Contact

2008-11-10T06:00:00.000-08:00

The November 10 issue of the New Yorker has an article about Kent Kiehl, a scientist who uses functional MRI to study the brains of psychopaths. He's got a trailer MRI machine set up at a New Mexico prison and has scanned the brains of most of its inmates. There are debates about the fruitfulness of this approach, but I am glad the problem is being studied by actually looking at real psychopaths. Dr. Kiehl says that whenever he goes to conferences the first thing his colleagues ask is “What are they like?” which seems a shame.

The assumption underlying this research is that there are physical brain differences in psychopaths, a tangible perversity. I was struck by a comment from Robert Hare, Dr. Kiehl's thesis professor, regarding psychopaths he's interviewed:

“It's their eyes that are the most remarkable feature,” he said. “How they drill into you.”

I wonder if the intense eye contact is an emotional version of lip-reading? Lacking emotional empathy or something like that, the psychopath must closely examine his conversation partner's face for clues as to what they are feeling, much like a poker player searching for tells. Perhaps the superficial charm that many psychopaths exhibit is a result of the heightened attention they are forced to devote to interpersonal interaction.

On a completely unrelated note, my latest bad movie premise: an Indian casino has been inadvertently constructed on the site of an ancient Indian burial ground.

Seen on the marquee of an indoor shooting range in Kent: “Come on in. You know you want to!”

Multiple predefined levels

2008-11-03T07:56:00.000-08:00

I'm averaging about one hour a week of work on my little game project. This week, I added support for multiple predefined maps. I'm thinking it is time to create a new test map that can help me answer questions about size: whether the game will primarily center around guarded compounds or if there are interesting things that would include surrounding city as well.

The prospect of creating a larger map using a text editor is daunting so I'm considering whether it might make sense to have a simple in-game editor. That is a pretty big change to how things work, though.

Other things I've done this week:

I bought Gothic from Good Old Games and have played it a little bit. I had played its sequel Gothic 2 several times, including with its Night of the Raven expansion and I have always wanted to try the first game in the series. It's been an interesting experience because Gothic 2 included Gothic's map as a subset of its world (albeit with some major changes due to war) so I am finding that I already roughly know my way around.

The Good Old Games folks are doing a great thing by fixing up old games so they'll run on modern computers and selling them without DRM. I had a terrible time trying to get my original Gothic 2 discs to run on my recent computer due to the execrable (StarForce or SecuROM, I forget which) DRM they employed. After getting the runaround from Gothic's publisher and some ineffectual assistance from the DRM company I ended up just buying the rerelease of the game, which (as is common) omitted the DRM. I suppose I'm sending the wrong message to the publisher by re-buying the game. (I tried looking for no-CD cracks first, believe me.) If I could personally deliver a good stiff whack with a stick I would.

I picked up John Christopher's Tripod series of young-adult sci-fi books at the library and have started reading those. They got made into a BBC show which I haven't seen. The setting is Europe a few hundred years after Earth has been enslaved by alien overlords, who use mild neurological pacification to maintain the remaining humans in a feudal state. Humans are fitted with “caps” at puberty; most become contributing members of society. In a small percentage of people the procedure fails, producing mentally ill vagrants. It sounds darker in my telling than it seems to me as I read it.

I played a bit more World of Goo but am stuck on a level in the Fall world now. This game is charming but it's not really my type, I think. Each level seems to consist mainly of finding the one trick that is necessary to complete the level, so it is more of a “get into the designer's head” than an avenue for creativity. My two-year-old likes watching me play, which makes my wife uneasy (there is a macabre undercurrent in the game which mostly goes over toddlers' heads).

Finally, I have been reading up on motion planning. I found a good survey paper here and an excellent textbook here.

Guard Turfs

2008-10-27T07:07:00.000-07:00

I've hacked together the beginnings of guard turf. The idea of turf is to have some areas of the map in which the player can move unmolested so long as he doesn't do anything suspicious. Here's a quick visualization of the turfs (click to enlarge):

Different guards have different turfs: the bank guards care about the cyan building in the upper right, for instance. This is likely overkill; I will probably be able to cut it down to a guarded/unguarded designation, or break it down by a handful of factions.

As an initial test I just made it so that guards can't see you if they are patrolling and you're not in their turf. This is not a terribly satisfactory solution, though.

I also did a quick experiment in loiter detection. I thought it might be interesting if the street guards would harass you if they thought you were hanging around somewhere you ought to be moving along. When I mentioned this to my wife she laughed and said that the Supreme Court has had its hands full slapping down anti-loitering legislation. Loiter detection in real life is tricky at best, often amounting to an excuse for police to arrest black men driving with white women and that sort of thing. Apparently Mayor Daley of Chicago has tried several times to pass laws prohibiting gang members from loitering on the streets.

Fortunately I don't care if my guards are just or not, so long as they act believably. I have tried summing the player's movements over a window of a few turns and if the resulting vector falls below a threshold he's considered to be loitering. I think this might work out OK.

I'm still pondering whether the addition of turfs is a good design decision. One goal is to add relatively safe areas from which to reconnoiter the guarded areas, looking for good ways in. Another goal is to have accessible public areas. I plan to do some experiments with overheard speech soon, and would like to have safe areas in which to listen. Also I'd like to have non-guard people walking the streets. These goals could also be met to some extent by providing appropriate cover or darkness within guarded territory, but I think the turfs will provide an additional layer of control and believability.

Bump To Use

2008-10-20T08:00:00.000-07:00

Continuing last week's thought, I tried out bump-to-use and really like it.

Formerly when you would attempt to move into a usable object (a door, lamp, or switch, say), you'd get a message saying something like “Press Ctrl-left to open the door.” Thus, you'd learn what something was by bumping it, then use a Ctrl-dir key chord to actually use it.

Following a tester suggestion, I tried switching it so that you don't have to press Ctrl-dir to use most things. Instead you just bump them directly and they get used.

This makes the game feel a lot more fluid, which is good. Most usable objects are fairly self-explanatory, and the ones that aren't were not getting well explained under the old system, anyway. The big puzzle for me is how to allow players to shut doors. At the moment this is accomplished by aiming a Ctrl-dir combo at an open door while standing next to it.

At the moment I have status-bar messages that indicate what happened when you use something. This is all right but I think I can pare it down to be even less obtrusive. I'm going to try allocating a field on the status bar for indicating the “current thing.” Normally this will be the terrain underneath the player, but when you use something or bump something it will describe that thing instead, so after opening a door it would say door on the status bar.

I also spent several hours writing some dialog for the captain of the protagonist's ship, which in the test level serves as home base. The ship captain is my first attempt at a friendly character. By having him guard his ship I hoped to introduce the player to the mechanics of guards in a safe environment. He says most of the same things as regular guards, until he recognizes his passenger. “Using” him triggers a series of lines. (Our hero is currently the classic silent player-character whose reticence provokes monologues from everyone he meets.)

I've been mulling over whether the game design has room for sidekicks; the ship captain is kind of a prototype. They have the potential to add a lot more interest to the story since they'd each have their own agendas. However, it's important that they not take away any of the fun of the game. None of them should steal any loot that you can, for instance.

Miscellaneous interface tests

2008-10-13T06:36:00.000-07:00

Another update for my turn-based, ASCII rendition of Thief.

I've decided to shelve random level construction for a bit and return to AI and gameplay development, where things were going well. To warm up I tried a couple of things I've been intending to for a long time. Neither worked out, but I'm glad to have seen them on-screen.

Status bar terrain description

At the moment the game requires a Ctrl-plus-direction key chord to use objects in the environment. If the player bumps into one of these objects using normal movement, the game gives them a prompt along the lines of “Press Ctrl-Up to open the door.”

This works pretty well for unobtrusively teaching the player what all the usable things are. Unfortunately it doesn't provide any way to teach the player about the terrain types under their feet.

As an experiment I added a phrase to the status bar that described the currently-occupied square. Something like “On a creaky floorboard&rdquo or “Under a table.” It feels a bit too overbearing to me, though, so I'm trying to think of alternatives.

Prohibit movement while speech is on-screen

The other problem I tried to solve is that the player can be holding down a movement key and miss the speech balloons flashing by when other characters talk. I did a quick experiment to require the player to press Space to clear the speech balloons before moving. That turns out to be incredibly onerous. If you aren't interested in what people are saying you should be able to just go about your business.

I think the correct solution for missed messages will be undo/redo. This will allow players to back up time a few moves to see dialog they missed. I've started looking at applications' undo/redo interfaces.

The Microsoft apps all seem to use Ctrl-Z and Ctrl-Y for undo and redo. I'm not sure how Ctrl-Y got chosen; it is not reachable with the same hand that's doing the undo operations. Perhaps undo predated redo by a few years and all the nearby keys were already taken by that time.

Maya (a 3D modeling package I use at work) uses Ctrl-Z and Shift-Z for undo/redo. This allow for easy motion in both directions. I think I have also used an application that paired Ctrl-Z with Ctrl-Shift-Z.

In addition to undo/redo I think I'm going to want a hotkey for jumping straight to the end of the timeline. I could envision Ctrl-Shift-Y under the Microsoft scheme, or perhaps Ctrl-Shift-Z under the Maya scheme.

Another key pair might be Space/Backspace, since they are natural antitheses. Space already does duty for clearing status-bar messages and speech balloons, though (as in most other Roguelikes), so that might not work. Backspace/Enter could work, too, but both of these ideas are pretty nonstandard.

Other Ideas

One of my testing complaints was that it was a bit cumbersome to have to use Ctrl-dir to open doors. I've been thinking about ways I could turn using into normal movement. For the most part it would just work. The interface would be slightly more risky for a couple of reasons: the player has to try an unfamiliar object to see what it does, rather than getting a bump message; and cruising along by holding down a key could result in using something when the player collided with it.

I'm not too worried about the learning aspect; I can put up a message on the status bar following the use saying what the player just did. A certain amount of experimentation is fun.

The accidental uses due to holding down keys could be reduced by not allowing a held key to use; you'd have to let up on the key and press it again.

The other thing I haven't figured out with a non-Ctrl-based use is how to close open doors. Open doors currently have no physical presence so they can't be bumped. In that way they are unique so they have always troubled me.

Open doors could be made into a physical presence. They would sit off to one side of the open doorway; stepping on one would close it. I think I'll try this out to see how it feels.

Nothing done

2008-10-06T07:56:00.000-07:00

I was in Portland/Vancouver all weekend (plus Friday) at a wedding so I've gotten very little done. More later, hopefully.

The wedding was at Marshall House, named after George Marshall (he of the Plan). I think Queen Anne Victorian is my style.

Had some superb biscuits and gravy at Bread and Ink Cafe in Portland's Hawthorne district. I've eaten there several times over the past decade and it's always been good. They've got some sort of walk-up waffle window now which we didn't get a chance to try.

Review: Gravitron 2

2008-09-29T06:15:00.000-07:00

Gravitron 2 is a retro-style arcade shooter in the vein of Gravitar and Thrust. You fly a rocket to a series of tiny planet surfaces, where you must destroy one or more reactors and then make your escape before the entire planet blows up. In addition to flying and shooting, the ship is capable of landing on any flat surface, which is useful for rescuing engineers. Each rescued engineer repairs a bit of hull damage as well as adding a bonus to your score for the level.

The ship controls are a slight update to the Lunar Lander family. The mouse's X axis directly orients the ship, and there is a button each for thrusting, firing, and shields. Thrusting and shields expend fuel, which can be replenished by landing or hovering near fuel depots in the levels.

The game has a nice variety of enemies. Levels often contain moving parts. There are occasionally gates with switches, and destructible trees. Each level has a checkpoint; when you first touch the checkpoint, it snapshots the enemies alive at that time. When you die the game restarts you at the checkpoint with the snapshotted enemies. Thus there is an incentive to try and clear as big a swath of the level as possible before touching the checkpoint, which is risky.

I have not finished the game; I think I'm about twenty levels in. I don't think the difficulty curve is as smooth as it ought to be (I'm reviewing version 1.5). Gravitron 2 is brutally hard in places; I've played some levels dozens of times to get through. I have a dormant game project that uses almost this exact interface, so I was already quite good at flying the rocket, and it is still really hard for me. In general the game does a good job of encouraging “Just one more try” gameplay, though. My two-year-old daughter likes watching the game; when I die she tells me “We have to try again!”

I was just over at the Chipmunk physics library page and noticed the game author's handle in the forums, so I wouldn't be surprised if Gravitron 2 makes use of the Chipmunk library for its physics. In general the game's physics is impressive, but there does seem to be some inconsistency in how much damage collisions with the environment do. I also wish the rocket didn't bounce quite so much off of walls.

There's a free demo available with the first five levels. If you like it, the full game only costs $5 (at this writing) so it's not a difficult purchase to justify. In terms of hours of gameplay per dollar this is a great value.

Ron “X-Out” Bunce has since updated his game to version 1.7, fixing several minor interface quirks and an instant-death physics bug. Give it a try!

Villa Creation (first steps)

2008-09-22T06:17:00.000-07:00

Andrea Palladio published his Four Books of Architecture in 1570. He designed villas for wealthy people who lived in and around Venice.

Palladio was one of the earliest Neoclassicists. You don't have to read him very far to find out that he was heavily influenced by Roman architecture, in particular by the only surviving book by a Roman architect, Vitruvius' Ten Books on Architecture.

Palladio's villas were an attempt to recreate Roman style in the 16th century. His books were eventually translated to English and because of them Neoclassicism swept 18th-century England. Thomas Jefferson was a fan, and used Palladio's blueprints as a starting point for designing his home Monticello.

I had gotten the impression that Palladio's books might have given some rules for laying out his villas, but that turns out not to be the case. He does give a whole bunch of floor-plans in Book Two, though, which are quite instructive.

In 1978 Stiny and Mitchell developed a shape grammar by looking at Palladio's blueprints (“The Palladian Grammar,” Environment and Planning B 5). I have not been able to get a copy of this paper so I don't know whether it's worth anything.

Vitruvius's books are interesting in their own right. For instance, the section about where to locate the temples for the various deities is interesting. Apparently the worship of Vulcan involves lots of fire, so you want his temple well outside the city. The worship of Venus involves rites that prove distracting to upright young men, so Vitruvius recommends putting Venus's temple outside the city as well. Near the harbor, if you've got one.

I have turned from whole-city layout to the layout of individual buildings. It seems wiser to work bottom-up from a single piece of gameplay (the burgling of a building) rather than top-down.

My initial steps for randomly constructing a building are not very impressive. I am using an adaptation of the algorithm I used for laying out alleys. The rooms of the house are laid out on a grid. The walls of the grid are then given random offsets. Finally, the random offsets are made to match in either the horizontal or vertical direction (randomly chosen) at each junction, to ensure that rooms don't overlap or leave gaps. Additionally I impose a line of symmetry on the house. Here's what I've got so far:

To ensure that all rooms are connected by doors, I use a breadth-first search to flood-fill connections from the front door. Then I go through and randomly add other door connections.

The problem with the grid-based approach is that it is hard to have rooms that vary significantly in size. For instance, a lot of urban Roman houses have a central courtyard (to admit light) surrounded by a whole bunch of little rooms.

Still, having something is better than having nothing. I'm going to throw in some loot and guard patrols and see how it plays, and then try to think about how to give the houses more realism and character.