You are viewing our Forum Archives. To view or take place in current topics click here.
[C++] Maze Solving Program
Posted:

[C++] Maze Solving ProgramPosted:

Experiment5X
  • TTG Senior
Status: Offline
Joined: Aug 14, 200915Year Member
Posts: 1,291
Reputation Power: 65
Status: Offline
Joined: Aug 14, 200915Year Member
Posts: 1,291
Reputation Power: 65
So awhile back someone on XboxMB (I think it was dcskill) posted a programming problem where you had to solve a maze recursively. I couldn't figure it out when he posted it, but recently I went back to it out of boredom and figured it out. This program will allow the user to enter the path to a maze file (a text file) and then my program will read it and tell you if the maze is solvable, and if it is, it will give you instructions on how to get to the goal. The structure of the maze file is as follows:


  • The first line needs to be the width of the maze
  • The second line needs to be the height of the maze
  • The rest of the file needs to be the maze itself, where S is the start, _ is a place where the player can walk, and G is the end or goal of the maze


[ Register or Signin to view external links. ]

If you're too lazy to download the source, here is the code


#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

struct Point
{
   Point(int _x, int _y) : x(_x), y(_y) { }

   int x, y;
};

enum Direction { Up, Down, Right, Left, None };

bool solveMaze(char **maze, Point point, Direction dir, string &instructions, int height, int width);
void doStuff(string &s, string toAdd);
void doFoundGoalStuff(string &instructions, string dir);

int main()
{
   int width, height;

   printf("Enter the path to a maze file...\n");
   char filePath[100];
   cin.getline(filePath, 100);

   /*
   STRUCTURE FOR MAZE FILE
      -The first line needs to be the width of the maze
      -The second line needs to be the height of the maze
      -The rest of the file needs to be the maze itself, where S is the start,
       _ is a place where the player can walk, and G is the end or goal of the maze
   */

   ifstream reader(filePath, ios::beg);
   string temp;
   getline(reader, temp);
   width = atoi(temp.c_str());
   getline(reader, temp);
   height = atoi(temp.c_str());

   Point p(0, 0);

   char **maze = new char*[height];

   for(int i = 0; i < height; i++)
   {
      maze[i] = new char[width];
      getline(reader, temp);
      for (int j = 0; j < width; j++)
      {
         if (temp[j] == 'S')
         {
            p.x = j;
            p.y = i;
         }
         maze[i][j] = temp[j];
      }
   }

   string s = "";

   if (solveMaze(maze, p, None, s, height, width))
      printf("\n%s\n", s.c_str());
   else
      printf("\nThe maze cannot be solved.\n");
   getchar();
   return 0;
}

bool solveMaze(char **maze, Point point, Direction dir, string &instructions, int height, int width)
{
   //check for up
   if (point.y - 1 >= 0 && dir != Up)
   {
      if (maze[point.y - 1][point.x] == 'G')
      {
         doFoundGoalStuff(instructions,"up");
         return true;
      }
      else if (maze[point.y - 1][point.x] == '_' && solveMaze(maze, Point(point.x, point.y - 1), Down, instructions, height, width))
      {
         doStuff(instructions, "Go up.\n");
         return true;
      }
   }

   //check for down
   if (point.y + 1 < height && dir != Down)
   {
      if (maze[point.y + 1][point.x] == 'G')
      {
         doFoundGoalStuff(instructions, "down");
         return true;
      }
      else if (maze[point.y + 1][point.x] == '_' && solveMaze(maze, Point(point.x, point.y + 1), Up, instructions, height, width))
      {
         doStuff(instructions, "Go down.\n");
         return true;
      }
   }

   //check for left
   if (point.x - 1 >= 0 && dir != Left)
   {
      if (maze[point.y][point.x - 1] == 'G')
      {
         doFoundGoalStuff(instructions, "left");
         return true;
      }
      else if (maze[point.y][point.x - 1] == '_' && solveMaze(maze, Point(point.x - 1, point.y), Right, instructions, height, width))
      {
         doStuff(instructions, "Go left.\n");
         return true;
      }
   }

   //check for right
   if (point.x + 1 < width && dir != Right)
   {
      if (maze[point.y][point.x + 1] == 'G')
      {
         doFoundGoalStuff(instructions, "right");
         return true;
      }
      if (maze[point.y][point.x + 1] == '_' && solveMaze(maze, Point(point.x + 1, point.y), Left, instructions, height, width))
      {
         doStuff(instructions, "Go right.\n");
         return true;
      }
   }

   return false;
}

void doStuff(string &s, string toAdd)
{
   string temp = s;
   s = toAdd;
   s += temp;
}

void doFoundGoalStuff(string &instructions, string dir)
{
   printf("The maze works.");
   doStuff(instructions, string("Go ").append(dir).append(" . You have reached the goal.\n"));
}



[ Register or Signin to view external links. ]
[ Register or Signin to view external links. ]
#2. Posted:
Z61
  • V5 Launch
Status: Offline
Joined: Apr 16, 201014Year Member
Posts: 4,309
Reputation Power: 179
Status: Offline
Joined: Apr 16, 201014Year Member
Posts: 4,309
Reputation Power: 179
Now this right here is pretty bossy.
Jump to:
You are viewing our Forum Archives. To view or take place in current topics click here.