Please delete/close thread sorry for the inconvenience it was a stupid question
Please delete/close thread sorry for the inconvenience it was a stupid question
Last edited by Nwb; 11-10-2018 at 01:35 AM.
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...
Last edited by GReaper; 11-10-2018 at 01:39 AM.
Devoted my life to programming...
Sorry I deleted my post but since we're here I'll say what I came up with.
Originally I had
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.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
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; }
Last edited by Nwb; 11-10-2018 at 01:51 AM.
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:Originally Posted by Nwb
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:return C >= 0 && B != ' ' && E != ' ' && D != ' ';
However, I note that the code that you posted mentions max_width, but this is not mentioned when you specified the condition.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] != ' '; }
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Yea forgot the max condition.
Basically I'm making a maze generator. The coordinates represent either a ' ' or an X. And to generate the maze I must make sure the paths do not collide that's why all of this.
I'll post the full code for the maze generator here once it's done
No, I did not forget the max condition. You didn't specify it. I even noted that in my post.Originally Posted by Nwb
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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 Nwb
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
I suggest simplifying your code:
to: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; }
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; }Prefer to use braces to delimit blocks of code even when unnecessary and you will avoid this kind of problem.Originally Posted by Nwb
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:
But eh, I note that you compare current_position.width with max_height rather than max_width. Is that a bug?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; }
Last edited by laserlight; 11-10-2018 at 02:54 AM.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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:
edit: Yes laserlight that was a bug thanks. But that doesn't fix it.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 ¤t_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 ¤t_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 ¤t_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"); }
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.
Last edited by Nwb; 11-10-2018 at 04:36 AM.
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; } }
Last edited by laserlight; 11-10-2018 at 09:37 AM.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
I donno why my post got deleted.. Must be my clumsy phone so sorry about that.
For some reason when I try to edit using my phone the forum deletes the post.. Weird.
Anyways I'll explain everything from the logic Tomorrow when I can get on my pc. That isn't the entire program I jsu wanted to test if the program could generate a path without intersecting itself.
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.Originally Posted by Nwb
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".
Last edited by laserlight; 11-10-2018 at 07:52 PM.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
I'll tell you my logic.. Its not complete yet so yes it is still a path. I don't know when I will be able to operate on my pc that's all.
The path need not hit the exit.
By the way since you worked it out what is wrong with my logic for checking possible paths? Can you give a small hint.
That's what I wanted help with originally. I was going to post the full program only when it was done but figured I might be wrong in the program itself because I can't think of a reason why my logic is failing. That said I'm sure the rest of the program is proper.
Just that my path is intersecting itself
You haven't told us your logic. You've shown us your code, but as we've all seen, there's no reason the code has to match the logic. So first we need to see what your logic is, then we can see whether that logic will actually solve your problem (whatever it is), then we can see whether your code matches the logic.