Character Generation [technical/theoretical]

[JamisBuck]

Yah, I've been really quiet for a while now. But it's just because I've been thinking...alot. I should mention up front that this discussion will be heavily technical, and in fact I discourage non-programmers and casual programmers from reading this, since it may just confuse you (no offense intended, honestly--this confuses me).

I'm convinced that there has to be a way to (flexibly and efficiently) generate characters (PC's and NPC's) both randomly and semi-randomly (ie, with limited input from the user). I'm also convinced that all of the character generation software written to date is doing it wrong. This is not a reflection on the talent or effort that has been invested in these projects. PCGen, most notably, is an incredible piece of software that is far and away the most sophisticated program of its type. However, every program available (and I certainly include my own generators when I say this) suffers from at least one significant defect: when a new ability is released in some published source, it requires (or may require) the program itself to be modified to support the new feature.

Naturally, projects like PCGen (which have pretty much categorized the entire bulk of published material) have reached a point where almost anything that comes out can be incorporated without significant modification to the program. But they can't guarantee (and I'm not singling out PCGen here--no existing software can guarantee) that any feature that might be concieved by publisher or fan can be accomodated without modifying the program again.

Now, the bad news is, I don't have a solution. But I think that I may be on to one. I've been doing a lot of research, thinking, and modeling, and I believe that if we can understand the problem, we can build a system in which any new feature can be implemented simply by changing the data; the program itself need never change in response to published material.

I would like to get some experienced software engineers talking about this issue. I believe it will tend toward the theoretical, and in fact I hope it does, because if we start talking about implementation too soon, we'll lock our thinking into a limited set of solutions.

So, a few ground rules for this thread:

1. Try to keep things generic, at least initially. An ideal solution would apply to more than simply random character generation.
2. Limit implementation discussions to examples of what you mean by a particular approach. If possible, avoid discussing implementation issues at all.
3. Let's try to identify related issues that exist in other fields of software design, and see if we can apply existing solutions to this.
   [/list=1]
   
   For example (and this is where my thinking has led me to date): character generation can be considered an N-Body problem. Each character has a set of "n" attributes (the "bodies"). A change to one attribute may affect any number of other attributes.
   
   Now, N-Body problems have many different solutions--physics simulations use them all the time to model the affects of forces on a set of bodies. Perhaps we can apply some of these solutions to a character generator.
   
   I know that if we can identify the problem, we can find a solution. I've been trying to do it myself, but I think this could really benefit from a larger group applying their minds to it. Please, contribute! What other ways can we look at a character generator? Let's brainstorm and discuss, and see if we can't invent a better mousetrap!
   
   Thanks,
   
   Jamis

 

[PeterDonis]

I've been working for some time now (in my copious free time ) on a character generator that basically works as you described. Every attribute, stat, spell, power, object, etc. that a character can have is an "item" that can be of various types and have various data fields attached to it. Then you have a (potentially huge) table of effects that one item can have on others. The problem is that these effects can cascade indefinitely, so it's a highly non-trivial task to figure out how to ensure that, every time an item is added, dropped, or changed, you catch *every* possible repercussion of that change. If the system for defining such effects is sufficiently general, I believe the goal that you've stated can be met, but as I said, it's a highly non-trivial task (in the mathematician's sense of "non-trivial", where tasks that are "trivial" are those which require anything less than a Ph.D. to accomplish ).

Peter Donis

(edit) One other thought: the N-body problem actually has no analytical solutions for N greater than two in classical physics (in quantum physics you can argue that the N-body problem has no solutions even for N=0, since the vacuum is not necessarily a stable state). All the models out there for many-body problems are numerical approximations, which are not general enough to apply to all situations. Which indicates to me that we'll never come up with a single program that can handle every possible rules variation that the d20 community can dream up. But we can still try.

 

[Knightcrawler]

Hey Jamis,

I probably fall under the "casual programmer" group but I had a couple of ideas after I read your post. First off you have to decide if your creating it for just specifically D&D or a more generic character generator.

Even if your going for more of a generic character generator that can be used with many different system there are certain things that pretty much all RPG's have.

1, Attributes

2. Defense/AC

3. Skills

4. Attack Bonus

PCGen right now is moving many of the mechanics that are built into the actual program to the data files. My idea is to have some configurable variables built into the program and then have the data files themselves specifically define what those variables mean to that particular set of data files.

This of course will be much easier if the generator is for specifically D&D or even D20. But I would think that would work for almost any gaming system because of the basic similarities between them.

Well just my two cents. I'll go back to lurking now.

 

[Davin]

I'm convinced that there has to be a way to (flexibly and efficiently) generate characters (PC's and NPC's) both randomly and semi-randomly (ie, with limited input from the user).

Now that's an interesting idea! I wasn't quite sure where you were heading with all that 'till I got to the end of your missive, but I think I figured out your intentions there. However, I also think that it's tremendously ambitious -- doable, but quite difficult. And you're right, it's going to have to be thoroughly designed, modelled, and tested before coding anything that won't be thrown away.

You talk about the final system being completely data-driven. I think that can be done (at least much easier) if you put *some* kind of environmental restrictions on it. For instance, a good starting point might be to assume that it's a d20-style game you're working with (D&D3e can be used for a specific example during development if desired). But in a larger sense, you could make this do more...such as design Mechs or Spaceships or decks of TCGs (the latter of which I've given some thought to myself). But it might be nice to limit ourselves to a single "field" for now.

Also in regards to the data, we're going to have to have some kind of database of information to drive this code. For instance, choosing a weapon would have to include information about its attacks, damage, synergy with abilities (e.g. mighty bows, etc.), or choosing a feat would have to know what the prerequisite chain is. So an early question I see (though the answer may be obvious) would be "where are we going to get/keep this information?" Are we going to lift it from some other source (like E-Tools or PCGen or whatever), or try to design it to use such a source directly, or are you intending on rebuilding everything from scratch just for this purpose?

Let's try to identify related issues that exist in other fields of software design, and see if we can apply existing solutions to this.

Ok - I'm already seeing several possible approaches...

• It looks like it's a classic example of a multivariate optimization problem. (Think epic-level [non-]linear programming...) Mathematical techniques have been derived for dealing directly with problems of this sort, which I expect we could use. However, I'm not quite enough of a math person to be able to tell you exactly what they are or how to use them. Maybe someone else better qualified could fill us in on this subject?
• This could also be handled with an expert system. Expert systems are nice because they can find their way to a solution rapidly and easily. Their difficulty lies in needing to pre-define all the possible interactions and ramifications for it to assemble and use.
• The next step up from an expert system is an AI system. Properly programmed, an AI system would be a perfect solution. But it can be extraordinarily difficult to program something that complex and give it enough knowledge (associated data) to be useful (unless you're a leading-edge AI researcher, whom I'd love to find hanging around here). [Oh, and heuristics wouldn't be helpful here unless you're also planning to write a gaming & DMing AI as well to test the final results. --- NOT!]
• Another possible approach that might just work is a system called "simulated annealing". (I understand the principles, but have never worked with any of the details.) I doubt I can describe it properly, but let me try... Think of the process of crystallization in a hunk of cooling molten metal. When it starts cooling, large areas of the metal can no longer migrate far from their current position. As the metal cools, this region of localization gets smaller and smaller, thus each crystal of the final product is slowly limited to narrower and narrower positional choices until it is finally locked into place. Building a character could be much like this, starting with a rough form, then defining smaller and smaller details (interacting things of the same scale) until you end up with the smallest pieces being defined. (I'm not sure I described that very well, but maybe you can see what I'm talking about?)
• Theoretically, you could also use a "genetic algorithm" approach, but that doesn't sound like it has as much promise in this particular case. (In general, it works better for small numbers of things taking a very long time on each one.)

Does that help get any juices flowing?

 

[Archimedes]

Two Giant Steps

Well, Jamis, you’ve certainly got my attention.

In software engineering, the goal is generally to define a problem and implement a solution given limited time and resources. So you want to avoid Analysis Paralysis.

If you’re going to define the problem as ‘A complete theory of RPG definition’, you’ve gone past the realm of engineering and into Computer Science or Mathematics.

Unless I’m completely misunderstanding you, N-Body algorithms would seem to be a bad fit. All the ones I’ve seen have assumed large values of n, all bodies have an effect on each other, and all those interactions are homogenous. None of these assumptions would be true for RPG character generation.

I’d consider tackling your problem in two large steps.

First, you’ll need to design a descriptive language for RPG character generation. In other words, it would be a formalized and general way to describe the rules for character generation. As Davin said, restricting this to D20 would be much easier than going general right away. A language that could describe D&D, Inomine, and Classic Deadlands character generation would be ambitious as a first attempt.

Second, design and build a program that would carry out any valid instruction written in your descriptive language. Yeah, easier said than done here too.

Oh, and please remember that at first we’ll be talking past each other quite a bit until we can settle on common terms for what we’re trying to do. We’ll need to be patient.

Sam

 

[Archimedes]

I've been working for some time now (in my copious free time ) on a character generator that basically works as you described. Every attribute, stat, spell, power, object, etc. that a character can have is an "item" that can be of various types and have various data fields attached to it. Then you have a (potentially huge) table of effects that one item can have on others. The problem is that these effects can cascade indefinitely, so it's a highly non-trivial task to figure out how to ensure that, every time an item is added, dropped, or changed, you catch *every* possible repercussion of that change. If the system for defining such effects is sufficiently general, I believe the goal that you've stated can be met, but as I said, it's a highly non-trivial task (in the mathematician's sense of "non-trivial", where tasks that are "trivial" are those which require anything less than a Ph.D. to accomplish ).

Checking all these cascades at run time can be done using the Observer Design Pattern. See Gamma E., R. Helm, R. Johnson, et al. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading, MA, 1995. The Observer pattern is trivial, but potentially expensive in computer resources. Since you're only checking a few hundred, it shouldn't be too bad.

Sam

 

[jmettraux]

So Jamis complains that character generators are too static.

In the field of Business Processes (workflows), the latest workflow engines accept a workflow engine which describes the flow between various activities.
Business Process analysts write such 'workflow definitions' and they get launched by the workflow engine.

We could have a generic charactor engine, which we could instantiate for a 'generation-run' with a 'definition'. There could be a definition for DnD, one for RoleMaster, one for DnD FR,...

a copper piece reflection.

 

[JamisBuck]

Thanks for all your ideas! This has already been extremely helpful for me. I'd like to respond to each posters comments:

Peter: Thank-you for your comments on N-Body problems. I've not had a chance to do any deep research on it, and the information you provided does seem to indicate that the multi-body approach may not be appropriate for what I have in mind. Also, you are absolutely correct in that what I am trying to do is non-trivial--I fully expect it will be a large scale project requiring lots of brilliant minds to come up with the design.

Knightcrawler: I should clarify that when I said "generic", I was actually referring to a process that could be applied to problems outside of the realm of RPG's. I apologize in advance to everyone who misunderstood my meaning there. Yah, that increases the difficulty of the problem considerably, but I know it can be done. Keep in mind that initially, we're just talking theory. The implementation that we eventually decide upon will of course be more specific (possibily even system specific, as suggested by other posters).

Davin: If we can "harvest" data from other sources, I'm not against doing so. However, I have a feeling that any satisfactory solution we come up with is going to require more information than existing systems provide. We may be able to harvest some of their data, but we'll have to massage it. That's just me trying to predict the future, though. You're absolutely right about the need to be more specific, but I think (as I mentioned above) that we can at least theorize in general about the class of the problem, and then restrict our implementation to a specific realm.

Thanks also, Davin, for the wonderful list of possible approaches to the problem. That is EXACTLY what I was hoping to see. I hadn't considered this as an expert system, but it really is (in many respects). Still, you're right about that probably not being the best approach. An AI approach is good, though--I suspect that we'll probably combine lots of different technologies to create what we come up with. The "simulated annealing" suggestion really got me thinking--I'll have to do some more reading about that.

Archimedes: you're right about the dangers of over-analysis. However, given that we have an extremely flexible schedule and no real resource constraints, we can pretty much do whatever we want with the scope...within reason. It may be that our discussions here will prompt others to begin implementing systems based on partial analyses, and I'm sure those have a high chance of success, but keep in mind that my ultimate goal here, is really just to design. Naturally, we'll want to actually produce software eventually, but right now I want to find one of the best solutions possible for this problem. Your suggestion about a description language for RPG's is exactly what I've been working on for some time (with both Basilisk and Medusa), but I've actually tabled work on that for now since I want to focus more on analysis of the problem.

Also, Archimedes, you're exhortation towards patience until we settle on common definitions is an excellent one. Discussions will probably fluctuate around the true issue for a while until we settle into how the dynamics of this group will really work.

jmettraux: that's an intriguing idea. It leans more towards implementation, but I'd like to read more about it. Is there anything online, or any books you would recommend?

Thanks, all, for your ideas! One last thing: I thought I'd post some of my analysis of the relationships between many of the attributes of an NPC. I worked heavily on this document for a few months, but it has guided my thinking ever since (at least until I realized that I needed to be thinking on a more theoretical level). The document is not particularly well written, but it should give you something to work from in discussing interrelations between attributes. (Please note that the document is too focused, really, for our current discussion, but it is an example of the kinds of interrelationships we'll be dealing with). The document may be read here: http://www.jamisbuck.org/CADD.html .

Thanks for your comments!

- Jamis

 

[Twin Rose]

At GenCon, I was able to add 2 new abilities from T20 - EDU and SOC - with no hard coding into Campaign Suite. The fact is they aren't hard coded - they are parsed at run time.

Each addition 'type' of point, say "Saving throws" or "Hit Points" has a method attached to it that determines generation or numbers. The method references the statistic seperately, and can in most cases be edited at run time as well - sometimes, in the data file and then re-run from startup, but it's not in and of itself found in the Campaign Suite source.

Jamis, I think you should go ahead and check out the program, and see how we did it and also that we -are- d20 covered and will continue to be in the future.

 

[CRGreathouse]

This must be the suingle most complicated undertaking I've ever seen in the realm of RPG programming - one one of the most ambitious ever!

I'm going to read over the posts here and the references, go over some related sites to brush up on this, and get back to you if I have any ideas. Kudos for trying something this big!