Monster creation in dungeons

[the Langolier]

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()
{
&nbsp; &nbsp;int dlvl=15;
&nbsp; &nbsp;...
&nbsp; &nbsp;//int mNum=15; //used for dlvl 14
&nbsp; &nbsp;//int mSize[15]={716,1740,2200,2200,1270,1270,980,980,980,2120,2120,2120,2120,2000,2000};
&nbsp; &nbsp;int mNum=9; //used for dlvl 15
&nbsp; &nbsp;int mSize[9]={2203,1273,981,982,983,2121,2122,2001,2002};
&nbsp; &nbsp;...
&nbsp; &nbsp;int comboID[10]={0}, uniqueID[2500][10]={0};
&nbsp; &nbsp;int tSize=3614, a, i, j, k, l, m, n, o, p, q, b, min=0, max=mNum-1, Ni=0;
&nbsp; &nbsp;int numSpawn=0;
&nbsp; &nbsp;bool didSpawn=0;
&nbsp; &nbsp;float percentN=0;
    
&nbsp; &nbsp;//initializes ID array
&nbsp; &nbsp;for (i=0; i<=9; i++)
&nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp;comboID[i]=0;
&nbsp; &nbsp;}

&nbsp; &nbsp;//determines all unique combinations
&nbsp; &nbsp;if (dlvl == 3)
&nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp;min=9;
&nbsp; &nbsp; &nbsp; &nbsp;max=17;
&nbsp; &nbsp;}
&nbsp; &nbsp;switch (dlvl)
&nbsp; &nbsp;{
&nbsp; &nbsp;case 2:
&nbsp; &nbsp; &nbsp; &nbsp;tSize = 3614-980;
&nbsp; &nbsp; &nbsp; &nbsp;break;
&nbsp; &nbsp;case 3:
&nbsp; &nbsp; &nbsp; &nbsp;tSize = 3614-1010;
&nbsp; &nbsp; &nbsp; &nbsp;break;
&nbsp; &nbsp;default:
&nbsp; &nbsp; &nbsp; &nbsp;tSize = 3614;
&nbsp; &nbsp;}
&nbsp; &nbsp;for (a=min; a<=max; a++)
&nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp;if (tSize-mSize[a] >= 0 && mNum >= 1) //then at least 1 type will spawn
&nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;tSize = tSize-mSize[a];
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;numSpawn=1;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (i=0; i<=mNum-1; i++)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (i != a && tSize-mSize[i] >= 0 && mNum >= 2) //then at least 2 type will spawn
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;tSize = tSize-mSize[i];
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;numSpawn=2;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (j=0; j<=mNum-1; j++)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (j != a && j != i && tSize-mSize[j] >= 0 && mNum >= 3) //then at least 3 type will spawn
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;tSize = tSize-mSize[j];
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;numSpawn=3;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (numSpawn == 3) //4 types did not spawn
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;comboID[0] = a+1;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;comboID[1] = i+1;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;comboID[2] = j+1;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sort(comboID);
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (compID(comboID,uniqueID,Ni)) //then it is a unique combonation
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (b=0; b<=9; b++)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;uniqueID[Ni][b] = comboID[b];
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Ni++;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (b=0; b<=9; b++)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;comboID[b]=0;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;tSize = tSize+mSize[j];
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (numSpawn == 2) //3 types did not spawn
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;comboID[0] = a+1;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;comboID[1] = i+1;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sort(comboID);
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (compID(comboID,uniqueID,Ni)) //then it is a unique combonation
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (b=0; b<=9; b++)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;uniqueID[Ni][b] = comboID[b];
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Ni++;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (b=0; b<=9; b++)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;comboID[b]=0;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;tSize = tSize+mSize[i];
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (numSpawn == 1) //2 types did not spawn
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;comboID[0] = a+1;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sort(comboID);
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (compID(comboID,uniqueID,Ni)) //then it is a unique combonation
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (b=0; b<=9; b++)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;uniqueID[Ni][b] = comboID[b];
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Ni++;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (b=0; b<=9; b++)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;comboID[b]=0;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;tSize = tSize+mSize[a];
&nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp;}

&nbsp; &nbsp;//displays monster probabilites
&nbsp; &nbsp;for (a=0; a<= mNum-1; a++)
&nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp;numSpawn=0;
&nbsp; &nbsp; &nbsp; &nbsp;for (i=0; i<=Ni-1; i++)
&nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;didSpawn=0;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (j=0; j<=9; j++)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (uniqueID[i][j] == a+1)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;didSpawn=1;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if (didSpawn)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;numSpawn++;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp;}
&nbsp; &nbsp; &nbsp; &nbsp;cout << mSize[a] << " &nbsp; &nbsp; " << float(numSpawn)/Ni*100 << "%" << endl;
&nbsp; &nbsp;}
&nbsp; &nbsp;cout << endl;
&nbsp; &nbsp;cout << "Number of combinations: " << Ni << endl;
}





//this function sorts a 1-D array from greatest value to lowest
void sort(int comboID[])
{
&nbsp; &nbsp; int temp[quote][10]={0}, i, j, largeNum=0, pos=0;
&nbsp; &nbsp; for (i=0; i<=9; i++)
&nbsp; &nbsp; {
&nbsp; &nbsp; &nbsp; &nbsp; temp[quote][i] = comboID[i];
&nbsp; &nbsp; &nbsp; &nbsp; comboID[i]=0;
&nbsp; &nbsp; }
&nbsp; &nbsp; for (i=0; i<=9; i++)
&nbsp; &nbsp; {
&nbsp; &nbsp; &nbsp; &nbsp; for (j=0; j<=9; j++)
&nbsp; &nbsp; &nbsp; &nbsp; {
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (temp[quote][j] > largeNum)
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; largeNum = temp[quote][j];
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pos = j;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }
&nbsp; &nbsp; &nbsp; &nbsp; }
&nbsp; &nbsp; &nbsp; &nbsp; comboID[i] = largeNum;
&nbsp; &nbsp; &nbsp; &nbsp; largeNum=0;
&nbsp; &nbsp; &nbsp; &nbsp; temp[quote][pos]=0;
&nbsp; &nbsp; }
}

//this function determines if the ID is unique
bool compID(int comboID[], int uniqueID[][10], int Ni)
{
&nbsp; &nbsp; int i, j;
&nbsp; &nbsp; int temp[10]={0};
&nbsp; &nbsp; bool unID=1, unRowID=0;
&nbsp; &nbsp; for (i=0; i<=Ni; i++)
&nbsp; &nbsp; {
&nbsp; &nbsp; &nbsp; &nbsp; unRowID=0;
&nbsp; &nbsp; &nbsp; &nbsp; for (j=0; j<=9; j++)
&nbsp; &nbsp; &nbsp; &nbsp; {
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (comboID[j] != uniqueID[i][j])
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; unRowID=1;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }
&nbsp; &nbsp; &nbsp; &nbsp; }
&nbsp; &nbsp; &nbsp; &nbsp; if (unRowID == 0)
&nbsp; &nbsp; &nbsp; &nbsp; {
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; unID=0;
&nbsp; &nbsp; &nbsp; &nbsp; }
&nbsp; &nbsp; }
&nbsp; &nbsp; return unID;
}