4
\$\begingroup\$

I've written C# code for solving a maze problem. It works, but I want to optimize it so that it could give me all paths. To solve the maze, I walk on the zeros and assumed that the final is reaching -3.

const int MAZE_SIZE = 6;
static int[] allowed_move_row = { 0, -1, 0, 1 };
static int[] allowed_move_col = { 1, 0, -1, 0 };
const int MAX_ALLOWED_MOVES = 4;
static int[,] Optmaze = new int[MAZE_SIZE, MAZE_SIZE];
static int[,] maze  = new int[MAZE_SIZE, MAZE_SIZE] { 
                       { -2 , 0  ,  0   , 0  ,  0  ,  -1 },
                       { -1 , 0  , -1   , 0  , -1  ,  0 } ,
                       { -1 , -1 , -1   , 0  ,  0  ,  0 } ,
                       { -1 , 0  , -1   , -1 ,  0  ,  -1 },
                       { -1 , -1 , -1   , 0  ,  0  ,  0 } ,
                       { -1 , 0  , -1   , -3 ,  0  ,  0 } };

static bool Solve(int previous_row, int previous_col, int next_step_no)
{
     for (int i = 0; i < MAX_ALLOWED_MOVES; i++)
     {
          int col = previous_col + allowed_move_col[i];
          int row = previous_row + allowed_move_row[i];
          if (col < 0 || col >= MAZE_SIZE) 
              continue;
          if (row < 0 || row >= MAZE_SIZE) 
              continue;

          if (maze[row, col] == -3)
              return true;

          if (maze[row, col] != 0) 
              continue;

          maze[row, col] = next_step_no;

          if (Solve(row, col, next_step_no + 1))
              return true;

          else maze[row, col] = 0;
     }
            return false;
}

static void Main(string[] args)
{
    Print(maze);
    Console.WriteLine("-----------Solve-------------");
    if (Solve (0, 0, 1) )
        Print( maze);
    else
        Console.WriteLine("No Result");
}

static void Print(int[,] maze)
{
    for (int i = 0; i < maze.GetLength(0); i++)
    {
        for (int j = 0; j < maze.GetLength(1); j++)
        {
            Console.Write(" " + String.Format("{0,3}",maze[i, j]) + " ");
        }
        Console.WriteLine();
    }
}

Outputting:

       -2    0    0    0    0   -1
       -1    0   -1    0   -1    0
       -1   -1   -1    0    0    0
       -1    0   -1   -1    0   -1
       -1   -1   -1    0    0    0
       -1    0   -1   -3    0    0
       -----------Solve-------------
       -2    1    2    3    0   -1
       -1    0   -1    4   -1    0
       -1   -1   -1    5    6    0
       -1    0   -1   -1    7   -1
       -1   -1   -1    0    8    9
       -1    0   -1   -3   11   10
\$\endgroup\$
  • \$\begingroup\$ I would parallelize the algorithm to make it search from both ends of the maze and stop when they meet half way. More of a brute force optimization than anything cleaver. \$\endgroup\$ – Admiral Nelson Nov 8 '13 at 18:20
  • 4
    \$\begingroup\$ You need to fully define "all paths." I could loop around the same two positions a few billion times and then get back on a path that actually finds a solution and this would be a "path." \$\endgroup\$ – Austin Salonen Nov 8 '13 at 18:24
  • \$\begingroup\$ You can use pathing or search algorithms for this such as A*, B* etc. See wikipedia's the side bar for different approaches to solve pathing problems like this one. \$\endgroup\$ – John S. Nov 8 '13 at 18:32
  • \$\begingroup\$ A helpful answer could be: stackoverflow.com/a/1523678/1445661 \$\endgroup\$ – mao47 Nov 8 '13 at 18:37
2
\$\begingroup\$

Walking all zeros is indeed suboptimal. A good first optimization is to preferentially walk on the zeros that bring you closer to the end point.

To do this, at each step calculate the pythagorean distance between the x,y coords of the array entry you're considering walking to, and the x,y coords of the array entry containing -3. This will be the cost of walking to that square. Store all calculated costs so you don't have to recalculate them.

Then, continue to preferentially choose lowest-cost next squares until you reach the end or a dead end. In cases of dead ends, simply go back and choose the next lowest-cost square that has yet to be traversed. To do this, you will need to keep some notion of path hierarchy, i.e. which steps lead to which next potential steps. A custom node type will do this for you.

If you've made it this far, then congratulations! You have a rudimentary A* path-finding algorithm. For a helpful guide to implementing this algorithm I recommend this resource.

There are further enhancements to A* efficiency, such as the Jump Point Search algorithm, which is best for more open spaces.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy