Pyrel dev log

[AnonymousHero]

A recursive descent expression parser/evaluator should be pretty easy to do. If you have a grammar without left recursion you can translate it pretty directly into simple python code. The same wiki page has an example grammar of which a subset is expressions and the necessary C code to implement expression parsing. (Though I wouldn't recommend a direct translation of that code -- it looks pretty old-school what with global state, etc.)

Tokenization is easily handled with regexes. (A simple dictionary of regex->token type should work ok for a simple expression language.)

[Derakon]

I don't really like the idea of implementing my own parser into Pyrel, mostly because parsers are solved problems -- writing my own doesn't really add anything interesting beyond new bug opportunities. This ought to be a situation in which there's a readily-available library that does what I need (once I substitute in the appropriate values for the strings we care about, of course).

Anyway, it's not critical that I tackle that problem right now, so I'm moving on to map generation. The current map generator is completely hardcoded, so obviously it has to go. Here's how I plan the new sequence to work:

We have the GameMap class instance. This holds all of the entities in the game. We create a single instance of this class at the start, and it remains for the duration of the game. It persists across levels largely because there are other entities that also persist across levels, and the easiest way to handle this is to have a "PERSISTENT" container in the GameMap instance that I can add those entities to. Examples of persistent entities would be the player and everything they're carrying; shops; hypothetical monsters that are allowed to chase the player across levels; etc. Note that the GameMap can contain entities that are not "physically present" on the current level.

When we want to generate a new level, we call GameMap.makeLevel(level). "level" here is a numeric argument indicating the depth. Obviously in variants this could be extended to specify which dungeon you're in, or to differentiate between different "level 0" maps instead of implicitly assuming the town. makeLevel() then invokes a function to decide on what map generator to use.

As of v4 we have four options: town, standard dungeon, labyrinth, and cavern. However, given that we've talked about mix&matching these generators (having levels that are largely "vanilla" but mix in a bit of natural caverns, for example), it seems likely that instead each "generator" will consist of calling a selection of functions that form the actual map. For example, everyone will share the same magma/quartz seam generator code; likewise, everyone needs the same rules for deciding if down staircases are generable (e.g. because the player's at level 99 and Sauron still lives). Still, a high-level function will be needed to decide how those different sub-functions are organized and invoked. And of course we need different rules for placing monsters and items as well.

We'll need an Allocator class that can handle picking monsters and items -- not just for level generation, but also for item drops and summons. Monsters and items use the same basic "rarity" mechanic, so the Allocator can iterate through the entirety of the monster/item records, find everything that's in-depth, sum up their rarities, and use that to decide how common various things are with respect to each other. I believe Magnate said this was called something like a "table selector" in Vanilla's code. Actually what will probably be done is that every monster/item in the game is added to the table, but they get multipliers to their rarity based on how in-depth they are. For example, every additional level of out-of-depthness makes a monster 25% more rare and an item 50% more rare. Or whatever.

Actual placement of the monsters/items in the level is up to the generator, of course; the allocator merely selects what should be placed.

As far as items are concerned, here's how I think generation to be done:

* Compile the frequency table for all items.
* Append the frequency table for all artifacts to this table.
* Select from the table. If it is a non-artifact equipment item, hand it off to the affix/promotion system, otherwise just use the item straight.

I'm not entirely clear on how exactly artifacts are allocated in current Vanilla, but this system I'm proposing would let us directly compare the frequency of a given artifact to the frequencies of normal items, which I don't believe is currently possible.

(Of course, I'll be postponing artifacts for the forseeable future, as well as the affix system. They're in that big bucket of things that I consider to be "fluff", which also includes stuff like proper combat calculations, actual creature AI, the look command, etc.)

Any thoughts?

[AnonymousHero]

I don't really like the idea of implementing my own parser into Pyrel, mostly because parsers are solved problems -- writing my own doesn't really add anything interesting beyond new bug opportunities. This ought to be a situation in which there's a readily-available library that does what I need (once I substitute in the appropriate values for the strings we care about, of course).

Certainly, however your point about dependencies is a real worry, especially if you don't pick something which has wide support on distros (and Windows + Mac OS X).

My point was simply that a recursive descent parser is about the same complexity as actually specifying the grammar. Unless you're going for efficiency (or a different class of languages that recursive descent can't handle) it's not actually a big deal to just implement this yourself. (Contrary to other types of parsers.)

When we want to generate a new level, we call GameMap.makeLevel(level). "level" here is a numeric argument indicating the depth. Obviously in variants this could be extended to specify which dungeon you're in, or to differentiate between different "level 0" maps instead of implicitly assuming the town. makeLevel() then invokes a function to decide on what map generator to use.

Implementing a highly linked structure, having every map location contain links to all the different exits from the location could a simpler and make it easier for variants to implement highly branching level structures (including persistent levels).

So you'd have something like this:

{ name: "town"
, level: 0,
, exits: {
      "down" : { name: "dlvl 1"
                  , level: 1,
                  , exits: {
                         "down" : ....
                         "up" : (reference back to town level },
                         "..." : ...
                 }
      }
}

The exit names are free-form and are referred to by terrain in the map levels, e.g. ">" in "dlvl 1" refers to "down".

You might want to permit exits which are actually functions/objects which can dynamically compute the map which the exit leads to. This lets you avoid computing the full map structure and do things like persistent levels.

This kind of structure should make it really easy to implement various kinds of map interconnectedness structures -- even things like infinite dungeons that are more interesting than simply going from level 1.. infinity.

[Derakon]

Persistent maps can be readily handled by only comparatively minor tweaks to the game:

1) Create a new class, call it something like StashedMap.
2) Set up a mapping of (staircase XY position + dungeon level) to StashedMaps.
3) When taking a staircase, first generate a new StashedMap and stick everything into it (except for the entities that always persist across levels, of course). Then, if we've been to the new level before, use a level generator that pulls info from its StashedMap; otherwise, create a new level.

This gets a bit more complicated if you want non-player things to be able to move from a StashedMap to the current map but should still be doable.

Fair point on the parser being comparatively simple to implement.

For what it's worth, staircases are Terrain instances whose interactions include "go up" or "go down" -- which invoke GameMap.makeLevel(current level +- 1) as appropriate.

[Sirridan]

I feel bad that I never finished my python port

If you want any help though, I'll gladly throw in my two or three cents. Especially now that my life is much less chaotic.

[AnonymousHero]

Persistent maps can be readily handled by only comparatively minor tweaks to the game:

1) Create a new class, call it something like StashedMap.
2) Set up a mapping of (staircase XY position + dungeon level) to StashedMaps.
3) When taking a staircase, first generate a new StashedMap and stick everything into it (except for the entities that always persist across levels, of course). Then, if we've been to the new level before, use a level generator that pulls info from its StashedMap; otherwise, create a new level.

This gets a bit more complicated if you want non-player things to be able to move from a StashedMap to the current map but should still be doable.

Fair point on the parser being comparatively simple to implement.

For what it's worth, staircases are Terrain instances whose interactions include "go up" or "go down" -- which invoke GameMap.makeLevel(current level +- 1) as appropriate.

Yeah, my point with the structure I posted is that there is absolutely no special casing of anything. For example: the level doesn't have to be an "integer", any level properties which a variant wants to add completely up to it, to fixed up/down exits -- you can do things like FA's east/west/north/south trivially. You can also store monsters and objects directly inside the level as properties -- there's no need to do anything special to move (e.g.) monsters between levels. You just move them in the data structure and you're done.

However, it's pretty hard to see if this would have any limitations of your current code structure -- I think you should probably post code on github if you want to get more constructive feedback.

[Magnate]

We'll need an Allocator class that can handle picking monsters and items -- not just for level generation, but also for item drops and summons. Monsters and items use the same basic "rarity" mechanic, so the Allocator can iterate through the entirety of the monster/item records, find everything that's in-depth, sum up their rarities, and use that to decide how common various things are with respect to each other. I believe Magnate said this was called something like a "table selector" in Vanilla's code.

Allocation table.

Actually what will probably be done is that every monster/item in the game is added to the table, but they get multipliers to their rarity based on how in-depth they are. For example, every additional level of out-of-depthness makes a monster 25% more rare and an item 50% more rare. Or whatever.

So a single master allocation table for the entire level. Good idea. Will you generate the table for every level at game start, or do it dynamically? v4 currently generates the base object tables for the whole game at the start, but generates affix and artifact tables on the fly (which I suspect is hugely inefficient).

As far as items are concerned, here's how I think generation to be done:

* Compile the frequency table for all items.
* Append the frequency table for all artifacts to this table.
* Select from the table. If it is a non-artifact equipment item, hand it off to the affix/promotion system, otherwise just use the item straight.

I'm not entirely clear on how exactly artifacts are allocated in current Vanilla, but this system I'm proposing would let us directly compare the frequency of a given artifact to the frequencies of normal items, which I don't believe is currently possible.

Now that's an interesting idea, which had never occurred to me. (I think direct comparison of frequencies is possible using stats, but I think perhaps by "direct" you meant without stats.) This would mean a fairly large table: if The One Ring has a frequency in this table of 1, the 'thancs should have a frequency of about 1000 or so, and most normal objects would have a frequency in the hundreds of thousands. I think this is the reason nobody's thought of it before: it's not intuitive to compare rarities of very common and ultra-rare objects so directly. That doesn't mean it's not a good idea though - as you say, it's ideal for direct comparisons and balancing.

How would you deal with the fact that not every item is a legal pick for every call to the table? This is the main reason for dynamic tables, when drops are limited. (The normal limitation is depth, but this isn't situational - you can make 100 allocation tables at the start of the game to cover all levels.) What if I want snagas to be able to drop food, weapons and armour but not potions, scrolls or devices? With a static table you'd ignore or re-try illegal picks?

Separately, how do you decide on affix generation / item promotion? With v4 we still have the old distinction between 'normal' and 'good' objects for this, but presumably you'd have nothing so clumsy. Will it be an inherent property of the table, i.e. if a dagger as 200,000 entries, the last 50,000 have increasing numbers of affixes?

(Of course, I'll be postponing artifacts for the forseeable future, as well as the affix system. They're in that big bucket of things that I consider to be "fluff", which also includes stuff like proper combat calculations, actual creature AI, the look command, etc.)

Brilliantly put.

[Derakon]

So a single master allocation table for the entire level. Good idea. Will you generate the table for every level at game start, or do it dynamically? v4 currently generates the base object tables for the whole game at the start, but generates affix and artifact tables on the fly (which I suspect is hugely inefficient).

It'll have to be dynamic at some level, because of artifact placement -- you obviously can't place an artifact twice, so once you've placed it you need to adjust the table. I'll be giving some more thought to how to do this efficiently; it may be possible to have a static table that you interact with "dynamically". That would probably make referring to the table slower though. The first thing to do, of course, is just time how long it takes to make a table and how long it takes to look up values in it; we may suspect it's inefficient but it makes zero sense to optimize without knowing that it's inefficient.

Now that's an interesting idea, which had never occurred to me. (I think direct comparison of frequencies is possible using stats, but I think perhaps by "direct" you meant without stats.) This would mean a fairly large table: if The One Ring has a frequency in this table of 1, the 'thancs should have a frequency of about 1000 or so, and most normal objects would have a frequency in the hundreds of thousands. I think this is the reason nobody's thought of it before: it's not intuitive to compare rarities of very common and ultra-rare objects so directly. That doesn't mean it's not a good idea though - as you say, it's ideal for direct comparisons and balancing.

It would be quite straightforward to have an implicit scaling factor to keep the number size under control, so that e.g. a "1" for a basic object type would be a "100" for an artifact. But I'll leave that until we get around to hooking in the appropriate stats (my assumption is that item rarities in Pyrel will be set by examining some stats data from v4).

How would you deal with the fact that not every item is a legal pick for every call to the table? This is the main reason for dynamic tables, when drops are limited. (The normal limitation is depth, but this isn't situational - you can make 100 allocation tables at the start of the game to cover all levels.) What if I want snagas to be able to drop food, weapons and armour but not potions, scrolls or devices? With a static table you'd ignore or re-try illegal picks?

My kneejerk reaction is to have subdivided tables by item type -- so you'd have the food table, the weapon table, the potion table, the weapon artifact table, etc. Then you could make a composite table with ease. All you need to know to make a selection is the size of the tables you're using, since that determines the range on the random number you generate.

Separately, how do you decide on affix generation / item promotion? With v4 we still have the old distinction between 'normal' and 'good' objects for this, but presumably you'd have nothing so clumsy. Will it be an inherent property of the table, i.e. if a dagger as 200,000 entries, the last 50,000 have increasing numbers of affixes?

This I haven't given much thought to. Affix selection is a complicated procedure, and then of course there's the theme application. To be quite honest I'm not entirely clear on how the current system works, so figuring out a redesign on that will have to wait.

In the meantime, you don't really need magical gear, right?

Oh, incidentally -- quoting your posts is kind of a pain because you don't put any newlines into 'em. I've noticed that the BB software here automatically puts in a minimum amount of vertical space between quoted text and non-quoted text (i.e. it adds newlines if you left them out of your post), so you may as well put them in.

[Magnate]

My kneejerk reaction is to have subdivided tables by item type -- so you'd have the food table, the weapon table, the potion table, the weapon artifact table, etc. Then you could make a composite table with ease. All you need to know to make a selection is the size of the tables you're using, since that determines the range on the random number you generate.

That takes care of the type limitations, certainly. But I was hoping for a more generic solution, so that I can make drop profiles like:

- cannot drop anything heavier than 10lbs
- can drop food with increased probability for beverages (3x for orcish firewater)
- can drop only items with gemstone flavours
- can drop anything except diggers

Admittedly this is more control than we have now - we can currently specify only tval, sval and amount for not-totally-random drops. But my guess is that this is all leading us towards dynamic table creation ...

This I haven't given much thought to. Affix selection is a complicated procedure, and then of course there's the theme application. To be quite honest I'm not entirely clear on how the current system works, so figuring out a redesign on that will have to wait.

Well, I'm very happy to help. The v4 system works like this:

1. We arrive at a point where we're creating a wearable item (including ammo; doesn't currently apply to jewelry, but it will soon) - so we call apply_magic. It takes an int and two bools: the item creation level (dlev with possible increases e.g. for vault items), whether it's 'good', and whether it's 'great'. (These two could easily be replaced with a more sophisticated reckoning of an item's quality or potential.) (I'm leaving artifacts aside - for unspecified drops we have already checked before we get here so we know it's not an artifact.)

2. We establish the *type* of affixes available to it: by default any item can have any affixes deemed Bad, Average or Good (levels 1-3). Note that this does not require the 'good' bool - poor use of terminology on my part. Depending on the passed-in creation level, the bools and some randomness, the min and max affix levels can increase: better and deeper items have access to higher affix categories (Great and Uber, and one day maybe Artifact affixes), and they also are more likely not to have Bad or Average affixes.

3. We calculate the *number* of affixes it will have. This is basically a function of the passed-in creation level, randint0(2 + lev / 20). So 0-1 at shallow depths, up to 0-5 at dl80. Plus 1d2 if good and 1d2 if great, +1 if it has access to Great affixes, for a range of 3-10 for the best endgame items, but capped at 8. This algorithm phases out junk pretty well as you go through the game - it currently leads to overpowered weapons though, because we don't have enough weapon affixes available (most of them tend to increase damage output).

4. We then call obj_add_affix until we've added them all OR acquired a theme. This contains a small chance of boosting the affix category - so an item might get a single Great affix even though it was only supposed to get access to Good ones. There's no real driver for this other than the pre-existing GREAT_EGO check (which used to allow OOD generation of ego types). This check also boosts the creation level, so a shallow item with a single affix might still get an endgame affix on it, once in a blue moon.

Anyway, we build an allocation table (obj_find_affix) of legal affixes every time we add one. It would be more efficient to build it once, because at the moment it depends only on the item's tval, sval, creation level and allowed affix categories. But building it on the fly will come into its own when we implement affix compatibility - i.e. X is not legal if we already have Y, etc.

After we've built and picked from the table, we actually apply it (ego_apply_magic). Then we check for breakage using object_power, rolling back if necessary. Then we check for a theme - again, we build an allocation table of available themes and roll for one. This does need to be dynamic, because it depends on the affixes on the item.

HTH. Happy to expand.

Oh, incidentally -- quoting your posts is kind of a pain because you don't put any newlines into 'em. I've noticed that the BB software here automatically puts in a minimum amount of vertical space between quoted text and non-quoted text (i.e. it adds newlines if you left them out of your post), so you may as well put them in.

Better?

[Derakon]

Well, of course it's easier to quote when your post itself contains multiple paragraphs. But yes, that does seem better. Not that I'm actually quoting in response.

Anyway, regarding item selection for drops, it sounds like you basically want a selection of filters which would specify either a (set of) flag(s) that must be present on the item (e.g. ORCISH, GEMSTONE) or a feature of the item that must match some conditional (e.g. "weight < 10", "type is potion"). Affix-based drops are something that I think we leave for much later, since there's some question of how exactly you do that -- do you automatically apply a gemstone affix to every affixable item the creature drops? I'd rather leave the item generator "pure" (i.e. context-agnostic) as long as possible. But everything else should be comparatively straightforward.

Thanks for the rundown on how affix generation is handled in v4. Here's how I'd re-implement it in Pyrel, I think (and again, this is just off the cuff, so I may well be missing subtleties).

1) drop_good and drop_great are replaced by boosts to the item's level. Thus a creature with the current equivalent of DROP_GOOD | ONLY_ITEM would be able to drop any non-money item at an effective level of, say, +15. Further limitations could be applied; presumably we'd also want most creatures with DROP_GOOD to also have a limitation to only drop wearable items, ammunition, dungeon spellbooks, and certain high-end consumables. But we could also add e.g. a filter to let uniques prior to level 20 potentially drop stat-gain potions.

2) We use the item's level to decide a target power level. In practice this defines a region of power levels (N +- X).

3) We pick an affix at complete random (no categorization of affixes), add it to the item, and calculate its power level. If it's in the target region, then we're done; if it's over the maximum, then we reject that affix and try again; otherwise, we try again. We have a max repeat on attempts to add affixes, of course, so we don't get stuck. Of course a "bad" affix would always succeed at this point since it doesn't increase the item's power, but see below.

4) Every time we add an affix, we check for theming; if the item matches a theme then we apply it and bump the item's power to suit (and again, rolling back the theme if it pushes the power too high).

Assuming we have a good item power calculation, this seems like it would avoid the issue currently in v4 where items end up getting overpowered later on. However, it doesn't break down the affixes by quality, so you could still be seeing e.g. "broken" items in the late game. I anticipate affixes having allocation rules much like items do where they have native depths and frequencies within those depths, though, so such affixes shouldn't show up as often as you go deeper, just like you don't often see e.g. Scrolls of Blessing in the late game.

[Magnate]

Affix-based drops are something that I think we leave for much later, since there's some question of how exactly you do that -- do you automatically apply a gemstone affix to every affixable item the creature drops? I'd rather leave the item generator "pure" (i.e. context-agnostic) as long as possible. But everything else should be comparatively straightforward.

I agree - and if we use a target power level (derived from depth and drop quality), the problem pretty much goes away.

3) We pick an affix at complete random (no categorization of affixes), add it to the item, and calculate its power level. If it's in the target region, then we're done; if it's over the maximum, then we reject that affix and try again; otherwise, we try again.

How does this fit ...

Assuming we have a good item power calculation, this seems like it would avoid the issue currently in v4 where items end up getting overpowered later on. However, it doesn't break down the affixes by quality, so you could still be seeing e.g. "broken" items in the late game. I anticipate affixes having allocation rules much like items do where they have native depths and frequencies within those depths, though, so such affixes shouldn't show up as often as you go deeper, just like you don't often see e.g. Scrolls of Blessing in the late game.

... with this? You won't categorise affixes but you'll still give them min and max depths? That would work for filtering out broken items later on etc., but will be harder to balance the rarities. It might also lead to overpowered early items if you allow OOD affixes (e.g. Nightbane and so on).

I see the categories as a helpful way to manage relative rarity at a high level, and to help conceptualise generation (sub-great items can't get X & Y, etc.). You could indeed do away with them and manage simply with allocation info (min/max depth, frequency - not all affixes are equally likely, item-specificity - an affix can be commonplace on shields but very rare on weapons etc.). It ends up being a different way to present the same data.

You're right that a target power level will avoid overpowered late-game items. I've never had the confidence in object_power to take that approach: I'd be happy to work with you on reimplementing object_power, having got about as far as I can with the existing version. (I realised that to get any further I'd need to create a dummy player struct with generic endgame stats and kit, and that seemed like a lot of work for minimal gain.)

[Derakon]

How does this fit ...

... with this? You won't categorise affixes but you'll still give them min and max depths? That would work for filtering out broken items later on etc., but will be harder to balance the rarities. It might also lead to overpowered early items if you allow OOD affixes (e.g. Nightbane and so on).

I would assume that most affixes won't have a max depth. Really, only the negative affixes would need to go away; the weak positive affixes can be piled on willy-nilly since they have comparatively little effect on the object power anyway.

You're right that a target power level will avoid overpowered late-game items. I've never had the confidence in object_power to take that approach: I'd be happy to work with you on reimplementing object_power, having got about as far as I can with the existing version. (I realised that to get any further I'd need to create a dummy player struct with generic endgame stats and kit, and that seemed like a lot of work for minimal gain.)

Hm, rethinking calculating object power will be tricky. Save that one for later, I think.

[Magnate]

I would assume that most affixes won't have a max depth. Really, only the negative affixes would need to go away; the weak positive affixes can be piled on willy-nilly since they have comparatively little effect on the object power anyway.

But I think you'd find that this produces really crappy items. If you're going to implement a min depth, and want to phase out negative affixes, max depth seems the obvious solution. Anyway, I'll save more details comments for now (any ETA on publication? Or at least, do you have a shrinking list of stuff you want to code up beforehand?).

Hm, rethinking calculating object power will be tricky. Save that one for later, I think.

Well, I always thought that the key was to calculate values for defensive abilities empirically, by reference to monster power - i.e. calculate the values of resists the same way as the values of slays.

So this means that what we actually want to rethink/improve is the monster power calc. It's not bad - nullfame made some significant improvements - but it still relies on some fairly dodgy constants (damage equivalents for non-damage spells).

[ekolis]

Now that's an interesting idea, which had never occurred to me. (I think direct comparison of frequencies is possible using stats, but I think perhaps by "direct" you meant without stats.) This would mean a fairly large table: if The One Ring has a frequency in this table of 1, the 'thancs should have a frequency of about 1000 or so, and most normal objects would have a frequency in the hundreds of thousands. I think this is the reason nobody's thought of it before: it's not intuitive to compare rarities of very common and ultra-rare objects so directly. That doesn't mean it's not a good idea though - as you say, it's ideal for direct comparisons and balancing.

This is why we have exponential notation!

One Ring = 1

Artifact = 1e3

Amulet of sustenance = 1e5

Food ration = 1e6

[Derakon]

(any ETA on publication? Or at least, do you have a shrinking list of stuff you want to code up beforehand?)

At this point I think the level generation (including creature and item allocators) is the only remaining core functionality I want to put in before I'm willing to release. There's lots of other Important Things, of course, but they aren't framework-level important (c.f. anything involving targeting/looking/projecting, a decent combat engine, actual stats for the player and monsters, being able to die, etc...).

Well, I always thought that the key was to calculate values for defensive abilities empirically, by reference to monster power - i.e. calculate the values of resists the same way as the values of slays.

So this means that what we actually want to rethink/improve is the monster power calc. It's not bad - nullfame made some significant improvements - but it still relies on some fairly dodgy constants (damage equivalents for non-damage spells).

This will get trickier if we decide to start making monster powers more exotic. For example, how do you consider the power of a monster whose melee attacks have a 10% chance of setting off a radius-2 fireball? I don't believe for an instant that we won't make use of readily-scriptable procs in basically every aspect of the game.

This is why we have exponential notation!

One Ring = 1

Artifact = 1e3

Amulet of sustenance = 1e5

Food ration = 1e6

More generally, there's nothing that says that the minimum rarity must be 1. Pyrel supports floating-point, so we could have values ranging from e.g. .001 to 1000 and still have that "common thing is a million times more common than rare thing" range. If ints are needed code-side then the code can simply apply a constant scaling factor based on the smallest value used in the data file.