Computer Problems Continued

I've isolated the problem to the hard drive. In the meantime I've been doing some thinking about the overall project I've been working on.

I've been contemplating two large changes to my thief-like/rogue-like. The first is random level generation. Before the computer crash I was working on a prototype for generating a full city. I envision the city as consisting of several large compounds which are the focus for thieving missions, surrounded by houses, shops, and so forth.

The main thing to consider with this is what gameplay purpose all the embedding city will serve. I run the risk of having large useless tracts of homes that just create unwanted travel time; or perhaps a level that will take too long to complete.

One idea I might try out is to have a kind of “inverse collectible”. I've been thinking about making gold into an actual currency rather than a strict collectible. In that case, I need places to spend gold. Taverns are an obvious thing. I was also thinking about having a “Robin Hood” style situation where you can distribute gold to the smaller homes. Perhaps homes would have little shrines into which you could deposit gold.

This opens up a lot of design issues. Can you retrieve the gold later? How does this change the main character's motivations? Do you get any sort of reward for doing this? I'm not convinced it's a good idea yet.

The other major feature I've been considering for the game is sidekicks. This could obviously be another gold sink. It might also help with the “heist” feel as you would need to plan out an operation ahead of time. This amounts to a whole new user interface element in the game, though; plus I would need to create the AI for the characters. So I'm trying to decide whether it would be an effective part of the game. One of my worries is that the AI characters would do interesting things that should properly be done by the player for maximum entertainment. Ideally they would either do things that the player can't do himself, or would allow tactics that aren't possible solo, or would make boring things less boring.

The Fire Emblem series of games (or perhaps Baldur's Gate) are a pretty good model of how I would envision sidekick characters interacting with each other. Basically there are little plot threads involving pairs (or in rare cases large configurations) of characters; if you have the proper character set assembled for a mission, another bit of that plot thread plays out. Sidekicks would also have plot threads that tied each of them to the central villain in some way, to help keep the player's focus on him.

Computer Problems

No post today. My notebook computer is dying. It's a ThinkPad T61 bought last year so I am annoyed. The symptoms so far are that it locks up after waking from sleep. The mouse cursor can be moved but it does not respond to keyboard or mouse buttons.

Fortunately things are backed up but it will take some time to sort through the problem.

You might think that programmers love computers more than the average person. Not true at all!

Flood-filled elevation

I sat down to eat in the Seattle airport last Thursday with a guy who unsurprisingly turned out to be a programmer. We talked a bit about Gaussian blurring; he was saying that for filter sizes much above 5x5 it was quicker to do the Fast Fourier Transform and do the blurring in frequency space. I spent some time trying to figure out how I might be able to do that. The pegging of the river to zero complicates things. Since I'm doing a bunch of steps it ought to be possible to replace them all with a single step with a really big kernel, but since I'm re-pegging the river in between each step I am not sure that would translate to the same thing at all. Maybe I could do half as many steps with a slightly larger kernel (in frequency space) instead.

On the plane back from Baltimore yesterday I tried a quick experiment. Because the Gaussian blurring is so slow I thought that if I could come up with a better first approximation I could get away with doing less of it. I tried flood-filling initial elevation data, working outward from the river. Each node is slightly higher than the highest of its neighbors that have been defined so far.

Unfortunately the quality of this is pretty bad:



Here are some resulting roads:



Overall I'm not sure that having roads primarily follow or cross the gradient is what I want. I may dive in and try to understand the L-system-based approach that Mueller's original paper describes. The writing is impenetrably bad, as is typical for academic papers.

I'm starting to feel like the terrain generation is eating up too much time. I'll probably just settle on something for now so I can move on to other aspects. I need to figure out if and how having a large city will be fun, and I need to work on plugging buildings into lots, generating patrol routes, street lights, and so forth.

Gradient Estimation

This week I did a little bit of work to improve gradient estimation. I start with the binary river/land map:



...and from it infer slope information for the land:



(Click images for larger versions.) This slope information can then be used to guide roads beside or across the river, a la Interactive Procedural Street Modeling.

I do this by setting the land squares to a high elevation and the river squares to zero, and then blurring the landscape while keeping the river squares clamped at zero. I am also experimenting with adding in a small elevation boost to the land before each blur iteration. This helps keep the landscape from flattening out, especially inside tight loops of the river:



Note that this slope information isn't necessarily indicative of how steep the actual landscape would be. I simply need good slope information to guide road placement.

With gradient information in hand it's possible to trace out roads that follow the terrain (click for larger version):



The elevation boost on each blur step is a bad idea, I think. It tends to cause hills to crease more, which makes level roads turn sharply when they go around the crease. Hill-climbing roads also turn sharply and go up the crest when you have sharp hills. I think I prefer rounded hills so that as roads are set further back from the river they follow it less precisely. You can see this at work in the screenshot above.

I am not yet spacing the roads apart intelligently; I just generated a bunch of maps and picked the best-looking example to show above. The SIGGRAPH paper I linked to above has a reference to another paper that describes how to space the roads apart, though, so that should be relatively easy to add.

My plan is to have a few major highways that follow the terrain like this, and then fill in between with grid-aligned roads, since the game is tile-based.

At the moment my blur is extremely expensive. Because of the clamping it's hard to use a very big filter kernel (I'm using 3x3 currently) so it takes many iterations to propagate the blurring over large distances. My filter kernel looks like:

1 2 1
2 4 2
1 2 1

When I'm dealing with Gaussian blurring I wish I'd stayed in grad school; the faculty at UNC worked pretty hard to hammer this stuff in. I feel like I'm twiddling a lot of knobs without wholly grasping how it all fits together.

I think I might be able to make it go much faster and still maintain the clamping behavior. I would run one iteration of smoothing at full resolution, then down-sample by a factor of two in each dimension. For the downsampled image, any pixel that was based in part on a clamped pixel in the source image would be marked as clamped. The process of blurring, downsampling, and clamping would be repeated for several more levels. Then I would go through a reverse process of upsampling with interpolation to arrive at a heavily-blurred version of the source image.

Obviously information is being lost by the downsampling, though, that isn't theoretically being lost by the blurring itself; I would like to understand this process better.