D&D, Knowledge bases, and Prolog (oh, my!)
Posted by Jamis on September 29, 2006 @ 11:58 AM
I only get to tinker on my D&D DSL (as mentioned in 1d6 more reasons to love Ruby) a very little bit each week—maybe an hour or two, if I’m lucky. This means the project is moving ahead with excruciating slowness, but it also gives me plenty of time to think about the roadblocks I face.
My current obstacle is how best to represent dependencies. For instance, certain feats are only available to characters who have met specific prerequisites. Likewise, prestige classes have various lists of requirements, as do certain magic items. Additionally, the list of goal conditions that the user requests of the utility (“I want a mid-level male elven wizard who can cast Fireball”) is essentially a list of dependencies, too.
I did manage to implement a simple tree for representing some kinds of dependencies. It can take the prerequisites for the Archmage prestige class and apply them to a character, telling me not only whether the character is eligible for the class, but if not what the character still requires in order to become eligible. It’s pretty slick, though hardly something to brag about at this point.
The last couple of weeks have seen me pondering over how to represent another kind of dependency; that is, the parameterized dependency, and especially a chain of parameterized dependencies, where each link in the chain has the same parameter. Consider the case of the Greater Weapon Specialization feat. You have to select a weapon that you already have the Weapon Specialization and Greater Weapon Focus feats for. Weapon Specialization and Greater Weapon Focus both require the Weapon Focus feat, and Weapon Focus requires (among other things), Weapon Proficiency in the weapon of choice. The chain from Greater Weapon Specialization to weapon proficiency requires that each link reference the same weapon; weapon proficiency with a dagger won’t make you eligible for Weapon Focus with a longsword.
It’s one thing to evaluate this chain when the parameter is known. If I want to know if a character is eligible for Greater Weapon Specialization (Longsword), then I know that they have to have the requisite feats with the longsword as well. However, sometimes I need to ask “what feats is the character eligible for right now?” In that case, I can see that the character has weapon proficiency with a particular set of weapons, which implies that the character may be eligible for Weapon Focus in any of those weapons as well. Even trickier is the case of a prestige class that simply says “must have the Greater Weapon Specialization feat”, but doesn’t require a specific weapon. In that case, when I ask whether or not the character is eligibile for the prestige class, I basically have to use a variable for the feat’s parameter and then bind it, at the end, to the set of all weapons that the character might be able to use to eventually meet that requirement.
Ah, my head spins!
However, as I was pondering all of this, I kept getting a little ping from my university memories. Something I studied (and promptly forgot) 10 years ago was trying to tell me it was now relevant…
Enter automated theorem proving. As I begin researching and remembering the hours I spent on my homework and programming assignments, the concepts of Resolution and Unification came flooding home. I actually really enjoyed that class (which is probably why I remembered anything at all about it), even though I was sure I would never ever be doing anything with that knowledge.
For about 10 years, I was right. It was useless data stored in my brain.
But suddenly, it was relevant. How? Well, what my NPC generator needs to be is a knowledge base of all the facts and relationships between the various data in the system. Generating a character is (essentially) a query against the knowledge base—”has this character met this goal?” The knowledge base then needs to come back and either say “yes” (in which case the goal is met), or “no” (in which case the response includes the actions that need to be taken to help the character achieve the goal). Revelation!
With that in mind, I finally decided it was time to learn Prolog. It’s been one of those languages on my “huh, maybe I ought to look at that someday” list, but now it actually has relevance to something I want to accomplish. Mostly, I only want to use Prolog to test my ideas, and to prototype the NPC generator. I still love Ruby and think I could make a killer DSL for this in Ruby, but we’ll see what happens.
So far, all I’ve managed to do in Prolog is hard code a bunch of assertions that define a genealogy database, along with some rules that I can use to ask things like “who are the grandparents of this person”. It’s fun, and I’m looking forward to delving further in. I’m especially excited to see how far I can apply this to my original problem domain: random generation of gaming characters with some (potentially arbitrary) set of constraints.