devilutionX
devilutionX copied to clipboard
diasurgical
Unique Item Generation Bug (with possible fix)
Hello! The unique item generation bug in Diablo has always bothered me, so I made an attempt to fix it. I thought I would share this information here in hope that it can aid others in possibly coming up with a more elegant solution. For those not familiar with the bug, unique items with the same base type and ilvl, only one ever spawn in multiplayer games. Even if you were to hack the item into your inventory, it would morph once you started a new game.
There's actually three parts to the bug, therefore three changes are required to get it working correctly.
Fix 1 - Fix UniqueItemList in itemdat.cpp so that there are no UIItemId and UIMinLvl conflicts. This change is pretty straight forward. Using UITYPE_LARGEAXE as an example, The Mangler and Sharp Beak both have a UIMinLvl of 2. Because of the way unique items are selected (fix 2), The Mangler would never drop. Simple fix was to give Sharp Beak a UIMinLvl of 3.
Fix 2 - Pick a random unique from the list of possible uniques. This fix is also straight forward. The way the game currently works is that if more than one unique of a given UIItemId is to be spawned, it always picks that last item in the order of indices in UniqueItemList. This is why Sharp Beak would always spawn when the UIMinLvl was the same as The Manger. I modified the selection code to pick an item at random when then generation routine was not set to "recreate". Now that the The Mangler can be selected and spawned it would morph back in to Sharp Beak when a new game would be started.
Fix 3 - Stop items from morphing. This one took me a bit to figure out what was going on. From what I can tell, the game only stores the UIItemId and the level of the monster that was killed which spawned the item. So when a new game is started, unique items are regenerated. So for example, if you kill a monster that drops UIMinLvl 10, when the items were re-created, it would go back to picking between The Mangler and Sharp Beak at random from fix 2. What I ended up doing was storing the UIMinLvl of the item instead, and then used the old unique selection code (which always picks the last item in the list) when the "recreate" flag was set. This code change I wasn't 100% sure it was the right change, but it seems to work.
Note that these changes are based on release 0.5. When I merged in the 1.0 changes, I think something broke, or I screwed up the merge on my local repository. I haven't had much time to look at it.
Relevant commits: https://github.com/cain05/devilutionX/commit/b294140e70d348a02e09ed79e6291024dfca74f4 https://github.com/cain05/devilutionX/commit/79fb1f3024920936c48caca47433488bc1196062
I apologize for a rather verbose post, but I hope that this information is useful for anyone looking for a fix to the issue.
EDIT: Spelling
Greetings. And thanks for taking the time to write out an in depth message on the issue. I have already attempted to fix the bug in #540, which works semantically the same as your fix outlined in 2. The issue of course is uniques morph on creating a new game. There's basically two ways this can be fixed:
-
The hacky way: this would involve storing the unique item's ID somewhere in the
ItemStruct, and then finding room for it in thePkItemStructused when saving. Might break compatibility with vanilla saves and might require adjusting packet code to accommodate size. - The proper way: this would be ditching the entire recreate system and storing the raw data for each item in the save file. That would ensure an item would never be able to morph, among expanding many other capabilities when modding the game. This would for sure break compatibility and require a good amount of code to be reworked.
- I think there are some unused variables that could be used for that = keeping compatibility, but do we care that much about compatibility at this point? :)
Well I dont. Worst comes to worst when @mewmew finishes the json save format, any vanilla saves can be converted anyway.
@galaxyhaxz For some reason I didn't see your post on the item generation bug when I was looking for something similar before posting, otherwise I would have just posted my findings there to keep things clean. I'm glad you found this information helpful. Diablo was and still is one of my favourite PC games, and was actually one of the first games I owned when I was a kid. :)
The recreate thing really threw me off when I was trying to solve the morphing issue. It seems like a strange way to do things. Maybe it was to keep the size of the save files small, but even back in 1996 I don't think it would have been a problem. Perhaps it was to keep network traffic down, I don't know. At any rate, I think in the long run, removing the recreate system would be best as it makes things more complicated than it needs to be.
Well I dont. Worst comes to worst when @mewmew finishes the json save format, any vanilla saves can be converted anyway.
Converter for hero save file is done. I'm now working on game.
was actually one of the first games I owned when I was a kid.
My first actually was Mario 64. I received an N64 on my 5th bday, and after that developed an obsession with the game's puzzles and secrets. Finding ways to get into places you werent supposed to, or bugs. etc was something I grew to fancy, and essentially the basis for all hacking which occurred thereafter. Diablo came later, when I was older and had access to it.
Perhaps it was to keep network traffic down
This was the real reason. Multiplayer was a feature added late in development. In the demo (circa august 1996) the very early stages of multiplayer can be seen in it's code, which was not yet enabled. There was no pack.cpp or the like, it just sent the data directly to the other players. Compression and packing of structs was added later to deal with lag.
removing the recreate system would be best
Yes. Diablo 2 had the same problem at launch, actually. Items were stored containing 2 32-bit seeds (d1 only has 1) to deal with rare items. But there were lots of problems with rares morphing still, and gems would sometimes morph too. Just look at all the bugs from this in the patch notes. Finally with the expansion, they fixed it by storing items as a bit array, while also keeping size down. The downside however is that if one bit is wrong, the entire array may be parsed wrong. Of course in Diablo 1, you don't have 1337 runewords and set items that need to save 15+ stats and tons of info on the item :)
Personally I prefer being backwards compatible with vanilla saves, it allows people to transfer there multiplayer hero between different clients.
@cain05 An idea: What If, to reduce code changes, you use a hash based on player's name + UIItemId as a seed for random (Fix 2). And then when the game were reloaded, the same item will be there (Fix 3)?
An alternative is to store the UniqueItemList index of the item instead of the UIMinLvl on it's initial spawn so when recreate is set, simply return that value. That would break compatibility with existing saves and cause all uniques to morph however. Since it sounds like the save format is changing, and there is a conversion tool, we could probably account for that and put the appropriate value in the new save file since it's easy to figure out what the item is.
@AJenbo the way I suggested the game would store UIItemId (as it is today) and to restore the item, it would regenerate the item, but since the hash/seed is fixed, the same item would be returned. Maybe I am I missing something.
Would it be too hard for someone to write a conversion tool for old saves so that it can be fixed properly?
Mewmew is already writing a tool that converts original saves in to JSON. If we end up breaking save game compatability we would probably go that route.
So, I applied my changes above to this repo's master since I managed to bork my repo's master (long story) and it turns out there are still some morphing issues. I was pretty sure it was working when I applied my changes last fall, but apparently that's not the case, or something has changed that I'm not aware of.
Anyway, Deadly Hunter dropped for me and when I started a new game, it changed to Bow of the Dead. When I stepped through the code when starting a new game, in CheckUnique lvl was set to 5 instead of 3 (UIMinLvl), which is why Bow of the Dead was selected on recreate. I was doing Laz runs, so it was dropped by either him (mlvl item 30) or one of his succubi (mlvl item 28). In SetupAllItems, one the first things that is done is setting the item's _iCreateInfo = lvl (either 28 or 30 in this case), and then if it's been determined that the item is unique, the change I made subtracts the original lvl then adds the UIMinLvl from the unique item that was selected, which should have set it to 3. _iCreateInfo contains other information which is set with various bitmasks, but they're large enough that they don't affect the item level. I find it odd that it was set to 5, and not 3, or either 28 or 30 if my code didn't change the value at all.
I'll continue looking in to it when I have some free time as it would be nice to get it fixed. While most of the unique items are not very good, fixing this issue would allow mods that add new items to work properly. It would also be nice to give meaningful names to the bit masks that are applied to _iCreateInfo.
This would be perfect for writing some unit tests that makes sure things are handled correctly :)
Ok I think I have it working. The reason the item morphed from a Laz run was that unique monsters get +4 added to ilvl, so instead of passing 3 to CheckUnique(), 7 was being passed, which made Bow of the Dead available to be selected. In order to make it work in a way that doesn't break compatibility, I took advantage of the unused ItemStruct._iDelFlag. Now, when an item is created this flag gets set. When recreating items, if this flag is set, then I don't add the +4 for a unique monster drop. This change should be backwards compatible with existing save files as .DelFlag will always be 0 for items generated before this change.
Here's the changes if anyone wants to give it a go. I made a few other temporary changes like forcing monsters to always drop an item, and all items will either be magical or unique (if applicable) in order to make testing easier. I plan on doing more testing, but I wanted to share what I found so that others can take a look at it and maybe test it if they like. Be sure to back up your save files just in case!
EDIT: while this change will load items before it no problem, items generated with this change will not be compatible with versions that don't have it. It's simply not possible, or at least not that I can see. The game won't crash or anything, but there's the risk of unique items dropped by unique monsters morphing. So you can use old save files with this change, but don't use the update save file with previous versions if you don't want your items to change.
Commit: https://github.com/cain05/devilutionX/commit/316ee6834ac69abf9762977c97869634b1b224ba
Branch: https://github.com/cain05/devilutionX/tree/upstream-item-generation-fix-test
Fix 2, as outlined in the OP, is that part of v1.3.0? I noticed this wasn't included in the milestone label.
@AJenbo
You have noticed correctly
On both accounts? Or just about the milestone label? So, essentially what I'm asking is, has this been fixed in the latest release? Assume not, since this issue is still open.
This has not been addressed. We have debated it a bit further on the chat. It is not fully clear if this is a bug, or partially intended. It seams that if the code is in a way that will let it span all unique items, then it will spawn items that where obviously not intended to be in game, or at the very least where not finished.
As mentioned in the comments "fixing" the issue will also break existing items as it will cause items to morph since the algorithm for item generation would have changed. As such there is a good chance this will never change for DevilutionX. We are keeping the issue open here until we have had time to fully investigate things. But it is not a priority (also why it does not appear on any milestones) so it may be a while before a final decisions is made.
While the changes I posted here are mostly working from what I can see, it's pretty hacky. I haven't looked at the code in a long time, but I don't believe it's a case of not wanting certain items to spawn. I don't think there's a clean fix without completely re-working the save files to store all the item information to get rid of the need to re-generate items. I get that they did to save space, but unfortunately the result is (in my opinion) things simply don't work the way they intended. This issue has bothered me for many, many years, even moreso when Hellfire came about because Sierra clearly had no idea how the item generation code worked. Hopefully one day it will get a proper fix.
Has anyone ever managed to fix the unique item generation bug in hellfire for DevilutionX?
I found two supposed posts on GitHub that have fixes but none of them have files available to download to try
My dream is to find the armor of gloom in Devolution x without having to find two unique full plate mails in the same game
If anyone knows anything I would greatly appreciate it.
