Category: Programming

Quill v0.4.0

For those who are interested, I released v0.4.0 of Quill this morning. You can find the release notes at the link.

George’s Saga: Angband-Style Combat

George As I promised, I’m now going to go into some detail about how combat works in Angband. Those of you who are not game geeks can feel free to move along.

In Angband, combat is based on skill and armor class (AC). Every mobile (by which I mean both the player character and the monsters) has an armor class; for monsters it is a fixed number, and for the PC it’s a number based on the armor the PC is wearing and many other factors, including the PC’s dexterity. The higher your AC, the harder you are to hit.

Similarly, the higher your attack skill, the easier it is to hit your opponent. Each PC has an attack skill based on his race, class, and level, and his equipment and circumstances can increase or decrease his “to hit” modifier. The basic equation is


A level 2 human warrior has a base attack skill of 68, and gets 4.5 more points for each level he attains. He might have an enchanted sword that gives him a to-hit bonus of +1. His attack skill is then

	K = 68 + 4.5*2 + 3*1 = 80

Thus, the PC’s skill goes up as he gains experience (and hence levels), and as he uses better and better equipment. There are also magic spells that will increase his “to hit” modifier, and other circumstances (such as wearing armor that’s too heavy for his strength) that will decrease it.

A monster’s skill level is similar; for normal physical attacks it’s simply

	K = 60 + 3*LEVEL

Thus, a level 5 monster will have an attack skill of 75. However, it gets a little more complicated because monsters have a wide variety of kinds of attack in Angband. Some monsters are poisonous, and will crawl on you to poison you. Others breathe fire, or spray acid, or such like. The base skill differs for each of these kinds of attack, and the level bonus might differ as well (I don’t recall, offhand). At the moment, the monsters in George’s Saga only have physical attacks.

Okay, so we have attack skills and armor classes. Let’s bring them together.

The probability P of a mobile with skill K hitting a mobile with armor class AC is

	P = 100 * (K - 0.75AC)/K

(It’s a little more complicated than this, actually; the code needs to handle the case where K is less than or equal to 0.) I don’t know how they came up with that particular equation; but it allows me to roll percentile dice for any attacker/defender pair, and if the roll is less than or equal to P, it’s a hit.

Well, actually…all rolls of 5% or less are deemed to be hits, and all rolls of 95% or more are deemed to be misses. (But that’s by the way, except that when the roll exceeds 95% I get to animate a “Swoosh” over the defender.)

If the attacker hits the defender, then he rolls for damage, and the damage is immediately applied to the defender. The armor doesn’t absorb it.

This system has many advantages over the GURPS Lite system, at least for my purposes.

  • It’s simpler, in that combat is resolved after one roll: the attacker hits or he doesn’t.
  • If the adversaries are of similar levels, the attacker will hit and do damage more often than not. There’s no frustration because you can’t hit the monster that’s attacking you.
  • If the defender is of a much higher level than the attacker, the attacker won’t be able to hit nearly as often (and will probably be toast in short order). This is appropriate.
  • Attack skill increases in small increments with levels gained and with “to hit” bonuses from equipment.
  • Armor class similarly increases in small increments with bonuses from equipment.

For example, a level 5 monster can hit a PC with no armor 95% of the time. Once the PC gets his armor class up to 8, the monster can hit 90% of the time; and when the PC’s armor class is 50 the monster can only hit 50% of the time. That might seem like a lot; a PC with AC=50 is probably at level 20 or higher. How come the monster can hit him so often?

It turns out that it’s fine. The point is that as the player’s AC increases the monster will do incrementally less damage, because it hits less often. And then, there’s a factor I’ve left out.

In Angband, unlike GURPS, a PC’s hit points go up fairly dramatically with level. A level 1 character might have 10 or 12 hit points; a level 25 character might have over 100 hit points. What’s going on here, in my view, is not that the level 25 character has ten times more life. Rather, it’s that the damage he takes is less significant. One point of damage for him is a minor cut or scrape, rather than a serious wound. In short, a mobile’s maximum number of hit points is a proxy for his skill at defense; the higher it is, the greater the number of small hits he can take. So the level 5 monster hits the level 25 PC less often, and the times the monster does hit are less important.

This is the scheme I’ve adopted in George’s Saga, and it appears to be working quite nicely.

George’s Saga: The Angband Connection

George Last time I wrote about how the combat system in GURPS Lite didn’t have the right characteristics for a computer RPG, or at least not for the kind of RPG I have in mind. GURPS Lite is a game in which hit points are limited, each successful hit on an opponent is a major event (and therefore successful hits are rare), and each skill increment makes a big difference (and therefore the total number of skill increments is small).

By contrast, I need a combat system in which there is a wide range of skill levels with small increments, so that a player character can grow slowly and but steadily in skill over the course of the game—and so that the monsters a PC faces can do the same. A table-top RPG might have these characteristics, but there’s no particular reason why it needs to; and so continue to look at other table-top RPGs seemed counter-productive. And as I’d noted earlier, computer RPGs are seldom well-documented, at least in my experience. To find one that is means turning to a free or open-source game; and of those the one I know best is Angband.

Angband is a massive dungeon crawl with roots that go back to the early 1980’s. I first played Angband’s immediate predecessor, Moria, on the college VAX-11/780 around 1983. (I killed an Icky White Thing, and then died of starvation.) Since then I’ve spent countless hours playing Angband or one its variants.

Classic Angband works like this. You begin in a small town, with a variety of shops and a dungeon entrance. Your mission is to work your way down to level 100, there to slay the evil Morgoth. This is extremely difficult to do, and almost never happens. You begin by designing your character, who belongs to a particular race and has a particular class; and then you begin your expeditions into the dungeon. There are many consumables that you need to survive, notably food and torches, many magic items, and of course weapons and armor. You start with basic equipment; everything else you need to find in the dungeon or buy in one of the shops.

The graphics in Angband are extremely simple, but the monster behaviors and the underlying combat model are rather complex. And it so happens that there are spoiler files available for download that go into a surprising amount of detail about how it all works. In fact, they go into much more detail than I’d realized. And it so happens that Angband has exactly the characteristics that I’m looking for. Next time, I’ll talk about them.

George’s Saga: Big Increments vs. Little Increments

George When last we spoke, I was working out how to do combat in George’s Saga, using GURPS Lite as my inspiration. Which is one reason it’s been so long since we last spoke.

Since then, I’ve come face to face with a number of basic differences between table-top RPGs and computer RPGs, and the main one is that table-top RPGs are about big increments and computer RPGs are about little increments. I’ll explain that, but first a few words about my experience using GURPS rules for combat in George’s Saga.

Verily, they sucketh.

Here’s how a round of combat might go in GURPS, insofar as I actually understand it.

Our hero, Akallabeth the Bold, wields a mean broadsword, with which he has a skill of 14. His opponent, Ulthar the Underhanded, has a basic dodge skill of 12, to which his trusty shield adds another point of defense, making 13 in all. Akallabeth swings at Ulthar, rolling 3D6 to see if he hits. He gets 11, less than 14, so he hits. We roll damage, and Ulthar takes it in the shorts.

No, wait a minute. He doesn’t. Ulthar makes his defense roll, and gets 7 on 3D6, which is less than 13. He managed to dodge the Akallabeth’s attack. Akallabeth used his sword skillfully, but Ulthar was just too quick.

Now it’s Ulthar’s turn. He comes in from below with his Dagger of Stabbing, with which he has a nearly super-human skill of 17. He rolls a 10; he hits. Akallabeth is bold, but none-too-quick on his feet; he rolls 16 against his defense skill of 7. He fails to evade Ulthar’s hit. Ulthar rolls 3 points of damage (I’ll spare you the details), and now Akallabeth takes it in the shorts!

No, wait a minute; he doesn’t. Ulthar was aiming at his chest, and Akallabeth is wearing his Corselet of Kevlar…which can absorb 4 points of damage. Net result: 0.

Now, in a table-top RPG this might be a thrilling moment. Each player got to roll four times, and feels that he’s the master of his fate. Three points of damage is a huge amount; Ulthar would have been happy to do one point of damage. Each player has lots of choices of how to attack and defend, and these choices, at the GM’s discretion, can make a huge difference; if Ulthar had but known that Akallabeth was wearing his Boots of Achilles, he might have stabbed down instead of up, and that would have made all the difference.

I’ll pass over the next four rounds of combat in which Ulthar is knocked down, stepped on, and ultimately flees the battlefield nursing a hangnail, leaving Akallabeth with one point of damage and all the glory.

Here’s what this style of combat looks like when I put it into my computer game.

Akallabeth swings at Ulthar. He misses.

Ulthar swings at Akallabeth. He misses.

Akallabeth swings at Ulthar. He misses.

Ulthar swings at Akallabeth. He does one point of damage.

Akallabeth swings at Ulthar. He does two points of damage.

Ulthar swings at Akallabeth. He misses.

Akallabeth swings at Ulthar. He misses.

And so on and so forth. Kind of lacks that old dramatic tension.

And that’s why computer RPGs are all about small increments. In GURPS, a powerful character might have 18 or 20 hit points. Losing one point is a big deal. Losing 10 is a catastrophe. Skills runs from 1 to 20, averaging around 10 or 11. Gaining 2 points of attack skill is huge. One would expect GURPS characters to become more skilled over time, but only very slowly; and there are hundreds of skills, each of which might be of use in a table-top scenario. But there’s so much else going on, and so much of it is going on only in the fevered imaginations of the GM and players, that this slow rate of progression doesn’t harm the play.

A computer RPG is different. Battles need to progress. You need to know whether you’re stronger than the monster or the monster is stronger than you, and you’d like to find out before he kills you. You can only judge this by the respective rates at which you each lose hit points…and that means you need to be able to hit and do damage with some frequency. If you’re only connecting every four or fifth stroke, it had better be because the monster is a lot more powerful than you are, and the monster had better be having you for lunch.

And then, your character needs to grow in strength throughout the duration of the game. Every time you level up you should gain strength. Each slight improvement in your weaponry, or your armor, or your various magical talismans should give you an edge. And this growth needs to be gradual; if it’s too rapid, the game will perforce be a short one.

Similarly, the monsters need to grow in strength, slowly and gradually. Of course, your party doesn’t grow in strength at quite the same rate as the monsters: sometimes it’s slower, and sometimes it’s faster, sometimes you’re enjoying a walk in the park, and sometimes you’re having to fight every inch of the way. That leads to a kind of rising action that carries you along to the end.

So…GURPS combat was not a success for me. GURPS is an interesting system, and I hope to mine it for a number of ideas, but I rapidly discovered that I needed something else.

George’s Saga: Armor

George So it’s an RPG with hand-to-hand combat against vicious Ladybugs and Cosmic Horrors and such-like. It’s a tough world out there; you have to have armor.

Now, in a typical computer RPG (AKA a CRPG) there are different types of damage that armor can protect against: physical damage, natch, but also acid damage, fire damage, and so forth, all of the usual elemental folderol, plus maybe some peculiar additions of my own. (In homage to Doug Piranha, I’m thinking I might have to add rhetorical damage. Ahem.) And in CRPGs, it’s typical that a player character (PC) can wear a number of articles of armor at the same time: body armor, helmet, boots, shield, and so forth. The number of different kinds depends on the RPG, but sometimes it can be quite stunningly high. George’s Saga currently supports the four types listed, though the list might prove to vary by character class. (The Friar’s shield might prove to be remarkably…book-shaped. Ahem.) And then, the effect of the various items of armor is cumulative: all of the armor the PC is wearing combines to block any hit.

So my notion was that each article of armor would block some percentage of each kind of damage, i.e., 33% of the physical damage but only 20% of the acid damage. Similarly, monsters would do damage of one or all types: a Fire Roach’s bite might do 5 to 10 points of physical damage along with 5 points of fire damage. When the Fire Roach bites the George, doing (as it turns out) 9 points of physical damage and 5 points of fire damage, George’s armor blocks 33% of the physical damage, living 6 points, and 20% of the fire damage, living 4 points, and so George takes 10 points total. Conceivably there could be other effects as well. George might be stunned by the damage, or burned by the fire such that he takes damage each turn until the burn heals. (Pokémon! It’s all in Pokémon! What do they teach in these schools?)

This scheme turns out to be somewhat problematic. When George, having gained 10 or 20 levels and having gotten the Truly Amazing Unobtainium Armor with the patented Asbestor Inner Lining that blocks 60% of physical damage and all fire damage, returns to the Fire Roach’s lair…the Fire Roach’s 10 point physical attack is still going to do 4 points of damage. It sure seems like George ought to be able to wade through the Fire Roach’s lair with impunity.

And then, why should armor that protects against 10% of the damage of a Fire Roach’s bite also protect against 10% of the physical damage inflicted by the Inflatable Cosmic Horror Juggernaut of Doom, which can do a whopping 500 points of damage with the lash of a single inflatable tentacle? It doesn’t pass the laugh test.

So how does armor work in GURPS Lite?

First, a piece of armor protects the part of the body it’s on. Helmets protect your head, breastplates your body. If your opponent strikes your head, your helmet matters and your breastplate doesn’t. Second, armor has a damage reduction factor (DR), which is the number of damage points absorbed by the armor. If your breastplate has a DR of 6 (appropriate for plate mail), then it will block six points of damage.

This highlights a significant difference between table top RPGs and CRPGs. In GURPS really amazingly good body armor has a DR of 12 points. Just twelve. There are no epic boss battles where you’ve got to be able to absorb or block thousands of points of damage in this scheme.

Shields are also different than the usual CRPG fair. In CRPGs, shields are usually just another kind of armor, interestingly mostly because if you use a shield you can’t use a two-handed weapon. In GURPS Lite, shields aren’t armor in the sense given above. Instead, shields help you to avoid being hit to begin with. That’s an interesting notion, and one I intend to think about—but that’s a combat detail, while I’ll have to come back to later.

So what should armor look like in George’s Saga?

First, armor effects will be cumulative for all armor worn; monsters simply aren’t going to be targeting particular body parts.

Second, some armor should clearly affect your evasiveness, i.e., whether you get hit at all. Shields are good candidate for providing this as a usual thing.

Third, armor should probably block damage points directly, rather than as a percentage. Thus, a given degree of armor protects you against a certain subset of the monsters in the game, leaves you somewhat vulnerable to others, and hardly protected at all against others.

Fourth, a combination of the effects might be useful: this armor protects against 20 points of physical damage plus 50% of the acid damage (because it blocks 50% of the acid). In short, I can use one scheme for some kinds of damage, plus another for other kinds. I like that.

George’s Saga: RPG Basics (UPDATED)

George So when you’re writing RPG software, eventually you need an RPG to base it on. What I mean by that is, you need a model of characters that includes basic statistics, skills, combat, damage, and the like, and how they all work together.

I’ve got a very simplistic RPG at the moment. Characters have “life points”; they can take damage, and if their life points drop to zero they die. They can wield weapons; the amount of damage a character can inflict in combat depends only on his weapon. They can wear armor, which absorbs a percentage of the damage done to them. This seemed like a neat idea when I first came up with it, and then I realized that a powerful character with lots of armor would still take damage from a cub scout with a pen-knife. Of course, they are no powerful characters, because I’ve got no notion of leveling up.

As you see, It’s easy to put together something, you should pardon the expression, half-assed. It’s less easy to put together something that works, and so great minds (and mine too!) look to see what others have done. And here’s where there’s a problem: the models underlying computer RPGs are often obscure. They’ll tell you a certain amount about the stats are, enough so that you can customize your character as you level up…but they won’t tell you what the stats of the monsters are, or just how all of the stats are used in combat and other activities. It’s possible to reverse engineer some of this, some of the time, but ugh! This is supposed to be fun.

That leaves looking at table-top RPGs for inspiration. That’s also a problem, because table-top RPGs don’t really translate well to the computer world. They assume lots of discretion and intelligence on the part of the GM (computers have none), and allow for a vast range of choices on the part of the players, many of which don’t translate well to the GUI world, and would be tedious as all get out if they did. But at least they are well-documented: they have to be, or people can’t play them.

So I asked Tom McDonald, Games Maven, for advice. He suggested I look at a number of freely available RPG rules:

to which I added Legend, a set of rules I downloaded a year or so ago and never did anything with.

The d20 System is basically a set of rules abstracted from Dungeons&Dragons by the owners of D&D, and made free to download and use. It is Very Complete. It is also Very Complicated. And some of the things I’m most interested (like how to put together a character and level him up) were judged to be Proprietary and Left Out, so far as I can tell. There is much to be learned here, but not World Enough and Time to learn it given my limited resources.

The Saga rules are defined by a short rule book (about 30 pages) which I found to be rather un-succinct. Characters have skills, and assets (which doesn’t mean what you think it means), and traits, and I found numbers and concise definitions to be scarce on the ground. I’m not saying that what I need isn’t here; I’m saying I had trouble finding it.

Legend looks more interesting, but the rule book is much longer (almost 200 pages); plus, it’s based on a specific fantasy milieu. I might be able to pull what I need out of it, but right now I’m looking for quick-and-dirty.

And so I’m looking hard at GURPS Lite. It’s short (32 pages), and heavily focussed on the mechanics: what are the stats? what effect do they have? What die rolls are used, and what do they mean? How do you get critical hits? And what does that mean? How does armor work? It’s all here. More than that: GURPS characters are point-based: the GM gives you a certain number of points, and you pick the set of stats and skills that you like, within your point budget. This gives me a path to allow the user to define his own characters; and even if the characters start with a fixed set of stats, it gives me a leveling-up mechanism: give the player some points, and let him buy skills and stat improvements.

Whatever I implement will evolve, and will likely end up looking entirely different in the long run. (See below.) But this looks like it’ll get me off dead center with a minimum of effort, so there you are.

UPDATE: I’ve just glanced at Steve Jackson Games’ policy for use of their intellectual property, which GURPS is. I am not allowed to release a computer game based on GURPS unless I’m willing to get a license from SJG. As a would-be author, I find this to be completely reasonable. It does mean, however, that I will be looking at GURPS for inspiration rather than copying it slavishly, and that I will not be making George’s Saga available for download so long as it is distinctively GURP-ish. Just to be clear.

Running the Maze

This weekend I’ve been busy programming “mobiles”, creatures that can move around in the maze. In fact, I’ve implemented two mobiles, George and the roach. George is a simple guy; there’s a treasure chest, and he means to find it, provided that he doesn’t get killed doing so. The roach is even simpler: it has a magnetic attraction to George, and will always move closer to George if it can. It’s not smart about walls, though, so it often gets stuck in corners.

The game is simple. If the roach catches George, it wins. If George gets to the chest before the roach catches him, he wins. If George can’t get to the chest but the roach can’t get him, it’s a draw.

Early on in development, George got eaten a lot; he was smart about moving to the chest, but dumb about avoiding the roach. He’s smarter, now, but he still gets eaten sometimes. Here’s an animation that shows the action.

Dead george

More frequently, the roach just gets stuck somewhere rather distant from George. As I say, the roach is no genius.

Roach stuck

And once in a while, things get exciting.

George avoids

George is pretty smart. At each step, he figures out the best route to the chest that doesn’t get too close to the roach. If there is none, he’ll back away from the roach until he gets stuck. But if a route opens up, he’ll take it.

Mazes! With New Improved Tiles!

I originally started implementing maze algorithms in order to write a Rogue-like dungeon crawling game. And a dungeon should look like a dungeon, not a maze on a kid’s place mat at a family restaurant. So here’s a maze drawn with graphic tiles for stone walls and floors.


On Beyond Mazes

So you’ve got some code to produce mazes; what do you do next?

The obvious answer is to make use of it put some kind of game together. Trouble is, that means learning to use Java’s GUI toolkit to put together a real GUI application. Now, I’ve done a fair amount of GUI programming over the years, so the basic concepts are familiar, and I’ve even done some Java GUIs in the distant past. And there’s a detailed Java GUI tutorial available on the Java website. Easy, right?

Wrong…because games usually have much different user interaction models than your typical GUI application. Instead of relying on high-level components like buttons and menus, you have to “paint” most of the GUI yourself, which means using the low-level drawing primitives. But that’s no problem, because there’s a tutorial for the Java 2D Graphics library. Easy, right?

Still wrong, because there’s a gap between the two tutorials. The one tells you how to assemble components into a GUI, and the other tells you how to draw; what’s needed is how to build new components that can draw game sprites and such-like.

But Google is your friend; and I found a very nice Java 2D Games Tutorial that’s exactly what I need. At the end of the first four lessons I’ve got a simple “Defender” style game, in which you can move a spaceship up and down and shoot missiles at the alien ships coming in from the right. It works nicely, and covers a lot of the skills I’d need to do something fun with moving around in a maze. The same website has its own tutorials for the Java Swing GUI toolkit and Java 2D Graphics, though I’ve not looked at those yet.

Recursive Backtracking, Animated

A couple of weeks ago I described the recursive backtracking algorithm for generating mazes. Here’s an animation of the generation of a maze using recursive backtracking. As you can see, the maze begins as an array of unconnected little rooms, and grows room by room from one starting room.


WordPress Themes