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

ID: 3720032 • Letter: C

Question

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 don’t 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);
}

}
}

Explanation / Answer