Pyrel dev log, part 3

[Derakon]

Character races and classes are now in the "official" repo, along with a rudimentary character sheet:



That's a level-50 half-troll warrior. He's missing a few important stats (e.g. hitpoints) but the basic concept is sound.

Now that fully-fleshed-out characters are in, it should be possible to tackle more of the items on the To Do List; I've updated it appropriately. In particular, the following items are readily accessible:

* Dungeon generation
* Melee combat
* Item generation
* Basic creature AI

Personally, my next project is to refactor the Effects system -- it's really starting to diverge from its initial design, so some aspects need to be changed. Once I've done that we should be clear to implement many of the effects currently in Angband.

[ekolis]

Heh, charisma comes first because it's alphabetized... :P

[Magnate]

Now that fully-fleshed-out characters are in, it should be possible to tackle more of the items on the To Do List; I've updated it appropriately. In particular, the following items are readily accessible:

* Dungeon generation
* Melee combat
* Item generation
* Basic creature AI

Personally, my next project is to refactor the Effects system -- it's really starting to diverge from its initial design, so some aspects need to be changed. Once I've done that we should be clear to implement many of the effects currently in Angband.

Awesome. Fizzix mentioned that he might take a look at dungeon generation, and if I can get myself up and running I'll look at combat or item gen - probably the latter, both because I'm more familiar with it and because it will be more useful to fizzix. And it probably requires less 'design' thinking than combat - much as I would love to try that I suspect others will get there well ahead of me.

So does curses work yet? (I gather Qt is also nearing release)

[Derakon]

I spent some time talking about the stats system with my friends, and we've so far come to the conclusion that we can have an elegant system without edge cases, but that is limited in scope, or we can have the current system which has edge cases and occasionally odd behaviors, but can do more things. Let me explain further.

Remember that we have the following four tiers for stat modifiers: Inherent > Permanent > Temporary > Derived. Inherent is for mods that are fundamental to the stat; Permanent for indefinite-duration modifiers (e.g. from equipping things); Temporary is obvious; Derived is for modifiers that are based on the sum total of some other stat (e.g. improving AC by your total DEX). When determining the bonus that a given stat gives, it is only allowed to consider modifiers of a strictly lesser tier, to avoid circular dependencies -- e.g. DEX gives a percentage boost to AC, and AC gives a percentage boost to DEX; what's the ultimate value for both stats? This obviously untenable situation is the reason for the tiering system.

Okay, so say we have a ring that gives you a bonus to INT based on your magic device skill. Say further that magic device skill is determined in large part by your DEX. So we have this arrangement:

Magic Device skill has a Derived-tier modifier for DEX
INT has a Permanent-tier modifier for Magic Device skill.

Now we have a problem. If Magic Device skill comes primarily from the DEX score, then it must be Derived-tier, so that your skill is improved by all DEX bonuses (e.g. gloves of DEX improve your magic device skill). But that means that your Magic Device skill is greatly reduced (or even zero) when calculating the INT bonus for this specific item. The behavior is non-obvious to the player as well -- the item would say something like "Increases INT by 10% of Magic Device skill" but their bonus is 1 instead of 5, say, for no obvious reason.

(Of course, Angband "solves" this by basing your Magic Device skill on your level, race, and class, with comparatively marginal stat modifiers -- this is a workaround, not a true solution, but it may just have to do)

The alternate scheme put forth by my friends was to tier the stats, not the modifiers. You would have "core" stats like STR, INT, etc. and derived stats that are based on those core stats. And modifiers would only be allowed to flow "out" from the core stats. So you could have a modifier that gives 50% of your DEX to your Magic Device skill, but not a modifier that gives 50% of your Magic Device skill to your INT. Such mods would be fundamentally not allowed. This bugs me since I really like the idea of magic device skill influencing core stats, and I'm sure that people writing new effects for Pyrel could come up with all kinds of wacky interactions that would make things very interesting indeed. So I'm inclined against this solution -- but it is a solution that's unambiguous and has no edge cases.

But can we come up with something better? Something that allows for complex interactions in "any direction", but is unambiguous about why things interact the way they do? Presupposing that any stat can modify any other stat, there must be a hierarchy; otherwise you will have circular dependency problems. But the current tier-based hierarchy needn't be the one we use -- you could have one where the hierarchy were simply the order in which the modifiers was applied, for example.

Any ideas? Suggestions? Random neuron firings?

[Nick]

But can we come up with something better? Something that allows for complex interactions in "any direction", but is unambiguous about why things interact the way they do? Presupposing that any stat can modify any other stat, there must be a hierarchy; otherwise you will have circular dependency problems. But the current tier-based hierarchy needn't be the one we use -- you could have one where the hierarchy were simply the order in which the modifiers was applied, for example.

Any ideas? Suggestions? Random neuron firings?

The precise thing you need, rather than a hierarchy, is a directed acyclic graph. Without thinking too deeply, my guess is that you would keep the tiers, and label vertices with (stat, tier) pairs. Then you would draw edges based on what is allowed to influence what, and make sure that modification only occurs along edges.

[buzzkill]

So you could have a modifier that gives 50% of your DEX to your Magic Device skill, but not a modifier that gives 50% of your Magic Device skill to your INT. Such mods would be fundamentally not allowed. This bugs me since I really like the idea of magic device skill influencing core stats...

Aside from being hugely counter-intuitive, why would you want to do this? Magic device skill (MDS) is derived from INT (presumably). That makes sense. To modify INT, you would modify INT, not MDS. To modify MDS you would modify MDS, not INT. There has to be limits. Even given Nick's solution, there has to be limits.

Either I'm wrong or missing something very obvious. Could you supply a better example.

[Magnate]

Aside from being hugely counter-intuitive, why would you want to do this? Magic device skill (MDS) is derived from INT (presumably). That makes sense. To modify INT, you would modify INT, not MDS. To modify MDS you would modify MDS, not INT. There has to be limits. Even given Nick's solution, there has to be limits.

Either I'm wrong or missing something very obvious. Could you supply a better example.

I think my main problem here is that I don't really understand the difference between a stat and a stat modifier. I think the problem is somewhere in the Derived tier, but I don't think I can work out what it is without that understanding.

I fully agree with Derakon that Pyrel's design should facilitate future creativity by precluding the smallest possible number of modifiers.

[Derakon]

Aside from being hugely counter-intuitive, why would you want to do this? Magic device skill (MDS) is derived from INT (presumably). That makes sense. To modify INT, you would modify INT, not MDS. To modify MDS you would modify MDS, not INT. There has to be limits. Even given Nick's solution, there has to be limits.

Either I'm wrong or missing something very obvious. Could you supply a better example.

That was just a hypothetical example in a game where magic device derived from DEX instead of INT (presumably representing your ability to wave the wand properly or something). If you just swap DEX and INT wherever they appear in the example (thus, an item that improves your DEX based on your magic device skill, which is based on your INT), you'll get something closer to the reality of current Angband. It doesn't change the nature of the problem any.

Nick: so how do we represent a directed acyclic graph to the users? How do we decide the structure of the graph? I note with some amusement that if it were up to the player to decide how to structure the thing, then we'd probably have an interesting little optimization problem...

Magnate: a stat is just a name that refers to a collection of stat modifiers. So for example, STR is a stat that, at the start of the game, has the base value of (10 + race modifier + class modifier). Does that help any?

[Magnate]

Magnate: a stat is just a name that refers to a collection of stat modifiers. So for example, STR is a stat that, at the start of the game, has the base value of (10 + race modifier + class modifier). Does that help any?

Yes - counter-intuitive but makes perfect sense now.

So isn't the problem in your example that the MDS-modifying-INT is in the wrong tier?

MDS is a Derived stat: it is not calculated until the Derived modifiers are done (so that all DEX mods can affect it). It therefore cannot provide a Permanent-tier modifier to INT, but only a Derived-tier one, yes?

So INT is modified by MDS after MDS is modified by DEX.

Is that too simple?

[Derakon]

So isn't the problem in your example that the MDS-modifying-INT is in the wrong tier?

MDS is a Derived stat: it is not calculated until the Derived modifiers are done (so that all DEX mods can affect it). It therefore cannot provide a Permanent-tier modifier to INT, but only a Derived-tier one, yes?

So INT is modified by MDS after MDS is modified by DEX.

Is that too simple?

But you can't have a Derived-tier modifier based on another Derived-tier modifier -- mods can only use strictly lesser tier mods to calculate themselves. Otherwise you can still allow cyclical dependencies.

[Magnate]

But you can't have a Derived-tier modifier based on another Derived-tier modifier -- mods can only use strictly lesser tier mods to calculate themselves. Otherwise you can still allow cyclical dependencies.

Then it looks like you need another tier if you want to allow your example to happen. A sort of derived-from-derived.

[Derakon]

Then it looks like you need another tier if you want to allow your example to happen. A sort of derived-from-derived.

I suspect such an approach would just be turtles all the way down (i.e. you'd always find yourself wanting to provide another tier). For example, the INT -> Magic Device -> DEX problem could be extended by an item that increased your Stealth by your DEX score, so we have INT -> Magic Device -> DEX -> Stealth, each of which must be on a strictly greater tier than the one before.

[Nick]

Nick: so how do we represent a directed acyclic graph to the users? How do we decide the structure of the graph? I note with some amusement that if it were up to the player to decide how to structure the thing, then we'd probably have an interesting little optimization problem...

I think we would need a set of rules for how stats can modify each other, and then the DAG should be used for checking. The thing is, it is the fact that the graph has no cycles that is important - no cycles means you definitely have no troubles, cycles mean you definitely do.

I am not thinking of the DAG as something that would be helpful directly to players, although maybe I'm wrong about that.

[Derakon]

Hm, perhaps we're coming at this from the wrong angle.

The original tiers -- Inherent, Permanent, Temporary -- were meant solely to decide how to apply multiplicative scaling factors. Like, if you had an item that increased your AC by 10%, which value did you use for that calculation? For that kind of situation, the existing tiers make perfect sense, both for programming and to the user. Items that you equip get to increase

It's the interstat modifiers that are problematic -- basically everything that we would want to fall into the Derived tier. We can split this into two categories: the Derived-tier modifications that are on the character when they're born, and the Derived-tier modifications that they get during the course of play. The former is a game design problem -- you can just ensure that any Derived-tier mods on a character will not care about what order they are applied in, and then you have no problem. The latter is where order of operations really becomes an issue.

It seems like any automatic decisionmaking we do on the order of operations would be "wrong" at some point, at least from the user's perspective -- they would want to do things in a different order to maximize their bonuses, and I can't think of any system that would be objectively logical (and thus justifiable) in all situations. So increasingly I'm leaning towards letting the user decide.

The idea here would be that any time a new Derived-tier modification is applied to the user's stats, it'd go onto the end of a queue; mods would be applied in the order on the queue. But the user would have access to the queue and would be allowed to re-order things as they wish. The default ordering then would be "order in which you received the mods", which is at least somewhat reasonable on its own.

Mm, and creating this chargen/later split does seem to mean that we'd want a second Derived tier (one for the mods created before chargen, which don't care about ordering; one for after, which does). Sorry, Magnate.

[AnonymousHero]

It seems like any automatic decisionmaking we do on the order of operations would be "wrong" at some point, at least from the user's perspective -- they would want to do things in a different order to maximize their bonuses, and I can't think of any system that would be objectively logical (and thus justifiable) in all situations. So increasingly I'm leaning towards letting the user decide.

The user as in the player? Sounds like this could get annoying from a UI perspective (not to mention hard to balance).

AFAICT the auto-tiering thing is pretty simple: 1) "Compress" the DAG to minimize distance from the root to every other node while maintaining proper dependencies, basically maximal path compression. 2) Classify into tiers based on distance from the root node. This will give you the minimal number of necessary tiers and the nodes in each tier.

I can think of at least one simple way to this: Do a topo-sort and build the tiers iteratively: If the next node in the topo-sorted list is pointed to directly by any node in the current tier, then start a new tier. If it isn't, then simply add to current tier. (With appropriate degenerate cases for the root, etc.)

There may be far better algorithms for doing this, but it's been a few (well, many) years since I took any Graph Theory classes