JvlS Dev Labyrinth

Development page for the Labyrinth system in J'ai vu le Soleil

Stage One: Dedalus

Well, at first, my goal was to build a simple procedural Labyrinth. So, because I'm a smartass, I called it Dedalus.

Dedalus is quite simple and works in two stages:

Create a grid floor

The first version utilizes plane primitive. This is a problem since Unity's WebGL compiler will NOT generate primitives, for some obscure reason.

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


/// <summary>
/// Dedalus: Maze builder for J'ai vu le soleil
/// Code by laei
/// </summary>

public enum linkPosition{
	//which wall is that link on
	north,
	east,
	south,
	west

}

public class link{
	public cell nearCell;
	public bool openWall;
	public linkPosition linkPos;

}

public class cell{
	public GameObject GO;
	public float size;
	public List<link> links;
	public int distanceIndex;
}




public class Dedalus : MonoBehaviour {
	public int seed;
	public int width;
	public int length;
	public float CellSurfaceSize;

	public Vector2 StartCell = new Vector2(0,0);
	public Vector2 EndCell = new Vector3(1,1);
	public cell[,] floor;

	private int seedIndex;

	public void reset(){
		foreach(cell C in floor){
			DestroyImmediate(C.GO);
		}
		floor = new cell[width, length];
	}

	public void makeFloor(){
		floor = new cell[width, length];
		for(int i = 0; i < width; i++){
			for(int j = 0; j < length; j++){
				floor[i,j] = new cell();
				//floor[i,j].GO = new GameObject();
				floor[i,j].GO = GameObject.CreatePrimitive(PrimitiveType.Plane);
				GameObject go = floor[i,j].GO;
				go.transform.localScale = new Vector3(CellSurfaceSize / 10f,CellSurfaceSize /10f,CellSurfaceSize /10f);
				go.name = "Cell_[" + i + "," + j +"]";
				//move gameobject in its place
				go.transform.position = new Vector3(i * CellSurfaceSize + this.gameObject.transform.position.x, this.gameObject.transform.position.y, j * CellSurfaceSize + this.gameObject.transform.position.z);
				go.transform.parent = this.transform;
				floor[i,j].links = new List<link>();
				floor[i,j].distanceIndex = -1;
			}
		}
		{
			//leftWall
			GameObject LW = GameObject.CreatePrimitive(PrimitiveType.Cube);
			LW.name = "LeftWall";
			LW.transform.parent = this.transform;
			LW.transform.localScale = new Vector3(CellSurfaceSize * width, 3f, 1f);
			LW.transform.localPosition = new Vector3((CellSurfaceSize * width/ 2f) - (0.5f * CellSurfaceSize), 1.5f, - CellSurfaceSize / 2f);

			//RightWall
			GameObject RW = GameObject.CreatePrimitive(PrimitiveType.Cube);
			RW.name = "RightWall";
			RW.transform.parent = this.transform;
			RW.transform.localScale = new Vector3(CellSurfaceSize * width, 3f, 1f);
			RW.transform.localPosition = new Vector3((CellSurfaceSize * width / 2f) - (0.5f * CellSurfaceSize), 1.5f, CellSurfaceSize * length - CellSurfaceSize / 2f);

			//North
			GameObject NW = GameObject.CreatePrimitive(PrimitiveType.Cube);
			NW.name = "NorthWall";
			NW.transform.parent = this.transform;
			NW.transform.localScale = new Vector3(1f, 3f, CellSurfaceSize * length);
			NW.transform.localPosition = new Vector3(CellSurfaceSize * width - CellSurfaceSize / 2f, 1.5f, (CellSurfaceSize * length / 2f) - (0.5f * CellSurfaceSize));

			//South
			GameObject SW = GameObject.CreatePrimitive(PrimitiveType.Cube);
			SW.name = "SouthWall";
			SW.transform.parent = this.transform;
			SW.transform.localScale = new Vector3(1f, 3f, CellSurfaceSize * length);
			SW.transform.localPosition = new Vector3( - CellSurfaceSize / 2f, 1.5f, (CellSurfaceSize * length / 2f) - (0.5f * CellSurfaceSize));

			//Goal
			GameObject Goal = GameObject.CreatePrimitive(PrimitiveType.Cylinder);
			Goal.name = "Goal";
			Goal.transform.parent = this.transform;
			Goal.transform.localScale = new Vector3(1f, 200f, 1f);
			Goal.transform.localPosition = floor[floor.GetLength(0) - 1, floor.GetLength(1) - 1].GO.transform.position + Vector3.up * 100f;
		}

		// Populating the links
		for(int i = 0; i < width; i++){
			for(int j = 0; j < length; j++){
				if(i > 0){
					link daLink = new link();
					daLink.nearCell = floor[i - 1, j];
					daLink.openWall = true;
					daLink.linkPos = linkPosition.east;
					floor[i,j].links.Add(daLink);
				}

				if(i < (width - 1)){
					link daLink = new link();
					daLink.nearCell = floor[i + 1, j];
					daLink.openWall = true;
					daLink.linkPos = linkPosition.west;
					floor[i,j].links.Add(daLink);
				}


				if(j > 0){
					link daLink = new link();
					daLink.nearCell = floor[i, j - 1];
					daLink.openWall = true;
					daLink.linkPos = linkPosition.north;
					floor[i,j].links.Add(daLink);
				}

				if(j < (length - 1)){
					link daLink = new link();
					daLink.nearCell = floor[i, j + 1];
					daLink.openWall = true;
					daLink.linkPos = linkPosition.south;
					floor[i,j].links.Add(daLink);
				}
			}
		}
	}

	public void evaluate(){
		List<cell> toVisit = new List<cell>();
		List<cell> toVisitNext = new List<cell>();
		int currentDistance = 0;
		toVisit.Add(floor[(int)StartCell.x, (int)StartCell.y]);
		while(toVisit.Count > 0 && currentDistance < width*length){
			toVisitNext.Clear();
			foreach(cell C in toVisit){
				C.distanceIndex = currentDistance;
				foreach(link nxt in C.links){
					if(nxt.openWall && nxt.nearCell.distanceIndex == -1) //checks the wall is open & nearCell is not already visited.
						toVisitNext.Add(nxt.nearCell);
				}
			}
			toVisit.Clear();
			toVisit.AddRange(toVisitNext);
			currentDistance++;
		}
		//Checking
		if(toVisit.Count !=0){
			Debug.Log("Incomplete visit - " + toVisit.Count);
			foreach(cell c in toVisit){
				Debug.Log(c.GO.name + " is unchecked");
			}
		}
		for(int i = 0; i < width; i++){
			for(int j = 0; j < length; j++){
				if(floor[i,j].distanceIndex == -1)
					Debug.Log("Warning: " + this.name + " has innaccessible cell@ " + i + ", " + j);
			}
		}
		Debug.Log("Maze shortest path is " + floor[(int)EndCell.x, (int)EndCell.y].distanceIndex + " cells long");
	}

	public void amazeMe(){
		//Recursive Backtracking Algorithm
		//Erase all distances
		foreach(cell C in floor){
			C.distanceIndex = -1;
		}
		seedIndex = 0;
		cell current = floor[(int)StartCell.x, (int)StartCell.y];
		recursion(current, 0);

		foreach(cell C in floor){
			foreach(link L in C.links){
				L.openWall = (Mathf.Abs(C.distanceIndex - L.nearCell.distanceIndex) == 1);
				if(!L.openWall){
					//build wall
					GameObject wall = GameObject.CreatePrimitive(PrimitiveType.Cube);
					wall.name = L.linkPos.ToString() + "WallOn_" + C.GO.name; 
					wall.transform.localScale = new Vector3(CellSurfaceSize + 1.5f ,3f , 1f);
					wall.transform.parent = C.GO.transform;

					switch(L.linkPos){
					case linkPosition.east :
						wall.transform.localPosition = Vector3.left * (CellSurfaceSize + 0.75f)+ Vector3.up * 3f;
						wall.transform.Rotate(new Vector3(0f,90f,0f));
						break;
					case linkPosition.west :
						wall.transform.localPosition = Vector3.right* (CellSurfaceSize + 0.75f) + Vector3.up * 3f;
						wall.transform.Rotate(new Vector3(0f,90f,0f));
						break;
					case linkPosition.north :
						wall.transform.localPosition = Vector3.back * (CellSurfaceSize + 0.75f) + Vector3.up * 3f;

						break;
					case linkPosition.south :
						wall.transform.localPosition =  Vector3.forward * (CellSurfaceSize + 0.75f) + Vector3.up * 3f;
						break;
					}
				}
			}
		}
		materializeMe();
	}

	private int seedRead(){
		int i = seedIndex;
		seedIndex++;
		if(seedIndex == seed.ToString().Length)
			seedIndex = 0;
		return int.Parse(seed.ToString().Substring(i, 1));
	}
		
	private void recursion(cell C, int currentDist){
		bool deadend = false;
		C.distanceIndex = currentDist;
		while(!deadend){
			bool canVisitNeighbour = false;
			for(int i = 0; i < C.links.Count && !canVisitNeighbour; i++)
				canVisitNeighbour = C.links[i].openWall && C.links[i].nearCell.distanceIndex == -1;

			if(canVisitNeighbour){
				List<cell> visitable = new List<cell>();
				for(int i = 0; i < C.links.Count; i++){
					if(C.links[i].openWall && C.links[i].nearCell.distanceIndex == -1)
						visitable.Add(C.links[i].nearCell);
					}
					//May require the double check for bidirectionality
				int alea = seedRead() % 4;
				recursion(visitable[alea % visitable.Count], currentDist + 1);
			}else
				deadend = true;
		}
	}

	public void materializeMe(){
		Material Blank = Resources.Load<Material>("Blank");
		//List<MeshRenderer> MRl = new List<MeshRenderer>(GetComponents<MeshRenderer>());
		List<Transform> children =  new List<Transform>(this.transform.GetComponentsInChildren<Transform>());
		children.Remove(this.transform);
		foreach(Transform child in children){
			Material[] m = child.gameObject.GetComponent<Renderer>().materials;
			if(m != null){
				m[0] = Blank;
				child.gameObject.GetComponent<MeshRenderer>().materials = m;
			}
		}
	}

	// Use this for initialization
	void Start () {
		CellSurfaceSize = 5f;
		seed = Random.Range(12021, int.MaxValue);
		width = Random.Range(8,75);
		length = Random.Range(8,75);
		makeFloor();
		amazeMe();

	}
	
	// Update is called once per frame
	void Update () {
		if(Input.GetKeyDown(KeyCode.T)){
			List<Transform> toDestroy =  new List<Transform>(this.transform.GetComponentsInChildren<Transform>());
			toDestroy.Remove(this.transform);
			foreach(Transform GO in toDestroy){
				Destroy(GO.gameObject);
			}
			reset();

			seed = Random.Range(12021, int.MaxValue);
			width = Random.Range(8,75);
			length = Random.Range(8,75);
			makeFloor();
			amazeMe();

		}
	}
}