Angband.oook.cz
Angband.oook.cz
AboutDownloadVariantsLadderForumCompetitionSpoilersComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Vanilla

Reply
 
Thread Tools Display Modes
Old October 7, 2011, 04:15   #1
bulian
Adept
 
Join Date: Sep 2010
Posts: 161
bulian is on a distinguished road
3.3 artifact generation

This is a little long and a little dense. Apologies.

Recently I've spent some time thinking about the change to object generation, specifically that monster inventories are created when monsters are generated. I've concluded that the change has a side effect of suppressing effective late game artifact generation.

For example, consider a DL90 with a demon pit with horned reapers and a greater vault. I'm not sure the exact dungeon generation algorithm, but lets say the pit is generated and populated before the GV. It doesn't matter much either way. Also, lets say a lesser balrog is generated with Nenya in its inventory. Nenya can no longer be generated on a special item floor squares. Furthermore, any monster generated after the lesser balrog has a 0% chance to yield Nenya. Since this an extreme example with horned reapers, the likelihood of a lesser balrog not being trampled AND the likelihood of the player choosing to clear that patricular pit are very small. Thus, the effective probability of finding Nenya on that level is 0.

To generalize this, lets say the chance a given monster is generated carrying Nenya is P_gen. Whether the item is created when the monster is generated or when the monster is killed shouldn't effect P_gen. Lets say the chance the player kills a monster ion a given level is P_kill.

Previously the effective chance to find Nenya per monster on a given level was P_gen, whereas now the chance is P_gen*P_kill. P_kill will inevitably be <1, so P_gen*P_kill < P_gen. Thus, the effective chance of finding Nenya on a level is reduced and depends strongly on playing style. This effect is compounded when considering graveyards and pits.

Graveyards and pits have a high concentration of deep monsters, which means the chance a monster in a graveyard or pit is generated with an artifact is higher relative to the rest of the dungeon. As monster density contributes to the difficulty of clearing the monsters, P_kill for monsters in graveyards, demon pits, and dragon pits with complex compositions is lower than P_kill for monsters scattered throughout the dungeon. Or, more directly, levels generated with these features are less likely to yield end game artifacts.

This behavior implies tuning rarity for late game artifacts is more difficult to control than editing a rarity index in a .txt file. I'm not sure the current behavior is ideal, but I don't have a suggestion except to consider reversion to item generation upon monster death and not monster generation.
bulian is offline   Reply With Quote
Old October 7, 2011, 04:28   #2
fizzix
Prophet
 
Join Date: Aug 2009
Location: Madison, Wisconsin, US
Posts: 2,614
fizzix is on a distinguished road
Your analysis is accurate. However, the problems are not relevant provided that (p_gen per item) * (number of items) << 1. We operate in this limit, so I think we're ok.

Essentially the argument goes like this. Let's say the prob of producing artifact A is 1/100,000 (it's actually likely to be a lot smaller) and there are 1000 items generated on the level (about the most crowded level imaginable) that have the possibility of becoming artifact A. Then overall, there's a 1% chance that artifact A can be created. (1000/100,000) However, we want the probability that artifact A is suppressed from being recreated. So we need the probability that artifact A is created twice, which is. (1000/100,000)*(999/100,000) < 0.01%. So essentially 1/10000 times you miss out on artifact A because of items being created in monster drops. I'm ok with this.

As long as we stay with ratios of 0.01 for (prob_per_item)*(number of items) we shouldn't run into any serious problems. Hopefully this made sense?
fizzix is offline   Reply With Quote
Old October 7, 2011, 04:54   #3
Timo Pietilš
Prophet
 
Join Date: Apr 2007
Location: Climbing up from hole I just dug.
Posts: 3,456
Timo Pietilš is on a distinguished road
Quote:
Originally Posted by bulian View Post
This is a little long and a little dense. Apologies.

Recently I've spent some time thinking about the change to object generation, specifically that monster inventories are created when monsters are generated. I've concluded that the change has a side effect of suppressing effective late game artifact generation.

For example, consider a DL90 with a demon pit with horned reapers and a greater vault. I'm not sure the exact dungeon generation algorithm, but lets say the pit is generated and populated before the GV. It doesn't matter much either way.
It does, if the GV floor is generated before monsters, then floor item generation is not affected by monster inventories. Your example about unkillable monster on level is valid though. If that monster carries the "valuable unique item", then nothing else can get it. OTOH trampling in this case is your friend. It frees the artifact back in the circulation, and any monster spawned after can again carry it, summons included.

I'd say effect is small as long as floor item generation is done before monster inventory generation (otherwise the Demon-pit in same level with GV probably does impact GV items).
Timo Pietilš is offline   Reply With Quote
Old October 10, 2011, 19:01   #4
bulian
Adept
 
Join Date: Sep 2010
Posts: 161
bulian is on a distinguished road
Apologies on letting this stagnate. Work is consumingly busy currently.

Quote:
It does, if the GV floor is generated before monsters, then floor item generation is not affected by monster inventories.
So it does, so it does. I would be curious whether this is the case?

Quote:
So we need the probability that artifact A is created twice, which is. (1000/100,000)*(999/100,000) < 0.01%.
If this were the case then its probably not a big deal - however, I think that maybe the % chances for artifact generation aren't quite so simple. FWIW, I estimated bulk artifact generation to be ~0.4% of loot in a game, but I didn't back calculate what that owuld be per artifact (assume 150 floors, 30 items per floor, 7000 monsters killed, 2 items per monster, 70 artifacts found), which isn't too far off from your estimate, but I think the devil is in the details.

My understanding from threads you wrote is that item generation goes:

generate base item -> roll for ego -> roll for artifact

with monsters having "good" and "great" tags getting reduced lists of items to choose from and additional rolls for item generation. So the odds of getting an artifact from these monsters is significantly higher than a monster without the tag. I checked a few monsters, and wyrms, lesser balrogs, demilichs (e.g. monsters likely present in deep pits/graveyards) have the drop good tag. Should artifact generation ever go to completely random and not be base item dependent, I would completely agree with you. As it stands, I'm still not completely convinced but I have no means to test.

Anyway, I thought of a not so complicated solution. If the roll for artifact generation were performed upon monster death, stat generation would not be effected (same number of random numbers generated per level), artifact generation would not be inadvertently reduced/prevented, and vault loot would not be affected regardless of dungeon generation order.
bulian is offline   Reply With Quote
Old October 10, 2011, 20:07   #5
fizzix
Prophet
 
Join Date: Aug 2009
Location: Madison, Wisconsin, US
Posts: 2,614
fizzix is on a distinguished road
Quote:
Originally Posted by bulian View Post

generate base item -> roll for ego -> roll for artifact

with monsters having "good" and "great" tags getting reduced lists of items to choose from and additional rolls for item generation.
Essentially that's correct. It's subtracting the roll for special artifacts, which is a mess in its own right.

Quote:
So the odds of getting an artifact from these monsters is significantly higher than a monster without the tag. I checked a few monsters, and wyrms, lesser balrogs, demilichs (e.g. monsters likely present in deep pits/graveyards) have the drop good tag. Should artifact generation ever go to completely random and not be base item dependent, I would completely agree with you. As it stands, I'm still not completely convinced but I have no means to test.
This is essentially correct as well. The odds go up a bit for drop_good monsters but not by a huge amount. drop_great is where it's at, those monsters have 4 artifact rolls instead of 1. However, a lot of this, maybe all, is getting overhauled in 3.4. With stats testing we can verify how many things are generated to make sure the actual gameplay isn't bad, while simultaneously simplifying the generation.

I know magnate's been working on it, and maybe in a couple weeks or so he'll have something playable. Truthfully, I'm pushing for artifacts to be rarer, so I'm unlikely to favor changes that make them more common.

Quote:
Anyway, I thought of a not so complicated solution. If the roll for artifact generation were performed upon monster death, stat generation would not be effected (same number of random numbers generated per level), artifact generation would not be inadvertently reduced/prevented, and vault loot would not be affected regardless of dungeon generation order.
I don't really like this, because it adds a layer of complexity to the object generation code. Also, let's say the odds of missing an artifact in a game due to attacking the wrong monster are higher, mabye 10% or even 20%. I'm not seeing the specific problem. You find 1-3 less artifacts than you otherwise would (or that stat generation predicts). That seems fine to me.
fizzix is offline   Reply With Quote
Old October 11, 2011, 03:26   #6
bulian
Adept
 
Join Date: Sep 2010
Posts: 161
bulian is on a distinguished road
Quote:
Truthfully, I'm pushing for artifacts to be rarer, so I'm unlikely to favor changes that make them more common.
I would consider overall artifact rarity to be a related but separate topic compared to this one.

Quote:
I'm not seeing the specific problem. You find 1-3 less artifacts than you otherwise would (or that stat generation predicts). That seems fine to me.
Sure, this may be a minor bug but I would still consider it a bug. If either item generation is going to be completely revamped anyway or the dev team is OK with systemic error in stats generation, than there's there no need to fix it. I'm a little surprised at the latter given how precise you are in other posts - e.g. native depth of wyrms being deeper than dracoliches/dracolisks. If you acknowledge the current behavior adversely affects melee-weak classes more than melee-strong classes, I'll be satisfied - occasionally I will clear a graveyard or demon pit with a warrior, but I wouldn't touch them with a mage.

I can currently only report what I see as a bug and do not have the time or skill to contribute more than that.
bulian is offline   Reply With Quote
Old October 11, 2011, 16:37   #7
Max Stats
Swordsman
 
Join Date: Jun 2010
Posts: 324
Max Stats is on a distinguished road
If I understand correctly, we are trying to reduce the odds that an overpowered monster that a player wants to avoid gets a desirable artifact in its inventory and blocks it from being generated elsewhere.

IMHO if we just make sure that floor items are generated before monster inventories, as mentioned by a previous poster, it does enough to alleviate the problem without over-complicating the generation algorithm.

The generation order could be further fine-tuned if it gives a good cost/benefit ratio:
  • Monster inventories could be generated in order from lowest to highest level. This would keep OOD monsters from blocking in-depth monsters from getting artifacts.
  • Order of generation for objects on vault floors and in vault monsters' inventories could be tweaked either way, depending on the logic we want to use (vaults should have first opportunity at good items vs. not wanting to penalize players for not taking on a seriously overpowered vault).
  • Pit monsters' inventories seem like they should be late in the order, just because of the number of monsters involved.
These tweaks could alleviate, although not completely solve, the problem without getting into too much extra overhead.
__________________
If beauty is in the eye of the beholder, then why are beholders so freaking ugly?
Max Stats is offline   Reply With Quote
Old October 11, 2011, 18:40   #8
fizzix
Prophet
 
Join Date: Aug 2009
Location: Madison, Wisconsin, US
Posts: 2,614
fizzix is on a distinguished road
I need to check specifically, but I'm pretty sure items and monsters are created at roughly the same time in pits and vaults, where the problems arise.

The generation algorithm looks like this:

Code:
1) Make rooms.  For each room do the following

2) If (vault){
   2a) Make all items on "*" squares
   2b) Make &,@ (monster squares) and 8,9 (monster + treasure squares)
      monsters are made before treasures
   }
3) If (pit/nest){
   3a) Make objects
   3b) Make monsters with drop
   }
4) If (special room, i.e. moated rooms){
   4a) Make monsters
   4b) Make objects
   }

After all rooms are finished
5) Place objects in rest of rooms
6) Place monsters in rest of rooms
So it's trivial to place objects before monsters in pits/nests/special rooms. It's a bit harder in vaults. And it's difficult to do it globally over an entire level. Not impossible, but it would involve some significant rewrite of the generation code. Specifically, it would require deferring giving monster drops until all the level has been fixed and then go through the monster list and make all the drops. Possible, but not trivial.

As far as inaccuracy of stats goes, the statistics are never really meant to mimic an actual play style. They're not really absolute. However, they are useful in comparison. The idea is, if you want to tweak object generation, you'll want to know what the change produces.

So let's say the average stats run has a player get 70 artifacts. After a change in artifact generation it becomes 63, a 10% reduction. A patient player might get 100 artifacts, a less patient one only 40. However, the change will probably give close to a 10% reduction in artifacts for both players. This is where stats shines, and is useful for development.

The actual question of "are artifacts too common" can really only be answered by player input. What stats can say is whether artifacts are more or less common than before some object generation change. Does that make sense?
fizzix is offline   Reply With Quote
Old October 11, 2011, 19:10   #9
Timo Pietilš
Prophet
 
Join Date: Apr 2007
Location: Climbing up from hole I just dug.
Posts: 3,456
Timo Pietilš is on a distinguished road
Quote:
Originally Posted by fizzix View Post
Specifically, it would require deferring giving monster drops until all the level has been fixed and then go through the monster list and make all the drops. Possible, but not trivial.
I think this is worth doing even if it has only small overall effect on gameplay now, because it makes predicting effects of changes in item rarities a bit easier. Floor drops and monster drops as completely separate processes. It really doesn't matter which order it is done as long as it is separate process.

Anything that makes understanding the logic behind what happens easier is welcome. Monster drop determination for artifacts etc. is real mysterious art for me. A flowchart of some kind could make the process easier to understand, and also could make easier to see if there is some oddity that needs to be fixed.
Timo Pietilš is offline   Reply With Quote
Old October 12, 2011, 01:55   #10
buzzkill
Prophet
 
buzzkill's Avatar
 
Join Date: May 2008
Location: Indiana, USA
Posts: 2,910
Donated: $8
buzzkill is on a distinguished road
Shouldn't high end items and artifacts be carried, rather than lying on the floor, and shouldn't the best stuff be carried by the strongest/OoD enemies available on the level? Am I reading this wrong, or are we discussing the exact opposite?
__________________
www.mediafire.com/buzzkill - Get your 32x32 tiles here. UT32 now compatible Ironband and Quickband 9/6/2012.
My banding life on Buzzkill's ladder.
buzzkill is offline   Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Artifact generation: some interesting stats PowerWyrm Vanilla 26 June 20, 2011 18:34
New level generation Timo Pietilš Development 28 June 20, 2011 00:40
Item generation suggestion Timo Pietilš Development 58 June 18, 2010 13:45
Object generation in 3.1.2 PowerWyrm Vanilla 4 May 7, 2010 22:08
item generation bron Vanilla 21 November 25, 2009 06:55


All times are GMT +1. The time now is 06:58.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2014, vBulletin Solutions, Inc.