Thread: Need help with logic..

  1. #31
    Registered User
    Join Date
    Sep 2018
    Posts
    150
    rand() % 2 will return 0 only when rand() gives a 0. So if rand() % 2 is giving equal amounts of 0 and equal amounts of 1s then it would be because rand() is generating a number, but also generating 0 every other time.. ugh?

  2. #32
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,041
    Quote Originally Posted by Nwb
    rand() % 2 will return 0 only when rand() gives a 0.
    That is not true. Compile and run this program:
    Code:
    #include <cstdlib>
    #include <ctime>
    #include <iostream>
    
    int main()
    {
        using namespace std;
        srand((unsigned)time(NULL));
        for (int i = 0; i < 20; ++i)
        {
            int n = rand();
            cout << "rand() returned " << n << " and rand() % 2 = " << (n % 2) << endl;
        }
    }
    Quote Originally Posted by Nwb
    So if rand() % 2 is giving equal amounts of 0 and equal amounts of 1s then it would be because rand() is generating a number, but also generating 0 every other time.. ugh?
    Sure, but if that were true, then the other number that rand() is generating must be 1, every other time that it is not generating 0. Since rand() only generates 0s and 1s, rand() % 100 will likewise also only ever result in 0s and 1s. Clearly, your reasoning does not follow.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #33
    Registered User
    Join Date
    Sep 2018
    Posts
    150
    OHHH right modulus.. nevermind stupid me.

  4. #34
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,041
    Quote Originally Posted by Nwb
    Conditions for building path:
    1) like classic mazes the path goes left, right, up, down and is one block wide.
    2) the path does not intersect itself, that would cause for multiple solutions. And the path does not build outside the 2d array (can't go outside maze).
    3) the current path being built stops when there is no place to go keeping in mind the above two conditions.

    (...)

    How would this become a maze?
    The array you saw called path coordinates keeps track of every coordinate that was turned into a path.

    When the first path from start hits a dead end, the program removes the coordinate from where path is not possible. And then tries to build a path from the last coordinate from the array. Consequently adding new paths to the array.

    Once even this path hits and end the program tries does the same process again by trying to build paths from the coordinates in the array and removes them from the array when no path is possible.

    Eventually no more paths are possible then the array is empty and the maze is complete.
    I tried a more naive approach: randomly select a starting point from one of the existing path cells, then randomly generate a dead end path from there until it can go no further, using the same approach for generating the path from start to end, except that I don't try again should I reach a dead end. Then I repeat this many times, e.g., half as many times as there are cells in the maze grid. This seems to work fairly well, as you can see from this sample maze:

    Need help with logic..-maze-png

    You can see some limitation in the use of randomness though: there's a cluster of wall cells in the left middle side that could have been turned into a path, but the random selection of starting points somehow never got to any of the possible starting points for a path there.

    Quote Originally Posted by Nwb
    But what about the end? This is the one thing I was not sure about.

    Two possinilities: either make the right and downmkst coordinate the end or what I chose:

    Keep rerunning the program until the end is linked with an existing path.
    For a 25 by 64 maze, I found that it might take more than 1600 tries to establish a path from start to end using your "forge ahead randomly as long as conditions are satisfied" approach. For 20 by 40, the difference is stark at 400 tries being a safe number. For now I just set the max tries to be the number of cells in the maze grid, even though this is actually inadequate for larger mazes and overkill for smaller ones.

    Quote Originally Posted by Nwb
    There is at least 1/5 chance of the path linking the end with the logic.
    How did you calculate that "1/5 chance"?
    Last edited by laserlight; 2 Days Ago at 10:18 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #35
    Registered User
    Join Date
    Sep 2018
    Posts
    150
    I need to thoroughly check my maze program (or even just redo the entire thing) a bit later I don't have time for that right now though but I'll say what I came up with even if it's a month from now.

    I tried a more naive approach:
    What about the logic I had said? That way we can have a starting point, there won't be clusters of walls, and maybe we can have an ending point.
    Why I can't accept your approach is because it has multiple solutions to the maze, it's not bad in fact it's really good but I want to have only one solution so my initial proposal would suit that.

    How did you calculate that "1/5 chance"?
    Just estimated. Since the program will try to build a path out of every single cell of an existing path, at least 1/3 of the board will be wiped out and chances are that the end is part of the 1/3rd of the board. So 1/5 is a safe number I thought.

  6. #36
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,041
    Quote Originally Posted by Nwb
    Why I can't accept your approach is because it has multiple solutions to the maze, it's not bad in fact it's really good but I want to have only one solution so my initial proposal would suit that.
    It only has one perfect solution, i.e., the complete path from start to end generated initially. Of course, it has multiple solutions, but it is impossible to have a maze that doesn't have multiple solutions unless it is only a single path (in which case surely that would be rather boring), or has the restriction that one cannot go back on a path already travelled. Your own proposed solution will have multiple solutions without that "no going back" restriction.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #37
    Registered User
    Join Date
    Sep 2018
    Posts
    150
    By the way can you show me the conditionals or the block itself that you used for building the path?

  8. #38
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,041
    Quote Originally Posted by Nwb
    What about the logic I had said? That way we can have a starting point, there won't be clusters of walls, and maybe we can have an ending point.
    I think that because it is systematic, it should be able to avoid having wall clusters: the issue with my naive approach is that it merely keeps at it for some predetermined number of iterations rather than stopping when there are no more candidate start cells for dead end paths. It would still be possible to randomly select path cells to start dead end paths, but if so you might want to use a std::list so that deletion from the middle takes constant time (although actually getting to the element to remove takes linear time); if you just want to work from "from the last coordinate from the array", then consider using a std::stack instead (which uses a std::deque for the container by default), which does harken to your talk about being inspired by depth-first search.

    Quote Originally Posted by Nwb
    By the way can you show me the conditionals or the block itself that you used for building the path?
    This is my updated code. You can find what you want in the generate_candidate_cells and filter_candidate_cells member functions.
    Code:
    #include <algorithm>
    #include <cstdlib>
    #include <ctime>
    #include <iostream>
    #include <ostream>
    #include <stdexcept>
    #include <vector>
    
    #define PATH_CELL ' '
    #define WALL_CELL 'x'
    #define BOUNDARY_CELL '0'
    
    struct Cell
    {
        // 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;
    
        Cell(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, WALL_CELL))
        {
            if (num_rows < 1)
            {
                throw std::domain_error("The maze must have at least one row.");
            }
            if (num_cols < 1)
            {
                throw std::domain_error("The maze must have at least one column.");
            }
    
            grid[0][0] = PATH_CELL;
        }
    
        void generate_path();
    
        void clear_path()
        {
            using std::vector;
            vector<vector<char>>(grid.size(), vector<char>(grid[0].size(), WALL_CELL)).swap(grid);
            grid[0][0] = PATH_CELL;
        }
    private:
        std::vector<std::vector<char>> grid;
    
        typedef decltype(grid.size()) size_type;
    
        size_type row_last_index() const
        {
            return grid.size() - 1;
        }
    
        size_type col_last_index() const
        {
            return grid[0].size() - 1;
        }
    
        bool generate_complete_path();
        Cell find_dead_end_path_start() const;
        void generate_dead_end_path();
        std::vector<Cell> generate_candidate_cells(const Cell& current_cell) const;
        void filter_candidate_cells(const Cell& current_cell,
                                    std::vector<Cell>& candidate_cells) const;
    };
    
    void Maze::generate_path()
    {
        const size_type max_tries = grid.size() * grid[0].size();
    
        size_type tries = 0;
        while (tries <= max_tries && !generate_complete_path())
        {
            clear_path();
            ++tries;
        }
        if (tries > max_tries)
        {
            throw std::runtime_error("Maximum number of tries to generate path exceeded.");
        }
    
        for (size_type i = 0; i < max_tries / 2; ++i)
        {
            generate_dead_end_path();
        }
    }
    
    bool Maze::generate_complete_path()
    {
        auto current_cell = Cell(0, 0);
        while (current_cell.row != row_last_index() || current_cell.col != col_last_index())
        {
            auto candidate_cells = generate_candidate_cells(current_cell);
            filter_candidate_cells(current_cell, candidate_cells);
            if (candidate_cells.empty())
            {
                return false;
            }
    
            current_cell = candidate_cells[rand() % candidate_cells.size()];
            grid[current_cell.row][current_cell.col] = PATH_CELL;
        }
        return true;
    }
    
    Cell Maze::find_dead_end_path_start() const
    {
        auto open_cells = std::vector<Cell>();
        for (size_type i = 0; i < grid.size(); ++i)
        {
            for (size_type j = 0; j < grid[i].size(); ++j)
            {
                if (grid[i][j] == PATH_CELL)
                {
                    open_cells.emplace_back(i, j);
                }
            }
        }
    
        if (open_cells.empty())
        {
            throw std::logic_error("No open cells to start a dead end path.");
        }
        return open_cells[rand() % open_cells.size()];
    }
    
    void Maze::generate_dead_end_path()
    {
        auto current_cell = find_dead_end_path_start();
    
        for (;;)
        {
            auto candidate_cells = generate_candidate_cells(current_cell);
            filter_candidate_cells(current_cell, candidate_cells);
            if (candidate_cells.empty())
            {
                break;
            }
    
            current_cell = candidate_cells[rand() % candidate_cells.size()];
            grid[current_cell.row][current_cell.col] = PATH_CELL;
        }
    }
    
    std::vector<Cell> Maze::generate_candidate_cells(const Cell& current_cell) const
    {
        auto candidate_cells = std::vector<Cell>();
        auto append_if_candidate = [this, &candidate_cells](size_t row, size_t col)
        {
            if (grid[row][col] == WALL_CELL)
            {
                candidate_cells.emplace_back(row, col);
            }
        };
        if (current_cell.row == 0)
        {
            if (current_cell.col == 0)
            {
                // top left corner:
                append_if_candidate(current_cell.row, current_cell.col + 1);
                append_if_candidate(current_cell.row + 1, current_cell.col);
            }
            else if (current_cell.col == col_last_index())
            {
                // top right corner:
                append_if_candidate(current_cell.row, current_cell.col - 1);
                append_if_candidate(current_cell.row + 1, current_cell.col);
            }
            else
            {
                // remaining top row:
                append_if_candidate(current_cell.row, current_cell.col - 1);
                append_if_candidate(current_cell.row, current_cell.col + 1);
                append_if_candidate(current_cell.row + 1, current_cell.col);
            }
        }
        else if (current_cell.row == row_last_index())
        {
            if (current_cell.col == 0)
            {
                // bottom left corner:
                append_if_candidate(current_cell.row - 1, current_cell.col);
                append_if_candidate(current_cell.row, current_cell.col + 1);
            }
            else if (current_cell.col == col_last_index())
            {
                // bottom right corner:
                append_if_candidate(current_cell.row - 1, current_cell.col);
                append_if_candidate(current_cell.row, current_cell.col - 1);
            }
            else
            {
                // remaining bottom row:
                append_if_candidate(current_cell.row - 1, current_cell.col);
                append_if_candidate(current_cell.row, current_cell.col - 1);
                append_if_candidate(current_cell.row, current_cell.col + 1);
            }
        }
        else if (current_cell.col == 0)
        {
            // remaining left column:
            append_if_candidate(current_cell.row - 1, current_cell.col);
            append_if_candidate(current_cell.row, current_cell.col + 1);
            append_if_candidate(current_cell.row + 1, current_cell.col);
        }
        else if (current_cell.col == col_last_index())
        {
            // remaining right column:
            append_if_candidate(current_cell.row - 1, current_cell.col);
            append_if_candidate(current_cell.row, current_cell.col - 1);
            append_if_candidate(current_cell.row + 1, current_cell.col);
        }
        else
        {
            // not at an edge:
            append_if_candidate(current_cell.row - 1, current_cell.col);
            append_if_candidate(current_cell.row, current_cell.col - 1);
            append_if_candidate(current_cell.row, current_cell.col + 1);
            append_if_candidate(current_cell.row + 1, current_cell.col);
        }
        return candidate_cells;
    }
    
    void Maze::filter_candidate_cells(const Cell& current_cell,
                                      std::vector<Cell>& candidate_cells) const
    {
        auto is_open = [this, &current_cell](size_t row, size_t col)
        {
            return !(row == current_cell.row && col == current_cell.col)
                && grid[row][col] == PATH_CELL;
        };
    
        candidate_cells.erase(
            std::remove_if(
                candidate_cells.begin(),
                candidate_cells.end(),
                [this, is_open](const Cell& cell)
                {
                    if (cell.row == 0)
                    {
                        if (cell.col == 0)
                        {
                            // top left corner:
                            return is_open(cell.row, cell.col + 1)
                                || is_open(cell.row + 1, cell.col);
                        }
                        else if (cell.col == col_last_index())
                        {
                            // top right corner:
                            return is_open(cell.row, cell.col - 1)
                                || is_open(cell.row + 1, cell.col);
                        }
                        else
                        {
                            // remaining top row:
                            return is_open(cell.row, cell.col - 1)
                                || is_open(cell.row, cell.col + 1)
                                || is_open(cell.row + 1, cell.col);
                        }
                    }
                    else if (cell.row == row_last_index())
                    {
                        if (cell.col == 0)
                        {
                            // bottom left corner:
                            return is_open(cell.row - 1, cell.col)
                                || is_open(cell.row, cell.col + 1);
                        }
                        else if (cell.col == col_last_index())
                        {
                            // bottom right corner:
                            return is_open(cell.row - 1, cell.col)
                                || is_open(cell.row, cell.col - 1);
                        }
                        else
                        {
                            // remaining bottom row:
                            return is_open(cell.row - 1, cell.col)
                                || is_open(cell.row, cell.col - 1)
                                || is_open(cell.row, cell.col + 1);
                        }
                    }
                    else if (cell.col == 0)
                    {
                        // remaining left column:
                        return is_open(cell.row - 1, cell.col)
                            || is_open(cell.row, cell.col + 1)
                            || is_open(cell.row + 1, cell.col);
                    }
                    else if (cell.col == col_last_index())
                    {
                        // remaining right column:
                        return is_open(cell.row - 1, cell.col)
                            || is_open(cell.row, cell.col - 1)
                            || is_open(cell.row + 1, cell.col);
                    }
                    else
                    {
                        // not at an edge:
                        return is_open(cell.row - 1, cell.col)
                            || is_open(cell.row, cell.col - 1)
                            || is_open(cell.row, cell.col + 1)
                            || is_open(cell.row + 1, cell.col);
                    }
                }
            ),
            candidate_cells.end()
        );
    }
    
    namespace
    {
        void print_maze_header(std::ostream& out, size_t num_cols)
        {
            for (size_t i = 0; i < num_cols + 2; ++i)
            {
                out << BOUNDARY_CELL;
            }
            out << '\n';
        }
    }
    
    std::ostream& operator<<(std::ostream& out, const Maze& maze)
    {
        print_maze_header(out, maze.grid[0].size());
        for (const auto& row : maze.grid)
        {
            out << BOUNDARY_CELL;
            for (const auto& col : row)
            {
                out << col;
            }
            out << BOUNDARY_CELL << '\n';
        }
        print_maze_header(out, maze.grid[0].size());
        return out;
    }
    
    int main()
    {
        using namespace std;
        srand((unsigned)time(NULL));
        try
        {
            auto maze = Maze(20, 40);
            maze.generate_path();
            cout << maze;
        }
        catch (const exception& e)
        {
            cerr << "Error: " << e.what() << endl;
        }
    }
    EDIT:
    Uh, I just modified my code to implement your "trying to build paths from the coordinates in the array and removes them from the array when no path is possible" idea, and yes, by being systematic about processing the path cells, it does make it such that there are no wall clusters that could be turned into paths. I continued to use random selection to choose the path cell to start the dead end path though.
    Last edited by laserlight; 2 Days Ago at 11:58 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. please help me with logic
    By Satya in forum C Programming
    Replies: 1
    Last Post: 05-21-2015, 12:47 PM
  2. Help with logic..
    By bconnor in forum C Programming
    Replies: 1
    Last Post: 05-18-2006, 07:49 PM
  3. Logic???
    By planet_abhi in forum Game Programming
    Replies: 1
    Last Post: 08-08-2003, 07:59 AM
  4. Logic?
    By planet_abhi in forum Game Programming
    Replies: 1
    Last Post: 01-18-2003, 03:46 PM
  5. logic
    By nupe02 in forum C++ Programming
    Replies: 4
    Last Post: 01-16-2003, 10:22 AM

Tags for this Thread