Pyxosoft Game Dev Community
Media => The Binary Cafe' => Topic started by: Jeod on November 29, 2010, 02:38:13 PM
-
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:
####################
## # ## ### #
## # ### # #
# # # ##### #######
# ## # ## # ##
# ## #### ## #### ##
# ## ## #### 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.
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.
-
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
-
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?
-
/*
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;
}
It doesn't work. Why?
-
What doesn't work about it?
-
I see your problem, your array doesn't hold separate elements.
#define COLS 20
#define ROWS 10
// Symbols:
// '.' = open
// '#' = wall
// 'S' = start
// 'E' = end
// '+' = path
// 'x' = bad path
char* maze[ROWS][COLS] = {
{"#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#"},
{"#","#",".","#",".",".",".",".",".","#","#",".",".",".",".","#","#","#",".","#"},
{"#","#",".","#",".","#","#","#",".",".",".",".",".","#",".",".",".",".",".","#"},
{"#",".",".","#",".","#",".","#","#","#","#","#",".","#","#","#","#","#","#","#"},
{"#",".","#","#",".","#",".",".",".",".","#","#",".","#",".",".",".",".","#","#"},
{"#",".","#","#",".","#","#","#","#",".","#","#",".","#","#","#","#",".","#","#"},
{"#",".","#","#",".",".",".",".",".",".","#","#",".","#","#","#","#",".",".","E"},
{"#",".","#","#",".","#","#","#","#",".","#","#",".","#","#","#","#",".","#","#"},
{"#",".",".",".",".","#","#","#","#",".",".",".",".",".",".",".",".",".","#","#"},
{"#","S","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#"},
};
Then if you want to draw the data, you just iterate through the array elements and draw the characters:
void display_maze(void)
{
printf("MAZE:\n");
for (int row = 0; row < ROWS; row++ )
{
printf("\n");
for (int col = 0; col < COLS; col++)
{
std::cout << maze[row][col];
}
}
printf("\n");
}
Will get back to you on the rest....
-
/*
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 <windows.h>
#define FALSE 0
#define TRUE 1
#define COLS 20
#define ROWS 10
// Symbols:
// '.' = open
// '#' = wall
// 'S' = start
// 'E' = end
// '+' = path
// 'x' = bad path
char* maze[ROWS][COLS] = {
"#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#","#",
"#","#",".","#",".",".",".",".",".","#","#",".",".",".",".","#","#","#",".","#",
"#","#",".","#",".","#","#","#",".",".",".",".",".","#",".",".",".",".",".","#",
"#",".",".","#",".","#",".","#","#","#","#","#",".","#","#","#","#","#","#","#",
"#",".","#","#",".","#",".",".",".",".","#","#",".","#",".",".",".",".","#","#",
"#",".","#","#",".","#","#","#","#",".","#","#",".","#","#","#","#",".","#","#",
"#",".","#","#",".",".",".",".",".",".","#","#",".","#","#","#","#",".",".","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");
Sleep(5000);
}
else
{
printf("Failed\n");
display_maze();
}
}
void display_maze(void)
{
printf("MAZE:\n");
for (int row = 0; row < ROWS; row++ )
{
printf("\n");
for (int col = 0; col < COLS; col++)
{
printf("%s", maze[row][col]);
}
}
printf("\n");
}
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;
}
Find_Path is supposed to be the function that solves the maze. It looks for a path, and when it finds one, moves to that spot and marks the spot it was at with a +. It is recursive; the function should repeat itself until it finds the exit. On the chance the function runs into a wall, it should go back to the closest + sign that has a turn and try a new path.