Media > The Binary Cafe'

My Final Exam

(1/2) > >>

Jeod:
For my computer science class, my final exam is a pretty difficult program (for my level of C experience anyway)

Solve the following 20x10 maze using an algorithm:


--- Code: ---####################
##  #    ##    ### #
## # ###     #     #
#  # # ##### #######
# ## #    ## #    ##
# ## #### ## #### ##
# ##      ## ####  E
# ## #### ## #### ##
#    ####         ##
#S##################

--- End code ---

The maze will be preset and not brought in as input. The solver should start as S and try to find a way to E. The program should mark the path it is
taking and also mark the paths that were incorrect.

Symbols:

# - Indicates a wall
' ' - Whitespaces, indicate paths
S - Indicates start position
E - Indicates end position
o - Indicates solver
+ - Indicates incorrect path

The program should redraw the maze each time the solver takes a new step. In the solution, show a clean maze with a solution path that the solver found. The program should have a main() function and at least one other function. You must also use arrays to store the maze. The masze must be solved in an algorithm. Do not simply hardcode print statements. Use pointers for moving around the maze. Do not use subscription or indexing techniques.

I've come to a point where I have to ask for assistance. I have no clue how to program this.

xfixium:
You definitely need an array to hold the maze. A 2d one is easier to visualize. As for path finding, I'd look into these:

A* Pathfinding
http://www.policyalmanac.org/games/aStarTutorial.htm

Flood Filling: (Might be useful)
http://en.wikipedia.org/wiki/Flood_fill

Jeod:
Okay, I understand a bit of the pathfinding, but how am I supposed to store the maze in an array and call it properly? It'll be a pretty long list (200 slots actually) to store each character of the maze. Is there an easier way to start off?

Jeod:

--- Code: ---/*
Solve the following 20x10 maze using an algorithm:

####################
##  #    ##    ### #
## # ###     #     #
#  # # ##### #######
# ## #    ## #    ##
# ## #### ## #### ##
# ##      ## ####  E
# ## #### ## #### ##
#    ####         ##
#S##################

The maze will be preset and not brought in as input. The solver should start as S and try to find a way to E. The program should mark the path it is
taking and also mark the paths that were incorrect.

The program should redraw the maze each time the solver takes a new step. In the solution, show a clean maze with a solution path that the solver found.
The program should have a main() function and at least one other function. You must also use arrays to store the maze. The masze must be solved in an
algorithm. Do not simply hardcode print statements. Use pointers for moving around the maze. Do not use subscription or indexing techniques.
*/

#include <stdio.h>
#include <iostream>

#define FALSE 0
#define TRUE 1

// Symbols:
// '.' = open
// '#' = wall
// 'S' = start
// 'E' = end
// '+' = path
// 'x' = bad path
char* maze[20][10] = {
"####################",
"##.#.....##....###.#",
"##.#.###.....#.....#",
"#..#.#.#####.#######",
"#.##.#....##.#....##",
"#.##.####.##.####.##",
"#.##......##.####..E",
"#.##.####.##.####.##",
"#....####.........##",
"#S##################"
};


void display_maze(void);
int find_path(int x, int y);


int main(void)
{
display_maze();

if ( find_path(0, 0) == TRUE )
printf("Success!\n");
else
printf("Failed\n");

display_maze();

system("pause");
}

void display_maze(void)
{
int i;

printf("MAZE:\n");
for ( i = 0; i < 20; i++ )
printf("%.*s\n", 10, maze[i]);
printf("\n");

return;
}


int find_path(int x, int y)
{
// If x,y is outside maze, return false.
if ( x < 0 || x > 9 || y < 0 || y > 19 ) return FALSE;

// If x,y is the goal, return true.
if ( *maze[y][x] == 'E' ) return TRUE;

// If x,y is not open, return false.
if ( *maze[y][x] != '.' && *maze[y][x] != 'S' ) return FALSE;

// Mark x,y part of solution path.
*maze[y][x] = '+';

// If find_path North of x,y is true, return true.
if ( find_path(x, y - 1) == TRUE ) return TRUE;

// If find_path East of x,y is true, return true.
if ( find_path(x + 1, y) == TRUE ) return TRUE;

// If find_path South of x,y is true, return true.
if ( find_path(x, y + 1) == TRUE ) return TRUE;

// If find_path West of x,y is true, return true.
if ( find_path(x - 1, y) == TRUE ) return TRUE;

// Unmark x,y as part of solution path.
*maze[y][x] = 'x';

return FALSE;
}

--- End code ---

It doesn't work. Why?

xfixium:
What doesn't work about it?

Navigation

[0] Message Index

[#] Next page