Maze generator/solver

[laurynas2003]

Hey,

So, I want to create a maze generator/solver with Qt. What is the best widget to make squares which will indicate walls and paths?

Added after 1 1:

Qlabels inside the layout should be fine?

[d_stranz]

Qlabels inside the layout should be fine?

It would be very painful, but you could probably do it that way.

But all of your projects are screaming "use the Qt Graphics View Framework (https://doc.qt.io/qt-5/graphicsview.html)". I think it would be worth the time for you to learn how to use this framework.

You also need to learn how to separate the program and its logic from how you display the game. In your Sudoku game, -everything- depended on the array of widgets in the display. If you found a better way to display the Sudoku board, then -everything- would have to be re-written. For your maze game, try to think of how you could create a maze as a data structure that did not depend on anything in a GUI. but was just pure data about how to represent the path through the maze from start to finish. Once you have that design, then using it as the source of data to draw the maze should be straight-forward.

Think about a tree-shaped data structure with one path from root to tip, and branches that lead to dead ends, and where at each node of the tree you can go in four directions - left, right, forward, back. Every branch where you are allowed to go next is an open wall, every place where you can't turn is a solid wall. In a tree structure, an open wall would have a child node leading to the next square, and a closed wall would have no child in that direction. To prevent circular paths in your maze, you have to make sure you don't use the same square in more than one path. If moving left, right, or forward leads to a square that is already used, then you have to put a solid wall there (by setting that child node to the null pointer).

Finding your way through such a maze is an example of "depth-first search". You start at the root, and work your way to the tip, trying each non-null child node. When you reach a dead end (a node with no non-null children), you have to go back one step and try a different child node. Eventually, by moving forward and backtracking when required, you reach the end of the maze.

[laurynas2003]

So should I make big QGraphicsRectItem and then inside that item smaller QGraphicsRectItem?

Something like that? :



// example
int height = 10;
int width = 10;

int grid_size = 10;

QGraphicsView w;

QGraphicsScene *scene = new QGraphicsScene(&w);
scene->setBackgroundBrush(Qt::yellow);

QGraphicsRectItem *rect = new QGraphicsRectItem(0, 0, 100, 100);
scene->addItem(rect);

for (int y = 0; y < grid_size; y++){
for (int x = 0; x < grid_size; x++){
QGraphicsRectItem *rect1 = new QGraphicsRectItem(x * width, y * height, width, height, rect);
}
}

w.setScene(scene);
w.resize(400, 400);
w.show();

[d_stranz]

So should I make big QGraphicsRectItem and then inside that item smaller QGraphicsRectItem?

Not exactly. A QGraphicsRectItem will draw a complete 4-sided rectangle. You need to be able to draw rectangles with one or more edges missing. You could use a QGraphicsRectItem for the outside box and make it the parent of all of the smaller boxes. That way, when it changes size, all of the boxes inside it will automatically be resized, too. If you set Qt::NoPen as the pen for this outer box, then the outline will not be drawn (which is what you want, because you need to leave openings for the entrance and exit of the maze.

For the inside boxes, you can derive a new class from QGraphicsRectItem, and override the paint() method. You could also add data members and methods to set which sides of the box are open. Then, in your paint method, you will draw lines only for the edges that are closed.

An easy way to keep a data structure for the sides is to use QFlags:



// A MazeRectItem is a 10 x 10 square (logical coordinates) with 0 - 4 closed sides
class MazeRectItem : public QGraphicsRectItem
{
public:
enum Side {
None = 0,
Left = 1,
Right = 2,
Top = 4,
Bottom = 8,
AllSides = Left | Right | Top | Bottom
};

Q_DECLARE_FLAGS( Side, Sides );

MazeRectItem( QGraphicsItem * parent ) : QGraphicsRectItem( parent ), mClosedSides( None ) { setRect( QRectF( -5.0, -5.0, 5.0, 5.0 ); }

Sides closedSides() const { return mClosedSides; }
void setClosedSides( const Sides & sides ) { mClosedSides = sides; }
void setClosedSide( const Side & side ) { mClosedSides |= side; }

bool isSideClosed( const Side & side ) const { return mClosedSides.testFlag( side ); }

void paint( QPainter * painter, const QStyleOptionGraphicsItem * option, QWidget * widget = nullptr ) override;

private:
Sides mClosedSides = None;
};

Q_DECLARE_OPERATORS_FOR_FLAGS( MazeRectItem::Sides );


and the way you use this is:



void MazeRectItem::paint( QPainter * painter, const QStyleOptionGraphicsItem * option, QWidget * widget )
{
// Save the current pen, set the pen to NoPen, then let the base class draw itself. NoPen means there will be
// no outline drawn
QPen savePen = pen();

setPen( Qt::NoPen );
QGraphicsRectItem::paint( painter, option, widget );

setPen( savePen );

if ( isSideClosed( Left ) )
{
// draw the left side
}

if ( isSideClosed( Right ) )
{
// draw the right side
}

// etc.
}


And remember for QGraphicsRectItem, the origin (0, 0 ) is the center of the rect and position (pos()) is relative to the parent of the item. So when you draw a maze rect, all you have to calculate is the position of the lines in the rect's own coordinates. If the rect has a width and height of 10, then the top line goes from (-5, -5) to (5, -5). When you put the maze rect inside another rect, all of the drawing coordinates will automatically be adjusted by the painter. You do not have to care. You just draw your 4 lines in your -5 - +5 coordinate space.

[laurynas2003]

Could you show me how to draw those walls? I can't figure out how:/



QPen savePen = pen();

setPen( Qt::NoPen );
QGraphicsRectItem::paint( painter, option, widget );

setPen( savePen );

if ( isSideClosed( Left ) )
{
// draw the left side
}

if ( isSideClosed( Right ) )
{
// draw the right side
}

// etc.

[d_stranz]

QPainter::drawLine() should do the trick.