none
Recursive Backtracker Maze RRS feed

  • General discussion

  • Greetings! It's been a while! I hope everyone is doing well here!

    I just wanted to drop in to say hi and share a little fun. 

    I'd like to see implementations of other maze generation algorithims, if anyone feels like it!

    MSDN Gallery Sample(VB.net & C#)

    Also available on my website in Javascript

    Option Strict On
    Option Explicit On
    Option Infer Off
    Public Class Form1
        Sub doLayout()
            Panel2.Top = 100
            Panel2.Left = 0
            Panel2.Height = Me.ClientRectangle.Height - Panel2.Top
            Panel2.Width = Me.ClientRectangle.Width
            Panel2.BorderStyle = BorderStyle.FixedSingle
        End Sub
        Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
            doLayout()
        End Sub
        Private Sub Form1_Resize(sender As Object, e As EventArgs) Handles Me.Resize
            doLayout()
        End Sub
        Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
            Dim maze As New Maze(CInt(nudRows.Value), CInt(nudCols.Value), CInt(nudWidth.Value), CInt(nudHeight.Value))
            AddHandler maze.MazeComplete, Sub(m As Image)
                                              Panel1.BackgroundImage = m
                                              Panel1.BackgroundImageLayout = ImageLayout.None
                                              Panel1.Width = m.Width
                                              Panel1.Height = m.Height
                                              'maze.PrintMaze()
                                          End Sub
            maze.Generate()
    
        End Sub
    End Class
    Public Class Maze
        Inherits Control
        Dim Rows As Integer
        Dim Columns As Integer
        Dim cellWidth As Integer
        Dim cellHeight As Integer
        Dim cells As New Dictionary(Of String, Cell)
        Dim stack As New Stack(Of Cell)
        Public Maze As Image
    
        Public Event MazeComplete(Maze As Image)
        Private Event CallComplete(Maze As Image)
        Public Shadows ReadOnly Property Bounds As Rectangle
            Get
                Dim rect As New Rectangle(0, 0, Width, Height)
                Return rect
            End Get
        End Property
        Dim WithEvents printDoc As New Printing.PrintDocument()
        Private Sub PrintImage(ByVal sender As Object, ByVal e As System.Drawing.Printing.PrintPageEventArgs) Handles printDoc.PrintPage
            Dim nonprinters As List(Of String) = ({"Send To OneNote 2013", "PDFCreator", "PDF Architect 4",
                                   "Microsoft XPS Document Writer", "Microsoft Print to PDF", "Fax", "-"}).ToList
            Dim printerName As String = "none"
            For Each a As String In System.Drawing.Printing.PrinterSettings.InstalledPrinters
                If nonprinters.IndexOf(a) > -1 Then Continue For
                printerName = a
            Next
            If printerName = "none" Then Exit Sub
            printDoc.PrinterSettings.PrinterName = printerName
            Dim imageLeft As Integer = CInt(e.PageBounds.Width / 2) - CInt(Maze.Width / 2)
            Dim imageTop As Integer = CInt(e.PageBounds.Height / 2) - CInt(Maze.Height / 2)
            e.Graphics.DrawImage(Maze, imageLeft, imageTop)
        End Sub
        Public Sub PrintMaze()
            printDoc.Print()
        End Sub
        Public Sub Generate()
            Dim c As Integer = 0
            Dim r As Integer = 0
            For y As Integer = 0 To Height Step cellHeight
                For x As Integer = 0 To Width Step cellWidth
                    Dim cell As New Cell(New Point(x, y), New Size(cellWidth, cellHeight), cells, r, c, (Rows - 1), (Columns - 1))
                    c += 1
                Next
                c = 0 : r += 1
            Next
            Dim thread As New Threading.Thread(AddressOf Dig)
            thread.Start()
        End Sub
        Function CountVisitedCells() As Integer
            Dim count As Integer = 0
            For Each cell As KeyValuePair(Of String, Cell) In cells
                If cell.Value.Visited Then
                    count += 1
                End If
            Next
            Return count
        End Function
        Private Sub Dig()
            Dim r As Integer = 0
            Dim c As Integer = 0
            Dim key As String = "c" & 5 & "r" & 5
            Dim startCell As Cell = cells(key)
            stack.Clear()
            startCell.Visited = True
            Dim visitedCells As Integer = 0
            Do
                startCell = startCell.Dig(stack)
                startCell.Visited = True
                startCell.Pen = Pens.Black
                visitedCells = CountVisitedCells()
            Loop Until visitedCells >= Rows * Columns
            stack.Clear()
            Dim Maze As New Bitmap(Width, Height)
            Using g As Graphics = Graphics.FromImage(Maze)
                g.Clear(Color.White)
                If cells.Count > 0 Then
                    For r = 0 To Me.Rows - 1
                        For c = 0 To Me.Columns - 1
                            Dim cell As Cell = cells("c" & c & "r" & r)
                            cell.draw(g)
                        Next
                    Next
                End If
            End Using
            Me.Maze = Maze
            RaiseEvent CallComplete(Maze)
        End Sub
        Delegate Sub dComplete(maze As Image)
        Private Sub Call_Complete(maze As Image) Handles Me.CallComplete
            If Me.InvokeRequired Then
                Me.Invoke(New dComplete(AddressOf Call_Complete), maze)
            Else
                RaiseEvent MazeComplete(maze)
            End If
        End Sub
        Sub New(rows As Integer, columns As Integer, cellWidth As Integer, cellHeight As Integer)
            Me.Rows = rows
            Me.Columns = columns
            Me.cellWidth = cellWidth
            Me.cellHeight = cellHeight
            Me.Width = (Me.Columns * Me.cellWidth) + 1
            Me.Height = (Me.Rows * Me.cellHeight) + 1
            Me.CreateHandle()
        End Sub
    End Class
    Public Class Cell
        Public NorthWall As Boolean = True
        Public SouthWall As Boolean = True
        Public WestWall As Boolean = True
        Public EastWall As Boolean = True
        Public id As String '
        Public Pen As Pen = Pens.Black
        Public Bounds As Rectangle '
        Public Cells As Dictionary(Of String, Cell) '
        Public Column As Integer '
        Public Row As Integer '
        Public NeighborNorthID As String '
        Public NeighborSouthID As String '
        Public NeighborEastID As String '
        Public NeighborWestID As String '
        Public Visited As Boolean = False '
        Public Stack As Stack(Of Cell) '
        Public Sub draw(g As Graphics)
            If NorthWall Then g.DrawLine(Pen, New Point(Bounds.Left, Bounds.Top), New Point(Bounds.Right, Bounds.Top))
            If SouthWall Then g.DrawLine(Pen, New Point(Bounds.Left, Bounds.Bottom), New Point(Bounds.Right, Bounds.Bottom))
            If WestWall Then g.DrawLine(Pen, New Point(Bounds.Left, Bounds.Top), New Point(Bounds.Left, Bounds.Bottom))
            If EastWall Then g.DrawLine(Pen, New Point(Bounds.Right, Bounds.Top), New Point(Bounds.Right, Bounds.Bottom))
        End Sub
        Sub New(location As Point, size As Size, ByRef cellList As Dictionary(Of String, Cell), r As Integer, c As Integer, maxR As Integer, maxC As Integer)
            Me.Bounds = New Rectangle(location, size)
            Me.Column = c
            Me.Row = r
            Me.id = "c" & c & "r" & r
            Dim rowNort As Integer = r - 1
            Dim rowSout As Integer = r + 1
            Dim colEast As Integer = c + 1
            Dim colWest As Integer = c - 1
            NeighborNorthID = "c" & c & "r" & rowNort
            NeighborSouthID = "c" & c & "r" & rowSout
            NeighborEastID = "c" & colEast & "r" & r
            NeighborWestID = "c" & colWest & "r" & r
            If rowNort < 0 Then NeighborNorthID = "none"
            If rowSout > maxR Then NeighborSouthID = "none"
            If colEast > maxC Then NeighborEastID = "none"
            If colWest < 0 Then NeighborWestID = "none"
            Me.Cells = cellList
            Me.Cells.Add(Me.id, Me)
        End Sub
        Function getNeighbor() As Cell
            Dim c As New List(Of Cell)
            If Not NeighborNorthID = "none" AndAlso Cells(NeighborNorthID).Visited = False Then c.Add(Cells(NeighborNorthID))
            If Not NeighborSouthID = "none" AndAlso Cells(NeighborSouthID).Visited = False Then c.Add(Cells(NeighborSouthID))
            If Not NeighborEastID = "none" AndAlso Cells(NeighborEastID).Visited = False Then c.Add(Cells(NeighborEastID))
            If Not NeighborWestID = "none" AndAlso Cells(NeighborWestID).Visited = False Then c.Add(Cells(NeighborWestID))
            Dim max As Integer = c.Count
            Dim currentCell As Cell = Nothing
            If c.Count > 0 Then
                Randomize()
                Dim index As Integer = CInt(Int(c.Count * Rnd()))
                currentCell = c(index)
            End If
            Return currentCell
        End Function
        Function Dig(ByRef stack As Stack(Of Cell)) As Cell
            Me.Stack = stack
            Dim nextCell As Cell = getNeighbor()
            If Not nextCell Is Nothing Then
                stack.Push(nextCell)
                If nextCell.id = Me.NeighborNorthID Then
                    Me.NorthWall = False
                    nextCell.SouthWall = False
                ElseIf nextCell.id = Me.NeighborSouthID
                    Me.SouthWall = False
                    nextCell.NorthWall = False
                ElseIf nextCell.id = Me.NeighborEastID
                    Me.EastWall = False
                    nextCell.WestWall = False
                ElseIf nextCell.id = Me.NeighborWestID
                    Me.WestWall = False
                    nextCell.EastWall = False
                End If
            ElseIf Not stack.Count = 0
                nextCell = stack.Pop
            End If
            Return nextCell
        End Function
    End Class


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.







    Wednesday, October 26, 2016 4:03 AM
    Moderator

All replies

  • Hi Paul!

    I dont have any maze generators but here is a simple shell I made a while ago to play them if modified just to have something to say.

    :)

    Imports System.Drawing.Drawing2D
    
    Public Class GameMaze
        Private WithEvents Timer1 As New System.Windows.Forms.Timer With {.Interval = 200, .Enabled = False}
        Private WithEvents Timer2 As New System.Windows.Forms.Timer With {.Interval = 200, .Enabled = False}
        Private WithEvents GroupBox2 As New System.Windows.Forms.Panel With {.Parent = Me, .Location = New Point(60, 70), .Size = New Size(200, 100), .Visible = False, .BackColor = Color.Teal, .ForeColor = Color.White}
        Private WithEvents Label2 As New System.Windows.Forms.Label With {.Parent = GroupBox2, .Location = New Point(10, 10), .Size = New Size(180, 55), .Font = New Font("Arial", 10, FontStyle.Bold)}
        Private WithEvents ButtonReset As New System.Windows.Forms.Button With {.Parent = GroupBox2, .Location = New Point(30, 70), .Name = "ButtonReset"}
        Private WithEvents ButtonEnd As New System.Windows.Forms.Button With {.Parent = GroupBox2, .Location = New Point(110, 70), .Name = "ButtonEnd"}
        Private SW As New Stopwatch
        Private Pathlist As New List(Of Drawing2D.GraphicsPath)
        Private Walllist As New List(Of Drawing2D.GraphicsPath)
        Private wallsState As Boolean = True
        Private MouseDownState, CollisionColor As Boolean
    
        Private Sub Form2_Load(sender As Object, e As EventArgs) Handles MyBase.Load
            Size = New Size(300, 300)
            DoubleBuffered = True
    
            MakeWall(30, 30, 170, 40)
            MakeWall(160, 70, 170, 190)
            MakeWall(160, 160, 250, 190)
            MakeWall(30, 80, 110, 90)
            MakeWall(110, 80, 120, 200)
            MakeWall(110, 230, 250, 260)
            MakeWall(30, 140, 90, 230)
            MakeWall(210, 30, 250, 90)
        End Sub
    
        Private Sub MakeWall(x1 As Integer, y1 As Integer, x2 As Integer, y2 As Integer)
            Dim gpath As New Drawing2D.GraphicsPath
            gpath.AddLine(New Point(x1, y1), New Point(x1, y2))
            gpath.AddLine(New Point(x1, y2), New Point(x2, y2))
            gpath.AddLine(New Point(x2, y2), New Point(x2, y1))
            gpath.AddLine(New Point(x2, y1), New Point(x1, y1))
            Walllist.Add(gpath)
        End Sub
    
        Private Sub Form2_MouseDown(sender As Object, e As MouseEventArgs) Handles MyBase.MouseDown
            If e.X > 20 Or e.Y > 100 Then Return
    
            Dim gpath As New Drawing2D.GraphicsPath
            gpath.AddLine(New Point(e.X, e.Y), New Point(e.X, e.Y))
            Pathlist.Add(gpath)
            MouseDownState = True
            Timer2.Start()
            SW.Reset()
            SW.Start()
        End Sub
    
        Private Sub Form2_MouseMove(sender As Object, e As MouseEventArgs) Handles MyBase.MouseMove
            If MouseDownState Then
                If Pathlist.Count = 0 Then Return
    
                For Each thispath In Walllist
                    If thispath.IsVisible(e.X, e.Y) Then
                        CollisionColor = True
                        GroupBox2.Visible = True
                        Label2.Text = "You hit the wall." & vbLf & "  Game Over."
                        ButtonReset.Text = "Reset"
                        ButtonEnd.Text = "End"
                        MouseDownState = False
                        SW.Stop()
                        Timer2.Stop()
                    End If
                Next
    
                If e.X > 260 And e.Y > 200 Then
                    Timer1.Start()
                    GroupBox2.Visible = True
                    Label2.Text = "You Win !!" & vbLf & "  Play again?"
                    ButtonReset.Text = "Yes"
                    ButtonEnd.Text = "No"
                    MouseDownState = False
                    SW.Stop()
                    Timer2.Stop()
                End If
    
                Dim apoint As PointF = New PointF(e.X, e.Y)
                Dim lastpoint As PointF = Pathlist(Pathlist.Count - 1).PathPoints(Pathlist(Pathlist.Count - 1).PathPoints.Count - 1)
                Pathlist(Pathlist.Count - 1).AddLine(lastpoint, apoint)
    
                Me.Refresh()
            End If
        End Sub
    
        Private Sub Form2_MouseUp(sender As Object, e As MouseEventArgs) Handles MyBase.MouseUp
            MouseDownState = False
        End Sub
    
        Private Sub Form2_Paint(sender As Object, e As PaintEventArgs) Handles MyBase.Paint
            With e.Graphics
                If CollisionColor Then .Clear(Color.Red) Else .Clear(Color.Black)
                .SmoothingMode = SmoothingMode.AntiAlias
    
                If wallsState Then
                    For Each thispath In Walllist
                        .FillPath(Brushes.SteelBlue, thispath)
                        .DrawPath(Pens.White, thispath)
                    Next
                End If
    
                For Each thispath In Pathlist
                    .DrawPath(New Pen(Color.Goldenrod, 3), thispath)
                Next
    
                Using theFont As Font = New Font(New FontFamily("Tahoma"), 24, FontStyle.Bold, Drawing.GraphicsUnit.Pixel), _
                    theBrush As Brush = New SolidBrush(Color.Goldenrod)
                    .TranslateTransform(0, 100)
                    .RotateTransform(-90)
                    .DrawString("Start", theFont, theBrush, 0, 0)
                    .ResetTransform()
                    .TranslateTransform(.VisibleClipBounds.Width - 30, 250)
                    .RotateTransform(-90)
                    .DrawString("Finish", theFont, theBrush, 0, 0)
                End Using
            End With
        End Sub
    
        Private Sub Timer1_Tick(sender As Object, e As EventArgs) Handles Timer1.Tick
            wallsState = Not wallsState
            Me.Invalidate()
        End Sub
    
        Private Sub Timer2_Tick(sender As Object, e As EventArgs) Handles Timer2.Tick
            If SW.IsRunning Then Text = SW.ElapsedMilliseconds.ToString Else Text = "Maze Game"
        End Sub
    
        Private Sub Buttons_Click(sender As Object, e As EventArgs) Handles ButtonReset.Click, ButtonEnd.Click
            Select Case CType(sender, Button).Name
                Case "ButtonReset"
                    Pathlist.Clear()
                    GroupBox2.Visible = False
                    CollisionColor = False
                    wallsState = True
                    Text = "0"
                    Timer1.Stop()
                    SW.Reset()
                    SW.Start()
                    Me.Invalidate()
                Case "ButtonEnd"
                    Me.Close()
            End Select
        End Sub
    End Class

    Wednesday, October 26, 2016 1:05 PM
  • Hi Paul!

    I dont have any maze generators but here is a simple shell I made a while ago to play them if modified just to have something to say.

    :)


    Tommy that's good, not sure how I'd implement it. I still plan on  implementing a backtracking solver algorithm...

    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Wednesday, October 26, 2016 8:02 PM
    Moderator
  • Tommy, ... oh, I once did something similar as a test of motoric capabilities (as far as I remember as a suggestion/help_idea for a developer in a medicine related environment) ...

    @ Paul: I also dont have any maze generators or maze games made yet... but I also just wanted to say something, so first I say "Hi Paul" :-), I'll play around with your code...

    Here a copy paste version...

    Draw a path on the left pane, follow it on the right one.

    Option Strict On
    
    Imports System.Drawing.Drawing2D
    
    Public Class Form1
        Private _gPath As GraphicsPath = Nothing
        Private _punkte As List(Of PointF) = New List(Of PointF)
        Private _tracking As Boolean = False
    
        Private _gPath2 As GraphicsPath = Nothing
        Private _punkte2 As List(Of PointF) = New List(Of PointF)
        Private _tracking2 As Boolean = False
    
        Private _tooFar As Boolean = False
        Private _played As Boolean = False
        Private _games_Won As Integer = 0
        Private _games_Lost As Integer = 0
        Private _playing_Time As Integer = 5000
    
        Const TOLERANCE As Integer = 20
        Const PLAYING_TIME As Integer = 15000
    
        Public Sub New()
            InitializeComponent()
            Init()
        End Sub
    
        Private Sub DBpanel1_Paint(ByVal sender As System.Object, ByVal e As System.Windows.Forms.PaintEventArgs) Handles DbPanel1.Paint
            If (Not _gPath Is Nothing) Then
                e.Graphics.PixelOffsetMode = PixelOffsetMode.None
                e.Graphics.DrawPath(Pens.Black, _gPath)
            End If
            If Not _punkte Is Nothing AndAlso _punkte.Count > 2 Then
                Using gP As New GraphicsPath()
                    Using fpen = New Pen(Color.Blue, 1)
                        gP.AddLines(_punkte.ToArray())
                        e.Graphics.DrawPath(fpen, gP)
                    End Using
                End Using
            End If
        End Sub
    
        Private Sub DBpanel1_MouseDown(ByVal sender As System.Object, ByVal e As System.Windows.Forms.MouseEventArgs) Handles DbPanel1.MouseDown
            'always start a new figure
            _punkte.Clear()
            If (Not _gPath Is Nothing) Then
                _gPath.Dispose()
                _gPath = Nothing
            End If
            If (Not _gPath2 Is Nothing) Then
                _gPath2.Dispose()
                _gPath2 = Nothing
            End If
    
            Me._tooFar = False
    
            Me.DbPanel1.Invalidate()
            Me.DbPanel2.Invalidate()
    
            _punkte.Add(New Point(e.X, e.Y))
            _tracking = True
        End Sub
    
        Private Sub DBpanel1_MouseMove(ByVal sender As System.Object, ByVal e As System.Windows.Forms.MouseEventArgs) Handles DbPanel1.MouseMove
            If _tracking Then
                _punkte.Add(New Point(e.X, e.Y))
                Me.DbPanel1.Invalidate()
            End If
        End Sub
    
        Private Sub DBpanel1_MouseUp(ByVal sender As System.Object, ByVal e As System.Windows.Forms.MouseEventArgs) Handles DbPanel1.MouseUp
            If (Not _gPath Is Nothing) Then
                _gPath.Dispose()
                _gPath = Nothing
            End If
            _gPath = New GraphicsPath()
            _gPath.FillMode = FillMode.Winding
            _gPath.AddLines(_punkte.ToArray())
            Me.DbPanel1.Invalidate()
            'show help/tolerance area, remove this if not needed
            Me.DbPanel2.Invalidate()
            _tracking = False
        End Sub
    
        Private Sub DBpanel2_Paint(ByVal sender As System.Object, ByVal e As System.Windows.Forms.PaintEventArgs) Handles DbPanel2.Paint
            If (Not _gPath Is Nothing) Then
                e.Graphics.PixelOffsetMode = PixelOffsetMode.None
                Using fpen As Pen = New Pen(Color.Gray, TOLERANCE)
                    If _tooFar Then
                        e.Graphics.FillRectangle(Brushes.Aqua, Me.DbPanel2.ClientRectangle)
    
                        If (_punkte2.Count > 0) Then
                            If (Not _gPath2 Is Nothing) Then
                                _gPath2.Dispose()
                                _gPath2 = Nothing
                            End If
                            _gPath2 = New GraphicsPath()
                            _gPath2.AddLines(_punkte2.ToArray())
                        End If
    
                        If _played = False Then
                            Me.Invoke(New Action(AddressOf DoBeep))
                            _played = True
                            _tracking2 = False
                        End If
                    Else
                        e.Graphics.DrawPath(fpen, _gPath)
                        'e.Graphics.DrawPath(Pens.Blue, _gPath)
                        If (Not _gPath Is Nothing) AndAlso (_gPath.PathPoints.Length > 1) Then
                            e.Graphics.FillEllipse(Brushes.DarkGray, New RectangleF(_gPath.PathPoints(0).X - (TOLERANCE \ 2),
                                                                                    _gPath.PathPoints(0).Y - (TOLERANCE \ 2), TOLERANCE, TOLERANCE))
    
                            Dim szs As SizeF = e.Graphics.MeasureString("Start", Me.Font)
                            e.Graphics.DrawString("Start", Me.Font, Brushes.Black, New PointF(_gPath.PathPoints(0).X - szs.Width / 2.0F,
                                                                                              _gPath.PathPoints(0).Y - szs.Height / 2.0F))
    
                            e.Graphics.FillEllipse(Brushes.DarkGray, New RectangleF(_gPath.PathPoints(_gPath.PathPoints.Length - 1).X - TOLERANCE \ 2,
                                                                                    _gPath.PathPoints(_gPath.PathPoints.Length - 1).Y - TOLERANCE \ 2,
                                                                                    TOLERANCE, TOLERANCE))
    
                            Dim sze As SizeF = e.Graphics.MeasureString("End", Me.Font)
                            e.Graphics.DrawString("End", Me.Font, Brushes.Black, New PointF(_gPath.PathPoints(_gPath.PathPoints.Length - 1).X - szs.Width / 2.0F,
                                                                                              _gPath.PathPoints(_gPath.PathPoints.Length - 1).Y - szs.Height / 2.0F))
                        End If
                    End If
                End Using
                If Not _punkte2 Is Nothing AndAlso _punkte2.Count > 2 Then
                    Using gP As New GraphicsPath()
                        Using fpen = New Pen(Color.Blue, 1)
                            gP.AddLines(_punkte2.ToArray())
                            e.Graphics.DrawPath(fpen, gP)
                        End Using
                    End Using
                End If
            End If
            If (Not _gPath2 Is Nothing) Then
                If _tooFar Then
                    e.Graphics.DrawPath(Pens.Red, _gPath2)
                Else
                    e.Graphics.DrawPath(Pens.Black, _gPath2)
                End If
            End If
        End Sub
    
        Private Sub DBpanel2_MouseDown(ByVal sender As System.Object, ByVal e As System.Windows.Forms.MouseEventArgs) Handles DbPanel2.MouseDown
            'always start a new figure
            _punkte2.Clear()
            If (Not _gPath2 Is Nothing) Then
                _gPath2.Reset()
            End If
            Me.DbPanel2.Invalidate()
    
            Me.Text = "playing..."
    
            _played = False
    
            Me.DbPanel2.Invalidate()
    
            If (CheckStartPos(e.X, e.Y)) Then
                _punkte2.Add(New Point(e.X, e.Y))
                _tracking2 = True
                Me._playing_Time = PLAYING_TIME
                Me.Timer1.Start()
            Else
                DoPaintOnFault()
            End If
        End Sub
    
        Private Sub DBpanel2_MouseMove(ByVal sender As System.Object, ByVal e As System.Windows.Forms.MouseEventArgs) Handles DbPanel2.MouseMove
            If _tracking2 Then
                _punkte2.Add(New Point(e.X, e.Y))
    
                Me.DbPanel2.Invalidate()
    
                If (CheckValues(e.X, e.Y) = False) Then
                    DoPaintOnFault()
                End If
            End If
        End Sub
    
        Private Sub DBpanel2_MouseUp(ByVal sender As System.Object, ByVal e As System.Windows.Forms.MouseEventArgs) Handles DbPanel2.MouseUp
            If (Not _gPath2 Is Nothing) Then
                _gPath2.Dispose()
                _gPath2 = Nothing
            End If
            If (_punkte2.Count > 0) Then
                _gPath2 = New GraphicsPath()
                _gPath2.AddLines(_punkte2.ToArray())
                Me.DbPanel2.Invalidate()
            End If
            _tracking2 = False
    
            If CheckEndPos(e.X, e.Y) And _playing_Time > 0 Then
                _games_Won += 1
                Me.Text = "Good!"
            Else
                DoPaintOnFault()
                _games_Lost += 1
                Me.Text = "You lost!"
            End If
    
            Me.Timer1.Stop()
        End Sub
    
        Private Function CheckValues(ByVal x As Integer, ByVal y As Integer) As Boolean
            If Not _gPath Is Nothing AndAlso _gPath.PathPoints.Count > 0 Then
                Using fpen As Pen = New Pen(Color.Red, TOLERANCE)
                    fpen.StartCap = LineCap.Round
                    fpen.EndCap = LineCap.Round
                    If _gPath.IsOutlineVisible(New Point(x, y), fpen) Then
                        Return True
                    Else
                        Return False
                    End If
                End Using
            Else
                Return False
            End If
        End Function
    
        Private Sub DoBeep()
            Media.SystemSounds.Beep.Play()
        End Sub
    
        Private Function CheckStartPos(ByVal x As Integer, ByVal y As Integer) As Boolean
            If (Not _gPath Is Nothing) AndAlso (_gPath.PathPoints.Length > 1) Then
                Dim r As RectangleF = New RectangleF(_gPath.PathPoints(0).X - (TOLERANCE \ 2),
                     _gPath.PathPoints(0).Y - (TOLERANCE \ 2), TOLERANCE, TOLERANCE)
    
                Dim fPath As GraphicsPath = New GraphicsPath()
                fPath.AddEllipse(r)
    
                If fPath.IsVisible(x, y) Then
                    fPath.Dispose()
                    Return True
                End If
    
                fPath.Dispose()
            End If
    
            Return False
        End Function
    
        Private Function CheckEndPos(ByVal x As Integer, ByVal y As Integer) As Boolean
            If (Not _gPath Is Nothing) AndAlso (_gPath.PathPoints.Length > 1) Then
                Dim r As RectangleF = New RectangleF(_gPath.PathPoints(_gPath.PathPoints.Length - 1).X - (TOLERANCE \ 2),
                     _gPath.PathPoints(_gPath.PathPoints.Length - 1).Y - (TOLERANCE \ 2), TOLERANCE, TOLERANCE)
    
                Dim fPath As GraphicsPath = New GraphicsPath()
                fPath.AddEllipse(r)
    
                If fPath.IsVisible(x, y) Then
                    fPath.Dispose()
                    Return True
                End If
    
                fPath.Dispose()
            End If
    
            Return False
        End Function
    
        Private Sub DoPaintOnFault()
            _tooFar = True
            Using g As Graphics = Me.DbPanel2.CreateGraphics()
                Me.InvokePaint(Me.DbPanel2, New PaintEventArgs(g, Me.DbPanel2.ClientRectangle))
            End Using
        End Sub
    
        Private Sub Timer1_Tick(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Timer1.Tick
            Me.Timer1.Stop()
            _playing_Time -= Me.Timer1.Interval
            Me.Text = "playing... - time remaining: " & _playing_Time.ToString()
    
            If _playing_Time <= 0 Then
                DoPaintOnFault()
                Me.Text = "You lost!"
            Else
                Me.Timer1.Start()
            End If
        End Sub
    
        Protected Overrides Function ProcessCmdKey(ByRef msg As System.Windows.Forms.Message, ByVal keyData As System.Windows.Forms.Keys) As Boolean
            If keyData = Keys.R Then
                _punkte2.Clear()
                If (Not _gPath2 Is Nothing) Then
                    _gPath2.Reset()
                End If
                _tooFar = False
                _played = False
    
                Me.DbPanel2.Invalidate()
                Return True
            End If
    
            If keyData = Keys.S Then
                MessageBox.Show("Won:" & vbTab & _games_Won.ToString() & vbCrLf & "Lost:" & vbTab & _games_Lost.ToString())
                Return True
            End If
    
            Return MyBase.ProcessCmdKey(msg, keyData)
        End Function
    
        Private Sub Form1_FormClosing(ByVal sender As System.Object, ByVal e As System.Windows.Forms.FormClosingEventArgs) Handles MyBase.FormClosing
            MessageBox.Show("Won:" & vbTab & _games_Won.ToString() & vbCrLf & "Lost:" & vbTab & _games_Lost.ToString())
    
            If Not Me._gPath Is Nothing Then
                Me._gPath.Dispose()
            End If
    
            If Not Me._gPath2 Is Nothing Then
                Me._gPath2.Dispose()
            End If
        End Sub
    
        Private Sub Init()
            Me.components = New System.ComponentModel.Container()
            Me.SplitContainer1 = New System.Windows.Forms.SplitContainer()
            Me.Timer1 = New System.Windows.Forms.Timer(Me.components)
            Me.DbPanel1 = New DBPanel()
            Me.DbPanel2 = New DBPanel()
            CType(Me.SplitContainer1, System.ComponentModel.ISupportInitialize).BeginInit()
            Me.SplitContainer1.Panel1.SuspendLayout()
            Me.SplitContainer1.Panel2.SuspendLayout()
            Me.SplitContainer1.SuspendLayout()
            Me.SuspendLayout()
            '
            'SplitContainer1
            '
            Me.SplitContainer1.Dock = System.Windows.Forms.DockStyle.Fill
            Me.SplitContainer1.Location = New System.Drawing.Point(0, 0)
            Me.SplitContainer1.Name = "SplitContainer1"
            '
            'SplitContainer1.Panel1
            '
            Me.SplitContainer1.Panel1.Controls.Add(Me.DbPanel1)
            '
            'SplitContainer1.Panel2
            '
            Me.SplitContainer1.Panel2.Controls.Add(Me.DbPanel2)
            Me.SplitContainer1.Size = New System.Drawing.Size(664, 390)
            Me.SplitContainer1.SplitterDistance = 334
            Me.SplitContainer1.TabIndex = 0
            '
            'Timer1
            '
            '
            'DbPanel1
            '
            Me.DbPanel1.Dock = System.Windows.Forms.DockStyle.Fill
            Me.DbPanel1.Location = New System.Drawing.Point(0, 0)
            Me.DbPanel1.Name = "DbPanel1"
            Me.DbPanel1.Size = New System.Drawing.Size(334, 390)
            Me.DbPanel1.TabIndex = 0
            '
            'DbPanel2
            '
            Me.DbPanel2.Dock = System.Windows.Forms.DockStyle.Fill
            Me.DbPanel2.Location = New System.Drawing.Point(0, 0)
            Me.DbPanel2.Name = "DbPanel2"
            Me.DbPanel2.Size = New System.Drawing.Size(326, 390)
            Me.DbPanel2.TabIndex = 0
            '
            'Form1
            '
            Me.AutoScaleDimensions = New System.Drawing.SizeF(6.0!, 13.0!)
            Me.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font
            Me.ClientSize = New System.Drawing.Size(664, 390)
            Me.Controls.Add(Me.SplitContainer1)
            Me.Name = "Form1"
            Me.Text = "Form1 - Hit R to reset panel2"
            Me.SplitContainer1.Panel1.ResumeLayout(False)
            Me.SplitContainer1.Panel2.ResumeLayout(False)
            CType(Me.SplitContainer1, System.ComponentModel.ISupportInitialize).EndInit()
            Me.SplitContainer1.ResumeLayout(False)
            Me.ResumeLayout(False)
    
        End Sub
        Friend WithEvents SplitContainer1 As System.Windows.Forms.SplitContainer
        Friend WithEvents Timer1 As System.Windows.Forms.Timer
        Friend WithEvents DbPanel1 As DBPanel
        Friend WithEvents DbPanel2 As DBPanel
    End Class
    
    Public Class DBPanel
        Inherits Panel
    
        Public Sub New()
            Me.DoubleBuffered = True
        End Sub
    End Class

    Regards,

      Thorsten

    Wednesday, October 26, 2016 10:46 PM

  • ...  I still plan on  implementing a backtracking solver algorithm...

    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Hi,

    this is an interesting task. Its a bit like floodfill plus chaincode in image-editing. So, if the maze is really big, a recursive algorithm could fail for possible stack overflows. In a floodfill algorithm this is circumvented usually by doing it iteratively.

    [just related to a floodfill algorithm, your problem is more complex and needs a different way to start, but maybe this could be used in a later step of processing...: Set up a List, add the first item that should be checked (in four neighboring directions) and then call the check method in a while loop (until the list is empty). Pass that list as parameter to that method and in the check method add the new items to the list and remove the currently checked items from the list...]

    To make a solver, you would of course need to also monitor the chains (all current chosen ways) and remove any cul de sacs from that list of paths, and finally chose the one with the least distance (steps) from start to finish... (Just an idea)

    I think in Graph theory there will be possible help for this task...

    https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

    and

    https://en.wikipedia.org/wiki/Maze_solving_algorithm

    Regards,

      Thorsten

    Wednesday, October 26, 2016 11:00 PM
  •  Hey Paul,  good to see you around again.  8)

     My Good God !!!   I`ll need to get out my SUPER DUPER HUGE magnifying glass and my EXTRA EXTRA FINE pen to do this maze.  haha!!   Nice work!!!

     


    If you say it can`t be done then i`ll try it

    Wednesday, October 26, 2016 11:36 PM
  • Hi Paul!

    I dont have any maze generators but here is a simple shell I made a while ago to play them if modified just to have something to say.

    :)


    Tommy that's good, not sure how I'd implement it. I still plan on  implementing a backtracking solver algorithm...

    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.


    It seems if you know the wall surface is flat, right angles, like Paul's, you can get the angle and follow it to a corner, then decide how to furn. Maybe always turn right? You would eventually follow around to the end?

    Phd type stuff I'm sure.

    Hi Thorsten!


    PS Hi Razerz!
    Wednesday, October 26, 2016 11:40 PM
  •  Hey Paul,  good to see you around again.  8)

     My Good God !!!   I`ll need to get out my SUPER DUPER HUGE magnifying glass and my EXTRA EXTRA FINE pen to do this maze.  haha!!   Nice work!!!


     


    If you say it can`t be done then i`ll try it

    Hey razerz,

    Thanks, lol It's probably like 5 pages wide if it was a normal size.  Was thinking about making laminated posters of giant mazes to sell at the flea market...


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Wednesday, October 26, 2016 11:42 PM
    Moderator

  • Here a copy paste version...

    Draw a path on the left pane, follow it on the right one.

    Thorsten,

    Is this cheating?


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Wednesday, October 26, 2016 11:47 PM
    Moderator
  • Hey razerz,

    Thanks, lol It's probably like 5 pages wide if it was a normal size.  Was thinking about making laminated posters of giant mazes to sell at the flea market...


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

     Not a bad idea.  Maybe poster sized crossword puzzles would sell too.  8)

    If you say it can`t be done then i`ll try it

    Wednesday, October 26, 2016 11:52 PM


  • It seems if you know the wall surface is flat, right angles, like Paul's, you can get the angle and follow it to a corner, then decide how to furn. Maybe always turn right? You would eventually follow around to the end?

    Phd type stuff I'm sure.

    Hi Thorsten!


    PS Hi Razerz!

    Actually, I think I was reading about that at some point, and there is a "right turn" method out there...

    I was thinking about a stack approach, although not sure if it would overflow. I like Thorsten's flood fill idea. I was happy to get this thing working...

    p.s. also did conways game of life, but that was in javascript/html5 canvas...

    Conway's Game of Life

    ...still working on my js version of the maze generator... ugh


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.


    Wednesday, October 26, 2016 11:56 PM
    Moderator

  •  Not a bad idea.  Maybe poster sized crossword puzzles would sell too.  8)

    If you say it can`t be done then i`ll try it

    That thought had crossed my mind, but I hadn't crossed my eyes yet trying to make the algorithm...

    Also want to get to word search generators one day too...


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Wednesday, October 26, 2016 11:59 PM
    Moderator
  • Hi

    As for a backtracker (if that means a solver), I remember,many years ago, a friend and I developed a GO game - not really sophisticated, but it served as a sort of 'referee' type programme and we did use it for a while.

    Anyway, one of the problems we faced was finding groups/enclosed areas etc, and we developed a series of functions to return various aspects of the current layout. One of the main features we used was a 'right hand' search (could have been a left hand search too). This did a quick and efficient job considering we were using a computer of the 1960's era and were not so very fast.

    I can't remember the details, but I remember that we could 'flag' crossings, backtracks and return to start point quite easily.

    I would imaging such a stratagy could be useful in solving a maze (I vaguely remember such algorithms being used in similar ways).


    Regards Les, Livingston, Scotland



    • Edited by leshay Thursday, October 27, 2016 12:38 AM
    Thursday, October 27, 2016 12:08 AM
  • Hi

    As for a backtracker (if that means a solver), I remember,many years ago, a friend and I developed a GO game - not really sophisticated, but it served as a sort of 'referee' type programme and we did use it for a while.

    Anyway, one of the problems we faced was finding groups/enclosed areas etc, and we developed a series of functions to return various aspects of the current layout. One of the main fetures we used was a 'right hand' search(could have been a left hand search too). This did a quick and efficient job considering we were using a computer of the 1960's era and were not so very fast.

    I can't remember the details, but I remember that we could 'flag' crossings, backtracks and return to start point quite easily.

    I would imaging such a stratagy could be useful in solving a maze (I vaguely remember such algorithms being used in similar ways).


    Regards Les, Livingston, Scotland



    Some of the calc area of a polygon things do the right hand stuff I guess thats what I remember. Or maybe its related maze solutions.

    Just speculating it seems a true maze would be one surface followed all the way to the end. Then if you came back on the other side you would end up where you started but on the wall on the other side of the hall.

    Its like an bizaro land inside mobius?

    The mazes were good on the early hardware as they could be printed with a dot matrix char printer.

    Thursday, October 27, 2016 12:32 AM

  • Here a copy paste version...

    Draw a path on the left pane, follow it on the right one.

    Thorsten,

    Is this cheating?


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Yes, you can cheat, in this version, its been just a suggestion for someone. Like:

    But its easy to verify that you have moved the mousepointer close to all pathpoints of the orig path.

    Regards,

      Thorsten

    Thursday, October 27, 2016 1:16 AM

  • I was thinking about a stack approach, although not sure if it would overflow. I like Thorsten's flood fill idea. I was happy to get this thing working...


    ... there's a recursive algorithm in here:

    https://en.wikipedia.org/wiki/Maze_solving_algorithm

    which you could test for overflow issues on large mazes. Actually this is a lot like floodfill and it could be modified to an iterative version.

    Regards,

      Thorsten


    Thursday, October 27, 2016 1:20 AM
  • Hope all is well.

    Here is some code I have had for several years, not mine, no idea who's responsible. It does have a solver. I suggest generating a maze, then turn the speed way way down and hit Solve. It's done in VS2010.

    Thursday, October 27, 2016 3:16 PM
  • Hope all is well.

    Here is some code I have had for several years, not mine, no idea who's responsible. It does have a solver. I suggest generating a maze, then turn the speed way way down and hit Solve. It's done in VS2010.

    Not sure how to incorporate this? :P


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Friday, October 28, 2016 2:51 AM
    Moderator
  • Hope all is well.

    Here is some code I have had for several years, not mine, no idea who's responsible. It does have a solver. I suggest generating a maze, then turn the speed way way down and hit Solve. It's done in VS2010.

    Not sure how to incorporate this? :P


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Ha that is the images from here.

    https://social.msdn.microsoft.com/Forums/vstudio/en-US/8a4dc107-3620-4951-b152-004e2cb3744f/continuation-of-slot-machine-simulation?forum=vbgeneral

    BTW congratulations!

    Friday, October 28, 2016 12:35 PM
  • Hope all is well.

    Here is some code I have had for several years, not mine, no idea who's responsible. It does have a solver. I suggest generating a maze, then turn the speed way way down and hit Solve. It's done in VS2010.

    Not sure how to incorporate this? :P


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Ha that is the images from here.

    https://social.msdn.microsoft.com/Forums/vstudio/en-US/8a4dc107-3620-4951-b152-004e2cb3744f/continuation-of-slot-machine-simulation?forum=vbgeneral

    BTW congratulations!

    Thank Tommy! So excited! It's a girl!!

    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Sunday, October 30, 2016 6:07 PM
    Moderator
  • So I am in the middle of making a routine to save mazes to disk.

    I have come to the following conclusion:

    I can save 2 cells per byte with the following enumeration:

    Public Enum CellWalls As Byte
        None = 0
        West = 1
        East = 2
        EastWest = 3
        South = 4
        SouthWest = 5
        SouthEast = 6
        SouthEastWest = 7
        North = 8
        NorthWest = 9
        NorthEast = 10
        NorthEastWest = 11
        NorthSouth = 12
        NorthSouthWest = 13
        NorthSouthEast = 14
        NorthSouthEastWest = 15
    End Enum

    This enumeration was generated based on the bit positions of the low order nibble in a byte as follows:

    NSEW
    0000
    0001
    0010
    0011
    0100
    0101
    0110
    0111
    1000
    1001
    1010
    1011
    1100
    1101
    1110
    1111

    For instance a cell with walls to the North, South, and West would have a bit signature of:

    1101 in binary, which is 13 in decimal. This allows for modification of only a single bit to change walls, yet a predictable uniform result each time(for later editable versions).

    A maze that is 100 cells wide by 100 cells tall would have maze data in the sum of 5000 bytes.

    100 x 100 = 10000, and since each cell is stored in only 4 bits, we can use 1 byte to store every 2 cells, meaning 10000 / 2 = 5000 bytes.

    I am wondering if this is as optimized as possible, or am I missing something?

    Is there a possible way I can further optimize this to utilize even less disk space for the storage of generated mazes?


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.


    Sunday, November 6, 2016 6:11 PM
    Moderator
  • Hi

    In my opinion, you have full optimization. 1byte = 2 cells each with 4 options - utilizing all 8 bits of every byte.


    Regards Les, Livingston, Scotland

    Sunday, November 6, 2016 6:24 PM
  • Hi

    In my opinion, you have full optimization. 1byte = 2 cells each with 4 options - utilizing all 8 bits of every byte.


    Regards Les, Livingston, Scotland

    I thought so, but sometimes people have some pretty neat tricks up their sleeves... thanks

    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Sunday, November 6, 2016 6:34 PM
    Moderator
  • Hi Paul,

    I dont seem to be able to run the code in your first post. I get an error:

       'System.Collections.Generic.KeyNotFoundException'

    at:

       Private Sub Dig()

           Dim startCell As Cell = cells(key)


    Any ideas what I am missing? I made the form controls etc.

    Sunday, November 6, 2016 7:16 PM
  • Hi Paul,

    I dont seem to be able to run the code in your first post. I get an error:

       'System.Collections.Generic.KeyNotFoundException'

    at:

       Private Sub Dig()

           Dim startCell As Cell = cells(key)


    Any ideas what I am missing? I made the form controls etc.

    hmm.... not sure tommy, did you try downloading the example project from the MSDN Gallery Sample(VB.net & C#)?

    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.


    Sunday, November 6, 2016 7:30 PM
    Moderator
  • I think you will get an error if you use the below, which is in the example. You get an error when the maze is less than 5 wide and 5 tall, because I am starting at col5, row5(c5r5) 


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.



    Sunday, November 6, 2016 7:34 PM
    Moderator
  • I think you will get an error if you use the below, which is in the example. You get an error when the maze is less than 5 wide and 5 tall, because I am starting at col5, row5(c5r5) 


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.



    Yes that was the problem when I set all four on 20 then it goes.

    Sunday, November 6, 2016 8:44 PM
  • I think you will get an error if you use the below, which is in the example. You get an error when the maze is less than 5 wide and 5 tall, because I am starting at col5, row5(c5r5) 


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.



    Yes that was the problem when I set all four on 20 then it goes.

    That's good, but for clarification, the better fix is to change the default key from "c5r5" to "c0r0", I had tested an idea about randomizing the default starting key, and never really implemented it, and to boot, I never changed the default key back to "c0r0".

    This key is essentially the same as an associative array(which are only available in the form of keypairvalue/dictionary in vb.net)


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Sunday, November 6, 2016 9:28 PM
    Moderator
  • I think you will get an error if you use the below, which is in the example. You get an error when the maze is less than 5 wide and 5 tall, because I am starting at col5, row5(c5r5) 


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.



    Yes that was the problem when I set all four on 20 then it goes.

    That's good, but for clarification, the better fix is to change the default key from "c5r5" to "c0r0", I had tested an idea about randomizing the default starting key, and never really implemented it, and to boot, I never changed the default key back to "c0r0".

    This key is essentially the same as an associative array(which are only available in the form of keypairvalue/dictionary in vb.net)


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Yeah. Ok.

    Well I did see that is what the key was, c5r5 that it did not like. I had a 4 x 3 or something.

    I was looking at how you draw it etc of course.

    Not that the drawing part is that critical to the overall thing. Especially with your simple four wall setup and then saving that etc.

    Then I was wondering if the entire thing could be made into single path. I mean the lines or walls. One that connects the lines from one end of the maze to other so it could be followed some how. Not sure why. I am sure there are phd's writing papers as we speak.

    Sunday, November 6, 2016 9:46 PM

  • Yeah. Ok.

    Well I did see that is what the key was, c5r5 that it did not like. I had a 4 x 3 or something.

    I was looking at how you draw it etc of course.

    Not that the drawing part is that critical to the overall thing. Especially with your simple four wall setup and then saving that etc.

    Then I was wondering if the entire thing could be made into single path. I mean the lines or walls. One that connects the lines from one end of the maze to other so it could be followed some how. Not sure why. I am sure there are phd's writing papers as we speak.

    If you look at the algorithm that fetches a neighbor cell while in the middle of the digging process, you will see that any neighbor that is retrieved that hasn't visited gets pushed to the stack, and when the "digger" gets to a point where there are no unvisited neighbors, it instead pops(and returns) the cell that was most recently added to the top of the stack. 

    I am thinking that the maze solving algorithm will work in a similar fashion, where it pushes, and pops from the stack, advancing to only previously unvisited cells, until it reaches the destination cells, at that time, only the cells remaining in the stack should be part of the solution. Still contemplating on this...


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Sunday, November 6, 2016 9:54 PM
    Moderator

  • If you look at the algorithm that fetches a neighbor cell while in the middle of the digging process, you will see that any neighbor that is retrieved that hasn't visited gets pushed to the stack, and when the "digger" gets to a point where there are no unvisited neighbors, it instead pops(and returns) the cell that was most recently added to the top of the stack. 

    I am thinking that the maze solving algorithm will work in a similar fashion, where it pushes, and pops from the stack, advancing to only previously unvisited cells, until it reaches the destination cells, at that time, only the cells remaining in the stack should be part of the solution. Still contemplating on this...


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Oh I see. :)

    Here is a maze from your app that I traced.

                   

    Sunday, November 6, 2016 10:31 PM
  • I updated the mazedigger so it would show its work as it goes, it now also shows how many cells are sitting on the stack during the digging process, watching it do it's work sheds some light on how it works.

    You can download this version of the project here:

    http://paulishak.ml/downloads/mazeNew.zip

    Screenshot:


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Sunday, November 6, 2016 11:18 PM
    Moderator

  •                

    Just saw this... Tommy... That's pretty sweet!

    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Sunday, November 6, 2016 11:29 PM
    Moderator
  • I updated the mazedigger so it would show its work as it goes, it now also shows how many cells are sitting on the stack during the digging process, watching it do it's work sheds some light on how it works.

    You can download this version of the project here:

    http://paulishak.ml/downloads/mazeNew.zip

    Screenshot:


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Very cool !

    So one could save the path its tracing and that is the solution?

    Ha, here you, go sell the maze for $ and the solution for $$.


    Sunday, November 6, 2016 11:56 PM

  • Very cool !

    So one could save the path its tracing and that is the solution?

    Ha, here you, go sell the maze for $ and the solution for $$.


    I'd like to make a book maybe in the near future...

    Unfortunately, I do not believe saving the steps will give me a solution, because there are multiple paths that can be taken to solve it.


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Monday, November 7, 2016 12:05 AM
    Moderator

  • I'd like to make a book maybe in the near future...

    Unfortunately, I do not believe saving the steps will give me a solution, because there are multiple paths that can be taken to solve it.


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Well I dont really understand exactly what the rules are or  what its doing etc.

    In this image that it generates it looks like it went from one end to the other which is "a" solution if that is how you define it. The rest is backfilling, with or without other solutions I guess?


    Monday, November 7, 2016 1:03 AM

  • Well I dont really understand exactly what the rules are or  what its doing etc.

    In this image that it generates it looks like it went from one end to the other which is "a" solution if that is how you define it. The rest is backfilling, with or without other solutions I guess?


    Well this is how it works:

    Recursive backtracker

    The depth-first search algorithm of maze generation is frequently implemented using backtracking.

    1. Make the initial cell the current cell and mark it as visited
    2. While there are unvisited cells
      1. If the current cell has any neighbours which have not been visited
        1. Choose randomly one of the unvisited neighbours
        2. Push the current cell to the stack
        3. Remove the wall between the current cell and the chosen cell
        4. Make the chosen cell the current cell and mark it as visited
      2. Else if stack is not empty
        1. Pop a cell from the stack
        2. Make it the current cell

    By the time the algorithm is done generating the maze, there is nothing left on the stack, also, along the way no particular cell is aware of future random diggings, so there is no real way to identify which cells to keep track of, so this can't be used as a solution.

    Although, I'm sure a similar algorithm can be ran after the maze is completely generated...


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.


    Monday, November 7, 2016 1:09 AM
    Moderator
  • Paul,

    I saved the path and then draw with blue line. It takes several tries to get a nice ones like these. Most fill the whole space more or less. It shows a solution from upper left corner to lower right. The code just shows where I saved the path.

       Public Sub draw(pathComplete As Boolean, ByRef pts As List(Of Point), g As Graphics, Optional currentCell As Cell = Nothing)
            If Not currentCell Is Nothing AndAlso currentCell Is Me Then
                g.FillRectangle(Brushes.Red, Me.Bounds)
                If Not pathComplete Then
                    Dim pt As New Point(Bounds.X, Bounds.Y)
                    pts.Add(pt)
                End If
            End If

    Monday, November 7, 2016 3:33 AM
  • Paul,

    I saved the path and then draw with blue line. It takes several tries to get a nice ones like these. Most fill the whole space more or less. It shows a solution from upper left corner to lower right. The code just shows where I saved the path.

       Public Sub draw(pathComplete As Boolean, ByRef pts As List(Of Point), g As Graphics, Optional currentCell As Cell = Nothing)
            If Not currentCell Is Nothing AndAlso currentCell Is Me Then
                g.FillRectangle(Brushes.Red, Me.Bounds)
                If Not pathComplete Then
                    Dim pt As New Point(Bounds.X, Bounds.Y)
                    pts.Add(pt)
                End If
            End If

    Cool, is that piece of code all you changed?

    What do I need to do to implement?


    Book session on Codementor
    Don't forget to vote for Helpful Posts and Mark Answers!
    *This post does not reflect the opinion of Microsoft, or its employees.

    Monday, November 7, 2016 3:36 AM
    Moderator
  • No there is are just a few more lines of code in a couple spots. I am embarrassed to show it as its just a quick thing to see if it works. I see how to improve already. I am sure you can do better.

    Here are the pieces I changed in your last download link. I took out the rtb and put the graphicspanel1. It just save the points you draw with the red square.

    'form1 AddHandler maze.MazeComplete, Sub(m As Image) Panel1.BackgroundImage = m Panel1.BackgroundImageLayout = ImageLayout.None Panel1.Width = m.Width Panel1.Height = m.Height Label2.Text = maze.StackSize.ToString 'maze.MazeName = "TEST MAZE 1" GraphicsPanel1.Size = Panel1.Size GraphicsPanel1.Invalidate() End Sub 'form1 Private Sub GraphicsPanel1_Paint(sender As Object, e As PaintEventArgs) Handles GraphicsPanel1.Paint If maze IsNot Nothing AndAlso maze.PathPoints.Count > 0 Then Using pth As New Drawing2D.GraphicsPath pth.AddLines(maze.PathPoints.ToArray) e.Graphics.Clear(Color.White) e.Graphics.DrawPath(New Pen(Color.Blue, 3), pth) End Using End If End Sub Public Class Maze Inherits Control

    'add these Public PathPoints As New List(Of Point) Public PathComplete As Boolean Sub updateMaze(isDigger As Boolean, Optional currentCell As Cell = Nothing) Dim Maze As New Bitmap(Width, Height) Using g As Graphics = Graphics.FromImage(Maze) g.Clear(Color.White) Dim r As Integer = 0 Dim c As Integer = 0 PathComplete = False If cells.Count > 0 Then For r = 0 To Me.Rows - 1 For c = 0 To Me.Columns - 1 Dim cell As Cell = cells("c" & c & "r" & r) If isDigger AndAlso Not currentCell Is Nothing Then cell.draw(PathComplete, PathPoints, g, currentCell) Else cell.draw(PathComplete, PathPoints, g) End If If PathPoints.Count > 0 Then If PathPoints(PathPoints.Count - 1).Y > (Rows - 2) * cellHeight AndAlso PathPoints(PathPoints.Count - 1).X > (Columns - 2) * cellWidth Then PathComplete = True End If End If Next Next End If Me.Maze = Maze End Using End Sub 'cell class Public Sub draw(pathComplete As Boolean, ByRef pts As List(Of Point), g As Graphics, Optional currentCell As Cell = Nothing) If Not currentCell Is Nothing AndAlso currentCell Is Me Then g.FillRectangle(Brushes.Red, Me.Bounds) If Not pathComplete Then Dim pt As New Point(Bounds.X, Bounds.Y) pts.Add(pt) End If End If If Me.Visited Then If NorthWall Then g.DrawLine(Pen, New Point(Bounds.Left, Bounds.Top), New Point(Bounds.Right, Bounds.Top)) If SouthWall Then g.DrawLine(Pen, New Point(Bounds.Left, Bounds.Bottom), New Point(Bounds.Right, Bounds.Bottom)) If WestWall Then g.DrawLine(Pen, New Point(Bounds.Left, Bounds.Top), New Point(Bounds.Left, Bounds.Bottom)) If EastWall Then g.DrawLine(Pen, New Point(Bounds.Right, Bounds.Top), New Point(Bounds.Right, Bounds.Bottom)) Else If NorthWall Then g.DrawLine(Pens.Red, New Point(Bounds.Left, Bounds.Top), New Point(Bounds.Right, Bounds.Top)) If SouthWall Then g.DrawLine(Pens.Red, New Point(Bounds.Left, Bounds.Bottom), New Point(Bounds.Right, Bounds.Bottom)) If WestWall Then g.DrawLine(Pens.Red, New Point(Bounds.Left, Bounds.Top), New Point(Bounds.Left, Bounds.Bottom)) If EastWall Then g.DrawLine(Pens.Red, New Point(Bounds.Right, Bounds.Top), New Point(Bounds.Right, Bounds.Bottom)) End If End Sub


    PS
    Or you can draw the path in the updatemaze sub to combine them like I did in the first example image.
    Monday, November 7, 2016 3:48 AM
  • That one long red example was the best easy one yet.

    Here are two put together to make a simple single "solution" path? The other areas would be filled with dead ends.

    Are there degrees of difficulty?

    In fact, assuming one wants it, one could generate the "solution" path and then backfill in from that! Thereby having only one solution as all the fill would be dead ends staring from the main path. The solution could be a nice winding path through the space.

    Monday, November 7, 2016 5:07 AM