C++

Forum

 
Better enemy wave spawning

Bingocat4 (105)
I've been making a multiplayer shooter game, and everything works good right now except enemy spawning. I want every enemy to have a chance of appearing that depends on how far you are in the game. The fist few waves should be easy, but have a low chance of a difficult enemy appearing, then the later waves should have harder enemies, but still a chance of having easy enemies. Here is the code I have right now.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
int enemy = rand() % (waveNum + 5);
if (enemy <= 5)
	type = SLIME;
if (enemy >= 6 && enemy <= 10)
	type = RAT;
if (enemy >= 11 && enemy <= 12)
	type = WOLF;
if (enemy >= 13 && enemy <= 13)
	type = BEETLE;
if (enemy >= 14 && enemy <= 19)
	type = ZOMBIE;
if (enemy >= 20)
	type = SWAMP_MONSTER;
SendEnemy(enemies, server, x, y, type, dir, enemyIDNum, waveNum);
Last edited on
Disch (13742)
How comfortable are you with statistical concepts like standard deviations? I have an idea for how to do this but I'm not 100% on the implementation details.
Bingocat4 (105)
Um I don't know what standard deviations are but what's your idea?
Disch (13742)
Okay so my idea might seem a little complicated... but I'll try to make it simple.

I'm assuming you don't have fixed levels here, and you just have unending waves of enemies that you keep track of (higher wave number = further along in the game the player is). If I'm wrong and you do have levels, then this is even easier and you can just use "levels" instead of "waves" as outlined below.


My idea is basically this:

1) Assign each enemy one or more 'natural' waves. IE: the wave they occur most frequently on.

2) The further away you are from that enemy's natural wave(s) (in either direction), the less likely that enemy is to appear.

3) Assign some other kind of "spread" value that indicates how far away from the natural wave you can be before the enemy frequency starts dropping off. IE, say for example the natural wave for an enemy is wave 10. If you assign a spread of 1, then the enemy will be extremely rare before wave 8 or after wave 12. But with a spread of 5, they will be seen frequently between waves 1-20.

4) In statistical terms... the "natural wave" is the mean... and the "spread" is the standard deviation. It effectively creates a bell curve of where the enemies will appear.

5) The tricky part (that I don't really know how to do), is to get a % chance based on that mean/stddev. IE, if your mean is wave 10, and you have a spread of 1.... then you'll have a 36% chance of it appearing on wave 10, but only a 25% chance of it appearing on wave 9, and like a 2% chance of it appearing on wave 8 (note: I'm pulling these percentages out of my ass, I have no idea what they are in reality -- that's the thing I can't figure out how to calculate). I posted another thread asking how to do this but no response yet: http://www.cplusplus.com/forum/lounge/159133/
Anyway, let's call this percentage 'X'. In theory you should be able to calculate X from the following info:
-- mean (natural wave)
-- stddev (spread)
-- current wave the player is on


6) Once you have X for all possible enemies, you normalize them (IE, adjust them linearly so the sum of all percentages is 100%). Example, on wave 2:
-- Slimes have a 36% chance
-- Rats have a 10% chance
-- Wolves have a 1% chance

Sum of all enemies' X = 47%. Normalize that to 100%: N = 100/47 = 2.128. So multiply each X value by N:

-- Slime:  36 * 2.128 = 76.6%
-- Rats:   10 * 2.128 = 21.3%
-- Wolves:  1 * 2.128 =  2.1
              (total) = 100%



7) Generate a random real number between [0,1) and use it to pick a enemy based on their appropriate percentages.
IE, if you get [0 , 0.766), you get a slime
if you get [0.766 , 0.979), you get a rat
if you get [0.979 , 1.0), you get a wolf






Again this might be unnecessarily complicated, but it is probably how I would approach this problem.




EDIT:


Okay so instead of using mean/stddev, you can create a bell curve with a sine wave to get 'X' for step 5.
This will create a more sudden dropoff, but should create a similar effect:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
// 3 values:
//   natural = the enemy's natural wave  (IE, where they appear most frequently
//
//   spread = the spread.  In this implementation, it is the 'endcap' of where the enemy can appear.
//      so for example, if natural=10 and spread=5, then the enemy will only appear on waves 5-15
//      (being more common the closer you are to wave 10)
//
//   curwave = the wave the player is currently on

double distance = natural - curwave;    // First, see how far the player is from the natural wave
distance /= spread*2.0;                 // Then normalize that value so it is between -0.5 and +0.5
distance += 0.5;                        // and ultimately between 0 and 1

// make sure it's in bounds
if(spread <= 0)     return 0;
if(spread >= 1)     return 0;

// use sine() as a bell curve generator (not ideal, but whatever)
return std::sin( spread * 3.14159 );



That code will get you 'X' as described in step 5.
Last edited on
Bingocat4 (105)
Ya that seems like exactly what I need, but not sure how to do it. Also, it just keeps track of what wave you are on. No set levels or anything. Everything is random. I just use this to figure out how many enemies should be on a wave and something else that the health should be multiplied by, and then use a for loop that picks an enemy. So it figures out how many enemies there should be, then picks that amount of enemies to put on the wave.

1
2
 
int amount= ((int((waveNum + 5) * ((rand() % 3 + 2) * .25)) + 1) * players.size());
float healthMult = 1 + ((rand() % waveNum) * .1);
Disch (13742)
So Lachlan Easton helped me out in that other thread. This is better than using sine() to generate your bell curve:

1
2
3
4
5
6
7
8
9
10
11
12
 
namespace c
{
    const double e =  2.71828182845904523536;
    const double pi = 3.14159265358979323846;
    const double rad2pi = std::sqrt(2*pi);
}

double getPercentage(int val, int mean, int stddev)
{
    double dif = val - mean;
    return std::pow(c::e,-0.5*dif*dif) / (c::rad2pi * stddev);
}


Just call getPercentage(current_wave, natural_wave, spread); to get X for step 5.
Last edited on
Bingocat4 (105)
Ok so would I do something like this to figure out what enemy should be picked? I can't try it tonight, but I will probably try it tomorrow. But the thing about setting a natural wave for each enemy is that the game goes on as long as you are alive. So on wave 100 or whatever there won't be an enemy with a natural wave set there.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
namespace c
{
    const double e =  2.71828182845904523536;
    const double pi = 3.14159265358979323846;
    const double rad2pi = std::sqrt(2*pi);
}

double getPercentage(int val, int mean, int stddev)
{
    double dif = val - mean;
    return std::pow(c::e,-0.5*dif*dif) / (c::rad2pi * stddev);
}

enum ENEMIES{SLIME, RAT, ZOMBIE, BEETLE, WOLF, BIG_SPIDER, SWAMP_MONSTER};
int naturalWaves[7] = {1, 3, 5, 8, 10, 15, 20};

void SpawnWave() {
	int randNum = ((int((waveNum + 5) * ((rand() % 3 + 2) * .25)) + 1) * players.size());
	for (int i = 0; i < randNum; i++) {
		float enemyChance[7];
		for (int j = 0; j < 7; j++) {
			enemyChance[j] = getPercentage(waveNum, naturalWaves[i], 5) * 2.128;
		}
		int type = (rand() % 1000) * .0001;
		SendEnemy(enemies, server, x, y, type, dir, enemyIDNum, waveNum);
	}
}

Last edited on
Disch (13742)
This was really fun for me so I made this test program which appears to work. You can use it as an example. Feel free to ask any Qs:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 

#include <random>
#include <cmath>
#include <ctime>

// note I'm using C++11 random number generators here because they're better
//   Also note I'm using a global rng object for simplicity, but I don't recommend making
//   this global
std::mt19937 rnge( unsigned(time(nullptr)) );


// different types of enemies available
enum Enemy
{
    slime,
    rat,
    wolf,
    beetle,
    zombie,
    swampMonster,

    // do not put any other enemy types after these
    count,
    none = -1
};

// struct to house enemy placement info
struct EnemyInfo
{
    Enemy   enemy;
    int     naturalwave;
    int     spread;
};

//////////////////
//  Assigned data.  Note this should probably be stored externally in files or something and not
//   hardcoded like this.  I'm only hardcoding for simplicity of this example, but it's generally
//   bad practice to do this in actual programs.

const EnemyInfo enemyData[] = {
    { Enemy::slime,             5,   5 },       // slimes appear early on, naturally at wave 5, with a spread of 5
    { Enemy::rat,               8,   3 },       // rats occur a little later
    { Enemy::wolf,              9,   4 },       //   etc
    { Enemy::beetle,            12,  3 },
    { Enemy::rat,               12,  5 },       // rats make another appearance just to illustrate you can have mulitple
    { Enemy::zombie,            15,  7 },       //   pools of the same enemy
    { Enemy::swampMonster,      20,  2 }
};

// Some mathematical constants
namespace c
{
    const double pi = 3.14159265358979323846;
    const double rad2pi = std::sqrt(2*pi);
}

// function to get the odds of 'val' in a normalized distribution
//   defined by mean,stdddev
double getChance(int val, int mean, int stddev)
{
    double dif = (val - mean) / (double)(stddev);
    return std::exp(-0.5*dif*dif) / (c::rad2pi * stddev);
}

/////////////////////
//  The actual function for randomly determining which enemy you get on a given wave
Enemy generateEnemyType(int currentwave)
{
    static const double minchance = 0.0001;    // any less than a 0.01% chance is not worth considering

    double enemyprobability[Enemy::count] = {};     // zero-filled array

    // figure out the probabilities of each enemy
    double sum = 0;
    for(auto& i : enemyData)
    {
        double chance = getChance( currentwave, i.naturalwave, i.spread );
        if(chance < minchance)      continue;       // discard it if it's extraordinarily unlikely

        enemyprobability[i.enemy] += chance;
        sum += chance;
    }

    // now that we have the probabilities of each enemy, generate a random number to pick one of them

    // make sure at least 1 kind of enemy is possible on this wave
    if(!sum)
        return Enemy::none;     // no enemies possible on this wave

    // otherwise, generate random number 'r' which is between 0,sum
    double r = std::uniform_real_distribution<double>(0,sum)(rnge);

    // use 'r' to choose our enemy
    for(int i = 0; i < Enemy::count; ++i)
    {
        if(!enemyprobability[i])        continue;       // no chance for this enemy

        // otherwise, did we get this enemy?
        if(r < enemyprobability[i])         // yes, return it
            return static_cast<Enemy>(i);
        else                                // no, keep looking
            r -= enemyprobability[i];
    }

    // we should never reach here, but just in case...
    return Enemy::none;
}




//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////////////////////////////////////
//  Testbed program
//////////////////////////////////////////////
//////////////////////////////////////////////
//////////////////////////////////////////////


#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
    while(true)
    {
        int wave;

        cout << "Enter a wave number (or 0 to exit):  ";
        cin >> wave;
        if(!cin || wave <= 0)
            break;

        Enemy en = generateEnemyType(wave);

        if(en == Enemy::none)
            cout << "<No enemies possible for this wave>\n\n";
        else
        {
            static const char* names[] = {
                "slime","rat","wolf","beetle","zombie","swamp monster"};
            
            cout << "Enemy for this wave:  " << names[en] << "\n\n";
        }
    }

    return 0;
}



EDIT: Updated with changes/corrections to getChance function.
Last edited on
Bingocat4 (105)
Hmm I couldn't try out your program probably because I don't think my version Microsoft visual c++ express has c++ 11, but I will try taking pieces out and trying it myself.
Disch (13742)
You should probably update your version of MSVC++.

The above code compiles and runs with MSVS 2012.

Not having C++11 features is a huge deal. They're terrific. You're doing yourself a disservice by using such an outdated compiler.
Last edited on
Bingocat4 (105)
Ok I got MSVS 2013 and tested it. I added a for loop to simulate what a wave of enemies would be like and it's sorta weird. Like on the first wave it has slimes and some rats, then on the wave after that all of the slimes dissapear and it is just a ton of rats. Does the spread setting not spread to waves above it? Does it only have a chance to appear before its natural wave or what? That's what it seems like.
Last edited on
Disch (13742)
Ok I got MSVS 2013 and tested it. I added a for loop to simulate what a wave of enemies would be like and it's sorta weird. Like on the first wave it has slimes and some rats, then on the wave after that all of the slimes dissapear and it is just a ton of rats.


What are your settings for slimes/rats?

Does the spread setting not spread to waves above it?


It goes both above and below.
Bingocat4 (105)
Same as yours. First wave is 99% slime second is 99% rat third is rat and wolf. Should I set an enemy type for every wave or something? I want it to not be like a ton of rats for a wave. A good mixture like 3 slimes, 4 rats, and a wolf or something for early waves. Maybe it would be better if the enemy is a little less likely on its natural wave or something?
Last edited on
Disch (13742)
Hrm... that's not happening for me at all. The distribution is about what I'd expect.

Can you run this code and post the output?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
// testbed:

#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
    static const char* const names[] = {"Sl","Rt","Wf","Bt","Zm","SM"};
    int count[Enemy::count];

    for(int wave = 0; wave < 20; ++wave)
    {
        for(auto& i : count) i = 0;

        for(int i = 0; i < 1000; ++i)
        {
            ++count[ generateEnemyType(wave) ];
        }

        cout << "Wave " << setw(2) << setfill('0') << wave << ": ";
        for(int i = 0; i < Enemy::count; ++i)
        {
            cout << names[i] << "=" << setw(2) << setfill('0') << (count[i]/10) << "%   ";
        }
        cout << '\n';
    }
}



My output:

Wave 00: Sl=68%   Rt=12%   Wf=11%   Bt=00%   Zm=07%   SM=00%
Wave 01: Sl=60%   Rt=16%   Wf=16%   Bt=00%   Zm=07%   SM=00%
Wave 02: Sl=51%   Rt=25%   Wf=16%   Bt=00%   Zm=06%   SM=00%
Wave 03: Sl=43%   Rt=28%   Wf=18%   Bt=01%   Zm=09%   SM=00%
Wave 04: Sl=38%   Rt=34%   Wf=18%   Bt=01%   Zm=06%   SM=00%
Wave 05: Sl=28%   Rt=38%   Wf=21%   Bt=02%   Zm=07%   SM=00%
Wave 06: Sl=25%   Rt=39%   Wf=22%   Bt=05%   Zm=06%   SM=00%
Wave 07: Sl=18%   Rt=43%   Wf=23%   Bt=08%   Zm=06%   SM=00%
Wave 08: Sl=15%   Rt=42%   Wf=21%   Bt=12%   Zm=07%   SM=00%
Wave 09: Sl=10%   Rt=41%   Wf=22%   Bt=17%   Zm=08%   SM=00%
Wave 10: Sl=10%   Rt=37%   Wf=19%   Bt=22%   Zm=10%   SM=00%
Wave 11: Sl=08%   Rt=33%   Wf=18%   Bt=29%   Zm=10%   SM=00%
Wave 12: Sl=07%   Rt=31%   Wf=17%   Bt=32%   Zm=11%   SM=00%
Wave 13: Sl=06%   Rt=29%   Wf=16%   Bt=33%   Zm=14%   SM=00%
Wave 14: Sl=05%   Rt=27%   Wf=13%   Bt=36%   Zm=16%   SM=00%
Wave 15: Sl=04%   Rt=30%   Wf=12%   Bt=28%   Zm=21%   SM=02%
Wave 16: Sl=03%   Rt=24%   Wf=10%   Bt=24%   Zm=24%   SM=11%
Wave 17: Sl=01%   Rt=22%   Wf=06%   Bt=16%   Zm=23%   SM=29%
Wave 18: Sl=01%   Rt=15%   Wf=03%   Bt=07%   Zm=20%   SM=53%
Wave 19: Sl=00%   Rt=11%   Wf=01%   Bt=03%   Zm=18%   SM=65%



The higher rat numbers are probably because there are 2 rat pools.
Bingocat4 (105)
Ok I think it was since there was 2 rat pools. I was able to use your code and put it in. I had to change a lot of things thought because of variables already being used and stuff, but it works now. Thanks for all the help!
Topic archived. No new replies allowed.