4 - Procedural Generation
Procedural generation is the algorithmic creation of game content rather than manual design. This technique is used to create diverse, often infinite game worlds, levels, textures, and other assets. This section covers key procedural generation algorithms and their implementation in C#.
Introduction to Procedural Generation
Procedural generation offers several advantages in game development:
- Content Variety: Creates diverse content that keeps games fresh and replayable.
- Development Efficiency: Reduces the manual effort required to create large amounts of content.
- Memory Efficiency: Generates content on-demand rather than storing it all.
- Emergent Gameplay: Creates unexpected scenarios and challenges.
Common applications include:
- Terrain and level generation
- Dungeon and cave systems
- Item and loot generation
- NPC behavior and dialogue
- Textures and visual effects
- Music and sound effects
Random Number Generation
The foundation of procedural generation is controlled randomness. Good random number generation is crucial for creating varied but consistent content.
Pseudo-Random Number Generators
public class RandomGenerator
{
private Random random;
public RandomGenerator(int seed)
{
random = new Random(seed);
}
public float Range(float min, float max)
{
return (float)(random.NextDouble() * (max - min) + min);
}
public int Range(int min, int max)
{
return random.Next(min, max);
}
public bool Chance(float probability)
{
return random.NextDouble() < probability;
}
public T Choose<T>(T[] options)
{
return options[random.Next(options.Length)];
}
public T Choose<T>(List<T> options)
{
return options[random.Next(options.Count)];
}
public T Choose<T>(T[] options, float[] weights)
{
if (options.Length != weights.Length)
throw new ArgumentException("Options and weights arrays must have the same length");
float totalWeight = 0;
for (int i = 0; i < weights.Length; i++)
{
totalWeight += weights[i];
}
float value = (float)(random.NextDouble() * totalWeight);
float cumulativeWeight = 0;
for (int i = 0; i < weights.Length; i++)
{
cumulativeWeight += weights[i];
if (value < cumulativeWeight)
return options[i];
}
return options[options.Length - 1];
}
public void Shuffle<T>(T[] array)
{
int n = array.Length;
while (n > 1)
{
n--;
int k = random.Next(n + 1);
T value = array[k];
array[k] = array[n];
array[n] = value;
}
}
}
Seeded Random Generation
Seeded random generation ensures that the same input seed produces the same sequence of random numbers, which is essential for reproducible procedural generation.
public class WorldGenerator
{
private RandomGenerator random;
public WorldGenerator(int seed)
{
random = new RandomGenerator(seed);
}
public int[,] GenerateWorld(int width, int height)
{
int[,] world = new int[width, height];
// Fill the world with procedurally generated content
for (int x = 0; x < width; x++)
{
for (int y = 0; y < height; y++)
{
// Use the random generator to determine the tile type
world[x, y] = random.Range(0, 4); // 0-3 for different tile types
}
}
return world;
}
}
Noise Algorithms
Noise algorithms generate smooth, natural-looking random values that are essential for creating terrain, textures, and other organic elements.
Perlin Noise
public class PerlinNoise
{
private int[] permutation;
public PerlinNoise(int seed)
{
Random random = new Random(seed);
// Initialize the permutation array
permutation = new int[512];
int[] p = new int[256];
// Fill p with values from 0 to 255
for (int i = 0; i < 256; i++)
{
p[i] = i;
}
// Shuffle using the Fisher-Yates algorithm
for (int i = 255; i > 0; i--)
{
int j = random.Next(i + 1);
(p[i], p[j]) = (p[j], p[i]);
}
// Duplicate the permutation array
for (int i = 0; i < 256; i++)
{
permutation[i] = permutation[i + 256] = p[i];
}
}
public float Noise(float x, float y, float z)
{
// Find unit cube that contains the point
int X = (int)Math.Floor(x) & 255;
int Y = (int)Math.Floor(y) & 255;
int Z = (int)Math.Floor(z) & 255;
// Find relative x, y, z of point in cube
x -= (float)Math.Floor(x);
y -= (float)Math.Floor(y);
z -= (float)Math.Floor(z);
// Compute fade curves for each of x, y, z
float u = Fade(x);
float v = Fade(y);
float w = Fade(z);
// Hash coordinates of the 8 cube corners
int A = permutation[X] + Y;
int AA = permutation[A] + Z;
int AB = permutation[A + 1] + Z;
int B = permutation[X + 1] + Y;
int BA = permutation[B] + Z;
int BB = permutation[B + 1] + Z;
// Add blended results from 8 corners of cube
float result = Lerp(w, Lerp(v, Lerp(u, Grad(permutation[AA], x, y, z),
Grad(permutation[BA], x - 1, y, z)),
Lerp(u, Grad(permutation[AB], x, y - 1, z),
Grad(permutation[BB], x - 1, y - 1, z))),
Lerp(v, Lerp(u, Grad(permutation[AA + 1], x, y, z - 1),
Grad(permutation[BA + 1], x - 1, y, z - 1)),
Lerp(u, Grad(permutation[AB + 1], x, y - 1, z - 1),
Grad(permutation[BB + 1], x - 1, y - 1, z - 1))));
// Scale to [-1, 1]
return result;
}
private float Fade(float t)
{
// Fade function as defined by Ken Perlin
// 6t^5 - 15t^4 + 10t^3
return t * t * t * (t * (t * 6 - 15) + 10);
}
private float Lerp(float t, float a, float b)
{
return a + t * (b - a);
}
private float Grad(int hash, float x, float y, float z)
{
// Convert low 4 bits of hash code into 12 gradient directions
int h = hash & 15;
float u = h < 8 ? x : y;
float v = h < 4 ? y : h == 12 || h == 14 ? x : z;
return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
}
// 2D noise
public float Noise(float x, float y)
{
return Noise(x, y, 0);
}
// Fractal Brownian Motion (fBm) - layered noise
public float FractalBrownianMotion(float x, float y, int octaves, float persistence)
{
float total = 0;
float frequency = 1;
float amplitude = 1;
float maxValue = 0;
for (int i = 0; i < octaves; i++)
{
total += Noise(x * frequency, y * frequency) * amplitude;
maxValue += amplitude;
amplitude *= persistence;
frequency *= 2;
}
return total / maxValue;
}
}
Simplex Noise
public class SimplexNoise
{
private int[] perm;
private float[][] grad3;
public SimplexNoise(int seed)
{
Random random = new Random(seed);
// Initialize the permutation array
perm = new int[512];
int[] p = new int[256];
// Fill p with values from 0 to 255
for (int i = 0; i < 256; i++)
{
p[i] = i;
}
// Shuffle using the Fisher-Yates algorithm
for (int i = 255; i > 0; i--)
{
int j = random.Next(i + 1);
(p[i], p[j]) = (p[j], p[i]);
}
// Duplicate the permutation array
for (int i = 0; i < 256; i++)
{
perm[i] = perm[i + 256] = p[i];
}
// Initialize gradient vectors
grad3 = new float[12][];
grad3[0] = new float[] { 1, 1, 0 };
grad3[1] = new float[] { -1, 1, 0 };
grad3[2] = new float[] { 1, -1, 0 };
grad3[3] = new float[] { -1, -1, 0 };
grad3[4] = new float[] { 1, 0, 1 };
grad3[5] = new float[] { -1, 0, 1 };
grad3[6] = new float[] { 1, 0, -1 };
grad3[7] = new float[] { -1, 0, -1 };
grad3[8] = new float[] { 0, 1, 1 };
grad3[9] = new float[] { 0, -1, 1 };
grad3[10] = new float[] { 0, 1, -1 };
grad3[11] = new float[] { 0, -1, -1 };
}
private float Dot(float[] g, float x, float y)
{
return g[0] * x + g[1] * y;
}
private float Dot(float[] g, float x, float y, float z)
{
return g[0] * x + g[1] * y + g[2] * z;
}
// 2D Simplex noise
public float Noise(float xin, float yin)
{
// Noise contributions from the three corners
float n0, n1, n2;
// Skew the input space to determine which simplex cell we're in
const float F2 = 0.5f * (MathF.Sqrt(3.0f) - 1.0f);
float s = (xin + yin) * F2; // Hairy factor for 2D
int i = FastFloor(xin + s);
int j = FastFloor(yin + s);
const float G2 = (3.0f - MathF.Sqrt(3.0f)) / 6.0f;
float t = (i + j) * G2;
float X0 = i - t; // Unskew the cell origin back to (x,y) space
float Y0 = j - t;
float x0 = xin - X0; // The x,y distances from the cell origin
float y0 = yin - Y0;
// For the 2D case, the simplex shape is an equilateral triangle.
// Determine which simplex we are in.
int i1, j1; // Offsets for second (middle) corner of simplex in (i,j) coords
if (x0 > y0) { i1 = 1; j1 = 0; } // lower triangle, XY order: (0,0)->(1,0)->(1,1)
else { i1 = 0; j1 = 1; } // upper triangle, YX order: (0,0)->(0,1)->(1,1)
// A step of (1,0) in (i,j) means a step of (1-c,-c) in (x,y), and
// a step of (0,1) in (i,j) means a step of (-c,1-c) in (x,y), where
// c = (3-sqrt(3))/6
float x1 = x0 - i1 + G2; // Offsets for middle corner in (x,y) unskewed coords
float y1 = y0 - j1 + G2;
float x2 = x0 - 1.0f + 2.0f * G2; // Offsets for last corner in (x,y) unskewed coords
float y2 = y0 - 1.0f + 2.0f * G2;
// Work out the hashed gradient indices of the three simplex corners
int ii = i & 255;
int jj = j & 255;
int gi0 = perm[ii + perm[jj]] % 12;
int gi1 = perm[ii + i1 + perm[jj + j1]] % 12;
int gi2 = perm[ii + 1 + perm[jj + 1]] % 12;
// Calculate the contribution from the three corners
float t0 = 0.5f - x0 * x0 - y0 * y0;
if (t0 < 0) n0 = 0.0f;
else
{
t0 *= t0;
n0 = t0 * t0 * Dot(grad3[gi0], x0, y0); // (x,y) of grad3 used for 2D gradient
}
float t1 = 0.5f - x1 * x1 - y1 * y1;
if (t1 < 0) n1 = 0.0f;
else
{
t1 *= t1;
n1 = t1 * t1 * Dot(grad3[gi1], x1, y1);
}
float t2 = 0.5f - x2 * x2 - y2 * y2;
if (t2 < 0) n2 = 0.0f;
else
{
t2 *= t2;
n2 = t2 * t2 * Dot(grad3[gi2], x2, y2);
}
// Add contributions from each corner to get the final noise value.
// The result is scaled to return values in the interval [-1,1].
return 70.0f * (n0 + n1 + n2);
}
private int FastFloor(float x)
{
return x > 0 ? (int)x : (int)x - 1;
}
// Fractal Brownian Motion (fBm) - layered noise
public float FractalBrownianMotion(float x, float y, int octaves, float persistence)
{
float total = 0;
float frequency = 1;
float amplitude = 1;
float maxValue = 0;
for (int i = 0; i < octaves; i++)
{
total += Noise(x * frequency, y * frequency) * amplitude;
maxValue += amplitude;
amplitude *= persistence;
frequency *= 2;
}
return total / maxValue;
}
}
Value Noise
public class ValueNoise
{
private float[,] values;
private int size;
public ValueNoise(int seed, int size = 256)
{
this.size = size;
values = new float[size, size];
Random random = new Random(seed);
// Generate random values
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
values[i, j] = (float)random.NextDouble() * 2 - 1; // Range: [-1, 1]
}
}
}
public float Noise(float x, float y)
{
// Get integer coordinates
int x0 = (int)Math.Floor(x) % size;
int y0 = (int)Math.Floor(y) % size;
// Ensure positive indices
if (x0 < 0) x0 += size;
if (y0 < 0) y0 += size;
// Get next coordinates (wrapping around)
int x1 = (x0 + 1) % size;
int y1 = (y0 + 1) % size;
// Get fractional part
float sx = x - (float)Math.Floor(x);
float sy = y - (float)Math.Floor(y);
// Interpolate between values
float n0 = values[x0, y0];
float n1 = values[x1, y0];
float ix0 = Lerp(n0, n1, SmoothStep(sx));
float n2 = values[x0, y1];
float n3 = values[x1, y1];
float ix1 = Lerp(n2, n3, SmoothStep(sx));
return Lerp(ix0, ix1, SmoothStep(sy));
}
private float Lerp(float a, float b, float t)
{
return a + t * (b - a);
}
private float SmoothStep(float t)
{
return t * t * (3 - 2 * t);
}
// Fractal Brownian Motion (fBm) - layered noise
public float FractalBrownianMotion(float x, float y, int octaves, float persistence)
{
float total = 0;
float frequency = 1;
float amplitude = 1;
float maxValue = 0;
for (int i = 0; i < octaves; i++)
{
total += Noise(x * frequency, y * frequency) * amplitude;
maxValue += amplitude;
amplitude *= persistence;
frequency *= 2;
}
return total / maxValue;
}
}
Terrain Generation
Terrain generation creates landscapes, including mountains, valleys, rivers, and other natural features.
Heightmap Generation
public class TerrainGenerator
{
private PerlinNoise noise;
public TerrainGenerator(int seed)
{
noise = new PerlinNoise(seed);
}
public float[,] GenerateHeightmap(int width, int height, float scale, int octaves, float persistence, float lacunarity)
{
float[,] heightmap = new float[width, height];
// Random offsets for variation
Random random = new Random();
Vector2[] octaveOffsets = new Vector2[octaves];
for (int i = 0; i < octaves; i++)
{
float offsetX = random.Next(-100000, 100000);
float offsetY = random.Next(-100000, 100000);
octaveOffsets[i] = new Vector2(offsetX, offsetY);
}
if (scale <= 0)
scale = 0.0001f;
float maxNoiseHeight = float.MinValue;
float minNoiseHeight = float.MaxValue;
// Calculate heightmap values
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
float amplitude = 1;
float frequency = 1;
float noiseHeight = 0;
// Calculate noise value using multiple octaves
for (int i = 0; i < octaves; i++)
{
float sampleX = (x / scale) * frequency + octaveOffsets[i].x;
float sampleY = (y / scale) * frequency + octaveOffsets[i].y;
float perlinValue = noise.Noise(sampleX, sampleY);
noiseHeight += perlinValue * amplitude;
amplitude *= persistence;
frequency *= lacunarity;
}
// Track min and max noise values
if (noiseHeight > maxNoiseHeight)
maxNoiseHeight = noiseHeight;
else if (noiseHeight < minNoiseHeight)
minNoiseHeight = noiseHeight;
heightmap[x, y] = noiseHeight;
}
}
// Normalize heightmap values to [0, 1]
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
heightmap[x, y] = Mathf.InverseLerp(minNoiseHeight, maxNoiseHeight, heightmap[x, y]);
}
}
return heightmap;
}
// Apply terrain types based on height and other factors
public int[,] GenerateTerrainTypes(float[,] heightmap, float waterLevel, float sandLevel, float grassLevel, float rockLevel)
{
int width = heightmap.GetLength(0);
int height = heightmap.GetLength(1);
int[,] terrainTypes = new int[width, height];
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
float height = heightmap[x, y];
if (height < waterLevel)
terrainTypes[x, y] = 0; // Water
else if (height < sandLevel)
terrainTypes[x, y] = 1; // Sand
else if (height < grassLevel)
terrainTypes[x, y] = 2; // Grass
else if (height < rockLevel)
terrainTypes[x, y] = 3; // Rock
else
terrainTypes[x, y] = 4; // Snow
}
}
return terrainTypes;
}
}
// Helper struct for Vector2
public struct Vector2
{
public float x;
public float y;
public Vector2(float x, float y)
{
this.x = x;
this.y = y;
}
}
// Helper class for Mathf functions
public static class Mathf
{
public static float InverseLerp(float a, float b, float value)
{
if (a != b)
return (value - a) / (b - a);
else
return 0.0f;
}
}
Hydraulic Erosion
public class HydraulicErosion
{
private float[,] heightmap;
private int width, height;
private Random random;
// Erosion parameters
private int dropletLifetime = 30;
private float inertia = 0.05f;
private float sedimentCapacityFactor = 4;
private float minSedimentCapacity = 0.01f;
private float depositSpeed = 0.3f;
private float erodeSpeed = 0.3f;
public HydraulicErosion(float[,] heightmap, int seed)
{
this.heightmap = heightmap;
width = heightmap.GetLength(0);
height = heightmap.GetLength(1);
random = new Random(seed);
}
public float[,] Erode(int iterations)
{
for (int i = 0; i < iterations; i++)
{
// Create water droplet at random position
int x = random.Next(width);
int y = random.Next(height);
float posX = x;
float posY = y;
float dirX = 0;
float dirY = 0;
float speed = 1;
float water = 1;
float sediment = 0;
for (int lifetime = 0; lifetime < dropletLifetime; lifetime++)
{
int nodeX = (int)posX;
int nodeY = (int)posY;
// Stop if we're outside the map
if (nodeX < 0 || nodeX >= width - 1 || nodeY < 0 || nodeY >= height - 1)
break;
// Calculate droplet's offset inside the cell (0,0) to (1,1)
float cellOffsetX = posX - nodeX;
float cellOffsetY = posY - nodeY;
// Calculate heights at the four nodes of the current cell
float heightNW = heightmap[nodeX, nodeY];
float heightNE = heightmap[nodeX + 1, nodeY];
float heightSW = heightmap[nodeX, nodeY + 1];
float heightSE = heightmap[nodeX + 1, nodeY + 1];
// Calculate the droplet's direction of flow with bilinear interpolation of height difference
float gradientX = (heightNE - heightNW) * (1 - cellOffsetY) + (heightSE - heightSW) * cellOffsetY;
float gradientY = (heightSW - heightNW) * (1 - cellOffsetX) + (heightSE - heightNE) * cellOffsetX;
// Update the droplet's direction, accounting for inertia
dirX = dirX * inertia - gradientX * (1 - inertia);
dirY = dirY * inertia - gradientY * (1 - inertia);
// Normalize direction
float len = MathF.Sqrt(dirX * dirX + dirY * dirY);
if (len != 0)
{
dirX /= len;
dirY /= len;
}
// Update position
posX += dirX;
posY += dirY;
// Stop if we've flowed over the edge of the map
if (posX < 0 || posX >= width - 1 || posY < 0 || posY >= height - 1)
break;
// Calculate new height and direction of flow with bilinear interpolation
nodeX = (int)posX;
nodeY = (int)posY;
cellOffsetX = posX - nodeX;
cellOffsetY = posY - nodeY;
heightNW = heightmap[nodeX, nodeY];
heightNE = heightmap[nodeX + 1, nodeY];
heightSW = heightmap[nodeX, nodeY + 1];
heightSE = heightmap[nodeX + 1, nodeY + 1];
float height = heightNW * (1 - cellOffsetX) * (1 - cellOffsetY) +
heightNE * cellOffsetX * (1 - cellOffsetY) +
heightSW * (1 - cellOffsetX) * cellOffsetY +
heightSE * cellOffsetX * cellOffsetY;
// Calculate the droplet's sediment capacity
float sedimentCapacity = MathF.Max(minSedimentCapacity, speed * water * sedimentCapacityFactor);
// If carrying more sediment than capacity, deposit sediment
if (sediment > sedimentCapacity)
{
float amountToDeposit = (sediment - sedimentCapacity) * depositSpeed;
sediment -= amountToDeposit;
// Add the sediment to the four nodes of the current cell
heightmap[nodeX, nodeY] += amountToDeposit * (1 - cellOffsetX) * (1 - cellOffsetY);
heightmap[nodeX + 1, nodeY] += amountToDeposit * cellOffsetX * (1 - cellOffsetY);
heightmap[nodeX, nodeY + 1] += amountToDeposit * (1 - cellOffsetX) * cellOffsetY;
heightmap[nodeX + 1, nodeY + 1] += amountToDeposit * cellOffsetX * cellOffsetY;
}
else
{
// Erode a fraction of the droplet's current capacity
float amountToErode = MathF.Min((sedimentCapacity - sediment) * erodeSpeed, -height);
// Erode from the four nodes of the current cell
heightmap[nodeX, nodeY] -= amountToErode * (1 - cellOffsetX) * (1 - cellOffsetY);
heightmap[nodeX + 1, nodeY] -= amountToErode * cellOffsetX * (1 - cellOffsetY);
heightmap[nodeX, nodeY + 1] -= amountToErode * (1 - cellOffsetX) * cellOffsetY;
heightmap[nodeX + 1, nodeY + 1] -= amountToErode * cellOffsetX * cellOffsetY;
// Add the eroded amount to the droplet's sediment
sediment += amountToErode;
}
// Update droplet's speed and water content
speed = MathF.Sqrt(speed * speed + height);
water *= 0.99f;
}
}
return heightmap;
}
}
Dungeon Generation
Dungeon generation creates indoor environments with rooms, corridors, and other features.
Binary Space Partitioning (BSP)
public class BSPDungeonGenerator
{
private int width, height;
private int minRoomSize;
private int maxRoomSize;
private Random random;
public BSPDungeonGenerator(int width, int height, int minRoomSize, int maxRoomSize, int seed)
{
this.width = width;
this.height = height;
this.minRoomSize = minRoomSize;
this.maxRoomSize = maxRoomSize;
random = new Random(seed);
}
public int[,] GenerateDungeon()
{
// Initialize dungeon with walls
int[,] dungeon = new int[width, height];
for (int x = 0; x < width; x++)
{
for (int y = 0; y < height; y++)
{
dungeon[x, y] = 1; // 1 = wall
}
}
// Create the root node of the BSP tree
BSPNode rootNode = new BSPNode(0, 0, width, height);
// Split the space recursively
SplitNode(rootNode, 0);
// Create rooms in the leaf nodes
List<Room> rooms = CreateRooms(rootNode);
// Carve rooms into the dungeon
foreach (Room room in rooms)
{
for (int x = room.X; x < room.X + room.Width; x++)
{
for (int y = room.Y; y < room.Y + room.Height; y++)
{
dungeon[x, y] = 0; // 0 = floor
}
}
}
// Connect rooms with corridors
ConnectRooms(dungeon, rooms);
return dungeon;
}
private void SplitNode(BSPNode node, int depth)
{
// Stop splitting if the node is too small
if (node.Width <= minRoomSize * 2 || node.Height <= minRoomSize * 2)
return;
// Limit the depth of the tree
if (depth > 10)
return;
// Decide whether to split horizontally or vertically
bool splitHorizontally = random.Next(2) == 0;
// If the node is much wider than tall, split vertically
if (node.Width > node.Height * 1.5)
splitHorizontally = false;
// If the node is much taller than wide, split horizontally
else if (node.Height > node.Width * 1.5)
splitHorizontally = true;
int splitPosition;
if (splitHorizontally)
{
// Split horizontally
splitPosition = random.Next(minRoomSize, node.Height - minRoomSize);
node.Left = new BSPNode(node.X, node.Y, node.Width, splitPosition);
node.Right = new BSPNode(node.X, node.Y + splitPosition, node.Width, node.Height - splitPosition);
}
else
{
// Split vertically
splitPosition = random.Next(minRoomSize, node.Width - minRoomSize);
node.Left = new BSPNode(node.X, node.Y, splitPosition, node.Height);
node.Right = new BSPNode(node.X + splitPosition, node.Y, node.Width - splitPosition, node.Height);
}
// Recursively split the children
SplitNode(node.Left, depth + 1);
SplitNode(node.Right, depth + 1);
}
private List<Room> CreateRooms(BSPNode node)
{
List<Room> rooms = new List<Room>();
if (node.Left != null || node.Right != null)
{
// This is not a leaf node, so get rooms from children
if (node.Left != null)
rooms.AddRange(CreateRooms(node.Left));
if (node.Right != null)
rooms.AddRange(CreateRooms(node.Right));
}
else
{
// This is a leaf node, so create a room
int roomWidth = random.Next(minRoomSize, Math.Min(node.Width - 2, maxRoomSize));
int roomHeight = random.Next(minRoomSize, Math.Min(node.Height - 2, maxRoomSize));
int roomX = node.X + random.Next(1, node.Width - roomWidth - 1);
int roomY = node.Y + random.Next(1, node.Height - roomHeight - 1);
Room room = new Room(roomX, roomY, roomWidth, roomHeight);
rooms.Add(room);
node.Room = room;
}
return rooms;
}
private void ConnectRooms(int[,] dungeon, List<Room> rooms)
{
// Connect each room to the next one
for (int i = 0; i < rooms.Count - 1; i++)
{
Room roomA = rooms[i];
Room roomB = rooms[i + 1];
// Get the center of each room
int centerAX = roomA.X + roomA.Width / 2;
int centerAY = roomA.Y + roomA.Height / 2;
int centerBX = roomB.X + roomB.Width / 2;
int centerBY = roomB.Y + roomB.Height / 2;
// Randomly decide whether to go horizontal-vertical or vertical-horizontal
if (random.Next(2) == 0)
{
// Horizontal then vertical
CreateHorizontalCorridor(dungeon, centerAX, centerBX, centerAY);
CreateVerticalCorridor(dungeon, centerAY, centerBY, centerBX);
}
else
{
// Vertical then horizontal
CreateVerticalCorridor(dungeon, centerAY, centerBY, centerAX);
CreateHorizontalCorridor(dungeon, centerAX, centerBX, centerBY);
}
}
}
private void CreateHorizontalCorridor(int[,] dungeon, int x1, int x2, int y)
{
int start = Math.Min(x1, x2);
int end = Math.Max(x1, x2);
for (int x = start; x <= end; x++)
{
if (x >= 0 && x < width && y >= 0 && y < height)
dungeon[x, y] = 0; // 0 = floor
}
}
private void CreateVerticalCorridor(int[,] dungeon, int y1, int y2, int x)
{
int start = Math.Min(y1, y2);
int end = Math.Max(y1, y2);
for (int y = start; y <= end; y++)
{
if (x >= 0 && x < width && y >= 0 && y < height)
dungeon[x, y] = 0; // 0 = floor
}
}
}
public class BSPNode
{
public int X { get; set; }
public int Y { get; set; }
public int Width { get; set; }
public int Height { get; set; }
public BSPNode Left { get; set; }
public BSPNode Right { get; set; }
public Room Room { get; set; }
public BSPNode(int x, int y, int width, int height)
{
X = x;
Y = y;
Width = width;
Height = height;
}
}
public class Room
{
public int X { get; set; }
public int Y { get; set; }
public int Width { get; set; }
public int Height { get; set; }
public Room(int x, int y, int width, int height)
{
X = x;
Y = y;
Width = width;
Height = height;
}
}
Cellular Automata
public class CellularAutomataGenerator
{
private int width, height;
private float initialWallProbability;
private int birthLimit;
private int deathLimit;
private Random random;
public CellularAutomataGenerator(int width, int height, float initialWallProbability, int birthLimit, int deathLimit, int seed)
{
this.width = width;
this.height = height;
this.initialWallProbability = initialWallProbability;
this.birthLimit = birthLimit;
this.deathLimit = deathLimit;
random = new Random(seed);
}
public int[,] GenerateCave(int iterations)
{
// Initialize map with random walls
int[,] map = new int[width, height];
for (int x = 0; x < width; x++)
{
for (int y = 0; y < height; y++)
{
// Add more walls near the edges
if (x == 0 || x == width - 1 || y == 0 || y == height - 1)
map[x, y] = 1; // 1 = wall
else
map[x, y] = random.NextDouble() < initialWallProbability ? 1 : 0;
}
}
// Run the cellular automata algorithm for several iterations
for (int i = 0; i < iterations; i++)
{
map = SimulateStep(map);
}
return map;
}
private int[,] SimulateStep(int[,] oldMap)
{
int[,] newMap = new int[width, height];
// Apply the rules to each cell
for (int x = 0; x < width; x++)
{
for (int y = 0; y < height; y++)
{
// Count the number of walls in the 3x3 neighborhood
int wallCount = CountWallsAround(oldMap, x, y);
// Apply the rules
if (oldMap[x, y] == 1) // If the cell is a wall
{
// Death rule: if there are too few walls around, the cell dies
newMap[x, y] = wallCount < deathLimit ? 0 : 1;
}
else // If the cell is empty
{
// Birth rule: if there are enough walls around, a new wall is born
newMap[x, y] = wallCount > birthLimit ? 1 : 0;
}
// Ensure the edges are always walls
if (x == 0 || x == width - 1 || y == 0 || y == height - 1)
newMap[x, y] = 1;
}
}
return newMap;
}
private int CountWallsAround(int[,] map, int x, int y)
{
int count = 0;
for (int i = -1; i <= 1; i++)
{
for (int j = -1; j <= 1; j++)
{
int nx = x + i;
int ny = y + j;
// Check if the neighbor is outside the map
if (nx < 0 || nx >= width || ny < 0 || ny >= height)
{
count++; // Count outside cells as walls
}
else if (map[nx, ny] == 1)
{
count++;
}
}
}
// Don't count the cell itself
if (map[x, y] == 1)
count--;
return count;
}
// Connect disconnected cave regions
public int[,] ConnectRegions(int[,] map)
{
// Find all separate regions
List<List<(int, int)>> regions = FindRegions(map);
// If there's only one region, we're done
if (regions.Count <= 1)
return map;
// Sort regions by size (largest first)
regions.Sort((a, b) => b.Count.CompareTo(a.Count));
// Keep the largest region, connect others to it
List<(int, int)> mainRegion = regions[0];
for (int i = 1; i < regions.Count; i++)
{
// Find the closest points between the main region and this region
(int mainX, int mainY, int regionX, int regionY) = FindClosestPoints(mainRegion, regions[i]);
// Create a corridor between these points
map = CreateCorridor(map, mainX, mainY, regionX, regionY);
// Add this region to the main region
mainRegion.AddRange(regions[i]);
}
return map;
}
private List<List<(int, int)>> FindRegions(int[,] map)
{
bool[,] visited = new bool[width, height];
List<List<(int, int)>> regions = new List<List<(int, int)>>();
for (int x = 0; x < width; x++)
{
for (int y = 0; y < height; y++)
{
if (map[x, y] == 0 && !visited[x, y])
{
// Found a new region
List<(int, int)> region = new List<(int, int)>();
FloodFill(map, visited, x, y, region);
regions.Add(region);
}
}
}
return regions;
}
private void FloodFill(int[,] map, bool[,] visited, int x, int y, List<(int, int)> region)
{
// Check if this cell is valid and unvisited
if (x < 0 || x >= width || y < 0 || y >= height || visited[x, y] || map[x, y] == 1)
return;
// Mark as visited and add to region
visited[x, y] = true;
region.Add((x, y));
// Recursively check neighbors
FloodFill(map, visited, x + 1, y, region);
FloodFill(map, visited, x - 1, y, region);
FloodFill(map, visited, x, y + 1, region);
FloodFill(map, visited, x, y - 1, region);
}
private (int, int, int, int) FindClosestPoints(List<(int, int)> regionA, List<(int, int)> regionB)
{
int closestDistance = int.MaxValue;
int bestAX = 0, bestAY = 0, bestBX = 0, bestBY = 0;
foreach (var (ax, ay) in regionA)
{
foreach (var (bx, by) in regionB)
{
int distance = Math.Abs(ax - bx) + Math.Abs(ay - by);
if (distance < closestDistance)
{
closestDistance = distance;
bestAX = ax;
bestAY = ay;
bestBX = bx;
bestBY = by;
}
}
}
return (bestAX, bestAY, bestBX, bestBY);
}
private int[,] CreateCorridor(int[,] map, int x1, int y1, int x2, int y2)
{
// Create a simple L-shaped corridor
int[,] newMap = (int[,])map.Clone();
// Horizontal part
for (int x = Math.Min(x1, x2); x <= Math.Max(x1, x2); x++)
{
newMap[x, y1] = 0; // 0 = floor
}
// Vertical part
for (int y = Math.Min(y1, y2); y <= Math.Max(y1, y2); y++)
{
newMap[x2, y] = 0; // 0 = floor
}
return newMap;
}
}
Procedural Item Generation
Procedural item generation creates weapons, armor, and other items with varying properties.
Item Generator
public class ItemGenerator
{
private Random random;
// Item properties
private string[] weaponTypes = { "Sword", "Axe", "Mace", "Dagger", "Bow", "Staff", "Wand" };
private string[] armorTypes = { "Helmet", "Chestplate", "Gauntlets", "Boots", "Shield" };
private string[] rarities = { "Common", "Uncommon", "Rare", "Epic", "Legendary" };
private string[] prefixes = { "Rusty", "Sharp", "Mighty", "Brutal", "Ancient", "Blessed", "Cursed", "Enchanted" };
private string[] suffixes = { "of Power", "of Giants", "of Destruction", "of Speed", "of Protection", "of the Whale", "of the Eagle" };
// Stat ranges for each rarity
private Dictionary<string, (int min, int max)> damageRanges = new Dictionary<string, (int min, int max)>
{
{ "Common", (1, 5) },
{ "Uncommon", (5, 10) },
{ "Rare", (10, 20) },
{ "Epic", (20, 35) },
{ "Legendary", (35, 50) }
};
private Dictionary<string, (int min, int max)> armorRanges = new Dictionary<string, (int min, int max)>
{
{ "Common", (1, 3) },
{ "Uncommon", (3, 6) },
{ "Rare", (6, 10) },
{ "Epic", (10, 15) },
{ "Legendary", (15, 25) }
};
public ItemGenerator(int seed)
{
random = new Random(seed);
}
public Item GenerateWeapon(int playerLevel)
{
string rarity = GetRandomRarity();
string type = weaponTypes[random.Next(weaponTypes.Length)];
// Determine if the item has a prefix and/or suffix
bool hasPrefix = random.NextDouble() < 0.3 + GetRarityValue(rarity) * 0.1;
bool hasSuffix = random.NextDouble() < 0.3 + GetRarityValue(rarity) * 0.1;
string prefix = hasPrefix ? prefixes[random.Next(prefixes.Length)] : "";
string suffix = hasSuffix ? suffixes[random.Next(suffixes.Length)] : "";
// Generate the item name
string name = "";
if (!string.IsNullOrEmpty(prefix))
name += prefix + " ";
name += type;
if (!string.IsNullOrEmpty(suffix))
name += " " + suffix;
// Generate stats based on rarity and player level
int damage = random.Next(damageRanges[rarity].min, damageRanges[rarity].max) + playerLevel;
// Add random bonus stats based on rarity
Dictionary<string, int> bonusStats = new Dictionary<string, int>();
int numBonusStats = random.Next(GetRarityValue(rarity) + 1);
for (int i = 0; i < numBonusStats; i++)
{
string statType = GetRandomStatType();
int statValue = random.Next(1, 5) + GetRarityValue(rarity);
if (bonusStats.ContainsKey(statType))
bonusStats[statType] += statValue;
else
bonusStats[statType] = statValue;
}
return new Item
{
Name = name,
Type = "Weapon",
Subtype = type,
Rarity = rarity,
Damage = damage,
BonusStats = bonusStats
};
}
public Item GenerateArmor(int playerLevel)
{
string rarity = GetRandomRarity();
string type = armorTypes[random.Next(armorTypes.Length)];
// Determine if the item has a prefix and/or suffix
bool hasPrefix = random.NextDouble() < 0.3 + GetRarityValue(rarity) * 0.1;
bool hasSuffix = random.NextDouble() < 0.3 + GetRarityValue(rarity) * 0.1;
string prefix = hasPrefix ? prefixes[random.Next(prefixes.Length)] : "";
string suffix = hasSuffix ? suffixes[random.Next(suffixes.Length)] : "";
// Generate the item name
string name = "";
if (!string.IsNullOrEmpty(prefix))
name += prefix + " ";
name += type;
if (!string.IsNullOrEmpty(suffix))
name += " " + suffix;
// Generate stats based on rarity and player level
int armor = random.Next(armorRanges[rarity].min, armorRanges[rarity].max) + playerLevel / 2;
// Add random bonus stats based on rarity
Dictionary<string, int> bonusStats = new Dictionary<string, int>();
int numBonusStats = random.Next(GetRarityValue(rarity) + 1);
for (int i = 0; i < numBonusStats; i++)
{
string statType = GetRandomStatType();
int statValue = random.Next(1, 5) + GetRarityValue(rarity);
if (bonusStats.ContainsKey(statType))
bonusStats[statType] += statValue;
else
bonusStats[statType] = statValue;
}
return new Item
{
Name = name,
Type = "Armor",
Subtype = type,
Rarity = rarity,
Armor = armor,
BonusStats = bonusStats
};
}
private string GetRandomRarity()
{
float roll = (float)random.NextDouble();
if (roll < 0.6f)
return "Common";
else if (roll < 0.85f)
return "Uncommon";
else if (roll < 0.95f)
return "Rare";
else if (roll < 0.99f)
return "Epic";
else
return "Legendary";
}
private int GetRarityValue(string rarity)
{
switch (rarity)
{
case "Common": return 0;
case "Uncommon": return 1;
case "Rare": return 2;
case "Epic": return 3;
case "Legendary": return 4;
default: return 0;
}
}
private string GetRandomStatType()
{
string[] statTypes = { "Strength", "Dexterity", "Intelligence", "Vitality", "CritChance", "CritDamage", "AttackSpeed" };
return statTypes[random.Next(statTypes.Length)];
}
}
public class Item
{
public string Name { get; set; }
public string Type { get; set; } // Weapon, Armor, Consumable, etc.
public string Subtype { get; set; } // Sword, Axe, Helmet, etc.
public string Rarity { get; set; }
public int Damage { get; set; } // For weapons
public int Armor { get; set; } // For armor
public Dictionary<string, int> BonusStats { get; set; } = new Dictionary<string, int>();
public override string ToString()
{
string result = $"{Name} ({Rarity} {Subtype})\n";
if (Damage > 0)
result += $"Damage: {Damage}\n";
if (Armor > 0)
result += $"Armor: {Armor}\n";
if (BonusStats.Count > 0)
{
result += "Bonus Stats:\n";
foreach (var stat in BonusStats)
{
result += $" +{stat.Value} {stat.Key}\n";
}
}
return result;
}
}
Conclusion
Procedural generation is a powerful technique for creating diverse and engaging game content. By understanding and implementing these algorithms, you can create games with virtually unlimited content, increasing replayability and player engagement.
The implementations provided in this section are simplified for clarity but demonstrate the core concepts of procedural generation. In practice, these algorithms can be combined and extended to create more complex and interesting game worlds.
When implementing procedural generation in your games, remember to:
- Use Seeded Random Generation: Ensure reproducibility and allow sharing of interesting generated content.
- Balance Randomness and Control: Too much randomness can lead to chaotic, unplayable content, while too much control limits variety.
- Layer Multiple Techniques: Combine different algorithms for more complex and interesting results.
- Validate Generated Content: Ensure that procedurally generated content meets gameplay requirements.
- Consider Performance: Optimize algorithms for real-time generation when needed.