Random Number Generator Bytes & Seed

[Quickdeath]

Like many other people, I'm puzzling through the multiple appearance of 20 -item drops that are identical from the LK super chests (see the Single Player Forum).

Clearly, the item generation algorithms for superchests are one of the longest series of item generation events that are uninterrupted by player decisions. If different players approach LK superchests on the same players setting and happen to call the Superchest Object Function with the same random number seed it does make sense that the identical set of 20 objects would appear. The fact that one fo the 20 objects is a Ber Rune has simply made this effect noticeable.

What is surprising is that so many players have apparently opened the LK superchests with the identical random number seed.

So, here is my question. Does anyone know how many bytes the Diablo 2 Random Number Generator has? i.e., how many binary digits are there? In other words, how many possible (integer) values can a random number have in D2?

I know in V1.07 that there were three seed numbers for some calls of the Object Functions (weapons and Armor racks.) Two of the random seeds were dependent on the X,Y position of the obejct and the third random seed was dependednt on the map seed. When an LK superchest is opened, does anyone know whether the random number seed depends upon anything in the game?

[TheJarulf]

Like many other people, I'm puzzling through the multiple appearance of 20 -item drops that are identical from the LK super chests (see the Single Player Forum).


The ammount of items from a single drop is irellevant since a drop is all, from that purpose, a single event. There won't be any intervening other actions that affects the random number generation.


Clearly, the item generation algorithms for superchests are one of the longest series of item generation events that are uninterrupted by player decisions.


Well, some quest drops can probably rival it, like the quest chest in act 1 in the keep (forgot the names). But yes, since special chests has a case of calling the drop from a TC function multiple times, it probably holds true.



If different players approach LK superchests on the same players setting and happen to call the Superchest Object Function with the same random number seed it does make sense that the identical set of 20 objects would appear. The fact that one fo the 20 objects is a Ber Rune has simply made this effect noticeable.


This is of course true for ANY drop in the game from ANY source. If the seed is the same, you get the same items (assuming everything else is also the same of course).


What is surprising is that so many players have apparently opened the LK superchests with the identical random number seed.


I have allready told what I think about the issue in the other thread.


So, here is my question. Does anyone know how many bytes the Diablo 2 Random Number Generator has?


It is basically a 64 bit value (so 8 bytes). However, when initialized, the upper 4 bits are always the same. Most sources in the game will use the current seed of the target unit (or for objects their common seed) and hence it will be an 8 byte seed (sources for random item drops would be monsters or objects as far as I can think of).


i.e., how many binary digits are there? In other words, how many possible (integer) values can a random number have in D2?


2^64 would be a number with 20 digits. However, since most are initially initialized as 32 bit (4 byte) values, that would be reduced. A 32 bit integer holds 2^32 (about 4 billion) different values.


I know in V1.07 that there were three seed numbers for some calls of the Object Functions (weapons and Armor racks.)


Ehh, nope. There is only ever one seed used (you can't for that matter combine several seeds into one really). The seed typically used for the part of item generation that pick base item and quality (unique, rare, superior and so on) is the current seed of the monster or for objects unless they made a recent change in latest patechs which I doubt, the global object seed. Once the item type and quality is determined, a unit for the item is created and gets its own seed initialized (which will thus be a 32 bit value at that time). This initialization is based on the current game global seed, used for all unit creation (which includes any unit in the game created, be it a monster, item, missile (including spell ones) and so on. This item seed is then used for picking the properties of the item such as affixes or what unique and so on. It also inlcludes the ammount of gold in a gold pile. The DR (defence rating or is it called Armor Class? Gee, I am geting rsuty on this game). is calculated based on the same seed that picked item type though as part of the item unit set up.

So one can say that for items, there is two different seeds from two different sources used for its creation, but it is for two seperate and well defined parts of the item creation. By the way, the game will save the intial seed of the item which is what ends up being called "fingerprint" by ATMA, in case anyone wonder.


Two of the random seeds were dependent on the X,Y position of the obejct and the third random seed was dependednt on the map seed.


Huh? No, there is no coordinate based seeds. Not sure exactly what you mean, but the closest thing you could get would be that a room (a subset of the map, I think it is a few screens in size) has a seed stream I think but I don't think it is used for much except map creation. Each individual coordinate or tile doesn't have its own seed, which would be insane due to their number. For example a player will occupy several coordinate points alone due to its size.

For reference, the "map seed" I always attribute to the inital seed set for the game which is also saved with a character exiting a game and can be reset, for example by the "-seed" command. That one is NEVER used for anything except the very first initial seeding of the global game seed. That one is then used (and hence updated if that is the proper word) for anything the game do when creationg for example units (see above) and a few other things. It is thus never identical to the intial "map seed" which is never ever used for anything closed to item generation.


When an LK superchest is opened, does anyone know whether the random number seed depends upon anything in the game?

Ehh, if from the global object seed, any object created/opened/operated so far. If from the chest object iteself with its 16 bit truncation, the same although at an earlier point only affected by the order in which other objects so far has been created (in effect, the way you have moved to the object through the map. As long as you initiate the "rooms" in the game in the same order it will be the same assuming the initial "map seed" is the same though.

[Hakai_no_Tenshi]

I have this coded in ATMA (thx Jarulf) and it's the rng() used in D2:


#ifndef __D2_RANDOM_H__
#define __D2_RANDOM_H__

// Diablo II random number generator header .. courtsey of Jarulf

// random.h

struct seeddata {
unsigned int seed;
unsigned int mod;
};


extern unsigned int __fastcall d2rnd(struct seeddata *ptseed, unsigned int x);
extern unsigned int __fastcall d2seed(struct seeddata *ptseed);

#endif


#pragma warning( disable : 4035 ) // avoids warning for not returning any value
__declspec( naked ) unsigned int __fastcall d2rnd(struct seeddata *ptseed, unsigned int x)
{
__asm
{
push edi;
push esi;
push ebx;
mov edi,edx;
mov esi,ecx; // no check on pointer!!
mov ebx,eax;
test edi,edi; // check if x>0
jg OK;
xor eax,eax; // return 0 if x <= 0
jmp END;
OK:
mov eax, [esi]; // get seed_lo
mov ecx, 0x6ac690c5; // rndmult
mul ecx;
mov ecx,[esi+4]; // get seed_hi
xor ebx,ebx;
add eax,ecx;
adc edx,ebx;
mov [esi],eax; // store away new seed
mov [esi+4],edx;
xor edx,edx;
div edi; // calculate random number based on seed_lo
mov eax,edx; // return reminder
END:
pop ebx;
pop esi;
pop edi;
ret
}
// returns random value in eax
} // d2rnd
#pragma warning( default : 4035 )


#pragma warning( disable : 4035 ) // avoids warning for not returning any value
__declspec( naked ) unsigned int __fastcall d2seed(struct seeddata *ptseed)
// same as above but no division at end, returns lo_seed instead
{
__asm
{
push esi;
push ebx;
mov esi,ecx; // no check on pointer!!
mov eax, [esi]; // get seed_lo
mov ecx, 0x6ac690c5; // rndmult
mul ecx;
mov ecx,[esi+4]; // get seed_hi
xor ebx,ebx;
add eax,ecx;
adc edx,ebx;
mov [esi],eax; // store away new seed
mov [esi+4],edx;
pop ebx;
pop esi;
ret
}
// returns value in eax (new lo_seed)
} // d2seed
#pragma warning( default : 4035 )



#if 0
#pragma warning( disable : 4035 ) // avoids warning for not returning any value
int d2rnd(__int64 *ptseed, int x)
{
__asm
{
mov edi,x;
mov esi,ptseed; // no check on pointer!!
test edi,edi; // check if x>0
jg OK;
xor eax,eax; // return 0 if x <= 0
jmp END;
OK:
mov eax, [esi]; // get seed_lo
mov ecx, 0x6ac690c5; // rndmult
mul ecx;
mov ecx,[esi+4]; // get seed_hi
xor ebx,ebx;
add eax,ecx;
adc edx,ebx;
mov [esi],eax; // store away new seed
mov [esi+4],edx;
xor edx,edx;
div edi; // calculate random number based on seed_lo
mov eax,edx; // return reminder
END:
}
// returns value in eax
} // d2rnd
#pragma warning( default : 4035 )


#pragma warning( disable : 4035 ) // avoids warning for not returning any value
int d2seed(__int64 *ptseed)
// same as above but no division at end, returns seed instead
{
__asm
{
mov esi,ptseed; // no check on pointer!!
mov eax, [esi]; // get seed_lo
mov ecx, 0x6ac690c5; // rndmult
mul ecx;
mov ecx,[esi+4]; // get seed_hi
xor ebx,ebx;
add eax,ecx;
adc edx,ebx;
mov [esi],eax; // store away new seed
mov [esi+4],edx;
}
// returns value in eax (new lo_seed)
} // d2seed
#pragma warning( default : 4035 )


#pragma warning( disable : 4035 ) // avoids warning for not returning any value
__declspec( naked ) int __fastcall d2rnd(__int64 *ptseed, int x)
{
__asm
{
push edi;
push esi;
push ebx;
mov edi,edx;
mov esi,ecx; // no check on pointer!!
test edi,edi; // check if x>0
jg OK;
xor eax,eax; // return 0 if x <= 0
jmp END;
OK:
mov eax, [esi]; // get seed_lo
mov ecx, 0x6ac690c5; // rndmult
mul ecx;
mov ecx,[esi+4]; // get seed_hi
xor ebx,ebx;
add eax,ecx;
adc edx,ebx;
mov [esi],eax; // store away new seed
mov [esi+4],edx;
xor edx,edx;
div edi; // calculate random number based on seed_lo
mov eax,edx; // return reminder
END:
pop ebx;
pop esi;
pop edi;
}
// returns value in eax
} // d2rnd
#pragma warning( default : 4035 )



void CUtilManager::SEED(unsigned int seed)
{
prng_seed.seed = seed;
prng_seed.mod = 666;

d2seed(&prng_seed);
}

DWORD CUtilManager::PRNG()
{
// The first thing to know about how all the rare and magic item
// decoding works is the random number generator function. The random
// number generator stores a 64 bit number. Call the low 32 bits Seed
// and high 32 Carry. // To initialize the random number generator with a 32 bit number
// (DWORD1, or DWORD2), set the seed value to the appropriate DWORD,
// and set the carry to 0x29A (666).
// To get an output from the random number generator, multiply the
// value in Seed by 0x6AC690C5 and then add the carry.
// The low 32 bits of this new result is the new value of Seed in the
// random # generator, and is also the output random value. The high
// 32 bits is the new value to put in Carry.

d2seed(&prng_seed);

return (DWORD)d2rnd(&prng_seed, 0xFFFFFFFF);
}

DWORD CUtilManager::PRNG(unsigned int x)
{
return d2rnd(&prng_seed, x);
}

[Quickdeath]

Well I'm honored that my question has been responded to at length by two of the most distinguished members of the D2 Forums.

To make sure that I don't waste anyone's time, I read (for the first time) Jarulf's posts in the LK Chest drop thread. The conjecture that Jarulf mades there was the same one that I was heading towards -that there were only about 64,000 different chest drop combinations from an LK superchest. I had not read Jarulf's post before because the LK thread is running very, very long.

Here were my thoughts (very humbly presented);

The one random decision in the game requiring the largest set of random numbers appears to be the decision of whether a Zod is dropped or all other runes are dropped (given that a Runes 17 call is made). The odds of a Zod rune drop, given that the Runes17 TC is called is 1:82,722. Of course, Zod runes can't be dropped by a chest until Hell Act V. So the decision with the longest odds that is made by an LK Chest is when Runes 15 TC is selected:
it must sort through 27,016 possibilities to test whether a Ber ( 2 chances) or a Sur (3 chances) is selected.

If the biggest random choice that needs to be made in an LK Superchest drop is 2:27,016, then why, I wondered, use a set of random numbers from 1 to 4,294,967,296 on which to make the decision? I wondered if the random number set might not be truncated somehow.

I also note that other than decisions involving rune drops, the largest random number set that appears to be needed to make any single decision in Hell - item drop is 2,306 (although some decisions involving gold drops might be slightly higher, I cannot tell.)

Again, thanks Hakai and Jarulf for your responses.