CSC 161 Schedule Readings Labs & Projects Homework Deadlines Resources

Maze Solving

Summary
You search a maze for an optimal path to the goal.
Objectives
  • Practice using
    • structures,
    • dynamic memory allocation,
    • linked lists, and
    • queues
  • Reinforce knowledge of arrays and pointers
  • Improve code-reading skills

Introduction

Both dynamic programming (which you'll study in CSC 301) and divide-and-conquer, (which you saw in CSC 151, with merge sort and binary search) are examples of general families of algorithmic approaches. Another family of algorithms involves graph traversal, in which an algorithm "travels" the connections (or edges) between nodes (or vertices) in a graph (or network). In this assignment, you will use a specific graph traversal algorithm called breadth first search to find a shortest solution to a maze.

The algorithm for maze solving involves marking locations that have already been visited and using a queue to keep track of partial maze solutions traversed so far. To get the complete maze solution, the queue stores not just a position to visit, but the entire shortest path tracing back from that position to the starting position.

Overview

The basic strategy proceeds as follows. Begin by enqueueing a path containing just the start position. Then, as long as the queue is not empty, you dequeue a path and see whether that path ends with the goal state. If it does, you're done! (Well, you still need to print the path from the start to the end.) If the dequeued path does not end with the goal state, you

You'll repeat this process until the queue is empty (meaning no solution to the maze was found), or the dequeued path indeed ends at the goal position.

In a grid, the neighbors will be to the north, south, east, and west. However, some of those locations may be blocked by a wall, so they should only be enqueued for later consideration if they are in fact open.

Implementing the path-finding algorithm will require libraries to maintain a list of positions (the path) and a list-based queue of such paths. You must develop a list-based queue with the operations necessary for this problem using a separate headers and implementation files, using a Makefile to link the various objects.

Your driver program solve.c should therefore:

In addition to implementing the library functions specified in the path.h and queue.h headers below, you are strongly encouraged to decompose the tasks in your driver program into smaller functions.

Details

Code

The sections below elaborate on the following starter codes:

Path: A List of Positions

Your program will accumulate partial solutions via the linked list type detailed in path.h. To conserve memory, the paths with partial solutions in common will use the same nodes. That is, when a new position is added to a partial solution, that position will belong to a new node that points to the first node in the existing solution. Other nodes may also point to the same node.

Though you likely did not know it, this behavior is analogous to what happens behind the scenes in Scheme when you built lists. For example: 

(define singleton (cons 'a null))
(define list-one  (cons 'b singleton))
(define list-two  (cons 'c singleton))

Each call to cons builds a pair (node) whose car (data item field) is the first parameter and cdr (next pointer field) is the second parameter. Thus, the pairs (nodes) at the front of both list-one and list-two each point to the one pair (node) of the one-item list singleton, as shown in the following illustration:

Shared Node Among Two Linked Lists
Shared Node Among Two Linked Lists

Correctly managing memory for such a complicated set of references is beyond the scope of this assignment. Thus, while your path list will certainly be required to allocate memory for additions (the list_add function acts as an exact analogue to cons, you will not be required to free the memory in a multiply linked list. We will instead rely on the operating system's ability reclaim memory allocated to your program upon its termination.

That said, for completeness you must still implement the method to release all the allocated memory for a singly-linked list. However, you should not attempt to use that routine in your eventual solver.

Queue of Paths

The maze traversal is managed by storing paths in a queue. Because newly augmented paths are added at the end of the queue, dequeued paths are necessarily the shortest.

The header queue.h details the operations that must be implemented. The queue must operate without leaking memory. Note that only the pointer given is stored in the queue, thus it is not responsible for managing any memory associated with the path, only the memory for the queue itself.

Maze Data Type

Maze positions are represented with the position_t data type holding a row/column pair.

The maze_t data type stores the maze dimensions, start and end positions, and a one-dimensional array representing the 2D grid of cells. Each cell_t in the array can be one of several values (OPEN, BLOCKED, VISITED, START, and END). To get the value at position, use the offset function. For example, 

maze->cells[offset(maze,position)];

Coordinates are the same as in Pictures and 2D arrays; the upper-left cell is at position (0,0), with rows and columns increasing downward and to the right.

Input

Your program solve.c will accept a maze in the format described below via "standard input" (aka the terminal). The task of reading such input can be somewhat tedious, so this capability is provided for you. (Plus, it is essential practice in learning to read documentation to use others' code.)

The code 

 maze_t * maze = readMaze(stdin);

would allow you to invoke your program on a maze file via input redirection, as follows: 

./solve < maze.txt

Rather than type the contents of the maze manually into the terminal, the contents of the file maze.txt are directed to the terminal as the input. Any other filename is possible as well.

When you need to invoke the debugger, you can do so with the same technique at the GDB command prompt (rather than the terminal); give the input redirection option to the run command of GDB.

Thus, you'd first start the debugger: 

gdb solve

Then within the debugger (perhaps after you've set whatever breakpoints you wish), you'd start the process: 

run < maze.txt

Maze File Format

The first line of a maze file should be the dimensions of the grid—two positive integers, representing the height and width, respectively.

The maze grid is given next. It will consist of an H×W matrix of characters, where

Here are two moderate examples: 
13 41
*********************S*******************
*   *       *         *                 *
*** * *** *** ******* * ******* * ***** *
*   *   *     *   *   *   *   * * *   * *
* * *** ******* * * ***** *** * * * * ***
* *   * *       *   *   *   * * * * *   *
* * *** * *********** * *** * * * * *** *
* * *   *     *     * *   *   * * *   * *
* * * ******* * *** * * ***** * * *** ***
* * * *     * * * *   *     * * * *   * *
* *** *** * * * * ******* *** * *** *** *
*         * *           *     *         *
*********************E*******************
10 20
####################
#S#       #E   #   #
# ####### #### # # #
#         #  # ### #
##### ### #        #
#   # #   ####### ##
#   # # ### #   #  #
#   # # #   # # ## #
#     #   #   #    #
####################
Maze from Figure 9.8 (p. 232) in Java Structures (McGraw-Hill) by Duane A. Bailey.

The amaze.c code above provides a program that will automatically generate random mazes, with a little follow-up manual annotation required.

Output

The output should be the sequence of positions beginning at the start, and ending at the goal location, one per line, with row and column column separated. (Be sure to include a newline on each line, including the final line).

For example, if the file short2.txt contains the following maze: 

5 5
#S###
#   #
## ##
#   #
#E###

The only optimal solution would be: 

solve < short2.txt
0,1
1,1
1,2
2,2
3,2
3,1
4,1

Note that some mazes might have several optimal shortest paths, depending on the order you visit the neighbors. Your solution only needs to produce any one of them.

If a maze has no solution, your program should produce no output.

Here are various mazes to try:

Specifications

Grading

In addition to the general grading guidelines for evaluation, the assignment is worth 30 points.

Creative Commons License Copyright © 2017, 2019, 2021 Jerod Weinman. This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International license.
Validate HTML