Thread: Need help with logic..

Please delete/close thread sorry for the inconvenience it was a stupid question

I think the final "else" of each move should return false instead of true.

EDIT: Please don't do that. Don't delete your post after you've realized you made a stupid mistake. Other people can learn from it, you know...

Originally Posted by GReaper

I think the final "else" of each move should return false instead of true.

Sorry I deleted my post but since we're here I'll say what I came up with.


Originally I had

Code:

    if (move == UP) {
        if (current_position.height + 1 >= max_height)
            return false;
        else if (!(current_position.height + 2 < max_height || current_position.width + 1 >= max_width || current_position.width - 1 < 0 )) {
            if (maze[current_position.height + 1][current_position.width - 1] == ' ' || maze[current_position.height + 1][current_position.width + 1] == ' ' ||
                maze[current_position.height + 2][current_position.width] == ' ')
                return false;
            else
                return true;
        }
        else

But the problem with that is that the condition was returning true for cases like (1,1) because one of the to-be-compared coordinate was out of limits (1-2 = -1) so the program never checked for adjacent coordinates to find ' ' (0,2 had ' '). So the function returned true even if there was an adjacent ' ' because the program never checked for ' ' because of the fact that height was out of range.

So instead I check for each ' ' individually, so it would work now.

Code:

      if (move == UP) {
        if (current_position.height - 1 < 0)
            return false;
        else {
            if (!(current_position.height - 1 < 0 || current_position.width - 1 < 0))
                if (maze[current_position.height - 1][current_position.width - 1] == ' ')
                    return false;
            if (!(current_position.height - 1 < 0 || current_position.width + 1 <= max_height))
                if (maze[current_position.height - 1][current_position.width + 1] == ' ')
                    return false;
            if (!(current_position.height - 2 < 0))
                if (maze[current_position.height - 2][current_position.width] == ' ')
                    return true;
        }
        return false;
    }

Originally Posted by Nwb

A, B, C, D and E are coordinates.
(...)
I want a condition such that the function returns true if
1) C is not less than 0 (less than lowest index)
2) B, E, D are not ' '
Otherwise false.

I don't quite understand how a coordinate can possibly be a space. Perhaps you meant to say, if the value at the given coordinate is a space? It is confusing because what you say can be expressed as:

Code:

return !(C < 0) && B != ' ' && E != ' ' && D != ' ';

or equivalently:

Code:

return C >= 0 && B != ' ' && E != ' ' && D != ' ';

So we just need to substitute your actual coordinate expressions for C, B, E, and D, and you're done. But it seems that by C you mean something different from B, E, and D (as in C is a coordinate and B, E, and D are the values at the coordinates). What exactly does "C is not less than 0" mean? It doesn't make sense for a coordinate since a coordinate is a pair, and a pair cannot be less than 0, unless you mean to say that each member of the pair is not less than 0. If so, my guess is that this means:

Code:

if (move == UP) {
    return current_position.height - 1 >= 0 && current_position.width >= 0
        && maze[current_position.height - 1][current_position.width - 1] != ' '
        && maze[current_position.height - 1][current_position.width + 1] != ' '
        && maze[current_position.height - 2][current_position.width] != ' ';
}

However, I note that the code that you posted mentions max_width, but this is not mentioned when you specified the condition.

Originally Posted by Nwb

Yea forgot the max condition.

No, I did not forget the max condition. You didn't specify it. I even noted that in my post.

Originally Posted by Nwb

Code:

if (move == UP) {
    if (current_position.height - 1 < 0)
        return false;
    else {
        if (!current_position.height - 1 < 0 || current_position.width - 1 < 0)
            if (maze[current_position.height - 1][current_position.width - 1] == ' ')
                return false;
        if (!current_position.height - 1 < 0 || current_position.width + 1 <= max_height)
            if (maze[current_position.height - 1][current_position.width + 1] == ' ')
                return false;
        if (!current_position.height - 2 < 0)
            if (maze[current_position.height - 2][current_position.width] == ' ')
                return false;
    }
    return false;
}

Note that !current_position.height - 1 < 0 is equivalent to (!current_position.height) - 1 < 0. I'm guessing that that is not your intent.

Originally Posted by laserlight

Note that !current_position.height - 1 < 0 is equivalent to (!current_position.height) - 1 < 0. I'm guessing that that is not your intent.

thanks!
(edited original reply)
I also wrote return false; instead of return true; in the last line

I put the big else because when I put the last line's else it got connected to the inner if of the nested if statement..

I suggest simplifying your code:

Code:

if (move == UP) {
    if (current_position.height - 1 < 0)
        return false;
    else {
        if (!(current_position.height - 1 < 0 || current_position.width - 1 < 0))
            if (maze[current_position.height - 1][current_position.width - 1] == ' ')
                return false;
        if (!(current_position.height - 1 < 0 || current_position.width + 1 <= max_height))
            if (maze[current_position.height - 1][current_position.width + 1] == ' ')
                return false;
        if (!(current_position.height - 2 < 0))
            if (maze[current_position.height - 2][current_position.width] == ' ')
                return true;
    }
    return false;
}

to:

Code:

if (move == UP) {
    if (current_position.height - 1 < 0) {
        return false;
    }

    if (current_position.height - 1 >= 0 && current_position.width - 1 >= 0
            && maze[current_position.height - 1][current_position.width - 1] == ' ') {
        return false;
    }

    if (current_position.height - 1 >= 0 && current_position.width + 1 > max_height
            && maze[current_position.height - 1][current_position.width + 1] == ' ') {
        return false;
    }

    if (current_position.height - 2 >= 0
            && maze[current_position.height - 2][current_position.width] == ' ') {
        return true;
    }

    return false;
}

Originally Posted by Nwb

I put the big else because when I put the last line's else it got connected to the inner if of the nested if statement..

Prefer to use braces to delimit blocks of code even when unnecessary and you will avoid this kind of problem.

EDIT:
Actually, since you check for (current_position.height - 1 < 0) first, you know that for the rest of the block, current_position.height - 1 >= 0. Therefore, you can simplify further:

Code:

if (move == UP) {
    if (current_position.height < 1) {
        return false;
    }

    if (current_position.width >= 1 && maze[current_position.height - 1][current_position.width - 1] == ' ') {
        return false;
    }

    if (current_position.width >= max_height && maze[current_position.height - 1][current_position.width + 1] == ' ') {
        return false;
    }

    if (current_position.height >= 2 && maze[current_position.height - 2][current_position.width] == ' ') {
        return true;
    }

    return false;
}

But eh, I note that you compare current_position.width with max_height rather than max_width. Is that a bug?

UGHHHHHHHHHHHHH I thought I had it.. but the logic still seems to not work! I don't know if it is the check_movement() function or what! I think it's check_movement() but I'm not sure.

The maze that is generated doesn't follow the conditions of check_movement() and sometimes nothing displays on the screen (can't be an infinite loop so I think it's because something is trying to access an out of reach index).

:'(

Here is the entire code:

Code:

#include <ctime>
#include <iostream>

using namespace std;

struct coordinates {
    int height;
    int width;
};

enum movement {
    RIGHT, LEFT, UP, DOWN
};

int random(int lower_limit, int upper_limit) {
    return rand() % (upper_limit - lower_limit + 1) + lower_limit;
}

void add_coordinates(coordinates current_path, coordinates *&path_array, int &current_size) {

    coordinates *new_path_array = new coordinates[current_size + 1];

    for (int i = 0; i < current_size; i++) {
        new_path_array[i] = path_array[i];
    }
    new_path_array[current_size] = current_path;

    current_size++;
    delete[] path_array;
    path_array = new_path_array;
}

void remove_coordinates(int index, coordinates *&path_array, int &current_size) {
    coordinates *new_path_array = new coordinates[current_size - 1];

    for (int i = 0; i < current_size; i++) {
        if (i == index - 1)
            continue;
        else if (i > index - 1)
            new_path_array[i - 1] = path_array[i];
        else
            new_path_array[i] = path_array[i];
    }

    current_size--;
    delete[] path_array;
    path_array = new_path_array;
}

bool check_movement(movement move, coordinates current_position, char **&maze, int max_height, int max_width) {
    if (move == UP) {
        if (current_position.height - 1 < 0)
            return false;
        else {
            if (!(current_position.height - 1 < 0 || current_position.width - 1 < 0))
                if (maze[current_position.height - 1][current_position.width - 1] == ' ')
                    return false;
            if (!(current_position.height - 1 < 0 || current_position.width + 1 <= max_width))
                if (maze[current_position.height - 1][current_position.width + 1] == ' ')
                    return false;
            if (!(current_position.height - 2 < 0))
                if (maze[current_position.height - 2][current_position.width] == ' ')
                    return false;
        }
        return true;
    }
    else if (move == DOWN) {
        if (current_position.height + 1 >= max_height)
            return false;
        else {
            if (!(current_position.height + 1 >= max_height || current_position.width - 1 < 0))
                if (maze[current_position.height + 1][current_position.width - 1] == ' ')
                    return false;

            if (!(current_position.height + 1 >= max_height || current_position.width + 1 >= max_width))
                if (maze[current_position.height + 1][current_position.width + 1] == ' ')
                    return false;

            if (!(current_position.height + 2 >= max_height))
                if (maze[current_position.height + 2][current_position.width] == ' ')
                    return false;
        }
        return true;
    }
    else if (move == RIGHT) {
        if (current_position.width + 1 >= max_width)
            return false;
        else {
            if (!(current_position.width + 2 >= max_width))
                if (maze[current_position.height][current_position.width + 2] == ' ')
                    return false;
            if (!(current_position.height + 1 >= max_height || current_position.width + 1 >= max_width))
                if (maze[current_position.height + 1][current_position.width + 1] == ' ')
                    return false;
            if (!(current_position.height - 1 < 0 || current_position.width + 1 >= max_width))
                if (maze[current_position.height - 1][current_position.width + 1] == ' ')
                    return false;
        }
        return true;
    }

    else if (move == LEFT) {
        if (current_position.width - 1 < 0)
            return false;
        else {
            if (!(current_position.width - 2 < 0))
                if (maze[current_position.height][current_position.width - 2] == ' ')
                    return false;
            if (!(current_position.height + 1 >= max_height || current_position.width - 1 < 0))
                if (maze[current_position.height + 1][current_position.width - 1] == ' ')
                    return false;
            if (!(current_position.height - 1 < 0 || current_position.width - 1 < 0))
                if (maze[current_position.height - 1][current_position.width - 1] == ' ')
                    return false;
        }
        return true;
    }
    else
        return false;
}

bool check_if_possible(coordinates current_position, char **&maze, int height, int width) {
    return check_movement(UP, current_position, maze, height, width) ||
           check_movement(DOWN, current_position, maze, height, width) ||
           check_movement(RIGHT, current_position, maze, height, width) ||
           check_movement(LEFT, current_position, maze, height, width);
}

void generate_next_path(coordinates &current_position, char **&maze, int max_height, int max_width) {
    int possible_move = 0;
    movement possibilities[4];

    if (check_movement(UP, current_position, maze, max_height, max_width)) {
        possibilities[possible_move] = UP;
        possible_move++;
    }
    if (check_movement(DOWN, current_position, maze, max_height, max_width)) {
        possibilities[possible_move] = DOWN;
        possible_move++;
    }
    if (check_movement(RIGHT, current_position, maze, max_height, max_width)) {
        possibilities[possible_move] = RIGHT;
        possible_move++;
    }
    if (check_movement(LEFT, current_position, maze, max_height, max_width)) {
        possibilities[possible_move] = LEFT;
        possible_move++;
    }

    int chosen;
    do
        chosen = rand() % possible_move + 1; 
        // 0 to possibilities, neglect 0 because it's unfairly unlikely
    while (chosen == 0);

    if (possibilities[chosen-1] == UP) {
        current_position.height--;
    }
    else if (possibilities[chosen-1] == DOWN) {
        current_position.height++;
    }
    else if (possibilities[chosen-1] == RIGHT) {
        current_position.width++;
    }
    else 
        current_position.width--;
}

void fill_maze(char **&maze, int height, int width) {
    for (int i = 0; i < height; i++) {
        maze[i] = new char[width];
    }

    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            maze[i][j] = 'x';
        }
    }
    maze[0][0] = ' ';
    maze[height - 1][width - 1] = ' ';
}

void display_maze(char **&maze, int height, int width) {
    for (int i = -1; i <= height; i++) {
        for (int j = -1; j <= width; j++) {
            if (i == -1 || j == -1 || i == height || j == width) {
                cout << '0';
            }
            else
                cout << maze[i][j];
        }
        cout << '\n';
    }
}

void generate_maze(int height, int width) {

    int covered_path_size = 0;
    coordinates *covered_path = new coordinates[0];

    char **p_p_maze = new char*[height];
    fill_maze(p_p_maze, height, width);

    coordinates current_position;
    current_position.height = 0;
    current_position.width = 0;
    add_coordinates(current_position, covered_path, covered_path_size);

    generate_next_path(current_position, p_p_maze, height, width);
    //cout << current_position.height << ' ' << current_position.width;


    //temporary while loop to test logic
        while (check_if_possible(current_position, p_p_maze, height, width)){
            p_p_maze[current_position.height][current_position.width] = ' ';
            generate_next_path(current_position, p_p_maze, height, width);
            p_p_maze[current_position.height][current_position.width] = ' ';
        }
    

    display_maze(p_p_maze, height, width);

}

int main() {
    srand((unsigned)time(NULL));
    generate_maze(20, 40);
    system("pause");
}

edit: Yes laserlight that was a bug thanks. But that doesn't fix it.

Here's the output I had gotten (which just doesn't make sense..)



Umgh dear mod pls don't close this thread, I can't edit the original post.

Correct me if I'm wrong, but I can only find one call to add_coordinates, and no calls to remove_coordinates. You don't seem to use covered_path except in generate_maze, and only to call add_coordinates. current_position is used quite a bit, but it doesn't involve a path, only the current position. So, it looks like you abandoned the use of coordinates for a path, keeping it only as a way to track the current position. Yet, you although you abandoned it, you couldn't bring yourself to remove it entirely, hence the creation of covered_path and the single call to add_coordinates. Is this correct?

Furthermore, it looks like your strategy for generating the maze is to forge a random path through the grid, and keep going as long as it is possible to do so. This sounds like it is good for generating a "cave" rather than a "maze", and then there's the problem that if you really want to end at the bottom right cell, you might not do so simply because you could keep reaching positions where it is impossible to forge ahead from the current position.

I was curious if your strategy had a snowball's chance in hell of working to create a maze (or rather a cave) from the top left cell to the bottom right cell for your sample 20x40 grid, and it looks it does, but I needed to set the max tries to 4000 to keep getting success. Probably you would want to set it to 5000 to be safe.

Code:

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <ostream>
#include <stdexcept>
#include <vector>

const int MAX_TRIES = 4000;

struct Coordinates {
    // (row, col) denotes the position at grid[row][col], i.e., (0, 0) is the top left cell
    size_t row;
    size_t col;

    Coordinates(size_t row, size_t col) : row(row), col(col) {}
};

class Maze {
public:
    friend std::ostream& operator<<(std::ostream& out, const Maze& maze);

    Maze(size_t num_rows, size_t num_cols) : grid(num_rows, std::vector<char>(num_cols, 'x')) {
        if (num_rows < 2) {
            throw std::domain_error("The maze must have at least two rows.");
        }
        if (num_cols < 2) {
            throw std::domain_error("The maze must have at least two columns.");
        }

        grid[0][0] = ' ';
    }

    void generate_path() {
        bool path_completed = false;
        int tries = 0;
        do {
            path_completed = true;
            ++tries;

            auto current_coords = Coordinates{0, 0};
            while (current_coords.row != row_last_index() || current_coords.col != col_last_index()) {
                auto candidate_coords = generate_candidate_coordinates(current_coords);
                if (candidate_coords.empty()) {
                    if (tries > MAX_TRIES) {
                        throw std::runtime_error("Maximum number of tries to generate path exceeded.");
                    }

                    path_completed = false;
                    clear_path();
                    break;
                }

                current_coords = candidate_coords[rand() % candidate_coords.size()];
                grid[current_coords.row][current_coords.col] = ' ';
            }
        } while (!path_completed);
    }

    void clear_path() {
        std::vector<std::vector<char>>(grid.size(), std::vector<char>(grid[0].size(), 'x')).swap(grid);
        grid[0][0] = ' ';
    }
private:
    std::vector<std::vector<char>> grid;

    decltype(grid.size()) row_last_index() const {
        return grid.size() - 1;
    }

    decltype(grid[0].size()) col_last_index() const {
        return grid[0].size() - 1;
    }

    std::vector<Coordinates> generate_candidate_coordinates(const Coordinates& current_coords) const {
        auto candidate_coords = std::vector<Coordinates>();
        if (current_coords.row == 0) {
            if (current_coords.col == 0) {
                // top left corner:
                if (grid[current_coords.row][current_coords.col + 1] == 'x') {
                    candidate_coords.emplace_back(current_coords.row, current_coords.col + 1);
                }
                if (grid[current_coords.row + 1][current_coords.col] == 'x') {
                    candidate_coords.emplace_back(current_coords.row + 1, current_coords.col);
                }
            } else if (current_coords.col == col_last_index()) {
                // top right corner:
                if (grid[current_coords.row][current_coords.col - 1] == 'x') {
                    candidate_coords.emplace_back(current_coords.row, current_coords.col - 1);
                }
                if (grid[current_coords.row + 1][current_coords.col] == 'x') {
                    candidate_coords.emplace_back(current_coords.row + 1, current_coords.col);
                }
            } else  {
                // remaining top row:
                if (grid[current_coords.row][current_coords.col - 1] == 'x') {
                    candidate_coords.emplace_back(current_coords.row, current_coords.col - 1);
                }
                if (grid[current_coords.row][current_coords.col + 1] == 'x') {
                    candidate_coords.emplace_back(current_coords.row, current_coords.col + 1);
                }
                if (grid[current_coords.row + 1][current_coords.col] == 'x') {
                    candidate_coords.emplace_back(current_coords.row + 1, current_coords.col);
                }
            }
        } else if (current_coords.row == row_last_index()) {
            if (current_coords.col == 0) {
                // bottom left corner:
                if (grid[current_coords.row - 1][current_coords.col] == 'x') {
                    candidate_coords.emplace_back(current_coords.row - 1, current_coords.col);
                }
                if (grid[current_coords.row][current_coords.col + 1] == 'x') {
                    candidate_coords.emplace_back(current_coords.row, current_coords.col + 1);
                }
            } else if (current_coords.col == col_last_index()) {
                // bottom right corner:
                if (grid[current_coords.row - 1][current_coords.col] == 'x') {
                    candidate_coords.emplace_back(current_coords.row - 1, current_coords.col);
                }
                if (grid[current_coords.row][current_coords.col - 1] == 'x') {
                    candidate_coords.emplace_back(current_coords.row, current_coords.col - 1);
                }
            } else {
                // remaining bottom row:
                if (grid[current_coords.row - 1][current_coords.col] == 'x') {
                    candidate_coords.emplace_back(current_coords.row - 1, current_coords.col);
                }
                if (grid[current_coords.row][current_coords.col - 1] == 'x') {
                    candidate_coords.emplace_back(current_coords.row, current_coords.col - 1);
                }
                if (grid[current_coords.row][current_coords.col + 1] == 'x') {
                    candidate_coords.emplace_back(current_coords.row, current_coords.col + 1);
                }
            }
        } else if (current_coords.col == 0) {
            // remaining left column:
            if (grid[current_coords.row - 1][current_coords.col] == 'x') {
                candidate_coords.emplace_back(current_coords.row - 1, current_coords.col);
            }
            if (grid[current_coords.row][current_coords.col + 1] == 'x') {
                candidate_coords.emplace_back(current_coords.row, current_coords.col + 1);
            }
            if (grid[current_coords.row + 1][current_coords.col] == 'x') {
                candidate_coords.emplace_back(current_coords.row + 1, current_coords.col);
            }
        } else if (current_coords.col == col_last_index()) {
            // remaining right column:
            if (grid[current_coords.row - 1][current_coords.col] == 'x') {
                candidate_coords.emplace_back(current_coords.row - 1, current_coords.col);
            }
            if (grid[current_coords.row][current_coords.col - 1] == 'x') {
                candidate_coords.emplace_back(current_coords.row, current_coords.col - 1);
            }
            if (grid[current_coords.row + 1][current_coords.col] == 'x') {
                candidate_coords.emplace_back(current_coords.row + 1, current_coords.col);
            }
        } else {
            // not at an edge:
            if (grid[current_coords.row - 1][current_coords.col] == 'x') {
                candidate_coords.emplace_back(current_coords.row - 1, current_coords.col);
            }
            if (grid[current_coords.row][current_coords.col - 1] == 'x') {
                candidate_coords.emplace_back(current_coords.row, current_coords.col - 1);
            }
            if (grid[current_coords.row][current_coords.col + 1] == 'x') {
                candidate_coords.emplace_back(current_coords.row, current_coords.col + 1);
            }
            if (grid[current_coords.row + 1][current_coords.col] == 'x') {
                candidate_coords.emplace_back(current_coords.row + 1, current_coords.col);
            }
        }
        return candidate_coords;
    }
};

namespace {
    void print_maze_header(std::ostream& out, const std::vector<std::vector<char>> grid) {
        for (decltype(grid[0].size()) i = 0; i < grid[0].size() + 2; ++i) {
            out << '0';
        }
        out << '\n';
    }
}

std::ostream& operator<<(std::ostream& out, const Maze& maze) {
    print_maze_header(out, maze.grid);
    for (const auto& row : maze.grid) {
        out << '0';
        for (const auto& col : row) {
            out << col;
        }
        out << "0\n";
    }
    print_maze_header(out, maze.grid);
    return out;
}

int main() {
    srand((unsigned)time(NULL));
    try {
        Maze maze(20, 40);
        maze.generate_path();
        std::cout << maze;
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
    }
}

Originally Posted by Nwb

Notice that even in your program (I ran it online) the path is not generated properly. It is supposed to be a single file and isn't supposed to intersect another path.

Although I told you that you would end up with a "cave" rather than a "maze", I cannot "notice" that "the path is not generated properly" because you didn't even mention that there were these additional requirements, so it is not my concern unless I should decide to look into it later.

Unless you change strategy, it looks like more of the same since you would be placing more restrictions on how to forge ahead, so max tries would have to increase. I was curious to see there would be hope for termination based on the strategy you outlined in your code, and the answer is yes.

Realistically though, if I only wanted to help you fix your logic in post #10, it would be a difficult task when you didn't outline your requirements properly.

EDIT:
Oh, I did decide to modify my code for the requirements of "supposed to be a single file and isn't supposed to intersect another path", and was surprised to discover that my intuition was wrong: imposing the additional requirements seems to have reduced the max tries needed by a magnitude, to around 400. It still isn't really a "maze", more like a "meandering path", but at least it is no longer a "cave".