January 31, 2005

Gobsmacked!

Ian's gobsmacked--gobsmacked, I say!--to find that until last week I'd never read Dashiell Hammett. This happens every so often with one author or another, and honestly I'm rather flattered. But why should it be so astonishing, given my approach to the classics?

I mean, there's no question that Hammett's a classic American voice. But I've rarely gone in for reading the classics just because they are the classics. When I go looking for something I've not read before, I'm most likely to choose something by an author I already like; I'm next most likely to pick something that's been recommended to me; and if I'm feeling expansive or I haven't found anything in the first two categories I'll just browse and find things I don't know anything about. Case in point--I very much like Jane Austen; I started reading her because Persuasion came up in a discussion of Patrick O'Brian's Aubrey/Maturin novels.

And not being a film geek like Ian (I use the term advisedly) I've not encountered Hammett's tales in the movies (except for The Maltese Falcon).

So what's so surprising?

Posted by Will Duquette at 05:12 PM | Comments(0)

January 30, 2005

Foraging Thither

The Forager has moved his blog; you can find his new posts here.

Posted by Will Duquette at 06:27 PM | Comments(0)

The Thin Man, by Dashiell Hammett

Craig Clarke reviewed this book in Ex Libris Reviews last month, causing me to reflect. I reflected that although I'd heard of Nick and Nora Charles, I'd never read a book or seen a movie in which they appeared. I reflected that although I'd heard of Dashiell Hammett, I'd never read anything by him. And I reflected that I'd been completely unaware that Hammett was responsible for Nick and Nora Charles, having associated him with mean streets and gumshoes and Humphrey Bogart. Clearly this was something to look into, and so I procured a copy of The Thin Man forthwith. And I read it.

And I enjoyed it.

But good grief, fish don't drink as much as these folks. It's like some witty, urbane game of quarters. You get home from the theater: take a drink. Some one comes to your hotel room: Take a drink. Your visitor takes a drink: take a drink. You get up in the morning: take a drink. Someone gets murdered: take a drink. Go out to a speakeasy patronized by underworld types: take a drink for each one. But sip them slowly, because the speakeasy's liquor is lousy. You're feeling a little tight: take a drink. You're not feeling tight enough: take a drink. Make a witty non-answer to an impertinent question: take a drink. Hear yet another all-too-plausible tale from Mimi Jorgenson that you don't believe: take two drinks.

It's all well-written, mind you; and it's fascinating to watch Nick's behavior change as he gets drunk. He doesn't get loud angry drunk; he doesn't slur his words or get sentimental, or any of the other cliched drunken behaviors; but there's a definite sense that the inhibitions are lifting, that he's not watching himself so carefully, that he might be saying a little more, saying it just a little louder, that he might not care quite as much about consequences.

The other characterizations are good, too. I especially enjoyed disliking Mimi Jorgenson, one of the most poisonous, duplicitous female characters I've ever come across. The only character I can compare her too is the lady in the movie The Maltese Falcon. Go figure.

Some time I'm going to have to re-read this to figure out just how Hammett did it.

Posted by Will Duquette at 06:01 PM | Comments(1)

January 29, 2005

Rambling About

I saw the doctor yesterday, and got some antibiotics, and I'm feeling better in that the symptoms are less severe, but I'm also completely wiped out, which I wasn't before today. Who knows what tomorrow will bring.

But there's been some sporadic progress in the world of Ramble. My development version now includes:

  • A simplified version of Angband combat
  • You can now buy a variety of hand and missile weapons, with appropriate ammunition for each.
  • Giant garden slugs
  • Line-of-sight visibility

That last feature came as quite a surprise to me, as I hadn't planned to do it yet; and even more surprising, it's fast enough. I'm rather shocked. Though, I'm not entirely happy with the function I'm using to compute the tiles on a line-of-sight between two other tiles.

Anyway, "I aten't dead", as Granny Weatherwax would say, and I hope to have energy for writing prose Real Soon Now.

Posted by Will Duquette at 06:45 PM | Comments(0)

January 28, 2005

Run Silent, Run Deep

Sorry for the lack of posts; I've been down with a nasty sore throat for a couple of days. Things should pick up soon.
Posted by Will Duquette at 06:36 AM | Comments(0)

January 25, 2005

The Ramble Chronicles: Combat 1

Driving home today, I made a number of decisions about the future evolution of Ramble. So far, I've been patterning it after games where it's easy to die...and when you die you have to start over from the beginning. That's OK for me, after all; I have a longer attention span, and I know how the game works. But Dave, I think, finds it annoying. So I'm going to change things so that if you die in the dungeon you wake up back in town, ready to go--but having been penalized seriously enough to give death some sting.

Second, I think I'm going to re-randomize most or all dungeon levels each time you visit them. That makes the game harder, but also more interesting and less predictable; it also improves the game economics in ways I'll go into another time.

But the big change is that I'm going to abandon the Advanced Dungeons & Dragons combat model for that used by Angband. The AD&D rules are copyrighted, of course, and while I don't think Wizards of the Coast are going to come after me if I use their combat model I'm still uncomfortable about releasing a game on the internet that uses copyrighted rules. But that's by the way.

The main reason is one of complexity. To be blunt, the AD&D rules are too simple, largely because of the dungeon economics I keep talking about and not defining. As an example, let's look at the "to hit" computations.

Making a hand-to-hand attack involves two steps. First it's determined whether you hit your opponent; then, if you hit it's determined how much damage you did. In AD&D (2nd Ed.), the "to hit" decision is determined by a number of factors:

  • Your opponent's Armor Class, or AC. This is a number from 10 (no armor) to -10 (astoundingly good armor). The better the armor, the harder they are to hit.
  • Your own THAC0 ("To Hit Armor Class 0") score. For a warrior (the only kind of character supported by Ramble at the moment), THAC0 is (21 - Level), with a minimum of 1. Thus, a first-level (i.e., novice) warrior will have a THAC0 of 20.
  • One roll of a 20-sided dice, marked 1 to 20.
    • If you roll 1, you always miss.
    • If you roll 20, you always hit.
    • Otherwise, you hit if you rolled higher than (THAC0 - AC). For example, if you're a first-level warrior fighting a monster with armor class 7 you need to roll higher than 20 - 7, or 13.
  • A small number of factors can influence this result. High strength can decrease your THAC0, making it easier for you to hit. High dexterity on the monster's part can increase its AC, making it harder to hit. Magic swords and armor can have similar effects.

You may well ask, "How can that possibly be too simple?" In two ways: first, it's too difficult to improve; second, there are too few gradations.

In a game like Ramble, there are two opposing forces that contribute to the fun of the game. The first is a sense of danger. The monsters really have to be able to hurt you, and maybe kill you. You have to be alert and pay attention. The second is a sense of improvement. As you play, you need to feel you're getting better -- that the monsters that gave you so much trouble early on are no more than a nuisance. Then, of course, you need to move on to more difficult monsters, and so on in a cycle.

Creating a sense of danger is no problem--just make the monsters a little more powerful, if things are two easy. No big deal. It's that sense of improvement that's the issue. So how can the player improve in combat? According to AD&D, he can improve in these ways:

  • He can increase in rank. Each level he gains decreases his THAC0 by one and improves his chance to hit. But after level 20, it's all over.
  • He can increase in strength or dexterity, which is a blunt hammer. These stats affect so much that they should be allowed to increase only rarely. In particular, they should never be allowed to increase early in the game.
  • He can gain a magic weapon. But even a minimal +1 magic sword has the affect of decreasing his THACO by 1; it's like gaining an entire level

In short, if I use the AD&D rules I'm presented with a serious problem. All of the possible improvements are really too strong. More than that, the total number of gradations in ability is low. I can either make improvements frequent and have the player top-out quickly (which makes for a shorter game than I have in mind) or I can make improvements extremely rare and increase the player's frustration.

The root problem is that the AD&D rules are designed for playing with pencil, paper, and real dice at conversational speed. Battles can take anywhere from minutes to hours. The total number of monsters a player slays during a session is usually going to be small. In Ramble, by comparison, a battle with a monster can take just a few seconds, and (as the game is currently written) you can fight 30 of them in just a few minutes. More than that, the computer can easily do computations that would become really annoying if you had to do them by hand.

The Angband combat model differs from AD&D in taking many more things into account, and in offering a much finer set of gradations. Your armor class, for example, starts at 0 and can go up almost indefinitely (one recent character of mine had an AC around 150). A new character might have an AC of 4, but with the benefit of a little gold that can quickly be increased to 16 or 20 after a short time playing. Similarly, a sword with +1 to hit isn't nearly the advantage that it is in AD&D, and so it can be much easier to acquire.

In short, the Angband model provides for a wider array of much smaller improvements, which allows the player to improve frequently over the course of a very long game.

Those who are interested can find details about Angband's "to hit" and damage computations here.

Of course, I could just go ahead and develop a whole new combat model; but Angband has been carefully honed over more than 20 years, resulting in a carefully tuned and well-balanced model. Anything I'm like to come up with along the same lines isn't likely to be as good. And I don't need to implement it all at once; I can add features as Ramble grows and evolves. I'll doubtless have more to say about that as I adopt things bit by bit.

Posted by Will Duquette at 06:45 PM | Comments(0)

January 24, 2005

Bye Bye Bertie, by Rick Dewhurst

Here's another remarkably funny book. It's a mystery novel, and a remarkably odd one at that.

Fair disclosure: the author sent me a free copy of this book, otherwise I'd never have picked it up in a million years. I accepted his offer with some apprehension, because this is a book that comes from the Christian Ghetto. There's quite a lot of fiction written from an explicitly Christian world view, published by explicitly Christian publishers for sale by explicitly Christian bookstores. I don't tend to read it, even though I'm a Christian; the little that has come to my attention (I'm thinking of the Left Behind series) hasn't been to my taste, and being a bit of a snob I've always felt that it was any good it would be sold in regular bookstores anyway (as Lewis and Tolkien and Walker are (Hi, Lars!)).

So I accepted this book rather against my better judgement, and rather put off reading it after it arrived in the mail. I was terribly afraid that it would be incompetently written, or so terribly, terribly earnest about the Christian faith that I'd find it uncomfortable reading. Please note: the Christian faith is indeed worth being terribly, terribly earnest about. But I find that fiction needs a lighter touch.

Anyway, I needn't have worried, and I'm actually a little ashamed of being such a snob, because I enjoyed Bye Bye Bertie immensely. Subtitled "A Joe LaFlam Mystery", it's a well-done farce. Joe LaFlam is a Christian private eye by day, a taxi driver by night, and a complete nutcase almost all of the time. He suffers, if that's the word I'm after, from a nearly continuous hard-boiled internal monologue about the state of his soul, his desire to be married, and his life as a private eye in the rainy town of Seattle, Washington, and sometimes his monologue spills over onto the people he meets. This generally causes them some confusion, because he in fact lives in Vancouver, British Columbia.

In the current tale (the first, and so far, I believe, the only one), Joe is approached by a beautiful young Christian woman; her sister has been kidnapped by a group of druids who are demanding $200,000 or they'll sacrifice her to their druidical divinity. Being, in his own mind, the gallant Christian knight, he undertakes to deliver the ransom--and then attempt to capture the kidnappers. Nothing goes as he plans, of course, and he ends up getting arrested by the police for rummaging suspiciously in trash cans; and the next day...

But I don't want to tell you the whole story, because that would spoil it.

The only thing that prevents me from recommending this book whole-heartedly is that it was written to be read by folks from a very specific Christian subculture, and if you aren't familiar with that background the book might seem very alien indeed, and you might have trouble telling when Dewhurst is being serious and when he's being over-the-top. The fact is, he's being over-the-top silly most of the time; like me, he's a man who needs to handle serious things with lightly.

And he does, indeed, speak of serious things. Joe's internal narrative reveals him to be a total nutcase, as I've said, Christian or not; but if Joe's capacity for self-delusion about the quality of his spiritual life is funny, it's also all-too familiar. My own internal monologues aren't nearly as purple as Joe's, but I've wrestled with lots of the same issues, and I've probably fooled myself just as often.

Well, maybe not that often. But often enough. At least--

Well, anyway, Dewhurst's written a book that even the secular humanists in my audience might enjoy. Just remember that it's a comedy, that it's over-the-top and exaggerated, and that it's not a life-portrait of those Red State voters you've been hearing about, as tempting as it might be to think otherwise. And even though your Borders or B&N might not have it, Amazon does.

Posted by Will Duquette at 07:14 PM | Comments(1)

Ramble Link Fixed!

Howdy! If you tried to download the OS X version of Ramble 0.3 yesterday and got a 404 error, try again today; the problem's been fixed.
Posted by Will Duquette at 06:28 PM | Comments(0)

January 23, 2005

The Ramble Chronicles: Ramble 0.3

I've just uploaded version 0.3 of Ramble to the Ramble Home Page. It's got many enhancements and changes, which I'll discuss below the fold. Here, I'd like to publicly thank Michael Cleverly, fellow Tcl'er and fellow father, who made speech synthesis work in Ramble (on Mac OS X only, alas). I first met Michael at the Tcl/Tk conference in Vancouver B.C. three and a half years ago, and I'm hoping to see him again in October at the Tcl/Tk conference in Portland. Speech synthesis isn't perfect yet; we only use one voice, and some of the more complicated interactions aren't spoken. But it's still useful for Michael's boy who isn't old enough to read.

The dungeons in Ramble 0.3 are fundamentally the same as in version 0.2. There are still three dungeon levels; there are still ten skeletons and ten or so chests on each level; and the level designs haven't changed. That said, there's quite a lot that's new.

Inventory: There's now a real inventory model. You keep the things you find, and you can drop them if you don't want them. (You might even be able to sell them....) I'll be writing more about the inventory model Real Soon Now. That said, the crossbow and its ammunition (bolts in 0.3, rather than missiles) are still handled by ad hoc code rather than being part of the inventory model (I need to add the ability to equip weapons and armor). If you drop objects, they accumulate in a chest at your feet. They'll even be there when you come back (though if you leave them anywhere but Trouserville, I'm not promising that this will always be true).

Combat: There's now a real combat model, based loosely on the AD&D second edition rules. I'm not entirely happy with it yet, but it's a start. Both you and the monsters you fight have hit points and some kind of hand weapon to hack and slash at each other with; you're not limited to using the crossbow to fight them.

Health Potions: Some chests will have "small health potions"; you'll also find these in the Potions store in Trouserville (if you can afford them). Each restores a small portion of health when you drink them. They are saved in your inventory until you need them; investigate the Trouserville Public Library to learn more.

Shops: I've developed a preliminary interface for interacting with the shopkeepers that lets you buy and sell goodies.

Reduced Viewport: The viewport is now 24*24 tiles in size, down from 31*47, which means you can't see an entire level at once. I find that this makes the game more interesting.

Redesigned Trouserville: I've redesigned and enlarged the town of Trouserville; it's more interesting to explore, I think, and nicer to look at. The Public Library is larger, and the quality of the on-line help has been significantly improved. The town has a few surprises as well.

Application Enhancements: You can now save and restore your game whenever you like. Note that save files for version 0.3 are unlikely to work with later versions.

Various Internal Changes: The internal code has been upgraded significantly to make all of this work. I'm following my favorite development process while working on Ramble: when you don't know quite how best to do something, write ad hoc code so that it works; based on that, figure out how to ought to work and then go back and fix it. You know you've got the right architecture when you can slot in new features cleanly, without a lot of changes to unrelated code.

So what might be next in the world of Ramble?

Essays: I want to write further essays on maze and level generation, inventory modeling (i.e., how do you make the health potion restore health? And how does it know it's a health potion anyway?), and dungeon economics (I've got a start on this one, but it's a big topic).

Weapons and Armor. That is, the ability to equip weapons and armor from your inventory, with a corresponding increase in the number of available kinds of weapons and armor. The point is to give you something to buy with your hard-earned loot that will make your job easier.

Additional Monsters. Just skeletons all the time is getting dull.

Treasure Drops. Monsters should drop treasure when you kill them. The treasure should vary depending on the monster, and also on the dungeon and your depth in the dungeon. The same applies to chests.

Level Regeneration. The monsters should come back after a while. In Angband, levels are completely regenerated (including the maps) each and every time you come back to them. I might want to go with that, but there are issues.

Multiple Quests. The quest for the Golden Underpants should be just the beginning. I have a suspicion that the manager of the town laundry might go missing.....

Posted by Will Duquette at 06:59 PM | Comments(0)

January 21, 2005

The Soddit, by A.R.R.R. Roberts

My brother gave me this book for Christmas, and he's probably been wondering when I was going to get around to reading it and reviewing it. I actually finished it over a week ago, but the reviews have been lagging.

The Soddit, subtitled "or, Let's Cash In Again", is a remarkably funny parody of J.R.R. Tolkien's The Hobbit. I say "remarkably" because parody is a form that backfires more often than not, and the likelihood of failure increases with the length of the work. At 343 pages, The Soddit is considerably longer than its nearest neighbor, Harvard Lampoon's Bored of the Rings, and it's also considerably funnier. Roberts somehow manages to stand every well-known scene on its head, and still come up with a fairly coherent narrative. When you're done, you've actually read a complete story, one with great similarities to Tolkien's work, but a genuine story in its own right as well. And it's funny, too, which as I say is remarkable.

I won't give any of the jokes away, much though I'd like to. I'll just say that Roberts appears to be aiming for something halfway between Douglas Adams and Terry Pratchett, and if he doesn't quite hit the bullseye he's still to be commended for hitting the target at all.

Read it yourself; or buy a copy for your favorite Tolkien fan. They'll like it, if their sense of humor is in working order; and if they don't at least you'll have the fun of watching them fume.

Posted by Will Duquette at 07:48 PM | Comments(0)

January 20, 2005

The Ramble Chronicles: Maze Generation 1

I'm writing Ramble for my kids to play, but I'm also writing it for myself. If a game is to be appealing to its author, then it has to include a fair amount of unpredictability. In a game like Ramble, that means generating interesting but unpredictable levels. The problem has many aspects, but in this essay I'm going to focus on the issue of random terrain in general, and random mazes in particular.

Note: So happens, this is the 1,000th post on this blog; so you should click through to the rest of it, if only for the pretty pictures.

I owe some of the ideas that follow to two web sites. The first is Jamis Buck's Random Dungeon Design, which describes the algorithms behind a program he wrote to randomly generate dungeons for traditional pencil and paper role-playing games; the second is Think Labyrinth, a site dedicated to mazes and random maze generation algorithms.

The algorithm I'm going to describe is called a recursive backtracker. It belongs to a class of algorithms that all work more or less the same way. You begin with a rectangular array of rooms separated by walls. Given a randomly chosen starting room, these algorithms proceed by repeatedly selecting a room adjacent to a room in the maze and opening a door in the wall between the two. When the algorithm's done, you've got what's called a "perfect maze": one in which every room is connected to every other room by exactly one path, and in which there are no circular paths. The algorithms differ in how the new rooms are selected.

The recursive backtracker uses a simple pushdown stack; the algorithm is as follows:

  • Pick a room randomly, and push it onto the stack. This is the starting room.
  • Pick a room adjacent to the first room, and open a door between them. This room is the current room.
  • Push the starting room onto the stack.
  • While there's at least one room left on the stack, repeat the following steps:
    • If there are any unconnected rooms next to the current room,
      • Pick one randomly, and open a door between it and the current room.
      • Push the current room onto the stack; the new room becomes the current room.
      • Go back to the top of the loop.
    • If there are no unconnected rooms next to the current room,
      • Pop a room off of the stack; it becomes the current room.
      • Go back to the top of the loop.
  • When the stack is empty, the maze is complete.

Here's a simple example, using a 3*3 maze. The stack is shown under each picture of the maze.

  • D is the randomly chosen starting room. We could choose any of A, E, or G as the current room; we'll roll a die and choose A. We open a door and push D on the stack.
  • There's only one unattached room next to A, and that's B. We open a door to it, and push A on the stack.
  • From B we can pick E or C, and we pick E, pushing B on the stack.
  • From E we can pick F or H. We pick F, pushing E on the stack.
  • From F we can pick C or I. We pick C, pushing F on the stack.
  • C has nothing unattached next to it, so we pop F back off of the stack. From F we can pick I, and we do. F goes back on the stack.
  • From I we can only pick H, and we do. I goes on the stack.
  • From H we can only pick G, and we do. H goes on the stack.
  • G is a dead end. We pop rooms off of the stack one at a time, looking for a room with an unattached neighbor. When the stack is empty, we're done; we have a maze.

Here's a 10*20 maze generated using this algorithm:

As you can see, it has relatively few short dead-ends and lots of long and twisty corridors, which is part of what I was looking for. It's also one of the faster algorithms, which is another part of what I was looking for.

Now it's time to think about how to represent all this in Tcl.

A maze is a rectangular array of rooms, so we'll represent it as a matrix. In an earlier essay, Efficient Matrices, I talked about how I planned to do that in Tcl; feel free to review. So for a 3*3 maze, I'll want to have a 3*3 matrix; each element in the matrix describes one room in the maze. And we'll use matrix notation. The dimensions of the maze are m rows by n columns, which are numbered from 1 to m and from 1 to n respectively. Each room in the maze is named by a pair of indices, which I'll write in Tcl list format as {i j}. Thus, the upper left roomm is {1 1}.

Now, what do I store in each cell of the matrix?

Each room in the maze has four walls, which I'll identify as the north, south, east, and west walls, or n, s, e, and w respectively. Each wall can be open (missing) or closed, which means we need four Boolean flags for each room. There are any number of ways to do that; being an old-time C programmer, I chose to use a bit vector--a coded integer the bits of which correspond to the flags I need. Here's an array that relates the four walls and the related bits:

    array set mask {
        n   1
        e   2
        s   4
        w   8
    }

    puts "n's bit value is $mask(n)"

Thus, if the north and west walls of a room are open, the value stored in the matrix for the room will be 9 = 1 + 8. If the value is 0, that means that no walls are open. I can initialize my matrix to all zeroes, and that means that all the walls are closed, ready for the algorithm to begin.

Now, a wall has two sides; the north wall of one room is the south wall of another; when opening a wall, we need to update the value in both rooms. Given a wall, the following array lists the bit value of the other side of the wall within its room:

    array set revmask {
        n   4
        e   8
        s   1
        w   2
    }

    puts "The bit value of the opposite of n is $revmask(n)"

Given the coordinates of a room, {i j}, and a direction, I will frequently want to know the coordinates of the adjacent room in that direction. I've written elsewhere of some utility routines I wrote to make this easier; I wrote the maze code before I wrote those, so here will do it the hardway. I need the following two arrays, which show the coordinate offsets by direction:

    # Row offsets
    array set roff {
        n  -1   ne -1  
        e   0   se  1
        s   1   sw  1
        w   0   nw -1
    }

    # Col offsets
    array set coff {
        n   0   ne  1
        e   1   se  1
        s   0   sw -1
        w  -1   nw -1
    }

Our recursive backtracking algorithm is written in terms of three lower-level functions: pickfrom, freedirs, and removewall. The first, pickfrom, I described in the essay Randomness; given a list, it returns a randomly chosen entry from the list.

Given a maze and an {i j} coordinate pair, freedirs returns a list of the directions n, s, e, or w in which there are unattached (or "free") rooms. It looks like this:

proc maze::freedirs {maze i j} {
    variable roff
    variable coff

    set dirs {}

    foreach dir {n s e w} {
        # Get the tile in that direction
        set i2 [expr {$i + $roff($dir)}]
        set j2 [expr {$j + $coff($dir)}]

        # If it's over the edge, skip it.
        if {![minside $maze $i2 $j2]} {
            continue
        }


        # If it's free, add the direction to the list.
        if {[lindex $maze $i2 $j2] == 0} {
            lappend dirs $dir 
        }
    }

    return $dirs
}

The room is free if no walls are open, i.e., if the room's value has no bits set, i.e., if the room's value is zero. The minside function is one of the matrix routines; it simply does a range check on a coordinate pair to see if it lies "inside" the matrix. Here it's used to skip invalid directions from rooms on the edge of the maze.

The removewall function removes a wall between two rooms given a variable containing a maze, the {i j} coordinates of one of the rooms, and the direction dir to the other room. The routine assumes that both rooms exist in the maze, e.g., their coordinates are minside the matrix. It looks like this:

proc maze::removewall {mazevar i j dir} {
    upvar $mazevar maze
    variable mask
    variable revmask
    variable roff
    variable coff

    # FIRST, if there's no wall we don't need to do anything.
    set map [lindex $maze $i $j]

    if {$map & $mask($dir)} {
        return
    }

    # NEXT, add the wall on this side.
    set map [expr {$map | $mask($dir)}]
    lset maze $i $j $map

    # NEXT, add the wall on the other side.
    incr i $roff($dir)
    incr j $coff($dir)

    set map [lindex $maze $i $j]
    set map [expr {$map | $revmask($dir)}]
    lset maze $i $j $map
}

Finally, we put it all together in mkrecback, which takes the dimensions of the maze and returns the finished maze. It also takes an option, -inertia 0|1; if 1, the maze is generated with "inertia", and if 0 without. Having inertia means that when it comes time to pick the next room to add to the maze, we're likely to keep going in the same direction as last time (assuming we can). That gives us longer straight sections in the maze, which I happen to like.

proc maze::mkrecback {m n args} {
    variable roff
    variable coff
    variable mask
    variable revmask

    # FIRST, get the options
    array set opts {
        -inertia 1
    }
    array set opts $args

    # FIRST, make a maze of all free cells.
    set maze [matrix::new $m $n -type maze -init 0]

    # NEXT, pick the starting cell.
    set i [rand 1 [mrows $maze]] 
    set j [rand 1 [mcols $maze]]

    # NEXT, get a direction to a free cell; there will always be one.
    set dir [pickfrom [freedirs $maze $i $j]]

    # NEXT, remove the wall between them.
    removewall maze $i $j $dir

    # NEXT, push the starting cell on the stack, and move to the new
    # cell.
    set stack {}
    lappend stack [list $i $j]
    set lastdir $dir
    set i [expr {$i + $roff($dir)}]
    set j [expr {$j + $coff($dir)}]

    # NEXT, add cells until the stack is empty.
    while {[llength $stack] > 0} {
        # Are there any free cells next to the current cell?
        set dirs [freedirs $maze $i $j]
        
        # If not, pop a cell from the stack and continue.
        if {[llength $dirs] == 0} {
            set i [lindex $stack end 0]
            set j [lindex $stack end 1]
            set stack [lrange $stack 0 end-1]
            continue
        }

        # Make it more likely to continue in the same direction.
        if {$opts(-inertia) && [lsearch -exact $dirs $lastdir] != -1} {
            lappend $dirs $lastdir
        }

        # Otherwise, carve into one.
        set dir [pickfrom $dirs]
        removewall maze $i $j $dir

        # Now push the current cell onto the stack and go on to the next.
        lappend stack [list $i $j]

        set i [expr {$i + $roff($dir)}]
        set j [expr {$j + $coff($dir)}]
    }

    return $maze
}

And that's (ha!) all there is to it.

Well, actually there's a lot more I need to do to a maze like this before it becomes a real dungeon level; in future essays I'll be talking about some of the things I do to make that happen.

Posted by Will Duquette at 07:41 PM | Comments(0)

January 19, 2005

Rambling About

I spent a good bit of the evening working on an essay about maze generation, but it's not done yet. Maybe tomorrow.

Posted by Will Duquette at 07:52 PM | Comments(0)

January 18, 2005

In Memoriam: Charlotte MacLeod

I've just learned from Jaquandor that mystery novelist Charlotte MacLeod has died. The announcement is here. Ms. MacLeod hadn't been able to write in several years, and perhaps this came as a release. In any event, she will be missed. If you've not read her books, you can find a list at our Charlotte MacLeod page.

Posted by Will Duquette at 10:12 PM | Comments(0)

January 17, 2005

The Far Side of the Stars, by David Drake

The is the latest in Drake's Daniel Leary/Adele Mundy series of space operas, and I have mixed feelings about it.

In the wake of Lieutenant Leary Commanding, Cinnabar and the Alliance have signed a peace treaty, with all that that entails for junior naval officers. Things are tight all round, and even so famous a hero as Leary isn't sure of getting a ship. But just because a treaty's been signed, that doesn't mean that the Alliance is sleeping; and Cinnabaran Intelligence never sleeps. A number of interests come together: A wealthy but eccentric couple from the planet of Novy Sverdlovsk wish to explore the Galactic North, a region of loosely federated, mostly primitive systems nominally friendly to Cinnabar. Supposedly they are travelling for pleasure, to indulge their interests in archaeology and big game hunting; actually, they are looking for signs of a man named John Tsetzes, one time dictator of Novy Sverdlovsk, who upon his overthrow a century before was known to have fled to the North with a number of planetary treasures. Meanwhile, Bernis Sand, head of Cinnabaran Intelligence, wants to get a skilled observer into the Galactic North, to look for signs of Alliance activity. There have been reports that the Alliance has begun building a base in the system of Radiance, and she wants the straight dope. Adele Mundy is her agent of choice.

Leary is in need of a command. The Klimovs are in need of a ship. Bernis Sand is in need of a spy. And the Princess Cecile is being sold out of the service. Leary finds himself the civilian captain of the Cecile, under contract to the Klimovs, to a place where Cinnabaran officers have but rarely gone.

It's an interesting story, with the usual smash-bang ending; my complaint is that large parts of it were too pat. For example, once they arrive in the Galactic North and begin searching in earnest they just happen to find a relic of John Tsetzes in the first house they enter on the first planet they visit, and thereafter track his steps in the most unlikely way, with nary a misstep or red herring or backtrack.

Still, it was quite a good read, and I'll certainly get the next Lt. Leary, should there be one.

Posted by Will Duquette at 03:47 PM | Comments(0)

The Ramble Chronicles: Quest

I'd like to begin with a couple of observations.

  • When I remember myself in past years, I'm often impressed with how much I've changed. And when I go back and look at things I wrote or built or created in past years, I'm often impressed with with how little I've changed.

  • It pays to be anal-retentive.

In the winter of 1992, I spent a week in Fort Leavenworth, Kansas, supporting a military training simulation for which I was one of the programmers. Actually, I only spent the days there; I spent the nights at a Comfort Inn in Platte City, Missouri. (No one on the project actually wanted to stay in Leavenworth.) It was the first week of the 1992 Winter Olympics, and I spent my evenings sitting on the bed in my hotel room, watching the Olympics and working on a little game called Quest on a DOS laptop I'd borrowed from my dad.

The laptop was a simple little thing, nearly obsolete even then; it was a Radio Shack model with not a lot of memory and a tiny hard drive and no graphics, and a battery that didn't hold a charge well, and it ran DOS. I loved it--it was a computer I could take on the road.

Quest was my first attempt at writing a tile-based game, along the lines of the Ultima series. It was written in a mixture of C++ and a Forth-like language for which I'd written an interpreter; the basic game engine was in C++, but all of the creatures and objects and regions to explore were defined in Forth. I'd never heard of Tcl at that point, but I'm sure the Tcl programmers reading this are nodding their heads--I was ripe to embrace Tcl when I discovered it.

The output was to the DOS screen, but by way of a hack. DOS allowed you to redefine the screen's character set temporarily. So Quest used character graphics, but with special graphical characters I defined for the various monsters, objects, and terrain features, along with all of the lovely characters in the PC's extended ASCII character set.

It was a thing of beauty, and I had a lot of fun working on it. In the end, though, it was a failure, for a host of reasons.

  • As a DOS program it was retro at a time when retro was no longer in. Microsoft Windows was already the next big thing.

  • There was no World Wide Web on which to distribute it. I could have uploaded it to a PC Bulletin Board, and it might have garnered some minimal attention, but (given that it was retro) probably not a whole lot.

  • It was trying to be Ultima rather than Angband, and consequently it was never finished.

That last point requires some explanation. Ultima was a game written for other people to play; it held few surprises for the its developer. The world map, the towns, the castles, and so forth were predetermined. Angband development has always been done by folks who want to play the game themselves, and want it to unpredictable and surprising, and so as much as possible of the game is randomized in one way or another.

So basically, Quest was a game I was writing for other people to play. The joy I got out of it was implementing the basic infrastructure to make the game work; designing new levels and quests was, on-the-whole, rather boring. Testing my new features was one; playing the levels I'd already designed was dull, because I knew exactly what I had to do.

This might not have been fatal had Quest had an audience; but in fact it didn't.

I like the Ultima model, and I want to bring some of that to Ramble; but I also want a game I'll enjoy playing, which is why much of my initial work on Ramble has focussed on creating interesting random levels.

Anyway, I needed a combat model for Quest, and I didn't really feel like making one up from scratch. So I went out and got a copy of the Advance Dungeons & Dragons (2nd Ed.) Player's Handbook and cribbed from that. I didn't use the AD&D rules verbatim, as they weren't written with computer games in mind, but I used them as a starting point and an inspiration.

Being about ready to start some simple combat modeling for Ramble, I cast about my hard drive and found the Quest source code, which, astoundingly, I hadn't thrown away in the intervening 13 years. I found the combat code easily enough, but I was lacking context--why had I done things the way I did? What, of all things, was a "THAC0"?

I put the computer away, and went to dig up that self-same Player's Handbook which, miraculously, I hadn't thrown away in the intervening 13 years--and struck gold.

Inside the front cover of the handbook was a hard copy of some of the Quest source code--and a print-out of something called (obscurely) the Analyst's Guide to VF. What it is, is a document that talks about how things are done in AD&D, with page references to the Player's Handbook, and then explains how I modified them to use them in Quest. More than that--it documents the basic player, creature, object, and combat models used in quest, and explains why they are the way they are.

Who would have thought, 13 years ago, that I'd be able to put my hand on all of these resources in a matter of moments?

As I said, it pays to be anal-retentive.

Posted by Will Duquette at 11:27 AM | Comments(0)

January 15, 2005

Lt. Leary Commanding, by David Drake

This is the second of Drake's Daniel Leary/Adele Mundy series, and though I enjoyed it well enough on second reading, I found that it dragged a bit. A ripping yarn, yes, but a bit slow to get going. The general outlines of the plot are similar to the previous book; Leary is sent to a nominally friendly place where the Alliance is secretly busy, and Leary saves the day with a big win against great odds due to equal parts of luck, talent, skill, and bullheaded determination. There's a fair amount of political intrigue that goes on toward the beginning, resulting in a surprising zoological discovery on Leary's part that I expect will have long term repercussions as the series progresses; but on the other hand, it had little enough to do with the present story.

So, good fun; but Drake can do better.

Posted by Will Duquette at 05:43 PM | Comments(0)

January 14, 2005

With the Lightnings, by David Drake

The first time I read this book, the first in Drake's Lieutenant Leary series, I suggested that Drake was channeling David Weber--he of Honor Harrington fame. By the time I'd finished the second book in the series I'd gotten the clue. Drake wasn't trying to out-Weber Weber, he was doing an homage to Patrick O'Brian's Aubrey/Maturin novels. There were just too many parallels for it to be by accident, and so when I set out to re-read With the Lightnings I had my eyes open. But more of that anon.

For those coming in late, the Lieutenant Leary series is pure military space opera. Daniel Leary is a Lieutenant in the Royal Cinnabaran Navy; the Empire of Cinnabar is one of two leading powers in the human-explored galaxy. He's come to the planet Kostroma as part of a diplomatic mission to the new ruler of Kostroma, but he has no particular duties; he was chosen only because he's the son of Corder Leary, one of the most powerful men in the Empire, and someone thought the Kostromans would be impressed by that. In fact, Leary hasn't spoken to his father since some years prior, when they fell out over his joining the RCN. Since then he's been scraping along, trying to get ship duty. Now he's got it, and he's bound and determined to enjoy it as much as he can.

Meanwhile, Adele Mundy has accepted a position as librarian to the ruler of Kostroma; the fellow wants to be accepted as a patron of learning, so he began his rule by looting every other library in the capital. Mundy's a post-graduate of the Academy on Bryce, and is extremely accomplished at winnowing, categorizing, cataloging, and above all retrieving data--whether she's supposed to have access to it or not. She's a Cinnabarran citizen--a member of one of the great Cinnabaran families, just as Daniel Leary is--but hasn't been back to Cinnabar in sixteen years, when the bulk of her family was put to death in the aftermath of a failed coup, by order of Daniel's father. Later it came out that the Alliance was behind the coup; the Alliance is the other major power in the galaxy. Adele's parents and baby-sister were among the dead, leaving her with a kind of pox-on-both-their-houses attitude toward both Cinnabar and the Alliance.

Daniel and Adele meet under uncomfortable circumstances, and surprisingly become friends. This is just a few days before the Alliance foments an uprising on Kostroma--and by chance Daniel is the only RCN officer left at large after the first hours. He's got a chance to save the day, and given the kind of book this is, you just know he's going to pull it off; it's time to sit back and enjoy the ride.

As I say, I was looking for the Aubrey and Maturin parallels this time through, and I found one that's just plain silly. Probably the best known scene in all of O'Brian's work is in the very first book, Master and Commander. And it's the best known because it's the scene that's most likely to cause first-time readers to put the book down and stop reading O'Brian forever. It's Stephen Maturin's first time aboard Jack Aubrey's new command, the sloop Sophy, and Jack has requested a midshipman to give Stephen a tour of the rigging. And Stephen is afraid of heights. What follows is, when read in the right spirit, a remarkably funny scene composed of two monologues--the midshipman reciting the names of all of the parts of each mast, and the different sails, and so on and so forth, in exacting detail, ad infinitum ad nauseum, and Stephen not listening because he's so worried about falling to the deck and killing himself, while yet trying to make the appropriate responses. Really, you shouldn't pay any more attention to the rigging than Stephen does, and then you'll get through the passage OK. But people always try to make sense of it, and then they fall out of the book. Pity.

Shortly before the uprising begins it's Founder's Day on Kostroma, when they celebrate the first landing on the planet. There's quite a spectacular parade, and Leary has figured out that they best place to sit and watch is on the roof of the ruler's palace--provided that one has binocular goggles to look through. And so Leary waltzes into the palace library and then waltzes Adele Mundy up to the roof to watch the parade. He nonchalantly walks down the tile roof (a 30 degree slope) to the very edge, where he can rest his feet in the rain gutter; while Adele makes her slow and painful way down to him backwards on her hands and knees, she being (natch) afraid of heights. And as she's coming slowly down the roof, Leary begins a long disquisition about what it's like to be out on the hull of a starship during a passage between systems, and what all the different parts are, and did I mention that in Drake's universe the starships have masts and sails? There's no reason for him to be talking about it at that particular point in the story, except to counterpoint Adele's internal monologue about what she'd look like after she hit the pavement.

It's all quite silly, and I had a good time re-reading it.

Posted by Will Duquette at 08:30 PM | Comments(0)

The Ramble Chronicles: Things to Avoid

This is not so much an essay as a brief rant on a couple of things I don't intend to put in Ramble. Read on!

Sewers. There will be no sewers. Your player will not need to descend into the sewers at any reason, for any time, for anybody. Almost every RPG out there takes you into the sewers at one point or another; it's trite, it's a cliche, and heaven knows I don't want to try to draw sewage tiles.

The Four Elements. If an RPG doesn't have sewers, it will certainly have the Four Elements: air, earth, fire, and water. There will be creatures based on each element (with variations like thunder and ice) and creatures susceptible to each element, and you'll end up with a variety of elemental attacks (fire balls, lightning bolts, ice storms, and so forth. The fun, of course, lies in figuring out which attacks work best on which creatures.

Ramble will not do this if I can possibly help it. Creatures might well be vulnerable to some attacks and resistant to others, but I'm going to do what I can not to base any of this on the Four Elements. There's got to be something more original that I can come up. I'm not saying that I won't have fire balls and lightning bolts, but I won't use the elements as a guiding principle.

Especially not in the sewers.

Posted by Will Duquette at 09:59 AM | Comments(0)

The Ramble Chronicles: Ramble 0.2

I decided that I'd done enough work since Ramble 0.1 to make it worth taking a snapshot; and if I were going to take a snapshot, I figured I might as well put it on the web. You can download Ramble 0.2 as a Windows or Mac OS X executable, or you can get a Tcl starkit. Read on for a description of the changes; you might also want to (re)read the description of Ramble 0.1.

The point of the game is still fundamentally the same as Ramble 0.1: you have to retrieve the treasure from the dungeon while not getting killed by the skeletons. However, there have been a number of improvements:

Inventory: You can now carry a maximum of 20 missiles; you get 10 when you receive the crossbow. Chests in the dungeon can now contain additional missiles and gold, along with the usual rubbish. There's still no real inventory model, though.

Status Display: There's a new status display on the right hand side of the window. It shows the level you're one, the amount of experience you've accumulated, the amount of gold you've accumulated, and the number of missiles you have left. Note that gold and experience aren't good for anything yet, but you do accumulate them.

Levels: There have been a few minor changes to the town level, and there are now three different kinds of dungeon level, chosen randomly at dungeon creation. Also, the dungeon used to only be one level deep; now it's three levels deep, and the treasure you're looking for is on the third level.

Also, some levels (including the town level) have doors which can be opened and closed. Visit the help spots in the Trouserville Public Library to learn how to open and close doors.

There are a few other surprises in the dungeon levels which I'm not going to tell you about; you'll have to take a look.

Movement: You can now use the movement keys I talked about in Key Sequences, which means that you can now move and shoot on the diagonals.

Game Menu: When the game ends, you can now start over by selecting New Game from the Game menu.

Things I might work on next: Ramble development proceeds in a rather drunken fashion, lurching this way and that as I figure out how to do things and as my whim takes me. But here are some of the things I might work on over the next few days:

  • Reduced Viewport. At present, all levels are 31 rows by 47 columns in size, which (given complete visibility) is also the size of the viewport. I want to reduce the viewport size and increase the level size. This is really why I released Ramble 0.2; the game's going to start looking rather different than it does now, and I wanted to capture the current version. It's fun to be able to go back and see what things were like before.
  • Shopkeepers. I've got shopkeepers, but they can't sell you anything. I want to build at least a preliminary interface for interacting with shopkeepers, so that at the very least you can buy missiles with the gold you find in the dungeon.
  • Better Combat. The current One-Touch-And-You're-Dead model is annoying. That means that the player and the creatures need hitpoints.
  • Additional Monsters. I'd like a few more monster types with different behaviors.
  • Level Regeneration. At present, if you kill all of the monsters on a level they never come back. It seems like at least a few of them should, possibly depending on how long you've been gone.
  • Treasure Drops. When you kill a monster, it should possibly drop some treasure. Which reminds me: I need to write an essay on Dungeon Economics.
  • Multiple Quests. The quest for the Golden Underpants of Timbucktoo is a slender reed on which to hang an entire game. Rather than winning the game when you bring them back to the King, he should probably set you another quest, probably in an entirely different dungeon.

We'll see what happens.

Posted by Will Duquette at 09:49 AM | Comments(0)

January 13, 2005

Rambling About

Once again I spent the evening working on Ramble instead of writing blog posts. And I've got a lot of write about: a bunch of books, and a bunch of Ramble topics; I suspect that the next Ramble Chronicles will be on maze generation. Come on back tomorrow, and I'll try to have more for you.

Posted by Will Duquette at 09:24 PM | Comments(0)

January 12, 2005

Deep Impact

NASA's Deep Impact spacecraft was successfully launched into space today, and yours truly was there to watch...sort of. I wasn't at Kennedy Space Center; instead, I was at the "ROC", which is where the project "NOPE" (Network Operations Project Engineer) keeps tabs on all the things that have to go right for JPL to track the spacecraft, receive its telemetry, and send it commands. Among those things are the various subsystems of JPL's Deep Space Network. For critical events (such as launch and first acquisition) the flight projects like to have subsystem engineers on-tap in case anything should go wrong. And since I work on the Uplink subsystem, that meant me, or one of my co-workers. This time it was me.

The experience was both exciting, as I'd not supported a launch before, and terribly, terribly boring, as nothing went wrong that I had to deal with. Please note: I'm not complaining. Boring is what I was hoping for.

But a full day of boring leaves me tolerably brain-dead and in no mood for blogging, so I will leave you with a link to the Deep Impact home page. Don't miss it!

Posted by Will Duquette at 08:11 PM | Comments(0)

January 10, 2005

Spring Fever, by P.G. Wodehouse

This is not a Blandings novel. There are no pigs. There is no Earl of Emsworth. There is no Beech the Butler. There is no Lady Constance... well, then again, there's sort of a Lady Constance, though she's the Earl's daughter rather than his sister. And there are imposters, and heaven knows Blandings just isn't Blandings without imposters. And though it's a stamp rather than a pig, heaven knows there's a McGuffin that's just ripe for being stolen, if only one of the guests was a former safecracker. But the Earl's not an idiot; he's merely impoverished. And his offspring aren't idiots either; the only idiot isn't even a member of the family.

In fact, Wodehouse has taken the established conventions for Blandings novels and turned most of them on their heads, and produced a really quite delightful confection that satisfies the same craving as do Lord Emsworth, the Empress of Blandings, and so forth, and yet in a delightfully different way.

I'm just itching to go into great detail about all the things Wodehouse does differently than usual in this book, but that would mean giving them away, and we can't have that. So if you're a Wodehouse fan, you'll just have to go out and find a copy.

And if you've never read Wodehouse, why on earth are you wasting your time with me when you could be discovering Wodehouse?

Posted by Will Duquette at 08:34 PM | Comments(0)

Lexicon: An RPG for frustrated encyclopedists

It's a game. You get together with a group of people, and make up encyclopedia entries. Each entry cites other entries, some already written, some not yet written. They need not be factual; in fact, it's probably best if they aren't factual. This is not an exercise in erudition, it's an exercise in imagination. At the end, you've got a web of 26*(number of players) entries, and presumably have had a good time.

As Michael says, it could be a lot of fun with the right group of people--rather like Balderdash on steroids, I'm thinking. But I'm having difficulty imagining how you'd pick such a group, though.

Posted by Will Duquette at 04:57 PM | Comments(0)

January 09, 2005

The Ramble Chronicles: Key Sequences

OK, this has got to the be the geekiest entry in this series to date, as well as the most specific, as it involves an obscure point of Tk programming that will be of interest to almost no one; on the other hand, there are some reflections on player controls that might be of interest to a broader audience.

Although Ramble has a GUI interface, it's a game played entirely with the keyboard. (I've seen tile-based games with mouse interfaces, and I've never liked them. ) This shouldn't be surprising; game console controllers got by for years with a handful of buttons and direction pad (basically four arrow keys combined into a single button); the newer consoles add analog joysticks, but for a tile-based game with discrete movement they don't really buy you anything. So using keyboard commands makes sense.

In your typical tile-based console game (Final Fantasy I, say, or Pokemon in its various flavors), your character is always facing one of four directions, which I'll call N, S, E, and W. If you wish to interact with a non-player character, or a switch, or some piece of machinery, you walk up to be and press a button. This is a nice, simple interface, and it works great for console games because you only need one button for all the different kinds of interaction you can do. On the other hand, it places some constraints on the game:

  • Any feature or creature in the game can only support one kind of interaction, because there's only one way to activate it (unless you have it pop-up a menu, which works but is obtrusive).
  • You can't face the diagonal directions (NE, NW, SE, and SW).
  • You need at least four separate graphics for the player and each kind of creature the player can talk to.

It's certainly possible to build a rich game under these constraints, but for several reasons I don't want to do so. First, I'd like to have features and creatures that have multiple interactions. Even now, features support at least two interactions, "examine" and "walkon" and therefore need at least two ways to be activated. Second, in the games I'm speaking of, combat doesn't take place in the same environment your character walks around in; instead you go to a separate combat mode. In Ramble, the monsters walk around just like you do, and the ability to attack or move along the diagonals can be really important. Third, life's too short for me to create all of those graphics.

So Ramble goes with a scheme where your character isn't facing any particular direction but can move and interact with creatures and features in any of the eight directions, N, S, E, W, NE, SE, NW, and SW. This has two implications: I need eight direction keys, instead of just four, and I'm going to need to use key-sequences for certain player actions. By key-sequence I mean two or more keys pressed in sequence; to examine the contents of an adjacent tile, for example, you press the "x" key, followed by a direction key. To talk to a creature in an adjacent tile, you press the "t" key, followed by a direction key. And so on.

As I say, I need eight direction keys. Two different sets suggest themselves; the first is that old standby, the numeric keypad:

I first wrote code to use a numeric keypad in this way back when I was learning to program back in the late 1970's (good grief--I've been programming for over twenty-five years!). This is decidedly retro, but if you play Angband then these are the keys you use to move your character around.

Unless of course they aren't, which leads me to the next possibility: the "Rogue" key set:

Back when the Unix operating system was first developed, many computer terminals didn't have arrow keys; consequently, many full-screen programs used the H, J, K, and L keys (or sometimes ^H, ^K, ^K, and ^L) as shown as direction keys. The vi text editor, in use daily by millions of programmers, still uses this scheme. The original Rogue game, the ancestor of Angband, extended this to the diagonals as shown. It's a remarkably efficient layout; you use the four fingers of the right hand for the four cardinal directions; the index finger picks up the diagonals. It takes a bit of getting used to, but it has one major advantage--it lets you play Angband on a keyboard that doesn't have a numeric keypad. My primary computer has been a laptop for many years now, and practically speaking laptops don't have a numeric keypad. As a result, this layout has become second nature.

I'm nerdier than 78 percent of the population according to an on-line quiz I took, did I tell you?

Anyway, Ramble will support both of these key sets: the Rogue keys for me and the numeric keypad for my kids.

OK, now on to the Tcl/Tk part of this essay. Tk allows you to define "key bindings"--in essence, you specify the keystroke and a Tcl command to execute, and when the key is pressed, Tk executes the command. Here are two of the key bindings for the numeric keypad:

bind . <Key-4> {game moveplayer w}
bind . <Key-6> {game moveplayer e}

In short, if the player presses 4, the player's character is moved west. Easy enough. But what about talking to another character where you need to press "t" and then indicate a direction? Tk handles this quite nicely:

bind . <key-t>        {game talk_intro}
bind . <Key-t><Key-4> {game talk w}
bind . <Key-t><Key-6> {game talk e}

When the player types "t" followed by "4", the player's character will talk to the creature to the west, if any. The first binding on "t" by itself logs a message that says to press a direction key to indicate the direction in which you want to talk.

So far so good. Now, our player can acquire a crossbow; once he has the crossbow, he can fire missiles using the "f" command and a direction. We can implement that in the same way:

bind . <key-f>        {game fire_intro}
bind . <Key-f><Key-4> {game fire w}
bind . <Key-f><Key-6> {game fire e}

This is exactly like the example above, except that it's more violent. But it presents a problem: what do we if the player hasn't found a crossbow yet? Obviously we tell him that he doesn't have a crossbow--but it seems silly to tell him to enter a direction key to fire a missile, and then tell him he has no crossbow. He shouldn't have been prompted to enter a direction key to begin with.

The naive solution is for the "fire_intro" routine to check whether the player has a crossbow, and either prompt the player for a direction or tell him he doesn't have one. Again, so far so good. The problem is, Tk is still waiting for the other shoe to drop. Suppose the player has no crossbow, and presses "f". He's told he has no crossbow. "Oh, dear," he says, "I'd better run." So he presses the "6" key to walk away from the monster--and the game calls the "fire" routine, and he fires a missile even though he has no crossbow.

Where I come from, we call that a bug.

OK, so the "fire" routine checks for a crossbow as well, and returns silently if the player has none. That's still not good enough, because then the player presses "6" to walk away from the monster, and nothing happens. Tk has called "fire" rather than "moveplayer", and so the player doesn't move. So what do we do now?

We could modify "fire" so that if the player has no crossbow, the player moves instead--which is such a dirty solution I'm ashamed to even have mentioned it. The right thing to do is somehow break the sequence: to do something so that Tk forgets that "f" was pressed, and is no longer looking for the direction key that follows the "f". Then when the player types "6" it's seen as a movement key, not as a direction in which to fire a missile.

There are two ways to do that that I've come up with, and the second is the obscure point of Tk programming I mentioned up top. The hard way is to add the "fire" bindings only when the user gets the crossbow, and remove them if he loses it. But there's an easier way. Tk's event command can generate mouse and keyboard events, just as though they came from the user. All I need to do is have the "fire_intro" routine generate a bogus (but harmless) keystroke, thus breaking the key sequence. The space character has no particular meaning to Ramble and has no special keybinding, so I'll use that. Here's the magic code:

event generate . <Key-space>

And that does the trick!

Posted by Will Duquette at 03:41 PM | Comments(0)

January 08, 2005

The Ramble Chronicles: Ramble 0.1

Just for fun, I've made my latest version of Ramble available for download at the new Ramble Home Page. It's available as a Mac OS X application, a Windows executable, and for the die-hard Tclers in the audience, a starkit. If you decide to take a look at it, be aware that it's still in its infancy, and isn't much of a game yet; it's more a preview of coming attractions. The game begins immediately when you start the application; it ends when you die or win the game. In either case, you'll need to quit the game and start over in order to play again.

Ramble 0.1 consists of two levels, a town level and a dungeon level. Here's the town level:

As you can see, the look owes a lot to the original Ultima series of games. We've got some shops (which sell absolutely nothing at the moment, though you can talk to the shopkeepers), a library (walk on the question marks to learn how to play the game) and a King; talk to the King to learn your quest. Then there's the dungeon:

The dungeon is a randomly generated maze with a bunch of chests, one of which contains the treasure you need to find to complete your quest. Unfortunately, it's also got a bunch of skeletons who are bent on killing you. You better hope you've acquired the crossbow before you go down there....

Some specifics of the current game model:

Visibility: The player has complete visibility of each level.

Creature Model: Most tile-based games--in fact, most RPGs--define the player and the monsters using a set of statistics ("stats") like Strength, Intelligence, and so forth; the granddaddy of all such schemes is, of course, the original Dungeons & Dragons rules. At present, Ramble has no such model.

Combat Model: The combat model is a simple as can be. If a skeleton catches the player, the player dies and the game's over. The player can acquire a crossbow; one shot kills any skeleton. I could get a little hifalutin here and say that each creature has one hitpoint and each attack is guaranteed to do one hitpoint of damage, but in fact the model isn't even that sophisticated--there's no notion of damage as yet.

Creature Movement: There are currently three kinds of creature in the game: the King, the shopkeepers, and the skeletons. The King doesn't move; he just waits to be talked to.

The skeletons get to move each time the player does. The algorithm is simple: the skeleton computes the distance to the player from each adjacent open tile, and moves to the tile with the minimum distance. If that tile contains the player, the player dies. Note that the skeleton will always move to an adjacent tile, even if that moves it farther away from the player--that seems counter-intuitive, but in fact it gives the skeleton a limited ability to get out of dead-ends that's surprisingly effective.

The shopkeepers get to move each time the player does, though they are confined to the space behind the counters in their respective shops. The algorithm is the same as for the skeletons, except that the shopkeeper won't ever move away from the player. This has the neat effect that the shopkeeper will follow the player up and down the counter, remaining always directly opposite, an effect I've stolen shamelessly from Ultima.

Player Inventory: There is none, really. There are only two objects the player can have, the crossbow and the treasure, and both are represented as Boolean flags. When the player is given the crossbow, for example, his crossbow flag is set; this enables the "fire" command, so he can now fire missiles. At present, the player has an unlimited supply of missiles. There's no way to drop an object.

So ramble is still incredibly limited. On the other hand, I've come a long way since my initial prototype. Here are some of the technical problems I've solved:

Displaying a graphical map of tiles: I got most of the bitmaps I'm using from a freeware set called Anthony's Icons (you can Google for it, if you care); they are clearly patterned after the original Ultima set. I've added some more of my own. If I were an artist, I'd use beautifully drawn GIF files instead; but I'm not.

Terrain Model: I've defined a number of terrain types (grass, tile floor, brick wall, and so forth), each of which has its own bitmap (or "glyph", as I call it in the code), as well as other attributes, like whether you can walk over it and whether you can see through it.

Feature Model: A feature is something that sits in a tile with which the player can interact. Ladders, chests, and "help spots" are all features. A feature has a glyph, a description, and handlers for different interactions. For example, when the player steps onto a tile containing a ladder feature, the "walkon" handler logs a message telling how to use the ladder.

Creature Model: A creature is (naturally) a person, a monster, an animal, or so forth. Creatures are a little like mobile features: they have a glyph, a description, and handlers for different interactions. In particular, each creature type has a "move" handler, which implements the creature's movement algorithm, and a "transact" handler, which allows the player to talk to the creature (not that skeletons say anything of interest).

Minimal Level Model: Since the game has two levels I obviously have a level model of some kind, but it's pretty simple at the moment. There's a lot more to do.

I'll probably have more to say about most of these things in future essays.

Posted by Will Duquette at 11:07 AM | Comments(0)

January 07, 2005

Rambling About

I spent the evening working on Ramble instead of writing about Ramble, and now I find I'm out of time. But I'm hoping to put the initial (very, very simple) version on-line sometime in the next couple of days. Hold your breath!

Posted by Will Duquette at 10:04 PM | Comments(0)

January 06, 2005

What Big Eyes You Have, Grandma!

Via Lynn Sislo I find this truly bizarre gallery of images--one artist's conception of the skeletal structure of a variety of well-known cartoon characters. Charlie Brown is here, as is Marvin the Martian, Tweety Bird, Fred Flintstone, and a number of others; but the real eye-openers are the Powerpuff Girls. This must be seen to be believed; you simply can't imagine it on your own.

Posted by Will Duquette at 08:59 PM | Comments(0)

Diamond Dust, by Peter Lovesey

On our Peter Lovesey page, I give him the tagline "diamonds, not so rough"; I sometimes wonder if "red herring monger" would be more precise. But be that as it may.

I first encountered Lovesey's books shortly before this book came out, and I confess it stopped me in my tracks; it's only recently that I've begun reading his Peter Diamond novels again. And all this without my even reading it, mind you; just reading the flyleaf was enough to put me off. Why? In this book, Peter Diamond loses his beloved wife Steph. Although she hasn't had a major part in any of the books, she's had a persistent and important role in all of them--she's Diamond's anchor, his prop and stay, the thing that keeps him from going nuts, his island of peace. And in this book, she dies...and Diamond has to deal with it.

I hate that.

Having read the flyleaf I put the book back on the shelf and said, "Well, I think I'll wait for the paperback of this one...and maybe even longer than that." I hadn't even read enough of the flyleaf to find out how Steph dies; just the bare fact was sufficient.

And for quite a while, the only Peter Diamond books I saw on the shelves were this one and some I already had. About a month ago, though, I found two others nestled on the bookstore shelf next to this one, and decided that it was time to bite the bullet and get on with it, especially since I could begin with the other two books. I didn't know at the time whether they were written before or after Diamond Dust, and it didn't matter; it was all insulation.

You've perhaps noticed that I haven't said much about what's in the book, or how Steph dies, and I'm not going to. I'll just say that parts of it were indeed painful to read; Steph's death is a bad thing, bad for Diamond, and bad for us, and knowing that, I'd guess, Lovesey doesn't rub our noses in it. He portrays Diamond's grief simply and poignantly without wallowing in it.

The mystery that follows is as intricate and surprising as anything else of Lovesey's I've read, with red herrings galore, and I found the ending perfectly satisfying--which was yet another surprise.

But I rather suspect that if I'd tried to read it when it first came out, I'd have had more trouble. Living with the fact of Steph's death for a couple of years lent me some needed distance.

It might seem odd that I'd get so worked up over a mystery series, and indeed I've probably overstated my dismay. It wasn't heartbreak that caused me to put this book back on the shelf a couple of years ago, it was the wish to spare myself an unpleasant read. But either way, it's a tribute to Lovesey's skill.

Posted by Will Duquette at 08:41 PM | Comments(0)

January 05, 2005

The Summons, by Peter Lovesey

The Summons, by Peter Lovesey

In the first Peter Diamond mystery, The Last Detective, Diamond ends the book in grand style by resigning from the Bath CID. He spends a fair amount of time unemployed and underemployed until this book, when the Bath CID needs him again. It seems that a guy Diamond put away for murder has escaped from prison and kidnapped the Chief Constable's daughter, and the only one he'll talk to is Diamond himself. He claims to be innocent of the murder, and he wants Diamond to prove it. The CID is interested only in capturing the guy before the Chief Constable's daughter is hurt, and they want Diamond to sweet-talk him; they have no intention of re-opening the case.

But Diamond's an honest man; that's why the escapee is willing to work with him. And though it seemed like an open-and-shut case at the time, and still seems like one now, if Diamond says he'll look into it, look into it he will, whatever the top brass say. And as he's still a civilian, they can't stop him....

The average Lovesey novel has some delightful twists, turns, and surprises, and this one is no exception; though, honestly, I'd kind of like to see a novel in which Peter Diamond isn't going it mostly alone.

Posted by Will Duquette at 06:27 PM | Comments(0)

January 04, 2005

The Ramble Chronicles: On Visibility

Visibility: What can the player see, and when can he see it?

The simplest answer is everything, all the time--what I'll call complete visibility. The entire world (or, at least, the entire level) is visible all at once. You can see your character, all terrain features, traps, treasures, monsters, etc., et al. This is dead simple to implement (provided the world is small enough to fit on the screen all at once), but generally speaking it's boring. A big part of the fun of playing a tile-based game is exploring the game world, and that requires limiting visiblity.

So what alternatives are there? The simplest is to use a limited viewport. For example, put your character at the center of an 11*11 square of tiles, but let him see absolutely everything within that square. You'll be able to see the skeleton that's lurking on the other side of that wall, waiting to attack you if you go around the corner...but unless you attack the skeleton and go down the path behind its hiding place, you'll never know that just beyond the edge of the viewport, just six tiles away, there's a room just full of treasure.

A limited viewport can be quite effective, and the technique has been used in lots and lots of games; I first encountered it in Ultima, but Final Fantasy I also uses it to good effect. Its primary advantage, as with complete visibility, is that it's cheap. You simply display the tiles around the character, and you're done. The disadvantage is that you never feel like you get the big picture--because you never get the big picture.

A game can't be said to use a limited viewport just because you can only see part of the world on the screen; it's essential that the viewport be used to hide things that are really quite close by from the player's point of view. Angband, for example, only shows you part of the level at once--but that's only because the level is bigger than will fit on the screen at once. If you've got a big enough screen, you can resize the Angband window until everything fits.

The next alternative is line-of-sight visibility. Some tiles are opaque (like walls) and block line-of-sight, and some are not (like floor tiles). In its most extreme form, the player can see only tiles to which he has an unblocked line-of-sight; all other tiles appear black. One correspondent sent me a link to a classic Macintosh game called TaskMaker that combines strict line-of-sight visibility with a limited viewport; here are three consecutive screenshots of the character walking by a pillar:

I confess that I find it disconcerting to have all that black flashing around as I walk; and if TaskMaker didn't use a limited viewport it would be even worse. Also, by the third frame I've seen every tile in the room, and I know perfectly well what they all look like. Granted, a monster could creep into my blind spot, but failing that I'd be really surprised if the tiles had changed when next I looked at them.

Let it be said: Ramble won't use strict line-of-sight.

Angband uses a scheme I'll call persistent line-of-sight (though it has a wrinkle I'm going to ignore for a moment).
In this mode, your character can initially see only those tiles to which he has an unblocked line of sight. But as he moves around, permanent terrain features are remembered, as are any objects that are lying around. Monsters remain volatile--you can only see monsters when they are in direct view. I like this mode; you have to explore, and (since there's no limited viewport) you end up getting to see a lot of the world at once. And there are no awful sweeping black triangles as you walk around. And you can do some fun things like detection spells (have objects in the black unexplored areas magically appear) and ESP (the player sees all monsters within a certain radius, whether they are in line-of-sight or not) and clairvoyance (the player sees everything within a certain radius). But there are some implications.

The first is a minor philosophical problem. Consider the map below, which I typed in by hand but which could easily have been part of a game of Angband:

#########
#....@..#
#.#######
#..!.....
#########

Our hero (the "@") has just walked into a dead-end, passing a potion (the "!") on the way. He knows that the wall below the potion is there because he saw it as he walked by; and he knows the potion is still there because potions are inanimate objects and don't walk around by themselves. But what if some monster sneaks in and takes the potion while he's not looking? In Angband, the potion (the "!") will disappear as soon as the monster takes it. This effectively gives the player a mild form of ESP--he can easily tell when objects he'd previously seen are moved. In practice this turns out to be less disconcerting than the alternatives: having objects vanish immediately when they are out-of-sight, or having moved objects vanish only when you come back to where you can see them.

Another implication is that you often can't see monsters until they are right on top of you, which can be a big deal. Ramble has precisely one monster at the moment, a skeleton; and if the skeleton touches your character, that game's over. There's no combat model yet, so the only way the player can avoid being killed by the skeleton is by avoiding the skeleton altogether. And that's very difficult to do if you can't see it. At present, consequently, Ramble gives the player complete visibility.

Finally, computing line of sight can be very costly, especially if the visible area is large. This is another advantage of persistent line-of-sight over strict line-of-sight. In strict line-of-sight you must compute the visibility of every tile in the viewport after each and every move the player makes. In persistent line-of-sight, you only need to compute visibility for tiles that haven't been seen yet, and for monsters; this is generally an easier problem. Moreover, it scales to the case where the viewport is large and the visible region within the viewport is also large: visibility is computed once for the terrain; after that, all you need to consider are the monsters.

As I hinted above, there's a wrinkle in Angband's implementation: the Dungeon generally isn't lit. You have to bring a light source with you, and different light sources give off different amounts of light. A torch will light up the tiles no more than one tile away from the character. A lamp will light up the tiles up to two tiles away from the character. In addition, rooms in the dungeon can be lighted or dark. In a room that's lighted, all of the tiles are already marked visible before you walk in. In a room that's dark, none of them are, and you must rely on your light-source. In general, you can only see monsters at a distance in a room that's lighted; otherwise, monsters outside your torchlight are invisible.

This has the effect of making the dungeon more mysterious and spooky; it also has the effect of limiting line-of-sight computations. You only need to compute visibility for tiles within the radius of torchlight, and for tiles that are lit permanently. The radius of torchlight effectively becomes a tiny viewport.

At present, as I said above, Ramble gives the player complete visibility. Ultimately, I'd like to implement persistent line-of-sight, possibly combined with a limited viewport (if necessary for speed). Whether I'll implement light or not, I don't know. But it's clear that I can't implement any kind of line-of-sight unless I either get rid of monsters or provide a combat model. Combat, however, is another topic.

Ramble is going to evolve slowly as I model and implement different bits, and might end up leaving a stream of distinct and separate games behind it as I work on particular techniques. More on that later.

Posted by Will Duquette at 07:01 PM | Comments(0)

Nerdlier Than Thou

OK. So I'm nerdlier than Ian Hamet. I'm a UNIX programmer, what did you expect?

I am nerdier than 78% of all people. Are you nerdier? Click here to find out!

Posted by Will Duquette at 09:40 AM | Comments(3)

January 03, 2005

Bloodhounds, by Peter Lovesey

In this book we find Peter Lovesey's irascible yet big-hearted detective, Peter Diamond, in an amusing yet silly book that's a cross between a police procedural and a puzzle mystery from the golden age of Christie, Allingham, and Marsh. It concerns a small literary group that meets periodically in the crypt of the church of St. Michael with St. Paul in the city of Bath to discuss murder mysteries--or, as they prefer to say, "crime fiction." The group's name is "The Bloodhounds of Bath", and its members are a delightful group of eccentrics.

There's the snobbish and very proper Miss Chilmark, whose ancestors have lived in the vicinity of Bath for five-hundred years, and who believes that Eco's The Name of the Rose is the pinnacle of the art. There's Milo, an older bachelor of the tweedy variety, who delights in the puzzle mystery. There's Jessica the art gallery owner, who specializes in female investigators. There's Rupert the repulsive, a decayed intellectual who delights in stirring things up and claims the group should read nothing but true crime. There's quiet Sid, a John Dickson Carr fan, who suffers from painful shyness and comes to the group on the advice of his therapist. And finally there's Shirley-Ann, newcomer to the group and to Bath, who has read almost every mystery ever published and has them all on-tap in her head.

And then a famous stamp is stolen from a Bath museum...and then reappears under mysterious circumstances. Clearly, it's time for the Bloodhounds to figure whodunnit. And then one of the Bloodhounds is murdered--and the body is found in a locked room. There's only one key, and its owner has an iron-clad alibi--he was at the police station throughout the time in question, and he had the key with him.

And in steps Peter Diamond, in best police-procedural fashion, to catch the murderer, and the conventions begin to run together a bit.... And if you think Lovesey had a lot of fun blending the two styles together, you're right. In fact, I'd been a little disappointed by the ending; but now that I think about it, given the problem Lovesey set himself the murderer could have been no one else. Nice, very nice.

Posted by Will Duquette at 06:53 PM | Comments(0)

January 02, 2005

The Ramble Chronicles: Matrix Coordinates

I want to talk about random maze generation, but I've got some more infrastructure to get out of the way first. This essay is about the Tcl implementation of Ramble rather than the game design, so pass on by if the code doesn't interest you.

As I noted in the Efficient Matrices chapter of The Ramble Chronicles, the size of a matrix is usually denoted m*n, and the coordinates are i and j where 1 <= i <= m and 1 <= j <= n. The nuisance about coordinates is that about half the time you want to deal with i and j as a pair (i.e., when saving a particular pair of coordinates for later) and the other half the time you want to deal with them individually (i.e., when doing computations). The normal way to store a pair of coordinates is as a list:

set i 4
set j 2
set pair [list $i $j]

Tcl's lset and lindex commands nicely support both forms; given the above assignments, for example, the following two statements are identical:

set a [lindex $matrix $i $j]
set a [lindex $matrix $pair]

Nevertheless, no matter which way you choose to store your coordinates, you're going to find yourself wanting to convert them to the other form on a regular basis--if only because writing Tcl commands to be as forgiving as lindex and lset is a royal pain. Hence, I define the following infrastructure: the i, j, and ij commands:

set pair [ij 4 5]
set i [i $pair]
set j [j $pair

These are implemented simply, as follows:

# Create an i,j pair
proc ij {i j} { list $i $j }

# Get i from an i,j pair
proc i {ij} { lindex $ij 0 }

# Get j from an i,j pair
proc j {ij} { lindex $ij 1 }

Trivial, you might say; but they are more expressive (and more concise) than the list and lindex calls they replace, especially when used in complex expressions.

Posted by Will Duquette at 07:36 PM | Comments(0)

January 01, 2005

The Ramble Chronicles: Randomness

One thing you need in most games is a source of randomness. In Tcl, random numbers are provided by the expr command's rand() function; but rand() can be made considerably more convenient by some judicious wrapping. Again, this is a Tcl-oriented essay rather than a game design essay; if the details don't interest you, pass on by.

The rand() function returns a floating-point value between 0 and 1, which is handy if you're working with raw probability figures. For many applications, though, what you're really looking for is an integer in some range. Here's a function that returns a random integer between $min and $max, inclusive:

proc rand {min max} {
    # Determine the number of possible values.
    set numValues [expr {$max - $min + 1}]

    # Get a random integer from 0 to numValues - 1
    set randInt [expr {int($numValues*rand())}]

    # Return a number from min to max
    return [expr {$min + $randInt}]
}

# Roll a six-sided die
puts "You rolled [rand 1 6]"

rand covers many of the cases I'm interested in; however, there's a particular application of rand that deserves further elaboration: picking an element randomly from a list. For example, suppose your game includes a creature that says something different every time the player talks to it. Provide the creature with a list of statements, and pick one randomly using pickfrom:

proc pickfrom {list} {
    set i [rand 0 [expr {[llength $list] - 1}]]
    set result [lindex $list $i]
    return $result
}

puts "The parrot said [pickfrom {
    {Polly wants a cracker!}
    {Shiver me timbers!}
    {Squawk!}
    {The treasure is hidden under the captain's pillow!}
}]" 

Sometimes you want to remove the selected element from the list, so that it can't be picked again. I use this a lot when randomly placing features on a newly created map. First I build up a list of open tiles, i.e., spots where I can legally put a chest, or a monster, or the player. Then I use takefrom to randomly choose tiles from the list. Because chosen tiles are removed from the list, I don't need to worry about putting two things in the same spot. Here's what takefrom looks like. Note that instead of passing a list, I'm passing a variable that contains a list; that's necessary so that takefrom can update the variable's value.

proc takefrom {listvar} {
    upvar $listvar list
    set i [rand 0 [expr {[llength $list] - 1}]]
    set result [lindex $list $i]
    set list [lreplace $list $i $i]
    return $result
}

set openlist [getopentiles $map]

set location [takefrom openlist]

puts "The player starts at $location!"

Between them, these three commands provide almost all of the randomness I need for Ramble...so far, anyway.

Posted by Will Duquette at 01:25 PM | Comments(0)