Monday, December 8, 2008

Spirit Engine 2 (demo)

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.

Monday, December 1, 2008

Preparing to Triangulate

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.

Monday, November 24, 2008

RRT With Obstacles

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.

Wednesday, November 19, 2008

Rapidly-Exploring Random Trees

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.

Monday, November 10, 2008

Eye Contact

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!”

Monday, November 3, 2008

Multiple predefined levels

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.

Monday, October 27, 2008

Guard Turfs

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.

Monday, October 20, 2008

Bump To Use

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.

Monday, October 13, 2008

Miscellaneous interface tests

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.

Monday, October 6, 2008

Nothing done

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.

Monday, September 29, 2008

Review: Gravitron 2



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!

Monday, September 22, 2008

Villa Creation (first steps)

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.

Tuesday, September 16, 2008

Science!

I'm having trouble getting back up to speed on my programming project, as no doubt is clear. Today I'm going to stop by the library to pick up Andrea Palladio's 16th century book on architecture. I've heard that it lays out a shape grammar for villas which would be useful in my project. That may be a 20th century paper by Mitchell and somebody else, though; I won't know until I can get my hands on some of it.

In the meantime science marches on:

Epazote: My wife tried making identical batches of pinto beans, one with epazote and one without. I could not really tell a difference, so either we had weak epazote or it doesn't add significantly to the flavor of beans. At least not in an unmistakable way like, say, chorizo.

Head On: A product with one of the most memorable no-budget TV advertising campaigns in recent history. We picked up a small tube the other day when we were at the pharmacy. It turns out to be a homeopathic headache remedy! Who knew? Of course it's got menthol in it: that's how you know it's working. I have an idea for a product of my own: a special lamp with a row of switches for enabling various rays which will cure headaches, insomnia, constipation, etc. It would make use of advanced LED technology and the unseen portions of the electromagnetic spectrum.

Cheesy Chipotle Chicken Chorizo Chili: How does this sound for a Taco Bell special?

Avatar, the last Airbender: I stayed away from this Nickelodeon series for a long time because of the cheesy name and four-elements premise (don't get me started on the four elements!) but enough people sang its praises that I finally borrowed the first season from the DVD library at work. It's a great show!

Monday, September 8, 2008

Coming back gradually

I got a new hard drive and have been gradually getting everything reinstalled. I'm taking the opportunity to upgrade in a few places along the way.

The 2008 edition of Visual Studio Express fixes the bugs that annoyed me in the 2005 edition: the inability to double-click on solution files in Vista, the extra security dialog check, and the inability to drag and drop files onto the Visual Studio editor. All of these are the kinds of things you'd think would be impossible to break in a long-running product like this, but they probably re-implement everything periodically just to keep life interesting.

Beyond Compare has a new version 3.0 out; they finally implemented 3-way merge although they charge an extra $20 for it. This diff utility is an integral part of my day job and I can't imagine working without it. There are much more expensive solutions out there (Araxis Merge) but I think Beyond Compare delivers some of the best value.

I'm getting more and more pissed off at Perforce, mostly because I'm the de facto Perforce administrator at work. I am unimpressed (version 2 of my post) with the current programming lineup behind this product. The current GUI client (P4V) is quite noticeably slower than their old Win32 client (P4Win) despite years of development and suffers from incredibly bad user interface design and a never-ending stream of bugs. As an example of the bad user interface, the Sync and Checkout buttons are adjacent on the toolbar. Once or twice every month somebody will select the root of the art tree and accidentally check out everything. This action is very quick and locks everyone else out from checking any of the art files out. Unfortunately reverting the checkout takes hours, unless you use command-line trickery. The old P4Win client, by asking the user “Do you really want to check out 60,000 files?” avoids this sort of problem. I've requested that they put this warning into P4V since it is present in P4Win, and I've reiterated that it's a problem four or five times, and in as many releases of P4V they have not done it. I haven't even mentioned the inexplicable problems with the user interface, like not being able to get the Submit dialog to appear, and I haven't mentioned the Qt debacle, whereby they used a DLL with the same name as a DLL in Maya, and from the same vendor, but with different function sets, thereby rendering either P4V or Maya inoperable depending on which came first in the PATH.

The Perforce server, which was written by the Wise Ones at the Dawn of Time, continues to be a most excellent piece of software. It's a shame that all we can do is gaze back in wonder and mystification at these relics of a bygone era.

I'm considering switching to a different version control for personal use. My criteria are: free, easy to install and administer, fast, and no “turd files” littering my work directories. A good GUI client would be nice too. Wish me luck; I have a feeling such a combination of things does not exist.

I've tried out Google Chrome for a while. It is a decent browser but has a tendency to get very thoughtful (shall we say) when you require it to share those 4GB of RAM with other programs.

Finally, Jungle Disk was the real star of this computer breakdown. I was able to restore my backed-up projects with no trouble. They've continued to improve the interface of the client.




It's past time to return to work on my little game; I've been getting antsy while my computer's been out of commission. Fortunately there have been things like crunch time at work to fill the void. I'm looking forward to getting back to work this week, though.

Monday, August 25, 2008

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.

Monday, August 18, 2008

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!

Monday, August 11, 2008

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.

Monday, August 4, 2008

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.

Monday, July 28, 2008

Kist List

I got very nearly no programming done this week. And so I present to you a list of things I have seen that are “kist”:



Seen any others?

Monday, July 21, 2008

Random offsets to streets, and not always connecting a built square to a neighbor:



The random offsets have to be unified to ensure that the streets match up properly. In my sleep-deprived state it took me a while to figure out how to do this.

I'm still not sure if this is the right approach to constructing streets and placing buildings. Its advantages are that it is very fast and ensures things are always tightly packed with no wasted space. A major disadvantage is that the buildings are clearly laid out on a grid. You can't have larger buildings in one area and smaller buildings in another unless you do so in increments of the grid size.

At the moment I'm mulling over some crystallization-type ideas, or simulating building construction over time. All of these things are likely to be more expensive to compute so they'd need to be worth it.

Monday, July 14, 2008

City Generation Progress

Here's a visual progress report on random city construction (click for larger versions):




I'm still not happy with it but it's coming. I need major roads which are very wide and connect gates to major compounds (palace, temple, market), minor roads which run fairly straight, and then alleyways which are narrow and twisty. I'd like for major and minor roads not to have any dead ends. I'd also like a little variation in building footprint thickness. I'll need landmarks as well, like open squares where major roads meet.

Figuring out how to marry my rectilinear buildings to the curvy river is another problem. I may make the river chunkier, or I may put in terrain features like park that can assume any shape in the triangular blank spaces.

The current algorithm involves figuring out which squares on a larger grid will contain buildings; then connecting each building square to one of its neighbors.

Monday, July 7, 2008

A River Runs Through It

This week I did a bit more work on random city map generation.

I'd like this kind of city to be in a floodplain with a meandering river running through it, perhaps joining with another river. Accordingly I decided to start with the river and build up from there.

Random river construction is not something that is well-documented on the web. Luckily I know Dr. J. Wesley Lauer at Seattle University, who specializes in the interaction between rivers and their floodplains. He's given me a couple of leads to follow.

The simplest model of a meandering river is a sine-generated curve, also known as a meander curve. The river direction oscillates via a sine wave as a function of arc length. Scaling the direction angle results in a river that meanders more or less. Here are some examples (maximum angles of 1.0, 1.5, and 2.0 respectively):







Here's an example with a varying direction angle scale:



It's really easy to generate these. Here's some Python code I used to generate the SVG diagrams above:

from math import sin, cos

viewSizeX = 300
viewSizeY = 300

x = 0
y = 20
angle = 0

angle_inc = 0.1
dir_scale = 1.0
step_size = 4.0

points = [(x, y)]

while x < viewSizeX:
dir_angle = dir_scale * sin(angle)
dir_x = step_size * cos(dir_angle)
dir_y = step_size * sin(dir_angle)
angle += angle_inc
x += dir_x
y += dir_y
points.append((x, y))

print '<?xml version="1.0" encoding="UTF-8" ?>'
print '<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="%d" height="%d">' % (viewSizeX, viewSizeY)
print ' <g fill="none" stroke="blue" stroke-width="2">'
print ' <polyline points="%s"/>' % (' '.join(map(lambda p: '%g,%g' % (p[0], p[1]), points)))
print ' </g>'
print '</svg>'


The next step is to replace my rather-lame first attempt at river shaping with something based on sine-generated curves. Here's what I'd be replacing:



The rivers in this version are based on some quadratic curves. The buildings are just splattered down in such a way as to not overlap; that'll be replaced with an algorithm that generates streets and city blocks and then subdivides the blocks into buildings. There's a bunch of little green lines which represent a gradient estimate, which I may use to guide some of the roads.

Monday, June 30, 2008

Random map generation

This week I've been working on random map generation for my Thief/Rogue hybrid. This is what new Roguelike developers generally start on, and they can easily waste years with it. It's a hard problem. I put it off on my project because I knew what a morass it could be, and because I didn't feel like I had a handle on what the gameplay would need from the landscape. Now that I have a pretty good idea of what the gameplay is, I've decided it's time to tackle landscape randomization.

By the way, here are some Roguelike development sites I keep an eye on:



What I'd like is something like the streets of Toledo (España, not Ohio):



(Image by ctankcycles.)

I don't have any great images handy, but Google Maps does a pretty good job of showing what I'm after:



Of course this has to be rectangularized to some extent.

I tried out a Voronoi diagram on a grid. Very unsatisfactory:



There's a paper in this year's SIGGRAPH that has some ideas I might try.

Wednesday, June 25, 2008

Space Steering Revisited

I had to make a detour from my current project to finish up some Newtonian spaceflight steering stuff I worked on a year ago (detailed in parts one, two, and three).



You could think of it as the beginnings of an AI for playing the old game Space Wars, or its descendants the two-player Star Control combat modes.

The rocket is flying to a target position in the lower left; in the background I'm plotting a graph of the objective function it's trying to minimize in order to pick the correct direction to point its thruster. At the moment it's finding the minimum pretty well (its result is the yellow cross). There are situations where it doesn't do so hot, though. I'm doing an extremely simple, brute-force approach to searching for it, and I'm sure I can do much better. I just need to learn something about minimization of nonlinear functions, especially ones with hard-to-compute derivatives.

Monday, June 16, 2008

Review: Treasures of a Slaver's Kingdom

Treasures of a Slaver's Kingdom is a text adventure of sorts by S. John Ross. It's likely to offend the sensibilities of Real Interactive Fiction lovers, as it pares down input to a handful of commands. I love this because I hate “guess the verb” gameplay. Treasures also features simple stats-'n'-dice-based combat, which puts some people off. On the positive side, it's a giddy pulp pastiche of Conan, Star Wars, and more. Atomic dinosaur? Sure! Give him a light saber! The writing is frequently hilarious. The game is solidly designed: the environment is fairly small, the inventory is kept to a manageable size at all times, and you can't really get stuck.

I discovered the game through Emily Short's excellent (as always) review over at Play This Thing. I really can't add much to her review, so head over there to read it.

Treasures does a good job of making memorable non-player characters. You actually feel like you've got a relationship with them. I think the limited input vocabulary helps here as it keeps you from getting frustrated trying to interact with them.

The full game costs $13, which I think might be slightly much for the amount of gameplay. I got through the game in under eight hours, although I made fairly extensive use of the crypto-clues offered in the instruction manual, to the point of writing a Python script to decode them for me. However, I spent the entire time playing the game with a big grin plastered on my face and laughed out loud on several occasions.

There's a free demo that lets you play the first fifth or so of the game. Try it out and see if it agrees with you. You will also need a Z-machine interpreter to run the game; Gargoyle is a very nice-looking one.

Sunday, June 15, 2008

Panty Raid

Two weeks ago last Friday, over $10,000 worth of panties (about 650 pair) were stolen during business hours at my local Victoria's Secret. More info There is no surveillance footage of the incident and no suspects.

Monday, June 9, 2008

Pathfinding notes and code

No progress this week, other than writing down a list of features, both necessary and desirable, for finishing my Thief-like Rogue-like.

When I was working on the pathfinding code I did some Googling for pathfinding tutorials, example code, etc. What I found was not entirely satisfactory, so I am adding some notes of my own here. This is talking specifically about the A* Search algorithm.

The basic idea is to search for a minimum-cost path through a graph of states. In my game a state is a position in the world, and the graph edges are the legal moves from one position to its adjacent positions. There can be up to eight of these in my game: north, south, east, west, and diagonals. The cost is based primarily on distance, but I add additional penalties to discourage movement through windows, over tables, through bushes, and things like that. I originally based cost on the number of moves required, ran into an aesthetic problem. On a square grid, if diagonal moves take the same amount of time as horizontal moves (which they do, in my game), there is no difference between these two moves:



If an AI needs to walk in a straight horizontal or vertical line it looks very strange if they veer out of their way, so I made the movement cost approximate true distance. It doesn't need to be exact; just enough so that a northeast-then-southeast move is more expensive than an east-east move, and a southeast move is cheaper than an east-then-south or south-then-east move. I assigned a cost of 2 to horizontal and vertical movements and a cost of 3 to diagonal movements, which took care of the problem.

The gist of A* is that we examine states in the order of the estimated total cost of a path through them from the start to the goal. In my code the states are called nodes, since they are nodes in a graph being searched. During a search I maintain a set (using an STL set) of nodes that have been seen so far. Here's the data structure:

struct PATH_NODE
{
PATH_NODE() {}
PATH_NODE(POINT2 pos_):
pos(pos_),
prev(NULL),
cost_from_start(0),
est_cost_to_goal(0),
num_paths(1),
closed(false)
{}

bool operator < (const PATH_NODE & other) const
{
return pos < other.pos;
}

POINT2 pos;

// Previous state on path through this node:

PATH_NODE * prev;

// Minimum cost found so far to reach this node from the start:

int cost_from_start;

// Estimated cost to reach goal from this node:

int est_cost_to_goal;

// How many paths with the same cost_from_start have been found so far?

int num_paths;

// Has the best path to this node been found already?

bool closed;
};


The node has a less-than operator for ordering nodes; this allows me to store them easily in an STL set. It's just ordering them by position, which will be unique.

The prev pointers allow the path to be reconstructed: once the search reaches the goal we just follow these pointers back to the start. std::set's implementation keeps entries at the same place in memory for their entire lifetimes so it's safe to keep pointers to them, as I'm doing here. cost_from_start may be reduced over time; it's possible to find one path to a node and later find a better path to that node. est_cost_to_goal never changes, though; it's based solely on the node's position. It's stored here just to save time recomputing it. num_paths is used to be able to choose uniformly randomly from paths with equal cost. Finally, closed indicates when we've found the best path to the node, after which we do not need to do anything further with it.

The other data structure used during the search is a priority queue, which keeps track of nodes to be examined in order of the total estimated cost to reach the goal through each one. I use the STL priority_queue for this, with the following queue entry data structure:

struct PRIORITY_NODE
{
PRIORITY_NODE() {}
PRIORITY_NODE(PATH_NODE * node_, int est_total_cost_):
node(node_),
est_total_cost(est_total_cost_)
{}

bool operator < (const PRIORITY_NODE & p) const
{
// Lower cost values have higher priority in the queue.
return p.est_total_cost < est_total_cost;
}

int est_total_cost;
PATH_NODE * node;
};


Again, I'm storing a pointer to a PATH_NODE inside a std::set.

Here's the pathfinding function:
POINT2 move_toward(POINT2 pos_start, POINT2 pos_goal)
{
if (pos_start == pos_goal)
return POINT2(0, 0);

std::set<PATH_NODE> path_nodes;
std::priority_queue<PRIORITY_NODE> open;

typedef std::pair<std::set<PATH_NODE>::iterator, bool> INSERT_RESULT;

INSERT_RESULT insert_result = path_nodes.insert(PATH_NODE(pos_start));
PATH_NODE * start_node = &*insert_result.first;
start_node->est_cost_to_goal = cost_estimate(pos_start, pos_goal);

open.push(PRIORITY_NODE(start_node, start_node->est_cost_to_goal));

while (!open.empty())
{
PATH_NODE * node = open.top().node;
open.pop();

if (node->closed)
continue;
node->closed = true;

// Have we found a path?

if (node->pos == pos_goal)
{
while (node->prev != start_node)
node = node->prev;

POINT2 pos_new = node->pos;

if (GUARD::at(pos_new) || SHIP_CAPTAIN::at(pos_new))
return POINT2(0, 0);

return pos_new - pos_start;
}

// Generate successor states.

for (int i = 0; i < 8; ++i)
{
POINT2 pos_new = node->pos + dir[i];

int move_cost = guard_move_cost(node->pos, pos_new);
if (move_cost == infinite_cost)
continue;

move_cost += dir_cost[i];

int cost_from_start = node->cost_from_start + move_cost;

INSERT_RESULT insert_result = path_nodes.insert(PATH_NODE(pos_new));
PATH_NODE * node_next = &*insert_result.first;
if (insert_result.second)
{
// Node was just inserted

node_next->prev = node;
node_next->cost_from_start = cost_from_start;
node_next->est_cost_to_goal = cost_estimate(node_next->pos, pos_goal);

open.push(PRIORITY_NODE(node_next,
node_next->cost_from_start + node_next->est_cost_to_goal));
}
else if (!node_next->closed)
{
// Node already exists; do we need to adjust its path?

if (cost_from_start < node->cost_from_start)
{
// Better path to node_next found.

node_next->prev = node;
node_next->cost_from_start = cost_from_start;
node_next->num_paths = 1;

open.push(PRIORITY_NODE(node_next,
node_next->cost_from_start + node_next->est_cost_to_goal));
}
else if (cost_from_start == node->cost_from_start)
{
// Same-length path; randomly replace existing path with new one

++node_next->num_paths;
if (random(node_next->num_paths) == 0)
{
node_next->prev = node;
}
}
}
}
}

// No path to destination found.

return POINT2(0, 0);
}


If I find a better path to a node, I don't bother trying to adjust the priority on the existing priority queue entry for that node; I just push another entry into the queue with the improved priority. When the function eventually pops the older queue entry off it'll see that the node is already closed and just ignore it.

One thing that wasn't clear to me at first when I was learning the algorithm: the first time you pop off a node from the priority queue, you have found the best path to it. This is why we're able to immediately mark the node as closed in the code.

Eventually I may refactor this code to separate enumeration of successor states from the search. At the moment you can see a loop over the eight possible neighbor states.

My actual pathfinding function has a coda at the end. Instead of giving up when no path can be found, it searches through the node set for the closest node to the goal. In the case where multiple nodes are found with the same estimated cost to the goal, the one that is cheapest to reach from the start is chosen. Then I return the first step along that path.

As you can see, I'm currently regenerating paths from scratch every turn. So far it hasn't been a problem but if it does become a noticeable CPU drain it would be possible to cache paths in some fashion.

When a path is found there is some ugly code in there checking to see if a guard or ship captain is at the spot where we want to move. I'm treating them as passable during the search, and just not moving if one happens to be in the way.

Monday, June 2, 2008

Relative Priority Queue

Games that choose lines of speech “randomly” from a set usually don't want true randomness. They want to be sure that the same line isn't chosen twice in a row, or perhaps for an even longer period.

For my game I opted for the simplest solution first. I just keep an iterator into each line set and run through the lines in order, wrapping back to the start after I've used all of them. I doubt anyone will notice that the lines are used in the same order, since I have lots of different line sets that come into play during gameplay.

I couldn't help thinking about more complicated solutions to the problem, though. What if you have some lines that are so memorable you don't want them to reappear for a long time after they've been used? Other, simpler lines could be reused more frequently without sounding dumb.

One way to do this would be to assign to each line a “timeout”; a duration before it can be used again. The line with the lowest timeout is the next to be used. After using it you'd reset its timeout value and decrement all the rest.

This is sort of like a regular priority queue, except that you really don't want to have to decrement priorities on all the entries every time you extract something.

I was thinking that you could implement a relative priority queue as a binary heap where each element stores its priority relative to its parent rather than a global priority value. For instance, here's a standard priority queue containing absolute priority values:



The relative representation of the same priorities would be:



The usual binary-heap-based queue algorithms should work with only small modifications to take into account the relative nature of the priority values. Here's extraction of the lowest-value element. The end element is swapped into the first position:



Then additional swaps are made to ensure that parent nodes have lower values than any of their children:



Relative priority queues could also be useful if you've got timer events in a game that are set to go off at times in the future. Some (shipped!) games I've worked on used absolute times for everything; they run into problems if you let them run continuously for too long. Dealing in relative times lets your game run in a kiosk at Best Buy for days on end.

Monday, May 26, 2008

Wonder Pets: Opera for two-year-olds

Wonder Pets

Speech bubbles 3

Another update on my turn-based, text-based rendition of stealth gameplay.

I decided it was finally time to improve the layout of speech bubbles. Here's how things looked:



The text was placed centered above the speaker with no regard to whether it went off-screen, covered other text, or covered one of the enemy guards.

The first thing I did was to constrain the speech to be on-screen. Then I generated all of the possible positions adjacent to the speaker and scored each one based on what it covered. The score penalizes speech bubbles a little bit for covering portions of the map that are either currently visible or previously seen, and it penalizes the bubbles a lot for covering the player or non-player characters. Picking the best-scoring position for each speech bubble produced good results except that the scores didn't take into account overlaps between speech bubbles. The next step was to implement some optimization. Overlaps are penalized and it looks for permutations to the current state that will reduce the overall score. The results look like this:



(I'm also experimenting with different speech bubble styles. Ultimately I will need to add stems back in to indicate where the speech is coming from.)

The optimization turned out to be really slow. It's also kind of fiddly because you have to come up with a numeric score for each kind of thing you're trying to avoid. I'm trying to think of alternatives. One idea is to treat it as a rigid-body physics problem. The speech bubbles would be constrained to be next to their sources, and would push each other away. I don't know if this would give good results or not, but since it's something I'm familiar with I will probably try it out.

Monday, May 19, 2008

Pathfinding improvements

Another weekly update for my riff on Thief in the style of Rogue.

I've been mulling over a big change. Guards need to have local knowledge of the current state of the world but use their memory of the default state of the world elsewhere. At the moment they use global knowledge of the current world state. If they are traveling somewhere and you open up a shortcut to their destination, they will veer toward it even if you opened it up out of their sight. For instance:



In this picture the guards are attempting to get to the open door next to the ghost (ignore him; he doesn't do anything yet). The window just southeast of the thief is locked from the inside so they have to take a very long route. If the thief opens the window, however, they will currently instantly change their path to this:



They shouldn't do this because they have no way of knowing that the window was opened.

I think what I will do is prepare a “field of view” for each guard on each turn. This would be an overlay created by using a version of the field of view algorithm that the thief and lamps use for projecting sight and light, respectively. When checking the world state, the guard would check the overlay first, and, if it didn't see the square, go to the world map and get the default state for that square.

This is a fairly big change, though. In the mean time I've tightened up the existing path-finding code and made a couple of improvements.

The main optimization was to reduce the number of searches the code does. The previous code was pointer-free, so there were lots of lookups based on position. Adding a closed flag to the path nodes, rather than having a separate set, was the first step. Using pointers between nodes to represent the path, and using pointers in priority-queue entries for referring to the nodes, was the next step. Finally, I stored the cost estimate for reaching the goal on each node rather than recomputing it when needed.

The enhancements I made are subtle. While messing around with secret doors I noticed that guards would sometimes take the long way to get to the secret door. This happened when I would open the door, they would see that it was open, and then I'd close it again. (Currently they don't care that it has been closed; they travel to it regardless.) The problem was because a closed secret door is currently impassable to them. (This is going to change; I need to overhaul guard movement costs to take into account the direction through doors and whether the guard has a key to that door.) When a guard tries to move to an impassable location the normal pathfinding fails. In that case he picks the closest reachable point to the goal and moves there instead. The problem came when there were multiple reachable points the same distance from the goal. The guard was just picking the first one. Now, ties are broken by considering the cost to reach each point, so the guard won't do anything crazy.

The other enhancement is something I've been meaning to add for a long time but hadn't gotten around to. Guards choose uniformly randomly from all paths that have the same cost. This breaks up their movement so they don't always take the exact same route. Each time an additional alternate path is found there is a (diminishing) chance that the algorithm will switch to that path instead. Each node keeps track of the number of paths found to it so far with the same cost. The chance of picking a new path is 1/n so that every path is equally likely even though we roll the dice every time we add a path.