This assignment will focus on the use of the following.
system("ls *.mze > filesxyz.abc"); // dumps listing into file
infile.open("filesxyz.abc"); // opens file containing filenames
while (infile >> fname) // read a filename
fnamelist.push_back(fname); // push it on the list
infile.close();
system("rm filesxyz.abc"); // get rid of temp file
The program will have a main loop that (1) displays a menu with the options listed above, (2) gets the users choice, and (3) calls procedures or functions to perform the selected option.
The rectangular (M x N) array of characters representing the maze is stored in a text file on M + 1 lines. The first line has two integers, M (the number of rows) and N (the number of columns). Each of the next M lines of the file has N characters on it. Each character represents the nature of a position in the maze. The characters used in the initial maze are ...
'0' -- Empty unsearched maze position '1' -- Wall '*' -- Starting position '$' -- Goal
Additional characters used during the maze search are ...
'?' -- Current position in the maze (display only)
'~' -- Positions seen (e.g., search has visited an adjacent position)
and stacked for future search, if necessary. This marker helps
prevent attempts to visit a place more than once.
'#' -- Positions searched but which lead to a dead end
'+' -- Positions searched that are still part of the path to exit
(note that the start ('*') and the goal ('$') are left
unchanged
A sample 5 x 8 maze is shown below. It assumes a search strategy of right, then left, then up, then down (discussed more below). I suggest that you store the maze in rows 1..M and columns 1..N in a character matrix that has indices 0..M+1, 0..N+1. That way you can surround the actual maze with a border of '1's. That is, put a wall around it. The outer wall will eliminate some of the special cases that otherwise will have to be dealt with in the StackPossibles procedure below. When you display the maze, show the outer wall BUT DO NOT SAVE THE OUTER WALL AS PART OF THE MAZE IN THE FILE.
FILE FORMAT BEFORE SEARCH DURING SEARCH AFTER SEARCH
5 8 1111111111 1111111111 1111111111
1101$011 11101$0111 11101$0111 11101$0111
00010010 1000100101 10?+100101 1###1+X101
01000110 1010001101 101+++11#1 1#1##+11#1
0111*000 10111*0001 10111*###1 1#111*###1
11000111 1110001111 1110001111 1110001111
1111111111 1111111111 1111111111
PATH -- (4,5)(3,5)(2,5)(1,5)
The maximum maze size will be unrestricted. The display area on the screen will be in the upper left of the screen. This area will be a boxed subwindow within which at least a 20x20 region of the maze will be displayed. Initial display will be the upper left area of the maze. As soon as the start is found by the searcher object, the display should be shifted to show the start centered somewhere on the display. As the search progresses, whenever the next location would take it off of the display, the maze display should be shifted to center the searcher's position.
The Menu I/O will take place on the right half of the screen in a boxed subwindow.
The maze file name selection I/O will take place in the upper left of the screen in a boxed subwindow.
The path and statistics should be displayed along the bottom of the screen, and should wrap around to be easily read. Something like shown in the example above.
The program name, your name and "CSE 331 - fall 2004" should appear as credits somewhere on the screen and remain there throughout the program execution.
The main menu should remain on the screen throughout the program execution, unless you decide to use a larger maze display area and display some other maze search related information in place of the menu during the search.
You will need to use Ncurses functions, keypad, and subwindows. You are encouraged to be creative (use the mouse and color if you like) BUT do not let the creativity prevent completion of the essentials. See the class web page for links to online references and tutorials.
************************************************ * this Maze Search * * J H Stewman * * area for CSE 331 - fall 2004 * * * * maze display ***************** * * * 1 - Options * * * and * 2 - Load Maze * * * * 3 - Search * * * filename list * 4 - My Search * * * * 5 - Quit * * * ***************** * * * * * ************************************************
The algorithm for the search looks like this ...
set trapped and free to FALSE
Findstart (row,col) { row and column of '*' }
Push (row,col) { save start position on stack }
StackPossibles (row,col) { find initial moves }
WHILE not trapped and not free DO { while not finished }
IF stack is empty THEN { no more places to move }
set trapped to TRUE { set flag to quit }
ELSE { more places to move }
Pop (row,col) { get next move }
If not at start or finish
Show '?' at position (row,col) { show that we are here }
delay 1/4 second
CASE maze[row,col] OF { where are we? }
'*' -- set maze[row,col] to '*' { we are back at start }
'$' -- set maze[row,col] to '$' { we are at goal }
Push (row,col) { save present position }
set free to TRUE { set flag to quit }
'~','0' -- set maze[row,col] to '+' { we are moving forwards }
show '+' at position (row,col)
Push (row,col) { save position }
StackPossibles (row,col) { find other moves }
'+' -- set maze[row,col] to '#' { we are backing up }
show '#' at position (row,col)
ENDCASE
ENDWHILE
IF trapped THEN
write trapped message
ELSE
write out path (from stack) recursively
The simplest algorithm for StackPossibles (row,col) looks like this ...
IF maze[row+1,col] in ['~','0','$'] THEN
Push (row+1,col) { save move down }
IF maze[row-1,col] in ['~','0','$'] THEN
Push (row-1,col) { save move up }
IF maze[row,col-1] in ['~','0','$'] THEN
Push (row,col-1) { save move to left }
IF maze[row,col+1] in ['~','0','$'] THEN
Push (row,col+1) { save move to right }
One more word about the use of the stack. Each stack entry should be a pair
of integers representing the row and column of a position. At any given
moment in the search, the stack contains all of the positions along the
partially completed path and all of the moves not taken at points in the
search where there were choices. When a dead end is encountered the stack
diminishes as the search backtracks to a position where there was a choice.
The search begins moving forward again when the maze at a position just
removed from the stack is '~', '0' or '$'. As long as the maze at the
current position is '+' or '*' we are backing up, looking for a move we did
not take before.
At the end of the search, the positions on the stack that have maze entries '*', '+' and '$' are the positions in the final path. Any others are first steps on paths that we never explored. The path is in the stack backwards, however, so you need to recursively process the stack (or use a second stack ) to print out the (row,col) pairs indicating the forward path (from '*' to '$').