C# Unity Project: Procedural Cave Generation - Part 2 - Maze Upgrade

* Rename your MapGenerator.cs to MapGeneratorCave.cs. Rename the class as well to MapGeneratorCave.

* Update the OnDraw gizmo method so that you can turn it off and on from the inspector window.

* Create a file called MapGeneratorMaze.cs, we will be generating a maze instead of a cave.

- Copy the Cave code into the Maze code to start with.

- Create a method called ClearMap().

-- This method will set the map to all zeros.

- Replace method RandomFillMap() with RandomPathGenerator(int startX, int startY).

-- This method will be a recursive method.

--- If you dont know what a recursive method is, look it up.

-- Randomly pick a direction (move) from the startX and startY location. One tile up, down, left, or right.

-- Determine if this location is valid to add the path to, if so, update the map and call RandomPathGenerator with the new location.

-- Pick another direction from the startX and startY location until all 4 directions have been checked to see if a path can go in that direction.

- Update GenerateMap() method so that it calls ClearMap() and RandomPathGenerator(#, #).

- You may need other methods to help make the code human readable and easier to deal with.

- Also, the methods described are not set in stone. If you feel the methods need more arguments, please feel free to update.

- Remove the method called SmoothMap(). SmoothMap will not work with the Maze.

=========================================

MapGenerator.cs

=========================================

using UnityEngine; using System.Collections; using System.Collections.Generic; using System;

public class MapGenerator : MonoBehaviour {

public int width; public int height;

public string seed; public bool useRandomSeed;

[Range(0, 100)] public int randomFillPercent;

int[,] map;

void Start() { GenerateMap(); }

void Update() { if (Input.GetMouseButtonDown(0)) { GenerateMap(); } }

void GenerateMap() { map = new int[width, height]; RandomFillMap();

for (int i = 0; i < 5; i++) { SmoothMap(); }

ProcessMap();

int borderSize = 1; int[,] borderedMap = new int[width + borderSize * 2, height + borderSize * 2];

for (int x = 0; x < borderedMap.GetLength(0); x++) { for (int y = 0; y < borderedMap.GetLength(1); y++) { if (x >= borderSize && x < width + borderSize && y >= borderSize && y < height + borderSize) { borderedMap[x, y] = map[x - borderSize, y - borderSize]; } else { borderedMap[x, y] = 1; } } }

MeshGenerator meshGen = GetComponent(); meshGen.GenerateMesh(borderedMap, 1); }

void ProcessMap() { List> wallRegions = GetRegions(1); int wallThresholdSize = 50;

foreach (List wallRegion in wallRegions) { if (wallRegion.Count < wallThresholdSize) { foreach (Coord tile in wallRegion) { map[tile.tileX, tile.tileY] = 0; } } }

List> roomRegions = GetRegions(0); int roomThresholdSize = 50; List survivingRooms = new List();

foreach (List roomRegion in roomRegions) { if (roomRegion.Count < roomThresholdSize) { foreach (Coord tile in roomRegion) { map[tile.tileX, tile.tileY] = 1; } } else { survivingRooms.Add(new Room(roomRegion, map)); } } survivingRooms.Sort(); survivingRooms[0].isMainRoom = true; survivingRooms[0].isAccessibleFromMainRoom = true;

ConnectClosestRooms(survivingRooms); }

void ConnectClosestRooms(List allRooms, bool forceAccessibilityFromMainRoom = false) {

List roomListA = new List(); List roomListB = new List();

if (forceAccessibilityFromMainRoom) { foreach (Room room in allRooms) { if (room.isAccessibleFromMainRoom) { roomListB.Add(room); } else { roomListA.Add(room); } } } else { roomListA = allRooms; roomListB = allRooms; }

int bestDistance = 0; Coord bestTileA = new Coord(); Coord bestTileB = new Coord(); Room bestRoomA = new Room(); Room bestRoomB = new Room(); bool possibleConnectionFound = false;

foreach (Room roomA in roomListA) { if (!forceAccessibilityFromMainRoom) { possibleConnectionFound = false; if (roomA.connectedRooms.Count > 0) { continue; } }

foreach (Room roomB in roomListB) { if (roomA == roomB || roomA.IsConnected(roomB)) { continue; }

for (int tileIndexA = 0; tileIndexA < roomA.edgeTiles.Count; tileIndexA++) { for (int tileIndexB = 0; tileIndexB < roomB.edgeTiles.Count; tileIndexB++) { Coord tileA = roomA.edgeTiles[tileIndexA]; Coord tileB = roomB.edgeTiles[tileIndexB]; int distanceBetweenRooms = (int)(Mathf.Pow(tileA.tileX - tileB.tileX, 2) + Mathf.Pow(tileA.tileY - tileB.tileY, 2));

if (distanceBetweenRooms < bestDistance || !possibleConnectionFound) { bestDistance = distanceBetweenRooms; possibleConnectionFound = true; bestTileA = tileA; bestTileB = tileB; bestRoomA = roomA; bestRoomB = roomB; } } } } if (possibleConnectionFound && !forceAccessibilityFromMainRoom) { CreatePassage(bestRoomA, bestRoomB, bestTileA, bestTileB); } }

if (possibleConnectionFound && forceAccessibilityFromMainRoom) { CreatePassage(bestRoomA, bestRoomB, bestTileA, bestTileB); ConnectClosestRooms(allRooms, true); }

if (!forceAccessibilityFromMainRoom) { ConnectClosestRooms(allRooms, true); } }

void CreatePassage(Room roomA, Room roomB, Coord tileA, Coord tileB) { Room.ConnectRooms(roomA, roomB); //Debug.DrawLine (CoordToWorldPoint (tileA), CoordToWorldPoint (tileB), Color.green, 100);

List line = GetLine(tileA, tileB); foreach (Coord c in line) { DrawCircle(c, 5); } }

void DrawCircle(Coord c, int r) { for (int x = -r; x <= r; x++) { for (int y = -r; y <= r; y++) { if (x * x + y * y <= r * r) { int drawX = c.tileX + x; int drawY = c.tileY + y; if (IsInMapRange(drawX, drawY)) { map[drawX, drawY] = 0; } } } } }

List GetLine(Coord from, Coord to) { List line = new List();

int x = from.tileX; int y = from.tileY;

int dx = to.tileX - from.tileX; int dy = to.tileY - from.tileY;

bool inverted = false; int step = Math.Sign(dx); int gradientStep = Math.Sign(dy);

int longest = Mathf.Abs(dx); int shortest = Mathf.Abs(dy);

if (longest < shortest) { inverted = true; longest = Mathf.Abs(dy); shortest = Mathf.Abs(dx);

step = Math.Sign(dy); gradientStep = Math.Sign(dx); }

int gradientAccumulation = longest / 2; for (int i = 0; i < longest; i++) { line.Add(new Coord(x, y));

if (inverted) { y += step; } else { x += step; }

gradientAccumulation += shortest; if (gradientAccumulation >= longest) { if (inverted) { x += gradientStep; } else { y += gradientStep; } gradientAccumulation -= longest; } }

return line; }

Vector3 CoordToWorldPoint(Coord tile) { return new Vector3(-width / 2 + .5f + tile.tileX, 2, -height / 2 + .5f + tile.tileY); }

List> GetRegions(int tileType) { List> regions = new List>(); int[,] mapFlags = new int[width, height];

for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { if (mapFlags[x, y] == 0 && map[x, y] == tileType) { List newRegion = GetRegionTiles(x, y); regions.Add(newRegion);

foreach (Coord tile in newRegion) { mapFlags[tile.tileX, tile.tileY] = 1; } } } }

return regions; }

List GetRegionTiles(int startX, int startY) { List tiles = new List(); int[,] mapFlags = new int[width, height]; int tileType = map[startX, startY];

Queue queue = new Queue(); queue.Enqueue(new Coord(startX, startY)); mapFlags[startX, startY] = 1;

while (queue.Count > 0) { Coord tile = queue.Dequeue(); tiles.Add(tile);

for (int x = tile.tileX - 1; x <= tile.tileX + 1; x++) { for (int y = tile.tileY - 1; y <= tile.tileY + 1; y++) { if (IsInMapRange(x, y) && (y == tile.tileY || x == tile.tileX)) { if (mapFlags[x, y] == 0 && map[x, y] == tileType) { mapFlags[x, y] = 1; queue.Enqueue(new Coord(x, y)); } } } } } return tiles; }

bool IsInMapRange(int x, int y) { return x >= 0 && x < width && y >= 0 && y < height; }

void RandomFillMap() {

if (useRandomSeed) { seed = Time.time.ToString(); }

System.Random pseudoRandom = new System.Random(seed.GetHashCode());

for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { if (x == 0 || x == width - 1 || y == 0 || y == height - 1) { map[x, y] = 1; } else { map[x, y] = (pseudoRandom.Next(0, 100) < randomFillPercent) ? 1 : 0; } } } }

void SmoothMap() { for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { int neighbourWallTiles = GetSurroundingWallCount(x, y);

if (neighbourWallTiles > 4) map[x, y] = 1; else if (neighbourWallTiles < 4) map[x, y] = 0;

} } }

int GetSurroundingWallCount(int gridX, int gridY) { int wallCount = 0; for (int neighbourX = gridX - 1; neighbourX <= gridX + 1; neighbourX++) { for (int neighbourY = gridY - 1; neighbourY <= gridY + 1; neighbourY++) { if (IsInMapRange(neighbourX, neighbourY)) { if (neighbourX != gridX || neighbourY != gridY) { wallCount += map[neighbourX, neighbourY]; } } else { wallCount++; } } }

return wallCount; }

struct Coord { public int tileX; public int tileY;

public Coord(int x, int y) { tileX = x; tileY = y; } }

class Room : IComparable { public List tiles; public List edgeTiles; public List connectedRooms; public int roomSize; public bool isAccessibleFromMainRoom; public bool isMainRoom;

public Room() { }

public Room(List roomTiles, int[,] map) { tiles = roomTiles; roomSize = tiles.Count; connectedRooms = new List();

edgeTiles = new List(); foreach (Coord tile in tiles) { for (int x = tile.tileX - 1; x <= tile.tileX + 1; x++) { for (int y = tile.tileY - 1; y <= tile.tileY + 1; y++) { if (x == tile.tileX || y == tile.tileY) { if (map[x, y] == 1) { edgeTiles.Add(tile); } } } } } }

public void SetAccessibleFromMainRoom() { if (!isAccessibleFromMainRoom) { isAccessibleFromMainRoom = true; foreach (Room connectedRoom in connectedRooms) { connectedRoom.SetAccessibleFromMainRoom(); } } }

public static void ConnectRooms(Room roomA, Room roomB) { if (roomA.isAccessibleFromMainRoom) { roomB.SetAccessibleFromMainRoom(); } else if (roomB.isAccessibleFromMainRoom) { roomA.SetAccessibleFromMainRoom(); } roomA.connectedRooms.Add(roomB); roomB.connectedRooms.Add(roomA); }

public bool IsConnected(Room otherRoom) { return connectedRooms.Contains(otherRoom); }

public int CompareTo(Room otherRoom) { return otherRoom.roomSize.CompareTo(roomSize); } }

}

=========================================

MeshGenerator.cs

=========================================

using UnityEngine; using System.Collections; using System.Collections.Generic;

public class MeshGenerator : MonoBehaviour {

public SquareGrid squareGrid; public MeshFilter walls; public MeshFilter cave;

public bool is2D;

List vertices; List triangles;

Dictionary> triangleDictionary = new Dictionary>(); List> outlines = new List>(); HashSet checkedVertices = new HashSet();

public void GenerateMesh(int[,] map, float squareSize) {

triangleDictionary.Clear(); outlines.Clear(); checkedVertices.Clear();

squareGrid = new SquareGrid(map, squareSize);

vertices = new List(); triangles = new List();

for (int x = 0; x < squareGrid.squares.GetLength(0); x++) { for (int y = 0; y < squareGrid.squares.GetLength(1); y++) { TriangulateSquare(squareGrid.squares[x, y]); } }

Mesh mesh = new Mesh(); cave.mesh = mesh;

mesh.vertices = vertices.ToArray(); mesh.triangles = triangles.ToArray(); mesh.RecalculateNormals();

int tileAmount = 10; Vector2[] uvs = new Vector2[vertices.Count]; for (int i = 0; i < vertices.Count; i++) { float percentX = Mathf.InverseLerp(-map.GetLength(0) / 2 * squareSize, map.GetLength(0) / 2 * squareSize, vertices[i].x) * tileAmount; float percentY = Mathf.InverseLerp(-map.GetLength(0) / 2 * squareSize, map.GetLength(0) / 2 * squareSize, vertices[i].z) * tileAmount; uvs[i] = new Vector2(percentX, percentY); } mesh.uv = uvs;

if (is2D) { Generate2DColliders(); } else { CreateWallMesh(); } }

void CreateWallMesh() {

CalculateMeshOutlines();

List wallVertices = new List(); List wallTriangles = new List(); Mesh wallMesh = new Mesh(); float wallHeight = 5;

foreach (List outline in outlines) { for (int i = 0; i < outline.Count - 1; i++) { int startIndex = wallVertices.Count; wallVertices.Add(vertices[outline[i]]); // left wallVertices.Add(vertices[outline[i + 1]]); // right wallVertices.Add(vertices[outline[i]] - Vector3.up * wallHeight); // bottom left wallVertices.Add(vertices[outline[i + 1]] - Vector3.up * wallHeight); // bottom right

wallTriangles.Add(startIndex + 0); wallTriangles.Add(startIndex + 2); wallTriangles.Add(startIndex + 3);

wallTriangles.Add(startIndex + 3); wallTriangles.Add(startIndex + 1); wallTriangles.Add(startIndex + 0); } } wallMesh.vertices = wallVertices.ToArray(); wallMesh.triangles = wallTriangles.ToArray(); walls.mesh = wallMesh;

MeshCollider wallCollider = walls.gameObject.AddComponent(); wallCollider.sharedMesh = wallMesh; }

void Generate2DColliders() {

EdgeCollider2D[] currentColliders = gameObject.GetComponents(); for (int i = 0; i < currentColliders.Length; i++) { Destroy(currentColliders[i]); }

CalculateMeshOutlines();

foreach (List outline in outlines) { EdgeCollider2D edgeCollider = gameObject.AddComponent(); Vector2[] edgePoints = new Vector2[outline.Count];

for (int i = 0; i < outline.Count; i++) { edgePoints[i] = new Vector2(vertices[outline[i]].x, vertices[outline[i]].z); } edgeCollider.points = edgePoints; }

}

void TriangulateSquare(Square square) { switch (square.configuration) { case 0: break;

// 1 points: case 1: MeshFromPoints(square.centreLeft, square.centreBottom, square.bottomLeft); break; case 2: MeshFromPoints(square.bottomRight, square.centreBottom, square.centreRight); break; case 4: MeshFromPoints(square.topRight, square.centreRight, square.centreTop); break; case 8: MeshFromPoints(square.topLeft, square.centreTop, square.centreLeft); break;

// 2 points: case 3: MeshFromPoints(square.centreRight, square.bottomRight, square.bottomLeft, square.centreLeft); break; case 6: MeshFromPoints(square.centreTop, square.topRight, square.bottomRight, square.centreBottom); break; case 9: MeshFromPoints(square.topLeft, square.centreTop, square.centreBottom, square.bottomLeft); break; case 12: MeshFromPoints(square.topLeft, square.topRight, square.centreRight, square.centreLeft); break; case 5: MeshFromPoints(square.centreTop, square.topRight, square.centreRight, square.centreBottom, square.bottomLeft, square.centreLeft); break; case 10: MeshFromPoints(square.topLeft, square.centreTop, square.centreRight, square.bottomRight, square.centreBottom, square.centreLeft); break;

// 3 point: case 7: MeshFromPoints(square.centreTop, square.topRight, square.bottomRight, square.bottomLeft, square.centreLeft); break; case 11: MeshFromPoints(square.topLeft, square.centreTop, square.centreRight, square.bottomRight, square.bottomLeft); break; case 13: MeshFromPoints(square.topLeft, square.topRight, square.centreRight, square.centreBottom, square.bottomLeft); break; case 14: MeshFromPoints(square.topLeft, square.topRight, square.bottomRight, square.centreBottom, square.centreLeft); break;

// 4 point: case 15: MeshFromPoints(square.topLeft, square.topRight, square.bottomRight, square.bottomLeft); checkedVertices.Add(square.topLeft.vertexIndex); checkedVertices.Add(square.topRight.vertexIndex); checkedVertices.Add(square.bottomRight.vertexIndex); checkedVertices.Add(square.bottomLeft.vertexIndex); break; }

}

void MeshFromPoints(params Node[] points) { AssignVertices(points);

if (points.Length >= 3) CreateTriangle(points[0], points[1], points[2]); if (points.Length >= 4) CreateTriangle(points[0], points[2], points[3]); if (points.Length >= 5) CreateTriangle(points[0], points[3], points[4]); if (points.Length >= 6) CreateTriangle(points[0], points[4], points[5]);

}

void AssignVertices(Node[] points) { for (int i = 0; i < points.Length; i++) { if (points[i].vertexIndex == -1) { points[i].vertexIndex = vertices.Count; vertices.Add(points[i].position); } } }

void CreateTriangle(Node a, Node b, Node c) { triangles.Add(a.vertexIndex); triangles.Add(b.vertexIndex); triangles.Add(c.vertexIndex);

Triangle triangle = new Triangle(a.vertexIndex, b.vertexIndex, c.vertexIndex); AddTriangleToDictionary(triangle.vertexIndexA, triangle); AddTriangleToDictionary(triangle.vertexIndexB, triangle); AddTriangleToDictionary(triangle.vertexIndexC, triangle); }

void AddTriangleToDictionary(int vertexIndexKey, Triangle triangle) { if (triangleDictionary.ContainsKey(vertexIndexKey)) { triangleDictionary[vertexIndexKey].Add(triangle); } else { List triangleList = new List(); triangleList.Add(triangle); triangleDictionary.Add(vertexIndexKey, triangleList); } }

void CalculateMeshOutlines() {

for (int vertexIndex = 0; vertexIndex < vertices.Count; vertexIndex++) { if (!checkedVertices.Contains(vertexIndex)) { int newOutlineVertex = GetConnectedOutlineVertex(vertexIndex); if (newOutlineVertex != -1) { checkedVertices.Add(vertexIndex);

List newOutline = new List(); newOutline.Add(vertexIndex); outlines.Add(newOutline); FollowOutline(newOutlineVertex, outlines.Count - 1); outlines[outlines.Count - 1].Add(vertexIndex); } } } }

void FollowOutline(int vertexIndex, int outlineIndex) { outlines[outlineIndex].Add(vertexIndex); checkedVertices.Add(vertexIndex); int nextVertexIndex = GetConnectedOutlineVertex(vertexIndex);

if (nextVertexIndex != -1) { FollowOutline(nextVertexIndex, outlineIndex); } }

int GetConnectedOutlineVertex(int vertexIndex) { List trianglesContainingVertex = triangleDictionary[vertexIndex];

for (int i = 0; i < trianglesContainingVertex.Count; i++) { Triangle triangle = trianglesContainingVertex[i];

for (int j = 0; j < 3; j++) { int vertexB = triangle[j]; if (vertexB != vertexIndex && !checkedVertices.Contains(vertexB)) { if (IsOutlineEdge(vertexIndex, vertexB)) { return vertexB; } } } }

return -1; }

bool IsOutlineEdge(int vertexA, int vertexB) { List trianglesContainingVertexA = triangleDictionary[vertexA]; int sharedTriangleCount = 0;

for (int i = 0; i < trianglesContainingVertexA.Count; i++) { if (trianglesContainingVertexA[i].Contains(vertexB)) { sharedTriangleCount++; if (sharedTriangleCount > 1) { break; } } } return sharedTriangleCount == 1; }

struct Triangle { public int vertexIndexA; public int vertexIndexB; public int vertexIndexC; int[] vertices;

public Triangle(int a, int b, int c) { vertexIndexA = a; vertexIndexB = b; vertexIndexC = c;

vertices = new int[3]; vertices[0] = a; vertices[1] = b; vertices[2] = c; }

public int this[int i] { get { return vertices[i]; } }

public bool Contains(int vertexIndex) { return vertexIndex == vertexIndexA || vertexIndex == vertexIndexB || vertexIndex == vertexIndexC; } }

public class SquareGrid { public Square[,] squares;

public SquareGrid(int[,] map, float squareSize) { int nodeCountX = map.GetLength(0); int nodeCountY = map.GetLength(1); float mapWidth = nodeCountX * squareSize; float mapHeight = nodeCountY * squareSize;

ControlNode[,] controlNodes = new ControlNode[nodeCountX, nodeCountY];

for (int x = 0; x < nodeCountX; x++) { for (int y = 0; y < nodeCountY; y++) { Vector3 pos = new Vector3(-mapWidth / 2 + x * squareSize + squareSize / 2, 0, -mapHeight / 2 + y * squareSize + squareSize / 2); controlNodes[x, y] = new ControlNode(pos, map[x, y] == 1, squareSize); } }

squares = new Square[nodeCountX - 1, nodeCountY - 1]; for (int x = 0; x < nodeCountX - 1; x++) { for (int y = 0; y < nodeCountY - 1; y++) { squares[x, y] = new Square(controlNodes[x, y + 1], controlNodes[x + 1, y + 1], controlNodes[x + 1, y], controlNodes[x, y]); } }

} }

public class Square {

public ControlNode topLeft, topRight, bottomRight, bottomLeft; public Node centreTop, centreRight, centreBottom, centreLeft; public int configuration;

public Square(ControlNode _topLeft, ControlNode _topRight, ControlNode _bottomRight, ControlNode _bottomLeft) { topLeft = _topLeft; topRight = _topRight; bottomRight = _bottomRight; bottomLeft = _bottomLeft;

centreTop = topLeft.right; centreRight = bottomRight.above; centreBottom = bottomLeft.right; centreLeft = bottomLeft.above;

if (topLeft.active) configuration += 8; if (topRight.active) configuration += 4; if (bottomRight.active) configuration += 2; if (bottomLeft.active) configuration += 1; }

}

public class Node { public Vector3 position; public int vertexIndex = -1;

public Node(Vector3 _pos) { position = _pos; } }

public class ControlNode : Node {

public bool active; public Node above, right;

public ControlNode(Vector3 _pos, bool _active, float squareSize) : base(_pos) { active = _active; above = new Node(position + Vector3.forward * squareSize / 2f); right = new Node(position + Vector3.right * squareSize / 2f); }

} }