Difficulty with C++

Status
Not open for further replies.
Fawfulfan

Fawfulfan

The Tortured Planet guy
Wow. I've been working on this problem all day, and it's driving me up the wall. I know there are some programmers here, so hopefully you guys can help me out with this.

Anyway, as many of you may know from my posts, I am currently taking my first semester in college. One of my classes is a standard Computer Science course, which is exclusively devoted to C++ programming. I'm slightly more than halfway through it, and it's getting tougher. There are labs twice a week, and quizzes every Monday. Homework is extremely rare (only four projects total), but they can be challenging.

I don't know when it will be given, but I suspect that the second homework is just around the corner, and I've heard that one commonly issued homework assignment in this class is a program that will navigate a maze. Though I don't know if that's the one I'll be getting, I thought I might as well practice and try to write a C++ algorithm for maze navigation on my own.

For a while, it was going pretty well. I have a matrix that produces a hollow, empty chamber onscreen. No maze yet, but I'm trying to work on the algorithm for collision detection and turning. The walls are represented by ones, the empty spaces are zeroes, and the moving character is a two.

Here's my problem. The moving character is supposed to check each of the four adjacent nodes in a clockwise circle--left, up, right, down. It can go left and up perfectly, but whenever it needs to go right or down, it stays put! I've been exploring as many solutions as I can think of, to no avail.

Do you guys think you can have a look at my code and tell me if you have a solution? I have of course commented each function and the more crucial blocks of code within them.

Code: 
#include <iostream>
#include <Windows.h>
using namespace std;

//PURPOSE: Specify a structure of walls, empty spaces, and place
//the start and exit points.
void construct(int maze[20][20])
{
    //start point
    maze[19][9] = 2;
    //exit point
    maze[0][10] = 0;
}

//PURPOSE: Create walls around every edge of the maze.
void initialize(int maze[20][20], int &i, int &j)
{
    for(i = 0; i < 20; i++)
    {
        for(j = 0; j < 20; j++)
        {
            if(i == 0 || i == 19 || j == 0 || j == 19)
            {
                maze[i][j] = 1;
            }
            else
            {
                maze[i][j] = 0;
            }
        }
        cout << endl;
    }
    construct(maze);
}

//PURPOSE: Display the maze on the console.
void display(int maze[20][20], int &i, int &j)
{
    system("cls");
    cout << endl;
    for(i = 0; i < 20; i++)
    {
        for(j = 0; j < 20; j++)
        {
            cout << " " << maze[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

//PURPOSE: Make the AI move through the maze.
void step(int maze[20][20], int &i, int &j)
{
    for(i = 0; i < 20; i++)
    {
        for(j = 0; j < 20; j++)
        {
            if(maze[i][j] == 2)
            {
                //tries to go left
                if(maze[i][j - 1] == 0)
                {
                    maze[i][j - 1] = 2;
                    maze[i][j] = 0;
                }
                //tries to go up
                else if(maze[i - 1][j] == 0)
                {
                    maze[i - 1][j] = 2;
                    maze[i][j] = 0;
                }
                //tries to go right
                else if(maze[i][j + 1] == 0)
                {
                    maze[i][j + 1] = 2;
                    maze[i][j] = 0;
                }
                //tries to go down
                else if(maze[i + 1][j] == 0)
                {
                    maze[i + 1][j] = 2;
                    maze[i][j] = 0;
                }
                //unable to move at all (this should never happen)
                else
                {
                    system("cls");
                    cout << "Error: Dynamic value is trapped!";
                }
            }
        }
    }
    display(maze, i, j);
}

//PURPOSE: Initialize the program, call the other functions,
//and refresh the maze every third of a second.
int main()
{
    //counter variables (these are used throughout the program)
    int i,j;
    //the matrix for the maze itself
    int maze[20][20];
    initialize(maze, i, j);
    display(maze, i, j);
    while (maze[0][10] != 2)
    {
        //one move through the maze
        step(maze, i, j);
        //delays the next move so that the individual moves can be seen
        Sleep(333);
    }
    return 0;
}
 
Last edited:
C++ books are overrated. There's pretty much nothing you can read out of a book about programming that you can't find online. In any case, the odds of finding the solution to a problem like this in a help resource are incredibly low, as there are rarely case-by-case solutions of the kind I need.

I really think that my best bet is to show the code to a more skilled programmer. Or hopefully in this case, a group of more skilled programmers, though I know that some of you might have more experience in plain old C. Of course, I could probably ask a TA in my next lab, but that's not until Thursday. I'd be great if you guys could help me before then.
 
You're not exiting your for() loops after moving the 2 to the right.

Thus, after it moves to the right, the next iteration sees that 2 and immediately moves it back to the left.
 
Oh, wow. Not sure how to fix that. Any chance you could show an alternate version of the code that will keep moving it in whatever direction is necessary?

EDIT: I fixed the problem by making the 2 leave a trail of 3s in its wake. But now it won't be able to revisit paths it already took, in case it hits a dead end when it actually runs through a maze. How can I get around this?
 
Last edited:
Amazing, we're moving from binary, to ternary, to quaternary. How fun!

After checking to make sure there's no 0s around the 2, you could start checking for 3s instead in the same manner to backtrack - replacing them with 1s or 4s or what have you instead that you'll never touch again (because you went down that path already).
 
Last edited:
Heheh, that occurred to me about ten seconds after I posted that.

Also, does anyone know a quick and easy way to initialize a complex maze without having to type in a value for every individual node? For example, a way that I can type every int value in the matrix on only a few lines of code?
 
Code: 
void generate_maze(int width, int height, int **maze)
{
    int i, j;
for (i = 0; i < width; i++)
{
for (j = 0; j < height; j++)
{
    maze[i][j] = rand() & 1; // Same as rand() % 2
}
}
}

Of course, if you actually want it NAVIGABLE, well... then no.

BTW, your maze assignment is just screaming for the use of recursion. Kinda odd they'd be lumping that on you so early.
 
Like I said, this isn't an assignment...at least not yet. I'm just practicing for the inevitable day when I am asked to do this.
 
Code: 
typedef struct
{
    int width;
    int height;
    unsigned char *fields;
} maze_t;
 
//PURPOSE: Create walls around every edge of the maze.
void initialize(int *maze, int width, int height)
{
    maze->fields = (unsigned char*)malloc(sizeof(unsigned char)*width*height);
 
    for(i = 0; i < 20; i++)
    {
        for(j = 0; j < 20; j++)
        {
            if(i == 0 || i == 19 || j == 0 || j == 19)
            {
                maze[i][j] = 1;
            }
            else
            {
                maze[i][j] = 0;
            }
        }
        cout << endl;
    }
    construct(maze);
}
 
int main(int argc, char *argv[])
{
    //counter variables (these variables are local)
    int i, j;
    //the matrix for the maze itself
    maze_t maze;
    initialize(maze, 20, 20);
    display(&maze, i, j);
 
/**** CHANGE ME KTHX*////////
    while (maze.fields[0][10] != 2)
    {
        //one move through the maze
        step(&maze, i, j);
        //delays the next move so that the individual moves can be seen
        Sleep(333);
    }
//*****//
 
    free(maze.fields);
    return 0;
}
 
Last edited:
Uh...wow, thanks. Nowhere near that level yet, though, so I haven't got a clue what a lot of that means or how to integrate it into my existing code, though, but I appreciate the effort.

Also,
maze->fields = (unsigned char*)malloc(sizeof(unsigned char)*width*height);

Error: expression must have pointer-to-class type
 
Last edited:
Really, if you want to practice, you should think more in an OOP-manner and think about allowing variable-size mazes and having the maze-finding be a 'player' that keeps track of itself and uses primitive AI to navigate.
structs are kind of like primitive classes. So you can create an 'object' by grouping different variables:

typedef struct
{
int width;
int height;
unsigned char *fields;
} maze_t;

typedef struct
{
int x, y;
int lastX, lastY;
} player_t;

You're not actually MAKING the structs/objects at this point, you're just defining what they are. Once you've done the above, you can use them like a variable in your code:

int i;
int j;
player_t player;
maze_t maze;

Also, while you are learning, always try to pay attention as to whether the variables you are creating are created on the stack, or on the heap. If they're made on the heap, you need to manually free that memory used by yourself. A lot of instructors miss this and then you start doing real-world work (SRB2) and wonder why stuff is breaking. C++ is also a lot less clear on this than C.


For example:

when you do

int[] myvar = new int[20];

When you're done with it, you NEED to do:

delete myvar;

But if you do

int myvar[20];

It will free itself when you leave scope.
 
Last edited:
Was this what you had in mind? Because it's riddled with errors.

Code: 
#include <iostream>
#include <Windows.h>
using namespace std;

typedef struct
{
int width;
int height;
unsigned char *fields;
} maze_t;

typedef struct
{
int x, y;
int lastX, lastY;
} player_t;

int i;
int j;
player_t player;
maze_t maze; 

//PURPOSE: Specify a structure of walls, empty spaces, and place
//the start and exit points.
void construct(int maze[20][20])
{
    //interior walls
    maze[1][9] = 1;
    maze[2][2] = 1;
    maze[2][3] = 1;
    maze[2][4] = 1;
    maze[2][5] = 1;
    maze[2][6] = 1;
    maze[2][7] = 1;
    maze[2][8] = 1;
    maze[2][9] = 1;
    //start point
    maze[19][9] = 2;
    //exit point
    maze[0][10] = 0;
}

void generate_maze(int width, int height, int **maze)
{
    int i, j;
    for (i = 0; i < width; i++)
        {
            for (j = 0; j < height; j++)
            {
                maze[i][j] = rand() & 1; // Same as rand() % 2
            }
        }
    }

//PURPOSE: Create walls around every edge of the maze.
void initialize(int *maze, int width, int height)
{
    maze->fields = (unsigned char*)malloc(sizeof(unsigned char)*width*height);
 
    for(int i = 0; i < 20; i++)
    {
        for(int j = 0; j < 20; j++)
        {
            if(i == 0 || i == 19 || j == 0 || j == 19)
            {
                maze[i][j] = 1;
            }
            else
            {
                maze[i][j] = 0;
            }
        }
        cout << endl;
    }
    construct(maze);
}


//PURPOSE: Display the maze on the console.
void display(int maze[20][20], int &i, int &j)
{
    system("cls");
    cout << endl;
    for(i = 0; i < 20; i++)
    {
        for(j = 0; j < 20; j++)
        {
            cout << " " << maze[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

//PURPOSE: Make the AI move through the maze.
void step(int maze[20][20], int &i, int &j)
{
    for(i = 0; i < 20; i++)
    {
        for(j = 0; j < 20; j++)
        {
            if(maze[i][j] == 2)
            {
                //tries to go left
                if(maze[i][j - 1] == 0)
                {
                        maze[i][j - 1] = 2;
                        maze[i][j] = 3;
                }
                //tries to go up
                else if(maze[i - 1][j] == 0)
                {
                        maze[i - 1][j] = 2;
                        maze[i][j] = 3;
                }
                //tries to go right
                else if(maze[i][j + 1] == 0)
                {
                    while(maze[i][j + 1] == 0)
                    {
                        maze[i][j + 1] = 2;
                        maze[i][j] = 3;
                        display(maze, i, j);
                    }
                }
                //tries to go down
                else if(maze[i + 1][j] == 0)
                {
                    while(maze[i + 1][j] == 0)
                    {
                        maze[i + 1][j] = 2;
                        maze[i][j] = 3;
                        display(maze, i, j);
                    }
                }
                //checks for any paths it already crossed and reuses them if necessary
                else
                {
                    //tries to go left on a path it already crossed
                    if(maze[i][j - 1] == 3)
                    {
                            maze[i][j - 1] = 2;
                            maze[i][j] = 4;
                    }
                    //tries to go up on a path it already crossed
                    else if(maze[i - 1][j] == 3)
                    {
                            maze[i - 1][j] = 2;
                            maze[i][j] = 4;
                    }
                    //tries to go right on a path it already crossed
                    else if(maze[i][j + 1] == 3)
                    {
                        while(maze[i][j + 1] == 3)
                        {
                            maze[i][j + 1] = 2;
                            maze[i][j] = 4;
                            display(maze, i, j);
                        }
                    }
                    //tries to go down on a path it already crossed
                    else if(maze[i + 1][j] == 3)
                    {
                        while(maze[i + 1][j] == 3)
                        {
                            maze[i + 1][j] = 2;
                            maze[i][j] = 4;
                            display(maze, i, j);
                        }
                    }
                    //unable to move at all (this should never happen)
                    else
                    {
                        system("cls");
                        cout << "Error: Dynamic value is trapped!";
                    }
                }
            }
        }
    }
    display(maze, i, j);
}

//PURPOSE: Initialize the program, call the other functions,
//and refresh the maze every tenth of a second.
int main(int argc, char *argv[])
{
    //counter variables (these variables are local)
    int i, j;
    //the matrix for the maze itself
    maze_t maze;
    initialize(maze, 20, 20);
    display(&maze, i, j);
 
/**** CHANGE ME KTHX*////////
    while (maze.fields[0][10] != 2)
    {
        //one move through the maze
        step(&maze, i, j);
        //delays the next move so that the individual moves can be seen
        Sleep(333);
    }
//*****//
 
    free(maze.fields);
    return 0;
}
 
Sort of, but it's not complete. For example, maze[j] needs to become maze->fields[j]

And you should use maze_t *maze in your function parameter list, instead of int maze[20][20]

And of course, all of the for() loops should use i < maze->width and j < maze->height

Also, create a player_t and pass it around, using x and y as the replacement for i and j.

This way, you can even have multiple players finding their way through a maze at once!

If you make a working version of your original code, I just might convert it.
 
Last edited:
Sorry, I'm just nowhere near skilled enough to implement all that. Besides, no matter how cool that program is, it wouldn't really be my own work, and I wouldn't understand it, which kind of defeats the purpose of practicing this stuff in the first place.

If you want to fix up the code, that'd be cool, and I'd love to take it for a spin, but right now I'm just tinkering with my old code; I have managed to make a primitive AI that will navigate most mazes. It has even successfully navigated everything your random maze assembler code has thrown at it!

I do have another question, however. My program desperately needs separate console colors for each number, to make the walls, empty space, and character easy to distinguish. Can you think of an efficient way to automatically assign specific colors to specific numbers?
 
Fawfulfan said:
Sorry, I'm just nowhere near skilled enough to implement all that. Besides, no matter how cool that program is, it wouldn't really be my own work, and I wouldn't understand it, which kind of defeats the purpose of practicing this stuff in the first place.
Click to expand...

Well, that's kind of my point - to try to introduce you to a few new concepts such as heap allocation (malloc/free), as well as holding all of the 'current state' information in a container (struct). This will help you form better 'plans of attack' for future problems, as well as maybe getting you some extra credit.

It has even successfully navigated everything your random maze assembler code has thrown at it!
Click to expand...

Heehee....has it actually formed any mazes of value?

I do have another question, however. My program desperately needs separate console colors for each number, to make the walls, empty space, and character easy to distinguish. Can you think of an efficient way to automatically assign specific colors to specific numbers?
Click to expand...

Unless you find some kind of way to use ANSI in the console, I'm not too optimistic. Maybe you could move to OpenGL (Haaa haa kidding). I want Jeck's models to navigate the maze. :E

Check Win32 API's console functions...warning, it could get nasty looking.

> Sleep(333);

Not that I like it much myself, mind you.
Click to expand...

Yeah! That's lame... it needs something more like

int wait;
for (wait = 0; wait < 1000000; wait++);

;)
 
Last edited:
All right, I've now got a maze that has color and prints characters instead of integers. But there's a new, enormous problem. The computer doesn't seem to be erasing the data created by this program once it's finished, and it's choking up the program's ability to write random mazes. The program just seems to grab mazes it made earlier and use them, instead of building new ones! I think this is one of those stack vs. heap issues that SSN told me to watch out for, but I haven't got a clue how to handle the memory so that this problem is fixed. Could you guys have a look at my code and tell me why this is happening?

Code: 
#include <iostream>
#include <conio.h>
#include <Windows.h>
#define _WIN32_WINNT 0x0500
using namespace std;
enum Colors {blue=1, green, cyan, red, purple, yellow, grey, dgrey, hblue, hgreen, hred, hpurple, hyellow, hwhite};

//function prototypes
void coutc(int color, char*output);
void ordConstruct(int maze[20][20]);
void randConstruct(int maze[20][20], int &i, int &j);
void initialize(int maze[20][20], int &i, int &j, int &mode);
void display(int maze[20][20], int &i, int &j);
int step(int maze[20][20], int &i, int &j);

//PURPOSE: Initialize the program, call the other functions,
//and refresh the maze every tenth of a second.
int main()
{
    //specifies console dimensions to fit size of maze
    HWND console = GetConsoleWindow();
    RECT r;
    GetWindowRect(console, &r);
    MoveWindow(console, r.left, r.top, 800, 400, TRUE);

    int i, j;            //counters
    int mode, choice;    //user choices
    int maze[20][20];    //the matrix for the maze itself

    //startup message
    cout << "Welcome to Maze Navigator!" << endl;
    cout << endl;
    cout << "Do you want to navigate an ordered maze or a random maze? (0/1)" << endl;
    cin >> mode;

    //checks whether mode setting is valid
    if (mode != 0 && mode != 1)
    {
        system("cls");
        cout << "Error: Invalid mode setting!" << endl;
        system("pause");
        system("cls");
        return main();
    }

    //startup functions
    initialize(maze, i, j, mode);
    display(maze, i, j);
    while (maze[0][10] != 2)
    {
        //one move through the maze
        step(maze, i, j);
        //delays the next move so that the individual moves can be seen
        Sleep(100);
    }

    //displays upon maze completion
    system("cls");
    coutc(grey, "Maze Solved!");
    cout << endl;
    cout << "Do you want to run another maze? (1/0)" << endl;
    cin >> choice;

    //program exits or restarts depending on player's choice
    if (choice == 1)
    {
        system("cls");
        return main();
    }
    else
    {
        return 0;
    }
}

void coutc(int color, char* output)
{
   HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
   SetConsoleTextAttribute(handle, color);
   cout << output;
   SetConsoleTextAttribute(handle, color);
}

//PURPOSE: Specify a structure of walls, empty spaces, and place
//the start and exit points.
void ordConstruct(int maze[20][20])
{
    //interior walls
    maze[0][9] = 1;
    maze[1][2] = 1;
    maze[1][3] = 1;
    maze[1][4] = 1;
    maze[1][5] = 1;
    maze[1][6] = 1;
    maze[1][7] = 1;
    maze[1][8] = 1;
    maze[1][9] = 1;
    //start point
    maze[20][9] = 2;
    //exit point
    maze[0][10] = 0;
}

//PURPOSE: Generate a randomly structured maze.
void randConstruct(int maze[20][20], int &i, int &j)
{
    int spaceFreq;
    system("cls");
    cout << "Enter a space frequency between 1 and 10: ";
    cin >> spaceFreq;
    //checks whether the chosen space frequency is valid
    if (spaceFreq < 1 || spaceFreq >10)
    {
        system("cls");
        cout << "Error: Invalid space frequency" << endl;
        system("pause");
        system("cls");
        main();
    }
    for (i = 0; i < 20; i++)
    {
        for (j = 0; j < 20; j++)
        {
            maze[i][j] = rand() & spaceFreq;
            if (maze[i][j] != 0 && maze[i][j] != 1)
            {
                maze[i][j] = 0;
            }
        }
    }
    //start point
    maze[19][9] = 2;
    //exit point
    maze[0][10] = 0;
}

//PURPOSE: Preliminarily fill in the maze with empty space before
//constructing it proper
void initialize(int maze[20][20], int &i, int &j, int &mode)
{
    for(i = 0; i < 20; i++)
    {
        for(j = 0; j < 20; j++)
        {
            maze[i][j] = 0;
        }
        cout << endl;
    }
    //depending on user specifications, use a prefabricated or random maze
    if (mode == 0)
    {
        ordConstruct(maze);
    }
    else if (mode == 1)
    {
        randConstruct(maze, i, j);
    }
}

//PURPOSE: Display the maze on the console.
void display(int maze[20][20], int &i, int &j)
{
    system("cls");
    cout << endl << endl;;
    coutc(hgreen, "                                        $");
    cout << endl;
    coutc(green, "                  X X X X X X X X X X X   X X X X X X X X X X");
    cout << endl;
    for(i = 0; i < 20; i++)
    {
        coutc(green,"                  X");
        //specifies the characters corresponding to different components of the maze
        for(j = 0; j < 20; j++)
        {
            //empty space
            if (maze[i][j] == 0)
            {
                coutc(blue, "  ");
            }
            //wall
            else if (maze[i][j] == 1)
            {
                coutc(green, " X");
            }
            //dynamic character
            else if (maze[i][j] == 2)
            {
                coutc(hblue, " O");
            }
            //path used once
            else if (maze[i][j] == 3)
            {
                coutc(blue, " '");
            }
            //path used twice
            else if (maze[i][j] == 4)
            {
                coutc(blue, " *");
            }
            //this shouldn't ever be activated
            else
            {
                cout << "  " << maze[i][j];
            }
        }
        coutc(green," X");
        cout << endl;
    }
    coutc(green, "                  X X X X X X X X X X   X X X X X X X X X X X");
    cout << endl;
    coutc(cyan, "                                      @");
    cout << endl;
}

//PURPOSE: Make the AI move through the maze.
int step(int maze[20][20], int &i, int &j)
{
    int choice;
    for(i = 0; i < 20; i++)
    {
        for(j = 0; j < 20; j++)
        {
            if(maze[i][j] == 2)
            {
                //tries to go left
                if(maze[i][j - 1] == 0 && j != 0)
                {
                        maze[i][j - 1] = 2;
                        maze[i][j] = 3;
                }
                //tries to go up
                else if(maze[i - 1][j] == 0 && i != 0)
                {
                        maze[i - 1][j] = 2;
                        maze[i][j] = 3;
                }
                //tries to go right
                else if(maze[i][j + 1] == 0 && j != 19)
                {
                    while(maze[i][j + 1] == 0 && j != 19)
                    {
                        maze[i][j + 1] = 2;
                        maze[i][j] = 3;
                        display(maze, i, j);
                    }
                }
                //tries to go down
                else if(maze[i + 1][j] == 0 && i != 19)
                {
                    while(maze[i + 1][j] == 0 && i != 19)
                    {
                        maze[i + 1][j] = 2;
                        maze[i][j] = 3;
                        display(maze, i, j);
                    }
                }
                //checks for any paths it already crossed and reuses them if necessary
                else
                {
                    //tries to go left on a path it already crossed
                    if(maze[i][j - 1] == 3 && j != 0)
                    {
                            maze[i][j - 1] = 2;
                            maze[i][j] = 4;
                    }
                    //tries to go up on a path it already crossed
                    else if(maze[i - 1][j] == 3 && i != 0)
                    {
                            maze[i - 1][j] = 2;
                            maze[i][j] = 4;
                    }
                    //tries to go right on a path it already crossed
                    else if(maze[i][j + 1] == 3 && j != 19)
                    {
                        while(maze[i][j + 1] == 3 && j != 19)
                        {
                            maze[i][j + 1] = 2;
                            maze[i][j] = 4;
                            display(maze, i, j);
                        }
                    }
                    //tries to go down on a path it already crossed
                    else if(maze[i + 1][j] == 3 && i != 19)
                    {
                        while(maze[i + 1][j] == 3 && i != 19)
                        {
                            maze[i + 1][j] = 2;
                            maze[i][j] = 4;
                            display(maze, i, j);
                        }
                    }
                    //unable to move at all
                    else
                    {
                        system("cls");
                        coutc(grey, "Dynamic value is trapped!");
                        cout << endl;
                        cout << "Do you want to run another maze? (1/0)" << endl;
                        cin >> choice;
                        if (choice == 1)
                        {
                            system("cls");
                            return main();
                        }
                        else
                        {
                            return 0;
                        }
                    }
                }
            }
        }
    }
    display(maze, i, j);
    return 1;
}
 
I'm still learning C++, and that program you are showing is just a pain for me. I do use printf for out, and not cout.
 
Status
Not open for further replies.

Who is viewing this thread (Total: 1, Members: 0, Guests: 1)

Back
Top