Maze Traversal

Question

rfrapp 17 Junior Poster in Training

11 Years Ago

I'm writing maze traversal for a school assignment, and I've got an issue. The X will move through most of the maze, but then it will get stuck at a position and keep cycling through. This is probably because I'm not checking properly to see if it hasn't been to a spot already. Here's my code:

/*
Name: Ryan Frappier
Date: 
Program: Recursively moves an X 
through a maze



Signature:____________________
*/

#include "stdafx.h"
#include <iostream>

using namespace std;

void printArray(char*[12], int);
void mazeTraverse(char*[12], int, int, int, int);

int _tmain(int argc, _TCHAR* argv[])
{
    // array of pointers
    char *maze[12];

    // Sets each element to a pointer based array
    for (int i = 0; i < 12; i++)
        maze[i] = new char[12];

    for (int y = 0; y < 12; y++)
    {
        for (int x = 0; x < 12; x++)
        {
            maze[y][x] = ' ';
        }
    }

    for (int col = 0; col < 12; col++)
    {
        for (int row = 0; row < 12; row++)
        {
            (*(maze))[col] = '#';
            (*(maze + 11))[col] = '#';
            (*(maze + row))[0] = '#';
            (*(maze + row))[11] = '#';
        }
    }

    (*(maze) + 4)[11] = ' ';
    (*(maze + 3))[1] = '#';
    (*(maze + 3))[2] = '#';
    (*(maze + 2))[2] = '#';
    (*(maze + 1))[4] = '#';
    (*(maze + 2))[4] = '#';
    (*(maze + 3))[4] = '#';
    (*(maze + 5))[1] = '#';
    (*(maze + 5))[2] = '#';
    (*(maze + 5))[3] = '#';
    (*(maze + 6))[3] = '#';
    (*(maze + 7))[3] = '#';
    (*(maze + 7))[1] = '#';
    (*(maze + 9))[1] = '#';
    (*(maze + 9))[2] = '#';
    (*(maze + 9))[3] = '#';
    (*(maze + 9))[4] = '#';
    (*(maze + 9))[5] = '#';
    (*(maze + 7))[5] = '#';
    (*(maze + 6))[5] = '#';
    (*(maze + 5))[5] = '#';
    (*(maze + 4))[5] = '#';
    (*(maze + 5))[7] = '#';
    (*(maze + 6))[7] = '#';
    (*(maze + 7))[7] = '#';
    (*(maze + 2))[6] = '#';
    (*(maze + 2))[7] = '#';
    (*(maze + 2))[8] = '#';
    (*(maze + 2))[9] = '#';
    (*(maze + 3))[9] = '#';
    (*(maze + 4))[9] = '#';
    (*(maze + 5))[9] = '#';
    (*(maze + 6))[9] = '#';
    (*(maze + 7))[9] = '#';
    (*(maze + 8))[9] = '#';
    (*(maze + 9))[9] = '#';
    (*(maze + 9))[8] = '#';
    (*(maze + 9))[7] = '#';
    (*(maze + 10))[7] = '#';
    (*(maze + 4))[6] = '#';
    (*(maze + 4))[7] = '#';

    mazeTraverse(maze, 2, 0, 2, 0);


    system("pause");
    return 0;
}

void mazeTraverse(char *maze[12], int row, int col, int lastRow, int lastCol)
{
    maze[row][col] = 'X';

    printArray(maze, 12);

    system("pause");
    system("cls");

    /* ------------- First try -----------------
    **Move right if the X has a # on the top and bottom
    **Move up if it has a # at the bottom, right, and bottom right
    **Move right if it has a # at the top, left, and top left
    **Move down if it has a # at the top, right, and top right
    **Move down if it has a # at the left and right
     */

    // relative to the position of the X
    char top = maze[row - 1][col];
    char bottom = maze[row + 1][col];
    char left = maze[row][col - 1];
    char right = maze[row][col + 1];
    char diagonalBottomLeft = maze[row + 1][col - 1]; 
    char diagonalBottomRight = maze[row + 1][col + 1];
    char diagonalTopLeft = maze[row - 1][col - 1];
    char diagonalTopRight = maze[row - 1][col + 1];

    // found exit
    if (row == 4 && col == 11)
        return;
    else 
    {

        // move right
        //if (row != lastRow && (col + 1) != lastCol)
        //{
            if (right != '#')
            {
                maze[row][col] = ' ';
                mazeTraverse(maze, row, col + 1, row, col);
            }
        //}

        // move left
        if (row != lastRow && (col - 1) != lastCol)
        {
            if (left != '#')
            {
                maze[row][col] = ' ';
                mazeTraverse(maze, row, col - 1, row, col);
            }
        }

        // move up
        if ((row - 1) != lastRow && col != lastCol)
        {
            if (top != '#')
            {
                maze[row][col] = ' ';
                mazeTraverse(maze, row - 1, col, row, col);
            }
        }

        // move down
        //if ((row + 1) != lastRow && col != lastCol)
        //{
            if (bottom != '#')
            {
                maze[row][col] = ' ';
                mazeTraverse(maze, row + 1, col, row, col);
            }
        //}
    }

}

void printArray(char *maze[12], int size)
{
    for (int x = 0; x < size; x++)
    {
        for (int y = 0; y < size; y++)
        {
            cout << maze[x][y];
        }
        cout << endl;
    }
}

Some of the checks are commented out in the mazeTraverse function because the program would stop sooner if they weren't. I don't really understand why that is. If anyone could help out, that'd be great. Thank you for your time!

c++ maze traverse

1 Contributor
3 Replies
906 Views
1 Hour Discussion Span
Latest Post 11 Years Ago Latest Post by rfrapp

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

rfrapp 17 Junior Poster in Training · Answer 1 · 2013-02-02T16:31:26+00:00

The point of the assignment was also to use pointers, so that's why they're there

rfrapp 17 Junior Poster in Training · Answer 2 · 2013-02-02T17:34:52+00:00

Here's pretty much the same thing. Just made it look nicer.

// MazeTraversal.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

void printArray(char*[12], int);
void mazeTraversal(char*[12], int, int);
bool isValidMove(char*[12], int, int, int, int);

int _tmain(int argc, _TCHAR* argv[])
{
    // array of pointers
    char *maze[12];

    // Sets each element to a pointer based array
    for (int i = 0; i < 12; i++)
        maze[i] = new char[12];

    for (int y = 0; y < 12; y++)
    {
        for (int x = 0; x < 12; x++)
        {
            maze[y][x] = ' ';
        }
    }
    for (int col = 0; col < 12; col++)
    {
        for (int row = 0; row < 12; row++)
        {
            (*(maze))[col] = '#';
            (*(maze + 11))[col] = '#';
            (*(maze + row))[0] = '#';
            if (row != 4)
                (*(maze + row))[11] = '#';
        }
    }
    (*(maze + 3))[1] = '#';
    (*(maze + 3))[2] = '#';
    (*(maze + 2))[2] = '#';
    (*(maze + 1))[4] = '#';
    (*(maze + 2))[4] = '#';
    (*(maze + 3))[4] = '#';
    (*(maze + 5))[1] = '#';
    (*(maze + 5))[2] = '#';
    (*(maze + 5))[3] = '#';
    (*(maze + 6))[3] = '#';
    (*(maze + 7))[3] = '#';
    (*(maze + 7))[1] = '#';
    (*(maze + 9))[1] = '#';
    (*(maze + 9))[2] = '#';
    (*(maze + 9))[3] = '#';
    (*(maze + 9))[4] = '#';
    (*(maze + 9))[5] = '#';
    (*(maze + 7))[5] = '#';
    (*(maze + 6))[5] = '#';
    (*(maze + 5))[5] = '#';
    (*(maze + 4))[5] = '#';
    (*(maze + 5))[7] = '#';
    (*(maze + 6))[7] = '#';
    (*(maze + 7))[7] = '#';
    (*(maze + 2))[6] = '#';
    (*(maze + 2))[7] = '#';
    (*(maze + 2))[8] = '#';
    (*(maze + 2))[9] = '#';
    (*(maze + 3))[9] = '#';
    (*(maze + 4))[9] = '#';
    (*(maze + 5))[9] = '#';
    (*(maze + 6))[9] = '#';
    (*(maze + 7))[9] = '#';
    (*(maze + 8))[9] = '#';
    (*(maze + 9))[9] = '#';
    (*(maze + 9))[8] = '#';
    (*(maze + 9))[7] = '#';
    (*(maze + 10))[7] = '#';
    (*(maze + 4))[6] = '#';
    (*(maze + 4))[7] = '#';

    mazeTraversal(maze, 2, 0);

    system("pause");
    return 0;
}

// takes coordinates of the new move
// and coordinates of the old move
bool isValidMove(char *maze[12], int row, int col, int lastRow, int lastCol)
{
    // if the coordinates are whithin bounds of the array
    if ((row >= 0 && col >= 0) && (row <= 11 && col <= 11))
    {
        // check if the new coordinates are not the same as the old
        // and check if the new coordinate is a space
        if (maze[row][col] == ' ' && (lastRow != row && lastCol != col))
            return true;
    }

    return false;
}

void mazeTraversal(char *maze[12], int row, int col)
{
    maze[row][col] = 'X';

    char left = maze[row][col - 1];
    char right = maze[row][col + 1];
    char top = maze[row - 1][col];
    char bottome = maze[row + 1][col];

    printArray(maze, 12);
    system("pause");

    if (row == 4 && col == 11)
        return;
    else 
    {
        // move right
        if (isValidMove(maze, row, col + 1, row, col))
        {
            maze[row][col + 1] = 'X';
            maze[row][col] = ' ';
            mazeTraversal(maze, row, col + 1);
        }

        // move up
        if (isValidMove(maze, row - 1, col, row, col))
        {
            maze[row - 1][col] = 'X';
            maze[row][col] = ' ';
            mazeTraversal(maze, row - 1, col);
        }

        // move down
        if (isValidMove(maze, row + 1, col, row, col))
        {
            maze[row + 1][col] = 'X';
            maze[row][col] = ' ';
            mazeTraversal(maze, row + 1, col);
        }

        // move left
        if (isValidMove(maze, row, col - 1, row, col))
        {
            maze[row][col - 1] = 'X';
            maze[row][col] = ' ';
            mazeTraversal(maze, row, col - 1);
        }
    }
}

void printArray(char *maze[12], int size)
{
    system("cls");
    for (int y = 0; y < size; y++)
    {
        for (int x = 0; x < size; x++)
        {
            cout << maze[y][x];
        }
        cout << endl;
    }
}

rfrapp 17 Junior Poster in Training · Answer 3 · 2013-02-02T17:35:39+00:00

rfrapp 17 Junior Poster in Training

11 Years Ago

It just doesn't move at all on the second one