1. Finding a shortest path

For this assignment, you are to write a program that finds a shortest path through a two-dimensional world partially filled by obstacles. The input to your program will be a map, with one character marking each position in the world, that shows where the obstacles and possible starting and ending locations are. To make allocating storage easier, the line before the actual map text will contain the height and width of the map.

Here is an example of a small map:

4 6
#&  ##
## #$#
#  ###
#@  ##

The meaning of each position on the map is represented by a character. The rules are:

So in the map above, the starting location is the @ near the lower left-hand corner, the goal is the $ near the upper right-hand corner, and there are a lot of walls (represented by # symbols) and an immovable gigantic statue (represented by the &) that get in our way.¹

To move from the start to the finish, you can make king's moves—a move from one square to any of the eight squares that are next to it either orthogonally or diagonally. You can only move through squares that are empty, i.e., squares represented by spaces in the input.

The output of your program should reproduce the original map with a shortest path from a starting location to a target location marked with '*' characters. For example, the output of the program for the small map above might look like:

#& *##
##*#$#
# *###
#@  ##

or like:

#& *##
##*#$#
#* ###
#@  ##

This map happens to have two shortest paths. It doesn't matter which one you pick.

2. Complications

It is possible for a map to have more than one starting location or target location:

4 6
What$a
rotten
map@ $
@    . 

This map has two @'s and two $'s. In this case, you should find the two-step path in the middle, instead of picking a longer path:

What$a
rotten
map@*$
@   ! 

It may also be that there are no sources, no targets, or no path between any source and target. In this case your program should reprint the map without drawing a path on it.

Finally, it is also possible that your input will be bad in some way. For example, it may be that the width and height fields don't make sense (-1 3), that some of the lines in the map are the wrong length, that you there are the wrong number of lines. For inputs that don't meet the requirements, your program should print a message explaining the problem to stderr and exit with a nonzero exit code.

Clarification added 2012-02-01: The specific requirements for width and height are that they be non-negative (zero is OK).

Be careful about the edges of the map. Since C doesn't do bounds checking on arrays, you will need to make sure yourself that you don't attempt to move to or look at locations that are off the edge.

3. Algorithm suggestions

There are many ways to compute shortest paths (see ShortestPath for some very old notes from CS365). Since this is not an algorithms course, we will offer a suggested algorithm that is chosen for ease of implementation.² Other choices for the algorithm are possible, but whatever code you use should be your own.

The basic idea is to keep around a distance estimate for each position in the map, which is guaranteed to be greater than or equal to the actual distance to the nearest starting position. For '@' positions, this will be 0; for anything else, this will be some huge integer value (e.g., INT_MAX defined in <limits.h>). So starting with the map

4 6
#&  ##
## #$#
#  ###
#@  ##

the initial distance array might look like

∞∞∞∞∞∞
∞∞∞∞∞∞
∞∞∞∞∞∞
∞0∞∞∞∞

Now carry out a sequence of steps where you check for locations at distance x that have neighbors whose distance is more than x+1; if you find such a neighbor (and it's not blocked by an obstacle), you can reduce its distance to x+1. A couple of steps of this process might produce intermediate values like:

∞∞∞∞∞∞
∞∞∞∞∞∞
∞11∞∞∞
∞01∞∞∞

∞∞∞∞∞∞
∞∞2∞∞∞
∞11∞∞∞
∞012∞∞

∞∞33∞∞
∞∞2∞∞∞
∞11∞∞∞
∞012∞∞

∞∞33∞∞
∞∞2∞4∞
∞11∞∞∞
∞012∞∞

Eventually the distances will stop changing. When they do, look for the target location with the smallest distance, and then trace back the decreasing distances until you find the nearest starting location.

If you use this algorithm, you will need some way to represent the input and the array of distances. You should feel free to do whatever works for this, but natural choices would be C99 variable-length arrays or classic C-style two-dimensional arrays built using malloc (see C/Pointers).

If for some reason you find yourself tempted to implement a more efficient algorithm, and bearing in mind that there is absolutely no good reason for you to do so, the program /c/cs223/Hwk3/make_long_path can be used to generate arbitrarily huge maps for testing your program. Typical useage would be /c/cs223/Hwk3/make_long_path 50 | time ./findpath > /dev/null, where the 50 is a parameter controlling the size of the map, time is a program that prints the running time of a command to stderr, and > /dev/null throws away the huge output of ./findpath. The default size parameter for make_long_path is 100, which will probably make a straightforward implementation of findpath run long enough to be annoying but not long enough to make your computer unusable.

4. Valgrind

If you use malloc and free for this assignment, you should check that your program produces no errors when run with the /c/cs223/bin/vg script. (The test script may also check for this.)

5. Submitting your assignment

Submit your file findpath.c using /c/cs223/bin/submit 3 findpath.c as usual. You may run the public test script /c/cs223/Hwk3/test.findpath on your submission using /c/cs223/bin/testit 3 findpath.

6. Sample solutions

Here is a version that uses variable-length arrays:

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <limits.h>
   4 
   5 /* map symbols */
   6 #define START_CHAR ('@')   /* starting position */
   7 #define END_CHAR ('$')     /* target position */
   8 #define OPEN_CHAR (' ')    /* space we can move through */
   9 #define PATH_CHAR ('*')    /* used to mark shortest path */
  10 
  11 #define INFINITY (INT_MAX-1)  /* -1 avoids complications of adding 1 */
  12 
  13 int
  14 main(int argc, char **argv)
  15 {
  16     int width;    /* width of map */
  17     int height;   /* height of map */
  18 
  19     if(scanf("%d %d", &height, &width) != 2) {
  20         fprintf(stderr, "File does not start with width and height\n");
  21         exit(1);
  22     }
  23     /* fetch the newline too */
  24     if(getchar() != '\n') {
  25         fprintf(stderr, "Newline not found where expected after header line\n");
  26         exit(1);
  27     }
  28 
  29     /* use C99 VLA */
  30     char map[height][width];
  31 
  32     int c;     /* input character for reading map */
  33 
  34     for(int i = 0; i < height; i++) {
  35         for(int j = 0; j < width; j++) {
  36             c = getchar();
  37             if(c == EOF || c == '\n') {
  38                 fprintf(stderr, "Incomplete map at line %d position %d\n", i, j);
  39                 exit(2);
  40             }
  41             /* else */
  42             map[i][j] = c;
  43         }
  44         if(getchar() != '\n') {
  45             fprintf(stderr, "Newline not found where expected at line %d\n", i);
  46             exit(3);
  47         }
  48     }
  49 
  50     /* shortest-path algorithm as described in assignment */
  51     int dist[height][width];
  52 
  53     /* initialize to INFINITY or 0 as appropriate */
  54     for(int i = 0; i < height; i++) {
  55         for(int j = 0; j < width; j++) {
  56             if(map[i][j] == START_CHAR) {
  57                 dist[i][j] = 0;
  58             } else{
  59                 /* -1 avoids special-case testing when we add 1 */
  60                 dist[i][j] = INFINITY;
  61             }
  62         }
  63     }
  64 
  65     /* update distances until none change */
  66     int changed;
  67     do {
  68         changed = 0;
  69 
  70         for(int i = 0; i < height; i++) {
  71             for(int j = 0; j < width; j++) {
  72                 if(map[i][j] != OPEN_CHAR && map[i][j] != END_CHAR) {
  73                     /* skip this location */
  74                     continue;
  75                 }
  76 
  77                 /* scan through neighborhood */
  78                 for(int ii = i-1; ii <= i+1; ii++) {
  79                     if(ii < 0 || ii >= height) {
  80                         /* skip row of neighbors */
  81                         continue;
  82                     }
  83 
  84                     /* else*/
  85 
  86                     for(int jj = j-1; jj <= j+1; jj++) {
  87                         if((ii == i && jj == j) || jj < 0 || jj >= width) {
  88                             /* skip this neighbor */
  89                             continue;
  90                         }
  91                         /* else */
  92                         if(dist[ii][jj] + 1 < dist[i][j]) {
  93                             /* we have an improvement */
  94                             dist[i][j] = dist[ii][jj] + 1;
  95                             changed = 1;
  96                         }
  97                     }
  98                 }
  99             }
 100         }
 101     } while(changed);
 102 
 103     /* find coords of closest target */
 104     int best = INFINITY;
 105     int besti;
 106     int bestj;
 107 
 108     for(int i = 0; i < height; i++) {
 109         for(int j = 0; j < width; j++) {
 110             if(map[i][j] == END_CHAR && dist[i][j] < best) {
 111                 best = dist[i][j];
 112                 besti = i;
 113                 bestj = j;
 114             }
 115         }
 116     }
 117 
 118     /* only fill in path if it exists */
 119     if(best < INFINITY) {
 120         /* fill in path back to source */
 121         while(dist[besti][bestj] > 0) {
 122             /* find closer neighbor */
 123             for(int ii = besti - 1; ii <= besti + 1; ii++) {
 124                 if(ii < 0 || ii >= height) {
 125                     continue;
 126                 }
 127                 for(int jj = bestj - 1; jj <= bestj + 1; jj++) {
 128                     if(jj < 0 || jj >= width) {
 129                         continue;
 130                     }
 131                     if(dist[ii][jj] < dist[besti][bestj]) {
 132                         /* got it */
 133                         if(map[ii][jj] != START_CHAR) {
 134                             /* rewrite as PATH_CHAR */
 135                             map[ii][jj] = PATH_CHAR;
 136                         }
 137                         besti = ii;
 138                         bestj = jj;
 139                         goto found_neighbor;
 140                     }
 141                 }
 142             }
 143         found_neighbor:
 144             ;
 145         }
 146     }
 147 
 148     /* print the map */
 149     for(int i = 0; i < height; i++) {
 150         for(int j = 0; j < width; j++) {
 151             putchar(map[i][j]);
 152         }
 153         putchar('\n');
 154     }
 155 
 156     return 0;
 157 }

And here is a version that uses malloc: findpath_malloc.c.