search

diasurgical / devilutionX

Diablo build for modern operating systems
Other
8.01k stars 786 forks source link

Fix infinite loop in unique item randomization #7370

Closed obligaron closed 3 weeks ago

obligaron commented 1 month ago

I tried to create some debug items for testing (with dev.items.spawn) and sometimes I encountered an infinite loop in TryRandomUniqueItem.

After some debugging I found out that it is trying to generate one of the following unqiues

The problem can be reproduced with debug lua commands dev.items.spawnUnique command and one of the above uniques.

The cause was that the uid offset was not always calculated correctly. There are two reasons why this can happen

  1. The valid uniques in CheckUnique and TryRandomUniqueItem can be different because the check against UIMinLvl is different (CheckUnique calculates it with GetItemBLevel and TryRandomUniqueItem has a custom implementation). So the calculated offset can be different or the desired unique can't be generated by CheckUnique.
  2. When calculating the offset the check against UIMinLvl is == and not >= as in CheckUnique.

All this can only happen for some specific uniques or item levels, so the problem is not so easy to get in normal gameplay.

This PR

kphoenix137 commented 1 month ago

Hold that thought. I seem to have some uniques vanishing before I can reach them. Also it appears to be generating like vanilla. Let me test further.

kphoenix137 commented 1 month ago

Okay, so I was able to get some item drops, but the vanished from the ground before I could pick them up:

(Note: All the other uniques I've encountered so far have not vanished)

This was played in Nightmare, so some of these could legally drop even in vanilla. What it looks like to me is that the uidOffset being utilized is causing the items to be in an invalid state for "impossible items", although there are items that don't require uidOffset at all to be functional, although those items are vanishing as well. So far it does appear that I'm getting mostly "vanilla" style drops (last valid uid), and the ones that aren't last valid uid vanish.

obligaron commented 1 month ago

How do you generate the uniques? I tried to generate Bramble and Bleeder with spawnUnique command and they work (single player hellfire; can pick them up from ground and place them there again).

kphoenix137 commented 1 month ago

How do you generate the uniques? I tried to generate Bramble and Bleeder with spawnUnique command and they work (single player hellfire; can pick them up from ground and place them there again).

I'm forcing all monsters to take on unique monster status, then spamming chain lightning around the dungeon. I personally don't trust the debug command

kphoenix137 commented 1 month ago

With this PR logic:

https://github.com/user-attachments/assets/65e5cf78-5aec-45b1-aa75-77427f51070f

Current master logic:

https://github.com/user-attachments/assets/1ea15998-18c1-4409-b30d-099601569b24

Debug modifications: items.cpp L3381:

} else if (true || monster.isUnique() || dropsSpecialTreasure) {

L3415

    int uper = 15;

L3237

    item._iIdentified = true;
obligaron commented 1 month ago

Thanks @kphoenix137 🙂 I think I found the issue. The item position wasn't set correctly when the unique is (re)created.

This didn't matter in the debug commands, because the position was set after the TryRandomUniqueItem.

kphoenix137 commented 1 month ago

Thanks @kphoenix137 🙂 I think I found the issue. The item position wasn't set correctly when the unique is (re)created.

Thats funny. I remember having the same exact problem when coding this in the first place. I just forgot what the problem was until you mentioned that

StephenCWills commented 1 month ago

You left your debug code in.

kphoenix137 commented 1 month ago

Bad news, nearly all the uniques I picked up morph in vanilla (Specifically most of the ones I was picking up were previously on the "vanish" list, so those are the ones being recreated). Are you utilizing uidOffset for more than just the "impossible" uniques? If so, that will certainly break reverse compatibility. uidOffset was introduced as a workaround to allow the impossibles to exist in DevilutionX without morphing on regeneration, and allow them to be moved to vanilla where they would inevitably morph, but still change back into what they were found as when returning to DevilutionX.

The code for selecting a target level was introduced in order to create reverse compatible uniques, as we would first select the uid we want, and then brute force search using target item data to find that unique, that doesn't exactly match the source of the drop, but it successfully allows us to create stable uniques that won't morph in vanilla. The idea was to take advantage of the fact vanilla always selects the last applicable uid, so we'd select a target level that makes sure that the desired uid is the last in the list.

kphoenix137 commented 1 month ago

I just tested forcing all monsters as unique monsters and forced the War Hammer as the selected idx for every drop, and I was able to successfully get Schaefer's Hammer to drop in the latest master. Maybe there's something wrong with the debug command for generating these uniques?

Edit: Back again, I got an infinite loop in Single Player Hellfire. I'll see what happens in Single Player Diablo

Edit: No infinite loop in SP Diablo

Edit: Infinite loop in SP and MP Hellfire. Looking into it.

kphoenix137 commented 1 month ago 
INFO: SetupAllItems: iblvl: 34
INFO: CheckUnique: (Schaefer's Hammer) Checking if lvl (34) is at least UIMinLvl (16)
INFO: CheckUnique: Added uid 52 to valid uniques vector
INFO: CheckUnique: Added uid 102 to valid uniques vector
INFO: CheckUnique: Selected uid: 102
INFO: TryRandomUniqueItem: Made it past return. Item is Unique, and item is a not a quest unique
INFO: TryRandomUniqueItem: Item._iUid (should be non-zero): 102
INFO: TryRandomUniqueItem: Item._iCreateInfo & CF_UNIQUE: 512
INFO: TryRandomUniqueItem: Item._iMiscId: 0
INFO: TryRandomUniqueItem: Item._iMagical: 2
INFO: TryRandomUniqueItem: We selected new uid: 102
INFO: TryRandomUniqueItem: The new uid matches the old one, returning.

Here, the vanilla algorithm picked Thunderclap, and then TryRandomUniqueItem() also picked Thunderclap, so it didn't need to regenerate.

INFO: SetupAllItems: iblvl: 31
INFO: CheckUnique: (Schaefer's Hammer) Checking if lvl (31) is at least UIMinLvl (16)
INFO: CheckUnique: Added uid 52 to valid uniques vector
INFO: CheckUnique: Added uid 102 to valid uniques vector
INFO: CheckUnique: Selected uid: 102

Vanilla algorithm decides again that it's a Thunderclap.

INFO: TryRandomUniqueItem: Made it past return. Item is Unique, and item is a not a quest unique
INFO: TryRandomUniqueItem: Item._iUid (should be non-zero): 102
INFO: TryRandomUniqueItem: Item._iCreateInfo & CF_UNIQUE: 512
INFO: TryRandomUniqueItem: Item._iMiscId: 0
INFO: TryRandomUniqueItem: Item._iMagical: 2
INFO: TryRandomUniqueItem: We selected new uid: 52
INFO: TryRandomUniqueItem: Potential uper adjustment. uper is: 15
INFO: TryRandomUniqueItem: uidOffset: 0

At this point, TryRandomUniqueItem() decides instead of Thunderclap, we're going to drop Schaefer's Hammer, with no uidOffset and keeping the item at uper15.

INFO: TryRandomUniqueItem: Forcing item generation until we find a match.
INFO: SetupAllItems: iblvl: 16
INFO: TryRandomUniqueItem: item._iUid 0 is not equal to desired uid 52, roll again
INFO: TryRandomUniqueItem: Forcing item generation until we find a match.
INFO: SetupAllItems: iblvl: 16
INFO: TryRandomUniqueItem: item._iUid 0 is not equal to desired uid 52, roll again
INFO: TryRandomUniqueItem: Forcing item generation until we find a match.

This repeats for a bit as it's selecting non-uniques.

INFO: SetupAllItems: iblvl: 16
INFO: CheckUnique: (Schaefer's Hammer) Checking if lvl (16) is at least UIMinLvl (16)
INFO: CheckUnique: Added uid 52 to valid uniques vector
INFO: CheckUnique: Added uid 102 to valid uniques vector
INFO: CheckUnique: Selected uid: 102

We finally roll a unique, but CheckUnique() selects Thunderclap. Both uniques are available. Since the lvl being passed is 16, naturally this should mean it would pick Schaefer's Hammer, however Hellfire added uniques that made the table no longer chronological, so instead of picking Schaefer's Hammer with a min level of 16, it picks Thunderclap with a min level of 13.

INFO: TryRandomUniqueItem: item._iUid 102 is not equal to desired uid 52, roll again
INFO: TryRandomUniqueItem: Forcing item generation until we find a match.
INFO: SetupAllItems: iblvl: 16
INFO: TryRandomUniqueItem: item._iUid 0 is not equal to desired uid 52, roll again
INFO: TryRandomUniqueItem: Forcing item generation until we find a match.
INFO: SetupAllItems: iblvl: 16
INFO: TryRandomUniqueItem: item._iUid 0 is not equal to desired uid 52, roll again
INFO: TryRandomUniqueItem: Forcing item generation until we find a match.
INFO: SetupAllItems: iblvl: 16
INFO: CheckUnique: (Schaefer's Hammer) Checking if lvl (16) is at least UIMinLvl (16)
INFO: CheckUnique: Added uid 52 to valid uniques vector
INFO: CheckUnique: Added uid 102 to valid uniques vector
INFO: CheckUnique: Selected uid: 102

As expected, it continues on and on like this. I truly didn't anticipate this happening as I was testing in Diablo. Maybe you already explained this, but the original post seems overly technical for my understanding. :(

AJenbo commented 3 weeks ago

Nice work, infinite loops are terrible