Results 1 to 6 of 6

Thread: Maze generator/solver

  1. #1
    Join Date
    Apr 2020
    Location
    Lithuania
    Posts
    24
    Thanks
    17
    Qt products
    Qt5
    Platforms
    MacOS X

    Default Re: Maze generator/solver

    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?
    Last edited by laurynas2003; 22nd April 2020 at 11:38.

  2. #2
    Join Date
    Jan 2008
    Location
    Alameda, CA, USA
    Posts
    4,695
    Thanks
    259
    Thanked 753 Times in 743 Posts
    Qt products
    Qt5
    Platforms
    Windows Android

    Default Re: Maze generator/solver

    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". 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.
    <=== The Great Pumpkin says ===>
    Please use CODE tags when posting source code so it is more readable. Click "Go Advanced" and then the "#" icon to insert the tags. Paste your code between them.

  3. The following user says thank you to d_stranz for this useful post:

    laurynas2003 (22nd April 2020)

  4. #3
    Join Date
    Apr 2020
    Location
    Lithuania
    Posts
    24
    Thanks
    17
    Qt products
    Qt5
    Platforms
    MacOS X

    Default Re: Maze generator/solver

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

    Something like that? :

    Qt Code:
    1. // example
    2. int height = 10;
    3. int width = 10;
    4.  
    5. int grid_size = 10;
    6.  
    7.  
    8. QGraphicsScene *scene = new QGraphicsScene(&w);
    9. scene->setBackgroundBrush(Qt::yellow);
    10.  
    11. QGraphicsRectItem *rect = new QGraphicsRectItem(0, 0, 100, 100);
    12. scene->addItem(rect);
    13.  
    14. for (int y = 0; y < grid_size; y++){
    15. for (int x = 0; x < grid_size; x++){
    16. QGraphicsRectItem *rect1 = new QGraphicsRectItem(x * width, y * height, width, height, rect);
    17. }
    18. }
    19.  
    20. w.setScene(scene);
    21. w.resize(400, 400);
    22. w.show();
    To copy to clipboard, switch view to plain text mode 
    Last edited by laurynas2003; 22nd April 2020 at 21:12.

  5. #4
    Join Date
    Jan 2008
    Location
    Alameda, CA, USA
    Posts
    4,695
    Thanks
    259
    Thanked 753 Times in 743 Posts
    Qt products
    Qt5
    Platforms
    Windows Android

    Default Re: Maze generator/solver

    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:

    Qt Code:
    1. // A MazeRectItem is a 10 x 10 square (logical coordinates) with 0 - 4 closed sides
    2. class MazeRectItem : public QGraphicsRectItem
    3. {
    4. public:
    5. enum Side {
    6. None = 0,
    7. Left = 1,
    8. Right = 2,
    9. Top = 4,
    10. Bottom = 8,
    11. AllSides = Left | Right | Top | Bottom
    12. };
    13.  
    14. Q_DECLARE_FLAGS( Side, Sides );
    15.  
    16. MazeRectItem( QGraphicsItem * parent ) : QGraphicsRectItem( parent ), mClosedSides( None ) { setRect( QRectF( -5.0, -5.0, 5.0, 5.0 ); }
    17.  
    18. Sides closedSides() const { return mClosedSides; }
    19. void setClosedSides( const Sides & sides ) { mClosedSides = sides; }
    20. void setClosedSide( const Side & side ) { mClosedSides |= side; }
    21.  
    22. bool isSideClosed( const Side & side ) const { return mClosedSides.testFlag( side ); }
    23.  
    24. void paint( QPainter * painter, const QStyleOptionGraphicsItem * option, QWidget * widget = nullptr ) override;
    25.  
    26. private:
    27. Sides mClosedSides = None;
    28. };
    29.  
    30. Q_DECLARE_OPERATORS_FOR_FLAGS( MazeRectItem::Sides );
    To copy to clipboard, switch view to plain text mode 

    and the way you use this is:

    Qt Code:
    1. void MazeRectItem::paint( QPainter * painter, const QStyleOptionGraphicsItem * option, QWidget * widget )
    2. {
    3. // Save the current pen, set the pen to NoPen, then let the base class draw itself. NoPen means there will be
    4. // no outline drawn
    5. QPen savePen = pen();
    6.  
    7. setPen( Qt::NoPen );
    8. QGraphicsRectItem::paint( painter, option, widget );
    9.  
    10. setPen( savePen );
    11.  
    12. if ( isSideClosed( Left ) )
    13. {
    14. // draw the left side
    15. }
    16.  
    17. if ( isSideClosed( Right ) )
    18. {
    19. // draw the right side
    20. }
    21.  
    22. // etc.
    23. }
    To copy to clipboard, switch view to plain text mode 

    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.
    Last edited by d_stranz; 23rd April 2020 at 00:06.
    <=== The Great Pumpkin says ===>
    Please use CODE tags when posting source code so it is more readable. Click "Go Advanced" and then the "#" icon to insert the tags. Paste your code between them.

  6. The following user says thank you to d_stranz for this useful post:

    laurynas2003 (23rd April 2020)

  7. #5
    Join Date
    Apr 2020
    Location
    Lithuania
    Posts
    24
    Thanks
    17
    Qt products
    Qt5
    Platforms
    MacOS X

    Default Re: Maze generator/solver

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

    Qt Code:
    1. QPen savePen = pen();
    2.  
    3. setPen( Qt::NoPen );
    4. QGraphicsRectItem::paint( painter, option, widget );
    5.  
    6. setPen( savePen );
    7.  
    8. if ( isSideClosed( Left ) )
    9. {
    10. // draw the left side
    11. }
    12.  
    13. if ( isSideClosed( Right ) )
    14. {
    15. // draw the right side
    16. }
    17.  
    18. // etc.
    To copy to clipboard, switch view to plain text mode 

  8. #6
    Join Date
    Jan 2008
    Location
    Alameda, CA, USA
    Posts
    4,695
    Thanks
    259
    Thanked 753 Times in 743 Posts
    Qt products
    Qt5
    Platforms
    Windows Android

    Default Re: Maze generator/solver

    QPainter::drawLine() should do the trick.
    <=== The Great Pumpkin says ===>
    Please use CODE tags when posting source code so it is more readable. Click "Go Advanced" and then the "#" icon to insert the tags. Paste your code between them.

Similar Threads

  1. Qt Drawing 2d grid based maze
    By thalorn in forum Newbie
    Replies: 4
    Last Post: 20th November 2019, 07:54
  2. How to integrate lp solver to QT
    By cancelik in forum Newbie
    Replies: 5
    Last Post: 29th April 2016, 17:40
  3. Discussion on GUI and Program-Solver Interaction
    By Omid123 in forum Qt Programming
    Replies: 4
    Last Post: 23rd February 2015, 23:54

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.