Author Topic: My Final Exam  (Read 20977 times)

0 Members and 1 Guest are viewing this topic.

Offline Jeod

  • Full Member
  • ***
  • Posts: 128
  • Karma: +2/-2
  • Gender: Male
My Final Exam
« 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:

Code: [Select]
####################
##  #    ##    ### #
## # ###     #     #
#  # # ##### #######
# ## #    ## #    ##
# ## #### ## #### ##
# ##      ## ####  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.
« Last Edit: November 29, 2010, 02:39:58 PM by Jeod »
Quote
A fangame is no less a game than the game it was based off of. If the fangame is decent or even better than that which it was based off of, then it is a game in its own right. It is a work of art created by a developer just like the original, despite being a derivative work.

Offline xfixium

  • Spanker of Mon-key-keyz
  • Administrator
  • Hero Member
  • *****
  • Posts: 706
  • Karma: +23/-23
  • Gender: Male
    • Pyxosoft
Re: My Final Exam
« Reply #1 on: November 29, 2010, 03:52:16 PM »
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

Offline Jeod

  • Full Member
  • ***
  • Posts: 128
  • Karma: +2/-2
  • Gender: Male
Re: My Final Exam
« Reply #2 on: November 30, 2010, 12:35:00 PM »
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?
Quote
A fangame is no less a game than the game it was based off of. If the fangame is decent or even better than that which it was based off of, then it is a game in its own right. It is a work of art created by a developer just like the original, despite being a derivative work.

Offline Jeod

  • Full Member
  • ***
  • Posts: 128
  • Karma: +2/-2
  • Gender: Male
Re: My Final Exam
« Reply #3 on: December 02, 2010, 01:51:23 PM »
Code: [Select]
/*
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?
Quote
A fangame is no less a game than the game it was based off of. If the fangame is decent or even better than that which it was based off of, then it is a game in its own right. It is a work of art created by a developer just like the original, despite being a derivative work.

Offline xfixium

  • Spanker of Mon-key-keyz
  • Administrator
  • Hero Member
  • *****
  • Posts: 706
  • Karma: +23/-23
  • Gender: Male
    • Pyxosoft
Re: My Final Exam
« Reply #4 on: December 02, 2010, 02:52:10 PM »
What doesn't work about it?

Offline xfixium

  • Spanker of Mon-key-keyz
  • Administrator
  • Hero Member
  • *****
  • Posts: 706
  • Karma: +23/-23
  • Gender: Male
    • Pyxosoft
Re: My Final Exam
« Reply #5 on: December 02, 2010, 03:41:24 PM »
I see your problem, your array doesn't hold separate elements.

Code: [Select]
#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:

Code: [Select]
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....
« Last Edit: December 02, 2010, 04:11:30 PM by xfixium »

Offline Jeod

  • Full Member
  • ***
  • Posts: 128
  • Karma: +2/-2
  • Gender: Male
Re: My Final Exam
« Reply #6 on: December 02, 2010, 05:26:18 PM »
Code: [Select]
/*
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.
Quote
A fangame is no less a game than the game it was based off of. If the fangame is decent or even better than that which it was based off of, then it is a game in its own right. It is a work of art created by a developer just like the original, despite being a derivative work.