Pyrel dev log, part 4

[Derakon]

I admit that I didn't read your entire post, so I apologize for short-circuiting the conversation. But my eventual conclusion on this problem is that there is no right answer, and it's up to the game designer to pick modifier tiers in a way that makes sense. The game will enforce an ordering of stat modifiers, so there can be no cyclic dependencies, but that's all it will do. "Inherent", "permanent", "temporary", etc. tiers may or may not make sense depending on what the designer wants to do, but they clearly won't fit every possible design.

[Kinematics]

Some thoughts on the issues of stat calculations from the #3 thread that never seemed to have gotten resolved (at least, not in the thread, and the code looks like it's still using the same ideas).


More confusing ways to apply: Suppose you decide that hobbits, rather than a static +3 bonus to dex, get a bonus of level/10, or just +20%. (note: seems less likely for base stats, and more likely to apply to things like speed, such as hengband's level-based speed increase for ninjas; just an example, though) Where does this apply in the calculation hierarchy?

It's part of what's considered the 'Inherent' level of calculation -- the race modifier -- yet depends on other calculations. Which leads me to a slightly different approach.


I would construct it like this:

Fundamental - initial birth value (dice roll, player buy, whatever); cannot change during the game.

Fixed mods - Additions that -do not- depend on the stat itself. static +3 from race; +level/10 to speed; etc.

Multiplier mods - Additions that -do- depend on the stat itself. Ring of +20% str, etc. These are only calculated after Fixed mods are done.


Whether it's a permanent or temporary effect doesn't matter. Ring of +3 str or Ring of +20% str are both permanent, but don't get calculated at the same time. A spell of Giant Strength that adds +5 to str for 50 turns would go under Fixed mods, not Multiplier mods, and there's no reason to treat it differently than a ring of +5 str.


Now, the hypothetical example:

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.

Ring would adjust Int as a Fixed mod based on Magic Devices.
Dex would adjust Magic Devices skill as a Fixed mod.

So when calculating Int, it gets to the Fixed mods level, determines there's a ring that modifies it (or the ring inserts its StatMod call into the queue), asks the ring how much to modify things by. Ring says "Hold on a minute..", asks how much the MD skill is; MD skill queries Dex, which carries out all of its calculations, returns a value, MD gets calculated, returned to the Ring, Ring figures out its value, and gives that to Int. No problems.

Now suppose Magic Devices depends on Int, and the Ring mods Int based on Magic Device skill. What I would do:

What is current Int? Start adding Fixed mods to the Fundamental value. When a StatMod() is called, mark it as 'In Use', and release it afterwards.
Call Ring.StatMod(). It queries Magic Devices for skill.
Magic Devices needs to know Int. Requests current Int value.
What is current Int? Start adding Fixed mods to the Fundamental value. Ring.StatMod() is 'In Use', so gets skipped. Returns a value for all adjustments other than Ring.StatMod().
We now have a Magic Devices skill value relevant to the Ring's query (not full magic skill, but magic skill without the bonus the ring provides). Return that.
Ring.StatMod() now has a value for Magic Devices skill, and returns the amount it increase Int by.
Int completes the Fixed mods calculations.
Int can then proceed to later add a Ring of +20% Int using the value that includes the MD-based Int ring value.

Supposing you had 2 such rings -- each gets locked during the Magic Device Skill query, so that the MDS value that they each use is based on neither of the rings being present. I'm pretty sure this would hold even if every single equip slot was making this same modification, though that would add a huge number of near-circular redundant calls. You could maybe cache each StatMod() call within a given top-level request, to reduce the redundancy; just make sure not to re-cache during a circular cycle.



Differentiating between Fixed and Multiplier mods would probably be easiest by just having two different functions. You can either insert a StatMods() call into the queue for complicated calculations that will eventually provide a fixed value addition, or just provide a simple percentage to the total multiplier value to be used as the final adjustment after Fixed mods are added in. EG:

OnEquip ring of str, AddStatMod(MyFunction)
OnEquip ring of +20% str, AddStatMultiplier(20%)

Though technically there's nothing to prevent the StatMod() call from calculating its result from the stat itself; it's just bad form, and will give lesser results [Edit: actually, it would probably give identical results; it would just take more work since you have to calculate everything twice], but won't break anything.

[LostTemplar]

It is a matter of taste, what to hardcode, you cannot make engine universal. Basically there must be a function, which tells you if a tile is transparent, there are two ways to use this function: call it when tile is checked in LOS function, or call it when tile is changed. I think, that second way will be more effective.

If you have a lot of functions for different kinds of LOS, it still may be faster to call them all for every tile changed. IMHO you will never really have a lot of different LOS types.

[jdh]

This would need to be handled on a per-invocation basis (as opposed to when the accessibility array is updated), since you can't have directionality without having a source and target. The way I'd do it would be to have a value (e.g. None) that indicates that the tile needs to be handled specially. So while trying to get LOS, the function checks that tile, sees that it requires special handling, and manually checks the tile contents.

I would think you could implement this as a sort of directed graph, with a cost for traveling from each tile to each adjacent tile: e.g., if you have tiles in each of the 8 keypad directions, there would be a cost for moving to each. (I don't know whether you're contemplating extensibility to other geometries.) Your cache would store costs for entire paths, but each path greater than 1 would have several other paths as subsets: cost(a,d) for a -> b -> c -> d would check cache[a,d], then fall back to cost(a,c)+cost(c,d). This may be excessive cleverness and I don't know how you would apply it to things other than line projections (such as Sil's noise concept), but I wouldn't think it would be too many more than 95 calculations for 95 orcs checking whether they can see the player.

[Derakon]

1. Opacity: you might be able to see through a few orcs if you are only a few orcs back in the mob, but a crowd of 100? And what if you have mist, rain, smoke or fog? It would be cool if it could accumulate and have stages of effect: you see poorly 3 or 4 tiles away, hallucinations or mirages 4-10 steps away and nothing further than that...

There's no reason you couldn't have an array of floating point numbers instead of an array of booleans. Then 0 represents completely unobstructed, 1 completely obstructed, and anything in-between is partially obstructed.

2. Directionality: suppose you would like to have one-way mirrors that let you see into rooms but not out, or perhaps camouflaged entrances which monsters see out of but are difficult to see into?

This would need to be handled on a per-invocation basis (as opposed to when the accessibility array is updated), since you can't have directionality without having a source and target. The way I'd do it would be to have a value (e.g. None) that indicates that the tile needs to be handled specially. So while trying to get LOS, the function checks that tile, sees that it requires special handling, and manually checks the tile contents.

Maybe just have one value per tile, that determine it's accessiblity status (not just boolean, but also not too genral, e.g. lava is different from floor, etc.) Which is computed when and only when the given tile is modifyed, not when someone wants to look thru it.

It sounds like you're suggesting I hardcode a set of kinds of accessibility into the game engine? But that means modifying the engine if we come up with new ways of seeing / projecting. For example, if we want to add X-ray vision and lead walls, then we'd have to modify the base engine instead of just adding a new pair of functions for accessibility and augmented LOS. Feel free to correct me if I'm misunderstanding you.

[jdh]

What these kinds of algorithms want to operate on is a 2D array of booleans, that indicates if a cell is "open" (visible / accessible / etc.) or "closed" (obstructed). Call it an "accessibility array". So we have a function that accepts a list of Things in the tile and decides if the tile is open or closed. Where we run into trouble is when we try to do this every tick for every cell for every thing that needs to check accessibility. Imagine calculating LOS for 95 orcs when the player opens a pit. Every orc would need to check if the other 94 orcs block its view (not to mention the walls and the player) -- a naive algorithm would perform horribly. What we need, I believe, is a cache.

The cache will remember, for a given function, the status of the function's accessibility array. All of the orcs use the same sight function (being able to see through creatures but not walls), so they all use the same logic to determine if a given tile is blocked or not. Thus we need only compute accessibility once for each tile, instead of once for each tile for each orc;

Two more complicated examples come to mind:

1. Opacity: you might be able to see through a few orcs if you are only a few orcs back in the mob, but a crowd of 100? And what if you have mist, rain, smoke or fog? It would be cool if it could accumulate and have stages of effect: you see poorly 3 or 4 tiles away, hallucinations or mirages 4-10 steps away and nothing further than that...

2. Directionality: suppose you would like to have one-way mirrors that let you see into rooms but not out, or perhaps camouflaged entrances which monsters see out of but are difficult to see into?

[LostTemplar]

Maybe just have one value per tile, that determine it's accessiblity status (not just boolean, but also not too genral, e.g. lava is different from floor, etc.) Which is computed when and only when the given tile is modifyed, not when someone wants to look thru it.

[Derakon]

Okay, let's start picking up where we left off. Uh, which is where, exactly? I know Magnate is working on item generation and Fizzix is working on dungeon generation. I don't know if anyone else is tackling a major feature at the moment. Checking the To-Do List, it looks like the top things are:

1) Porting in effects from Vanilla (spell, item, and monster effects).
2) Limiting player knowledge (limited LOS; unidentified and partially-identified items)
3) Making creatures smarter (pathfinding)

I'd like to start on adding effects in. Some of these are straightforward -- anything that applies a (de)buff, for example, can be done right now with no further modification to the code. However, many spells require what Vanilla calls "projections" where a projectile needs to move across terrain. I believe the same system is also used to determine what has LOS on what. Both of these will need some efficient way to determine if a given tile is obstructed or not. And that in turn ties into pathfinding. So basically all three of these major features are related at some level.

In Vanilla, determining if a tile is obstructed is fairly straightforward: there's one terrain type and one monster per tile, and they either obstruct (sight/projection/movement) or they don't. Pyrel doesn't have that kind of simplicity -- there can be any number of Things in a tile (terrain, creatures, and more), and we might potentially want any number of them to act as an obstruction, so we'll need to be clever if we want calculations to be fast.

What these kinds of algorithms want to operate on is a 2D array of booleans, that indicates if a cell is "open" (visible / accessible / etc.) or "closed" (obstructed). Call it an "accessibility array". So we have a function that accepts a list of Things in the tile and decides if the tile is open or closed. Where we run into trouble is when we try to do this every tick for every cell for every thing that needs to check accessibility. Imagine calculating LOS for 95 orcs when the player opens a pit. Every orc would need to check if the other 94 orcs block its view (not to mention the walls and the player) -- a naive algorithm would perform horribly. What we need, I believe, is a cache.

The cache will remember, for a given function, the status of the function's accessibility array. All of the orcs use the same sight function (being able to see through creatures but not walls), so they all use the same logic to determine if a given tile is blocked or not. Thus we need only compute accessibility once for each tile, instead of once for each tile for each orc; the result can be compiled into an array and passed to the LOS computation function (which would need to run once for each orc). Moreover, so long as the contents of the tile do not change, we don't have to recompute its accessibility. We can use the same "dirty tile" logic we use in drawing the game map to determine which tiles need to have their accessibility re-checked (i.e. to flush cache entries). NB currently dirty tiles are tracked by the artists; that should be moved into the GameMap, probably.

So what this looks like, in practice, is that we have two sets of functions. The first set determines tile accessibility, and the second set makes use of the accessibility arrays. For example:

First set
1) Can see through tile
2) Can walk through tile (normal)
3) Can walk through tile (wallwalker)

Second set
A) Compute LOS
B) Pathfind to player
C) Fire projectile

Each function in the second set begins by requesting a specific accessibility array from the GameMap. It then does whatever it needs to do with that array (e.g. compute a path, or determine where a projectile stops). The first time the accessibility array is requested, it has to be computed for the entire map; from then on, incremental updates can be used instead. This should work well for most use cases I can think of; it's not ideal for functions that are used rarely (e.g. projectiles that can pass through glass walls), but those are used rarely, so their impact shouldn't be heavily felt.

When a new map is generated, every tile is dirty, of course. We can track accessibility functions that were used commonly on the previous level, and pre-emptively compute their accessibility arrays as part of new map generation, in a multithreaded manner so that they don't contribute excessively to level generation time.

Potentially we can let the second-set functions request subsets of the accessibility array. That would then save on the amount of dirty cells that would need to be recomputed -- you wouldn't have to do the entire map. I think this mostly only makes sense for projectile calculations, though, since those have a known maximum range (dependent on the projectile function). I don't know how much time it would save in practice, since at the very most there's only going to be a couple hundred or so dirty cells per player turn, right?

Does this all seem reasonable? Unreasonable? Am I overlooking anything?

[Derakon]

Quick note, folks -- Aerdan's IRC logs seem to be offline, so I can't guarantee I'll see anything you say to me. Might be best to do our asynchronous communication on the forum for the time being.

Magnate -- I see your pull requests, I'll try to get to them tonight but if I don't, tomorrow's looking pretty busy unfortunately.

[Patashu]

Ok, calc is now an order of magnitude slower than eval for common cases (although I would like to have it much faster!)

http://pastebin.com/U2iRBxqX

using timeit with 10000 repeats in the python interpreter:

calc("1")  0.0418998227178
eval("1")  0.0812901957397
1  0.000138238181535
calc("1+1")  0.576610918564
eval("1+1")  0.0973678084556
1+1  0.000208210600249
calc("1+2-3*4/5*6-7+8")  1.62794541196
eval("1+2-3*4/5*6-7+8")  0.184303583337
1+2-3*4/5*6-7+8  0.00143016787479

Outstanding issues:
1) How should it take in variables - should it take an object with them, a dictionary with them? Should it discard them after one calculation or only when you explicitly tell it? Should the calculator itself be an object, such that you garbage collect it when you no longer need its variables?
2) Should it always return a float? (It could try to determine if it is an int and return that instead. Or just return the string and let the caller decide.)
3) User defined functions?
4) Faster!

[Derakon]

@Derakon: I assume you'll be copying the instructional parts of previous dev log entries to said wiki at some point?

Good idea!

(They'll probably need some tweaking since they're "this is what I plan to do", not "this is what was done", but they'll make a good starting point)

[Magnate]

It's not necessarily just for fine-tuning rarities. I've crafted a very simple but efficient rarity system for a future version of Mist. I'm going to have only six different rarity lines for melee weapons, and perhaps for devices too:

A:0/55:12/30:24/0
A:0/40:24/10:36/10:60/0
A:0/5:12/40:60/0
A:0/0:12/5:24/40:60/10
A:12/0:36/40:60/20
A:36/0:60/70

As long as there are as many melee weapons of each rarity, melee weapons as a group will always be just as common, but your chances of finding better weapons increases slightly every time you take the stairs down.

You'll be able to replicate that in Pyrel using the "allocations" member of each object's definition.

I've cut and pasted my stream of consciousness to http://bitbucket.org/derakon/pyrel/w...m%20generation where it now precedes the more low-level code-related stuff. I was of course intending to write a 'proper' wiki entry on item generation when Pyrel 'went public' on rephial or its own site or wherever. Glad it was helpful.

@Derakon: I assume you'll be copying the instructional parts of previous dev log entries to said wiki at some point?

[Mikko Lehtinen]

I suppose we could make the "commonness" field be optionally a proc that calculates a value based on depth, if you really wanted to fine-tune things, but that hasn't yet been implemented.

It's not necessarily just for fine-tuning rarities. I've crafted a very simple but efficient rarity system for a future version of Mist. I'm going to have only six different rarity lines for melee weapons, and perhaps for devices too:

A:0/55:12/30:24/0
A:0/40:24/10:36/10:60/0
A:0/5:12/40:60/0
A:0/0:12/5:24/40:60/10
A:12/0:36/40:60/20
A:36/0:60/70

As long as there are as many melee weapons of each rarity, melee weapons as a group will always be just as common, but your chances of finding better weapons increases slightly every time you take the stairs down.

[Derakon]

Thanks, that was very informative!

Sounds like a very flexible system. I'm already imagining implementing Mist's weapon racks, closets and bookshelves with templates...

BTW, it would be nice to collect exactly that kind of explanations for a layman in a wiki. It would be immensely helpful for someone who wants to help with Pyrel or base a variant on it. Or perhaps include explanations in the beginning of text files in lib/edit?

Seconded that this should be on the wiki as a high-level overview of item generation. The current wiki is also good but gets into lower-level details pretty quickly. 1000'-views are also useful.

Unfortunately JSON doesn't allow for in-file explanations since they aren't valid JSON formatting. We're working on documentation for the data files, which will initially live on the wiki and eventually live in the data directory as well (once it stops changing so much).

In the Oangband system (also used in Halls of Mist, Sangband, FAangband), you can allocate up to four dungeon level/commonness pairs for base items. For example, rarity 10 for dungeon level 5 and rarity 50 for dungeon level 30. The system will smoothly increase the commonness as the player descends from 5 to 30. Can the Pyrel system do this?

Pyrel can have any number of allocation rules. They can even overlap; the game will choose the most generous rule. I suppose we could make the "commonness" field be optionally a proc that calculates a value based on depth, if you really wanted to fine-tune things, but that hasn't yet been implemented.

[Mikko Lehtinen]

Thanks, that was very informative!

Sounds like a very flexible system. I'm already imagining implementing Mist's weapon racks, closets and bookshelves with templates...

BTW, it would be nice to collect exactly that kind of explanations for a layman in a wiki. It would be immensely helpful for someone who wants to help with Pyrel or base a variant on it. Or perhaps include explanations in the beginning of text files in lib/edit?

The commonness of items can vary with depth, so an item might have commonness 10 at depths 1 to 50, and commonness 5 at 51 to 75, and then not appear at all below that.

In the Oangband system (also used in Halls of Mist, Sangband, FAangband), you can allocate up to four dungeon level/commonness pairs for base items. For example, rarity 10 for dungeon level 5 and rarity 50 for dungeon level 30. The system will smoothly increase the commonness as the player descends from 5 to 30. Can the Pyrel system do this?