Skip to content

Instantly share code, notes, and snippets.

@poemdexter

poemdexter/dungeon.cs

Created October 16, 2015 05:29
Show Gist options
  • Save poemdexter/53f608ae7d1be30ca620 to your computer and use it in GitHub Desktop.
Save poemdexter/53f608ae7d1be30ca620 to your computer and use it in GitHub Desktop.
Download ZIP
yet another dungeon generator
Raw
dungeon.cs
using System;
using System.Collections.Generic;
// from https://github.com/adonaac/blog/issues/1
public class DungeonGenerator
{
/** GRID OF CELLS **/
private Cell[,] grid;
private int gridWidth, gridHeight; // of grid
private const int UNASSIGNED = 0, EASY = 1, MED = 2, HARD = 3; // difficulty
private int easyCells, mediumCells, hardCells; // sum of all rooms must equal gridwidth x gridheight
/** DUNGEON ROOMS **/
private List<Room> rooms;
private int defaultChance, wideChance, tallChance, squareChance; // sum of all room chances must be 100
private const int DEFAULT = 1; // room type 1 x 1
private const int WIDE = 2; // room type 2 x 1
private const int TALL = 3; // room type 1 x 2
private const int SQUARE = 4; // room type 2 x 2
private float connectedness;
private Cell startCell, finishCell;
private static System.Random random = new System.Random();
public DungeonGenerator(int gridWidth, int gridHeight, int easyCells, int mediumCells, int hardCells, int defaultChance, int wideChance, int tallChance, int squareChance, float connectedness)
{
this.gridWidth = gridWidth;
this.gridHeight = gridHeight;
this.easyCells = easyCells;
this.mediumCells = mediumCells;
this.hardCells = hardCells;
this.defaultChance = defaultChance;
this.wideChance = wideChance;
this.tallChance = tallChance;
this.squareChance = squareChance;
this.connectedness = connectedness;
// create new grid and populate with Cells
grid = new Cell[gridWidth, gridHeight];
for (int x = 0; x < gridWidth; x++)
{
for (int y = 0; y < gridHeight; y++)
{
grid[x, y] = new Cell(x, y);
}
}
}
public void Generate()
{
// dungeon generation steps
AssignDifficulty();
CreatePath();
CreateRooms();
ConnectRooms();
}
public Cell[,] GetGrid()
{
return grid;
}
public List<Room> GetRooms()
{
return rooms;
}
public Cell GetStartingCell()
{
return startCell;
}
public Cell GetFinishCell()
{
return finishCell;
}
public void ConnectRooms()
{
// -- connection positions based on room type --
// DEFAULT 0 WIDE 0 1 TALL 0 SQUARE 0 1
// 3 o 1 5 o x 2 5 x 1 7 x x 2
// 2 4 3 4 o 2 6 o x 3
// 3 5 4
// create all possible connections between rooms
foreach (Room room in rooms)
{
int x = room.X;
int y = room.Y;
switch (room.Type)
{
case DEFAULT:
if (y + 1 < gridHeight && grid[x , y + 1].IsRoom()) room.Connections[0] = grid[x , y + 1]; // 0
if (x + 1 < gridWidth && grid[x + 1, y ].IsRoom()) room.Connections[1] = grid[x + 1, y ]; // 1
if (y - 1 >= 0 && grid[x , y - 1].IsRoom()) room.Connections[2] = grid[x , y - 1]; // 2
if (x - 1 >= 0 && grid[x - 1, y ].IsRoom()) room.Connections[3] = grid[x - 1, y ]; // 3
break;
case WIDE:
if (y + 1 < gridHeight && grid[x , y + 1].IsRoom()) room.Connections[0] = grid[x , y + 1]; // 0
if (x + 1 < gridWidth && y + 1 < gridHeight && grid[x + 1, y + 1].IsRoom()) room.Connections[1] = grid[x + 1, y + 1]; // 1
if (x + 2 < gridWidth && grid[x + 2, y ].IsRoom()) room.Connections[2] = grid[x + 2, y ]; // 2
if (x + 1 < gridWidth && y - 1 >= 0 && grid[x + 1, y - 1].IsRoom()) room.Connections[3] = grid[x + 1, y - 1]; // 3
if (y - 1 >= 0 && grid[x , y - 1].IsRoom()) room.Connections[4] = grid[x , y - 1]; // 4
if (x - 1 >= 0 && grid[x - 1, y ].IsRoom()) room.Connections[5] = grid[x - 1, y ]; // 5
break;
case TALL:
if (y + 2 < gridHeight && grid[x , y + 2].IsRoom()) room.Connections[0] = grid[x , y + 2]; // 0
if (x + 1 < gridWidth && y + 1 < gridHeight && grid[x + 1, y + 1].IsRoom()) room.Connections[1] = grid[x + 1, y + 1]; // 1
if (x + 1 < gridWidth && grid[x + 1, y ].IsRoom()) room.Connections[2] = grid[x + 1, y ]; // 2
if (y - 1 >= 0 && grid[x , y - 1].IsRoom()) room.Connections[3] = grid[x , y - 1]; // 3
if (x - 1 >= 0 && grid[x - 1, y ].IsRoom()) room.Connections[4] = grid[x - 1, y ]; // 4
if (x - 1 >= 0 && y + 1 < gridHeight && grid[x - 1, y + 1].IsRoom()) room.Connections[5] = grid[x - 1, y + 1]; // 5
break;
case SQUARE:
if (y + 2 < gridHeight && grid[x , y + 2].IsRoom()) room.Connections[0] = grid[x , y + 2]; // 0
if (x + 1 < gridWidth && y + 2 < gridHeight && grid[x + 1, y + 2].IsRoom()) room.Connections[1] = grid[x + 1, y + 2]; // 1
if (x + 2 < gridWidth && y + 1 < gridHeight && grid[x + 2, y + 1].IsRoom()) room.Connections[2] = grid[x + 2, y + 1]; // 2
if (x + 2 < gridWidth && grid[x + 2, y ].IsRoom()) room.Connections[3] = grid[x + 2, y ]; // 3
if (x + 1 < gridWidth && y - 1 >= 0 && grid[x + 1, y - 1].IsRoom()) room.Connections[4] = grid[x + 1, y - 1]; // 4
if (y - 1 >= 0 && grid[x , y - 1].IsRoom()) room.Connections[5] = grid[x , y - 1]; // 5
if (x - 1 >= 0 && grid[x - 1, y ].IsRoom()) room.Connections[6] = grid[x - 1, y ]; // 6
if (x - 1 >= 0 && y + 1 < gridHeight && grid[x - 1, y + 1].IsRoom()) room.Connections[7] = grid[x - 1, y + 1]; // 7
break;
}
}
// randomly remove connections until a certain number of connections per room is met
int connectionsCount = GetTotalRoomConnections();
int connectionsNeeded = (int)Math.Ceiling(connectionsCount * connectedness);
int connectionsToRemove = connectionsCount - connectionsNeeded;
for (int i = 1; i <= connectionsToRemove; i++)
{
int r;
do
{
r = random.Next(rooms.Count);
}
while (!rooms[r].CanRemoveConnection());
RemoveRandomConnection(rooms[r]);
}
ValidateDungeonConnections();
}
private void RemoveRandomConnection(Room room)
{
int r;
do
{
r = random.Next(room.Connections.Length);
}
while (room.Connections[r] == null);
Cell connectingCell = room.Connections[r];
Cell roomCell = GetCellByRoomConnectionsPosition(room, r);
room.Connections[r] = null;
int p = rooms[connectingCell.RoomId].GetConnectionPositionByCell(roomCell);
rooms[connectingCell.RoomId].Connections[p] = null;
}
private Cell GetCellByRoomConnectionsPosition(Room room, int position)
{
// -- connection positions based on room type --
// DEFAULT 0 WIDE 0 1 TALL 0 SQUARE 0 1
// 3 o 1 5 o x 2 5 x 1 7 x x 2
// 2 4 3 4 o 2 6 o x 3
// 3 5 4
switch (room.Type)
{
case DEFAULT:
return grid[room.X, room.Y];
case WIDE:
if (position == 0 || position == 4 || position == 5) return grid[room.X, room.Y];
else return grid[room.X + 1, room.Y];
case TALL:
if (position == 2 || position == 3 || position == 4) return grid[room.X, room.Y];
else return grid[room.X, room.Y + 1];
case SQUARE:
if (position == 5 || position == 6) return grid[room.X, room.Y];
else if (position == 0 || position == 7) return grid[room.X, room.Y + 1];
else if (position == 1 || position == 2) return grid[room.X + 1, room.Y + 1];
else return grid[room.X + 1, room.Y];
}
return null;
}
private void ValidateDungeonConnections()
{
// flood fill to ensure we have a connection from start to finish
List<int> floodedRooms = DoFloodFillOfRooms();
// if flooded rooms count not equal total rooms count, start adding single connections and rechecking
while (floodedRooms.Count != rooms.Count)
{
// find earliest room not flooded
for (int i = 0; i < rooms.Count; i++)
{
if (!floodedRooms.Contains(i))
{
// check room's adjacent cells to see if we can be connected to a flooded room
// -- connection positions based on room type --
// DEFAULT 0 WIDE 0 1 TALL 0 SQUARE 0 1
// 3 o 1 5 o x 2 5 x 1 7 x x 2
// 2 4 3 4 o 2 6 o x 3
// 3 5 4
Room room = rooms[i];
int x = room.X;
int y = room.Y;
switch (room.Type)
{
case DEFAULT:
if ( y + 1 < gridHeight && floodedRooms.Contains(grid[x , y + 1].RoomId)) ConnectTwoRooms(room, grid[x ,y ], 0, "N", grid[x , y + 1]); // 0
else if (x + 1 < gridWidth && floodedRooms.Contains(grid[x + 1, y ].RoomId)) ConnectTwoRooms(room, grid[x ,y ], 1, "E", grid[x + 1, y ]); // 1
else if ( y - 1 >= 0 && floodedRooms.Contains(grid[x , y - 1].RoomId)) ConnectTwoRooms(room, grid[x ,y ], 2, "S", grid[x , y - 1]); // 2
else if (x - 1 >= 0 && floodedRooms.Contains(grid[x - 1, y ].RoomId)) ConnectTwoRooms(room, grid[x ,y ], 3, "W", grid[x - 1, y ]); // 3
break;
case WIDE:
if ( y + 1 < gridHeight && floodedRooms.Contains(grid[x , y + 1].RoomId)) ConnectTwoRooms(room, grid[x ,y ], 0, "N", grid[x , y + 1]); // 0
else if (x + 1 < gridWidth && y + 1 < gridHeight && floodedRooms.Contains(grid[x + 1, y + 1].RoomId)) ConnectTwoRooms(room, grid[x + 1,y ], 1, "N", grid[x + 1, y + 1]); // 1
else if (x + 2 < gridWidth && floodedRooms.Contains(grid[x + 2, y ].RoomId)) ConnectTwoRooms(room, grid[x + 1,y ], 2, "E", grid[x + 2, y ]); // 2
else if (x + 1 < gridWidth && y - 1 >= 0 && floodedRooms.Contains(grid[x + 1, y - 1].RoomId)) ConnectTwoRooms(room, grid[x + 1,y ], 3, "S", grid[x + 1, y - 1]); // 3
else if ( y - 1 >= 0 && floodedRooms.Contains(grid[x , y - 1].RoomId)) ConnectTwoRooms(room, grid[x ,y ], 4, "S", grid[x , y - 1]); // 4
else if (x - 1 >= 0 && floodedRooms.Contains(grid[x - 1, y ].RoomId)) ConnectTwoRooms(room, grid[x ,y ], 5, "W", grid[x - 1, y ]); // 5
break;
case TALL:
if ( y + 2 < gridHeight && floodedRooms.Contains(grid[x , y + 2].RoomId)) ConnectTwoRooms(room, grid[x ,y + 1], 0, "N", grid[x , y + 2]); // 0
else if (x + 1 < gridWidth && y + 1 < gridHeight && floodedRooms.Contains(grid[x + 1, y + 1].RoomId)) ConnectTwoRooms(room, grid[x ,y + 1], 1, "E", grid[x + 1, y + 1]); // 1
else if (x + 1 < gridWidth && floodedRooms.Contains(grid[x + 1, y ].RoomId)) ConnectTwoRooms(room, grid[x ,y ], 2, "E", grid[x + 1, y ]); // 2
else if ( y - 1 >= 0 && floodedRooms.Contains(grid[x , y - 1].RoomId)) ConnectTwoRooms(room, grid[x ,y ], 3, "S", grid[x , y - 1]); // 3
else if (x - 1 >= 0 && floodedRooms.Contains(grid[x - 1, y ].RoomId)) ConnectTwoRooms(room, grid[x ,y ], 4, "W", grid[x - 1, y ]); // 4
else if (x - 1 >= 0 && y + 1 < gridHeight && floodedRooms.Contains(grid[x - 1, y + 1].RoomId)) ConnectTwoRooms(room, grid[x ,y + 1], 5, "W", grid[x - 1, y + 1]); // 5
break;
case SQUARE:
if ( y + 2 < gridHeight && floodedRooms.Contains(grid[x , y + 2].RoomId)) ConnectTwoRooms(room, grid[x ,y + 1], 0, "N", grid[x , y + 2]); // 0
else if (x + 1 < gridWidth && y + 2 < gridHeight && floodedRooms.Contains(grid[x + 1, y + 2].RoomId)) ConnectTwoRooms(room, grid[x + 1,y + 1], 1, "N", grid[x + 1, y + 2]); // 1
else if (x + 2 < gridWidth && y + 1 < gridHeight && floodedRooms.Contains(grid[x + 2, y + 1].RoomId)) ConnectTwoRooms(room, grid[x + 1,y + 1], 2, "E", grid[x + 2, y + 1]); // 2
else if (x + 2 < gridWidth && floodedRooms.Contains(grid[x + 2, y ].RoomId)) ConnectTwoRooms(room, grid[x + 1,y ], 3, "E", grid[x + 2, y ]); // 3
else if (x + 1 < gridWidth && y - 1 >= 0 && floodedRooms.Contains(grid[x + 1, y - 1].RoomId)) ConnectTwoRooms(room, grid[x + 1,y ], 4, "S", grid[x + 1, y - 1]); // 4
else if ( y - 1 >= 0 && floodedRooms.Contains(grid[x , y - 1].RoomId)) ConnectTwoRooms(room, grid[x ,y ], 5, "S", grid[x , y - 1]); // 5
else if (x - 1 >= 0 && floodedRooms.Contains(grid[x - 1, y ].RoomId)) ConnectTwoRooms(room, grid[x ,y ], 6, "W", grid[x - 1, y ]); // 6
else if (x - 1 >= 0 && y + 1 < gridHeight && floodedRooms.Contains(grid[x - 1, y + 1].RoomId)) ConnectTwoRooms(room, grid[x ,y + 1], 7, "W", grid[x - 1, y + 1]); // 7
break;
}
}
}
// recheck flood fill
floodedRooms = DoFloodFillOfRooms();
}
}
private void ConnectTwoRooms(Room currentRoom, Cell currentRoomCell, int connectionPosition, String connectionDirection, Cell connectingFloodCell)
{
// set cell connection for current room
currentRoom.Connections[connectionPosition] = connectingFloodCell;
// get room for connectingFloodCell
Room room = rooms[connectingFloodCell.RoomId];
// get room's connection position (polar opposite of connectionDirection)
// -- connection positions based on room type --
// DEFAULT 0s WIDE 0s 1s TALL 0s SQUARE 0s 1s
// 3e oo 1w 5e oo xx 2w 5e xx 1w 7e xx xx 2w
// 2n 4n 3n 4e oo 2w 6e oo xx 3w
// 3n 5n 4n
switch (room.Type)
{
case DEFAULT:
if ("S".Equals(connectionDirection)) room.Connections[0] = currentRoomCell;
if ("W".Equals(connectionDirection)) room.Connections[1] = currentRoomCell;
if ("N".Equals(connectionDirection)) room.Connections[2] = currentRoomCell;
if ("E".Equals(connectionDirection)) room.Connections[3] = currentRoomCell;
break;
case WIDE:
if ("S".Equals(connectionDirection))
{
if (room.X == connectingFloodCell.X) room.Connections[0] = currentRoomCell; // aligns with origin (o)
else room.Connections[1] = currentRoomCell;
}
if ("W".Equals(connectionDirection)) room.Connections[2] = currentRoomCell;
if ("N".Equals(connectionDirection))
{
if (room.X == connectingFloodCell.X) room.Connections[4] = currentRoomCell; // aligns with origin (o)
else room.Connections[3] = currentRoomCell;
}
if ("E".Equals(connectionDirection)) room.Connections[5] = currentRoomCell;
break;
case TALL:
if ("S".Equals(connectionDirection)) room.Connections[0] = currentRoomCell;
if ("W".Equals(connectionDirection))
{
if (room.Y == connectingFloodCell.Y) room.Connections[2] = currentRoomCell; // aligns with origin (o)
else room.Connections[1] = currentRoomCell;
}
if ("N".Equals(connectionDirection)) room.Connections[3] = currentRoomCell;
if ("E".Equals(connectionDirection))
{
if (room.Y == connectingFloodCell.Y) room.Connections[4] = currentRoomCell; // aligns with origin (o)
else room.Connections[5] = currentRoomCell;
}
break;
case SQUARE:
if ("S".Equals(connectionDirection))
{
if (room.X == connectingFloodCell.X) room.Connections[0] = currentRoomCell; // aligns with origin (o)
else room.Connections[1] = currentRoomCell;
}
if ("W".Equals(connectionDirection))
{
if (room.Y == connectingFloodCell.Y) room.Connections[3] = currentRoomCell; // aligns with origin (o)
else room.Connections[2] = currentRoomCell;
}
if ("N".Equals(connectionDirection))
{
if (room.X == connectingFloodCell.X) room.Connections[5] = currentRoomCell; // aligns with origin (o)
else room.Connections[4] = currentRoomCell;
}
if ("E".Equals(connectionDirection))
{
if (room.Y == connectingFloodCell.Y) room.Connections[6] = currentRoomCell; // aligns with origin (o)
else room.Connections[7] = currentRoomCell;
}
break;
}
}
private List<int> DoFloodFillOfRooms()
{
List<int> floodedRooms = new List<int>();
Queue<Room> roomQueue = new Queue<Room>();
Room startRoom = rooms[0];
roomQueue.Enqueue(startRoom);
while (roomQueue.Count > 0)
{
Room room = roomQueue.Dequeue();
floodedRooms.Add(room.Id);
// queue up each new room we're connected to
foreach (Cell cell in room.Connections)
{
if (cell != null && !floodedRooms.Contains(cell.RoomId) && !roomQueue.Contains(rooms[cell.RoomId]))
{
roomQueue.Enqueue(rooms[cell.RoomId]);
}
}
}
return floodedRooms;
}
private int GetTotalRoomConnections()
{
int total = 0;
foreach (Room room in rooms)
{
foreach (Cell cell in room.Connections)
{
total += (cell != null) ? 1 : 0;
}
}
return total / 2; // divide by 2 because connections are shared by 2 rooms
}
public void CreateRooms()
{
rooms = new List<Room>();
int roomId = 0;
for (int x = 0; x < gridWidth; x++)
{
for (int y = 0; y < gridHeight; y++)
{
Cell cell = grid[x, y];
if (cell.IsActive && !cell.IsRoom()) // part of path cells but isn't room yet
{
int type;
do
{
type = GetRandomRoomType();
}
while (!ValidateRoomType(cell, type));
CreateRoom(cell, type, roomId);
roomId++;
}
}
}
}
private void CreateRoom(Cell cell, int roomType, int roomId)
{
// mark cells used in room and add room to rooms list
// all cells used in room use origin cell's difficulty
Room room = new Room(roomId, cell.X, cell.Y, roomType);
switch (roomType)
{
case DEFAULT:
room.Connections = new Cell[4];
room.Width = 1;
room.Height = 1;
cell.RoomId = roomId;
break;
case WIDE:
room.Connections = new Cell[6];
room.Width = 2;
room.Height = 1;
cell.RoomId = roomId;
grid[cell.X + 1, cell.Y].RoomId = roomId;
grid[cell.X + 1, cell.Y].Difficulty = cell.Difficulty;
break;
case TALL:
room.Connections = new Cell[6];
room.Width = 1;
room.Height = 2;
cell.RoomId = roomId;
grid[cell.X, cell.Y + 1].RoomId = roomId;
grid[cell.X, cell.Y + 1].Difficulty = cell.Difficulty;
break;
case SQUARE:
room.Connections = new Cell[8];
room.Width = 2;
room.Height = 2;
cell.RoomId = roomId;
grid[cell.X + 1, cell.Y ].RoomId = roomId;
grid[cell.X , cell.Y + 1].RoomId = roomId;
grid[cell.X + 1, cell.Y + 1].RoomId = roomId;
grid[cell.X + 1, cell.Y ].Difficulty = cell.Difficulty;
grid[cell.X , cell.Y + 1].Difficulty = cell.Difficulty;
grid[cell.X + 1, cell.Y + 1].Difficulty = cell.Difficulty;
break;
}
rooms.Add(room);
}
private bool ValidateRoomType(Cell cell, int roomType)
{
// ensure we're not going off the grid when we use not default size rooms
switch (roomType)
{
case DEFAULT:
return true;
case WIDE:
return cell.X + 1 < gridWidth && !grid[cell.X + 1, cell.Y].IsRoom();
case TALL:
return cell.Y + 1 < gridHeight && !grid[cell.X, cell.Y + 1].IsRoom();
case SQUARE:
return cell.X + 1 < gridWidth && cell.Y + 1 < gridHeight && !grid[cell.X + 1, cell.Y].IsRoom() && !grid[cell.X, cell.Y + 1].IsRoom() && !grid[cell.X + 1, cell.Y + 1].IsRoom();
default:
return false;
}
}
private int GetRandomRoomType()
{
int c = random.Next(100);
if (c < defaultChance) return DEFAULT;
if (c < defaultChance + wideChance) return WIDE;
if (c < defaultChance + wideChance + tallChance) return TALL;
if (c < defaultChance + wideChance + tallChance + squareChance) return SQUARE;
return -1;
}
public void CreatePath()
{
// choose two cells on opposite ends of grid for start and finish point
int y1 = random.Next(gridHeight);
startCell = grid[0, y1];
int y2;
do
{
y2 = random.Next(gridHeight);
}
while (grid[gridWidth - 1, y2].Difficulty == HARD);
finishCell = grid[gridWidth - 1, y2];
startCell.IsPathed = true;
startCell.ParentX = startCell.X;
startCell.ParentY = startCell.Y;
// A* from one cell to the other
List<Cell> openList = new List<Cell>();
List<Cell> closedList = new List<Cell>();
openList.Add(startCell);
bool found = false;
while (openList.Count > 0 && !found)
{
Cell parentCell = openList[0];
openList.Remove(parentCell);
closedList.Add(parentCell);
if (parentCell.X == finishCell.X && parentCell.Y == finishCell.Y)
{
found = true;
break;
}
// path check order ignoring cells in closed list and avoiding HARD cells
// 1
// 4 x 2
// 3
int x = parentCell.X;
int y = parentCell.Y;
if (y + 1 < gridHeight && grid[x , y + 1].Difficulty != HARD && !closedList.Contains(grid[x , y + 1])) MarkPath(grid[x , y + 1], parentCell, openList); // 1
if (x + 1 < gridWidth && grid[x + 1, y ].Difficulty != HARD && !closedList.Contains(grid[x + 1, y ])) MarkPath(grid[x + 1, y ], parentCell, openList); // 2
if (y - 1 >= 0 && grid[x , y - 1].Difficulty != HARD && !closedList.Contains(grid[x , y - 1])) MarkPath(grid[x , y - 1], parentCell, openList); // 3
if (x - 1 >= 0 && grid[x - 1, y ].Difficulty != HARD && !closedList.Contains(grid[x - 1, y ])) MarkPath(grid[x - 1, y ], parentCell, openList); // 4
}
// backtrack through closed list parents to get path
List<Cell> path = new List<Cell>();
if (found)
{
Cell currentCell = finishCell;
bool pathing = true;
while (pathing)
{
if (currentCell.ParentX == startCell.X && currentCell.ParentY == startCell.Y)
{
pathing = false;
}
path.Add(currentCell);
currentCell = grid[currentCell.ParentX, currentCell.ParentY];
}
}
foreach (Cell c in path)
{
// mark cells on path active
c.IsActive = true;
int x = c.X;
int y = c.Y;
// mark neighbors of path cells active
// check order
// 1 2 3
// 8 x 4
// 7 6 5
if (x - 1 >= 0 && y + 1 < gridHeight) grid[x - 1, y + 1].IsActive = true; // 1
if ( y + 1 < gridHeight) grid[x , y + 1].IsActive = true; // 2
if (x + 1 < gridWidth && y + 1 < gridHeight) grid[x + 1, y + 1].IsActive = true; // 3
if (x + 1 < gridWidth ) grid[x + 1, y ].IsActive = true; // 4
if (x + 1 < gridWidth && y - 1 >= 0 ) grid[x + 1, y - 1].IsActive = true; // 5
if ( y - 1 >= 0 ) grid[x , y - 1].IsActive = true; // 6
if (x - 1 >= 0 && y - 1 >= 0 ) grid[x - 1, y - 1].IsActive = true; // 7
if (x - 1 >= 0 ) grid[x - 1, y ].IsActive = true; // 8
}
}
private void MarkPath(Cell cell, Cell parentCell, List<Cell> openList)
{
if (!openList.Contains(cell)) // new path cell so set parent and add to open list
{
cell.ParentX = parentCell.X;
cell.ParentY = parentCell.Y;
cell.G = parentCell.G + 10;
cell.H = Math.Abs(cell.X - parentCell.X) + Math.Abs(cell.Y - parentCell.Y); // manhattan distance
openList.Add(cell);
}
else
{
if (cell.G > parentCell.G + 10) // see if linking to new parent is faster path
{
cell.G = parentCell.G + 10;
cell.ParentX = parentCell.X;
cell.ParentY = parentCell.Y;
}
}
}
public void AssignDifficulty()
{
while (hardCells > 0)
{
Cell cell = AssignHardCell();
if (mediumCells > 0) AssignRandomNeighborDifficulty(cell, MED); // for each hard cell, assign one neighbor medium
if (easyCells > 0) AssignRandomNeighborDifficulty(cell, EASY); // for each hard cell, assign one neighbor easy
}
// assign rest of cells randomly with remaining numbers of rooms
List<Cell> unassigned = new List<Cell>();
for (int x = 0; x < gridWidth; x++)
{
for (int y = 0; y < gridHeight; y++)
{
if (grid[x, y].Difficulty == UNASSIGNED)
{
unassigned.Add(grid[x, y]);
}
}
}
while (unassigned.Count > 0)
{
Cell cell = unassigned[random.Next(unassigned.Count)];
int d = random.Next(1, 3); // gets EASY or MED
if (d == EASY && easyCells > 0)
{
cell.Difficulty = EASY;
easyCells--;
}
else if (mediumCells > 0)
{
cell.Difficulty = MED;
mediumCells--;
}
else
{
cell.Difficulty = EASY;
easyCells--;
}
unassigned.Remove(cell);
}
}
private Cell AssignHardCell()
{
Cell cell;
do
{
cell = GetRandomEmptyCell();
}
while (IsAdjacentToRedCell(cell)); // no red cell can have a red neighbor
cell.Difficulty = HARD;
hardCells--; // decrement after assigning a cell
return cell;
}
private void AssignRandomNeighborDifficulty(Cell cell, int difficulty)
{
int x = cell.X;
int y = cell.Y;
bool[] neighbors = new bool[4]; // unassigned cell flags
// position
// 0
// 3 x 1
// 2
neighbors[0] = (y + 1 < gridHeight);
neighbors[1] = (x + 1 < gridWidth);
neighbors[2] = (y - 1 >= 0);
neighbors[3] = (x - 1 >= 0);
int i;
do
{
i = random.Next(4);
}
while (!neighbors[i]); // only want valid neighbor
switch (i)
{
case 0: // N
grid[x, y + 1].Difficulty = difficulty;
break;
case 1: // E
grid[x + 1, y].Difficulty = difficulty;
break;
case 2: // S
grid[x, y - 1].Difficulty = difficulty;
break;
case 3: // W
grid[x - 1, y].Difficulty = difficulty;
break;
}
if (difficulty == MED) mediumCells--; // decrement after assigning a cell
if (difficulty == EASY) easyCells--; // decrement after assigning a cell
}
private Cell GetRandomEmptyCell()
{
int x, y;
do
{
x = random.Next(gridWidth);
y = random.Next(gridHeight);
}
while (grid[x, y].Difficulty != UNASSIGNED);
return grid[x, y];
}
private bool IsAdjacentToRedCell(Cell cell)
{
int x = cell.X;
int y = cell.Y;
// check order
// 1
// 4 x 2
// 3
if (y + 1 < gridHeight && grid[x, y + 1].Difficulty == HARD) return true; // 1
if (x + 1 < gridWidth && grid[x + 1, y].Difficulty == HARD) return true; // 2
if (y - 1 >= 0 && grid[x, y - 1].Difficulty == HARD) return true; // 3
if (x - 1 >= 0 && grid[x - 1, y].Difficulty == HARD) return true; // 4
return false;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment