Thread: Need help with logic..

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;
    }
}

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.

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:



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.

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.

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"?

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.

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.

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.

Originally Posted by Nwb

where am I missing delete[]?

The only two places where you invoke delete[] is in add_coordinates and remove_coordinates. You didn't call remove_coordinates, so that means only add_coordinates is relevant. But you use new[] not only for coordinates, but also for p_p_maze and maze[i], and then when you're done with covered_path you do not invoke delete[] on it.

Originally Posted by Nwb

In the snippet below, I thought that removing the comment would mean that there would no longer be any memory at all that is allocated?

Removing the comment would indeed be wrong.

Ohhh you mean for p_p_maze and covered_path.. that makes sense. Thanks.

I will edit this post a little later with regards to the maze generator.