Posts: 456
Threads: 36
Joined: Feb 2003
06-22-2003, 10:30 PM
(This post was last modified: 06-22-2003, 10:31 PM by the Langolier.)
My goal here is to determine a formula for how many monsters of a given type I will find on a given level in an X number of games (100, 250, 5000, etc). As in example, I am trying to calculate how many balrogs will spawn on dlvl 15 in 2500 games. The easiest way to do that for any number of games would be to calculate the average fractional amount of that enemy per game, and then simply multiply that number by the number of games. This would be like a game that spawned every monster that could spawn on a given level - I would like to calculate what percentage of the level each monster constitutes (the percentages should add up to 100%). An example would be level 15 that spawned balrogs, drakes, cabalists, three witch classes, magistrates, steel lords, and doom gaurds, but only 15-30 of each type constrained to their relative occurances (more withes than mages because they are more likely to spawn in one game). It is easy to see that this is quite a chore for level 15, and much more so on earlier levels where many other monsters types can spawn.
Jarulf's Guide has a section that deals with monster generation, but I can't find quite what I need. In section 5.3.2, it gives a routine that is used to determine what enemies appear on a level based on which monsters can appear on that level and their sizes. Essentially it works like this:
Randomly pick a monster from the types that can appear on the level
Subtract the size of that monster class from 3614 (the max size for one level)
Repeat until there is no monster that has a smaller size than what is left
To see how it works, we will look at dlvl 15 when balrogs and SB's spawn.
Balrogs randomly chosen first (size 2200)
Remaining size = 3614 - 2200 = 1414
At this point, only drakes and witches has a size smaller than what is left, so the remaining choices are: Azure drakes, Snow witch, Hell spawn, Soul Burner
Sould burners randomly chosen (size 980)
Remaining size = 1414 - 980 = 434
No monster have a size smaller than what remains - end monster selection.
Using this method it is easy to compute the various possiblities of spawned monsters for dlvl 15 including balrogs/drakes, balrogs/SB's, tri-witch, etc. Further down in the guide there are tables that list the probabilities of a certain monsters spawning on given dlvls. The problem I am having is relating these percantages to what monsters actually spawn. Is there any way to use those percantages to calculate a monsters fractional occurance?
The guide mentions that 185 monsters spawn per level on average. Will the number of monsters that spawn of each type be divided equally? If two monster types spawn on level 15, will each one constitute 50% of that level? If three types spawn, will each type constitute 33% of that level? I know that level 16 is a special case, and that I always find a greater number of knights than I do advocates. Does anyone know the generation for this level, such as knight-to-advocate ratio?
My guess is that I will have to calculate them by hand. First you have to determine to total number of all monster combonations that can exist per level. Go through each combonation one by one and calculate the total number of enmies of each monster type based on an average of 185 total monsters. Once you have the totals for every monster type, divide that number by 185 multiplied by the total number of combonations possible. Summing up the fractional amount for each monter type should equal 185. Is this method correct (just to double check myself in the event I do need to do this). Any help with ideas to simplify the calculations would be appreciated.
Take an example where there are only two possible combonations that a level can spawn with: balrogs/drakes or balrogs/snow witches. 92.5 balrogs will spawn in both cases because in each case they make up half of the level, giving a total of 185 balrogs spawned. 92.5 drakes will spawn in the first case, 0 in the second. 0 snow withces will spawn in the first case, 92.5 in the second. The totals for each monster class for these two possible combonations are as follows:
Balrogs: 185
Witches: 92.5
Drakes: 92.5
Now divide of each of these values by 182*2 because that is the total number of monsters that have spawned in the 2 cases. We end up with a level that spawns with 50% balrogs, 25% witches, and 25% drakes. Note this doesn't mean those are the probabilities an enemy of that type will spawn of the level (which is the information giving in the guide). Using these percentages it is easy to see that after 1000 games, 500 balrogs, 250 witches, and 250 drakes would have spawned.
Posts: 4,063
Threads: 68
Joined: Feb 2003
Hi,
Using this method it is easy to compute the various possiblities of spawned monsters for dlvl 15 including balrogs/drakes, balrogs/SB's, tri-witch, etc. Further down in the guide there are tables that list the probabilities of a certain monsters spawning on given dlvls. The problem I am having is relating these percantages to what monsters actually spawn. Is there any way to use those percantages to calculate a monsters fractional occurance?
Effectively, no. What you described is the explanation from Jarulf's Guide as to what the probabilities of monster *types* appearing in the various levels. However, IIRC, nowhere in the guide does it address just how the actual placement of the individual monsters on a level is determined. Without that information, you have no real means of generating the number you want. And even with that information, the calculation might not be tractable.
The guide mentions that 185 monsters spawn per level on average. Will the number of monsters that spawn of each type be divided equally?
That is an approximate average value. Claudio was interested in this because of a discussion of accidental leveling in a 3@30 attempt. He and I and a few other people did hell clears keeping track of the number of monsters per level. I don't remember the exact results, but there was a fair spread around the mean.
If two monster types spawn on level 15, will each one constitute 50% of that level? If three types spawn, will each type constitute 33% of that level?
I don't think that that would necessarily be the case. IIRC, the distribution between monsters varied even more than the total number.
Your proposed method probably give a fairly good answer. It could probably be done fairly rapidly in a spreadsheet. First, generate all combinations of monster types that could appear on the level. Each of these should be equally probable. So, if there are N combinations, the probability of any one of them is 1/N. Then, for each combination, look at how many monster types are represented. For instance, if three monster types are in the first combination, then the number of each of those types of monster is 1/N*1/3*185 average per game. Do this for all monsters and all combinations and you'll generate an "average number of monsters of type X that can appear on level Y" table. If you are only interested in one particular type of monster, be sure to include all the combinations that that monster does *not* appear in in your count of N.
If you do push this through, you really should post your results. Even though they will not make any difference on how the game is played, they'll still have some curiosity value :)
--Pete
How big was the aquarium in Noah's ark?
Posts: 69
Threads: 8
Joined: Apr 2003
well it is ...
I hope you find an answer ;)
Posts: 456
Threads: 36
Joined: Feb 2003
Good tip, I hadn't thought of using a spreadsheet to do the calculations for me. That should make things quite a bit simpler. Once I get back home and have access to excel, I will certainly start plugging away and post my findings.
Posts: 233
Threads: 12
Joined: Apr 2003
[nt]
"My doctor says that I have a malformed public-duty gland and a natural deficiency in moral fibre, and that I am therefore excused from saving Universes."
-- Ford Prefect
Posts: 233
Threads: 12
Joined: Apr 2003
I don't know if this is a psychological trick or a fact, but if it's the latter it should probably be taken into consideration:
Every time I get an "every stairway in its own quadrant" dungeon layout, the total number of monsters seems to drop a wee bit. Has anyone else noticed this? I've never really been paying attention to the numbers killed though, so it may very well be that in those layouts the mass of monsters stays the same, they're just bunched closer together (talk about ironman hell :blink: ).
If so far nobody has done any research (if you can call playing a game research) on that, perhaps this is the time to do it. I think separating the results into different classes (3 for dlvl 13, 2 for dlvls 14 and 15) would confirm my assumption or prove it's false, if it hasn't already been done, of course.
"My doctor says that I have a malformed public-duty gland and a natural deficiency in moral fibre, and that I am therefore excused from saving Universes."
-- Ford Prefect
Posts: 31
Threads: 6
Joined: May 2003
Quote:Every time I get an "every stairway in its own quadrant" dungeon layout, the total number of monsters seems to drop a wee bit.
Yeah, I've noticed this too. In fact, the # of monsters was usually 0 for me, except once! This is since I recently started playing again, about a month ago. Didn't pay much attention to it a few years ago, when I last had a Diablo-playing spurt.
Posts: 52
Threads: 16
Joined: Jun 2003
06-23-2003, 05:32 PM
(This post was last modified: 06-23-2003, 05:33 PM by hell-bringer.)
I have also noticed this and in a case the stairs down was next to the stairs i just went down i used to think "heh where are all the monsters gone :blink: !" B)
"Darkness and evil shall fall back to the burning hells within and light shall rule the lands of the good."
Posts: 233
Threads: 12
Joined: Apr 2003
dfn,Jun 23 2003, 11:00 AM Wrote:In fact, the # of monsters was usually 0 for me, except once! ...it wasn't. It couldn't have been.
I was referring to the phenomenon of the safe place around the stairways, not that there are no monsters on the level.
"My doctor says that I have a malformed public-duty gland and a natural deficiency in moral fibre, and that I am therefore excused from saving Universes."
-- Ford Prefect
Posts: 31
Threads: 6
Joined: May 2003
Yogi_Baar,Jun 23 2003, 10:50 AM Wrote:I was referring to the phenomenon of the safe place around the stairways, not that there are no monsters on the level. So was I. I was saying that the # of monsters for me was usually 0, around the stairways. Not that there are no monsters on the level. Weren't you saying something similar?
Posts: 983
Threads: 113
Joined: Feb 2003
Not much detailed memories here but basically the game first pick the types. Then when placing individual monsters it will pick one of the types at random. It will then try to place the monster. I think it pick at random a location and then see if it is free space, if not it loops arround (I don]t think it repick type yet though). WHen found, I think it places a patch of monsters, pretty much in the same way it places barrels (although I can remember wrong). That means it will not be possible to calculate exactly accurate since that requires in part to have a generated dungeon since the patch will place random monsters arround the last one until it won]t find a free space (in x attempts which might be 1 or more, don]t remember, for a possible estimate, check number of barrels in a patch and see if it match, if way of, it was done in a different manner). I think one would still be ablte to calculate a decent ammount of accuracy the number of monsters.
Next comes the "ending" of monster placement which is where the limit of arround 185 comes in. Remember that first it places special monsters, bosses and their packs, then it loops for monsters until it gets to arround 185 (don´t remmeber the exact way, and level 1 and 2 are smaller and thus have a smaller value I think). I can possible get arround to check it some time but unfortunately not at the moment.
Anyway, I think the way it pick monsters, I would say it is more or less the same ammount of each type of monsters on a level (disregarding the ones for bosses and specially placed and such).
There are three types of people in the world. Those who can count and those who can't.
Posts: 360
Threads: 6
Joined: Feb 2003
Hello Jarulf,
"Next comes the "ending" of monster placement which is where the limit of arround 185 comes in. Remember that first it places special monsters, bosses and their packs, then it loops for monsters until it gets to arround 185 (don´t remmeber the exact way, and level 1 and 2 are smaller and thus have a smaller value I think)."
Are you sure minions are placed before the common monsters? In the Dark (Hellfire) we have much more types per level (due to lower seeding sizes), and thus more bosses, in general. The bosses always appear when they should, but sometimes (pretty rare, but it happens) the number of minions is (much) lower as 8. So far, I assumed the packs are placed later, with the consequent risk of running into the limit.
Posts: 983
Threads: 113
Joined: Feb 2003
>Are you sure minions are placed before the common monsters?
Ehh, now that you say it, no, they are probably not. Not sure when though. First all bosses are played, then random ones. Not sure if minions come inbetween. By the way, special monsters placed as part of the dungeon level map comes before even bosses.
There are three types of people in the world. Those who can count and those who can't.
Posts: 456
Threads: 36
Joined: Feb 2003
I decided to write a small program that would determine all the monster combinations and output the information I am looking for. In order to check my work, I decided to just output the probability that a certain monster type would spawn and compare that to the information in Jarulf's guide. I wrote the algorithm and tried it on level 15, and it worked! Here's the output:
16.67% Balrog
33.33% Azure Drake
33.33% Snow Witch
33.33% Hell Spawn
33.33% Soul Burner
16.67% Doom Guard
16.67% Steel Lord
16.67% Magistrate
16.67% Cabalist
Combinations: 24
Excelent! Time to move on to level 14:
28.7671% Lava Maw
6.84932% Maelstorm
8.21918% Vortex Lord
8.21918% Balrog
26.0274% Fire Drake
26.0274% Gold Viper
26.0274% Succubus
26.0274% Snow Witch
26.0274% Hell Spawn
8.21918% Black Knight
8.21918% Doom Guard
8.21918% Steel Lord
8.21918% Blood Knight
8.21918% Counselor
8.21918% Magistrate
Combinations: 73
Err... That doesn't match the information in the guide. Nor does it for level 13. 12. 11. 10. 9. 8. You get the idea.
Ok, clearly something is wrong.
First, I create an array of the various monster sizes for each level like this one for level 15:
int mSize[9]={2203,1273,981,982,983,2121,2122,2001,2002};
The program goes through the array in a series of nested for loops to determine a monster combination. First it subtracts a monster size from 3614 (the total size available on one level). It then moves onto another monstersize and another until nothing more can spawn for that combination. In order to check to make sure it is a unique monster combination it saves the pointers to the mSize (0-9) in a seperate array and compares that to the existing array of unique ID.
So basically what I'm saying is that I have no idea what is going on. I'll post the first three iterations of the algorithm (if you want the source, send me PM and I'll email it to you). Can anyone give insight as to what I am forgetting? As far as I know, the code works fine but I am just missing a detail that gives me incorrect results.
Code: #include<iostream.h>
void sort(int[]); //this function sorts a 1-D array from greatest to lowest value
bool compID(int[], int[][10], int); //this function compares a combo ID to the list of unique ID's
void main()
{
int dlvl=15;
...
//int mNum=15; //used for dlvl 14
//int mSize[15]={716,1740,2200,2200,1270,1270,980,980,980,2120,2120,2120,2120,2000,2000};
int mNum=9; //used for dlvl 15
int mSize[9]={2203,1273,981,982,983,2121,2122,2001,2002};
...
int comboID[10]={0}, uniqueID[2500][10]={0};
int tSize=3614, a, i, j, k, l, m, n, o, p, q, b, min=0, max=mNum-1, Ni=0;
int numSpawn=0;
bool didSpawn=0;
float percentN=0;
//initializes ID array
for (i=0; i<=9; i++)
{
comboID[i]=0;
}
//determines all unique combinations
if (dlvl == 3)
{
min=9;
max=17;
}
switch (dlvl)
{
case 2:
tSize = 3614-980;
break;
case 3:
tSize = 3614-1010;
break;
default:
tSize = 3614;
}
for (a=min; a<=max; a++)
{
if (tSize-mSize[a] >= 0 && mNum >= 1) //then at least 1 type will spawn
{
tSize = tSize-mSize[a];
numSpawn=1;
for (i=0; i<=mNum-1; i++)
{
if (i != a && tSize-mSize[i] >= 0 && mNum >= 2) //then at least 2 type will spawn
{
tSize = tSize-mSize[i];
numSpawn=2;
for (j=0; j<=mNum-1; j++)
{
if (j != a && j != i && tSize-mSize[j] >= 0 && mNum >= 3) //then at least 3 type will spawn
{
tSize = tSize-mSize[j];
numSpawn=3;
if (numSpawn == 3) //4 types did not spawn
{
comboID[0] = a+1;
comboID[1] = i+1;
comboID[2] = j+1;
sort(comboID);
if (compID(comboID,uniqueID,Ni)) //then it is a unique combonation
{
for (b=0; b<=9; b++)
{
uniqueID[Ni][b] = comboID[b];
}
Ni++;
}
for (b=0; b<=9; b++)
{
comboID[b]=0;
}
}
tSize = tSize+mSize[j];
}
}
if (numSpawn == 2) //3 types did not spawn
{
comboID[0] = a+1;
comboID[1] = i+1;
sort(comboID);
if (compID(comboID,uniqueID,Ni)) //then it is a unique combonation
{
for (b=0; b<=9; b++)
{
uniqueID[Ni][b] = comboID[b];
}
Ni++;
}
for (b=0; b<=9; b++)
{
comboID[b]=0;
}
}
tSize = tSize+mSize[i];
}
}
if (numSpawn == 1) //2 types did not spawn
{
comboID[0] = a+1;
sort(comboID);
if (compID(comboID,uniqueID,Ni)) //then it is a unique combonation
{
for (b=0; b<=9; b++)
{
uniqueID[Ni][b] = comboID[b];
}
Ni++;
}
for (b=0; b<=9; b++)
{
comboID[b]=0;
}
}
tSize = tSize+mSize[a];
}
}
//displays monster probabilites
for (a=0; a<= mNum-1; a++)
{
numSpawn=0;
for (i=0; i<=Ni-1; i++)
{
didSpawn=0;
for (j=0; j<=9; j++)
{
if (uniqueID[i][j] == a+1)
{
didSpawn=1;
}
}
if (didSpawn)
{
numSpawn++;
}
}
cout << mSize[a] << " " << float(numSpawn)/Ni*100 << "%" << endl;
}
cout << endl;
cout << "Number of combinations: " << Ni << endl;
}
//this function sorts a 1-D array from greatest value to lowest
void sort(int comboID[])
{
int temp[quote][10]={0}, i, j, largeNum=0, pos=0;
for (i=0; i<=9; i++)
{
temp[quote][i] = comboID[i];
comboID[i]=0;
}
for (i=0; i<=9; i++)
{
for (j=0; j<=9; j++)
{
if (temp[quote][j] > largeNum)
{
largeNum = temp[quote][j];
pos = j;
}
}
comboID[i] = largeNum;
largeNum=0;
temp[quote][pos]=0;
}
}
//this function determines if the ID is unique
bool compID(int comboID[], int uniqueID[][10], int Ni)
{
int i, j;
int temp[10]={0};
bool unID=1, unRowID=0;
for (i=0; i<=Ni; i++)
{
unRowID=0;
for (j=0; j<=9; j++)
{
if (comboID[j] != uniqueID[i][j])
{
unRowID=1;
}
}
if (unRowID == 0)
{
unID=0;
}
}
return unID;
}
Posts: 983
Threads: 113
Joined: Feb 2003
I always get nervous after posts like this. Might I have goofed so that all info in my Guide is wrong??? *gulp*
Some general comments. First an interesting observation:
>Excelent! Time to move on to level 14:
>26.0274% Gold Viper
>26.0274% Succubus
I note that two monsters with different sizes still show up equal ammount of time. This MIGHT not be strange since the difference might not be of importance for this particulary level. I get a difference however.
>The program goes through the array in a series of nested for loops to determine a monster combination. First it
>subtracts a monster size from 3614 (the total size available on one level). It then moves onto another
>monstersize and another until nothing more can spawn for that combination. In order to check to make sure it is
>a unique monster combination it saves the pointers to the mSize (0-9) in a seperate array and compares that to
>the existing array of unique ID.
When I worte my program to calculate the occurance probabilities, I tried several approaches. I wrote it way back on an old computer in Turbo Pascal. One of the problems I had was memory limitations (I never got arround to rewrite it in C now, but I have rewritten the part that output table data, pretty much into spread sheet txt files, like D2, hence my mod question in this forum). Anyway. The options I first tried was to simply calculate all possible combinations. I first set up a recursive method to do it, however, it didnât go to well since there is really TONS of ways to pick monsters for a level. Especially for church levels that has many small size monsters. Level 15 is easier since it has just a few monsters, most of big size. Next I tried some loop method, again, getting into problems (I donât recall if it was memory problems or simple time problems). I ended up simply writing a program that did as the game did, pick monsters at random and then loop it many times until the end result did not change by going up in number of attempts. I think 100k times was enough for a level to get a value with one decimal point of precision. So that is how I ended up doing it. I did compare a simple level with the other methods just to compare results, and it did match.
Now, you seem to approach it from the point of view in finding all possible unique combinations, right? Not bad. However, consider that a combination can be reached in multiple ways. Some might be more common than others. Also, from your program, it seems you assume there never spawn more than 3 types of monsters on a level, that is not true. Also, variants with say 4 monsters picked have more possible ways than a combination with 3 monsters (in general I think) and so on. I think that could be it. So you canât ONLY look at number of unique combinations but also the number of ways you got there (I am bad at these things so canât tell if all variants with, say, 3 monsters are equal probable, but I think they donât have to be, since in some of them, there might be ways to go to 4, while for others not and so on. Oh well, someone better at probabilities can probably explain better. Here is the code I wrote for the calculations. Not particulary good looking code but it gets the work done. Note that it uses data tables for monster info and such for which code and info is NOT part of it. I have tried to add comments to explain what is going on. Note that it is Turbo Pascal. I can help converting to C if you need.
Code: procedure pickpossible(var monsters:mlist;var lastmonster:word;dlvl:word);
var
dlvl1,dlvl2 : word;
mslot : word;
begin
for mslot:=0 to mlast do begin
This goes through all monsters in the game!
if (mslot<>133) or (dlvl<>24) then begin { Arch Liches }
Skip these since they wonât end up randomly picked.
dlvl1:=(mdata^[mslot,84]+2) div 2;
dlvl2:=(mdata^[mslot,85]+2) div 2;
mdata is an array with the monster data, at position 84 and 85 for example, you find the dlvl.
if (dlvl>=dlvl1) and (dlvl<=dlvl2) then
if ((adata[mslot] and 128)=0) and ((adata[mslot] and 3)<>0) then begin
Checks if the monster is active in the active list. My program was also meant to handle mods so it read it properly and check for all cases.
inc(lastmonster);
monsters[lastmonster,0]:=mslot;
monsters[lastmonster,1]:=lastmonster;
Builds a table with possible monsters to pick from on the level we are calculating on.
end;
end;
end;
end; { pickpossible }
procedure pickrandomskel(var nbr:word);
var
dlvl1,dlvl2 : word;
ok : boolean;
tries : word;
begin
ok:=false;
tries:=0;
repeat
nbr:=random(12);
inc(tries);
case nbr of
0.. 3 : nbr:=nbr+8;
4..11 : nbr:=nbr+16;
end;
dlvl1:=(mdata^[nbr,84]+2) div 2;
dlvl2:=(mdata^[nbr,85]+2) div 2;
if (3>=dlvl1) and (3<=dlvl2) then
if ((adata[nbr] and 128)=0) and ((adata[nbr] and 3)<>0) then
ok:=true;
until ok or (tries=1000);
if not ok then
nbr:=maxint;
end; { pickrandomskel }
Well, on level 3, we wantâ a skeleton to go with Leoric. This pick one, it is inserted as a âpickedâ monster on the level before the random picking starts. Like the game code, my program only check the 12 existing skeleton slots. It do check if they are active though, in case a mod deactivated any!!
procedure seedmonsters(monsters:mlist;lastmonster:word;sizeleft:word;dlvl:word;var picks:plist);
var
run : longint;
minsize : longint;
msize : longint;
size : word;
last : word;
lskel : word;
i,j : word;
monst : mlist;
begin
for run:=1 to runs do begin
As I explained, number of times to do it. I think 100k was enough.
size:=sizeleft;
This is the total size possible on a level. My program actually read the size out of the code since some mods changed it. The size of the golem (from the monster table in case it was changed, should allready be subtracted from the value.
monst:=monsters;
last:=lastmonster;
if dlvl=3 then begin
pickrandomskel(lskel);
For level 3, pick a random skeleton.
for i:=1 to last do begin
if monst[i,0]=lskel then begin
Check if the skeleton picked existed allready as possible monsters for that level. If so, remove it from the list of possible monsters. Note that I shrink this list by simply removing the picked monster and at that place inserting the last monster of the list. Then I shrink the variable that keep track of how many monsters are possible by 1. I keep track for each monster though, how many times it has been picked. Divided by the number of runs, gives the probability of it occuring.
size:=size-value(@mdata^[i,4],4);
inc(picks[monst[i,1]]);
monst[i]:=monst[last];
dec(last);
end;
end;
end;
repeat
i:=random(last)+1;
Pick one of the remaining possible monsters at random.
msize:=value(@mdata^[monst[i,0],4],4);
Turbo Pascal did not have a good way to cast values, at least not that I used. My âvalueâ function do this. It takes a pointer to the data (in this case in the mdata, column âmonst[i,0]â, row 4 (the size). The final 4 indicate what type of value the function should interpret the data as. A 4 should be longint which in that implementation of Turbo Pascal meant a 4 byte integer.
if msize<=size then begin
size:=size-msize;
inc(picks[monst[i,1]]);
monst[i]:=monst[last];
dec(last);
end;
If the random monsters size was small enough to fit. Add it as picked and remove it from the list.
minsize:=maxint;
for j:=1 to last do begin
msize:=value(@mdata^[monst[j,0],4],4);
if msize<minsize then
minsize:=msize;
end;
Search remaining monsters to see if any still have a size small enough to fit (one could of course have removed those large enough to not fit, but I did not do that).
until (minsize>size) or (last=0);
Loop until there is no more possible monster to pick.
end;
end; { seedmonsters }
procedure printlevels;
This procedure (or function if you want to call it that), loops the different dungeon levels.
var
monsters : mlist;
picks : plist;
lastmonster : word;
sizeleft : word;
dlvl,mslot : word;
begin
writeln('Simulating monster selection. Please have patience...');
write('dlvl: ');
writeln(target);
writeln(target,'Monsters occuring on each level. Size: ',totsize,' Runs: ',runs);
writeln(target,'Singleplayer quests may affect the probabilities.');
totsize:=totsize-value(@mdata^[109,4],4); { golem }
Here the golem size is removed.
for dlvl:=1 to lastlevel do begin
writedlvl(output,dlvl,3);
sizeleft:=totsize;
if dlvl=16 then begin
monsters[1,0]:=93;
picks[1]:=runs;
monsters[2,0]:=96;
picks[2]:=runs;
monsters[3,0]:=108;
picks[3]:=runs;
lastmonster:=3; end
else begin
Level 16 is special, so I handle it specially too!!
case dlvl of
2 : sizeleft:=sizeleft-value(@mdata^[50,4],4); { Skeleton King }
3 : sizeleft:=sizeleft-value(@mdata^[51,4],4); { Butcher }
18 : sizeleft:=sizeleft-value(@mdata^[117,4],4); { Hork Spawn }
19 : begin
sizeleft:=sizeleft-value(@mdata^[117,4],4); { Hork Spawn }
sizeleft:=sizeleft-value(@mdata^[123,4],4); { Hork Demon }
end;
20 : sizeleft:=sizeleft-value(@mdata^[124,4],4); { The Defiler }
24 : sizeleft:=sizeleft-value(@mdata^[133,4],4); { Arch Lich }
end;
Remove the size of monsters that always occur. Note, some monsters that always occur does NOT have its size subtracted if I recall correctly. I only remove those that affect size here.
lastmonster:=0;
pickpossible(monsters,lastmonster,dlvl);
Set up possible monsters to pick from (see above):
for mslot:=1 to lastmonster do
picks[mslot]:=0;
Reset how many times they were picked.
seedmonsters(monsters,lastmonster,sizeleft,dlvl,picks);
case dlvl of
18 : begin
inc(lastmonster);
monsters[lastmonster,0]:=117; { Hork Spawn }
picks[lastmonster]:=runs;
end;
19 : begin
inc(lastmonster);
monsters[lastmonster,0]:=117; { Hork Spawn }
picks[lastmonster]:=runs;
end;
24 : begin
inc(lastmonster);
monsters[lastmonster,0]:=133; { Arch Lich }
picks[lastmonster]:=runs;
end;
end;
This adds a few monsters for picking that would not otherwise have been pickable if I remember correctly. None is in Diablo though, so you might just want to ignore many of these special cases. I think the Arch Liches was especially complicated how they handled it in the code.
end;
writeln(target);
case dlvl of
1.. 4 : write(target,'Level ',dlvl,' Church');
5.. 8 : write(target,'Level ',dlvl,' Catacombs');
9..12 : write(target,'Level ',dlvl,' Caves');
13..16 : write(target,'Level ',dlvl,' Hell');
17..20 : write(target,'Level H',dlvl-16,' The Hive');
21..24 : write(target,'Level C',dlvl-20,' The Crypt');
Just writes the dlvl in a nice way.
end;
writeln(target,',',lastmonster:3,' monsters');
for mslot:=1 to lastmonster do
writeln(target,picks[mslot]/runs*100:5:1,'%',value(@mdata^[monsters[mslot,0],4],4):6,'
Then write out the occurance probability for each monster that was pickable on that level.
',mname^[monsters[mslot,0]]);
end;
writeln;
end; { printlevels }
procedure dooccurance;
begin
printlevels;
end; { dooccurance }
Just a forwarding function.
Have fun and if you wonder anything, feel free to ask.
There are three types of people in the world. Those who can count and those who can't.
Posts: 456
Threads: 36
Joined: Feb 2003
07-24-2003, 08:20 AM
(This post was last modified: 07-24-2003, 08:22 AM by the Langolier.)
Thank you so much for the insight! I just assumed that each combination was equally probable than the others and didn't think otherwise. I quickly wrote another program that does the same, and it all worked out. After the weekend I will get back to the original project of creating the histrogram instead of the probabilities. At least my first program is somewhat interesting. It can output all possible combinations (most recorded was 10,270 on dlvl 3 - not counting dlvls 4-6 which take at least an hour of computing to determine) for a level and lists how many combination each monster appears in.
> Also, from your program, it seems you assume there never spawn more than 3 types of monsters on a level, that is not true.
I only posted three levels to keep it from getting too confusing and that is all that is needed for dlvl 14 and 15. The actual source goes up to ten.
Here are some quick results from the routine. The values are virtually those that are in the guide, plus or minus a percent. I ran 500,000 iterations, but it doesn't seem to be anymore accurate than 100,000 for smaller levels. Speaking of which, I know the random values aren't actually random, but what is going on with dlvl 1? Can you make the random numbers MORE random - is there a way to get more accurate results?
Code: mSize   Prob.
~~~~~~~~~
Dlvl 1:
799 Â Â 81.8808%
543 Â Â 83.0794%
553 Â Â 83.756%
623 Â Â 87.3978%
410 Â Â 121.625%
575 Â Â 132.085%
(average probability for dlvl 1 ~ 100%)
Dlvl 6:
570 Â Â 30.6454%
578 Â Â 30.442%
413 Â Â 42.2644%
366 Â Â 46.4796%
367 Â Â 48.2684%
993 Â Â 22.9128%
994 Â Â 23.0402%
1030 Â Â 22.1982%
1031 Â Â 22.3858%
1032 Â Â 22.3006%
1040 Â Â 22.2794%
1041 Â Â 22.3398%
1042 Â Â 22.4784%
1130 Â Â 22.077%
1650 Â Â 16.7808%
716 Â Â 30.0854%
Dlvl 14:
719 Â Â 26.1026%
1743 Â Â 10.0414%
2202 Â Â 9.5376%
2203 Â Â 9.5392%
1271 Â Â 21.144%
1272 Â Â 21.126%
980 Â Â 21.856%
981 Â Â 21.7238%
982 Â Â 22.3446%
2120 Â Â 9.5238%
2121 Â Â 9.551%
2122 Â Â 9.5396%
2123 Â Â 9.5144%
2000 Â Â 9.4948%
2001 Â Â 9.564%
Dlvl 15:
2203 Â Â 16.6936%
1273 Â Â 32.7402%
981 Â Â 32.8576%
982 Â Â 32.918%
983 Â Â 34.74%
2121 Â Â 16.7978%
2122 Â Â 16.595%
2001 Â Â 16.6094%
2002 Â Â 16.6766%
Posts: 983
Threads: 113
Joined: Feb 2003
>At least my first program is somewhat interesting. It can output all possible combinations (most recorded
>was 10,270 on dlvl 3 - not counting dlvls 4-6 which take at least an hour of computing to determine) for a
>level and lists how many combination each monster appears in.
Ahh, one of the reasons I simulated picks instead, didn't take as long to do (for some reason), it was seconds on my old Pentium 130.
>I ran 500,000 iterations, but it doesn't seem to be anymore accurate than 100,000 for
>smaller levels. Speaking of which, I know the random values aren't actually random,
Well, my routine uses the built in random number function from Turbo Pascal (it is relatively good, especially for 100k itterations).
> but what is going on
>with dlvl 1?
???
> Can you make the random numbers MORE random - is there a way to get more accurate
>results?
??? Don't understand what you mean or ask about. Is it the fact that you get more than 100% for some monsters? That seems to be an algorithm problem with your program or simply a coding bug.
By the way, it would be interesting to add the number of unique combinations of monsters on each dlvl to the guide. However, your program only handle Diablo, right? Not Hellfire? My current program doesn't handle the ability to store the number of unique combinations. On the other hand, it would probably be easy to make a program that calculate that only, since you don't need to simultaneously calculate the probability of it. Hmm. I will see. Right now I will try to finnish converting my old Dview program to output plain txt spread sheets (and swith just a few lines of extra code I think it would be able to reverse the process and take txt files and put that data into the exe. I have a nice idea about the strings of monsters, items and such too. Basically each type has its own small data area where the strings are saved (however , the compiler do point into other areas should the string be available there). Anyway, one could write the code so that it pool all those string areas, and then take the names people enter into the txt files and store them were it fits. It would mean that if you have shorter monster names, longer item names can get stored there and so on. Just a thought. That will require additional work though, right now I just move arround the pointer.
There are three types of people in the world. Those who can count and those who can't.
Posts: 4,063
Threads: 68
Joined: Feb 2003
Hi,
At least my first program is somewhat interesting. It can output all possible combinations (most recorded was 10,270 on dlvl 3 - not counting dlvls 4-6 which take at least an hour of computing to determine) for a level and lists how many combination each monster appears in.
Starting from this, I think the probabilities could be easily calculated without resorting to Monte Carlo methods.
Let us say that a given level has N distinct possible combinations. Each of those combinations has M(k) monsters, with k = 1 to M. Each combination can then be chosen in M(k)! ways. The total ways (not distinct) the level could be populated is then
T = Sum (k = 1 to M) of M(k)!
The total number of ways a particular monster can be on that level is
t(monster) = Sum (k = 1 to M) of {M(k)! if monster is included in the combination; 0 if not)}
Then, the probability of that monster appearing on that level is t(monster)/T
I haven't thought this out in detail, but on first blush, I think it should work and with less than fifteen thousand combinations per level it shouldn't take an unreasonable computation time.
--Pete
How big was the aquarium in Noah's ark?
Posts: 456
Threads: 36
Joined: Feb 2003
Yes you are correct, there was a small error that caused the program to generate an incorrect list of monsters that could still spawn (it didn't remove the ones that had already been selected). Interestingly enough the error would virtually go away with a large number of iterations. Now it is working fine and the numbers are much better.
Posts: 456
Threads: 36
Joined: Feb 2003
That would work if each specific combination had the same probabilty to be generated no matter the path. Due to the way the game untilizes monster sizes, however, this is not the case. For instance, let's look at dlvl 14 where two witch type monsters spawn with lava maws.
One way to get there is in this (random) order: Lava Maw, Witch1, Witch2
Another way to get to that combination is: Witch1, Witch2, Lava Maw
Using monster sizes, we can determine the number of possible selections available after each monster spawns:
1: 1/15 (lava maw) 1/14 (witch1) 1/5 (witch2)
2: 1/15 (witch1) 1/14 (witch2) 1/4 (lava maw)
As you can see, when two witch type enemies spawn first there is a greater probability for the combination to be maw/witch/witch than the first. The reason is because two witch types take a larger chunk out of the total size for a level than do a witch and maw type (980 and 980 v. 980 and 716). This small difference determines whether or not Maelstorms are able to spawn or not as the third and final monster type.
This has given me an idea though. Basically, the program works by first randomly producing a combination. Every time it generates a combination it adds one to a counter for the monster which spawned in an array called spawnCount. sCount that matches the size of mSize where spawnCount[i] = the number of times the monster of size mSize[i] has spawned. When you divide sCount[i] by the number of iterations for every monster type, it gives you the probability for that monster to spawn.
Right now my first program generates all monster combinations INCLUDING all paths to get to a specific monster combination using for loops. What if I ditched the unique combination array altogether. Everytime a combination is generated, unique or not, it will increment the counter for the monsters that spawn in that combination just like it does for the other program. It will do this for all non-unique combinations then go through sCount element by element dividing by the total number all combinations. I think it will work. I'll try that tonight and see what happens.
|
