[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 120: preg_filter(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 120: preg_filter(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 120: preg_filter(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 120: preg_filter(): The /e modifier is no longer supported, use preg_replace_callback instead
QCF Design Community • View topic - Ok, so how does the shop algorithm actually work?


Ok, so how does the shop algorithm actually work?

All things Desktop Dungeons

Ok, so how does the shop algorithm actually work?

Postby Tinker on Tue Nov 24, 2015 5:07 pm

So I had a casual run today. My shop pool was: 3 elite items, and 5 basic items (and zero quest items). The catch: I prepared the "Quest Items" Bezaar preparation! I have been feeling quite clueless regarding the shop pool especially in the context of the dailies, and so I'm now trying to pay closer attention to what spawns, and well I'm even more clueless than I was before... ;)

Does anyone have any idea how the shop pool is populated? Any experiments / educated guesses / generous developer infoshare? :P I did some searching and found an old post by Wald0, saying he was doing repeat runs to document item drop rates, but I don't think he ever publicly shared anything...

It would be so cool to know at least rule of thumb probabilities of what governs shop spawn... :roll:
"Thinker", just without the "ache".
User avatar
Tinker
 
Posts: 2000
Joined: Fri Oct 31, 2014 8:51 am

Re: Ok, so how does the shop algorithm actually work?

Postby Darvin on Tue Nov 24, 2015 5:14 pm

I guess you could do a whole bunch of Transmuter in Venture Cave runs to figure out the frequency of different items. Would certainly make it easier if dislekcia just dropped the algorithm on our head like we got with Jehora Jeheyu's boredom scheme.
User avatar
Darvin
 
Posts: 4355
Joined: Thu Jun 02, 2011 1:44 am

Re: Ok, so how does the shop algorithm actually work?

Postby Tinker on Tue Nov 24, 2015 5:20 pm

"Thinker", just without the "ache".
User avatar
Tinker
 
Posts: 2000
Joined: Fri Oct 31, 2014 8:51 am

Re: Ok, so how does the shop algorithm actually work?

Postby William on Tue Nov 24, 2015 6:19 pm

"Because Goatperson"
User avatar
William
 
Posts: 719
Joined: Tue Jun 16, 2015 10:52 am
Location: Port Elizabeth, South Africa

Re: Ok, so how does the shop algorithm actually work?

Postby Phoil on Wed Nov 25, 2015 11:11 am

Here's an unofficial description of the algorithm. This description may contain errors. Let me know if anything here doesn't match your experience.

1. Start with a list of all potential items.
2. If quest or elite preparations are chosen, then move those items to the front of the list.
3. Remove prepared inventory items from the list.
4. Let the length of the list now be n.
5. Generate a random number in the range 0 to n^2.
6. Take the square root of that number, round down, and subtract from n-1.This is the index of the chosen item.
7. Remove the chosen item from the list.
8. Repeat steps 4-7 for each additional shop.

For normal dungeon runs, the potential item list is created by adding basic items, then unlocked quest items, then elite items.

For the DERPs, the potential item list is a fixed list containing all items, but the basic items are still at the start, and elite items at the end. For a given DERP seed and a given length n, the generated random numbers will be identical, but the chosen items depend on the order of the list as affected by preparations. If both quest and elite preparations are chosen, then whichever was last in the available preparations will be at the front of the list.
Phoil
 
Posts: 19
Joined: Thu Sep 03, 2015 10:06 am

Re: Ok, so how does the shop algorithm actually work?

Postby Gakato on Wed Nov 25, 2015 12:10 pm

Yep, I agree that is how the shop pool is generated. Kudos to you to make it comprehensible! :) I had a quick look at it already yesterday, but had not enough time to find out how the potential item list was generated. :)

The whole point is that the first items in the list have a higher probability to be chosen, while the last items have the lowest probability. So by reordering the list you are changing probabilities. However, when the random number is seeded, all chosen positions are "fixed". Assuming the same amount of basic, quest, and elite items, this means that when preparing quest items, all basic items are replaced with quest items, and the quest items with basic items.
However, this also means that you may have moved your Amulet of Yendor out of the picked "slot" in another not chosen "slot", though that slot would be more likely to be chosen (when it is randomly picked with a fresh seed).
Gakato
 
Posts: 118
Joined: Mon Dec 30, 2013 10:31 pm

Re: Ok, so how does the shop algorithm actually work?

Postby dislekcia on Wed Nov 25, 2015 12:27 pm

Yup. That's how it works.

We didn't want to mandate X items of a specific type if Quest or Elite items were prepped, mostly because that ruins the fun of finding new shops as you explore: Oh, I've found my 2 elite items this run and they're not what I was hoping for, time to scum more! vs Any shop I find could have an elite that I'm looking for!

Also, the different item lists can be very different lengths, this was a cleaner solution than having all sorts of fall-through cases if you didn't have enough quest items, for instance.
User avatar
dislekcia
 
Posts: 2321
Joined: Fri Mar 25, 2011 5:58 pm
Location: Cape Town, South Africa

Re: Ok, so how does the shop algorithm actually work?

Postby Tinker on Wed Nov 25, 2015 1:30 pm

Wow, thanks for the responses! :) I'll try to wrap my mind around the formula a bit later. ;)

So basically, the bottom line is:
1. It is technically possible to have very weird item spreads. Like the one where I got zero quest items despite prepping them. Though this should be very rare (it means, RNG chose 8 small numbers, and no big numbers).

2. In the context of the Dailies... Taking either Quest or Elite items prep basically totally re-randomizes the shop pool, and there will be no guarantee that anything you had before in the pool will still be there. The only exception is, if you take Quest Items prep (but not Elite Items), any Elite Items in the shop pool should stay there untouched.

3. However! Prepping any item effectively changes the number of items in the list, which will change "n", so the same pure random number may round to a different integer. So even doing something innocuous as preparing a Spoon may mean that the whole shop pool gets altered. Exception: taking the same number of item-preparations, of the same group(s), means that any preceding groups will for sure be the same. So for example, if I take Quest Items and Spoon preparation, and someone else takes Quest Items and Dwarven Gauntlets preparation, we are guaranteed to get the same Quest Items (as our list is the same length, and Quest Items are at the front), but there is no such guarantee for the Basic or Elite items, as any "hits" between the ranks of the Spoon I took, and the Gauntlets the other player took, will be moved up one rank. However, if the other player takes Fine Sword instead of the Gauntlets, we are again guaranteed to get the same Elite Items, as our preps can only "mess up" the ranks within the Basic Items range.

Right? :?
"Thinker", just without the "ache".
User avatar
Tinker
 
Posts: 2000
Joined: Fri Oct 31, 2014 8:51 am

Re: Ok, so how does the shop algorithm actually work?

Postby Tinker on Wed Nov 25, 2015 1:40 pm

"Thinker", just without the "ache".
User avatar
Tinker
 
Posts: 2000
Joined: Fri Oct 31, 2014 8:51 am

Re: Ok, so how does the shop algorithm actually work?

Postby Darvin on Wed Nov 25, 2015 6:10 pm

User avatar
Darvin
 
Posts: 4355
Joined: Thu Jun 02, 2011 1:44 am

Next

Return to Desktop Dungeons

Who is online

Users browsing this forum: No registered users and 73 guests