Генерация лабиринта

@Deebosh401 · Регистрация: 16.10.2020

Author24 — интернет-сервис помощи студентам

Всем кодерам доброго времени суток)))
Написал код для генерации лабиринта и нахождении пути из него...Но вышел очень громоздкий..Может подскажите как можно его сократить хоть как-нибудь,оставляя структуру той же самой(использование векторов,классов и тд)?

Буду рад выслушать,а ещё лучше увидеть варианты как можно его улучшить)

C++

#include <iostream>
#include <string>
#include <random>
#include <time.h>
#include <vector>
#include <stack>
 
class CCoordinate
{
    public:
        explicit CCoordinate(int iX, int iY);
    ~CCoordinate() = default;
    bool operator==(const CCoordinate &other) const;
 
    void SetX(int iX);
    int GetX() const;
 
    void SetY(int iY);
    int GetY() const;
 
    private:
        int m_iX;
    int m_iY;
};
 
CCoordinate::CCoordinate(int iX, int iY): m_iX(iX), m_iY(iY) {}
 
bool CCoordinate::operator==(const CCoordinate &other) const
{
    return (m_iX == other.GetX()) && (m_iY == other.GetY());
}
 
void CCoordinate::SetX(int iX)
{
    m_iX = iX;
}
 
int CCoordinate::GetX() const
{
    return m_iX;
}
 
void CCoordinate::SetY(int iY)
{
    m_iY = iY;
}
 
int CCoordinate::GetY() const
{
    return m_iY;
}
 
class CCell
{
    public:
        explicit CCell();
    ~CCell() = default;
 
    void SetTopWall(bool bTopWall);
    bool GetTopWall() const;
 
    void SetLeftWall(bool bLeftWall);
    bool GetLeftWall() const;
 
    void SetRightWall(bool bRightWall);
    bool GetRightWall() const;
 
    void SetBottomWall(bool bBottomWall);
    bool GetBottomWall() const;
 
    void SetVisited(bool bVisited);
    bool GetVisited() const;
 
    void SetCoordinate(const CCoordinate &position);
    const CCoordinate &GetCoordinate() const;
 
    private:
        bool m_bTopWall;
    bool m_bLeftWall;
    bool m_bRightWall;
    bool m_bBottomWall;
    bool m_bVisited;
    CCoordinate m_position;
};
 
CCell::CCell(): m_bTopWall(true), m_bLeftWall(true), m_bRightWall(true), m_bBottomWall(true), m_bVisited(false), m_position(CCoordinate(-1, -1)) {}
 
void CCell::SetTopWall(bool bTopWall)
{
    m_bTopWall = bTopWall;
}
 
bool CCell::GetTopWall() const
{
    return m_bTopWall;
}
 
void CCell::SetLeftWall(bool bLeftWall)
{
    m_bLeftWall = bLeftWall;
}
 
bool CCell::GetLeftWall() const
{
    return m_bLeftWall;
}
 
void CCell::SetRightWall(bool bRightWall)
{
    m_bRightWall = bRightWall;
}
 
bool CCell::GetRightWall() const
{
    return m_bRightWall;
}
 
void CCell::SetBottomWall(bool bBottomWall)
{
    m_bBottomWall = bBottomWall;
}
 
bool CCell::GetBottomWall() const
{
    return m_bBottomWall;
}
 
void CCell::SetVisited(bool bVisited)
{
    m_bVisited = bVisited;
}
 
bool CCell::GetVisited() const
{
    return m_bVisited;
}
 
void CCell::SetCoordinate(const CCoordinate &position)
{
    m_position = position;
}
 
const CCoordinate &CCell::GetCoordinate() const
{
    return m_position;
}
 
enum class EDirection
{
    ED_UNKNOWN = 0,
        ED_UP = 1,
        ED_LEFT = 2,
        ED_RIGHT = 3,
        ED_DOWN = 4
};
 
class CMaze
{
    public:
        explicit CMaze(int iRows, int iColumns, int iSeed = 0, bool bUseSeed = false);
    ~CMaze() = default;
 
    std::vector<std::vector < CCell>> &GetMaze();
    const std::vector<std::vector < CCell>> &GetMaze() const;
    int GetRows() const;
    int GetColumns() const;
    std::vector<CCoordinate> GetUnvisitedNeighbours(const CCoordinate &position);
 
    private:
        void GenerateMaze(int iSeed, bool bUseSeed);
    void AllocateCapacity();
    void InitializePositionCoordinates();
    void GenerateMazeRecursive(CCell &currentCell, int &iVisitedCells, bool bStackPopped = false);
    bool AdjacentCellsVisited(const CCoordinate &position) const;
    void TidyVisitedCells();
 
    bool CanGoUp(int iY) const;
    bool CanGoLeft(int iX) const;
    bool CanGoRight(int iX) const;
    bool CanGoDown(int iY) const;
 
    EDirection GetAcceptableDirection(const CCoordinate &position) const;
 
    private:
        std::vector<std::vector < CCell>> m_vMaze;
    std::stack<CCell> m_sStackTrace;
    int m_iMazeSize;
    int m_iRows;
    int m_iColumns;
    EDirection m_eLastDirection;
};
 
CMaze::CMaze(int iRows, int iColumns, int iSeed, bool bUseSeed): m_iRows(iRows), m_iColumns(iColumns), m_iMazeSize(iRows *iColumns), m_eLastDirection(EDirection::ED_UNKNOWN)
{
    GenerateMaze(iSeed, bUseSeed);
}
 
std::vector<std::vector < CCell>> &CMaze::GetMaze()
{
    return m_vMaze;
}
 
const std::vector<std::vector < CCell>> &CMaze::GetMaze() const
{
    return m_vMaze;
}
 
int CMaze::GetRows() const
{
    return m_iRows;
}
 
int CMaze::GetColumns() const
{
    return m_iColumns;
}
 
std::vector<CCoordinate> CMaze::GetUnvisitedNeighbours(const CCoordinate &position)
{
    std::vector<CCoordinate> vNeighbours;
 
    int iY = position.GetY();
    int iX = position.GetX();
 
    if (CanGoUp(iY) &&
        m_vMaze[iY - 1][iX].GetVisited() == false)
    {
        vNeighbours.push_back(m_vMaze[iY - 1][iX].GetCoordinate());
    }
 
    if (CanGoLeft(iX) &&
        m_vMaze[iY][iX - 1].GetVisited() == false)
    {
        vNeighbours.push_back(m_vMaze[iY][iX - 1].GetCoordinate());
    }
 
    if (CanGoRight(iX) &&
        m_vMaze[iY][iX + 1].GetVisited() == false)
    {
        vNeighbours.push_back(m_vMaze[iY][iX + 1].GetCoordinate());
    }
 
    if (CanGoDown(iY) &&
        m_vMaze[iY + 1][iX].GetVisited() == false)
    {
        vNeighbours.push_back(m_vMaze[iY + 1][iX].GetCoordinate());
    }
 
    return vNeighbours;
}
 
void CMaze::GenerateMaze(int iSeed, bool bUseSeed)
{
    bUseSeed ? srand(iSeed) : srand(time(NULL));
    AllocateCapacity();
    InitializePositionCoordinates();
 
    int iVisitedCells = 0;
    GenerateMazeRecursive(m_vMaze[0][0], iVisitedCells);
    TidyVisitedCells();
}
 
void CMaze::AllocateCapacity()
{
    m_vMaze.resize(m_iRows);
    for (int i = 0; i < m_iRows; ++i)
    {
        m_vMaze[i].resize(m_iColumns);
    }
}
 
void CMaze::InitializePositionCoordinates()
{
    for (int i = 0; i < m_iRows; ++i)
    {
        for (int j = 0; j < m_iColumns; ++j)
        {
            m_vMaze[i][j].SetCoordinate(CCoordinate(j, i));
        }
    }
}
 
void CMaze::GenerateMazeRecursive(CCell &currentCell, int &iVisitedCells, bool bStackPopped)
{
    currentCell.SetVisited(true);
    if (bStackPopped == false)
    {
        ++iVisitedCells;
        switch (m_eLastDirection)
        {
            case EDirection::ED_UP:
                {
                    currentCell.SetBottomWall(false);
                }
 
                break;
            case EDirection::ED_LEFT:
                {
                    currentCell.SetRightWall(false);
                }
 
                break;
            case EDirection::ED_RIGHT:
                {
                    currentCell.SetLeftWall(false);
                }
 
                break;
            case EDirection::ED_DOWN:
                {
                    currentCell.SetTopWall(false);
                }
 
                break;
        }
    }
 
    if (iVisitedCells == m_iMazeSize)
    {
        const CCoordinate &lastCoordinate = currentCell.GetCoordinate();
        std::vector<CCoordinate> vLastCell = GetUnvisitedNeighbours(lastCoordinate);
        bool bUseLastCoordinate = vLastCell.size() > 0;
        switch (bUseLastCoordinate ? GetAcceptableDirection(lastCoordinate) : EDirection::ED_UNKNOWN)
        {
            case EDirection::ED_UP:
                {
                    currentCell.SetTopWall(false);
                    m_vMaze[lastCoordinate.GetY() - 1][lastCoordinate.GetX()].SetBottomWall(false);
                }
 
                break;
            case EDirection::ED_LEFT:
                {
                    currentCell.SetLeftWall(false);
                    m_vMaze[lastCoordinate.GetY()][lastCoordinate.GetX() - 1].SetRightWall(false);
                }
 
                break;
            case EDirection::ED_RIGHT:
                {
                    currentCell.SetRightWall(false);
                    m_vMaze[lastCoordinate.GetY()][lastCoordinate.GetX() + 1].SetLeftWall(false);
                }
 
                break;
            case EDirection::ED_DOWN:
                {
                    currentCell.SetBottomWall(false);
                    m_vMaze[lastCoordinate.GetY() + 1][lastCoordinate.GetX()].SetTopWall(false);
                }
 
                break;
        }
 
        return;
    }
 
    m_sStackTrace.push(currentCell);
 
    const CCoordinate &currentPosition = currentCell.GetCoordinate();
    if (currentCell.GetVisited() && AdjacentCellsVisited(currentPosition))
    {
        while (AdjacentCellsVisited(m_sStackTrace.top().GetCoordinate()))
        {
            m_sStackTrace.pop();
        }
 
        const CCoordinate &newPosition = m_sStackTrace.top().GetCoordinate();
        GenerateMazeRecursive(m_vMaze[newPosition.GetY()][newPosition.GetX()], iVisitedCells, true);
        return;
    }
 
    EDirection eRandomDirection = GetAcceptableDirection(currentPosition);
    m_eLastDirection = eRandomDirection;
 
    switch (eRandomDirection)
    {
        case EDirection::ED_UP:
            {
                currentCell.SetTopWall(false);
                CCell &nextCell = m_vMaze[currentPosition.GetY() - 1][currentPosition.GetX()];
                GenerateMazeRecursive(nextCell, iVisitedCells);
            }
 
            break;
        case EDirection::ED_LEFT:
            {
                currentCell.SetLeftWall(false);
                CCell &nextCell = m_vMaze[currentPosition.GetY()][currentPosition.GetX() - 1];
                GenerateMazeRecursive(nextCell, iVisitedCells);
            }
 
            break;
        case EDirection::ED_RIGHT:
            {
                currentCell.SetRightWall(false);
                CCell &nextCell = m_vMaze[currentPosition.GetY()][currentPosition.GetX() + 1];
                GenerateMazeRecursive(nextCell, iVisitedCells);
            }
 
            break;
        case EDirection::ED_DOWN:
            {
                currentCell.SetBottomWall(false);
                CCell &nextCell = m_vMaze[currentPosition.GetY() + 1][currentPosition.GetX()];
                GenerateMazeRecursive(nextCell, iVisitedCells);
            }
 
            break;
    }
}
 
bool CMaze::AdjacentCellsVisited(const CCoordinate &position) const
{
    int iCurrentX = position.GetX();
    int iCurrentY = position.GetY();
 
    if ((CanGoUp(iCurrentY) && m_vMaze[iCurrentY - 1][iCurrentX].GetVisited() == false) ||
        (CanGoLeft(iCurrentX) && m_vMaze[iCurrentY][iCurrentX - 1].GetVisited() == false) ||
        (CanGoRight(iCurrentX) && m_vMaze[iCurrentY][iCurrentX + 1].GetVisited() == false) ||
        (CanGoDown(iCurrentY) && m_vMaze[iCurrentY + 1][iCurrentX].GetVisited() == false))
    {
        return false;
    }
 
    return true;
}
 
void CMaze::TidyVisitedCells()
{
    for (int i = 0; i < m_iRows; ++i)
    {
        for (int j = 0; j < m_iColumns; ++j)
        {
            m_vMaze[i][j].SetVisited(false);
        }
    }
}
 
bool CMaze::CanGoUp(int iY) const
{
    return iY > 0;
}
 
bool CMaze::CanGoLeft(int iX) const
{
    return iX > 0;
}
 
bool CMaze::CanGoRight(int iX) const
{
    return iX < (m_iColumns - 1);
}
 
bool CMaze::CanGoDown(int iY) const
{
    return iY < (m_iRows - 1);
}
 
EDirection CMaze::GetAcceptableDirection(const CCoordinate &position) const
{
    EDirection eRandomDirection = EDirection::ED_UNKNOWN;
 
    while (true)
    {
        eRandomDirection = static_cast<EDirection> ((rand() % 4) + 1);
 
        if (eRandomDirection == EDirection::ED_UP && CanGoUp(position.GetY()) && m_vMaze[position.GetY() - 1][position.GetX()].GetVisited() == false ||
            eRandomDirection == EDirection::ED_LEFT && CanGoLeft(position.GetX()) && m_vMaze[position.GetY()][position.GetX() - 1].GetVisited() == false ||
            eRandomDirection == EDirection::ED_RIGHT && CanGoRight(position.GetX()) && m_vMaze[position.GetY()][position.GetX() + 1].GetVisited() == false ||
            eRandomDirection == EDirection::ED_DOWN && CanGoDown(position.GetY()) && m_vMaze[position.GetY() + 1][position.GetX()].GetVisited() == false)
        {
            break;
        }
    }
 
    return eRandomDirection;
}
 
EDirection GetDirection(const CCoordinate &from, const CCoordinate &to)
{
    if (from.GetX() > to.GetX())
    {
        return EDirection::ED_LEFT;
    }
 
    if (from.GetX() < to.GetX())
    {
        return EDirection::ED_RIGHT;
    }
 
    if (from.GetY() > to.GetY())
    {
        return EDirection::ED_UP;
    }
 
    if (from.GetY() < to.GetY())
    {
        return EDirection::ED_DOWN;
    }
 
    return EDirection::ED_UNKNOWN;
}
 
bool findPath(CMaze &maze, const CCoordinate &from, const CCoordinate &to)
{
    std::vector<std::vector < CCell>> &vMaze = maze.GetMaze();
    vMaze[from.GetY()][from.GetX()].SetVisited(true);
 
    if (from == to)
    {
        return true;
    }
 
    std::vector<CCoordinate> vNeighbours = maze.GetUnvisitedNeighbours(from);
    int iSize = vNeighbours.size();
    for (int i = 0; i < iSize; ++i)
    {
        const CCoordinate &neighbour = vNeighbours[i];
        CCell &neighbourCell = vMaze[neighbour.GetY()][neighbour.GetX()];
        EDirection direction = GetDirection(from, neighbour);
        bool bIsWallObstructing = false;
 
        switch (direction)
        {
            case EDirection::ED_UP:
                {
                    bIsWallObstructing = neighbourCell.GetBottomWall();
                }
 
                break;
            case EDirection::ED_LEFT:
                {
                    bIsWallObstructing = neighbourCell.GetRightWall();
                }
 
                break;
            case EDirection::ED_RIGHT:
                {
                    bIsWallObstructing = neighbourCell.GetLeftWall();
                }
 
                break;
            case EDirection::ED_DOWN:
                {
                    bIsWallObstructing = neighbourCell.GetTopWall();
                }
 
                break;
        }
 
        if (neighbourCell.GetVisited() == false && bIsWallObstructing == false)
        {
            if (findPath(maze, neighbour, to))
            {
                return true;
            }
        }
    }
 
    vMaze[from.GetY()][from.GetX()].SetVisited(false);
    return false;
}
 
void PrintMaze(const CMaze &maze)
{
    const std::vector<std::vector < CCell>> &vMaze = maze.GetMaze();
 
    std::string sFirstThirdRow = "";
    std::string sSecondThirdRow = "";
    std::string sThirdThirdRow = "";
    bool bFirstThirdPrintedOnce = false;
 
    int iRows = maze.GetRows();
    int iColumns = maze.GetColumns();
 
    for (int i = 0; i < iRows; ++i)
    {
        for (int j = 0; j < iColumns; ++j)
        {
            const CCell &cell = vMaze[i][j];
            if (j == 0)
            {
                sFirstThirdRow += "+";
            }
 
            cell.GetTopWall() ? sFirstThirdRow += "---" : sFirstThirdRow += "   ";
            sFirstThirdRow += "+";
 
            if (j == 0)
            {
                cell.GetLeftWall() ? sSecondThirdRow += "|" : sSecondThirdRow += " ";
            }
 
            cell.GetVisited() ? sSecondThirdRow += " . " : sSecondThirdRow += "   ";
            cell.GetRightWall() ? sSecondThirdRow += "|" : sSecondThirdRow += " ";
 
            if (j == 0)
            {
                sThirdThirdRow += "+";
            }
 
            cell.GetBottomWall() ? sThirdThirdRow += "---" : sThirdThirdRow += "   ";
            sThirdThirdRow += "+";
        }
 
        if (bFirstThirdPrintedOnce == false)
        {
            std::cout << sFirstThirdRow << std::endl;
            bFirstThirdPrintedOnce = true;
        }
 
        std::cout << sSecondThirdRow << std::endl;
        std::cout << sThirdThirdRow << std::endl;
 
        sFirstThirdRow = "";
        sSecondThirdRow = "";
        sThirdThirdRow = "";
    }
}
 
int main(int argc, char **argv)
{
    int iRows = 0;
    int iColumns = 0;
    int iSeed = 0;
    bool bUseSeed = false;
 
    switch (argc)
    {
        case 0:
        case 1:
        case 2:
            {
                return -1;
            }
 
        case 3:
            {
                iRows = std::atoi(argv[1]);
                iColumns = std::atoi(argv[2]);
            }
 
            break;
        case 4:
            {
                iRows = std::atoi(argv[1]);
                iColumns = std::atoi(argv[2]);
                iSeed = std::atoi(argv[3]);
                bUseSeed = true;
            }
    }
 
    CMaze maze(iRows, iColumns, iSeed, bUseSeed);
    findPath(maze, CCoordinate(0, 0), CCoordinate(iColumns - 1, iRows - 1));
    PrintMaze(maze);
 
    return 0;
}

	17.10.2022, 16:31