Home
C#
Maze Algorithm
This page was last reviewed on Feb 19, 2023.
Dot Net Perls
Maze. In a maze we find walls, a start point, and an endpoint. With brute force we can always solve a maze (if it can be solved). Recursion or iteration can be used.
With a string we can specify the maze data. Our algorithm takes a step on each user input. Our intelligent agent avoids obstacles and reaches its endpoint.
Console.ReadKey
Example code. First we specify the maze string. It has a special format—the "x" is a wall, and the start and end are specified as 1 and 2.
Info The jagged int array specifies the possible directions our agent can move on each turn.
Detail GetMazeArray converts the maze string into a more usable jagged int array. We use Split and switch to parse the string.
String Split
switch
Note Display takes our memory representation of the maze (a jagged int array) and print it to the screen as characters.
Detail IsValidPos() tells us if a square we are considering is within the bounds of our maze array.
Finally ModifyPath() considers the maze and advances our agent's path to a possible square. It returns the agent's status.
using System; class Program { const string _maze = @" xxx1. x x . x2x x. xxx . x x . x xx"; static int[][] _moves = { new int[] { -1, 0 }, new int[] { 0, -1 }, new int[] { 0, 1 }, new int[] { 1, 0 } }; static int[][] GetMazeArray(string maze) { // Split apart the maze string. string[] lines = maze.Split(new char[] { '.', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries); // Create jagged array. int[][] array = new int[lines.Length][]; for (int i = 0; i < lines.Length; i++) { string line = lines[i]; // Create row. var row = new int[line.Length]; for (int x = 0; x < line.Length; x++) { // Set ints from chars. switch (line[x]) { case 'x': row[x] = -1; break; case '1': row[x] = 1; break; case '2': row[x] = -3; break; default: row[x] = 0; break; } } // Store row in jagged array. array[i] = row; } return array; } static void Display(int[][] array) { // Loop over int data and display as characters. for (int i = 0; i < array.Length; i++) { var row = array[i]; for (int x = 0; x < row.Length; x++) { switch (row[x]) { case -1: Console.Write('x'); break; case 1: Console.Write('1'); break; case -3: Console.Write('2'); break; case 0: Console.Write(' '); break; default: Console.Write('.'); break; } } // End line. Console.WriteLine(); } } static bool IsValidPos(int[][] array, int row, int newRow, int newColumn) { // ... Ensure position is within the array bounds. if (newRow < 0) return false; if (newColumn < 0) return false; if (newRow >= array.Length) return false; if (newColumn >= array[row].Length) return false; return true; } static int ModifyPath(int[][] array) { // Loop over rows and then columns. for (int rowIndex = 0; rowIndex < array.Length; rowIndex++) { var row = array[rowIndex]; for (int columnIndex = 0; columnIndex < row.Length; columnIndex++) { // Find a square we have traveled to. int value = array[rowIndex][columnIndex]; if (value >= 1) { // Try all possible moves from this square. foreach (var movePair in _moves) { // Move to a valid square. int newRow = rowIndex + movePair[0]; int newColumn = columnIndex + movePair[1]; if (IsValidPos(array, rowIndex, newRow, newColumn)) { int testValue = array[newRow][newColumn]; if (testValue == 0) { // Travel to a new square for the first time. // ... Record the count of total moves to it. array[newRow][newColumn] = value + 1; // Move has been performed. return 0; } else if (testValue == -3) { // We are at our endpoint. return 1; } } } } } } // We cannot do anything. return -1; } static void Main() { // Parse our maze and display it. var array = GetMazeArray(_maze); Display(array); int count = 0; // Read user input and evaluate maze. while (true) { string line = Console.ReadLine(); int result = ModifyPath(array); if (result == 1) { Console.WriteLine($"DONE: {count} moves"); break; } else if (result == -1) { Console.WriteLine($"FAIL: {count} moves"); break; } else { Display(array); } count++; } } }
xxx1 x x x2x x xxx x x x xx xxx1 x x . x2x x xxx x x x xx xxx1 x x .. x2x x xxx x x x xx xxx1 x x... x2x x xxx x x x xx xxx1 x x... x2x. x xxx x x x xx xxx1 x x... x2x..x xxx x x x xx xxx1 x x... x2x..x xxx. x x x xx xxx1 x x... x2x..x xxx.. x x x xx xxx1 x x... x2x..x xxx.. x .x x xx xxx1 x x... x2x..x xxx... x .x x xx xxx1 x x... x2x..x xxx... x .x. x xx xxx1 x x... x2x..x xxx... x ..x. x xx xxx1 x x... x2x..x xxx... x...x. x xx xxx1 x x... x2x..x xxx... x...x. .x xx xxx1 x x... x2x..x xxx... x...x. .x.xx xxx1 x x... x2x..x xxx... x...x. ..x.xx xxx1 x x... x2x..x xxx... x...x. ...x.xx xxx1 x x... x2x..x xxx... .x...x. ...x.xx xxx1 x x... x2x..x .xxx... .x...x. ...x.xx xxx1 x x... .x2x..x .xxx... .x...x. ...x.xx xxx1 .x x... .x2x..x .xxx... .x...x. ...x.xx . xxx1 .x x... .x2x..x .xxx... .x...x. ...x.xx .. xxx1 .x x... .x2x..x .xxx... .x...x. ...x.xx ...xxx1 .x x... .x2x..x .xxx... .x...x. ...x.xx ...xxx1 .x.x... .x2x..x .xxx... .x...x. ...x.xx DONE: 24 moves
Optimal example. This version is not interactive, but it does find the optimal solution. It uses recursion to evaluate all paths. It records the path with the lowest move count.
Detail To use recursion on an array we are modifying, we must copy it on each method call. This prevents data corruption.
Note To display the optimal path, add back the Display() method and then call on each best move—the last one is the optimal solution.
Result This agent solves the maze in 20 moves, which is as well as I can do.
using System; class Program { const string _maze = @" xxx1. x x . x2x x. xxx . x x . x xx"; static int[][] _moves = { new int[] { -1, 0 }, new int[] { 0, -1 }, new int[] { 0, 1 }, new int[] { 1, 0 } }; static int[][] GetMazeArray(string maze) { string[] lines = maze.Split(new char[] { '.', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries); // Create array. int[][] array = new int[lines.Length][]; for (int i = 0; i < lines.Length; i++) { string line = lines[i]; var row = new int[line.Length]; for (int x = 0; x < line.Length; x++) { switch (line[x]) { case 'x': row[x] = -1; break; case '1': row[x] = 1; break; case '2': row[x] = -3; break; default: row[x] = 0; break; } } array[i] = row; } return array; } static bool IsValidPos(int[][] array, int row, int newRow, int newColumn) { if (newRow < 0) return false; if (newColumn < 0) return false; if (newRow >= array.Length) return false; if (newColumn >= array[row].Length) return false; return true; } static int Move(int[][] arrayTemp, int rowIndex, int columnIndex, int count, ref int lowest) { // Copy map so we can modify it and then abandon it. int[][] array = new int[arrayTemp.Length][]; for (int i = 0; i < arrayTemp.Length; i++) { var row = arrayTemp[i]; array[i] = new int[row.Length]; for (int x = 0; x < row.Length; x++) { array[i][x] = row[x]; } } int value = array[rowIndex][columnIndex]; if (value >= 1) { // Try all moves. foreach (var movePair in _moves) { int newRow = rowIndex + movePair[0]; int newColumn = columnIndex + movePair[1]; if (IsValidPos(array, rowIndex, newRow, newColumn)) { int testValue = array[newRow][newColumn]; if (testValue == 0) { array[newRow][newColumn] = value + 1; // Try another move. Move(array, newRow, newColumn, count + 1, ref lowest); } else if (testValue == -3) { // Endpoint. // ... Could print the optimal maze solution here. if (count + 1 < lowest) { lowest = count + 1; } return 1; } } } } return -1; } static void Main() { var array = GetMazeArray(_maze); // Get start position. for (int i = 0; i < array.Length; i++) { var row = array[i]; for (int x = 0; x < row.Length; x++) { // Start square is here. if (row[x] == 1) { int lowest = int.MaxValue; Move(array, i, x, 0, ref lowest); Console.WriteLine($"Optimal moves: {lowest}"); } } } } }
Optimal moves: 20
Notes, tracing. The agent's exact path could be traced by following the ints from its destination to its start (high to low). Recursion is used to find an optimal path.
Recursion
A summary. With this algorithm, we solve a simple maze. Brute force is used to evaluate all directions. If a wrong turn is taken, it is discarded like it never was traveled.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Feb 19, 2023 (edit).
Home
Changes
© 2007-2024 Sam Allen.