Maze.razor

@page "/maze"

<div @onkeydown="@OnKeyDown" tabindex="0">
	<h3>Maze</h3>
	<div class="source-code-badge">
		<a href="https://github.com/ZacharyPatten/dotnet-blazor-games/blob/main/dotnet-blazor-games/Pages/Maze.razor" alt="Go To Source Code">
			<img title="Go To Source Code" alt="Go To Source Code" src="https://img.shields.io/badge/source-code-black?logo=github&amp;style=flat">
		</a>
	</div>
	<div class="row">
		@((MarkupString)MazeRender)
	</div>
	<div class="row">
		<div class="controls">
			<button class="btn btn-primary" @onclick="() => { TryMove(Direction.Left); StateHasChanged(); }">←</button>
			<button class="btn btn-primary" @onclick="() => { TryMove(Direction.Right); StateHasChanged(); }">→</button>
			<button class="btn btn-primary" @onclick="() => { TryMove(Direction.Up); StateHasChanged(); }">↑</button>
			<button class="btn btn-primary" @onclick="() => { TryMove(Direction.Down); StateHasChanged(); }">↓</button>
		</div>
	</div>
	<div class="row controls">
		<button class="btn btn-primary" @onclick="() => { Win = false; PlayerX = 0; PlayerY = 0; _currentMaze = Generate(10, 10); StateHasChanged(); }">New Maze</button>
	</div>
	<div class="row winmessage" style="display:@(Win ? "block" : "none")">
		You Win! Press "New Maze" to play again.
	</div>
	<div class="alert alert-dismissible alert-secondary">
		<strong>Rules:</strong>
		You are the blue square, and always start in the top left. Nagivate the maze to make it to the end in the bottom right.
		Keyboard inputs (←, →, ↑, ↓) are supported if you <i>click on the board</i>.
	</div>
</div>

<style>

	.player {
		x: @(PlayerX * 3 + 1.2);
		y: @(PlayerY * 3 + 1.2);
	}

	.controls {
		margin-top: 1rem;
	}

		.controls button {
			margin-right: .5rem;
			margin-bottom: .5rem;
		}

</style>

@code
{
	bool Win = false;

	Tile[,] _currentMaze;
	Tile[,] CurrentMaze => _currentMaze ?? (_currentMaze = Generate(10, 10));
	string MazeRender => RenderToSvg(CurrentMaze);
	int PlayerX = 0;
	int PlayerY = 0;

	enum Direction
	{
		Up = 1,
		Down = 2,
		Left = 3,
		Right = 4,
	}

	[Flags]
	enum Tile
	{
		Null = 0,
		Up = 1,
		Down = 2,
		Left = 4,
		Right = 8,
		Start = 16,
		End = 32,
	}

	void OnKeyDown(KeyboardEventArgs e)
	{
		switch (e.Key)
		{
			case "ArrowLeft":  TryMove(Direction.Left); break;
			case "ArrowRight": TryMove(Direction.Right); break;
			case "ArrowUp":    TryMove(Direction.Up); break;
			case "ArrowDown":  TryMove(Direction.Down); break;
			default: return;
		}
		StateHasChanged();
	}

	void TryMove(Direction direction)
	{
		if (!Win)
		{
			if (direction is Direction.Up && CurrentMaze[PlayerY, PlayerX].HasFlag(Tile.Up))
			{
				PlayerY--;
			}
			else if (direction is Direction.Down && CurrentMaze[PlayerY, PlayerX].HasFlag(Tile.Down))
			{
				PlayerY++;
			}
			else if (direction is Direction.Left && CurrentMaze[PlayerY, PlayerX].HasFlag(Tile.Left))
			{
				PlayerX--;
			}
			else if (direction is Direction.Right && CurrentMaze[PlayerY, PlayerX].HasFlag(Tile.Right))
			{
				PlayerX++;
			}
			if (PlayerX == CurrentMaze.GetLength(1) - 1 && PlayerY == CurrentMaze.GetLength(0) - 1)
			{
				Win = true;
			}
		}
	}

	#region Algorithm 1

	class Node
	{
		internal int Row;
		internal int Column;
		internal bool UpExplored;
		internal bool DownExplored;
		internal bool LeftExplored;
		internal bool RightExplored;
	}

	Tile[,] Generate(
		int rows, int columns,
		int? start_row = null, int? start_column = null,
		int? end_row = null, int? end_column = null)
	{
		// parameter defaults
		start_row ??= 0;
		start_column ??= 0;
		end_row ??= rows - 1;
		end_column ??= columns - 1;

		#region Exceptions
		if (rows <= 1)
			throw new ArgumentOutOfRangeException(nameof(rows));
		if (columns <= 1)
			throw new ArgumentOutOfRangeException(nameof(columns));
		if (start_row < 0 || rows < start_row)
			throw new ArgumentOutOfRangeException(nameof(start_row));
		if (end_row < 0 || rows < end_row || start_row == end_row)
			throw new ArgumentOutOfRangeException(nameof(end_row));
		if (start_column < 0 || columns < start_column)
			throw new ArgumentOutOfRangeException(nameof(start_column));
		if (end_column < 0 || columns < end_column || start_column == end_column)
			throw new ArgumentOutOfRangeException(nameof(end_column));
		#endregion

		Tile[,] maze = new Tile[rows, columns];
		Random random = new Random();
		var directionBuffer = new (int Row, int Column)[4];

		maze[start_row.Value, start_column.Value] = Tile.Start;
		maze[end_row.Value, end_column.Value] = Tile.End;

		// generate a valid path (so the maze is guaranteed to be solve-able)
		{
			var stack = new Stack<Node>();
			stack.Push(new Node()
			{
				Row = start_row.Value,
				Column = start_column.Value,
			});

			#region Optimizations

			// optimizations to prevent the algorithm from exploring unnecessary isolations
			// that will never reach the end of the maze. these currently depend on using the
			// default start/end locations, but they could be improved to help with custom
			// locations too. I am just lazy and didn't care enough to make a more general
			// purpose algorithm...

			bool DefaultLocations() =>
				start_row == 0 && start_column == 0 &&
				end_row == rows - 1 && end_column == columns - 1;
			bool UpOptimization(int column) => !(DefaultLocations() && column == columns - 1 || column == 0);
			bool LeftOptimization(int row) => !(DefaultLocations() && row == rows - 1 || row == 0);

			#endregion

			static bool NullOrEnd(Tile tile) => tile is Tile.Null || tile is Tile.End;

			bool MoveRandom()
			{
				Node node = stack.Peek();
				int i = 0;
				// populate possible moves
				if (node.Row != rows - 1 && NullOrEnd(maze[node.Row + 1, node.Column]) && !node.DownExplored)
					directionBuffer[i++] = (node.Row + 1, node.Column);
				if (node.Row != 0 && NullOrEnd(maze[node.Row - 1, node.Column]) && !node.UpExplored && UpOptimization(node.Column))
					directionBuffer[i++] = (node.Row - 1, node.Column);
				if (node.Column != 0 && NullOrEnd(maze[node.Row, node.Column - 1]) && !node.LeftExplored && LeftOptimization(node.Row))
					directionBuffer[i++] = (node.Row, node.Column - 1);
				if (node.Column != columns - 1 && NullOrEnd(maze[node.Row, node.Column + 1]) && !node.RightExplored)
					directionBuffer[i++] = (node.Row, node.Column + 1);
				// if no possibilities return false
				if (i is 0)
					return false;
				// get a random move from the possibilities
				var move = directionBuffer[random.Next(0, i)];
				// mark the move as explored
				if (move.Row == node.Row + 1)
				{
					node.DownExplored = true;
					maze[node.Row, node.Column] |= Tile.Down;
					maze[move.Row, move.Column] |= Tile.Up;
				}
				if (move.Row == node.Row - 1)
				{
					node.UpExplored = true;
					maze[node.Row, node.Column] |= Tile.Up;
					maze[move.Row, move.Column] |= Tile.Down;
				}
				if (move.Column == node.Column - 1)
				{
					node.LeftExplored = true;
					maze[node.Row, node.Column] |= Tile.Left;
					maze[move.Row, move.Column] |= Tile.Right;
				}
				if (move.Column == node.Column + 1)
				{
					node.RightExplored = true;
					maze[node.Row, node.Column] |= Tile.Right;
					maze[move.Row, move.Column] |= Tile.Left;
				}
				stack.Push(new Node()
				{
					Row = move.Row,
					Column = move.Column,
				});
				// return the move
				return true;
			}

			while (stack.Peek().Row != end_row || stack.Peek().Column != end_column)
			{
				if (!MoveRandom())
				{
					Node move = stack.Pop();
					maze[move.Row, move.Column] = Tile.Null;
					Node parent = stack.Peek();
					if (move.Row == parent.Row - 1) maze[parent.Row, parent.Column] &= ~Tile.Up;
					if (move.Row == parent.Row + 1) maze[parent.Row, parent.Column] &= ~Tile.Down;
					if (move.Column == parent.Column + 1) maze[parent.Row, parent.Column] &= ~Tile.Right;
					if (move.Column == parent.Column - 1) maze[parent.Row, parent.Column] &= ~Tile.Left;
				}
			}
		}

		// Generate invalid paths (to fill in the rest of the maze)
		{
			var stack = new Stack<Node>();
			var invalidPath = new HashSet<(int Row, int Column)>();
			Tile previousMove;

			int CountNulls()
			{
				int count = 0;
				for (int row = 0; row < rows; row++)
					for (int column = 0; column < columns; column++)
						if (maze[row, column] is Tile.Null)
							count++;
				return count;
			}

			(int Row, int Column)? GetRandomNull(int? nullCount = null)
			{
				int nullCountInt = nullCount ?? CountNulls();
				// if no Tile.Null's, return null
				if (nullCountInt <= 0) return null;
				// nulls exist, get a random one
				int index = random.Next(0, nullCountInt + 1);
				(int, int) _null = default;
				for (int row = 0; row < rows && index > 0; row++)
					for (int column = 0; column < columns && index > 0; column++)
						if (maze[row, column] is Tile.Null && --index == 0)
							_null = (row, column);
				return _null;
			}

			bool MoveRandom()
			{
				Node node = stack.Peek();
				int i = 0;
				if (node.Row != rows - 1 && !invalidPath.Contains((node.Row + 1, node.Column)) && !node.DownExplored)
					directionBuffer[i++] = (node.Row + 1, node.Column);
				if (node.Row != 0 && !invalidPath.Contains((node.Row - 1, node.Column)) && !node.UpExplored)
					directionBuffer[i++] = (node.Row - 1, node.Column);
				if (node.Column != 0 && !invalidPath.Contains((node.Row, node.Column - 1)) && !node.LeftExplored)
					directionBuffer[i++] = (node.Row, node.Column - 1);
				if (node.Column != columns - 1 && !invalidPath.Contains((node.Row, node.Column + 1)) && !node.RightExplored)
					directionBuffer[i++] = (node.Row, node.Column + 1);
				if (i is 0)
					return false;
				var move = directionBuffer[random.Next(0, i)];
				if (move.Row == node.Row + 1)
				{
					node.DownExplored = true;
					maze[node.Row, node.Column] |= Tile.Down;
					maze[move.Row, move.Column] |= previousMove = Tile.Up;
				}
				if (move.Row == node.Row - 1)
				{
					node.UpExplored = true;
					maze[node.Row, node.Column] |= Tile.Up;
					maze[move.Row, move.Column] |= previousMove = Tile.Down;
				}
				if (move.Column == node.Column - 1)
				{
					node.LeftExplored = true;
					maze[node.Row, node.Column] |= Tile.Left;
					maze[move.Row, move.Column] |= previousMove = Tile.Right;
				}
				if (move.Column == node.Column + 1)
				{
					node.RightExplored = true;
					maze[node.Row, node.Column] |= Tile.Right;
					maze[move.Row, move.Column] |= previousMove = Tile.Left;
				}
				stack.Push(new Node()
				{
					Row = move.Row,
					Column = move.Column,
				});
				invalidPath.Add((node.Row, node.Column));
				return true;
			}

			(int Row, int Column)? nullStart;
			while ((nullStart = GetRandomNull()).HasValue)
			{
				stack.Clear();
				invalidPath.Clear();
				stack.Push(new Node()
				{
					Row = nullStart.Value.Row,
					Column = nullStart.Value.Column,
				});
				invalidPath.Add((nullStart.Value.Row, nullStart.Value.Column));
				previousMove = Tile.Null;
				while (maze[stack.Peek().Row, stack.Peek().Column] == previousMove)
				{
					if (!MoveRandom())
					{
						Node move = stack.Pop();
						Node parent = stack.Peek();
						if (move.Row == parent.Row - 1)
						{
							maze[move.Row, move.Column] &= ~Tile.Down;
							maze[parent.Row, parent.Column] &= ~Tile.Up;
						}
						if (move.Row == parent.Row + 1)
						{
							maze[move.Row, move.Column] &= ~Tile.Up;
							maze[parent.Row, parent.Column] &= ~Tile.Down;
						}
						if (move.Column == parent.Column + 1)
						{
							maze[move.Row, move.Column] &= ~Tile.Left;
							maze[parent.Row, parent.Column] &= ~Tile.Right;
						}
						if (move.Column == parent.Column - 1)
						{
							maze[move.Row, move.Column] &= ~Tile.Right;
							maze[parent.Row, parent.Column] &= ~Tile.Left;
						}
					}
				}
			}
		}

		return maze;
	}

	#endregion

	string RenderToSvg(Tile[,] maze)
	{
		System.Text.StringBuilder stringBuilder = new System.Text.StringBuilder();
		stringBuilder.AppendLine();
		stringBuilder.AppendLine($@"<svg width=""60vmin"" height=""60vmin"" viewBox=""0 0 {maze.GetLength(0) * 3} {maze.GetLength(1) * 3}"" preserveAspectRatio=""xMinYMin meet"" xmlns=""http://www.w3.org/2000/svg"" xmlns:svg=""http://www.w3.org/2000/svg"">");
		for (int i = 0; i < maze.GetLength(0); i++)
		{
			for (int j = 0; j < maze.GetLength(1); j++)
			{
				// corners
				{
					stringBuilder.AppendLine($@"{'\t'}<rect fill=""#24292e"" stroke=""#24292e"" stroke-width=""0"" width=""1"" height=""1"" x=""{i * 3 + 0}"" y=""{j * 3 + 0}""/>");
					stringBuilder.AppendLine($@"{'\t'}<rect fill=""#24292e"" stroke=""#24292e"" stroke-width=""0"" width=""1"" height=""1"" x=""{i * 3 + 2}"" y=""{j * 3 + 0}""/>");
					stringBuilder.AppendLine($@"{'\t'}<rect fill=""#24292e"" stroke=""#24292e"" stroke-width=""0"" width=""1"" height=""1"" x=""{i * 3 + 0}"" y=""{j * 3 + 2}""/>");
					stringBuilder.AppendLine($@"{'\t'}<rect fill=""#24292e"" stroke=""#24292e"" stroke-width=""0"" width=""1"" height=""1"" x=""{i * 3 + 2}"" y=""{j * 3 + 2}""/>");
				}
				// sides
				if (!maze[j, i].HasFlag(Tile.Up))
				{
					stringBuilder.AppendLine($@"{'\t'}<rect fill=""#24292e"" stroke=""#24292e"" stroke-width=""0"" width=""3"" height=""1"" x=""{i * 3 + 0}"" y=""{j * 3 + 0}""/>");
				}
				if (!maze[j, i].HasFlag(Tile.Down))
				{
					stringBuilder.AppendLine($@"{'\t'}<rect fill=""#24292e"" stroke=""#24292e"" stroke-width=""0"" width=""3"" height=""1"" x=""{i * 3 + 0}"" y=""{j * 3 + 2}""/>");
				}
				if (!maze[j, i].HasFlag(Tile.Left))
				{
					stringBuilder.AppendLine($@"{'\t'}<rect fill=""#24292e"" stroke=""#24292e"" stroke-width=""0"" width=""1"" height=""3"" x=""{i * 3 + 0}"" y=""{j * 3 + 0}""/>");
				}
				if (!maze[j, i].HasFlag(Tile.Right))
				{
					stringBuilder.AppendLine($@"{'\t'}<rect fill=""#24292e"" stroke=""#24292e"" stroke-width=""0"" width=""1"" height=""3"" x=""{i * 3 + 2}"" y=""{j * 3 + 0}""/>");
				}
			}
		}
		stringBuilder.AppendLine($@"{'\t'}<rect class=""start"" fill=""#bbb"" stroke=""#24292e"" stroke-width=""0"" width="".6"" height="".6"" x=""1.2"" y=""1.2""/>");
		stringBuilder.AppendLine($@"{'\t'}<rect class=""end"" fill=""#999"" stroke=""#24292e"" stroke-width=""0"" width="".6"" height="".6"" x=""{maze.GetLength(0) * 3 - 1.8}"" y=""{maze.GetLength(1) * 3 - 1.8}""/>");
		stringBuilder.AppendLine($@"{'\t'}<rect class=""player"" fill=""#7abafc"" stroke=""#24292e"" stroke-width=""0"" width="".6"" height="".6"" x=""2.2"" y=""2.2""/>");
		stringBuilder.AppendLine($@"</svg>");
		stringBuilder.AppendLine();
		return stringBuilder.ToString();
	}
}