Maze Escape

 

The first step in the problem is to read in and store the maze

in a suitable data structure. A two-dimentional array will suffice.

E.g.

  char maze[100][100];

or

  int maze[100][100];

 

Storing the array as 'int' instead of 'char' takes up more

memory (usually char=1 byte, int=4 bytes) but a char can only

store values between 0 and 255.

 

We will use an 'int' array for this solution.

Again, dynamic programming will be used; we will calculate a very

simple piece of knowledge and reuse this knowledge to find our

solution.

 

But first, I will show another possible solution.

You could try all possible paths and store the length of

the shortest path.

 

A simple recursive algorithm is shown below. 'Simple', meaning

very short to write but recursion is a difficult concept to

grasp for beginners.

Also important is the order of your indices into an array:

e.g. are you going to use maze[y][x] or maze[x][y],

ake sure you remain consistant in your code.

 

void findpath(int x, int y, int length) {

  if ((x<0) || (y<0) || (x>=width) || (y>=height))

    return;

  if (maze[y][x] == 'E') {

    if (length < minlength)

      minlength = length;

    return;

  }

  if (maze[y][x] != '-')

    return;

 

  maze[y][x] = '.'; // Leave a mark to show I've been here

  findpath(x,y-1,length+1);  // up

  findpath(x-1,y,length+1);  // left

  findpath(x,y+1,length+1);  // down

  findpath(x+1,y,length+1);  // right

  maze[y][x] = '-'; // remove mark

}

 

 

to find the minimum path length:

 

minlength = 32000; // no path can be as long as this

mazy[sy][sx] = '-'; // Replace the 'S' character with '-'

findpath(sx,sy,0);

 

 

This should try every possible path. Because of this, it will be very

slow. It is a good, quick solution for small mazes.

 

 

 

Dynamic programming solution:

 

 

Given the map below:

--X-XXX-X--XXXX--

--X-----X---X----

--X-X---XXXX---E-

S-X-X--X---------

----X-----X------

----XXX---X------

----------X------

 

It's easy to calculate the distance to the End from

certain squares; the ones right beside it

  --X-XXX-X--XXXX--

  --X-----X---X--1-

  --X-X---XXXX--1E1

  S-X-X--X-------1-

  ----X-----X------

  ----XXX---X------

  ----------X------

It takes one step to get to the end from these squares.

 

Using this knowledge, we can find the distance to the

end for other squares; the ones beside the squares that are

one step away

  --X-XXX-X--XXXX2-

  --X-----X---X-212

  --X-X---XXXX-21E1

  S-X-X--X------212

  ----X-----X----2-

  ----XXX---X------

  ----------X------

 

Continuing in this way, we fill the grid

  --X-XXX-X--XXXX23

  --X-----X---X3212

  --X-X---XXXX321E1

  S-X-X--X-----3212

  ----X-----X---323

  ----XXX---X----3-

  ----------X------

 

etc...

  --X-XXX-X--XXXX23

  --X-----X---X3212

  --X-X---XXXX321E1

  S-X-X--X876543212

  ----X---98X654323

  ----XXX--9X765434

  ----------X876545

 

The basic algorithm is:

  For each square,

    look at the four squares north,south,east and west of it

    if any of them have values in them (i.e. not just a '-')

    pick the smallest value, add one, and set the value of this

    square to that number.

 

Eventually, the grid will be filled and each square will contain

the minimum number of steps from it to the end. To get the solution,

just look at the value stored in the starting square.

 

It is important to have a system of storing the 'X' squares. You

could store them as -1 values for instance.

 

Quick Algorithm:

  read in the grid:

    store 'E' as zero (zero distance to the end)

    store '-' as -2 (unknown value)

    store 'S' as -2 but remember its location (store coordinates in sx,sy)

    store 'X' as -1 (trap)

 

  run the basic algorithm as above until no change as made to the array

  (i.e. until the grid is filled)

 

  return map[sy][sx];