Shop Spawn

From DDwiki
Jump to: navigation, search

This page elaborates the algorithm used to populate the Item shops. It can get a bit mathsy, though understanding the algorithm can help also to understand (and possibly improve) the odds of finding certain items. Also, for the D.E.R.P. challenges there is an additional consideration: given the uniform daily seed given to all players, the item spoilers sometimes posted on the "qcfdesign forums" can be used to predict how certain preparations will impact the shops' item pools. For new players, this page is probably a bit too much.

The Algorithm

The shop algorithm in a nutshell is:

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 interval [0, 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 contains all items (as would be the case for a kingdom which has unlocked every item, and does not veto any), and follows the same logic as non-Daily runs, i.e. 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, as well as any shop items picked for any 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.

The Item Lists

Each of the three item lists follow a specific sequence. So for example, the 8 basic items have an intrinsic ranking that gives their relative position within the "Basic Items" list; this intrinsic ranking never changes. So if the Item: Pendant of Health Pendant of Health is always the first item on the Basic Items list, it will remain so even if the list itself is moved down due to Quest Items / Elite Items preparations. Consequently, if no items are vetoed (or in a DERP), the Health Pendant will be the 1st, 9th, 23rd or 31st item in the list (depending on whether neither Quest Items or Elite Items are prepped; only Elite Items is prepped; only Quest Items is prepped; or both Elite and Quest items are prepped).

The below chart shows the five possible itemlists (depending on which item group preparations are taken):

Itemlist.PNG

The logic is, each item retains its intrinsic ranking within its item group; if neither Quest or Elite Items are prepared, the default order followed is Basic Items, then Quest Items, then Elite Items; if either item group preparations is used, it places the given item group at the start of the list, which is then followed by Basic Items and then the remaining item group; if both item group preparations are used, the prep order sequence is followed, putting first the group in the lower prep slot; then the group in the higher prep slot; and finally the remaining Basic Items.

D.E.R.P. relevance

The random seed for the Daily contains a pre-selected shop item index list. However, which items will actually appear in the shops can change completely in light of what preparations are selected by each player for the given daily. It is important to note that even if a player posts complete item spoilers about their run, another player will only get the same items if he takes the same preparations. Relevant preparations:

  • Preparations "Quest Items" and "Elite Items" will alter the item list and so the same index will yield a different item;
  • Taking any of the 38 possible shop items as preparations may shift some of the indexes, as the random seed's floating point numbers may be rounded differently if fewer (or more) items are available;
  • The Item: Shop Scroll Shop Scroll spawns an additional shop, again with a pre-determined item index;
  • Any preparation that impacts the starting area - prepared altars, the Smuggler Den subdungeon - may also change the location of the shops, so although it will not change the overall items available, it may change which items appear in which shops.

In light of the above explanations on how the item lists are populated, it is therefor possible to predict the impact of some preparations on the available items. Some rules of thumb:

  • If you prepare the same *number* of shop items, you can predict with certainty how Quest/Elite Items impact the shop items, because then the item indexes are the same, only modified by the item group preparations, and the rank of the items prepared (which are removed from the list before generating the shop items).
  • If you prepare *fewer* shop items, some items may "slide up" (i.e. give you the previous item in the list instead).
  • If you prepare *more* shop items, some items may "slide down" (i.e. give you the next item in the list instead).
  • On top of potentially changing the indexes as mentioned above... Any prepared shop items will reduce all lower indexes by one. This is because the item is pulled from the item list before the indexes are applied to it, and since the item indexes count backwards (i.e. from the end of the item list), the same count will yield one lower index.
  • So the *number* of shop item preparations taken will influence the basic indexes (this is an alteration that cannot be accurately predicted, because it will depend on the rounding of the original randomly generated numbers); but which specific items are prepared, and which item group preparations are taken, will influence which items each index picks up (this can be predicted with complete accuracy). {verification needed}

Vetoing Items

Bazaar offers the possibility to veto up to 7 shop items (tying 4 slots to completing all the Class Challenges of each main guild, and 3 additional slots can be purchased in the Bank). Any items vetoed will be removed from the initial item lists before the master list is assembled based on the item group preparations. This allows a degree of control over the relative position of each item within its item group list; combined with the item group preparations Elite/Quest Items, the chances of finding certain specific items can be greatly increased. Important to note that your kingdom's Veto slots (or unlock progress, for that matter) does not impact the item lists for D.E.R.P.s! The Dailies always use the full item list (i.e. everything unlocked, nothing vetoed).

If you want to increase the likelihood of finding specific items in your dungeon runs, on top of picking the right Bazaar preparation (Quest/Elite Items if you're looking for items belonging to those groups, or Shop Scroll if you're looking for Basic Items or a combination of items from different groups), vetoing higher-ranked items (i.e. those with lower indexes) helps the most. Vetoing lower-ranked items (i.e. those with higher indexes) may or may not help, depending on the relative initial position of the item you want; as a rule of thumb, if your item is among the top 2/3 of items (this is normally a given if you could pick the relevant item group preparation), then your chances also improve a bit if you veto lower-ranked items; however, items in the bottom 1/3 of the list will actually have their chances to be found *reduced*, if items below them are vetoed!

For example, let's say you want to increase your chances of finding the Item: Vampiric Blade Vampiric Blade item in a fully-unlocked kingdom, assuming 8 stores.

  • Without any preparations or vetoes, you will have 27.2% chance to find it.
  • If you prepare Shop Scroll, the chance goes up to 30.6%.
  • If you prepare Quest Items, the chance increases to 33.9%.
  • On the other hand, if you prepare Elite Items, your chances diminish to 19.6%.

So the optimal Bazaar preparation is Quest Items, which can boost your chances by 6.7%. Vetoing items:

  • If you prepare Quest Items and veto the higher-ranked five Quest Items (Fire Heart, Hero's Helm, Battlemage Ring, Venom Dagger, Whurrgarbl), your chances go up to 42.6%; adding two more vetos (to reduce number of items) also helps, getting you 45%.
  • If you want to play purist, you can still veto items to help your odds. In this case, vetoing as many as possible Basic Items and/or some of the five quest items mentioned above helps the most. You get a 38.7% chance this way if you veto 7 items, so actually better than just with quest items prep without any vetoes.

Selective Unlocks

You may choose not to unlock certain items in your kingdom. These items will then never appear in shops, however, this may improve the chances of finding other items. A word of advice: do not do this for your first kingdom; every single shop item is good for something (and outright awesome for some specific runs), and learning to use each item greatly improves your skill as a Desktop Dungeons player. It can be, however, a fun way to "rig" the shop pool of a subsequent / alternative kingdom, greatly improving the odds of certain items.

Unlocking Elite Items is tied to the Bazaar upgrade and happens in a batch; and doing so also gives 2 extra shops and opens up the Quest/Elite Items preparations (as well as the possibility to have veto slots at all). Add to this that due to the square-root formula used to populate the shops, Elite Items will normally appear very infrequently, the net result is, that there is virtually no benefit in not upgrading Bazaar to Level 3 as soon as possible.

That said, since Quest Items can be unlocked individually, there is a lot of leeway to exercise selective unlocks by picking & choosing which quests you do. To illustrate the impact on probabilities, let's assume that in an alternate kingdom you only have a single Quest Item unlocked, the Item: Vampiric Blade Vampiric Blade. Assuming Level 3 Bazaar and 8 shops, the odds to find it in a shop is:

  • You have a base 52% chance to find it in store.
  • Preparing Quest Items improves the chance to 72%.
  • Having some items vetoed (maximum 3 is possible without the other class challenges) helps a bit, pushing chances up to 81.6% if you have prepped Quest Items.
  • If you play purist, vetoing 3 Basic Items gives you 69.8% chance (almost as good as the Quest Items prep).

Needless to say, as different builds/maps/runs require different items, and it is very true that no item is overall weak, it is very difficult to use selective unlocking for anything other than a refreshing experience. Even though individual item chances can be increased this way, it pretty much commits the whole kingdom to this specific "rig", whereas a fully upgraded kingdom can use a combination of 1) re-shuffled veto slots, 2) proper item group preparation, and 3) lots of available gold being able to fuel many attempts, to eventually guarantee finding the right item(s) for any run.

Also, needless to say, there are very few maps/challenges in Desktop Dungeons that would even require the player to think about rigging shops. Everything can be won in the game without ever worrying about this.

External Links

[1] is a handy tool to calculate individual item probabilities for virtually any scenario.