CSharp Example of a Dungeon-Building Algorithm
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
namespace DungeonGenerator.Java
{
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
public class Dungeon
{
// misc. messages to print
const string MsgXSize = "X size of dungeon: \t";
const string MsgYSize = "Y size of dungeon: \t";
const string MsgMaxObjects = "max # of objects: \t";
const string MsgNumObjects = "# of objects made: \t";
// max size of the map
int xmax = 80; //columns
int ymax = 25; //rows
// size of the map
int _xsize;
int _ysize;
// number of "objects" to generate on the map
int _objects;
// define the %chance to generate either a room or a corridor on the map
// BTW, rooms are 1st priority so actually it's enough to just define the chance
// of generating a room
const int ChanceRoom = 75;
// our map
Tile[] _dungeonMap = { };
readonly IRandomize _rnd;
readonly Action<string> _logger;
public Dungeon(IRandomize rnd, Action<string> logger)
{
_rnd = rnd;
_logger = logger;
}
public int Corridors
{
get;
private set;
}
public static bool IsWall(int x, int y, int xlen, int ylen, int xt, int yt, Direction d)
{
Func<int, int, int> a = GetFeatureLowerBound;
Func<int, int, int> b = IsFeatureWallBound;
switch (d)
{
case Direction.North:
return xt == a(x, xlen) || xt == b(x, xlen) || yt == y || yt == y - ylen + 1;
case Direction.East:
return xt == x || xt == x + xlen - 1 || yt == a(y, ylen) || yt == b(y, ylen);
case Direction.South:
return xt == a(x, xlen) || xt == b(x, xlen) || yt == y || yt == y + ylen - 1;
case Direction.West:
return xt == x || xt == x - xlen + 1 || yt == a(y, ylen) || yt == b(y, ylen);
}
throw new InvalidOperationException();
}
public static int GetFeatureLowerBound(int c, int len)
{
return c - len / 2;
}
public static int IsFeatureWallBound(int c, int len)
{
return c + (len - 1) / 2;
}
public static int GetFeatureUpperBound(int c, int len)
{
return c + (len + 1) / 2;
}
public static IEnumerable<PointI> GetRoomPoints(int x, int y, int xlen, int ylen, Direction d)
{
// north and south share the same x strategy
// east and west share the same y strategy
Func<int, int, int> a = GetFeatureLowerBound;
Func<int, int, int> b = GetFeatureUpperBound;
switch (d)
{
case Direction.North:
for (var xt = a(x, xlen); xt < b(x, xlen); xt++) for (var yt = y; yt > y - ylen; yt--) yield return new PointI { X = xt, Y = yt };
break;
case Direction.East:
for (var xt = x; xt < x + xlen; xt++) for (var yt = a(y, ylen); yt < b(y, ylen); yt++) yield return new PointI { X = xt, Y = yt };
break;
case Direction.South:
for (var xt = a(x, xlen); xt < b(x, xlen); xt++) for (var yt = y; yt < y + ylen; yt++) yield return new PointI { X = xt, Y = yt };
break;
case Direction.West:
for (var xt = x; xt > x - xlen; xt--) for (var yt = a(y, ylen); yt < b(y, ylen); yt++) yield return new PointI { X = xt, Y = yt };
break;
default:
yield break;
}
}
public Tile GetCellType(int x, int y)
{
try
{
return this._dungeonMap[x + this._xsize * y];
}
catch (IndexOutOfRangeException)
{
new { x, y }.Dump("exceptional");
throw;
}
}
public int GetRand(int min, int max)
{
return _rnd.Next(min, max);
}
public bool MakeCorridor(int x, int y, int length, Direction direction)
{
// define the dimensions of the corridor (er.. only the width and height..)
int len = this.GetRand(2, length);
const Tile Floor = Tile.Corridor;
int xtemp;
int ytemp = 0;
switch (direction)
{
case Direction.North:
// north
// check if there's enough space for the corridor
// start with checking it's not out of the boundaries
if (x < 0 || x > this._xsize) return false;
xtemp = x;
// same thing here, to make sure it's not out of the boundaries
for (ytemp = y; ytemp > (y - len); ytemp--)
{
if (ytemp < 0 || ytemp > this._ysize) return false; // oh boho, it was!
if (GetCellType(xtemp, ytemp) != Tile.Unused) return false;
}
// if we're still here, let's start building
Corridors++;
for (ytemp = y; ytemp > (y - len); ytemp--)
{
this.SetCell(xtemp, ytemp, Floor);
}
break;
case Direction.East:
// east
if (y < 0 || y > this._ysize) return false;
ytemp = y;
for (xtemp = x; xtemp < (x + len); xtemp++)
{
if (xtemp < 0 || xtemp > this._xsize) return false;
if (GetCellType(xtemp, ytemp) != Tile.Unused) return false;
}
Corridors++;
for (xtemp = x; xtemp < (x + len); xtemp++)
{
this.SetCell(xtemp, ytemp, Floor);
}
break;
case Direction.South:
// south
if (x < 0 || x > this._xsize) return false;
xtemp = x;
for (ytemp = y; ytemp < (y + len); ytemp++)
{
if (ytemp < 0 || ytemp > this._ysize) return false;
if (GetCellType(xtemp, ytemp) != Tile.Unused) return false;
}
Corridors++;
for (ytemp = y; ytemp < (y + len); ytemp++)
{
this.SetCell(xtemp, ytemp, Floor);
}
break;
case Direction.West:
// west
if (ytemp < 0 || ytemp > this._ysize) return false;
ytemp = y;
for (xtemp = x; xtemp > (x - len); xtemp--)
{
if (xtemp < 0 || xtemp > this._xsize) return false;
if (GetCellType(xtemp, ytemp) != Tile.Unused) return false;
}
Corridors++;
for (xtemp = x; xtemp > (x - len); xtemp--)
{
this.SetCell(xtemp, ytemp, Floor);
}
break;
}
// woot, we're still here! let's tell the other guys we're done!!
return true;
}
public IEnumerable<Tuple<PointI, Direction>> GetSurroundingPoints(PointI v)
{
var points = new[]
{
Tuple.Create(new PointI { X = v.X, Y = v.Y + 1 }, Direction.North),
Tuple.Create(new PointI { X = v.X - 1, Y = v.Y }, Direction.East),
Tuple.Create(new PointI { X = v.X , Y = v.Y-1 }, Direction.South),
Tuple.Create(new PointI { X = v.X +1, Y = v.Y }, Direction.West),
};
return points.Where(p => InBounds(p.Item1));
}
public IEnumerable<Tuple<PointI, Direction, Tile>> GetSurroundings(PointI v)
{
return
this.GetSurroundingPoints(v)
.Select(r => Tuple.Create(r.Item1, r.Item2, this.GetCellType(r.Item1.X, r.Item1.Y)));
}
public bool InBounds(int x, int y)
{
return x > 0 && x < this.xmax && y > 0 && y < this.ymax;
}
public bool InBounds(PointI v)
{
return this.InBounds(v.X, v.Y);
}
public bool MakeRoom(int x, int y, int xlength, int ylength, Direction direction)
{
// define the dimensions of the room, it should be at least 4x4 tiles (2x2 for walking on, the rest is walls)
int xlen = this.GetRand(4, xlength);
int ylen = this.GetRand(4, ylength);
// the tile type it's going to be filled with
const Tile Floor = Tile.DirtFloor;
const Tile Wall = Tile.DirtWall;
// choose the way it's pointing at
var points = GetRoomPoints(x, y, xlen, ylen, direction).ToArray();
// Check if there's enough space left for it
if (
points.Any(
s =>
s.Y < 0 || s.Y > this._ysize || s.X < 0 || s.X > this._xsize || this.GetCellType(s.X, s.Y) != Tile.Unused)) return false;
_logger(
string.Format(
"Making room:int x={0}, int y={1}, int xlength={2}, int ylength={3}, int direction={4}",
x,
y,
xlength,
ylength,
direction));
foreach (var p in points)
{
this.SetCell(p.X, p.Y, IsWall(x, y, xlen, ylen, p.X, p.Y, direction) ? Wall : Floor);
}
// yay, all done
return true;
}
public Tile[] GetDungeon()
{
return this._dungeonMap;
}
public char GetCellTile(int x, int y)
{
switch (GetCellType(x, y))
{
case Tile.Unused:
return ;
case Tile.DirtWall:
return '|';
case Tile.DirtFloor:
return '_';
case Tile.StoneWall:
return 'S';
case Tile.Corridor:
return '#';
case Tile.Door:
return 'D';
case Tile.Upstairs:
return '+';
case Tile.Downstairs:
return '-';
case Tile.Chest:
return 'C';
default:
throw new ArgumentOutOfRangeException("x,y");
}
}
//used to print the map on the screen
public void ShowDungeon()
{
for (int y = 0; y < this._ysize; y++)
{
for (int x = 0; x < this._xsize; x++)
{
Console.Write(GetCellTile(x, y));
}
if (this._xsize <= xmax) Console.WriteLine();
}
}
public Direction RandomDirection()
{
int dir = this.GetRand(0, 4);
switch (dir)
{
case 0:
return Direction.North;
case 1:
return Direction.East;
case 2:
return Direction.South;
case 3:
return Direction.West;
default:
throw new InvalidOperationException();
}
}
//and here's the one generating the whole map
public bool CreateDungeon(int inx, int iny, int inobj)
{
this._objects = inobj < 1 ? 10 : inobj;
// adjust the size of the map, if it's smaller or bigger than the limits
if (inx < 3) this._xsize = 3;
else if (inx > xmax) this._xsize = xmax;
else this._xsize = inx;
if (iny < 3) this._ysize = 3;
else if (iny > ymax) this._ysize = ymax;
else this._ysize = iny;
Console.WriteLine(MsgXSize + this._xsize);
Console.WriteLine(MsgYSize + this._ysize);
Console.WriteLine(MsgMaxObjects + this._objects);
// redefine the map var, so it's adjusted to our new map size
this._dungeonMap = new Tile[this._xsize * this._ysize];
// start with making the "standard stuff" on the map
this.Initialize();
/*******************************************************************************
And now the code of the random-map-generation-algorithm begins!
*******************************************************************************/
// start with making a room in the middle, which we can start building upon
this.MakeRoom(this._xsize / 2, this._ysize / 2, 8, 6, RandomDirection()); // getrand saken f????r att slumpa fram riktning p?? rummet
// keep count of the number of "objects" we've made
int currentFeatures = 1; // +1 for the first room we just made
// then we sart the main loop
for (int countingTries = 0; countingTries < 1000; countingTries++)
{
// check if we've reached our quota
if (currentFeatures == this._objects)
{
break;
}
// start with a random wall
int newx = 0;
int xmod = 0;
int newy = 0;
int ymod = 0;
Direction? validTile = null;
// 1000 chances to find a suitable object (room or corridor)..
for (int testing = 0; testing < 1000; testing++)
{
newx = this.GetRand(1, this._xsize - 1);
newy = this.GetRand(1, this._ysize - 1);
if (GetCellType(newx, newy) == Tile.DirtWall || GetCellType(newx, newy) == Tile.Corridor)
{
var surroundings = this.GetSurroundings(new PointI() { X = newx, Y = newy });
// check if we can reach the place
var canReach =
surroundings.FirstOrDefault(s => s.Item3 == Tile.Corridor || s.Item3 == Tile.DirtFloor);
if (canReach == null)
{
continue;
}
validTile = canReach.Item2;
switch (canReach.Item2)
{
case Direction.North:
xmod = 0;
ymod = -1;
break;
case Direction.East:
xmod = 1;
ymod = 0;
break;
case Direction.South:
xmod = 0;
ymod = 1;
break;
case Direction.West:
xmod = -1;
ymod = 0;
break;
default:
throw new InvalidOperationException();
}
// check that we haven't got another door nearby, so we won't get alot of openings besides
// each other
if (GetCellType(newx, newy + 1) == Tile.Door) // north
{
validTile = null;
}
else if (GetCellType(newx - 1, newy) == Tile.Door) // east
validTile = null;
else if (GetCellType(newx, newy - 1) == Tile.Door) // south
validTile = null;
else if (GetCellType(newx + 1, newy) == Tile.Door) // west
validTile = null;
// if we can, jump out of the loop and continue with the rest
if (validTile.HasValue) break;
}
}
if (validTile.HasValue)
{
// choose what to build now at our newly found place, and at what direction
int feature = this.GetRand(0, 100);
if (feature <= ChanceRoom)
{ // a new room
if (this.MakeRoom(newx + xmod, newy + ymod, 8, 6, validTile.Value))
{
currentFeatures++; // add to our quota
// then we mark the wall opening with a door
this.SetCell(newx, newy, Tile.Door);
// clean up infront of the door so we can reach it
this.SetCell(newx + xmod, newy + ymod, Tile.DirtFloor);
}
}
else if (feature >= ChanceRoom)
{ // new corridor
if (this.MakeCorridor(newx + xmod, newy + ymod, 6, validTile.Value))
{
// same thing here, add to the quota and a door
currentFeatures++;
this.SetCell(newx, newy, Tile.Door);
}
}
}
}
/*******************************************************************************
All done with the building, let's finish this one off
*******************************************************************************/
AddSprinkles();
// all done with the map generation, tell the user about it and finish
Console.WriteLine(MsgNumObjects + currentFeatures);
return true;
}
void Initialize()
{
for (int y = 0; y < this._ysize; y++)
{
for (int x = 0; x < this._xsize; x++)
{
// ie, making the borders of unwalkable walls
if (y == 0 || y == this._ysize - 1 || x == 0 || x == this._xsize - 1)
{
this.SetCell(x, y, Tile.StoneWall);
}
else
{ // and fill the rest with dirt
this.SetCell(x, y, Tile.Unused);
}
}
}
}
// setting a tile's type
void SetCell(int x, int y, Tile celltype)
{
this._dungeonMap[x + this._xsize * y] = celltype;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void AddSprinkles()
{
// sprinkle out the bonusstuff (stairs, chests etc.) over the map
int state = 0; // the state the loop is in, start with the stairs
while (state != 10)
{
for (int testing = 0; testing < 1000; testing++)
{
var newx = this.GetRand(1, this._xsize - 1);
int newy = this.GetRand(1, this._ysize - 2);
// Console.WriteLine("x: " + newx + "\ty: " + newy);
int ways = 4; // from how many directions we can reach the random spot from
// check if we can reach the spot
if (GetCellType(newx, newy + 1) == Tile.DirtFloor || GetCellType(newx, newy + 1) == Tile.Corridor)
{
// north
if (GetCellType(newx, newy + 1) != Tile.Door)
ways--;
}
if (GetCellType(newx - 1, newy) == Tile.DirtFloor || GetCellType(newx - 1, newy) == Tile.Corridor)
{
// east
if (GetCellType(newx - 1, newy) != Tile.Door)
ways--;
}
if (GetCellType(newx, newy - 1) == Tile.DirtFloor || GetCellType(newx, newy - 1) == Tile.Corridor)
{
// south
if (GetCellType(newx, newy - 1) != Tile.Door)
ways--;
}
if (GetCellType(newx + 1, newy) == Tile.DirtFloor || GetCellType(newx + 1, newy) == Tile.Corridor)
{
// west
if (GetCellType(newx + 1, newy) != Tile.Door)
ways--;
}
if (state == 0)
{
if (ways == 0)
{
// we're in state 0, let's place a "upstairs" thing
this.SetCell(newx, newy, Tile.Upstairs);
state = 1;
break;
}
}
else if (state == 1)
{
if (ways == 0)
{
// state 1, place a "downstairs"
this.SetCell(newx, newy, Tile.Downstairs);
state = 10;
break;
}
}
}
}
}
}
}