C# Maze Pathfinding Algorithm

Use pathfinding logic to go from a start to end point in a maze. Solve a maze.

Maze. In a maze we find walls, a start point, and an end point. 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 end point.

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.

Moves: This jagged int array specifies the possible directions our agent can move on each turn.

GetMazeArray: Here we convert the maze string into a more usable jagged int array. We use Split and switch to parse the string.

Split Switch

Display: We take our memory representation of the maze (a jagged int array) and print it to the screen as characters.

IsValidPos: This helper method tells us if a square we are considering is within the bounds of our maze array.

ModifyPath: Considers the maze and advances our agent's path to a possible square. It returns a value that indicates the agent's status.

C# program that solves mazes 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 end point. 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++; } } } Output 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

Notes, above program. This algorithm is not advanced. It solves the maze by always moving right first—and these mistakes are counted in its final move count.

Notes, moves. Our agent manages to solve this maze in 24 moves (evaluations). You can follow its decision as it moves with the period paths. It finds its end point.

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.

Copy: To use recursion on an array we are modifying, we must copy it on each method call. This prevents data corruption.

Display: To display the optimal path, add back the Display() method and then call on each best move—the last one is the optimal solution.

20 moves: This agent solves the maze in 20 moves, which is as well as I can do.

C# program that finds optimal moves 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) { // End point. // ... 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}"); } } } } } Output 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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# Maze Pathfinding Algorithm

Related Links:

.Net

Java

Related Links